One of the most important results in basic algebra is the Fundamental Theorem of Algebra. In the formulation that will be most useful for the context of this article it states the following.

Fundamental Theorem of Algebra. Every univariate polynomial of degree $d$ over a field $\mathbb F$ has at most $d$ roots in $\mathbb F$.

Unfortunately, the same does not hold true anymore for multivariate polynomials in $n\geq 2$ variables as the following easy counterexample shows.

Counterexample. Consider the polynomial $f(X,Y)\in\mathbb{F}$ with $f(X,Y)\coloneqq X\cdot Y$. Then $f$ is a polynomial of degree $2$ but it has many more than just $2$ roots. They are given by $$ \{ (0,y) : y\in \mathbb F\}\cup\{(x,0) : x\in\mathbb F\}. $$

But not all hope is lost. We are still able to make a statement about the density of roots of polynomials.

For a univariate polynomial $f(X)\in\mathbb F[X]$ of degree $d$, the Fundamental Theorem of Algebra yields that the density of roots of $f$ over any finite subset $S\subseteq\mathbb F$ with $|S|\geq d$ is at most $$ \frac{|\{a\in S : f(a)=0\}|}{|S|}\leq \frac{d}{|S|}. $$ As it turns out, this statement carries over to the multivariate case. It is exactly the assertion of the following lemma.

Schwartz-Zippel-DeMillo-Lipton Lemma. Let $n\in\mathbb N$ and let $f\in\mathbb F[X_1,\ldots,X_n]$ be a multivariate plynomial of degree $d$. Let $S\subseteq \mathbb F$ be a finite subset with $|S|\geq d$. Then it holds $$ \frac{|\{(a_1,\ldots,a_n)\in S^n : f(a_1,\ldots,a_n)=0\}|}{|S|^n} \leq \frac{d}{|S|}. $$

This is a very powerful result which is used extensively in many constructions for (succinct) argument systems. In particular, argument systems use this result for polynomial identity testing or to compress (batch, accumulate) many such tests into a single test. As a concrete example, the permutation check employed in PLONK uses this result as well. Before we proceed to the proof of the lemma, let us have another look at the counterexample from above. It helps us to illustrate the assertion of the lemma.

Counterexample; revisited. For the polynomial $f(X,Y) = X\cdot Y$ over $\mathbb F$ and a finite subset $S\subseteq \mathbb F$, we have $$ \begin{aligned} \frac{|\{(a_1,a_2)\in S^2 : f(a_1,a_2)=0\}|}{|S|^2} &= \begin{cases} 0, & 0\notin S\\ \frac{2|S|-1}{|S|^2}, & 0\in S \end{cases}\\ &\leq \frac{2}{|S|}. \end{aligned} $$

Proof (of the Lemma). By induction over $n$.

Probabilistic version. If we draw elements from $S$ independently and uniformly at random, we arrive at the probabilistic formulation of the Schwartz-Zippel-DeMillo-Lipton Lemma. Let $n\in\mathbb N$ and let $f\in\mathbb F[X_1,\ldots,X_n]$ be a multivariate polynomial of degree $d$. Furthermore, let $U_1,\ldots,U_n$ be identically and independently distributed random variables with a uniform distribution over $S$. Then it holds $$ \text{Pr}(f(U_1,\ldots,U_n)=0)\leq\frac{d}{|S|}. $$ In other words, the probability that (uniformly and independently selected) random elements $u_1,\ldots,u_n\in S$ are a root of $f$ is at most $\frac{d}{|S|}$.

The real power of the lemma is unlocked if the set $S$ is very large compared to the degree $d$ of $f$, i.e., if $d\ll |S|$. In this case, the lemma asserts that it is highly unlikely for a uniformly at random selected element from $\mathbb F_q^n$ to be a root of $f$. This gives us an efficient statistical test for checking if a polynomial is the zero polynomial, or, equivalently, if two polynomials are identical. Such a test is particularly advantageous if we don’t want (or don’t can) compare polynomials coefficient-wise due to high computational complexity.

Polynomial Zero Testing. Let $n\in\mathbb N$ and let $\mathbb F$ be a field. Given a polynomial $f\in\mathbb F[X_1,\ldots,X_n]$ of degree at most $d$, we employ the following statistical test for the claim $f=0$.

1. Choose $u_1,\ldots,u_n\in S\subseteq\mathbb F$ uniformly and independently at random.
2. Check if $f(u_1,\ldots,u_n) = 0$.
3. If yes, accept. Otherwise reject.

Put differently, we use the fact that $f(u_1,\ldots,u_n) = 0$ (as points) to infer that $f=0$ (as polynomials) with confidence (or likelihood) at least $1-\frac{d}{|S|}$. I.e., we have $$ f(u_1,\ldots,u_n) = 0 \stackrel{\text{high confidence}}{\Longleftrightarrow} f=0. $$ Let us elaborate on this test and have a look at the involved errors.

• $f=0$: $\text{Pr}(f(u_1,\ldots,u_n) = 0) = 1-\alpha = 1$ $\quad$ (correct accept)
• $f=0$: $\text{Pr}(f(u_1,\ldots,u_n)\neq 0) = \alpha = 0$ $\quad$ (false reject)
• $f\neq 0$: $\text{Pr}(f(u_1,\ldots,u_n) = 0) = \beta \leq \frac{d}{|S|}$ $\quad$ (false accept)
• $f\neq 0$: $\text{Pr}(f(u_1,\ldots,u_n)\neq 0) = 1 - \beta \geq 1-\frac{d}{|S|}$ $\quad$ (correct reject)

The error probability $\alpha$ that we falsely reject the zero polynomial corresponds to the completeness error in SNARKs. The error probability $\beta$ that we falsely accept a non-zero polynomial corresponds to the soundness error.