Sub-Linear Point Counting for Variable Separated Curves over Prime Power Rings
share
Let k,p∈ℕ with p prime and let f∈ℤ[x_1,x_2] be a bivariate polynomial with degree d and all coefficients of absolute value at most p^k. Suppose also that f is variable separated, i.e., f=g_1+g_2 for g_i∈ℤ[x_i]. We give the first algorithm, with complexity sub-linear in p, to count the number of roots of f over ℤ mod p^k for arbitrary k: Our Las Vegas randomized algorithm works in time (dklog p)^O(1)√(p), and admits a quantum version for smooth curves working in time (dlog p)^O(1)k. Save for some subtleties concerning non-isolated singularities, our techniques generalize to counting roots of polynomials in ℤ[x_1,…,x_n] over ℤ mod p^k. Our techniques are a first step toward efficient point counting for varieties over Galois rings (which is relevant to error correcting codes over higher-dimensional varieties), and also imply new speed-ups for computing Igusa zeta functions of curves. The latter zeta functions are fundamental in arithmetic geometry.
READ FULL TEXT