= Random evaluation test for a polynomial identity
{title2=$\mathbb P(P(a_1,\ldots,a_n)=0)\le d/|S|$}
Let $P$ be a nonzero <multivariate polynomial> over a <field> $K$, with <total degree> at most $d\ge0$. Choose a nonempty <finite set> $S\subseteq K$. For <independent random variables> $a_1,\ldots,a_n$, each with a <uniform distribution on a finite set> on $S$, the <Schwartz-Zippel lemma> gives
$$
\mathbb P\bigl(P(a_1,\ldots,a_n)=0\bigr)\le\min\{1,d/|S|\}.
$$
Nonzeroness is essential; the zero <polynomial> always evaluates to zero. The <total degree> sums exponents within each <monomial>, rather than taking their maximum: $x^2y^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$.<CMPT 710 and CMPT 407 - Computational Complexity - Fall 2007/CMPT 710 - Complexity Theory: Lecture 18>[CMPT 710 and CMPT 407 - Computational Complexity - Fall 2007; CMPT 710 - Complexity Theory: Lecture 18, §3.1, pp. 3–4: Lemma 4 and its inductive proof]{ref}
The proof begins with the <root bound for a polynomial>. For several <variables>, write $P=\sum_{j=0}^m Q_j(x_1,\ldots,x_{n-1})x_n^j$, with $Q_m\ne0$. 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|$.<CMPT 710 and CMPT 407 - Computational Complexity - Fall 2007/CMPT 710 - Complexity Theory: Lecture 18>[CMPT 710 and CMPT 407 - Computational Complexity - Fall 2007; CMPT 710 - Complexity Theory: Lecture 18, §3.1, pp. 3–4: split by the leading coefficient in the last variable]{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.
Back to article page
