The Schwartz–Zippel lemma
ProvedFamousTheorems.schwartz_zippelThe Schwartz–Zippel lemma. Let be a polynomial in variables over an integral domain , and finite. Then
In particular, with all , a random point is a zero with probability at most .
It is the basis of randomized polynomial identity testing, with applications in algorithms (matchings, primality-style certificates), complexity (PCP, low-degree testing) and coding theory.
Formalization note. Mathlib's MvPolynomial.schwartz_zippel_sup_sum, in the sharp form using the support of (exponent vectors ) and values in ℚ≥0. The platform previously carried only a grid-induction step, not the lemma itself.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem schwartz_zippel {R : Type*} [CommRing R] [IsDomain R] [DecidableEq R] {n : ℕ} {p : MvPolynomial (Fin n) R}
(hp : p ≠ 0) (S : Fin n → Finset R) :
(({x ∈ Fintype.piFinset fun i => S i | MvPolynomial.eval x p = 0}.card : NNRat) /
∏ i, ((S i).card : NNRat)) ≤
p.support.sup fun s => ∑ i, ((s i : NNRat) / (S i).card) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `MvPolynomial.schwartz_zippel_sup_sum`. Proof here reduces to that Mathlib result.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.