Counting solutions to equations in many variables over finite fields
algorithmdeformation theoryDwork cohomologyfinite fieldhomogeneous polynomialprojective hypersurfacezeta function
Counting solutions of Diophantine equations (11D45) Varieties over finite and local fields (11G25) Zeta and (L)-functions in characteristic (p) (11M38) Number-theoretic algorithms; complexity (11Y16) (p)-adic cohomology, crystalline cohomology (14F30) Finite ground fields in algebraic geometry (14G15)
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.
- Counting solutions to generalized Markoff-Hurwitz-type equations in finite fields
- Rigid cohomology and \(p\)-adic point counting
- Improved explicit estimates on the number of solutions of equations over a finite field
- Solutions of equations over finite fields: enumeration via bijections
- A Recursive Method for Computing Zeta Functions of Varieties
- Computing zeta functions of arithmetic schemes
- Computing zeta functions of a hypersurface over finite field F_q
- Faster p-adic feasibility for certain multivariate sparse polynomials
- Counting solutions to some polynomial equations over finite fields
- Nonstandard rank-one nonincreasing maps on symmetric matrices
- Computing zeta functions of generic projective hypersurfaces in larger characteristic
- Deformation theory and the computation of zeta functions
- scientific article; zbMATH DE number 1408418 (Why is no real title available?)
- Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
- A numerical transcendental method in algebraic geometry: computation of Picard groups and related invariants
- Randomized polynomial-time root counting in prime power rings
- Deterministic equation solving over finite fields
- Point Counting on Singular Hypersurfaces
- Counting roots for polynomials modulo prime powers
- Zeta functions of nondegenerate hypersurfaces in toric varieties via controlled reduction in p-adic cohomology
- Solving polynomial systems over non-fields and applications to modular polynomial factoring
- Flux vacua and modularity for \(\mathbb{Z}_2\) symmetric Calabi-Yau manifolds
- Local zeta functions of multiparameter Calabi-Yau threefolds from the Picard-Fuchs equations
- Modular Calabi-Yau fourfolds and connections to M-theory fluxes
- Improvements to the deformation method for counting points on smooth projective hypersurfaces
- Fast arithmetic in unramified \(p\)-adic fields
This page was built for publication: Counting solutions to equations in many variables over finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1767486)
