schwartz_zippel_zero_count_tight
For any integral domain F with decidable equality, any positive integer n, any finite subset S of F, and any natural number d with d ≤ S.card, there exists a nonzero multivariate polynomial p in n variables over F with total degree at most d such that the number of points in S^n at which p evaluates to zero equals d * S.card ^ (n - 1).
Statement
theorem schwartz_zippel_zero_count_tight {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n : ℕ} (hn : 0 < n) {S : Finset F} {d : ℕ} (hd : d ≤ S.card) : ∃ p : MvPolynomial (Fin n) F, p ≠ 0 ∧ p.totalDegree ≤ d ∧ Finset.card (Finset.filter (fun x => MvPolynomial.eval x p = 0) (Fintype.piFinset (fun _ : Fin n => S))) = d * S.card ^ (n - 1)
- Related work
- Burgisser, Clausen & Shokrollahi, Algebraic Complexity Theory
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- card_piFinset_filter_apply_memFor any type α with decidable equality, any positive integer n, any finite subset S of α, any subset T of α with T ⊆ S, and any coordinate…
Read back from the Lean
Given a commutative domain $F$ with decidable equality, a positive natural number $n > 0$, a finite subset $S \subseteq F$, and a natural number $d \le |S|$, there exists a non-zero multivariate polynomial $p \in F[X_0, \ldots, X_{n-1}]$ (indexed by Fin n) such that:
1. The total degree of $p$ is at most $d$, and
2. The number of tuples $x \in S^n$ (viewed as functions Fin n → F with all values in $S$, formed by Fintype.piFinset) at which $p$ evaluates to $0$ is exactly $d \cdot |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
To prove tightness of the Schwartz-Zippel upper bound, we construct an explicit polynomial p that depends on only one variable X₀. Choosing a subset T ⊆ S of size d, we set p = ∏_{s ∈ T} (X₀ - s). In an integral domain, p is nonzero with total degree at most d, and p(x) = 0 if and only if x₀ ∈ T, so the number of zeros in S^n is precisely |T| · |S|^(n - 1) = d · |S|^(n - 1).
The linear polynomial X_i - C(s) is nonzero for any variable index i and scalar s.
Assume for contradiction that X_i - C(s) = 0. Comparing the coefficient of the monomial X_i on both sides via congr_arg and MvPolynomial.coeff_sub, the coefficient of X_i in X_i - C(s) is 0. Since the coefficient of X_i in X_i is 1 (MvPolynomial.coeff_X, if_pos) and its coefficient in the constant polynomial C(s) is 0 (MvPolynomial.coeff_C, if_neg) because the monomial exponent for X_i is nonzero (Finsupp.ext_iff.mp), we simplify with sub_zero to obtain 1 = 0, which contradicts one_ne_zero.
uses
congr_arg,MvPolynomial.coeff_sub,MvPolynomial.coeff_zero,MvPolynomial.coeff_X,if_pos,MvPolynomial.coeff_C,Finsupp.ext_iff.mp,if_neg,sub_zero,one_ne_zerointro h have h2 := congr_arg (MvPolynomial.coeff (Finsupp.single i 1)) h rw [MvPolynomial.coeff_sub, MvPolynomial.coeff_zero, MvPolynomial.coeff_X, if_pos rfl, MvPolynomial.coeff_C] at h2 have hne : (0 : Fin n →₀ ℕ) ≠ Finsupp.single i 1 := by intro h3 have h4 := Finsupp.ext_iff.mp h3 i simp at h4 rw [if_neg hne, sub_zero] at h2 exact one_ne_zero h2
Choose a subset T ⊆ S of cardinality d and define the polynomial p = ∏_{s ∈ T} (X_{i₀} - s).
Using Finset.exists_subset_card_eq on the hypothesis d ≤ |S|, we obtain a subset T ⊆ S of cardinality d. Since n > 0, we select the coordinate index i₀ = 0 ∈ Fin n. We define p as the product of the linear factors X_{i₀} - C(s) over all s ∈ T, and supply p as the existential witness, splitting the remaining goal into three parts: nonzeroness, total degree at most d, and the zero count.
uses
Finset.exists_subset_card_eqobtain ⟨T, hT, hTcard⟩ := Finset.exists_subset_card_eq hd let i₀ : Fin n := ⟨0, hn⟩ let p : MvPolynomial (Fin n) F := ∏ s ∈ T, (MvPolynomial.X i₀ - MvPolynomial.C s) use p refine ⟨?_, ?_, ?_⟩
The polynomial p is nonzero.
In an integral domain, a finite product is nonzero if and only if every factor is nonzero (Finset.prod_ne_zero_iff). Each factor X_{i₀} - C(s) is nonzero by schwartz_zippel_zero_count_tight_x_sub_c_ne_zero.
uses
Finset.prod_ne_zero_iff,schwartz_zippel_zero_count_tight_x_sub_c_ne_zero· rw [Finset.prod_ne_zero_iff] intro s hs exact schwartz_zippel_zero_count_tight_x_sub_c_ne_zero i₀ s
The total degree of p is at most d.
The total degree of a product is bounded by the sum of total degrees (MvPolynomial.totalDegree_finsetProd). Subtracting a constant does not increase total degree (MvPolynomial.totalDegree_sub_C_le), and the single variable X_{i₀} has total degree 1 (MvPolynomial.totalDegree_X), so each factor has total degree at most 1. Summing these bounds over T (Finset.sum_le_sum) yields |T| · 1 = d (Finset.sum_const, nsmul_eq_mul, mul_one), matching the cardinality |T| = d.
uses
MvPolynomial.totalDegree_finsetProd,MvPolynomial.totalDegree_sub_C_le,MvPolynomial.totalDegree_X,Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mul,mul_one· refine (MvPolynomial.totalDegree_finsetProd T _).trans ?_ have h1 (s : F) (hs : s ∈ T) : (MvPolynomial.X i₀ - MvPolynomial.C s : MvPolynomial (Fin n) F).totalDegree ≤ 1 := (MvPolynomial.totalDegree_sub_C_le (MvPolynomial.X i₀) s).trans (MvPolynomial.totalDegree_X i₀).le have h2 : ∑ s ∈ T, (MvPolynomial.X i₀ - MvPolynomial.C s : MvPolynomial (Fin n) F).totalDegree ≤ ∑ s ∈ T, 1 := Finset.sum_le_sum h1 simp only [Finset.sum_const, nsmul_eq_mul, mul_one] at h2 rw [hTcard] at h2 exact h2
A point x ∈ S^n is a zero of p if and only if its i₀-th coordinate lies in T.
Evaluating p at x distributes over the product (map_prod) to yield ∏_{s ∈ T} (x(i₀) - s) via Finset.prod_congr. Because F is an integral domain with no zero divisors (Finset.prod_eq_zero_iff), this product vanishes if and only if x(i₀) - s = 0 for some s ∈ T, which means x(i₀) = s (sub_eq_zero). Hence, the set of zeros of p in S^n equals the set of points whose i₀-th coordinate lies in T (Finset.filter_congr).
uses
Finset.filter_congr,map_prod,Finset.prod_congr,Finset.prod_eq_zero_iff,sub_eq_zero· have h_filter : Finset.filter (fun x => MvPolynomial.eval x p = 0) (Fintype.piFinset (fun _ : Fin n => S)) = Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S)) := by apply Finset.filter_congr intro x hx dsimp [p] rw [map_prod] have : (∏ s ∈ T, MvPolynomial.eval x (MvPolynomial.X i₀ - MvPolynomial.C s)) = ∏ s ∈ T, (x i₀ - s) := by apply Finset.prod_congr rfl intro s hs simp rw [this, Finset.prod_eq_zero_iff] simp [sub_eq_zero]
The number of zeros of p in S^n is d · |S|^(n - 1).
We replace the filter condition with x(i₀) ∈ T using the equivalence established in the previous step. By card_piFinset_filter_apply_mem, the number of tuples in S^n whose i₀-th coordinate belongs to T is |T| · |S|^(n - 1). Since |T| = d, this equals d · |S|^(n - 1).
uses
card_piFinset_filter_apply_memrw [h_filter] rw [card_piFinset_filter_apply_mem hn S T hT i₀] rw [hTcard]
congr_arg- If two inputs are equal, applying any function to both yields equal results.
MvPolynomial.coeff_sub- The coefficient of a monomial in the difference of two multivariate polynomials is the difference of their coefficients.
MvPolynomial.coeff_zero- Every coefficient of the zero multivariate polynomial is zero.
MvPolynomial.coeff_X- The coefficient of a monomial m in the single-variable polynomial X_i is 1 if m = X_i and 0 otherwise.
if_pos- If a condition c holds, the conditional expression if c then t else e evaluates to t.
MvPolynomial.coeff_C- The coefficient of a monomial m in the constant polynomial C(a) is a if m = 0 and 0 otherwise.
Finsupp.ext_iff.mp- If two finitely supported functions are equal, their values agree at every index.
if_neg- If a condition c is false, the conditional expression if c then t else e evaluates to e.
sub_zero- Subtracting zero from any element leaves it unchanged.
one_ne_zero- In a nontrivial ring, the element 1 is nonzero.
Finset.exists_subset_card_eq- A finite set has a subset of any cardinality less than or equal to its own cardinality.
Finset.prod_ne_zero_iff- In an integral domain, a finite product is nonzero if and only if every factor is nonzero.
schwartz_zippel_zero_count_tight_x_sub_c_ne_zero- For any variable index i and scalar s, the multivariate polynomial X_i - C(s) is nonzero.
MvPolynomial.totalDegree_finsetProd- The total degree of a finite product of multivariate polynomials is at most the sum of their individual total degrees.
MvPolynomial.totalDegree_sub_C_le- Subtracting a constant polynomial from a polynomial does not increase its total degree.
MvPolynomial.totalDegree_X- A single-variable monomial X_s has total degree 1.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f over the set is at most the sum of g.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set times the constant.
nsmul_eq_mul- Multiplication by a natural number as repeated addition agrees with algebraic multiplication.
mul_one- Multiplying any element by 1 leaves it unchanged.
Finset.filter_congr- Filtering a finite set by two predicates yields the same subset if the predicates are equivalent on all elements of the set.
map_prod- A monoid homomorphism, such as polynomial evaluation, preserves finite products.
Finset.prod_congr- Two finite products are equal if their index sets are equal and their terms agree on all indices.
Finset.prod_eq_zero_iff- In a domain with no zero divisors, a finite product equals zero if and only if at least one factor is zero.
sub_eq_zero- In an additive group, a - b = 0 if and only if a = b.
card_piFinset_filter_apply_mem- In the Cartesian product S^n, the number of tuples whose i₀-th coordinate lies in T ⊆ S equals |T| · |S|^(n - 1).
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.
lemma schwartz_zippel_zero_count_tight_x_sub_c_ne_zero {F : Type*} [CommRing F] [IsDomain F] {n : ℕ} (i : Fin n) (s : F) : (MvPolynomial.X i - MvPolynomial.C s : MvPolynomial (Fin n) F) ≠ 0 := by intro h have h2 := congr_arg (MvPolynomial.coeff (Finsupp.single i 1)) h rw [MvPolynomial.coeff_sub, MvPolynomial.coeff_zero, MvPolynomial.coeff_X, if_pos rfl, MvPolynomial.coeff_C] at h2 have hne : (0 : Fin n →₀ ℕ) ≠ Finsupp.single i 1 := by intro h3 have h4 := Finsupp.ext_iff.mp h3 i simp at h4 rw [if_neg hne, sub_zero] at h2 exact one_ne_zero h2/-- Tightness of the Schwartz-Zippel zero count upper bound via a product of univariate linear factors. -/theorem schwartz_zippel_zero_count_tight {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F] {n : ℕ} (hn : 0 < n) {S : Finset F} {d : ℕ} (hd : d ≤ S.card) : ∃ p : MvPolynomial (Fin n) F, p ≠ 0 ∧ p.totalDegree ≤ d ∧ Finset.card (Finset.filter (fun x => MvPolynomial.eval x p = 0) (Fintype.piFinset (fun _ : Fin n => S))) = d * S.card ^ (n - 1) := by obtain ⟨T, hT, hTcard⟩ := Finset.exists_subset_card_eq hd let i₀ : Fin n := ⟨0, hn⟩ let p : MvPolynomial (Fin n) F := ∏ s ∈ T, (MvPolynomial.X i₀ - MvPolynomial.C s) use p refine ⟨?_, ?_, ?_⟩ · rw [Finset.prod_ne_zero_iff] intro s hs exact schwartz_zippel_zero_count_tight_x_sub_c_ne_zero i₀ s · refine (MvPolynomial.totalDegree_finsetProd T _).trans ?_ have h1 (s : F) (hs : s ∈ T) : (MvPolynomial.X i₀ - MvPolynomial.C s : MvPolynomial (Fin n) F).totalDegree ≤ 1 := (MvPolynomial.totalDegree_sub_C_le (MvPolynomial.X i₀) s).trans (MvPolynomial.totalDegree_X i₀).le have h2 : ∑ s ∈ T, (MvPolynomial.X i₀ - MvPolynomial.C s : MvPolynomial (Fin n) F).totalDegree ≤ ∑ s ∈ T, 1 := Finset.sum_le_sum h1 simp only [Finset.sum_const, nsmul_eq_mul, mul_one] at h2 rw [hTcard] at h2 exact h2 · have h_filter : Finset.filter (fun x => MvPolynomial.eval x p = 0) (Fintype.piFinset (fun _ : Fin n => S)) = Finset.filter (fun x => x i₀ ∈ T) (Fintype.piFinset (fun _ : Fin n => S)) := by apply Finset.filter_congr intro x hx dsimp [p] rw [map_prod] have : (∏ s ∈ T, MvPolynomial.eval x (MvPolynomial.X i₀ - MvPolynomial.C s)) = ∏ s ∈ T, (x i₀ - s) := by apply Finset.prod_congr rfl intro s hs simp rw [this, Finset.prod_eq_zero_iff] simp [sub_eq_zero] rw [h_filter] rw [card_piFinset_filter_apply_mem hn S T hT i₀] rw [hTcard]