Counting solutions to equations in many variables over finite fields (Q1767486): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q293716 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Dimitrios Poulakis / rank | |||
Normal rank |
Revision as of 22:49, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting solutions to equations in many variables over finite fields |
scientific article |
Statements
Counting solutions to equations in many variables over finite fields (English)
0 references
11 March 2005
0 references
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.
0 references
finite field
0 references
homogeneous polynomial
0 references
projective hypersurface
0 references
zeta function
0 references
algorithm
0 references
Dwork cohomology
0 references
deformation theory
0 references