Schwartz-Zippel Lemma

Schwartz-Zippel Lemma

$Pr[P(x_1,x_2,...,x_n)=0]\le \frac{d}{s}$

• where: - $P$ is a non-zero $n$-variate polynomial - $d$ is the total degree of $P$ - $s$ is the finite field size

  Intuition $P(x)$ is equal to zero, and $P(x)$ has at most $d$ roots.

  Only the roots of

  This is the univariate polynomial special case of the Schwartz-Zeppel Lemma.

Applications

Polynomial Comparison

• to check if $P_a(x)\stackrel{?}{=}{P}_b(x)$
  • let $P_c(x)=P_a(x)-P_b(x)$
  • check if $P_c(x)\stackrel{?}{=}0$

Intuition

If $P_a$ and $P_b$ are distinct polynomials (i.e. $P_a\ne P_b$) of total degree at most $d$ over $f$, then probability $Pr[P_a=P_b]\le \frac{d}{p}$ because they will share points only at their common roots of at most $d$, if any.

Zero Testing

• To check if a polynomial equals 0, one can multiply it out, but it’ll take exponential time
• Instead, the polynomial can be represented as an arithmetic formula and be tested much more efficiently