Schwartz–Zippel lemma

Let be a field, a nonzero polynomial of total degree at most , and a finite nonempty set. Then

— Sch80. DeMillo and Lipton, and Zippel, proved related bounds independently — DL78, Zip79.

Nonzero means nonzero as a formal polynomial, and the bound is informative only for : the nonzero polynomial vanishes on all of .

Proof

Induction on . For , a nonzero univariate polynomial of degree at most has at most roots. For , write with ; then has total degree at most , so by induction. When , the polynomial is a nonzero univariate polynomial of degree , so the independent is a root with probability at most . A union bound gives — standard.

The proof uses only that a nonzero univariate polynomial of degree has at most roots, so the bound holds over every integral domain — standard.

Uses

  • Two distinct polynomials of total degree at most agree on at most a fraction of , which gives a one-sided-error test of whether a polynomial given by an evaluation procedure is identically zero (polynomial identity testing) — Sch80.
  • A univariate polynomial identity of degree at most over a finite field , checked at one uniformly random point of sampled independently of both sides, is sound up to error , as in the divisibility check of a QAP (GGPR13) — standard.
  • Generic-group lower bounds, such as GGM ⇒ DLOG, bound by a version of this lemma the probability that two distinct polynomials in the hidden exponents agree at a random point — Sho97.