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

$$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

$$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

$$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

$$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

$$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.