AFTD Auto-Formalizing Theoretical Domains

schwartz_zippel_nonzero_count_ge

theoremverified

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 the number of points of S^n at which p does not vanish is at least |S|^n − d·|S|^(n−1); equivalently, at least a fraction 1 − d/|S| of the points of S^n are nonzero for p. This is the guarantee of the random-evaluation identity test: a point where p is nonzero certifies p ≠ 0, so the test has one-sided error and rejects a nonzero p with probability at most d/|S|.

Statement

open scoped Finset in
theorem schwartz_zippel_nonzero_count_ge {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F]
    {n : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0) {S : Finset F}
    (hS : 0 < S.card) :
    S.card ^ n - p.totalDegree * S.card ^ (n - 1)
      ≤ #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p ≠ 0}
Source
Schwartz 1980; Zippel 1979, in the one-sided-error form used for the randomized identity test (Motwani & Raghavan, Randomized Algorithms, ch. 7); companion of 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

The declaration universally quantifies over a type F carrying a commutative ring structure, an integral-domain structure, and decidable equality; over a natural number n with 0 < n; over a nonzero multivariate polynomial p in n variables over F; and over a finite subset S of F with 0 < S.card. It asserts that the number of n-tuples x : Fin n → F whose coordinates all lie in S and at which p evaluates to a nonzero element is at least S.card ^ n - p.totalDegree * S.card ^ (n - 1), where p.totalDegree is the total degree of p and the subtraction is the truncated subtraction of natural numbers. Equivalently, the count is at least max(0, |S|^n - deg(p) * |S|^(n-1)).

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 total number of points in the grid S^n is |S|^n, partitioned into the points where p vanishes and those where p does not vanish. By the Schwartz–Zippel lemma (`schwartz_zippel_zero_count_le`), the zero set contains at most d · |S|^(n−1) points. Subtracting this upper bound from |S|^n yields the required lower bound of |S|^n − d · |S|^(n−1) on the number of nonzeros.

  1. The polynomial p vanishes at at most d · |S|^(n−1) points in S^n, where d is the total degree of p.

    This is the standard Schwartz–Zippel bound (`schwartz_zippel_zero_count_le`), which bounds the number of roots of a nonzero multivariate polynomial over an integral domain in a finite grid S^n.

    line 8

    uses schwartz_zippel_zero_count_le

      have h_le := schwartz_zippel_zero_count_le hn hp hS
  2. The number of zeros of p in S^n plus the number of nonzeros of p in S^n equals |S|^n.

    Any finite set is partitioned into elements satisfying a predicate and those satisfying its negation (`Finset.card_filter_add_card_filter_not`). Here the ambient set is the Cartesian product S^n (`Fintype.piFinset`), and simplifying its cardinality via `Fintype.card_piFinset`, `Finset.prod_const`, `Finset.card_univ`, and `Fintype.card_fin` shows that |S^n| = |S|^n.

    lines 9–11

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

      have h_sum := Finset.card_filter_add_card_filter_not (s := Fintype.piFinset (fun _ : Fin n => S))
        (fun x => MvPolynomial.eval x p = 0)
      simp only [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sum
  3. The number of points in S^n where p does not vanish is at least |S|^n − d · |S|^(n−1). automation

    After rewriting p(x) ≠ 0 to ¬(p(x) = 0) via `ne_eq` to match the partition identity, linear integer arithmetic (`omega`) subtracts the upper bound on zeros from the total count |S|^n to obtain the desired lower bound on nonzeros.

    lines 12–13

    uses ne_eq

      simp only [ne_eq]
      omega
Finset.card_filter_add_card_filter_not
For any finite set s and predicate p, the number of elements in s satisfying p plus the number of elements satisfying ¬p equals |s|.
Finset.card_univ
The cardinality of the universal set Finset.univ of a finite type α is the cardinality of α.
Finset.prod_const
The product of a constant value over a finite set equals the constant raised to the power of the set's size.
Fintype.card_fin
The finite type Fin n (the integers 0, 1, ..., n − 1) has cardinality n.
Fintype.card_piFinset
The cardinality of the Cartesian product of a finite family of finite sets is the product of their cardinalities.
ne_eq
Inequality a ≠ b is equivalent to the negation ¬(a = b).
schwartz_zippel_zero_count_le
A nonzero polynomial of total degree d in n variables over an integral domain vanishes on at most d · |S|^(n−1) points of S^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/-- At least |S|^n − d·|S|^(n−1) points of S^n are nonzero for a nonzero polynomial of total degree d. -/theorem schwartz_zippel_nonzero_count_ge {F : Type*} [CommRing F] [IsDomain F] [DecidableEq F]    {n : ℕ} (hn : 0 < n) {p : MvPolynomial (Fin n) F} (hp : p ≠ 0) {S : Finset F}    (hS : 0 < S.card) :    S.card ^ n - p.totalDegree * S.card ^ (n - 1)      ≤ #{x ∈ Fintype.piFinset (fun _ : Fin n => S) | MvPolynomial.eval x p ≠ 0} := by  have h_le := schwartz_zippel_zero_count_le hn hp hS  have h_sum := Finset.card_filter_add_card_filter_not (s := Fintype.piFinset (fun _ : Fin n => S))    (fun x => MvPolynomial.eval x p = 0)  simp only [Fintype.card_piFinset, Finset.prod_const, Finset.card_univ, Fintype.card_fin] at h_sum  simp only [ne_eq]  omega
See it in the graphDiscuss this resultChallenge it