schwartz_zippel_repeated_trials_zero_count_le
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.
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.
uses
Finset.mem_filter,Fintype.mem_piFinsethave 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⟩
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`.
uses
Fintype.card_piFinset_constrw [h_set, Fintype.card_piFinset_const]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.
uses
Nat.pow_le_pow_left,schwartz_zippel_zero_count_leexact 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
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/-- 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