Removing restrictions from hyperelliptic zeta algorithms

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a smooth projective geometrically connected curve $C/\mathbb F_q$, where $q=p^n$ and $p$ is prime, define \[ Z_C(T)=\exp\left(\sum_{r\ge1}\#C(\mathbb F_{q^r})\frac{T^r}{r}\right)=\frac{P_C(T)}{(1-T)(1-qT)}. \] Here $P_C\in\mathbb Z[T]$ has degree $2g$, with $g$ the genus. Computing the zeta function means determining this integer polynomial. A hyperelliptic curve has a degree-two map to the projective line. In odd characteristic, the imaginary model in the slides is the smooth completion of $y^2=P(x)$ with $P$ monic squarefree of degree $2g+1$, having a single point above infinity. The corresponding real case has the even-degree model and two geometric points above infinity. The symbol $\widetilde O$ suppresses logarithmic factors; the slides consider small characteristic, with $p$ fixed in the complexity estimates.

Statement recorded in the supplied source.

Extend hyperelliptic zeta computation to the real case and to characteristic $p=2$, retaining the bounds \[ \text{time }\widetilde O(g^3n^4),\qquad \text{space }\widetilde O(g^3n^3),\qquad q=p^n. \] Thus remove both the imaginary-model restriction and the requirement $p\ne2$ from the stated bounds. [S2]

Short English statement

Remove the two model/characteristic restrictions without worsening the displayed hyperelliptic zeta time and memory bounds.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800013 (AMR-087-0013). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Kiran S. Kedlaya, Recent results on p-adic computation of zeta functions, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), logical slides 11--13, PDF pages 24--26. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6220.pdf.