Polynomials Modulo Composite Numbers: Ax-Katz type theorems for the structure of their solution sets

2014/04/18 by Robert L. Surowka, Surowka, Robert L., Kenneth W. Regan +1
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1404.4852

openalex publication_date 2014/04/18 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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.

Related

• Quadratic polynomials of small modulus cannot represent OR
• Computing Elementary Symmetric Polynomials with a Sublinear Number of Multiplications
• On some properties of polynomial composites
• Comparing EQP and MOD_p^kP using Polynomial Degree Lower Bounds
• A polynomial composites and monoid domains as algebraic structures and their applications