schwartz_zippel_union_bound_zero_set
Let F be an integral domain, S a nonempty finite subset of F, n a positive integer, and let k ≥ 0, d ∈ ℕ and p_1, …, p_k be nonzero polynomials in n variables over F whose total degrees are all at most d. Then the number of points x of S^n at which at least one of p_1, …, p_k vanishes is at most k·d·|S|^(n−1). In particular, if k·d < |S| then some point of S^n is nonzero for all of p_1, …, p_k simultaneously.
Statement
open scoped Finset in theorem schwartz_zippel_union_bound_zero_set {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n k d : ℕ} (hn : 0 < n) {S : Finset F} (hS : 0 < S.card) {p : Fin k → MvPolynomial (Fin n) F} (hp : ∀ i, p i ≠ 0) (hd : ∀ i, (p i).totalDegree ≤ d) : #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | ∃ i, MvPolynomial.eval x (p i) = 0} ≤ k * (d * S.card ^ (n - 1))
- Related work
- Schwartz 1980 / Zippel 1979 together with the union bound; the simultaneous form of the identity test as in Motwani & Raghavan, Randomized Algorithms, ch. 7. Concepts anchored by Mathlib `MvPolynomial.schwartz_zippel_totalDegree` and 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
Let F be a commutative ring that is an integral domain (IsDomain, i.e. no zero divisors and nontrivial) with decidable equality. Let n, k, d : ℕ with n > 0 (hn). Let S be a finite subset of F that is nonempty (hS : 0 < S.card). Let p be a family of k multivariable polynomials over F in n variables, indexed by Fin k, such that (hp) each p i is not the zero polynomial, and (hd) each p i has total degree at most d. Then: the number of points x in the Cartesian power S^n — i.e. functions x : Fin n → F with x j ∈ S for every j — at which at least one of the polynomials vanishes (∃ i, eval x (p i) = 0), is at most k * (d * |S|^(n-1)). Equivalently, the size of the union of the zero sets of the p i inside S^n is bounded by k·d·|S|^(n-1), the Schwartz–Zippel union bound. All binders in order: F (implicit, with [CommRing F] [IsDomain F] [DecidableEq F]), n, k, d (implicit naturals), hn : 0 < n, S : Finset F, hS : 0 < S.card, p : Fin k → MvPolynomial (Fin n) F, hp : ∀ i, p i ≠ 0, hd : ∀ i, (p i).totalDegree ≤ d. The hypotheses hn, hS, hp, hd are all genuinely used (hn makes n − 1 well-behaved, hS makes S^n nonempty, hp and hd feed the degree bound).
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 set of points in S^n where at least one of the polynomials p_1, …, p_k vanishes is contained in the union of their individual zero sets. By the single-polynomial Schwartz–Zippel lemma and the degree hypothesis totalDegree(p_i) ≤ d, each individual zero set contains at most d · |S|^(n - 1) points. Applying the union bound across all k polynomials then bounds the total number of vanishing points by k · d · |S|^(n - 1).
The set of points in S^n at which at least one polynomial p_i vanishes is a subset of the union of the individual zero sets ⋃_{i ∈ Fin k} {x ∈ S^n | p_i(x) = 0}.
Let S^n denote the Cartesian product S^n. Given an element x ∈ S^n where some polynomial p_i vanishes, unfolding the definitions of filtered finsets (Finset.mem_filter), indexed union (Finset.mem_biUnion), and the universal set (Finset.mem_univ, true_and) shows that x belongs to the zero set of that specific polynomial p_i. Thus x belongs to the indexed union of all k zero sets.
uses
Finset.mem_filter,Finset.mem_biUnion,Finset.mem_univ,true_andlet Sn := Fintype.piFinset (fun _ : Fin n => S) have h_sub : {x ∈ Sn | ∃ i, MvPolynomial.eval x (p i) = 0} ⊆ Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0}) := by intro x hx simp only [Finset.mem_filter, Finset.mem_biUnion, Finset.mem_univ, true_and] at hx ⊢ rcases hx with ⟨hxs, i, hpi⟩ exact ⟨i, hxs, hpi⟩
The number of points in S^n where at least one polynomial vanishes is at most the cardinality of the union of the individual zero sets.
Because a finite set has cardinality at most that of any superset (Finset.card_le_card), the inclusion proved in the previous step immediately yields this cardinality inequality.
uses
Finset.card_le_cardhave h1 : #{x ∈ Sn | ∃ i, MvPolynomial.eval x (p i) = 0} ≤ #(Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0})) := Finset.card_le_card h_sub
The union of the k individual zero sets has cardinality at most k · (d · |S|^(n - 1)).
For each index i, the Schwartz–Zippel lemma for a single polynomial (schwartz_zippel_zero_count_le) bounds the number of zeros of p_i in S^n by totalDegree(p_i) · |S|^(n - 1). Since totalDegree(p_i) ≤ d, multiplying this degree bound by |S|^(n - 1) on the right (Nat.mul_le_mul_right) and applying transitivity (le_trans) shows that each individual zero set has size at most d · |S|^(n - 1). By the union bound for finite sets (Finset.card_biUnion_le_card_mul), the union of these k sets has cardinality at most the number of polynomials times this uniform bound. Since the index set Fin k has size k (Finset.card_fin), this gives the upper bound k · (d · |S|^(n - 1)).
uses
schwartz_zippel_zero_count_le,Nat.mul_le_mul_right,le_trans,Finset.card_biUnion_le_card_mul,Finset.card_finhave h2 : #(Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0})) ≤ k * (d * S.card ^ (n - 1)) := by have h_bound : ∀ i ∈ (Finset.univ : Finset (Fin k)), #{x ∈ Sn | MvPolynomial.eval x (p i) = 0} ≤ d * S.card ^ (n - 1) := by intro i _ have h_sz := schwartz_zippel_zero_count_le hn (hp i) hS have h_deg : (p i).totalDegree * S.card ^ (n - 1) ≤ d * S.card ^ (n - 1) := Nat.mul_le_mul_right _ (hd i) exact le_trans h_sz h_deg have h_mul := Finset.card_biUnion_le_card_mul (Finset.univ : Finset (Fin k)) (fun i => {x ∈ Sn | MvPolynomial.eval x (p i) = 0}) (d * S.card ^ (n - 1)) h_bound rw [Finset.card_fin] at h_mul exact h_mul
The number of points in S^n where at least one of p_1, …, p_k vanishes is at most k · d · |S|^(n - 1).
Combining the inequality bounding the joint zero set by the union's cardinality with the inequality bounding the union's cardinality via transitivity of ≤ (le_trans) yields the theorem.
uses
le_transexact le_trans h1 h2
Finset.mem_filter- An element belongs to the filtered set {x ∈ s | p(x)} if and only if it belongs to s and satisfies property p.
Finset.mem_biUnion- An element belongs to the indexed union ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- For any proposition p, True ∧ p is equivalent to p.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
schwartz_zippel_zero_count_le- For a nonzero multivariate polynomial p in n variables (n > 0) over an integral domain, the number of zeros of p in S^n is at most totalDegree(p) · |S|^(n - 1).
Nat.mul_le_mul_right- For natural numbers, if n ≤ m, then n · k ≤ m · k.
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of inequality).
Finset.card_biUnion_le_card_mul- If each set f(a) for a ∈ s has cardinality at most c, then the cardinality of the union ⋃_{a ∈ s} f(a) is at most |s| · c.
Finset.card_fin- The cardinality of the universal finset of Fin n is n.
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/-- Schwartz–Zippel with the union bound: at most k·d·|S|^(n−1) points of S^n are zeros of one of k nonzero polynomials of total degree at most d. -/theorem schwartz_zippel_union_bound_zero_set {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n k d : ℕ} (hn : 0 < n) {S : Finset F} (hS : 0 < S.card) {p : Fin k → MvPolynomial (Fin n) F} (hp : ∀ i, p i ≠ 0) (hd : ∀ i, (p i).totalDegree ≤ d) : #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | ∃ i, MvPolynomial.eval x (p i) = 0} ≤ k * (d * S.card ^ (n - 1)) := by let Sn := Fintype.piFinset (fun _ : Fin n => S) have h_sub : {x ∈ Sn | ∃ i, MvPolynomial.eval x (p i) = 0} ⊆ Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0}) := by intro x hx simp only [Finset.mem_filter, Finset.mem_biUnion, Finset.mem_univ, true_and] at hx ⊢ rcases hx with ⟨hxs, i, hpi⟩ exact ⟨i, hxs, hpi⟩ have h1 : #{x ∈ Sn | ∃ i, MvPolynomial.eval x (p i) = 0} ≤ #(Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0})) := Finset.card_le_card h_sub have h2 : #(Finset.univ.biUnion (fun i : Fin k => {x ∈ Sn | MvPolynomial.eval x (p i) = 0})) ≤ k * (d * S.card ^ (n - 1)) := by have h_bound : ∀ i ∈ (Finset.univ : Finset (Fin k)), #{x ∈ Sn | MvPolynomial.eval x (p i) = 0} ≤ d * S.card ^ (n - 1) := by intro i _ have h_sz := schwartz_zippel_zero_count_le hn (hp i) hS have h_deg : (p i).totalDegree * S.card ^ (n - 1) ≤ d * S.card ^ (n - 1) := Nat.mul_le_mul_right _ (hd i) exact le_trans h_sz h_deg have h_mul := Finset.card_biUnion_le_card_mul (Finset.univ : Finset (Fin k)) (fun i => {x ∈ Sn | MvPolynomial.eval x (p i) = 0}) (d * S.card ^ (n - 1)) h_bound rw [Finset.card_fin] at h_mul exact h_mul exact le_trans h1 h2