mv_polynomial_eq_zero_of_eval_eq_zero_on_finset
Let R be an integral domain and p be a multivariate polynomial in n variables over R. If S is a finite subset of R with cardinality strictly greater than the total degree of p, and p evaluates to zero at every point of the product S^n, then p is the zero polynomial.
Statement
theorem mv_polynomial_eq_zero_of_eval_eq_zero_on_finset {n : ℕ} {R : Type*} [CommRing R] [IsDomain R] (p : MvPolynomial (Fin n) R) (S : Finset R) (hcard : p.totalDegree < S.card) (h_eval : ∀ f : Fin n → R, (∀ i, f i ∈ S) → MvPolynomial.eval f p = 0) : p = 0
- Formalizes
- Shpilka & Yehudayoff 2010, Lemma 2.1; Schwartz 1980; Zippel 1979
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Let $n$ be a natural number and let $R$ be a commutative ring that is an integral domain. Let $p$ be a multivariate polynomial with variables indexed by Fin n and coefficients in $R$ (MvPolynomial (Fin n) R), and let $S$ be a finite subset of $R$ (Finset R). If the total degree of $p$ is strictly less than the cardinality of $S$ (p.totalDegree < S.card), and if for every function $f : \text{Fin } n \to R$ such that $f(i) \in S$ for all $i : \text{Fin } n$, the evaluation of $p$ at $f$ is zero (MvPolynomial.eval f p = 0), then $p = 0$.
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 proof proceeds by contradiction: assume p ≠ 0. The Schwartz-Zippel lemma states that the fraction of points in the grid S^n on which p vanishes is at most deg(p) / |S|. Since p evaluates to zero on all of S^n by assumption, this fraction is |S|^n / |S|^n = 1. However, the hypothesis deg(p) < |S| implies deg(p) / |S| < 1, yielding the contradiction 1 ≤ deg(p) / |S| < 1.
Assume for contradiction that p ≠ 0.
We enable classical logic (allowing decidability of propositions) and begin an indirect proof by assuming p ≠ 0.
classical by_contra hpThe proportion of zeros of p in the grid S^n is bounded above by deg(p) / |S|.
Applying the Schwartz-Zippel lemma (MvPolynomial.schwartz_zippel_totalDegree) to the nonzero polynomial p and finite set S bounds the fraction of roots in S^n by deg(p) / |S| in ℚ≥0.
uses
MvPolynomial.schwartz_zippel_totalDegreehave h_sz := MvPolynomial.schwartz_zippel_totalDegree hp SThe zero set of p on S^n is the entire grid S^n.
By assumption h_eval, p evaluates to 0 on every point f whose coordinates all belong to S. Applying Finset.filter_true_of_mem shows that filtering the Cartesian product S^n by the vanishing condition p(f) = 0 leaves the entire set S^n.
uses
Finset.filter_true_of_mem,Fintype.mem_piFinsethave h_eq : {f ∈ Fintype.piFinset (fun (_ : Fin n) ↦ S) | MvPolynomial.eval f p = 0} = Fintype.piFinset (fun (_ : Fin n) ↦ S) := by apply Finset.filter_true_of_mem intro f hf apply h_eval intro i rw [Fintype.mem_piFinset] at hf exact hf i
The Schwartz-Zippel inequality reduces to |S|^n / |S|^n ≤ deg(p) / |S|.
Substituting the identity of the root set into the Schwartz-Zippel inequality gives |S^n| / |S|^n ≤ deg(p) / |S|. The cardinality of the product is |S|^n by Fintype.card_piFinset and Finset.prod_const. Pushing the natural-number casts into ℚ≥0 yields |S|^n / |S|^n ≤ deg(p) / |S|.
uses
Fintype.card_piFinset,Finset.prod_const,Finset.card_univ,Fintype.card_finrw [h_eq] at h_sz rw [Fintype.card_piFinset] at h_sz simp only [Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sz push_cast at h_sz
The left-hand side of the Schwartz-Zippel inequality equals 1, yielding 1 ≤ deg(p) / |S|.
Since |S| > deg(p) ≥ 0, S is non-empty, so |S|^n is strictly positive. Dividing |S|^n by itself gives 1 via div_self, simplifying the bound to 1 ≤ deg(p) / |S|.
uses
div_self,ne_of_gthave hScard_pos : 0 < S.card := by omega have hpow_pos : (0 : ℚ≥0) < (S.card : ℚ≥0) ^ n := by positivity rw [div_self (ne_of_gt hpow_pos)] at h_sz
The ratio deg(p) / |S| is strictly less than 1.
Because |S| > 0, the quotient deg(p) / |S| is strictly less than 1 if and only if deg(p) < |S| (by div_lt_one). This holds by casting the hypothesis hcard from ℕ to ℚ≥0.
uses
div_lt_one,Nat.cast_lt.mprhave hS_pos : (0 : ℚ≥0) < (S.card : ℚ≥0) := by positivity have h_lt : (p.totalDegree : ℚ≥0) / (S.card : ℚ≥0) < 1 := by rw [div_lt_one hS_pos] exact Nat.cast_lt.mpr hcard
Contradiction, concluding p = 0.
The strict inequality deg(p) / |S| < 1 contradicts 1 ≤ deg(p) / |S| via not_le_of_gt, concluding the proof by contradiction.
uses
not_le_of_gtexact not_le_of_gt h_lt h_sz
MvPolynomial.schwartz_zippel_totalDegree- For a nonzero multivariate polynomial p over an integral domain and a finite set S, the fraction of points in S^n where p evaluates to 0 is at most deg(p) / |S| (in ℚ≥0).
Finset.filter_true_of_mem- Filtering a finite set by a predicate that holds for all of its elements returns the entire set.
Fintype.mem_piFinset- A function belongs to the Cartesian product ∏_i S_i if and only if each coordinate value f(i) belongs to S_i.
Fintype.card_piFinset- The cardinality of a Cartesian product of finite sets is the product of the cardinalities of the factors.
Finset.prod_const- The product of a constant element over a finite set equals that element raised to the cardinality of the set.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
div_self- Any nonzero element divided by itself equals 1.
ne_of_gt- If b < a in a preorder, then a ≠ b.
div_lt_one- For a strictly positive denominator b, a / b < 1 if and only if a < b.
Nat.cast_lt.mpr- If a < b for natural numbers, then their casts into a linearly ordered semiring satisfy ↑a < ↑b.
not_le_of_gt- If a < b in a preorder, then b ≤ a does not hold.
- The Schwartz-Zippel inequality and subsequent comparisons are formally carried out in the non-negative rationals ℚ≥0. This necessitates non-trivial type casts (push_cast) and non-zeroness proofs (via positivity and omega) that are standard or implicit in a pen-and-paper presentation.
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.
/-- A multivariate polynomial over an integral domain vanishing on a grid S^n with |S| > deg(p) is zero. -/theorem mv_polynomial_eq_zero_of_eval_eq_zero_on_finset {n : ℕ} {R : Type*} [CommRing R] [IsDomain R] (p : MvPolynomial (Fin n) R) (S : Finset R) (hcard : p.totalDegree < S.card) (h_eval : ∀ f : Fin n → R, (∀ i, f i ∈ S) → MvPolynomial.eval f p = 0) : p = 0 := by classical by_contra hp have h_sz := MvPolynomial.schwartz_zippel_totalDegree hp S have h_eq : {f ∈ Fintype.piFinset (fun (_ : Fin n) ↦ S) | MvPolynomial.eval f p = 0} = Fintype.piFinset (fun (_ : Fin n) ↦ S) := by apply Finset.filter_true_of_mem intro f hf apply h_eval intro i rw [Fintype.mem_piFinset] at hf exact hf i rw [h_eq] at h_sz rw [Fintype.card_piFinset] at h_sz simp only [Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sz push_cast at h_sz have hScard_pos : 0 < S.card := by omega have hpow_pos : (0 : ℚ≥0) < (S.card : ℚ≥0) ^ n := by positivity rw [div_self (ne_of_gt hpow_pos)] at h_sz have hS_pos : (0 : ℚ≥0) < (S.card : ℚ≥0) := by positivity have h_lt : (p.totalDegree : ℚ≥0) / (S.card : ℚ≥0) < 1 := by rw [div_lt_one hS_pos] exact Nat.cast_lt.mpr hcard exact not_le_of_gt h_lt h_sz