polynomial_log_concave_mul_linear_nonneg
Multiplying a natural-coefficient polynomial that is log-concave with interval support by 1+cX preserves both properties.
Statement
theorem polynomial_log_concave_mul_linear_nonneg (p : Polynomial ℕ) (c : ℕ) (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 * (1 + Polynomial.C c * Polynomial.X)).coeff k * (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 2) ≤ (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 1) * (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff i → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff k → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff j)- Source
- An algebraic helper for leaf_rich_except_zero_forcing_poly_unimodal, a partial case of OP-1399.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
To show that multiplying a log-concave polynomial p with interval support by 1 + cX preserves both properties, the proof splits into two parts. First, interval support is preserved because any zero coefficient between positive coefficients in the product would force an internal zero in p itself. Second, log-concavity is proved by expanding the coefficient inequality for the product; for the base case it reduces to log-concavity of p at 0, and for higher degrees it reduces to summing the log-concavity inequalities of p at m and m+1 with a cross-term inequality p_m * p_{m+3} ≤ p_{m+1} * p_{m+2} proved by cancelling positive intermediate coefficients.
The constant term of p(X)(1 + cX) equals the constant term of p(X).
Expanding p(X)(1 + cX) as p(X) + (p(X) * c)X, its degree-0 coefficient is p.coeff 0 + 0 = p.coeff 0.
uses
coeff_add,coeff_mul_X_zero,add_zerohave h1 : p * (1 + Polynomial.C c * Polynomial.X) = p + (p * Polynomial.C c) * Polynomial.X := by ring rw [h1, coeff_add, coeff_mul_X_zero, add_zero]
For any k, the (k+1)-th coefficient of p(X)(1 + cX) is p.coeff (k+1) + c * p.coeff k.
Expanding p(X)(1 + cX) as p(X) + c * (p(X) * X), the (k+1)-th coefficient is the sum of p.coeff (k+1) and c times the k-th coefficient of p(X).
uses
coeff_add,coeff_C_mul,coeff_mul_Xhave h1 : p * (1 + Polynomial.C c * Polynomial.X) = p + Polynomial.C c * (p * Polynomial.X) := by ring rw [h1, coeff_add, coeff_C_mul, coeff_mul_X]
Every coefficient of p(X) is bounded above by the corresponding coefficient of p(X)(1 + cX).
When n = 0, both coefficients are equal. When n = k + 1, the coefficient in the product is p.coeff (k+1) + c * p.coeff k, which is at least p.coeff (k+1).
uses
polynomial_log_concave_mul_linear_nonneg_coeff_zero,polynomial_log_concave_mul_linear_nonneg_coeff_succ,Nat.le_add_rightcases n with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero] | succ n => rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ]; exact Nat.le_add_right _ _
If the n-th coefficient of p(X)(1 + cX) is strictly positive, then either p.coeff n > 0, or n > 0 and p.coeff (n-1) > 0.
For n = 0, the coefficient is p.coeff 0, so p.coeff 0 > 0. For n = k + 1, the coefficient is p.coeff (k+1) + c * p.coeff k > 0; if p.coeff (k+1) > 0 the claim holds, and if p.coeff (k+1) = 0 then c * p.coeff k > 0, which implies p.coeff k > 0 with n > 0.
uses
polynomial_log_concave_mul_linear_nonneg_coeff_zero,polynomial_log_concave_mul_linear_nonneg_coeff_succ,Nat.lt_or_ge,zero_add,Nat.succ_pos,Nat.pos_of_mul_pos_leftcases n with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero] at h left; exact h | succ n => rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ] at h rcases Nat.lt_or_ge 0 (p.coeff (n + 1)) with hpos | hzero · left; exact hpos · right have hz : p.coeff (n + 1) = 0 := by omega rw [hz, zero_add] at h refine ⟨Nat.succ_pos n, ?_⟩ exact Nat.pos_of_mul_pos_left h
If p(X) has interval support, then p(X)(1 + cX) also has interval support.
Given indices i ≤ j ≤ k with positive coefficients at i and k in the product, if j = k the result is immediate. If j < k, then j ≤ k - 1. The positivity of the coefficients in the product implies that p has a positive coefficient at i or i-1, and at k or k-1. By the interval support of p, p.coeff j > 0, and since the j-th coefficient of the product is at least p.coeff j, it is also strictly positive.
uses
eq_or_lt_of_le,Nat.le_pred_of_lt,polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp,lt_of_lt_of_le,polynomial_log_concave_mul_linear_nonneg_coeff_gercases eq_or_lt_of_le hjk with rfl | hjk_lt · exact hk · have hjk' : j ≤ k - 1 := Nat.le_pred_of_lt hjk_lt rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c i hi with hi1 | ⟨hi_pos, hi2⟩ · rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c k hk with hk1 | ⟨hk_pos, hk2⟩ · have : 0 < p.coeff j := hint i j k hij hjk hi1 hk1 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · have : 0 < p.coeff j := hint i j (k - 1) hij hjk' hi1 hk2 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c k hk with hk1 | ⟨hk_pos, hk2⟩ · have : 0 < p.coeff j := hint (i - 1) j k (by omega) hjk hi2 hk1 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · have : 0 < p.coeff j := hint (i - 1) j (k - 1) (by omega) hjk' hi2 hk2 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j)
For a log-concave polynomial p with interval support, p.coeff m * p.coeff (m+3) ≤ p.coeff (m+1) * p.coeff (m+2) for all m.
If either p.coeff m = 0 or p.coeff (m+3) = 0, the product on the left is zero and the inequality is trivial. Otherwise, both are positive, so by interval support p.coeff (m+1) and p.coeff (m+2) are strictly positive. Multiplying the log-concavity inequalities at m and m+1 yields (p.coeff m * p.coeff (m+3)) * (p.coeff (m+1) * p.coeff (m+2)) ≤ (p.coeff (m+1) * p.coeff (m+2))^2, and cancelling the positive factor p.coeff (m+1) * p.coeff (m+2) gives the result.
uses
zero_mul,Nat.zero_le,mul_zero,Nat.pos_of_ne_zero,Nat.mul_le_mul,mul_pos,Nat.le_of_mul_le_mul_rightby_cases hm0 : p.coeff m = 0 · rw [hm0, zero_mul]; exact Nat.zero_le _ by_cases hm30 : p.coeff (m + 3) = 0 · rw [hm30, mul_zero]; exact Nat.zero_le _ have hm : 0 < p.coeff m := Nat.pos_of_ne_zero hm0 have hm3 : 0 < p.coeff (m + 3) := Nat.pos_of_ne_zero hm30 have hm1 : 0 < p.coeff (m + 1) := hint m (m + 1) (m + 3) (by omega) (by omega) hm hm3 have hm2 : 0 < p.coeff (m + 2) := hint m (m + 2) (m + 3) (by omega) (by omega) hm hm3 have h1 : p.coeff m * p.coeff (m + 2) ≤ p.coeff (m + 1) * p.coeff (m + 1) := hlc m have h2 : p.coeff (m + 1) * p.coeff (m + 3) ≤ p.coeff (m + 2) * p.coeff (m + 2) := hlc (m + 1) have h_prod : (p.coeff m * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 3)) ≤ (p.coeff (m + 1) * p.coeff (m + 1)) * (p.coeff (m + 2) * p.coeff (m + 2)) := Nat.mul_le_mul h1 h2 have h_rearr : (p.coeff m * p.coeff (m + 3)) * (p.coeff (m + 1) * p.coeff (m + 2)) ≤ (p.coeff (m + 1) * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 2)) := by calc (p.coeff m * p.coeff (m + 3)) * (p.coeff (m + 1) * p.coeff (m + 2)) = (p.coeff m * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 3)) := by ring _ ≤ (p.coeff (m + 1) * p.coeff (m + 1)) * (p.coeff (m + 2) * p.coeff (m + 2)) := h_prod _ = (p.coeff (m + 1) * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 2)) := by ring have h_pos : 0 < p.coeff (m + 1) * p.coeff (m + 2) := mul_pos hm1 hm2 exact Nat.le_of_mul_le_mul_right h_rearr h_pos
The theorem goal reduces to establishing log-concavity of p(X)(1 + cX).
The statement asserts both log-concavity and interval support for the product polynomial. The second conjunct is discharged directly by polynomial_log_concave_mul_linear_nonneg_interval_support.
uses
polynomial_log_concave_mul_linear_nonneg_interval_supportrefine ⟨?_, polynomial_log_concave_mul_linear_nonneg_interval_support p c hint⟩The log-concavity inequality holds at index 0: [X^0](p(1+cX)) * [X^2](p(1+cX)) ≤ ([X^1](p(1+cX)))^2. automation
Expanding the coefficients in terms of p, the left-hand side is p_0 p_2 + c p_0 p_1 and the right-hand side is p_1^2 + 2c p_0 p_1 + c^2 p_0^2. The inequality follows from the log-concavity of p at 0 (p_0 p_2 ≤ p_1^2) and non-negativity of the remaining terms.
uses
polynomial_log_concave_mul_linear_nonneg_coeff_zero,polynomial_log_concave_mul_linear_nonneg_coeff_succintro k cases k with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero, polynomial_log_concave_mul_linear_nonneg_coeff_succ, polynomial_log_concave_mul_linear_nonneg_coeff_succ] have hl : p.coeff 0 * (p.coeff 2 + c * p.coeff 1) = p.coeff 0 * p.coeff 2 + c * (p.coeff 0 * p.coeff 1) := by ring have hr : (p.coeff 1 + c * p.coeff 0) * (p.coeff 1 + c * p.coeff 0) = p.coeff 1 * p.coeff 1 + (c * (p.coeff 0 * p.coeff 1) + c * (p.coeff 0 * p.coeff 1) + c * c * (p.coeff 0 * p.coeff 0)) := by ring rw [hl, hr] have h_lc0 : p.coeff 0 * p.coeff 2 ≤ p.coeff 1 * p.coeff 1 := hlc 0 omega
The log-concavity inequality holds at all higher indices k = m + 1. automation
Expanding both sides into polynomials in c, the left-hand side is p_{m+1} p_{m+3} + c(p_m p_{m+3} + p_{m+1} p_{m+2}) + c^2 p_m p_{m+2} and the right-hand side is p_{m+2}^2 + 2c p_{m+1} p_{m+2} + c^2 p_{m+1}^2. The inequality follows by summing the log-concavity of p at m+1, the cross-product inequality scaled by c, and the log-concavity of p at m scaled by c^2.
uses
polynomial_log_concave_mul_linear_nonneg_coeff_succ,polynomial_log_concave_mul_linear_nonneg_coeff_cross_le,Nat.mul_le_mul_left| succ m => have h_idx2 : m + 1 + 2 = (m + 2) + 1 := by omega have h_idx1 : m + 1 + 1 = m + 2 := by omega rw [h_idx2, h_idx1] rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ, polynomial_log_concave_mul_linear_nonneg_coeff_succ (k := m + 2), polynomial_log_concave_mul_linear_nonneg_coeff_succ (k := m + 1)] have h1 : p.coeff (m + 1) * p.coeff (m + 3) ≤ p.coeff (m + 2) * p.coeff (m + 2) := hlc (m + 1) have h2 := polynomial_log_concave_mul_linear_nonneg_coeff_cross_le p hlc hint m have h3 : p.coeff m * p.coeff (m + 2) ≤ p.coeff (m + 1) * p.coeff (m + 1) := hlc m have hl : (p.coeff (m + 1) + c * p.coeff m) * (p.coeff (m + 3) + c * p.coeff (m + 2)) = p.coeff (m + 1) * p.coeff (m + 3) + c * (p.coeff m * p.coeff (m + 3)) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * c * (p.coeff m * p.coeff (m + 2)) := by ring have hr : (p.coeff (m + 2) + c * p.coeff (m + 1)) * (p.coeff (m + 2) + c * p.coeff (m + 1)) = p.coeff (m + 2) * p.coeff (m + 2) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * c * (p.coeff (m + 1) * p.coeff (m + 1)) := by ring rw [hl, hr] have h2' : c * (p.coeff m * p.coeff (m + 3)) ≤ c * (p.coeff (m + 1) * p.coeff (m + 2)) := Nat.mul_le_mul_left c h2 have h3' : c * c * (p.coeff m * p.coeff (m + 2)) ≤ c * c * (p.coeff (m + 1) * p.coeff (m + 1)) := Nat.mul_le_mul_left (c * c) h3 omega
coeff_add- The n-th coefficient of the sum of two polynomials is the sum of their n-th coefficients.
coeff_mul_X_zero- The constant term of any polynomial multiplied by X is 0.
add_zero- Adding zero to any element leaves it unchanged.
coeff_C_mul- Multiplying a polynomial by a constant scalar multiplies every coefficient by that constant.
coeff_mul_X- Multiplying a polynomial by X shifts its coefficients up by one degree.
polynomial_log_concave_mul_linear_nonneg_coeff_zero- The constant term of p(X)(1 + cX) equals the constant term of p(X).
polynomial_log_concave_mul_linear_nonneg_coeff_succ- The (k+1)-th coefficient of p(X)(1 + cX) is the (k+1)-th coefficient of p(X) plus c times the k-th coefficient of p(X).
Nat.le_add_right- Any natural number is less than or equal to itself plus another natural number.
Nat.lt_or_ge- For any two natural numbers, the first is either strictly less than or greater than or equal to the second.
zero_add- Adding zero on the left leaves an element unchanged.
Nat.succ_pos- The successor of any natural number is strictly positive.
Nat.pos_of_mul_pos_left- If a product of natural numbers is strictly positive, its right factor is strictly positive.
eq_or_lt_of_le- If a ≤ b in a partial order, then either a = b or a < b.
Nat.le_pred_of_lt- If n < m for natural numbers, then n ≤ m - 1.
polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp- If the n-th coefficient of p(X)(1 + cX) is positive, then either p's n-th coefficient is positive, or n > 0 and p's (n-1)-th coefficient is positive.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
polynomial_log_concave_mul_linear_nonneg_coeff_ge- The n-th coefficient of p(X) is at most the n-th coefficient of p(X)(1 + cX).
zero_mul- Zero multiplied by any element is zero.
Nat.zero_le- Zero is less than or equal to any natural number.
mul_zero- Any element multiplied by zero is zero.
Nat.pos_of_ne_zero- Any non-zero natural number is strictly positive.
Nat.mul_le_mul- Multiplication of natural numbers preserves non-strict inequalities.
mul_pos- The product of two strictly positive elements is strictly positive.
Nat.le_of_mul_le_mul_right- A strictly positive factor can be cancelled from the right side of an inequality between natural numbers.
polynomial_log_concave_mul_linear_nonneg_interval_support- If p(X) has interval support, then p(X)(1 + cX) also has interval support.
polynomial_log_concave_mul_linear_nonneg_coeff_cross_le- For a log-concave polynomial with interval support, the cross-product inequality p_m * p_{m+3} ≤ p_{m+1} * p_{m+2} holds.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality.
- The algebraic expansions and linear inequalities in the base case and inductive step are discharged using Lean's automated tactics ring and omega.
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 Polynomiallemma polynomial_log_concave_mul_linear_nonneg_coeff_zero (p : Polynomial ℕ) (c : ℕ) : (p * (1 + Polynomial.C c * Polynomial.X)).coeff 0 = p.coeff 0 := by have h1 : p * (1 + Polynomial.C c * Polynomial.X) = p + (p * Polynomial.C c) * Polynomial.X := by ring rw [h1, coeff_add, coeff_mul_X_zero, add_zero]lemma polynomial_log_concave_mul_linear_nonneg_coeff_succ (p : Polynomial ℕ) (c : ℕ) (k : ℕ) : (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 1) = p.coeff (k + 1) + c * p.coeff k := by have h1 : p * (1 + Polynomial.C c * Polynomial.X) = p + Polynomial.C c * (p * Polynomial.X) := by ring rw [h1, coeff_add, coeff_C_mul, coeff_mul_X]lemma polynomial_log_concave_mul_linear_nonneg_coeff_ge (p : Polynomial ℕ) (c : ℕ) (n : ℕ) : p.coeff n ≤ (p * (1 + Polynomial.C c * Polynomial.X)).coeff n := by cases n with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero] | succ n => rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ]; exact Nat.le_add_right _ _lemma polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp (p : Polynomial ℕ) (c : ℕ) (n : ℕ) (h : 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff n) : 0 < p.coeff n ∨ (n > 0 ∧ 0 < p.coeff (n - 1)) := by cases n with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero] at h left; exact h | succ n => rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ] at h rcases Nat.lt_or_ge 0 (p.coeff (n + 1)) with hpos | hzero · left; exact hpos · right have hz : p.coeff (n + 1) = 0 := by omega rw [hz, zero_add] at h refine ⟨Nat.succ_pos n, ?_⟩ exact Nat.pos_of_mul_pos_left hlemma polynomial_log_concave_mul_linear_nonneg_interval_support (p : Polynomial ℕ) (c : ℕ) (hint : ∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < p.coeff i → 0 < p.coeff k → 0 < p.coeff j) (i j k : ℕ) (hij : i ≤ j) (hjk : j ≤ k) (hi : 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff i) (hk : 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff k) : 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff j := by rcases eq_or_lt_of_le hjk with rfl | hjk_lt · exact hk · have hjk' : j ≤ k - 1 := Nat.le_pred_of_lt hjk_lt rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c i hi with hi1 | ⟨hi_pos, hi2⟩ · rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c k hk with hk1 | ⟨hk_pos, hk2⟩ · have : 0 < p.coeff j := hint i j k hij hjk hi1 hk1 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · have : 0 < p.coeff j := hint i j (k - 1) hij hjk' hi1 hk2 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · rcases polynomial_log_concave_mul_linear_nonneg_coeff_pos_imp p c k hk with hk1 | ⟨hk_pos, hk2⟩ · have : 0 < p.coeff j := hint (i - 1) j k (by omega) hjk hi2 hk1 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j) · have : 0 < p.coeff j := hint (i - 1) j (k - 1) (by omega) hjk' hi2 hk2 exact lt_of_lt_of_le this (polynomial_log_concave_mul_linear_nonneg_coeff_ge p c j)lemma polynomial_log_concave_mul_linear_nonneg_coeff_cross_le (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) (m : ℕ) : p.coeff m * p.coeff (m + 3) ≤ p.coeff (m + 1) * p.coeff (m + 2) := by by_cases hm0 : p.coeff m = 0 · rw [hm0, zero_mul]; exact Nat.zero_le _ by_cases hm30 : p.coeff (m + 3) = 0 · rw [hm30, mul_zero]; exact Nat.zero_le _ have hm : 0 < p.coeff m := Nat.pos_of_ne_zero hm0 have hm3 : 0 < p.coeff (m + 3) := Nat.pos_of_ne_zero hm30 have hm1 : 0 < p.coeff (m + 1) := hint m (m + 1) (m + 3) (by omega) (by omega) hm hm3 have hm2 : 0 < p.coeff (m + 2) := hint m (m + 2) (m + 3) (by omega) (by omega) hm hm3 have h1 : p.coeff m * p.coeff (m + 2) ≤ p.coeff (m + 1) * p.coeff (m + 1) := hlc m have h2 : p.coeff (m + 1) * p.coeff (m + 3) ≤ p.coeff (m + 2) * p.coeff (m + 2) := hlc (m + 1) have h_prod : (p.coeff m * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 3)) ≤ (p.coeff (m + 1) * p.coeff (m + 1)) * (p.coeff (m + 2) * p.coeff (m + 2)) := Nat.mul_le_mul h1 h2 have h_rearr : (p.coeff m * p.coeff (m + 3)) * (p.coeff (m + 1) * p.coeff (m + 2)) ≤ (p.coeff (m + 1) * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 2)) := by calc (p.coeff m * p.coeff (m + 3)) * (p.coeff (m + 1) * p.coeff (m + 2)) = (p.coeff m * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 3)) := by ring _ ≤ (p.coeff (m + 1) * p.coeff (m + 1)) * (p.coeff (m + 2) * p.coeff (m + 2)) := h_prod _ = (p.coeff (m + 1) * p.coeff (m + 2)) * (p.coeff (m + 1) * p.coeff (m + 2)) := by ring have h_pos : 0 < p.coeff (m + 1) * p.coeff (m + 2) := mul_pos hm1 hm2 exact Nat.le_of_mul_le_mul_right h_rearr h_postheorem polynomial_log_concave_mul_linear_nonneg (p : Polynomial ℕ) (c : ℕ) (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 * (1 + Polynomial.C c * Polynomial.X)).coeff k * (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 2) ≤ (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 1) * (p * (1 + Polynomial.C c * Polynomial.X)).coeff (k + 1)) ∧ (∀ i j k : ℕ, i ≤ j → j ≤ k → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff i → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff k → 0 < (p * (1 + Polynomial.C c * Polynomial.X)).coeff j) := by refine ⟨?_, polynomial_log_concave_mul_linear_nonneg_interval_support p c hint⟩ intro k cases k with | zero => rw [polynomial_log_concave_mul_linear_nonneg_coeff_zero, polynomial_log_concave_mul_linear_nonneg_coeff_succ, polynomial_log_concave_mul_linear_nonneg_coeff_succ] have hl : p.coeff 0 * (p.coeff 2 + c * p.coeff 1) = p.coeff 0 * p.coeff 2 + c * (p.coeff 0 * p.coeff 1) := by ring have hr : (p.coeff 1 + c * p.coeff 0) * (p.coeff 1 + c * p.coeff 0) = p.coeff 1 * p.coeff 1 + (c * (p.coeff 0 * p.coeff 1) + c * (p.coeff 0 * p.coeff 1) + c * c * (p.coeff 0 * p.coeff 0)) := by ring rw [hl, hr] have h_lc0 : p.coeff 0 * p.coeff 2 ≤ p.coeff 1 * p.coeff 1 := hlc 0 omega | succ m => have h_idx2 : m + 1 + 2 = (m + 2) + 1 := by omega have h_idx1 : m + 1 + 1 = m + 2 := by omega rw [h_idx2, h_idx1] rw [polynomial_log_concave_mul_linear_nonneg_coeff_succ, polynomial_log_concave_mul_linear_nonneg_coeff_succ (k := m + 2), polynomial_log_concave_mul_linear_nonneg_coeff_succ (k := m + 1)] have h1 : p.coeff (m + 1) * p.coeff (m + 3) ≤ p.coeff (m + 2) * p.coeff (m + 2) := hlc (m + 1) have h2 := polynomial_log_concave_mul_linear_nonneg_coeff_cross_le p hlc hint m have h3 : p.coeff m * p.coeff (m + 2) ≤ p.coeff (m + 1) * p.coeff (m + 1) := hlc m have hl : (p.coeff (m + 1) + c * p.coeff m) * (p.coeff (m + 3) + c * p.coeff (m + 2)) = p.coeff (m + 1) * p.coeff (m + 3) + c * (p.coeff m * p.coeff (m + 3)) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * c * (p.coeff m * p.coeff (m + 2)) := by ring have hr : (p.coeff (m + 2) + c * p.coeff (m + 1)) * (p.coeff (m + 2) + c * p.coeff (m + 1)) = p.coeff (m + 2) * p.coeff (m + 2) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * (p.coeff (m + 1) * p.coeff (m + 2)) + c * c * (p.coeff (m + 1) * p.coeff (m + 1)) := by ring rw [hl, hr] have h2' : c * (p.coeff m * p.coeff (m + 3)) ≤ c * (p.coeff (m + 1) * p.coeff (m + 2)) := Nat.mul_le_mul_left c h2 have h3' : c * c * (p.coeff m * p.coeff (m + 2)) ≤ c * c * (p.coeff (m + 1) * p.coeff (m + 1)) := Nat.mul_le_mul_left (c * c) h3 omega