we-solve (beta)

CS-15 · computer science · mathematics · Computational algebra and number theory · Computational complexity

Derandomization of Polynomial Identity Testing

Status OpenLLM status Open unverified

Statement

Definitions and mathematical statement

An arithmetic circuit over a specified effective field has variables and field constants as inputs and addition and multiplication gates. Its output is a polynomial $f_C$. Polynomial identity testing asks whether \[ f_C\equiv0\quad\text{in the polynomial ring}, \] not whether it vanishes at one input or has some root. The goal is a deterministic polynomial-time test in the circuit's encoded size and the necessary field-representation parameters. The catalogue leaves the field, characteristic, and constant-encoding convention implicit; these must be fixed before interpreting "polynomial time." General circuits, not just sparse polynomials or formulas of bounded depth, are intended.

Formulation and concept references: [S1].

Short English statement

Can one deterministically and efficiently recognize when a general arithmetic circuit computes the zero polynomial?

Sources

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-15-A1 · No claim recorded · LLM-generated · gpt 6 astra pro ·

gpt 6 astra pro attempt on CS-15

Derandomization of Polynomial Identity Testing

Definitions and mathematical statement

An arithmetic circuit over a specified effective field has variables and field constants as inputs and addition and multiplication gates. Its output is a polynomial $f_C$. Polynomial identity testing asks whether \[ f_C\equiv0\quad\text{in the polynomial ring}, \] not whether it vanishes at one input or has some root. The goal is a deterministic polynomial-time test in the circuit's encoded size and the necessary field-representation parameters. The catalogue leaves the field, characteristic, and constant-encoding convention implicit; these must be fixed before interpreting "polynomial time." General circuits, not just sparse polynomials or formulas of bounded depth, are intended.

Formulation and concept references: [S1].

Short English statement

Can one deterministically and efficiently recognize when a general arithmetic circuit computes the zero polynomial?

Research attempt

Current frontier and model convention.
Kaplan--Shpilka's 2026 read-four result gives deterministic polynomial-time white-box testing, and quasipolynomial-time black-box testing, for that restricted formula model in characteristic zero or at least five; it is not a general-circuit algorithm. [E1] The Kabanets--Impagliazzo theorem links an appropriate deterministic identity test for integer circuits to a disjunction of major circuit lower bounds. Its field and algorithmic conventions cannot be silently exchanged with a finite-field statement. [E2] Here the concrete attack fixes a finite field ${\mathbb{F}}_q$ with an effective representation and unit-cost field arithmetic (or its usual polynomial-bit implementation). This resolves a local ambiguity for the attempt, not the unspecified field convention of the whole catalogue target. In particular, no claim about arbitrary rational constants of enormous intermediate height is inferred from the calculation.
Attack route.
Direct grid evaluation costs exponentially many points. Kronecker substitution compresses many variables into one but produces exponential degree. The route tested below preserves this compression while evaluating in many small quotient rings. The hoped-for missing lemma is that small circuits admit a polynomial-size collection of collision-free residue certificates even when their expanded supports are large. First a precise sparse version is proved; then a small circuit is used to test exactly where that proof ceases to be efficient.
Attempt: compressed exponents with exact collision control.
Let $C$ have $s$ gates in $n$ variables, and let $D\geq1$ be an upper bound on every individual degree. A formal degree bound of $2^{O(s)}$ is available without expanding the circuit. Set $w_i=(D+1)^{i-1}$ and \[ F(t)=f_C(t^{w_1},\ldots,t^{w_n}),\qquad M=(D+1)^n. \] Base-$(D+1)$ uniqueness shows that distinct exponent vectors with coordinates at most $D$ have distinct encoded exponents in $[0,M)$. Thus $F=0$ if and only if $f_C=0$. Although $M$ is large, $\log M=n\log(D+1)$ is polynomial in the circuit parameters under discussion.

Suppose, as an additional promise, that the nonzero polynomial has at most $T$ monomials after collecting coefficients. Write $F(t)=\sum_{j=1}^u c_jt^{e_j}$, with $u\leq T$, $c_j\ne0$ and distinct $0\leq e_j<M$. Define the nonzero integer \[ \Delta=\prod_{i<j}|e_i-e_j|, \qquad 1\leq\Delta\leq M^{T(T-1)/2}. \] For $u\leq1$ the product is one. A prime $\ell$ at which two exponents coincide modulo $\ell$ divides $\Delta$. Therefore, among any distinct primes $\ell_1,\ldots,\ell_R$ satisfying \begin{equation}\label{wsref-0-65-71-37-30-3a-70-72-6f-64-75-63-74} \prod_{j=1}^R\ell_j>M^{T(T-1)/2}, \end{equation} at least one separates all the exponents. At that prime, \begin{equation}\label{wsref-0-65-71-37-30-3a-71-75-6f-74-69-65-6e-74} F(t)\not\equiv0\pmod{t^\ell-1}. \end{equation} The proof is entirely about integer exponents; it does not assume that $\ell$ differs from the characteristic of ${\mathbb{F}}_q$. Even if the quotient ring has nilpotents, $1,t,\ldots,t^{\ell-1}$ is still an ${\mathbb{F}}_q$-basis, so distinct residues with nonzero coefficients cannot cancel.

One can take $R=1+\lceil T(T-1)\log_2(M)/2\rceil$, since every prime is at least two. The first $R$ primes have polynomial magnitude in $R$, and can be found by a sieve; an explicit standard bound is recorded in [E3]. For each prime compute $t^{w_i}$ modulo $t^\ell-1$ by reducing $w_i$ modulo $\ell$, then evaluate every gate of $C$ as a vector of $\ell$ coefficients. Addition is componentwise and multiplication is cyclic convolution, taking $O(\ell^2)$ field operations by the elementary method. The algorithm accepts identity only if every quotient evaluation vanishes. An identically zero polynomial certainly passes every test; for a nonzero polynomial under the support promise, (eq70:product)--(eq70:quotient) reject it. Hence this is a deterministic procedure polynomial in $s,n,T,\log D$ and the chosen field-operation costs. It need not know the actual support or the integer $\Delta$.

Attempt: the general-circuit certificate that is still missing.
A usable strengthening would give a deterministic algorithm that, from $C$, constructs exponent maps $w^{(j)}$ and moduli $m_j$ such that \[ f_C\ne0\ \Longrightarrow\ f_C(t^{w^{(j)}_1},\ldots,t^{w^{(j)}_n}) \not\equiv0\pmod{t^{m_j}-1}\quad\text{for some }j, \] with the sum of quotient dimensions, all exponent bit lengths, and the construction time polynomial in the input size. Evaluation of the resulting certificates would then be polynomial-time by the preceding gate simulation. This is a sufficient condition, not an asserted equivalent to all possible white-box derandomizations. In particular, constructing the certificates cannot itself call an identity oracle or enumerate an exponential support.

The support proof does not give this strengthening. The polynomial $\prod_{i=1}^n(1+x_i)$ has a circuit of linear size and $2^n$ monomials over every field. For it the displayed worst-case choice of $R$ is exponential. The example does not prove that this polynomial needs many quotients; it proves that the support-size estimate fails to bound the cost by circuit size. It leaves open whether cancellations and circuit structure could yield a smaller, differently organized family.

Stress test.
There is a separate finite-field pitfall: $x^q-x$ is a nonzero polynomial in ${\mathbb{F}}_q[x]$ but vanishes at every point of ${\mathbb{F}}_q$. Testing only scalar inputs over the base field cannot decide the polynomial question. The quotient construction avoids that error because it tests coefficients in a polynomial quotient, not just the induced function on ${\mathbb{F}}_q$.

A single quotient also fails universally: $t^m-1$ vanishes in the quotient by $t^m-1$, and small circuits can manufacture very large exponents by repeated squaring. The collision argument deliberately uses several moduli. It assumes a valid support bound and a valid degree bound; neither is inferred from the number of variables alone. Nonassociative-algebra algorithms in [S3] use a different algebraic model. They do not justify forgetting the commutativity and associativity of the target's polynomial ring.

The companion computation checks several residue collisions and their removal by another modulus over ${\mathbb{F}}_5$, including the polynomial/function distinction. These finite tests audit the mechanism, not the missing polynomial bound for all circuits. The sparse calculation is elementary and is not offered as a previously unknown sparse-PIT theorem.

Outcome.
Outcome: Exploratory approach with unresolved gap.

A complete sparse-support certificate argument and its bit-size accounting were obtained for the declared finite-field model. The attempt identifies a concrete generalization that would suffice for deterministic testing, but an exponential-support circuit breaks the only bound proved here. No general derandomization or circuit lower bound follows from this notebook. A continuation must construct polynomial-cost certificates from circuit structure itself, and must separately address the field and constant encoding convention of any broader formulation.

Sources

Go to contribution →