AFTD Auto-Formalizing Theoretical Domains

polynomial_log_concave_erase_top

theoremverified

Erasing the highest-degree coefficient of a natural polynomial preserves log-concavity and interval support.

Statement

theorem polynomial_log_concave_erase_top (p : Polynomial ℕ) (hlc : ∀ k : ℕ, p.coeff k * p.coeff (k + 2) ≤ p.coeff (k + 1) * p.coeff (k + 1)) (hint : ∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < p.coeff i → 0 < p.coeff k → 0 < p.coeff j) : (∀ k : ℕ, (p.erase p.natDegree).coeff k * (p.erase p.natDegree).coeff (k + 2) ≤ (p.erase p.natDegree).coeff (k + 1) * (p.erase p.natDegree).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p.erase p.natDegree).coeff i → 0 < (p.erase p.natDegree).coeff k → 0 < (p.erase p.natDegree).coeff j)
Source
Algebraic helper for the leaf-rich graph case of OP-1399.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof establishes that erasing the leading term of a polynomial preserves log-concavity and interval support. It first proves an auxiliary lemma that coefficients at or beyond the degree vanish in the erased polynomial. For log-concavity, if the upper index k + 2 is strictly below the degree, all three involved coefficients are unchanged and log-concavity is inherited from the original polynomial; if k + 2 is at or above the degree, the (k+2)-th coefficient becomes zero, making the inequality trivial. For interval support, any index with a positive coefficient must be strictly below the degree, so all intermediate indices also lie strictly below the degree where coefficients coincide with the original polynomial.

  1. For any index k at or above the degree of p, the k-th coefficient of the polynomial with its top degree term erased is zero.

    By the definition of polynomial erasure (Polynomial.coeff_erase), the k-th coefficient is zero if k equals the degree of p, and equals the original coefficient p.coeff k otherwise. When k equals the degree, the result is immediately zero. When k is strictly greater than the degree (from p.natDegree ≤ k and k ≠ p.natDegree via lt_of_le_of_ne and Ne.symm), the coefficient vanishes by Polynomial.coeff_eq_zero_of_natDegree_lt because coefficients above the degree are zero.

    lines 1–8

    uses Polynomial.coeff_erase, Polynomial.coeff_eq_zero_of_natDegree_lt, lt_of_le_of_ne, Ne.symm

    lemma polynomial_log_concave_erase_top_coeff_ge (p : Polynomial ℕ) {k : ℕ} (h : p.natDegree ≤ k) :
        (p.erase p.natDegree).coeff k = 0 := by
      rw [Polynomial.coeff_erase]
      split_ifs with hk
      · rfl
      · apply Polynomial.coeff_eq_zero_of_natDegree_lt
        exact lt_of_le_of_ne h (Ne.symm hk)
    
  2. When k + 2 < natDegree(p), the log-concavity condition holds for the erased polynomial at index k.

    We split the conjunction to treat log-concavity first, then fix an arbitrary index k. If k + 2 < natDegree(p), then by Nat.lt_of_succ_lt we also have k + 1 < natDegree(p) and k < natDegree(p). Thus none of the indices k, k+1, k+2 equals natDegree(p), so rewriting with Polynomial.coeff_erase and if_neg (ne_of_lt ...) shows that each coefficient of the erased polynomial matches that of p. The log-concavity inequality at k then follows directly from the log-concavity hypothesis on p.

    lines 10–16

    uses Nat.lt_of_succ_lt, Polynomial.coeff_erase, if_neg, ne_of_lt

      constructor
      · intro k
        by_cases hk2 : k + 2 < p.natDegree
        · have hk1 : k + 1 < p.natDegree := Nat.lt_of_succ_lt hk2
          have hk0 : k < p.natDegree := Nat.lt_of_succ_lt hk1
          simp only [Polynomial.coeff_erase, if_neg (ne_of_lt hk2), if_neg (ne_of_lt hk1), if_neg (ne_of_lt hk0)]
          exact hlc k
  3. When k + 2 ≥ natDegree(p), the log-concavity condition holds for the erased polynomial at index k.

    If k + 2 is not strictly less than natDegree(p), then natDegree(p) ≤ k + 2 by not_lt.mp. By the auxiliary lemma polynomial_log_concave_erase_top_coeff_ge, the (k + 2)-th coefficient of the erased polynomial is zero. The left-hand side is therefore zero by mul_zero, and since coefficients in ℕ are non-negative, the inequality 0 ≤ (coeff (k + 1))² holds trivially by Nat.zero_le.

    lines 17–19

    uses not_lt.mp, polynomial_log_concave_erase_top_coeff_ge, mul_zero, Nat.zero_le

        · have hge : p.natDegree ≤ k + 2 := not_lt.mp hk2
          rw [polynomial_log_concave_erase_top_coeff_ge p hge, mul_zero]
          exact Nat.zero_le _
  4. Any index k with a strictly positive coefficient in the erased polynomial must satisfy k < natDegree(p).

    Assuming for contradiction that k is not strictly less than natDegree(p), we obtain natDegree(p) ≤ k via not_lt.mp. Then the auxiliary lemma polynomial_log_concave_erase_top_coeff_ge implies that the k-th coefficient of the erased polynomial is zero, which contradicts the hypothesis that this coefficient is strictly positive (Nat.lt_irrefl).

    lines 20–26

    uses not_lt.mp, polynomial_log_concave_erase_top_coeff_ge, Nat.lt_irrefl

      · intro i j k hij hjk hi hk
        have hk_lt : k < p.natDegree := by
          by_contra h
          have hge : p.natDegree ≤ k := not_lt.mp h
          have hz := polynomial_log_concave_erase_top_coeff_ge p hge
          rw [hz] at hk
          exact Nat.lt_irrefl 0 hk
  5. The erased polynomial has interval support: if coefficients at i and k are positive with i ≤ j ≤ k, then the coefficient at j is also positive.

    Since k < natDegree(p) and i ≤ j ≤ k, transitivity (lt_of_le_of_lt) implies that both j and i are also strictly less than natDegree(p). Consequently, none of the indices i, j, k equals natDegree(p), so their coefficients in the erased polynomial are identical to their coefficients in p by Polynomial.coeff_erase and if_neg (ne_of_lt ...). The positivity of the j-th coefficient then follows from the assumed interval support of p.

    lines 27–32

    uses lt_of_le_of_lt, Polynomial.coeff_erase, if_neg, ne_of_lt

        have hj_lt : j < p.natDegree := lt_of_le_of_lt hjk hk_lt
        have hi_lt : i < p.natDegree := lt_of_le_of_lt (hij.trans hjk) hk_lt
        rw [Polynomial.coeff_erase, if_neg (ne_of_lt hi_lt)] at hi
        rw [Polynomial.coeff_erase, if_neg (ne_of_lt hk_lt)] at hk
        rw [Polynomial.coeff_erase, if_neg (ne_of_lt hj_lt)]
        exact hint i j k hij hjk hi hk
Polynomial.coeff_erase
The i-th coefficient of p with the degree-n term erased is 0 if i = n, and p.coeff i otherwise.
Polynomial.coeff_eq_zero_of_natDegree_lt
Any coefficient of a polynomial at an index strictly greater than its degree is zero.
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Nat.lt_of_succ_lt
If n + 1 < m, then n < m.
if_neg
An if-then-else expression evaluates to its else branch when the condition is false.
ne_of_lt
A strictly smaller element is not equal to a larger one.
not_lt.mp
If a is not strictly less than b, then b ≤ a.
polynomial_log_concave_erase_top_coeff_ge
Erasing the top degree term of a polynomial leaves all coefficients at or above the original degree equal to zero.
mul_zero
Multiplication by zero on the right yields zero.
Nat.zero_le
Every natural number is greater than or equal to zero.
Nat.lt_irrefl
Strict inequality on natural numbers is irreflexive: no natural number is strictly less than itself.
lt_of_le_of_lt
If a ≤ b and b < c, then a < 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

lemma polynomial_log_concave_erase_top_coeff_ge (p : Polynomial ℕ) {k : ℕ} (h : p.natDegree ≤ k) :    (p.erase p.natDegree).coeff k = 0 := by  rw [Polynomial.coeff_erase]  split_ifs with hk  · rfl  · apply Polynomial.coeff_eq_zero_of_natDegree_lt    exact lt_of_le_of_ne h (Ne.symm hk)theorem polynomial_log_concave_erase_top (p : Polynomial ℕ) (hlc : ∀ k : ℕ, p.coeff k * p.coeff (k + 2) ≤ p.coeff (k + 1) * p.coeff (k + 1)) (hint : ∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < p.coeff i → 0 < p.coeff k → 0 < p.coeff j) : (∀ k : ℕ, (p.erase p.natDegree).coeff k * (p.erase p.natDegree).coeff (k + 2) ≤ (p.erase p.natDegree).coeff (k + 1) * (p.erase p.natDegree).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p.erase p.natDegree).coeff i → 0 < (p.erase p.natDegree).coeff k → 0 < (p.erase p.natDegree).coeff j) := by  constructor  · intro k    by_cases hk2 : k + 2 < p.natDegree    · have hk1 : k + 1 < p.natDegree := Nat.lt_of_succ_lt hk2      have hk0 : k < p.natDegree := Nat.lt_of_succ_lt hk1      simp only [Polynomial.coeff_erase, if_neg (ne_of_lt hk2), if_neg (ne_of_lt hk1), if_neg (ne_of_lt hk0)]      exact hlc k    · have hge : p.natDegree ≤ k + 2 := not_lt.mp hk2      rw [polynomial_log_concave_erase_top_coeff_ge p hge, mul_zero]      exact Nat.zero_le _  · intro i j k hij hjk hi hk    have hk_lt : k < p.natDegree := by      by_contra h      have hge : p.natDegree ≤ k := not_lt.mp h      have hz := polynomial_log_concave_erase_top_coeff_ge p hge      rw [hz] at hk      exact Nat.lt_irrefl 0 hk    have hj_lt : j < p.natDegree := lt_of_le_of_lt hjk hk_lt    have hi_lt : i < p.natDegree := lt_of_le_of_lt (hij.trans hjk) hk_lt    rw [Polynomial.coeff_erase, if_neg (ne_of_lt hi_lt)] at hi    rw [Polynomial.coeff_erase, if_neg (ne_of_lt hk_lt)] at hk    rw [Polynomial.coeff_erase, if_neg (ne_of_lt hj_lt)]    exact hint i j k hij hjk hi hk
See it in the graphDiscuss this resultChallenge it