Session S34 - Symbolic and Numerical Computation with Polynomials

Friday, July 16, 14:45 ~ 15:15 UTC-3

Sub-Linear Point Counting for Arbitrary Curves Over Prime Power Rings

J. Maurice Rojas

Texas A&M University, USA   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ have degree $d$ and all coefficients in $\{0,\ldots,p^{k-1}\}$. We give the first algorithm, with complexity sub-linear in $p$, to count the number of roots of $f$ over $\mathbb{Z}/(p^k)$: Our Las Vegas randomized algorithm works in time $(dk\log p)^{O(1)}\sqrt{p}$. The key is an efficient reduction from point counting over prime power rings to point counting over finite fields. Another consequence of our work is a recurrence that simplifies the computation of p-adic Igusa local zeta functions for curves.

The practical importance of our work is that it is faster than performing a resolution of singularities on the underlying curve and then applying a multivariate version of Hensel's Lemma. In particular, our algorithm sets the stage for point counting in higher dimensions, where resolution of singularities has completely impractical complexity.

Joint work with Caleb Robelle, University of Maryland, Baltimore County and Yuyu Zhu, Texas A&M University.

View abstract PDF