AFTD Auto-Formalizing Theoretical Domains

polynomial_log_concave_mul_linear_nonneg

theoremverified

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.

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

    lines 5–6

    uses coeff_add, coeff_mul_X_zero, add_zero

      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]
  2. 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).

    lines 10–11

    uses coeff_add, coeff_C_mul, coeff_mul_X

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

    lines 15–17

    uses polynomial_log_concave_mul_linear_nonneg_coeff_zero, polynomial_log_concave_mul_linear_nonneg_coeff_succ, Nat.le_add_right

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

    lines 22–34

    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_left

      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 h
  5. 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.

    lines 42–55

    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_ge

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

    lines 62–83

    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_right

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

    line 86

    uses polynomial_log_concave_mul_linear_nonneg_interval_support

      refine ⟨?_, polynomial_log_concave_mul_linear_nonneg_interval_support p c hint⟩
  8. 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.

    lines 87–98

    uses polynomial_log_concave_mul_linear_nonneg_coeff_zero, polynomial_log_concave_mul_linear_nonneg_coeff_succ

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

    lines 99–120

    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.

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