Polynomial identity testing

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials $A,B$ amounts to testing $P=A-B$ for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer $n\ge 1$, ${\prod }_{i=1}^n(1+x_i)$ has $2^n$ distinct monomials, one for each subset of the $n$ variables. Its factored expression needs only $n$ additions and $n-1$ multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Work in the finite field ${\mathbb{F}}_5=\{0,1,2,3,4\}$, using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives $(x+1{)}^2=x^2+2x+1$, so all coefficients of $F$ cancel: $F$ is identically zero. In contrast, $G=x^2-3x+2=x^2+2x+2$ in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.

The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, $G(3)=(3-1)(3-2)=2$ is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that $G$ is nonzero. A random variable $a$ with a uniform distribution on a finite set ${\mathbb{F}}_5$ hits those two polynomial roots with probability $2/5$.

A crucial limit appears with $H(x)=x^5-x$. Its coefficients make it a nonzero polynomial of polynomial degree five in ${\mathbb{F}}_5[x]$, yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are $0,0,30,240,1020$, all divisible by five. Thus $H$ induces the same polynomial function as the zero polynomial. Any number of trials restricted to ${\mathbb{F}}_5$ will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is $5/5=1$, which gives no useful guarantee.

When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish $H$ from zero.^[ref]

Let $P$ be a nonzero multivariate polynomial over a field $K$, with total degree at most $d\ge 0$. Choose a nonempty finite set $S\subseteq K$. For independent random variables $a_1,\dots ,a_n$, each with a uniform distribution on a finite set on $S$, the Schwartz-Zippel lemma givesNonzeroness is essential; the zero polynomial always evaluates to zero. The total degree sums exponents within each monomial, rather than taking their maximum: $x^2{y}^3+y$ has total degree five. The field need not be finite, but $S$ must be finite. The estimate reduces error only when $d/|S|<1$.^[ref]

The proof begins with the root bound for a polynomial. For several variables, write $P={\sum }_{j=0}^m{Q}_j(x_1,\dots ,x_{n-1})x_n^j$, with $Q_m\ne 0$. The total degree of $Q_m$ is at most $d-m$. By induction, $Q_m$ vanishes with probability at most $(d-m)/|S|$. Otherwise the remaining univariate polynomial has at most $m$ polynomial roots. Adding the two contributions gives $d/|S|$.^[ref]

The algorithm samples a point, performs exact polynomial evaluation, rejects the identity if the value is nonzero, and otherwise accepts. The lemma bounds false acceptance for every fixed nonzero input. For the polynomial identity testing over a finite field example, $G$ has $d=2$ and $|S|=5$, so its exact $2/5$ error attains the bound. Numerical near-zero values from floating-point arithmetic do not satisfy this exact algebraic contract. A polynomial-time algorithm claim additionally needs efficient sampling and evaluation, including the bit cost of representing and operating on field elements. Counting field operations alone does not establish that cost.

Repeat the random evaluation test for a polynomial identity with fresh independent random variables, keeping the same fixed polynomial. Reject as soon as any polynomial evaluation is nonzero; accept only if all $k$ values vanish. An identity is always accepted, preserving one-sided error. If a nonzero polynomial has single-trial false acceptance probability $p_1$, independence gives $p_k=p_1^k$. The Schwartz-Zippel lemma bounds this by $(d/|S|{)}^k$ when $d<|S|$.

For $G(x)=(x-1)(x-2)$ over the finite field ${\mathbb{F}}_5$, two uniform independent choices $(a,b)$ have $25$ equally likely ordered outcomes, each with probability $1/25$. Both polynomial evaluations are zero only at $(1,1),(1,2),(2,1),(2,2)$. Hence false acceptance falls from $2/5$ in one trial to $4/25$ in two trials, and correct rejection rises from $3/5$ to $21/25$.

If the second choice reuses the first, the pair is $(a,a)$ and only five diagonal outcomes are possible. Two still falsely accept, so the error remains $2/5$. Choosing fresh independent points is precisely what makes the full $25$-cell grid and the product of probabilities valid. For a target error $0<\epsilon <1$, this example needsThe ceiling function makes the trial count an integer. Four trials give $(2/5{)}^4=16/625>1/100$, while six give $64/15625<1/100$; five still give $32/3125>1/100$, so six is the first count below one percent. This is an exact error guarantee for each run on $G$, rather than an observed success rate.