ZKP-Schwartz-Zippel Lemma

Schwartz-Zippel Lemma

In mathematics, the Schwartz–Zippel Lemma is a tool commonly used in probabilistic polynomial identity testing.

Schwartz, Jacob T. “Fast probabilistic algorithms for verification of polynomial identities.” Journal of the ACM (JACM) 27.4 (1980): 701-717.
Zippel, Richard. “Probabilistic algorithms for sparse polynomials.” International symposium on symbolic and algebraic manipulation. Berlin, Heidelberg: Springer Berlin Heidelberg, 1979.

For an m-variate polynomial $g$, the degree of a term of $g$ is the sum of the exponents of the variables in the term.

Let $\mathbb{F}$ be any field, and let $g : \mathbb{F}^m \rightarrow \mathbb{F}$ be a nonzero m-variate polynomial of total degree at most $d$. Then on any finite set $S \subseteq F$,

$$
\Pr_{x\leftarrow S^m}[g(x)=0]\leq d/\vert S \vert
$$

Here, $x\leftarrow S^m$ denotes an $x$ drawn uniformly at random from the product set $S^m$, and $\vert S \vert$ denotes the size of $S$. In words, if $x$ is chosen uniformly at random from $S^m$, then the probability that $g(x) = 0$ is at most $d/\vert S \vert$.

In particular, any two distinct polynomials of total degree at most $d$ can agree on at most a $d/\vert S \vert$ fraction of points in $S^m$.