Polynomials Modulo Composite Numbers: Ax-Katz type theorems for the structure of their solution sets
Preprint
Abstract
We extend the Ax-Katz theorem for a single polynomial from finite fields to the rings Z_m with m composite. This extension not only yields the analogous result, but gives significantly higher divisibility bounds. We conjecture what computer runs suggest is the optimal result for any m, and prove a special case of it. The special case is for m = 2^r and polynomials of degree 2. Our results also yield further properties of the solution spaces. Polynomials modulo composites are the focus of some computational complexity lower bound frontiers, while those modulo 2^r arise in the simulation of quantum circuits. We give some prospective applications of this research.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Warning’s Second Theorem with restricted variablesCombinatorica, 2016
- Graph Homomorphisms with Complex Values: A Dichotomy TheoremSIAM Journal on Computing, 2013
- A partial improvement of the Ax–Katz theoremJournal of Number Theory, 2012
- Chevalley’s theorem with restricted variablesCombinatorica, 2011
- Dilation of Newton Polytope and p-adic EstimateDiscrete & Computational Geometry, 2010
- Improvements upon the Chevalley–Warning–Ax–Katz-type estimatesJournal of Number Theory, 2007
- Improved simulation of stabilizer circuitsPhysical Review A, 2004
- Tight bounds for Chevalley–Warning–Ax–Katz type estimates, with improved applicationsProceedings of the London Mathematical Society, 2004
- Zeroes of Polynomials Over Finite FieldsAmerican Journal of Mathematics, 1964
- On the Rationality of the Zeta Function of an Algebraic VarietyAmerican Journal of Mathematics, 1960