Proof of Theorem 48 (Schwartz-Zippel Lemma)

We prove the theorem by induction on $n$ (the number of variables). When $n=1$, this is exactly the univariate case so the polynomial has at most $d$ roots, and therefore the probability of at most $d/|S|$ follows trivially.

Now assume that the claim is true for up to $(n-1)$ variables and consider a polynomial $p(x_1,\ldots, x_n)$. Let $\ell$ be the highest degree of $x_n$ among all the terms in $p$. We can write

$p(x_1,\ldots, x_n) = x_n^{\ell}\cdot q(x_1,\ldots, x_{n-1}) + r(x_1,\ldots, x_n)$ where the degree of $x_n$ in $r$ is at most $(\ell-1)$.

Let $E_p$ be the event that we are interested in, i.e., the event that $p(a_1,\ldots, a_n) = 0$ and $E_q$ be the event that $q(a_1,\ldots, a_{n-1}) = 0$.

${\mathbb P}[E_p] = {\mathbb P}[E_p \cap E_q] + {\mathbb P} [E_p \cap \overline{E}_q] \leq {\mathbb P}[E_q] + {\mathbb P}[E_p \cap \overline{E}_q]$

Since $q$ has $n-1$ variables and $\deg(q) \le d-\ell$ (do you see why?), we use the induction hypothesis to say that ${\mathbb P}[E_q] \leq (d-\ell)/|S|$. The following claim will complete the proof of the theorem.

Claim 1

${\mathbb P}[E_p \cap \overline{E}_q] \leq \ell/|S|$.

Proof:

Notice that the event $\overline{E}_q$ depends on the values of $a_1,\ldots, a_{n-1}$, so we can further partition $\overline{E}_q$ based on the values of these $a_i$'s. Let $F(\alpha_1,\ldots, \alpha_{n-1}) = \overline{E}_q \cap \{(a_1,\ldots, a_{n-1}): (\forall i \in [n-1])\ a_i = \alpha_i\}$ (these are disjoint events that $\overline{E}_q$ holds for a given choice of $a_i$'s). Therefore,

${\mathbb P}[E_p \cap \overline{E}_q] = \sum_{(\alpha_1,\ldots, \alpha_{n-1})} {\mathbb P}[E_p \cap F(\alpha_1,\ldots, \alpha_{n-1})] \leq \sum_{(\alpha_1,\ldots, \alpha_{n-1})} {\mathbb P}[E_p \mid F(\alpha_1,\ldots, \alpha_{n-1})] \cdot {\mathbb P}[F(\alpha_1,\ldots, \alpha_{n-1})]$

The key is that, in the conditional term ${\mathbb P}[E_p \mid F(\alpha_1,\ldots, \alpha_{n-1})]$, the values of $a_1,\ldots, a_{n-1}$ are all fixed (they are equal to the $\alpha_i$'s). Therefore, $p(\alpha_1,\ldots, \alpha_{n-1}, x_n)$ is a univariate polynomial of degree $\ell$. By the base case, we have that the probability is at most $\ell/|S|$.

Exercise 130

Benjawan claims the following version of the Schwartz-Zippel lemma: Let $f \in {\mathbb F}_p[x_1,\ldots, x_n]$ be a polynomial. For this $f$, define the sequence $d_1,\ldots, d_n$ as follows:

• $d_n$ is the maximum exponent of $x_n$ in $f$, and $q_n(x_1,\ldots, x_{n-1})$ is the coefficient of $x_n^{d_n}$ in $f$.
• $d_{n-1}$ is the maximum exponent of $x_{n-1}$ in $q_n$ and $q_{n-1}(x_1,\ldots, x_{n-2})$ is the coefficient of $x_{n-1}^{d_{n-1}}$ in $q_n$
• and so on until we have completely defined $d_1$.

Now perform a random process where each $a_i$ is chosen uniformly at random from some set $S_i \subseteq {\mathbb F}_p$. Then,

${\mathbb P}[f(a_1,\ldots, a_n) = 0] \leq \sum_{i} d_i/|S_i|$

Is this claim true? Prove or disprove it. In case it is true, is this stronger or weaker than the original Schwartz-Zippel lemma?