×

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
PDF BibTeX XML Cite
Full Text: DOI