Counting solutions to equations in many variables over finite fields (Q1767486)

Let \(\mathbb{F}_q\) be the finite field with \(q\) elements. Let \(f\in\mathbb{F}_q[x_1,\dots, x_n]\) be homogeneous of degree \(d\), where \(n\geq 2\). For \(k\geq 1\), denote by \(N_k\) the number of \(\mathbb{F}_{q^k}\)-rational points on the projective hypersurface defined by the equation \(f= 0\). The zeta function of the projective surface defined by \(f\) is \[ Z(f/\mathbb{F}_q,T)= \exp\Biggl(\sum^\infty_{k=1} N_k{T^k\over k}\Biggr). \] By a classical theorem of Dwork \(Z(f/\mathbb{F}_q,T)\) is a rational function. In this paper the author proves that there exists an explicit deterministic algorithm with the following input, output and bit complexity. The input is a polynomial \(f\in\mathbb{F}_q[x_1,\dots, x_n]\) in an explicit Zariski dense open subset of the space of homogeneous polynomials of degree \(d\) in \(n\) variables over \(\mathbb{F}_q\) with \(\text{gcd}(d,q)= 1\) and \(q\) is not a power of 2. The output is the zeta function \(Z(f/\mathbb{F}_q,T)\) of the projective surface defined by \(f\). The algorithm requires \((pd^n\log(q))^{O(1)}\) bit operations. An interesting consequence of this result is that for any explicit polynomial \(f\in\mathbb{Z}[x_1,\dots, x_n]\), \(f\neq 0\), and \(\varepsilon> 0\) there exists an explicit deterministic algorithm which takes as input a prime \(p\), gives as output the number of solutions to the equation \(f\equiv 0\pmod p\) and takes \(O(p^{2+\varepsilon})\) bit operations.