positive_coefficient_selected_linear_product
Selecting a variable in each linear form with natural coefficients gives a positive coefficient of the corresponding product monomial.
Statement
theorem positive_coefficient_selected_linear_product {E V : Type*} [DecidableEq E] [DecidableEq V] (s : Finset E) (A : E → Finset V) (f : E → V) (hf : ∀ e ∈ s, f e ∈ A e) : 0 < (∏ e ∈ s, (∑ w ∈ A e, X w : MvPolynomial V ℕ)).coeff (∑ e ∈ s, Finsupp.single (f e) 1)
- Source
- Helper for OP-494 in arXiv:2610.30174, following the additive-list coloring argument of arXiv:2302.02190v3, Corollary 5.3. Induct over the factors. In the coefficient convolution retain the positive term given by the selected monomials; all other terms are nonnegative.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- exists_signed_nonzero_linear_formsA family of sums of variables admits a simultaneous nonzero evaluation on finite integer lists whose sizes exceed the selection…
The proof, explained
The theorem is proved by induction on the finite set s. In the base case s = ∅, the empty product is 1 and its constant term is 1 > 0. In the induction step, the product and target exponent are factored into the contribution of a new element e and the product over s, expanding the coefficient as an antidiagonal sum. Because the coefficients are natural numbers, the total coefficient is bounded below by the product of the individual coefficients for the two parts, each of which is strictly positive by the choice of variable and the induction hypothesis.
The claim holds in the base case where s is the empty set. automation
We proceed by induction on the finite set s using Finset.induction_on. When s = ∅, the product of polynomials is the empty product 1, and the target exponent vector is the empty sum 0. The constant term of 1 is 1 > 0, which simp verifies directly.
uses
Finset.induction_oninduction s using Finset.induction_on with | empty => simp
In the induction step, the coefficient of the monomial in the extended product expands as an antidiagonal sum over products of coefficients.
Assuming the result holds for s, consider insert e s with e ∉ s. Using Finset.prod_insert, the polynomial product factors into the single linear form for e times the product over s. Using Finset.sum_insert, the target exponent splits into the single basis vector Finsupp.single (f e) 1 plus the exponent sum over s. Then coeff_mul expresses the coefficient of this sum in the product polynomial as a sum over all pairs in the antidiagonal of the products of their respective coefficients.
uses
Finset.prod_insert,Finset.sum_insert,coeff_mul| @insert e s hes ih => rw [Finset.prod_insert hes, Finset.sum_insert hes, coeff_mul]The coefficient of Finsupp.single (f e) 1 in the linear form ∑ w ∈ A e, X w is strictly positive.
Rewriting the coefficient of the sum as the sum of coefficients with coeff_sum, each term is a natural number and hence nonnegative (Nat.zero_le). Because f e ∈ A e by hypothesis hf and Finset.mem_insert_self, Finset.single_le_sum bounds the sum below by the single term corresponding to w = f e. That single coefficient is 1 > 0, so by lt_of_lt_of_le, the coefficient in the linear form is strictly positive.
uses
coeff_sum,Finset.single_le_sum,Nat.zero_le,Finset.mem_insert_self,lt_of_lt_of_lehave hfirst : 0 < (∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1) := by rw [coeff_sum] have hle := Finset.single_le_sum (fun w (_ : w ∈ A e) => Nat.zero_le ((X w : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1))) (hf e (Finset.mem_insert_self _ _)) simpa using (lt_of_lt_of_le (by simp : 0 < (X (f e) : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1)) hle)
By induction, the coefficient of ∑ x ∈ s, Finsupp.single (f x) 1 in ∏ x ∈ s, ∑ w ∈ A x, X w is strictly positive.
We apply the induction hypothesis ih to s. The prerequisite that f x ∈ A x for each x ∈ s follows from the hypothesis on insert e s via Finset.mem_insert_of_mem.
uses
Finset.mem_insert_of_memhave hrest := ih (fun e he => hf e (Finset.mem_insert_of_mem he))
The full coefficient in the product polynomial is strictly positive.
The product of the two positive coefficients hfirst and hrest is strictly positive by Nat.mul_pos. By lt_of_lt_of_le, it suffices to show this product is bounded by the total antidiagonal sum. The pair (Finsupp.single (f e) 1, ∑ x ∈ s, Finsupp.single (f x) 1) belongs to the antidiagonal by Finset.HasAntidiagonal.mem_antidiagonal.mpr. Because all terms in the antidiagonal sum are nonnegative products in ℕ (Nat.zero_le), Finset.single_le_sum bounds the sum from below by this single term, completing the induction step.
uses
lt_of_lt_of_le,Nat.mul_pos,Finset.single_le_sum,Nat.zero_le,Finset.HasAntidiagonal.mem_antidiagonal.mprapply lt_of_lt_of_le (Nat.mul_pos hfirst hrest) exact Finset.single_le_sum (f := fun p : (V →₀ ℕ) × (V →₀ ℕ) => (∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff p.1 * (∏ e ∈ s, ∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff p.2) (a := (Finsupp.single (f e) 1, ∑ e ∈ s, Finsupp.single (f e) 1)) (fun _ _ => Nat.zero_le _) (Finset.HasAntidiagonal.mem_antidiagonal.mpr rfl)
Finset.induction_on- The induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved by inserting an element.
Finset.prod_insert- Splits a product over an inserted element: ∏ x ∈ insert a s, f x = f a * ∏ x ∈ s, f x when a ∉ s.
Finset.sum_insert- Splits a sum over an inserted element: ∑ x ∈ insert a s, f x = f a + ∑ x ∈ s, f x when a ∉ s.
coeff_mul- The coefficient of a monomial in the product of two polynomials is the sum over the antidiagonal of its exponent of the products of their coefficients.
coeff_sum- The coefficient of a monomial in a finite sum of polynomials is the sum of its coefficients in each summand.
Finset.single_le_sum- A single term in a finite sum is less than or equal to the total sum, provided all terms are nonnegative.
Nat.zero_le- Zero is less than or equal to any natural number (0 ≤ n).
Finset.mem_insert_self- An element a is always a member of insert a s.
lt_of_lt_of_le- Strict inequality is preserved when composed with a weak inequality: a < b and b ≤ c imply a < c.
Finset.mem_insert_of_mem- If an element belongs to s, it belongs to insert b s.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive (0 < n and 0 < m imply 0 < n * m).
Finset.HasAntidiagonal.mem_antidiagonal.mpr- A pair (a, b) belongs to the antidiagonal of c if and only if a + b = c.
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.
open scoped BigOperatorsopen MvPolynomialtheorem positive_coefficient_selected_linear_product {E V : Type*} [DecidableEq E] [DecidableEq V] (s : Finset E) (A : E → Finset V) (f : E → V) (hf : ∀ e ∈ s, f e ∈ A e) : 0 < (∏ e ∈ s, (∑ w ∈ A e, X w : MvPolynomial V ℕ)).coeff (∑ e ∈ s, Finsupp.single (f e) 1) := by induction s using Finset.induction_on with | empty => simp | @insert e s hes ih => rw [Finset.prod_insert hes, Finset.sum_insert hes, coeff_mul] have hfirst : 0 < (∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1) := by rw [coeff_sum] have hle := Finset.single_le_sum (fun w (_ : w ∈ A e) => Nat.zero_le ((X w : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1))) (hf e (Finset.mem_insert_self _ _)) simpa using (lt_of_lt_of_le (by simp : 0 < (X (f e) : MvPolynomial V ℕ).coeff (Finsupp.single (f e) 1)) hle) have hrest := ih (fun e he => hf e (Finset.mem_insert_of_mem he)) apply lt_of_lt_of_le (Nat.mul_pos hfirst hrest) exact Finset.single_le_sum (f := fun p : (V →₀ ℕ) × (V →₀ ℕ) => (∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff p.1 * (∏ e ∈ s, ∑ w ∈ A e, X w : MvPolynomial V ℕ).coeff p.2) (a := (Finsupp.single (f e) 1, ∑ e ∈ s, Finsupp.single (f e) 1)) (fun _ _ => Nat.zero_le _) (Finset.HasAntidiagonal.mem_antidiagonal.mpr rfl)