Schwartz-Zippel Lemma
Summary
The Schwartz-Zippel Lemma bounds the probability that a nonzero multivariate polynomial evaluates to zero at a random point. It is a fundamental tool in randomized algorithms and cryptographic protocol design, where it underpins polynomial identity testing, interactive proofs, and zero-knowledge protocols.
Discovered independently by Schwartz [1] and Zippel [2], with an earlier result by DeMillo and Lipton [3]. Sometimes called the DeMillo-Lipton-Schwartz-Zippel lemma.
Formal Statement
Let \(f(x_1, \ldots, x_n) \in \mathbb{F}[x_1, \ldots, x_n]\) be a nonzero polynomial of total degree \(d\) over a field \(\mathbb{F}\). Let \(S \subseteq \mathbb{F}\) be a finite set. If \(r_1, \ldots, r_n\) are chosen independently and uniformly at random from \(S\), then:
\[\Pr[f(r_1, \ldots, r_n) = 0] \leq \frac{d}{|S|}\]
Intuition
A nonzero univariate polynomial of degree \(d\) has at most \(d\) roots. So if you pick a random element from a set \(S\), the chance of hitting a root is at most \(d / |S|\). The Schwartz-Zippel lemma generalizes this to multivariate polynomials: even with many variables, the fraction of zeroes in \(S^n\) is still bounded by \(d / |S|\), regardless of the number of variables.
The practical consequence: to test whether two polynomials \(p\) and \(q\) are identical, form \(f = p - q\) and evaluate at a random point. If \(f\) is nonzero (i.e., \(p \neq q\)), the test catches this with probability at least \(1 - d/|S|\). By choosing \(|S| \gg d\), the error probability becomes negligible.
Notes
- The lemma is often applied in the following way: to check whether a polynomial identity \(p \equiv q\) holds, evaluate \(f = p - q\) at a random point. If \(p \neq q\), then \(f\) is nonzero and the check fails with probability at most \(d / |S|\).
- Applications include polynomial identity testing and verifiable computation.
- Used extensively in SNARKs, STARKs, and other proof systems where the prover commits to polynomials and the verifier checks evaluations at random points.