Computing zeta functions of generic projective hypersurfaces in larger characteristic

Tuitman, Jan

doi:10.1090/mcom/3325

Computing zeta functions of generic projective hypersurfaces in larger characteristic
HTML articles powered by AMS MathViewer

by Jan Tuitman HTML | PDF

Math. Comp. 88 (2019), 439-451 Request permission

Abstract:

We give an improvement of the deformation method for computing the zeta function of a generic projective hypersurface over a finite field of characteristic $p$ that reduces the dependence of the complexity on $p$ to $\tilde {O}(p^{1/2})$ while remaining polynomial in the other input parameters.

References

T. G. Abbott, K. S. Kedlaya, and D. Roe. Bounding Picard numbers of surfaces using $p$-adic cohomology, Arithmetic, Geometry, and Coding Theory (AGCT-10), 2006.
Pierre Berthelot, Géométrie rigide et cohomologie des variétés algébriques de caractéristique $p$, Mém. Soc. Math. France (N.S.) 23 (1986), 3, 7–32 (French, with English summary). Introductions aux cohomologies $p$-adiques (Luminy, 1984). MR 865810
Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777–1806. MR 2299425, DOI 10.1137/S0097539704443793
W. Castryck, J. Denef, and F. Vercauteren, Computing zeta functions of nondegenerate curves, IMRP Int. Math. Res. Pap. (2006), Art. ID 72017, 57. MR 2268492
D. V. Chudnovsky and G. V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, Ramanujan revisited (Urbana-Champaign, Ill., 1987) Academic Press, Boston, MA, 1988, pp. 375–472. MR 938975
David Harvey, Kedlaya’s algorithm in larger characteristic, Int. Math. Res. Not. IMRN 22 (2007), Art. ID rnm095, 29. MR 2376210, DOI 10.1093/imrn/rnm095
David Harvey, Computing zeta functions of arithmetic schemes, Proc. Lond. Math. Soc. (3) 111 (2015), no. 6, 1379–1401. MR 3447797, DOI 10.1112/plms/pdv056
Hendrik Hubrechts, Memory efficient hyperelliptic curve point counting, Int. J. Number Theory 7 (2011), no. 1, 203–214. MR 2776016, DOI 10.1142/S1793042111004034
Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. MR 1877805
Alan G. B. Lauder, Counting solutions to equations in many variables over finite fields, Found. Comput. Math. 4 (2004), no. 3, 221–267. MR 2078663, DOI 10.1007/s10208-003-0093-y
Alan G. B. Lauder, Deformation theory and the computation of zeta functions, Proc. London Math. Soc. (3) 88 (2004), no. 3, 565–602. MR 2044050, DOI 10.1112/S0024611503014461
Alan G. B. Lauder and Daqing Wan, Counting points on varieties over finite fields of small characteristic, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 579–612. MR 2467558
Sebastian Pancratz and Jan Tuitman, Improvements to the deformation method for counting points on smooth projective hypersurfaces, Found. Comput. Math. 15 (2015), no. 6, 1413–1464. MR 3413626, DOI 10.1007/s10208-014-9242-8
Jan Tuitman, Counting points on curves using a map to $\mathbf {P}^1$, Math. Comp. 85 (2016), no. 298, 961–981. MR 3434890, DOI 10.1090/mcom/2996
Jan Tuitman, Counting points on curves using a map to $\mathbf {P}^1$, II, Finite Fields Appl. 45 (2017), 301–322. MR 3631366, DOI 10.1016/j.ffa.2016.12.008