quantitative_combinatorial_nullstellensatz
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}.
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.
uses
Polynomial.degree_X_pow,Nat.lt_succ_iff.mpr,Lagrange.coeff_eq_sum,Function.injective_id.injOn,Polynomial.coeff_X_pow,eq_commprivate 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
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.
uses
Fintype.piFinset_univ,Finset.prod_univ_sumprivate 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]
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.
uses
Finset.sum_le_sum,le_antisymm,Finset.sum_eq_sum_iff_of_leprivate 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)
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).
uses
if_pos,Finset.prod_eq_one,quantitative_combinatorial_nullstellensatz_sum_weight,le_rfl,Finset.sum_finset_coeprivate 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
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).
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]
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).
uses
MvPolynomial.eval_monomial,Finsupp.prod_pow,div_eq_mul_inv,Finset.prod_div_distribprivate 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
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.
uses
Finset.sum_congr,Finset.mul_sum,quantitative_combinatorial_nullstellensatz_sum_pi_prod,quantitative_combinatorial_nullstellensatz_pi_weight_productcalc (∑ 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
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).
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]
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.
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_totalDegreehave 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)
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.
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.
- The vector of exponents t is converted to a finitely supported function using Finsupp.equivFunOnFinite.symm, which is a formal artifact of how Mathlib defines multivariate polynomials.
- Points in the grid ∏ S_i are represented as functions a : (i : σ) → S i whose coordinate values are subtypes of F; explicit coercions (a i : F) are used when evaluating or subtracting.
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]