Schwartz-Zippel Lemma

We prove the lemma via induction.

Let $n=1$ be the base case, a degree $d$ polynomial has at most $d$ real roots, so the probability that $r_1$ hits a root is at most $d/q.$

Otherwise, write

$$P(x_1, x_2, \dots, x_n) = \sum_{i=0}^{d} x_1^i \cdot F_i(x_2, \dots, x_n).$$

Since the above is nonzero, there exists a nonzero $F_i(\cdot)$ with degree $d-i.$ Take the largest $i.$

By induction,

$$\Pr\left[F_i(r_2, \dots, r_n) = 0\right] \leq \frac{d-i}{q}.$$

Then, $P(x_1, r_2, \dots, r_n)$ is a polynomial with degree $i$, we have that

$$\Pr[P(x_1, x_2, \dots, x_n) = 0] \leq \frac{i}{q}.$$

Through union bound, we have that

$$\Pr\left[P(r_1, r_2, \dots, r_n) = 0\right] \leq \frac{d}{q}.$$