AFTD Auto-Formalizing Theoretical Domains

quantitative_combinatorial_nullstellensatz

theoremverifiedformalization

For a multivariate polynomial f of total degree at most ∑ t_i over a field F, the coefficient of the monomial ∏ x_i^{t_i} equals the sum over points a in the grid ∏ S_i of f(a) divided by ∏_i ∏_{b ∈ S_i \ {a_i}} (a_i - b), where each S_i has cardinality t_i + 1.

Statement

theorem quantitative_combinatorial_nullstellensatz {σ F : Type*} [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]
    (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)
    (f : MvPolynomial σ F) (hdeg : f.totalDegree ≤ ∑ i, t i) :
    MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm t) f =
      ∑ a : (i : σ) → S i,
        (MvPolynomial.eval (fun i => (a i : F)) f) /
        (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b))
Formalizes
arXiv:2610.41820 Lemma 2.1
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
  • monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
  • Cslib.SKI.Polynomial.evalSubstitute terms for the free variables of a polynomial

Read back from the Lean

Let σ be a finite type with decidable equality, and let F be a field with decidable equality. Let t : σ → ℕ be an exponent vector, and let S : σ → Finset F be a family of finite subsets of F such that for each i : σ, the cardinality of S i is t i + 1. Let f : MvPolynomial σ F be a multivariate polynomial whose total degree is at most ∑ i, t i. Then the coefficient in f of the monomial corresponding to t (i.e. ∏ i, X_i^(t i)) is equal to: $$\sum_{a \in \prod_{i : \sigma} S i} \frac{f(a)}{\prod_{i : \sigma} \prod_{b \in S i \setminus \{a i\}} (a i - b)}$$ where the sum is taken over all choice functions a : (i : σ) → S i, evaluated at a coerced to F, and the denominator is the product over all i : σ and all elements b in S i other than a i of (a i - b).

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 establishes the quantitative Combinatorial Nullstellensatz (the Schauz–Lasoń interpolation formula) by decomposing a multivariate polynomial into monomials. For a single variable, Lagrange interpolation applied to X^k shows that the weighted sum over a set S of size t + 1 equals 1 if k = t and 0 if k < t. In several variables, the grid sum for a monomial x^v factors into a product of these univariate sums; when ∑ v_i ≤ ∑ t_i, this product vanishes unless v = t, where it equals 1. Finally, expanding any polynomial of total degree at most ∑ t_i as a linear combination of monomials and swapping the finite sums equates the weighted grid sum of f with the coefficient of ∏ x_i^{t_i}.

  1. For any subset S of size t + 1 in a field and k ≤ t, the weighted sum ∑_{a ∈ S} a^k / ∏_{b ∈ S \ {a}} (a - b) equals 1 if k = t and 0 if k < t.

    Apply the Lagrange interpolation formula (Lagrange.coeff_eq_sum) to the univariate polynomial P(X) = X^k. Since k ≤ t, the degree of P is k < t + 1 = |S| (Polynomial.degree_X_pow, Nat.lt_succ_iff.mpr). Lagrange interpolation expresses the leading coefficient of degree |S| - 1 = t of P as the weighted sum of evaluations P(a) over a ∈ S. The coefficient of X^t in X^k is 1 if k = t and 0 if k < t (Polynomial.coeff_X_pow), which proves the claim.

    lines 1–9

    uses Polynomial.degree_X_pow, Nat.lt_succ_iff.mpr, Lagrange.coeff_eq_sum, Function.injective_id.injOn, Polynomial.coeff_X_pow, eq_comm

    private lemma quantitative_combinatorial_nullstellensatz_sum_weight {F : Type*} [Field F] [DecidableEq F]
        (t : ℕ) (S : Finset F) (hS : S.card = t + 1) {k : ℕ} (hk : k ≤ t) :
        (∑ a ∈ S, a ^ k / ∏ b ∈ S.erase a, (a - b)) = if k = t then 1 else 0 := by
      have hdeg : (Polynomial.X ^ k : Polynomial F).degree < (S.card : WithBot ℕ) := by
        rw [Polynomial.degree_X_pow, hS]
        exact_mod_cast Nat.lt_succ_iff.mpr hk
      have h := Lagrange.coeff_eq_sum (s := S) (v := fun x : F => x) (P := Polynomial.X ^ k)
        Function.injective_id.injOn hdeg
      simpa [hS, hk, Polynomial.coeff_X_pow, eq_comm] using h
  2. The sum over the Cartesian product grid ∏_{i ∈ σ} S_i of a product ∏_{i ∈ σ} f_i(a_i) factors into the product of the univariate sums ∏_{i ∈ σ} ∑_{a ∈ S_i} f_i(a).

    By the generalized distributive law for finite sets (Finset.prod_univ_sum), a product over coordinates of univariate sums expands into the sum over tuples in the Cartesian product of the coordinate-wise products. Identifying the universal set of tuples with the Cartesian product of the finite sets S_i using Fintype.piFinset_univ gives the identity.

    lines 11–18

    uses Fintype.piFinset_univ, Finset.prod_univ_sum

    private lemma quantitative_combinatorial_nullstellensatz_sum_pi_prod {σ F : Type*}
        [Fintype σ] [DecidableEq σ] [Field F] (S : σ → Finset F)
        (f : (i : σ) → S i → F) :
        (∑ a : (i : σ) → S i, ∏ i, f i (a i)) = ∏ i, ∑ a : S i, f i a := by
      classical
      rw [← Fintype.piFinset_univ (β := fun i : σ => S i)]
      rw [← Finset.prod_univ_sum (fun i : σ => (Finset.univ : Finset (S i))) f]
    
  3. If v, t : σ → ℕ satisfy ∑_i v_i ≤ ∑_i t_i and v ≠ t, then there exists some coordinate i such that v_i < t_i.

    We argue by contradiction. Suppose that v_i ≥ t_i for all i. Summing these inequalities gives ∑_i t_i ≤ ∑_i v_i (Finset.sum_le_sum). Combined with the hypothesis ∑_i v_i ≤ ∑_i t_i, antisymmetry (le_antisymm) implies ∑_i t_i = ∑_i v_i. Since t_i ≤ v_i for each coordinate, equality of the sums forces t_i = v_i for all i (Finset.sum_eq_sum_iff_of_le). Hence v = t, contradicting v ≠ t.

    lines 19–31

    uses Finset.sum_le_sum, le_antisymm, Finset.sum_eq_sum_iff_of_le

    private lemma quantitative_combinatorial_nullstellensatz_exists_lt {σ : Type*} [Fintype σ]
        {v t : σ → ℕ} (hsum : ∑ i, v i ≤ ∑ i, t i) (hne : v ≠ t) :
        ∃ i, v i < t i := by
      classical
      by_contra h
      push_neg at h
      have hle : ∑ i, t i ≤ ∑ i, v i := Finset.sum_le_sum fun i _ => h i
      have heq : ∑ i, t i = ∑ i, v i := le_antisymm hle hsum
      have hall : ∀ i, t i = v i := by
        simpa using (Finset.sum_eq_sum_iff_of_le (s := Finset.univ)
          (f := t) (g := v) (fun i _ => h i)).mp heq
      exact hne (funext fun i => (hall i).symm)
    
  4. When v = t, the product over coordinates of the univariate weighted sums equals 1.

    In the case v = t, each coordinate satisfies v_i = t_i. By the univariate lemma (quantitative_combinatorial_nullstellensatz_sum_weight) with k = t_i, each factor in the product evaluates to 1. Since every factor in the finite product is 1, the product is 1 (Finset.prod_eq_one).

    lines 32–49

    uses if_pos, Finset.prod_eq_one, quantitative_combinatorial_nullstellensatz_sum_weight, le_rfl, Finset.sum_finset_coe

    private lemma quantitative_combinatorial_nullstellensatz_pi_weight_product {σ F : Type*}
        [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]
        (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)
        (v : σ →₀ ℕ) (hsum : v.sum (fun _ e => e) ≤ ∑ i, t i) :
        (∏ i : σ, ∑ x : S i,
           (x : F) ^ (v i) / ∏ b ∈ (S i).erase (x : F), ((x : F) - b)) =
        if v = Finsupp.equivFunOnFinite.symm t then 1 else 0 := by
      classical
      by_cases hv : v = Finsupp.equivFunOnFinite.symm t
      · subst hv
        rw [if_pos rfl]
        apply Finset.prod_eq_one
        intro i _
        have h := quantitative_combinatorial_nullstellensatz_sum_weight (t i) (S i) (hS i)
          (le_rfl : t i ≤ t i)
        rw [if_pos rfl] at h
        exact (Finset.sum_finset_coe
          (fun a : F => a ^ (t i) / ∏ b ∈ (S i).erase a, (a - b)) (S i)).trans h
  5. When v ≠ t and ∑_i v_i ≤ ∑_i t_i, the product over coordinates of the univariate weighted sums equals 0.

    In the case v ≠ t, the hypothesis ∑_i v_i ≤ ∑_i t_i implies by quantitative_combinatorial_nullstellensatz_exists_lt that there is some coordinate j with v_j < t_j. For this coordinate j, the univariate lemma (quantitative_combinatorial_nullstellensatz_sum_weight) with k = v_j < t_j evaluates the factor to 0. Since at least one factor in the product is 0, the entire product is 0 (Finset.prod_eq_zero).

    lines 50–66

    uses Finsupp.sum_fintype, quantitative_combinatorial_nullstellensatz_exists_lt, quantitative_combinatorial_nullstellensatz_sum_weight, Nat.le_of_lt, if_neg, ne_of_lt, Finset.sum_finset_coe, Finset.prod_eq_zero, Finset.mem_univ

      · have hvfun : (fun i => v i) ≠ t := by
          intro h
          apply hv
          ext i
          exact congrFun h i
        have hsum' : ∑ i, v i ≤ ∑ i, t i := by
          simpa [Finsupp.sum_fintype] using hsum
        obtain ⟨j, hj⟩ := quantitative_combinatorial_nullstellensatz_exists_lt hsum' hvfun
        have hfac : (∑ x : S j,
            (x : F) ^ (v j) / ∏ b ∈ (S j).erase (x : F), ((x : F) - b)) = 0 := by
          have h := quantitative_combinatorial_nullstellensatz_sum_weight (t j) (S j) (hS j)
            (Nat.le_of_lt hj)
          rw [if_neg (ne_of_lt hj)] at h
          exact (Finset.sum_finset_coe
            (fun a : F => a ^ (v j) / ∏ b ∈ (S j).erase a, (a - b)) (S j)).trans h
        rw [Finset.prod_eq_zero (Finset.mem_univ j) hfac, if_neg hv]
    
  6. For a monomial term c · x^v, the evaluation at grid point a divided by the product of coordinate differences factors as c ∏_i f_i(a_i), where f_i(x) = x^{v_i} / ∏_{b ∈ S_i \ {x}} (x - b).

    Evaluating the monomial c · x^v at tuple a gives c ∏_i (a_i)^{v_i} (MvPolynomial.eval_monomial, Finsupp.prod_pow). Dividing by the product of differences ∏_i ∏_{b ∈ S_i \ {a_i}} (a_i - b) distributes coordinate-wise across the product over i (Finset.prod_div_distrib), factoring the expression into c times the product of coordinate terms f_i(a_i).

    lines 67–86

    uses MvPolynomial.eval_monomial, Finsupp.prod_pow, div_eq_mul_inv, Finset.prod_div_distrib

    private lemma quantitative_combinatorial_nullstellensatz_monomial_weighted_eval {σ F : Type*}
        [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]
        (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)
        (v : σ →₀ ℕ) (c : F) (hsum : v.sum (fun _ e => e) ≤ ∑ i, t i) :
        (∑ a : (i : σ) → S i,
           MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /
           (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b))) =
        if v = Finsupp.equivFunOnFinite.symm t then c else 0 := by
      classical
      let f : (i : σ) → S i → F := fun i x =>
        (x : F) ^ (v i) / ∏ b ∈ (S i).erase (x : F), ((x : F) - b)
      have hterm : ∀ a : (i : σ) → S i,
          MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /
            (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) =
          c * ∏ i, f i (a i) := by
        intro a
        dsimp [f]
        rw [MvPolynomial.eval_monomial, Finsupp.prod_pow]
        rw [div_eq_mul_inv, Finset.prod_div_distrib]
        ring
  7. The weighted grid sum of the monomial c · x^v equals c if v = t and 0 if v ≠ t.

    Factoring out the constant c (Finset.mul_sum), the remaining sum of products over the Cartesian grid factors into the product of univariate sums via quantitative_combinatorial_nullstellensatz_sum_pi_prod. Applying quantitative_combinatorial_nullstellensatz_pi_weight_product, this product is 1 if v = t and 0 otherwise, so the entire expression simplifies to c when v = t and 0 when v ≠ t.

    lines 87–104

    uses Finset.sum_congr, Finset.mul_sum, quantitative_combinatorial_nullstellensatz_sum_pi_prod, quantitative_combinatorial_nullstellensatz_pi_weight_product

      calc
        (∑ a : (i : σ) → S i,
           MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /
           (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)))
            = ∑ a : (i : σ) → S i, c * ∏ i, f i (a i) := by
              exact Finset.sum_congr rfl fun a _ => hterm a
        _ = c * ∑ a : (i : σ) → S i, ∏ i, f i (a i) := by rw [Finset.mul_sum]
        _ = c * ∏ i : σ, ∑ x : S i, f i x := by
              rw [quantitative_combinatorial_nullstellensatz_sum_pi_prod]
        _ = c * (if v = Finsupp.equivFunOnFinite.symm t then 1 else 0) := by
              have hprod : (∏ i : σ, ∑ x : S i, f i x) =
                  if v = Finsupp.equivFunOnFinite.symm t then 1 else 0 := by
                dsimp [f]
                exact quantitative_combinatorial_nullstellensatz_pi_weight_product t S hS v hsum
              rw [hprod]
        _ = if v = Finsupp.equivFunOnFinite.symm t then c else 0 := by
              split_ifs <;> simp
    
  8. The coefficient of x^t in f equals the sum over all exponent vectors v in the support of f of (if v = t then c_v else 0).

    Writing f as the sum of its monomials over its support (MvPolynomial.as_sum) and distributing the coefficient operator across the sum (MvPolynomial.coeff_sum), each monomial c_v x^v contributes c_v when v = t and 0 otherwise (MvPolynomial.coeff_monomial).

    lines 105–121

    uses MvPolynomial.as_sum, MvPolynomial.coeff_sum, Finset.sum_congr, MvPolynomial.coeff_monomial

    /-- Quantitative Combinatorial Nullstellensatz coefficient interpolation formula over finite grids in a field. -/
    theorem quantitative_combinatorial_nullstellensatz {σ F : Type*} [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]
        (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)
        (f : MvPolynomial σ F) (hdeg : f.totalDegree ≤ ∑ i, t i) :
        MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm t) f =
          ∑ a : (i : σ) → S i,
            (MvPolynomial.eval (fun i => (a i : F)) f) /
            (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by
      classical
      have hcoeff : MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm t) f =
          ∑ v ∈ f.support,
            if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by
        conv_lhs => rw [MvPolynomial.as_sum f]
        rw [MvPolynomial.coeff_sum]
        apply Finset.sum_congr rfl
        intro v hv
        rw [MvPolynomial.coeff_monomial]
  9. The weighted grid sum of f equals the sum over v in the support of f of (if v = t then c_v else 0).

    Decomposing f into its constituent monomials, evaluation distributes across the sum (map_sum), and dividing by the difference product distributes term by term (Finset.sum_div). Swapping the grid sum and the support sum (Finset.sum_comm) isolates the weighted grid sum for each monomial. Since the degree of each monomial in the support is at most the total degree of f (MvPolynomial.le_totalDegree), which is at most ∑ t_i, the monomial formula (quantitative_combinatorial_nullstellensatz_monomial_weighted_eval) evaluates each inner sum to c_v if v = t and 0 otherwise.

    lines 122–160

    uses MvPolynomial.as_sum, map_sum, Finset.sum_congr, Finset.sum_div, Finset.sum_comm, quantitative_combinatorial_nullstellensatz_monomial_weighted_eval, le_trans, MvPolynomial.le_totalDegree

      have hsum_rhs :
          (∑ a : (i : σ) → S i,
            (MvPolynomial.eval (fun i => (a i : F)) f) /
            (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b))) =
          ∑ v ∈ f.support,
            if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by
        have h_eval_sum : ∀ a : (i : σ) → S i,
            MvPolynomial.eval (fun i => (a i : F)) f =
              ∑ v ∈ f.support,
                MvPolynomial.eval (fun i => (a i : F))
                  (MvPolynomial.monomial v (MvPolynomial.coeff v f)) := by
          intro a
          conv_lhs => rw [MvPolynomial.as_sum f]
          exact map_sum (MvPolynomial.eval (fun i => (a i : F)))
            (fun v => MvPolynomial.monomial v (MvPolynomial.coeff v f)) f.support
        calc
          (∑ a : (i : σ) → S i,
            (MvPolynomial.eval (fun i => (a i : F)) f) /
            (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)))
              = ∑ a : (i : σ) → S i,
                  ∑ v ∈ f.support,
                    (MvPolynomial.eval (fun i => (a i : F))
                      (MvPolynomial.monomial v (MvPolynomial.coeff v f))) /
                    (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by
                apply Finset.sum_congr rfl
                intro a _
                rw [h_eval_sum a, Finset.sum_div]
          _ = ∑ v ∈ f.support,
                  ∑ a : (i : σ) → S i,
                    (MvPolynomial.eval (fun i => (a i : F))
                      (MvPolynomial.monomial v (MvPolynomial.coeff v f))) /
                    (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by
                rw [Finset.sum_comm]
          _ = ∑ v ∈ f.support,
                  if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by
                apply Finset.sum_congr rfl
                intro v hv
                exact quantitative_combinatorial_nullstellensatz_monomial_weighted_eval t S hS v
                  (MvPolynomial.coeff v f) (le_trans (MvPolynomial.le_totalDegree hv) hdeg)
  10. The coefficient of x^t in f equals the weighted sum of f(a) over all grid points a in ∏_i S_i.

    Both the coefficient of x^t in f and the weighted grid sum were proven in the previous two steps to equal ∑_{v ∈ support(f)} (if v = t then c_v else 0). Substituting these two identities equates the coefficient with the grid sum.

    line 161

      rw [hcoeff, hsum_rhs]
Polynomial.degree_X_pow
The degree of the univariate monomial X^n is n.
Nat.lt_succ_iff.mpr
For natural numbers, k ≤ t implies k < t + 1.
Lagrange.coeff_eq_sum
For an injective evaluation map on a finite set s and a polynomial P with deg(P) < |s|, the coefficient of degree |s| - 1 in P equals the sum over i ∈ s of P(v(i)) / ∏_{j ≠ i} (v(i) - v(j)).
Function.injective_id.injOn
The identity function is injective on any subset.
Polynomial.coeff_X_pow
The coefficient of X^n in the monomial X^k is 1 if n = k and 0 otherwise.
eq_comm
Symmetry of equality: a = b is equivalent to b = a.
quantitative_combinatorial_nullstellensatz_sum_weight
For a finite subset S of size t + 1 in a field and k ≤ t, the weighted sum of a^k over a ∈ S equals 1 if k = t and 0 if k < t.
Fintype.piFinset_univ
The Cartesian product of universal sets over a finite index type is the universal set of dependent functions.
Finset.prod_univ_sum
A product of finite sums over independent coordinates factors into the sum over the Cartesian product grid of the coordinate-wise products.
quantitative_combinatorial_nullstellensatz_sum_pi_prod
Summing a product of coordinate functions over all tuples in the grid equals the product over coordinates of the univariate sums.
Finset.sum_le_sum
Pointwise inequality of summands implies the same inequality between their sums.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
Finset.sum_eq_sum_iff_of_le
If f ≤ g pointwise, their sums over a finite set are equal if and only if f = g pointwise.
quantitative_combinatorial_nullstellensatz_exists_lt
If the sum of coordinates of v is at most that of t and v ≠ t, then v_i < t_i for some coordinate i.
if_pos
An if-then-else evaluates to the then-branch when the condition is true.
Finset.prod_eq_one
A finite product in which every factor is 1 equals 1.
le_rfl
Reflexivity of inequality: a ≤ a.
Finset.sum_finset_coe
Summing over the subtype of elements belonging to a finite set equals summing over the set directly.
Finsupp.sum_fintype
On a finite index type, a finitely supported sum can be evaluated as a sum over the full type.
Nat.le_of_lt
A strict inequality between natural numbers implies a non-strict inequality.
if_neg
An if-then-else evaluates to the else-branch when the condition is false.
ne_of_lt
Strict inequality implies inequality: if a < b then a ≠ b.
Finset.prod_eq_zero
A finite product is 0 if at least one factor is 0.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
quantitative_combinatorial_nullstellensatz_pi_weight_product
The product over coordinates of the univariate weighted sums for an exponent vector v equals 1 if v = t and 0 if v ≠ t, provided ∑ v_i ≤ ∑ t_i.
MvPolynomial.eval_monomial
Evaluating a multivariate monomial c · x^s at a point evaluates to c multiplied by the product of powers of coordinate evaluations.
Finsupp.prod_pow
A product over a finitely supported function of powers equals the product over the finite type.
div_eq_mul_inv
Division is multiplication by the multiplicative inverse: a / b = a * b⁻¹.
Finset.prod_div_distrib
A finite product of quotients equals the quotient of the products.
Finset.sum_congr
Sums over equal sets with equal summands are equal.
Finset.mul_sum
Multiplication distributes over a finite sum: c * ∑ x = ∑ c * x.
MvPolynomial.as_sum
A multivariate polynomial equals the sum over its support of its constituent monomials.
MvPolynomial.coeff_sum
Extracting a monomial coefficient commutes with finite sums of polynomials.
MvPolynomial.coeff_monomial
The coefficient of monomial m in the monomial a · x^n is a if n = m and 0 otherwise.
map_sum
An additive monoid homomorphism preserves finite sums.
Finset.sum_div
Division by a scalar distributes over a finite sum: (∑ x) / a = ∑ (x / a).
Finset.sum_comm
Finite double sums can be swapped: Fubini's theorem for finite sums.
quantitative_combinatorial_nullstellensatz_monomial_weighted_eval
For a monomial c · x^v with total degree at most ∑ t_i, the weighted grid sum equals c if v = t and 0 otherwise.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
MvPolynomial.le_totalDegree
The degree of any monomial in the support of a polynomial is bounded by the total degree of the polynomial.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

private lemma quantitative_combinatorial_nullstellensatz_sum_weight {F : Type*} [Field F] [DecidableEq F]    (t : ℕ) (S : Finset F) (hS : S.card = t + 1) {k : ℕ} (hk : k ≤ t) :    (∑ a ∈ S, a ^ k / ∏ b ∈ S.erase a, (a - b)) = if k = t then 1 else 0 := by  have hdeg : (Polynomial.X ^ k : Polynomial F).degree < (S.card : WithBot ℕ) := by    rw [Polynomial.degree_X_pow, hS]    exact_mod_cast Nat.lt_succ_iff.mpr hk  have h := Lagrange.coeff_eq_sum (s := S) (v := fun x : F => x) (P := Polynomial.X ^ k)    Function.injective_id.injOn hdeg  simpa [hS, hk, Polynomial.coeff_X_pow, eq_comm] using hprivate lemma quantitative_combinatorial_nullstellensatz_sum_pi_prod {σ F : Type*}    [Fintype σ] [DecidableEq σ] [Field F] (S : σ → Finset F)    (f : (i : σ) → S i → F) :    (∑ a : (i : σ) → S i, ∏ i, f i (a i)) = ∏ i, ∑ a : S i, f i a := by  classical  rw [← Fintype.piFinset_univ (β := fun i : σ => S i)]  rw [← Finset.prod_univ_sum (fun i : σ => (Finset.univ : Finset (S i))) f]private lemma quantitative_combinatorial_nullstellensatz_exists_lt {σ : Type*} [Fintype σ]    {v t : σ → ℕ} (hsum : ∑ i, v i ≤ ∑ i, t i) (hne : v ≠ t) :    ∃ i, v i < t i := by  classical  by_contra h  push_neg at h  have hle : ∑ i, t i ≤ ∑ i, v i := Finset.sum_le_sum fun i _ => h i  have heq : ∑ i, t i = ∑ i, v i := le_antisymm hle hsum  have hall : ∀ i, t i = v i := by    simpa using (Finset.sum_eq_sum_iff_of_le (s := Finset.univ)      (f := t) (g := v) (fun i _ => h i)).mp heq  exact hne (funext fun i => (hall i).symm)private lemma quantitative_combinatorial_nullstellensatz_pi_weight_product {σ F : Type*}    [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]    (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)    (v : σ →₀ ℕ) (hsum : v.sum (fun _ e => e) ≤ ∑ i, t i) :    (∏ i : σ, ∑ x : S i,       (x : F) ^ (v i) / ∏ b ∈ (S i).erase (x : F), ((x : F) - b)) =    if v = Finsupp.equivFunOnFinite.symm t then 1 else 0 := by  classical  by_cases hv : v = Finsupp.equivFunOnFinite.symm t  · subst hv    rw [if_pos rfl]    apply Finset.prod_eq_one    intro i _    have h := quantitative_combinatorial_nullstellensatz_sum_weight (t i) (S i) (hS i)      (le_rfl : t i ≤ t i)    rw [if_pos rfl] at h    exact (Finset.sum_finset_coe      (fun a : F => a ^ (t i) / ∏ b ∈ (S i).erase a, (a - b)) (S i)).trans h  · have hvfun : (fun i => v i) ≠ t := by      intro h      apply hv      ext i      exact congrFun h i    have hsum' : ∑ i, v i ≤ ∑ i, t i := by      simpa [Finsupp.sum_fintype] using hsum    obtain ⟨j, hj⟩ := quantitative_combinatorial_nullstellensatz_exists_lt hsum' hvfun    have hfac : (∑ x : S j,        (x : F) ^ (v j) / ∏ b ∈ (S j).erase (x : F), ((x : F) - b)) = 0 := by      have h := quantitative_combinatorial_nullstellensatz_sum_weight (t j) (S j) (hS j)        (Nat.le_of_lt hj)      rw [if_neg (ne_of_lt hj)] at h      exact (Finset.sum_finset_coe        (fun a : F => a ^ (v j) / ∏ b ∈ (S j).erase a, (a - b)) (S j)).trans h    rw [Finset.prod_eq_zero (Finset.mem_univ j) hfac, if_neg hv]private lemma quantitative_combinatorial_nullstellensatz_monomial_weighted_eval {σ F : Type*}    [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]    (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)    (v : σ →₀ ℕ) (c : F) (hsum : v.sum (fun _ e => e) ≤ ∑ i, t i) :    (∑ a : (i : σ) → S i,       MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /       (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b))) =    if v = Finsupp.equivFunOnFinite.symm t then c else 0 := by  classical  let f : (i : σ) → S i → F := fun i x =>    (x : F) ^ (v i) / ∏ b ∈ (S i).erase (x : F), ((x : F) - b)  have hterm : ∀ a : (i : σ) → S i,      MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /        (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) =      c * ∏ i, f i (a i) := by    intro a    dsimp [f]    rw [MvPolynomial.eval_monomial, Finsupp.prod_pow]    rw [div_eq_mul_inv, Finset.prod_div_distrib]    ring  calc    (∑ a : (i : σ) → S i,       MvPolynomial.eval (fun i => (a i : F)) (MvPolynomial.monomial v c) /       (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)))        = ∑ a : (i : σ) → S i, c * ∏ i, f i (a i) := by          exact Finset.sum_congr rfl fun a _ => hterm a    _ = c * ∑ a : (i : σ) → S i, ∏ i, f i (a i) := by rw [Finset.mul_sum]    _ = c * ∏ i : σ, ∑ x : S i, f i x := by          rw [quantitative_combinatorial_nullstellensatz_sum_pi_prod]    _ = c * (if v = Finsupp.equivFunOnFinite.symm t then 1 else 0) := by          have hprod : (∏ i : σ, ∑ x : S i, f i x) =              if v = Finsupp.equivFunOnFinite.symm t then 1 else 0 := by            dsimp [f]            exact quantitative_combinatorial_nullstellensatz_pi_weight_product t S hS v hsum          rw [hprod]    _ = if v = Finsupp.equivFunOnFinite.symm t then c else 0 := by          split_ifs <;> simp/-- Quantitative Combinatorial Nullstellensatz coefficient interpolation formula over finite grids in a field. -/theorem quantitative_combinatorial_nullstellensatz {σ F : Type*} [Fintype σ] [DecidableEq σ] [Field F] [DecidableEq F]    (t : σ → ℕ) (S : σ → Finset F) (hS : ∀ i, (S i).card = t i + 1)    (f : MvPolynomial σ F) (hdeg : f.totalDegree ≤ ∑ i, t i) :    MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm t) f =      ∑ a : (i : σ) → S i,        (MvPolynomial.eval (fun i => (a i : F)) f) /        (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by  classical  have hcoeff : MvPolynomial.coeff (Finsupp.equivFunOnFinite.symm t) f =      ∑ v ∈ f.support,        if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by    conv_lhs => rw [MvPolynomial.as_sum f]    rw [MvPolynomial.coeff_sum]    apply Finset.sum_congr rfl    intro v hv    rw [MvPolynomial.coeff_monomial]  have hsum_rhs :      (∑ a : (i : σ) → S i,        (MvPolynomial.eval (fun i => (a i : F)) f) /        (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b))) =      ∑ v ∈ f.support,        if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by    have h_eval_sum : ∀ a : (i : σ) → S i,        MvPolynomial.eval (fun i => (a i : F)) f =          ∑ v ∈ f.support,            MvPolynomial.eval (fun i => (a i : F))              (MvPolynomial.monomial v (MvPolynomial.coeff v f)) := by      intro a      conv_lhs => rw [MvPolynomial.as_sum f]      exact map_sum (MvPolynomial.eval (fun i => (a i : F)))        (fun v => MvPolynomial.monomial v (MvPolynomial.coeff v f)) f.support    calc      (∑ a : (i : σ) → S i,        (MvPolynomial.eval (fun i => (a i : F)) f) /        (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)))          = ∑ a : (i : σ) → S i,              ∑ v ∈ f.support,                (MvPolynomial.eval (fun i => (a i : F))                  (MvPolynomial.monomial v (MvPolynomial.coeff v f))) /                (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by            apply Finset.sum_congr rfl            intro a _            rw [h_eval_sum a, Finset.sum_div]      _ = ∑ v ∈ f.support,              ∑ a : (i : σ) → S i,                (MvPolynomial.eval (fun i => (a i : F))                  (MvPolynomial.monomial v (MvPolynomial.coeff v f))) /                (∏ i : σ, ∏ b ∈ (S i).erase (a i), ((a i : F) - b)) := by            rw [Finset.sum_comm]      _ = ∑ v ∈ f.support,              if v = Finsupp.equivFunOnFinite.symm t then MvPolynomial.coeff v f else 0 := by            apply Finset.sum_congr rfl            intro v hv            exact quantitative_combinatorial_nullstellensatz_monomial_weighted_eval t S hS v              (MvPolynomial.coeff v f) (le_trans (MvPolynomial.le_totalDegree hv) hdeg)  rw [hcoeff, hsum_rhs]
See it in the graphDiscuss this resultChallenge it