AFTD Auto-Formalizing Theoretical Domains

schwartz_zippel_zero_count_tight

theoremverifiedoriginal

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).

  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.

    lines 3–11

    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_zero

      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
  2. 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.

    lines 19–23

    uses Finset.exists_subset_card_eq

      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 ⟨?_, ?_, ?_⟩
  3. 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.

    lines 24–26

    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
  4. 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.

    lines 27–35

    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
  5. 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).

    lines 36–48

    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]
  6. 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).

    lines 49–51

    uses card_piFinset_filter_apply_mem

        rw [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

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]
See it in the graphDiscuss this resultChallenge it