AFTD Auto-Formalizing Theoretical Domains

mv_polynomial_eq_zero_of_eval_eq_zero_on_finset

theoremverifiedformalization

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.

  1. Assume for contradiction that p ≠ 0.

    We enable classical logic (allowing decidability of propositions) and begin an indirect proof by assuming p ≠ 0.

    lines 3–4

      classical
      by_contra hp
  2. The 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.

    line 5

    uses MvPolynomial.schwartz_zippel_totalDegree

      have h_sz := MvPolynomial.schwartz_zippel_totalDegree hp S
  3. The 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.

    lines 6–12

    uses Finset.filter_true_of_mem, Fintype.mem_piFinset

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

    lines 13–16

    uses Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_fin

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

    lines 17–19

    uses div_self, ne_of_gt

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

    lines 20–23

    uses div_lt_one, Nat.cast_lt.mpr

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

    line 24

    uses not_le_of_gt

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

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

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