The Schwartz-Zippel Lemma

We will now look at a generalization of the above technique. The key idea is that the equation $(AB-C)\textbf{x}$ (as considered in the previous section) is a polynomial $p(x_1,\ldots, x_n)$ of degree one, and the problem we are solving is to check whether this polynomial is the zero polynomial or not.

In this section, we look at a generalization of this problem. Let us consider a polynomial $p(x_1,\ldots, x_n)$ of any degree $d \geq 1$, e.g.,

$p(x_1,x_2,x_3) = 12x_1^2 x_3^2 - 3 x_2 x_3^2 + x_1^3$

Each term of the sum is called a monomial. The degree of a monomial is the sum of all the exponents in that monomial, and the degree of a polynomial is the maximum over all the monomial's degrees. For instance, the above polynomial is of degree $4$ (from the monomial $12x_1^2 x_3^2$). The following theorem is known as the Schwartz-Zippel Lemma.

Theorem 48

Let $p(x_1,\ldots, x_n)$ be a non-zero polynomial of degree $d$. Let $S$ be a set of numbers. If we pick $a_1,\ldots, a_n \in S$ at random, uniformly and independently, then we have that

${\mathbb P}[p(a_1,\ldots, a_n) = 0] \leq d/|S|$

We will prove this theorem later. Now let us see some applications. A direct application of this theorem is to solve the Polynomial Identity Testing (PIT) problem: Given a polynomial $p(x_1,\ldots, x_n)$, our task is to decide whether $p$ is the zero polynomial (i.e. all coefficients are zero). This might sound like an easy problem since we can just look at the coefficients and check them one by one, but we are not always given the polynomial's coefficients explicitly. For instance, if an input polynomial is $p(x) = (x_1-x_2)^{25}x_3 x_4 - (x_3+x_1)^26x_2$, expanding all monomials might be computationally too expensive.

With the Schwartz-Zippel lemma, we can solve PIT by a simple randomized algorithm: Given a polynomial $p(x_1,\ldots,x_n)$ of degree $d$, pick $\textbf{a} \in \{1,\ldots, 10d\}^n$ and check whether $p(\textbf{a})= 0$.

• If $p$ is a zero polynomial, the algorithm will always answer correctly.
• Otherwise, if $p$ is non-zero, using the Schwartz-Zippel lemma, the probability that $p(\textbf{a}) = 0$ (algorithm fails) is at most $d/10d = 1/10$.

PIT is one of the most well-studied problems in the area of computational complexity, where we know an efficient randomized algorithm but not an efficient deterministic algorithm. If we know the input is a univariate polynomial, PIT is in fact easy (i.e., we can reconstruct the polynomial of degree $d$ by evaluating it at $d+1$ points).