Computation of étale cohomology on curves in single exponential time

Jin, Jinbi

Journal de théorie des nombres de Bordeaux, Volume 32 (2020) no. 2, pp. 311-354.

In this paper, we describe an algorithm that, for a smooth connected curve $X$ over a field $k$, a finite locally constant sheaf $𝒜$ on $X_{\mathrm{ét}}$ of abelian groups of torsion invertible in $k$, computes the first étale cohomology ${\mathrm{H}}^1(X_{k^{\mathrm{sep}},\mathrm{ét}},𝒜)$ and the first étale cohomology with proper support ${\mathrm{H}}_c^1(X_{k^{\mathrm{sep}},\mathrm{ét}},𝒜)$ as sets of torsors.

The complexity of this algorithm is exponential in $n^{logn}$, $p_a\left(X\right)$, and $p_a\left(𝒜\right)$, where $p_a\left(X\right)$ is the arithmetic genus of the normal completion of $X$, $p_a\left(𝒜\right)$ is the arithmetic genus of the normal completion $Y$ of the smooth curve representing $𝒜$, and $n$ is the degree of $Y$ over $X$.

The computation in this algorithm is done via the computation of a groupoid scheme classifying the $𝒜$-torsors with some extra rigidifying data.

Dans ce texte, on décrit un algorithme calculant, pour une courbe lisse et connexe $X$ sur un corps $k$ et un faisceau localement constant de groupes abéliens de torsion inversible dans $k$, le premièr groupe de cohomologie étale ${\mathrm{H}}^1(X_{k^{\mathrm{sep}},\mathrm{ét}},𝒜)$ et le premièr groupe de cohomologie étale à support propre ${\mathrm{H}}_c^1(X_{k^{\mathrm{sep}},\mathrm{ét}},𝒜)$ comme ensembles de torseurs.

La complexité arithmétique de cet algorithme est exponentielle en $n^{logn}$, $p_a\left(X\right)$, et $p_a\left(𝒜\right)$, où $p_a\left(X\right)$ est le genre arithmétique de la complétion normale de $X$ sur $k$, $p_a\left(𝒜\right)$ est le genre arithmétique de la complétion normale de la courbe $Y$ répresentant le faisceau $𝒜$, et $n$ est le degré de $Y$ sur $X$.

L’algorithme passe par le calcul d’un schéma en groupoïdes classifiant les $𝒜$-torseurs étales avec quelques structures additionnelles rigidifiantes.

Classification: 14F20, 14Q05, 14Q20
Keywords: Algebraic geometry, Algorithm, Curves, Étale cohomology

[1] Berkowitz, Stuart J. On computing the determinant in small parallel time using a small number of processors, Inf. Process. Lett., Volume 18 (1984), pp. 147-150 | DOI | MR | Zbl

[2] Chistov, Alexander Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time, J. Sov. Math., Volume 34 (1986) no. 4, pp. 1838-1882 (Translated from Zap. Nauchn. Sem. S.-Petersburg, 137:124–188, 1984) | DOI | Zbl

[3] Computational aspects of modular forms and Galois representations (Couveignes, Jean-Marc; Edixhoven, Sebastiaan J., eds.), Annals of Mathematics Studies, 176, Princeton University Press, 2011 | MR | Zbl

[4] Dedekind, Richard; Weber, Heinrich Theorie der algebraischen Funktionen einer Veränderlichen, J. Reine Angew. Math. (1882)

[5] Deligne, Pierre Cohomologie étale, Lecture Notes in Mathematics, 569, Springer, 1977 | Zbl

[6] Deligne, Pierre Le déterminant de la cohomologie, Current trends in arithmetical algebraic geometry (Contemporary Mathematics), Volume 67, American Mathematical Society, 1987, pp. 93-177 | DOI | Zbl

[7] Dickenstein, Alicia; Fitchas, Noaï; Giusti, Marc; Sessa, Carmen The membership problem for unmixed polynomial ideals is solvable in single exponential time, Discrete Appl. Math., Volume 33 (1991), pp. 73-94 | DOI | MR | Zbl

[8] Diem, Claus On arithmetic and the discrete logarithm problem in class groups of curves, 2008 (Habilitation thesis) | Zbl

[9] Ferrand, Daniel Un foncteur norme, Bull. Soc. Math. Fr., Volume 126 (1998), pp. 1-49 | DOI | Numdam | MR | Zbl

[10] Fu, Lei Étale cohomology theory, Nankai Tracts in Mathematics, 14, World Scientific, 2015 | Zbl

[11] Görtz, Ulrich; Wedhorn, Torsten Algebraic geometry I. Schemes. With examples and exercises, Advanced Lectures in Mathematics, Vieweg+Teubner, 2010 | DOI | Zbl

[12] Grothendieck, Alexander Éléments de Géométrie Algébrique II. Etude globale élémentaire de quelques classes de morphismes, Publ. Math., Inst. Hautes Étud. Sci., Volume 8 (1961), pp. 5-222 | Numdam

[13] Grothendieck, Alexander Revêtements étales et groupe fondamental (SGA1), Lecture Notes in Mathematics, 224, Springer, 1971

[14] Harvey, David Counting points on hyperelliptic curves in average polynomial time, Ann. Math., Volume 179 (2014) no. 2, pp. 783-803 | DOI | MR | Zbl

[15] Hess, Florian Computing Riemann–Roch spaces in algebraic function fields and related topics, J. Symb. Comput., Volume 33 (2002) no. 4, pp. 425-445 | DOI | MR | Zbl

[16] Kaltofen, Erich Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput., Volume 14 (1985) no. 2, pp. 469-489 | DOI | MR | Zbl

[17] Kedlaya, Kiran S. Counting points on hyperelliptic curves using Monsky–Washnitzer cohomology, J. Ramanujan Math. Soc., Volume 16 (2001) no. 4, pp. 323-338 | MR | Zbl

[18] Khuri-Makdisi, Kamal Asymptotically fast group operations on Jacobians of general curves (2004) (https://arxiv.org/abs/math/0409209v2) | Zbl

[19] Lauder, Alan; Wan, Daqing Counting points on varieties over finite fields of small characteristic, Algorithmic Number Theory (Mathematical Sciences Research Institute Publications), Volume 44, Cambridge University Press, 2008 | MR

[20] Lieblich, Max Galois representations arising from p-divisible groups, Ph. D. Thesis, Harvard University (2000)

[21] Madore, David A.; Orgogozo, Fabrice Calculabilité de la cohomologie étale modulo $\ell$, Algebra Number Theory, Volume 9 (2015) no. 7, pp. 1647-1739 | DOI | Zbl

[22] Poonen, Bjorn; Testa, Damiano; van Luijk, Ronald Computing Néron–Severi groups and cycle class groups, Compos. Math., Volume 151 (2015) no. 4, pp. 713-734 | DOI | Zbl

[23] Stacks Project Authors Stacks Project, 2014 (http://stacks.math.columbia.edu)