AFTD Auto-Formalizing Theoretical Domains

schwartz_zippel_repeated_trials_zero_count_le

theoremverifiedoriginal

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 for every t the number of t-tuples (x_1, …, x_t) of points of S^n at which p vanishes at every one of the t coordinates is at most (d·|S|^(n−1))^t; equivalently, t independent random trials of the evaluation test all fail with probability at most (d/|S|)^t.

Statement

open scoped Finset in
theorem schwartz_zippel_repeated_trials_zero_count_le {F : Type*} [CommRing F] [IsDomain F]
    [DecidableEq F] {n t : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0)
    {S : Finset F} (hS : 0 < S.card) :
    #{X ∈ Fintype.piFinset (fun _ : Fin t => Fintype.piFinset (fun _ : Fin n => S)) |
        ∀ i, MvPolynomial.eval (X i) p = 0}
      ≤ (p.totalDegree * S.card ^ (n - 1)) ^ t
Related work
Amplification by independent repetition of the random-evaluation identity test of Schwartz 1980 / Zippel 1979 (Motwani & Raghavan, Randomized Algorithms, ch. 7). Concepts anchored by Mathlib `MvPolynomial.schwartz_zippel_totalDegree`.
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

For every type F with a commutative ring structure, an integral domain structure, and decidable equality, for all natural numbers n and t with n > 0, for every nonzero polynomial p in n variables over F, and every finite subset S of F with positive cardinality, the number of t-tuples of points of S^n at which p vanishes is at most (p.totalDegree * |S|^(n-1))^t. More explicitly, the tuples are functions X : Fin t → (Fin n → F) such that every coordinate X j i lies in S, and the vanishing condition is that for every j : Fin t, the evaluation of p at the assignment X j : Fin n → F is zero. The bound parses as (p.totalDegree * (S.card ^ (n - 1))) ^ t, because ^ binds more tightly than *; the outer exponent t applies to the whole product.

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 argument identifies the set of joint zeros in (S^n)^t with the t-fold Cartesian product of the single-trial zero set Z = {x ∈ S^n | p(x) = 0}, since a polynomial vanishes at every coordinate of a t-tuple if and only if each coordinate independently belongs to Z. The cardinality of this product is therefore |Z|^t. Bounding |Z| by d · |S|^(n - 1) via the single-trial Schwartz-Zippel lemma and raising both sides to the power t establishes the inequality.

  1. The set of t-tuples in (S^n)^t on which p vanishes at every coordinate equals the t-fold Cartesian product of the zero set {x ∈ S^n | p(x) = 0}.

    By set extensionality (`ext`), a t-tuple X belongs to the set on the left if and only if every coordinate X(i) lies in S^n and satisfies p(X(i)) = 0 (using `Finset.mem_filter` and `Fintype.mem_piFinset`). Distributing the universal quantifier over the conjunction shows this is equivalent to requiring X(i) ∈ {x ∈ S^n | p(x) = 0} for every coordinate i, which is the definition of membership in the product set.

    lines 9–20

    uses Finset.mem_filter, Fintype.mem_piFinset

      have h_set :
        {X ∈ Fintype.piFinset (fun _ : Fin t => Fintype.piFinset (fun _ : Fin n => S)) |
            ∀ i, MvPolynomial.eval (X i) p = 0} =
        Fintype.piFinset (fun _ : Fin t =>
          {x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p = 0}) := by
        ext X
        simp only [Finset.mem_filter, Fintype.mem_piFinset]
        constructor
        · rintro ⟨h1, h2⟩ i
          exact ⟨h1 i, h2 i⟩
        · intro h
          exact ⟨fun i => (h i).1, fun i => (h i).2⟩
  2. The number of such t-tuples is |Z|^t, where Z = {x ∈ S^n | p(x) = 0}.

    Rewriting the set of t-tuples as the Cartesian product Z^t using the set equality `h_set`, its cardinality becomes |Z|^t by `Fintype.card_piFinset_const`.

    line 21

    uses Fintype.card_piFinset_const

      rw [h_set, Fintype.card_piFinset_const]
  3. The t-th power of the number of zeros |Z|^t is bounded by (d · |S|^(n - 1))^t.

    By the Schwartz-Zippel lemma for a single trial (`schwartz_zippel_zero_count_le`), the polynomial p has at most d · |S|^(n - 1) zeros in S^n. Raising both sides of this inequality to the power t via monotonicity of powers (`Nat.pow_le_pow_left`) yields the required bound.

    line 22

    uses Nat.pow_le_pow_left, schwartz_zippel_zero_count_le

      exact Nat.pow_le_pow_left (schwartz_zippel_zero_count_le hn hp hS) t
Finset.mem_filter
An element x belongs to the filtered set {y ∈ s | p y} if and only if x ∈ s and p x holds.
Fintype.mem_piFinset
A function f belongs to the Cartesian product ∏ a, t a if and only if f a ∈ t a for every a.
Fintype.card_piFinset_const
The cardinality of the Cartesian product of n copies of a finite set s is |s|^n.
Nat.pow_le_pow_left
If n ≤ m for natural numbers, then n^i ≤ m^i for any exponent i.
schwartz_zippel_zero_count_le
For a nonzero polynomial p of degree d in n variables over an integral domain and a finite nonempty subset S, the number of zeros of p in S^n is at most d · |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

open scoped Finset in/-- Amplification by repetition: the number of t-tuples of points of S^n that are all zeros of a nonzero polynomial of total degree d is at most (d·|S|^(n−1))^t. -/theorem schwartz_zippel_repeated_trials_zero_count_le {F : Type*} [CommRing F] [IsDomain F]    [DecidableEq F] {n t : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0)    {S : Finset F} (hS : 0 < S.card) :    #{X ∈ Fintype.piFinset (fun _ : Fin t => Fintype.piFinset (fun _ : Fin n => S)) |        ∀ i, MvPolynomial.eval (X i) p = 0}      ≤ (p.totalDegree * S.card ^ (n - 1)) ^ t := by  have h_set :    {X ∈ Fintype.piFinset (fun _ : Fin t => Fintype.piFinset (fun _ : Fin n => S)) |        ∀ i, MvPolynomial.eval (X i) p = 0} =    Fintype.piFinset (fun _ : Fin t =>      {x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p = 0}) := by    ext X    simp only [Finset.mem_filter, Fintype.mem_piFinset]    constructor    · rintro ⟨h1, h2⟩ i      exact ⟨h1 i, h2 i⟩    · intro h      exact ⟨fun i => (h i).1, fun i => (h i).2⟩  rw [h_set, Fintype.card_piFinset_const]  exact Nat.pow_le_pow_left (schwartz_zippel_zero_count_le hn hp hS) t
See it in the graphDiscuss this resultChallenge it