Polynomial Identity Testing

DeMillo-Lipton-Schwartz–Zippel Lemma

Let $P$ be a non-zero polynomial on $n$ variables of degree $d$.
Let $S$ be the set of size at least $d + 1$.
We randomly sample $n$ values, $a_{1}, a_{2}, \dots, a_{i}$ from $S$ independently, uniformly and randomly. The theorem states that

Proof

Proof using mathematical induction on $n$.
Base Case - $n = 1$
We know that a $d$-degree polynomial can have at most $d$ roots (Fundamental theorem of algebra). Hence, the bound holds true for $n = 1$ variable polynomials.
Induction state - Assume it’s true for $n \leq k - 1$, prove for $n = k$
We have the variables $x_{1}, x_{2}, \dots, x_{n}$
We can restructure the $n$ variable polynomial in terms of coefficients of $x_{1}$

From our initial assumption, it’s known that $P$ is not identically $0$, therefore we find the largest $i$ such that $P_{i}$ is not identically $0$.
Note that for any $i$, $\operatorname{deg} P_{i} \leq d - i$, as the degree of $x_{1}^{i}P_{i}$ is at most $d$

We aim to prove the bound defined by the lemma using this structure

Here, we define events $A, B$ as\

Where $r_{i}$ are independently, uniformly, and randomly (i.u.a.r) sampled from $S$.

$\mathbb{P}[B]$

We know that the degree of $P_{i}$ is $\leq d - i$. Therefore, by the induction hypothesis, for an $n - 1$ variable polynomial we get

$\mathbb{P}[A | B^{c}]$

If $P_{i}(r_{2}, r_{3}, \dots, r_{n}) \neq 0$, $B^{c}$ occurs, we now know that the degree of the polynomial $P$ is $i$, since all the $P_{j} \equiv 0, \forall j > i$. We can plug in the values of $r_{2}, r_{3}, \dots, r_{n}$, and get an $i$-degree univariate polynomial in terms of $x_{i}$.

Therefore, with the help of the induction hypothesis, for a univariate polynomial we can say that

$\mathbb{P}[A]$

Therefore, we get

Hence, proved.

Using this lemma, we can test if two multivariate polynomials $f, g$ are equal by identity testing polynomial $h = f - g$.

Randomized Algorithm for Polynomial Identity Testing

1. Pick a set $S$ of size $\alpha d$, where $\alpha > 1$
2. Evaluate at a point $\bar a$ (a vector of size $n$) whose corrdinates are sample i.u.a.r from $S$.
3. If $f(\bar a) = 0$ assert $f \equiv 0$, else $f \not \equiv 0$ .

The possible error is that a non-zero polynomial is asserted as a zero-polynomial.

Verifying Matrix Multiplication

An application of Polynomial Identity Testing is verifying matrix multiplication
Given matrices $A, B, C$, we need to verify if $AB = C$.

This can be done in $O(n^{w})$ ($w$ is the matrix multiplication exponent), but we can speed this up using randomization.

Let $S$ be a finite subset of $\mathbb{R}$, and we choose $\bar x = (x_{1}, x_{2}, \dots, x_{n})$ i.u.a.r
We then verify if $ABx = Cx$. If true, we say that $AB = C$, else return $AB \neq C$.
Running this takes $O(n^{2})$ time, as finding $Bx$, $A(Bx)$ and $Cx$ are all $O(n^{2})$ time operations.

Probability Analysis

$ABx, Cx$ are both vectors, whose entries are linear forms in $x$.

If $AB=C$, then we know that $\forall \bar x, AB\bar x = C \bar x$, which essentially means
$\forall 1 \leq i \leq n, L_{i}(\bar x) - L_{i}'(\bar x)= 0$
If $AB \neq C$, then there exists some vector $\bar x$ such that $L_{i}(\bar x) - L_{i}'(\bar x) \neq 0$

Lemma - For any linear polynomial $L(x)$

Proof - We can arrive to this result using the principle of deferred decision.

We know that we can represent $L(x)$ as

Assume we randomly pick the first $n - 1$ values for $x$ as $a_{1}, a_{2}, \dots, a_{n-1}$, we’d get

For $L(x) = 0$,

There is at max $1$ possible value for $x_{n}$ in $S$ for which this equality holds true, hence the probability of this being true is $\leq \frac{1}{|S|}$.

Claim - If $AB \neq C$, then $\mathbb{P}[ABx = Cx] \leq \frac{1}{|S|}$
Proof - When $AB \neq C$, we say a bad event is when $L_{i}(\bar x) - L_{i}'(\bar x) =0\ \forall i \in [n]$, i.e we picked a vector such that $ABx = Cx$ event when $AB \neq C$, which causes us to incorrectly say that $AB = C$.

The probability of the bad event occurring is bounded by

And using the earlier Lemma, we can bound this further, giving us

Hence proved.