## Counting solutions to equations in many variables over finite fields.(English)Zbl 1076.11040

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.

### MSC:

 11G25 Varieties over finite and local fields 14G15 Finite ground fields in algebraic geometry 11D45 Counting solutions of Diophantine equations 11M38 Zeta and $$L$$-functions in characteristic $$p$$ 11Y16 Number-theoretic algorithms; complexity 14F30 $$p$$-adic cohomology, crystalline cohomology
Full Text: