AFTD Auto-Formalizing Theoretical Domains

schwartz_zippel_union_bound_zero_set

theoremverifiedoriginal

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

  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.

    lines 9–15

    uses Finset.mem_filter, Finset.mem_biUnion, Finset.mem_univ, true_and

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

    lines 16–18

    uses Finset.card_le_card

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

    lines 19–31

    uses schwartz_zippel_zero_count_le, Nat.mul_le_mul_right, le_trans, Finset.card_biUnion_le_card_mul, Finset.card_fin

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

    line 32

    uses le_trans

      exact 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

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