Lesson 2

The following lemma is known as the Schwartz–Zippel lemma and is also called the DeMillo–Lipton–Schwartz–Zippel lemma.

Lemma. Let \(P(x_{1}, x_{2}, …, x_{n})\) be a non-zero polynomial of total degree \(d\) over a field \(\mathbb{F}\). Let \(S\) be a finite subset of \(\mathbb{F}\), and let \(r_{1}, r_{2}, \dotsc, r_{n}\) be chosen uniformly and independently at random from \(S\). Then, \[\Pr[P(r_{1}, r_{2}, \dotsc, r_{n})=0] \le \frac{d}{|S|}.\]

Proof. We prove the lemma by induction on \(n\). In the base case \(n = 1\), we are dealing with a single-variate polynomial (rather than multivariate), and the result follows from the fact that any non-zero polynomial of degree \(d\) over a field has at most \(d\) roots in the field. The inequality holds with equality if and only if \(P\) has \(d\) roots and \(S\) contains all of them.

For the induction step \(n-1 \to n\), express \(P\) as a polynomial in the first variable: \[P(x_{1}, \dotsc, x_{n}) = x_{1}^{k} P_{k}(x_{2}, \dotsc, x_{n}) + x_{1}^{k-1}P_{k-1}(x_{2}, \dotsc, x_{n}) + \dotsb + P_{0}(x_{2}, \dotsc, x_{n}),\] where the polynomial \(P_{k}\) is non-zero and has total degree at most \(d-k\). Then, \[\begin{align*}&\Pr[P(r_{1}, \dotsc, r_{n})=0]\\ =&\Pr[P(r_{1}, \dotsc, r_{n})=0 \land P_{k}(r_{2}, \dotsc, r_{n})=0]\\ +&\Pr[P(r_{1}, \dotsc, r_{n})=0 \land P_{k}(r_{2}, \dotsc, r_{n})\neq 0].\end{align*}\] The first term can be upper bounded by the inductive hypothesis: \[\Pr[P(r_{1}, \dotsc, r_{n})=0 \land P_{k}(r_{2}, \dotsc, r_{n})=0] \le \Pr[P_{k}(r_{2}, \dotsc, r_{n}) = 0] \le \frac{d - k}{|S|}.\] It remains to show that the second term is at most \(k/|S|\). To estimate this term, note that, when \(r_{2}, \dotsc, r_{n}\) are fixed so that \(P_{k}(r_{2}, \dotsc, r_{n}) \neq 0\), \(P\) becomes a non-zero polynomial in \(x_{1}\) of degree \(k\) and hence has at most \(k\) roots. A bit more formally: \[\Pr[P(r_{1}, \dotsc, r_{n})=0 \land P_{k}(r_{2}, \dotsc, r_{n})\neq 0] \le \Pr[P(r_{1}, \dotsc, r_{n})=0 \mid P_{k}(r_{2}, \dotsc, r_{n})\neq 0] \le \frac{k}{|S|}.\]◼