schwartz_zippel_nonzero_count_ge
Let F be an integral domain, S a nonempty finite subset of F, n a positive integer, and p a nonzero polynomial in n variables over F of total degree d. Then the number of points of S^n at which p does not vanish is at least |S|^n − d·|S|^(n−1); equivalently, at least a fraction 1 − d/|S| of the points of S^n are nonzero for p. This is the guarantee of the random-evaluation identity test: a point where p is nonzero certifies p ≠ 0, so the test has one-sided error and rejects a nonzero p with probability at most d/|S|.
Statement
open scoped Finset in theorem schwartz_zippel_nonzero_count_ge {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0) {S : Finset F} (hS : 0 < S.card) : S.card ^ n - p.totalDegree * S.card ^ (n - 1) ≤ #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p ≠ 0}
- Source
- Schwartz 1980; Zippel 1979, in the one-sided-error form used for the randomized identity test (Motwani & Raghavan, Randomized Algorithms, ch. 7); companion of the knowledge-base node `schwartz_zippel_exists_nonzero_eval`.
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- schwartz_zippel_zero_count_leLet F be an integral domain, S a nonempty finite subset of F, n a positive integer, and p a nonzero polynomial in n variables over F of…
Read back from the Lean
The declaration universally quantifies over a type F carrying a commutative ring structure, an integral-domain structure, and decidable equality; over a natural number n with 0 < n; over a nonzero multivariate polynomial p in n variables over F; and over a finite subset S of F with 0 < S.card. It asserts that the number of n-tuples x : Fin n → F whose coordinates all lie in S and at which p evaluates to a nonzero element is at least S.card ^ n - p.totalDegree * S.card ^ (n - 1), where p.totalDegree is the total degree of p and the subtraction is the truncated subtraction of natural numbers. Equivalently, the count is at least max(0, |S|^n - deg(p) * |S|^(n-1)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The total number of points in the grid S^n is |S|^n, partitioned into the points where p vanishes and those where p does not vanish. By the Schwartz–Zippel lemma (`schwartz_zippel_zero_count_le`), the zero set contains at most d · |S|^(n−1) points. Subtracting this upper bound from |S|^n yields the required lower bound of |S|^n − d · |S|^(n−1) on the number of nonzeros.
The polynomial p vanishes at at most d · |S|^(n−1) points in S^n, where d is the total degree of p.
This is the standard Schwartz–Zippel bound (`schwartz_zippel_zero_count_le`), which bounds the number of roots of a nonzero multivariate polynomial over an integral domain in a finite grid S^n.
uses
schwartz_zippel_zero_count_lehave h_le := schwartz_zippel_zero_count_le hn hp hSThe number of zeros of p in S^n plus the number of nonzeros of p in S^n equals |S|^n.
Any finite set is partitioned into elements satisfying a predicate and those satisfying its negation (`Finset.card_filter_add_card_filter_not`). Here the ambient set is the Cartesian product S^n (`Fintype.piFinset`), and simplifying its cardinality via `Fintype.card_piFinset`, `Finset.prod_const`, `Finset.card_univ`, and `Fintype.card_fin` shows that |S^n| = |S|^n.
uses
Finset.card_filter_add_card_filter_not,Fintype.card_piFinset,Finset.prod_const,Finset.card_univ,Fintype.card_finhave h_sum := Finset.card_filter_add_card_filter_not (s := Fintype.piFinset (fun _ : Fin n => S)) (fun x => MvPolynomial.eval x p = 0) simp only [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sum
The number of points in S^n where p does not vanish is at least |S|^n − d · |S|^(n−1). automation
After rewriting p(x) ≠ 0 to ¬(p(x) = 0) via `ne_eq` to match the partition identity, linear integer arithmetic (`omega`) subtracts the upper bound on zeros from the total count |S|^n to obtain the desired lower bound on nonzeros.
uses
ne_eqsimp only [ne_eq] omega
Finset.card_filter_add_card_filter_not- For any finite set s and predicate p, the number of elements in s satisfying p plus the number of elements satisfying ¬p equals |s|.
Finset.card_univ- The cardinality of the universal set Finset.univ of a finite type α is the cardinality of α.
Finset.prod_const- The product of a constant value over a finite set equals the constant raised to the power of the set's size.
Fintype.card_fin- The finite type Fin n (the integers 0, 1, ..., n − 1) has cardinality n.
Fintype.card_piFinset- The cardinality of the Cartesian product of a finite family of finite sets is the product of their cardinalities.
ne_eq- Inequality a ≠ b is equivalent to the negation ¬(a = b).
schwartz_zippel_zero_count_le- A nonzero polynomial of total degree d in n variables over an integral domain vanishes on at most d · |S|^(n−1) points of S^n.
- Line 12 rewrites `≠` to `¬ ... = ...` using `ne_eq` so that the goal's filtering predicate is syntactically identical to the complement set produced by `Finset.card_filter_add_card_filter_not`, enabling the linear integer arithmetic tactic `omega` to recognize them as the same quantity.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Finset in/-- At least |S|^n − d·|S|^(n−1) points of S^n are nonzero for a nonzero polynomial of total degree d. -/theorem schwartz_zippel_nonzero_count_ge {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0) {S : Finset F} (hS : 0 < S.card) : S.card ^ n - p.totalDegree * S.card ^ (n - 1) ≤ #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p ≠ 0} := by have h_le := schwartz_zippel_zero_count_le hn hp hS have h_sum := Finset.card_filter_add_card_filter_not (s := Fintype.piFinset (fun _ : Fin n => S)) (fun x => MvPolynomial.eval x p = 0) simp only [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sum simp only [ne_eq] omega