Given two polynomials $f$ and $g$, like $x_1^2 - x_2^2$ and $(x_1 + x_2)(x_1 - x_2)$, how do we determine whether they are equal? This problem is known as Polynomial Identity Testing (PIT), which is equivalent to testing whether $f - g$ is identically zero. A polynomial is identically $0$ if and only if all its coefficients are $0$. However, expanding a polynomial into its monomial representation may incur exponential cost. This blog presents a simple randomized algorithm that solves PIT efficiently.
I learned this algorithm in the Combinatorial Optimization class (MS&E 315) taught by Professor Aaron Sidford. The course encodes the problem of testing whether a graph has a perfect matching as an instance of PIT. (See the lecture notes, Chapter 10, for details.)
Algorithm
The algorithm is remarkably simple: randomly sample a point and check whether the polynomial evaluates to $0$.
Specifically, let $f(x_1, \ldots, x_n)$ be a polynomial of degree at most $d$ over a field $\mathbb{F}$, and let $S \subseteq \mathbb{F}$ be any finite set. Sample $r_1, \ldots, r_n$ independently and uniformly at random from $S$. If $f(r_1, \ldots, r_n) = 0$, return “$f \equiv 0$”; otherwise return “$f \not\equiv 0$”.
The correctness of this algorithm is guaranteed by the following lemma:
Schwartz-Zippel Lemma. Let $f \in \mathbb{F}[x_1, \ldots, x_n]$ be a nonzero polynomial of degree at most $d$. For any finite set $S \subseteq \mathbb{F}$, if $r_1, \ldots, r_n$ are sampled independently and uniformly at random from $S$, then
\[\Pr[f(r_1, \ldots, r_n) = 0] \leq \frac{d}{\lvert S\rvert}.\]
Several observations follow from this lemma:
- The algorithm can only err when $f \not\equiv 0$ but the random evaluation happens to land on a root of $f$. The Schwartz-Zippel Lemma guarantees that the success probability is at least $1 - \frac{d}{\lvert S\rvert}$. Since $S$ is arbitrary, choosing a larger set $S$ increases the success probability.
- By repeating the test independently $k$ times, the error probability drops to $\left(\frac{d}{\lvert S\rvert}\right)^k$.
- The bound is independent of the number of variables $n$.
Proof
The proof proceeds by induction on $n$.
Base case ($n = 1$). The polynomial $f$ is univariate of degree at most $d$, so it has at most $d$ roots over $\mathbb{F}$. Therefore,
\[\Pr[f(r) = 0] \leq \frac{\lvert\{\text{roots of } f\} \cap S\rvert}{\lvert S\rvert} \leq \frac{d}{\lvert S\rvert}.\]Inductive step. Assume the lemma holds for all nonzero polynomials in $n - 1$ variables. We prove it for $n$ variables. Factor out $x_1$ by writing
\[f(x_1, \ldots, x_n) = \sum_{i=0}^{k} x_1^i \, f_i(x_2, \ldots, x_n),\]where $k$ is the largest power of $x_1$ appearing in $f$, so that $f_k \not\equiv 0$. Note that $\deg(f_k) \leq d - k$, since each monomial $x_1^k \cdot m$ in $f$ contributes a monomial $m$ of degree at most $d - k$ to $f_k$.
Define the event $A = {f_k(r_2, \ldots, r_n) = 0}$. We consider two cases.
Case 1: $A$ occurs. Since $f_k$ is a nonzero polynomial in $n - 1$ variables with $\deg(f_k) \leq d - k$, the induction hypothesis gives
\[\Pr[A] \leq \frac{d - k}{\lvert S\rvert}.\]Case 2: $A^c$ occurs. Conditioned on $r_2, \ldots, r_n$ such that $f_k(r_2, \ldots, r_n) \neq 0$, the function $g(x_1) = f(x_1, r_2, \ldots, r_n)$ is a nonzero univariate polynomial of degree $k$ in $x_1$. By the base case argument,
\[\Pr[f(r) = 0 \mid A^c] \leq \frac{k}{\lvert S\rvert}.\]Combining the two cases by the law of total probability,
\[\begin{aligned} \Pr[f(r) = 0] &= \Pr[A]\,\Pr[f(r) = 0 \mid A] + \Pr[A^c]\,\Pr[f(r) = 0 \mid A^c] \\ &\leq \Pr[A] + \Pr[f(r) = 0 \mid A^c] \\ &\leq \frac{d - k}{\lvert S\rvert} + \frac{k}{\lvert S\rvert} = \frac{d}{\lvert S\rvert}. \end{aligned}\]$\blacksquare$
