polynomial_log_concave_erase_top
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.
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.
uses
Polynomial.coeff_erase,Polynomial.coeff_eq_zero_of_natDegree_lt,lt_of_le_of_ne,Ne.symmlemma 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)
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.
uses
Nat.lt_of_succ_lt,Polynomial.coeff_erase,if_neg,ne_of_ltconstructor · 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
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.
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 _
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).
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
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.
uses
lt_of_le_of_lt,Polynomial.coeff_erase,if_neg,ne_of_lthave 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
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.
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