Counting points on smooth plane quartics

DOI10.1007/S40993-022-00397-8MaRDI QIDQ6408397arXivFDO

Authors Edgar Costa, David Harvey, Andrew V. Sutherland

Publication date 21 August 2022

Published in arXiv

Full work available at URL https://doi.org/10.1007/S40993-022-00397-8

Mathematics Subject Classification ID

Curves over finite and local fields (11G20) (L)-functions of varieties over global fields; Birch-Swinnerton-Dyer conjecture (11G40) Number-theoretic algorithms; complexity (11Y16) Zeta functions and related questions in algebraic geometry (e.g., Birch-Swinnerton-Dyer conjecture) (14G10)

arXiv classification

math.NT

Abstract: We present efficient algorithms for counting points on a smooth plane quartic curve $X$ modulo a prime $p$. We address both the case where $X$ is defined over $mathbb{F}_p$ and the case where $X$ is defined over $mathbbQ$ and $p$ is a prime of good reduction. We consider two approaches for computing $$, one which runs in $O(plogploglogp)$ time using $O(logp)$ space and one which runs in $O(p^{1/2}lo{g}^2!p)$ time using $O(p^{1/2}logp)$ space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for $X/mathbbQ$ that compute $$ for good primes $pleN$ in $O(Nlo{g}^3!N)$ time using $O(N)$ space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of $mathbb{P}^1$, which in combination with previous results addresses all curves of genus $gle3$. Our algorithms also compute Cartier-Manin/Hasse-Witt matrices that may be of independent interest.

This page was built for publication: Counting points on smooth plane quartics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408397)