Counting solutions to equations in many variables over finite fields (Q1767486): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Dimitrios Poulakis / rank | |||
Property / reviewed by | |||
Property / reviewed by: Dimitrios Poulakis / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10208-003-0093-y / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2000578879 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 21:03, 19 March 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