AFTD Auto-Formalizing Theoretical Domains

positive_coefficient_selected_linear_product

theoremverified

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

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.

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

    lines 10–11

    uses Finset.induction_on

      induction s using Finset.induction_on with
      | empty => simp
  2. 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.

    lines 12–13

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

    lines 14–22

    uses coeff_sum, Finset.single_le_sum, Nat.zero_le, Finset.mem_insert_self, lt_of_lt_of_le

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

    line 23

    uses Finset.mem_insert_of_mem

        have hrest := ih (fun e he => hf e (Finset.mem_insert_of_mem he))
  5. 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.

    lines 24–30

    uses lt_of_lt_of_le, Nat.mul_pos, Finset.single_le_sum, Nat.zero_le, Finset.HasAntidiagonal.mem_antidiagonal.mpr

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

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