Lauder: Counting Solutions to Equations in Many Variables over Finite Fields

We present an algorithm which allows us to count solutions to a homogeneous equation $ f(X_1,\dots,X_n) \in \mathbb{F}_q[X_1,\dots,X_n]$ of degree $ d$ (for simplicity we assume $ d \geq 2$, $ n \geq 2$) with running time which does not increase exponentially in number of variables. In other words, we are interested in computing the number of projective solutions

$\displaystyle N_k=\char93 \{(x_1:\dots:x_n) \in \mathbb{P}^{n-1}_{\mathbb{F}_{q^k}}:f(x_1,\dots,x_n)=0\} $

for every $ k \geq 1$. We encode these numbers in the generating function

$\displaystyle Z(f,T)=\exp(\textstyle{\sum}_k N_k T^k/k) \in \mathbb{Q}[[T]] $

which, by a theorem of Dwork, is in fact a rational function. We assume that $ f$ is nonsingular, i.e. $ f$ and $ \partial f/\partial x_i$ for $ i=1,\dots,n$ have no common projective solution. In this situation, we know that

$\displaystyle Z(f,T)=\frac{P(T)^{(-1)^{n+1}}}{(1-T)(1-qT)\dots(1-q^{n-2}T)} $

where $ \deg P=(1/d)((d-1)^n+(-1)^n(d-1))$.

If we compute $ N_k$ naively for $ k=1,\dots,\deg P$ then we can of course recover the polynomial $ P(T)$; the time required to do this, however, requires $ (q^{\deg P})^n \approx 2^{d^{n-1}\log q}$ evaluations of $ f$. The input is given by $ \binom{d+n-1}{n-1} \leq d^{n-1}$ terms of size $ \log q$, and the output size is approximately $ (d^{n-1}\log q)^{O(1)}$. We would like the running time to be polynomial in this quantity.

If $ n=2$, we are counting solutions of a univariate polynomial, and this can be done in time $ (d \log q)^{O(1)}$. For $ n=3$, we have an algorithm of Schoof-Pila for curves which has run time $ (\log q)^{\Delta}$ where $ \Delta$ depends on $ d$ exponentially. In general, there is an algorithm (due to L. and Wan) which runs in time $ (pd^n\log q)^{O(n)}$. Notice the $ n$ in the exponent--we would like to lose this dependence.

The new result: If $ f$ is `sufficiently generic' (we exclude a Zariski closed set which is efficiently computable), $ p \neq 2$, and $ p \nmid d$, then we can find $ P(T)$ using $ (pd^n\log q))^{O(1)}$ bit operations. As a corollary, we see that if $ f \in \mathbb{Z}[X_1,\dots,X_n]$ is sufficiently generic, then there exists an algorithm which takes as input a prime $ p$, outputs the number of solutions $ f \bmod p=0$, and has run time $ O(p^{2+\epsilon})$.

Recall that $ P(T)=\det(I-T{\mathrm{Frob}}_q\vert H^{n-2}(X))$, where we write $ X$ for the projective variety defined by the equation $ f=0$. The action of $ {\mathrm{Frob}}_q$ can be represented by a matrix with entries in a field of characteristic zero, and we find that

$\displaystyle N_k=(-1)^n {\mathrm{Tr}}({\mathrm{Frob}}_q^k\vert H^{n-2}(X))+1+q^k+\dots+(q^k)^{n-2}. $

For curves, for example, the dimension is $ n-2=1$, and $ H^1(X)$ is a $ \mathbb{Z}_\ell$-module, for $ \ell \neq p$.

Instead, we work with the $ p$-adic theory, where $ H^{n-2}(X)$ is a $ R$-module for a ring $ R \supset \mathbb{Z}_p$. We compute instead $ {\mathrm{Frob}}_q={\mathrm{Frob}}_p^{\log_p(q)}$, and compute the matrix of $ {\mathrm{Frob}}_p\vert H^{n-2}(X)$. (Specifically, $ R=\mathbb{Q}_q(\pi)$ where $ \mathbb{Q}_q$ is the unramified extension of $ \mathbb{Q}_p$ of degree $ \log_p q$ and $ \pi^{p-1}=-p$. Also our $ H^{n-2}(X)$ is actually the primitive part of the cohomology space.) Consider the family

$\displaystyle f_Y=\sum_{i=1}^n a_iX_i^d + Yh(X_1,\dots,X_n), $

and assume that $ a_1 \dots a_n \neq 0$. Then $ f_1=f$ and $ f_0$ is a diagonal form, for which it is easy to count the number of solutions. Now $ {\mathrm{Frob}}_p(Y)$ is a $ p$-adic analytic function with the property that $ {\mathrm{Frob}}_p(Y)$ evaluated at a Teichmuller lift of $ y^{1/p}$ is exactly the $ {\mathrm{Frob}}_p$ associated to $ f_y$.

We see that $ {\mathrm{Frob}}_p(Y)=C(Y^p)^{-1}{\mathrm{Frob}}_p(0)C^{\tau-1}(Y)$ where $ \tau \bmod p:\alpha \mapsto \alpha^p$, and $ C(Y)$ is a matrix of power series around the origin satisfying the differential equation $ dC/dY=C(Y)B(Y)$ with initial condition $ C(0)=I$, where $ B(Y)$ is easily computed. This gives a way to compute $ {\mathrm{Frob}}_p(Y)$ in a radius around the origin, and we need to extend this to the closed disc of radius $ 1$.

The entries of the matrices are $ p$-adic holomorphic functions, so to compute these modulo a power of $ p$ we find rational functions with denominators corresponding to the values of $ Y$ where the variety becomes singular and then recover the numerator from the power series. Using overconvergence we get a bound on the degree of these rational functions. We evaluate the rational functions at $ Y=1$. One gets nice complexity because we work with univariate power series, with decay in the coefficients on the order of $ 1/p$, and one needs to take the power of $ p$ approximately on the order of $ d^n \log q$.

In the old algorithm, we would work in $ H^{n-2}(X)$, the ring of power series in $ X_1,\dots,X_n$ over an $ R=\mathbb{Q}_p^{(m)}(\pi)$ where $ \mathbb{Q}_p^{(m)}$ is the unramified extension of $ \mathbb{Q}_p$ of degree $ m$ (if $ q=p^m$) and $ \pi^{p-1}=-p$ modulo an infinite subspace; the power series we must work with have on the order of $ (pd^n\log q)^n$ terms.

Problem. Find an algorithm which counts the number of points on a curve in time $ (d \log q)^{O(1)}$.

Back to the main index for Future directions in algorithmic number theory.