AFTD Auto-Formalizing Theoretical Domains

polynomial_log_concave_interval_support_unimodal

theoremverified

A natural-coefficient polynomial with log-concave coefficients and no internal zero coefficients is unimodal.

Statement

theorem polynomial_log_concave_interval_support_unimodal (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) : polynomial_is_unimodal p
Source
Helper for tree_zero_forcing_poly_unimodal, via log-concavity of its coefficient sequence.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • polynomial_is_unimodalA polynomial with natural coefficients is unimodal if its coefficient sequence is weakly increasing up to some index and weakly decreasing…

The proof, explained

The proof establishes that a polynomial with natural coefficients, log-concavity, and interval support is unimodal. If the polynomial is zero, the result holds trivially with mode 0. Otherwise, the coefficients must eventually strictly decrease at the degree, where the leading coefficient is strictly positive while the next coefficient is zero; let m be the first index of strict decrease. By minimality of m, coefficients weakly increase up to m, while log-concavity and interval support guarantee by induction that no increase can ever occur after m, establishing unimodality.

  1. A sequence that is weakly increasing up to m and weakly decreasing from m onward is unimodal with mode m.

    Providing m as the peak witness, the proof establishes monotonicity on both sides by induction. For i ≤ j ≤ m, induction on j starting from i using `Nat.le_induction` chains the single-step increases a_t ≤ a_{t+1} (valid since t < m) to yield a_i ≤ a_j. Similarly, for m ≤ i ≤ j, induction on j starting from i chains the single-step decreases a_{t+1} ≤ a_t (valid since t ≥ m) to yield a_j ≤ a_i.

    lines 1–27

    uses Nat.le_induction, le_rfl, le_trans, Nat.le_succ, Nat.lt_of_succ_le

    private lemma polynomial_log_concave_interval_support_unimodal_halves
        (a : ℕ → ℕ) (m : ℕ)
        (hlo : ∀ i, i < m → a i ≤ a (i+1))
        (hhi : ∀ j, m ≤ j → a (j+1) ≤ a j) :
        ∃ m, (∀ i j, i ≤ j → j ≤ m → a i ≤ a j) ∧ (∀ i j, m ≤ i → i ≤ j → a j ≤ a i) := by
      refine ⟨m, ?_, ?_⟩
      · intro i j hij hjm
        have key : ∀ t, i ≤ t → t ≤ m → a i ≤ a t := by
          intro t hit
          induction t, hit using Nat.le_induction with
          | base => intro _; exact le_rfl
          | succ t hit ih =>
              intro htm
              have htm' : t ≤ m := le_trans (Nat.le_succ t) htm
              have hlt : t < m := Nat.lt_of_succ_le htm
              exact le_trans (ih htm') (hlo t hlt)
        exact key j hij hjm
      · intro i j hmi hij
        have key : ∀ t, i ≤ t → a t ≤ a i := by
          intro t hit
          induction t, hit using Nat.le_induction with
          | base => exact le_rfl
          | succ t hit ih =>
              have hmt : m ≤ t := le_trans hmi hit
              exact le_trans (hhi t hmt) ih
        exact key j hij
    
  2. A log-concave sequence that weakly decreases at index k with a(k+1) > 0 also weakly decreases at k + 1.

    Multiplying the assumed decrease a(k+1) ≤ a(k) on the right by a(k+2) gives a(k+1) * a(k+2) ≤ a(k) * a(k+2). Applying log-concavity a(k) * a(k+2) ≤ a(k+1)^2 and transitivity gives a(k+1) * a(k+2) ≤ a(k+1)^2. Since a(k+1) > 0, left cancellation of multiplication on natural numbers implies a(k+2) ≤ a(k+1).

    lines 28–36

    uses Nat.mul_le_mul_right, le_trans, Nat.le_of_mul_le_mul_left

    private lemma polynomial_log_concave_interval_support_unimodal_step (a : ℕ → ℕ)
        (hlc : ∀ k, a k * a (k + 2) ≤ a (k + 1) * a (k + 1))
        (k : ℕ) (hmono : a (k+1) ≤ a k) (hpos : 0 < a (k+1)) :
        a (k+2) ≤ a (k+1) := by
      have h1 : a (k+1) * a (k+2) ≤ a k * a (k+2) := Nat.mul_le_mul_right _ hmono
      have h2 : a k * a (k+2) ≤ a (k+1) * a (k+1) := hlc k
      have h3 : a (k+1) * a (k+2) ≤ a (k+1) * a (k+1) := le_trans h1 h2
      exact Nat.le_of_mul_le_mul_left h3 hpos
    
  3. Once a log-concave sequence with interval support strictly decreases at index k, it weakly decreases at all subsequent indices k' > k.

    The proof splits on whether a(k'+1) = 0. If a(k'+1) = 0, the inequality a(k'+1) ≤ a(k') is trivial because 0 ≤ a(k'). If a(k'+1) > 0, we prove a(t+1) ≤ a(t) for all t in [k, k'] by induction on t. The base case t = k holds from the assumed strict decrease a(k+1) < a(k). In the induction step, the induction hypothesis provides a(t+1) ≤ a(t). Because k ≤ t + 1 ≤ k' + 1 and both endpoints a(k) > 0 and a(k'+1) > 0 are positive, the interval support hypothesis guarantees that a(t+1) > 0. The one-step decrease lemma then advances the weak decrease to a(t+2) ≤ a(t+1). Evaluating this induction at t = k' yields a(k'+1) ≤ a(k').

    lines 37–58

    uses polynomial_log_concave_interval_support_unimodal_step, lt_of_le_of_lt, Nat.zero_le, Nat.pos_of_ne_zero, Nat.le_induction, le_of_lt, le_trans, Nat.le_succ, le_rfl

    private lemma polynomial_log_concave_interval_support_unimodal_no_inc (a : ℕ → ℕ)
        (hlc : ∀ k, a k * a (k+2) ≤ a (k+1) * a (k+1))
        (hint : ∀ i j k, i ≤ j → j ≤ k → 0 < a i → 0 < a k → 0 < a j)
        {k k' : ℕ} (hkk' : k < k') (hdec : a (k+1) < a k) :
        a (k'+1) ≤ a k' := by
      have hstep := polynomial_log_concave_interval_support_unimodal_step a hlc
      have hkpos : 0 < a k := lt_of_le_of_lt (Nat.zero_le _) hdec
      by_cases hz : a (k'+1) = 0
      · rw [hz]; exact Nat.zero_le _
      · have hk'pos : 0 < a (k'+1) := Nat.pos_of_ne_zero hz
        have key : ∀ t, k ≤ t → t ≤ k' → a (t+1) ≤ a t := by
          intro t hkt
          induction t, hkt using Nat.le_induction with
          | base => intro _; exact le_of_lt hdec
          | succ t hkt ih =>
              intro htk'
              have htk : t ≤ k' := le_trans (Nat.le_succ t) htk'
              have ih' : a (t+1) ≤ a t := ih htk
              have hpos_t : 0 < a (t+1) := hint k (t+1) (k'+1) (by omega) (by omega) hkpos hk'pos
              exact hstep t ih' hpos_t
        exact key k' (le_of_lt hkk') le_rfl
    
  4. The zero polynomial is unimodal.

    When p = 0, we choose mode 0. Any index bounded above by 0 must be 0 by linear arithmetic, reducing the increasing condition to p.coeff 0 ≤ p.coeff 0, which is reflexive. For the decreasing condition, every coefficient of the zero polynomial is 0, so p.coeff j ≤ p.coeff i simplifies immediately to 0 ≤ 0.

    lines 59–70

    theorem polynomial_log_concave_interval_support_unimodal (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) : polynomial_is_unimodal p := by
      by_cases hp : p = 0
      · subst hp
        refine ⟨0, ?_, ?_⟩
        · rintro i j hij hj0
          have hj : j = 0 := by omega
          subst hj
          have hi : i = 0 := by omega
          subst hi
          simp
        · rintro i j hi0 hij
          simp
  5. Every non-zero polynomial has an index where its coefficients strictly decrease.

    For a non-zero polynomial p, its degree provides the witness k = natDegree(p). The coefficient p.coeff k is the leading coefficient, which is non-zero because p ≠ 0, hence strictly positive. The next coefficient p.coeff (k+1) vanishes because k + 1 > natDegree(p). Thus p.coeff (k+1) = 0 < p.coeff k, witnessing a strict decrease.

    lines 71–78

    uses Polynomial.coeff_natDegree, Polynomial.leadingCoeff_ne_zero.mpr, Polynomial.coeff_eq_zero_of_natDegree_lt, Nat.lt_succ_self, Nat.pos_of_ne_zero

      · have hex : ∃ k, p.coeff (k+1) < p.coeff k := by
          refine ⟨p.natDegree, ?_⟩
          have h1 : p.coeff p.natDegree = p.leadingCoeff := Polynomial.coeff_natDegree
          have h2 : p.leadingCoeff ≠ 0 := Polynomial.leadingCoeff_ne_zero.mpr hp
          have h3 : p.coeff (p.natDegree + 1) = 0 :=
            Polynomial.coeff_eq_zero_of_natDegree_lt (Nat.lt_succ_self _)
          rw [h3, h1]
          exact Nat.pos_of_ne_zero h2
  6. A non-zero polynomial satisfying log-concavity and interval support is unimodal, with peak at the first index of strict decrease.

    Let m be the smallest index where the coefficients strictly decrease, found by `Nat.find`. For any i < m, the minimality of m implies that the coefficients do not strictly decrease at i, so p.coeff i ≤ p.coeff (i+1). For j ≥ m, if j = m then p.coeff (m+1) ≤ p.coeff m follows from strict decrease; if j > m, the propagation lemma shows p.coeff (j+1) ≤ p.coeff j. Applying the two-halves lemma with mode m concludes that p is unimodal.

    lines 79–86

    uses Nat.find_spec, polynomial_log_concave_interval_support_unimodal_halves, le_of_not_gt, Nat.find_min, lt_or_eq_of_le, polynomial_log_concave_interval_support_unimodal_no_inc, le_of_lt

        let m := Nat.find hex
        have hm : p.coeff (m+1) < p.coeff m := Nat.find_spec hex
        exact polynomial_log_concave_interval_support_unimodal_halves p.coeff m
          (fun i hi => le_of_not_gt (Nat.find_min hex hi))
          (fun j hj => by
            rcases lt_or_eq_of_le hj with hlt | heq
            · exact polynomial_log_concave_interval_support_unimodal_no_inc p.coeff hlc hint hlt hm
            · subst heq; exact le_of_lt hm)
Nat.le_induction
Induction principle for natural numbers starting from a base index: to prove P(n) for all n ≥ m, it suffices to prove P(m) and that P(n) implies P(n+1) for n ≥ m.
le_rfl
Reflexivity of inequality: a ≤ a for any element a.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Nat.le_succ
Any natural number n is less than or equal to its successor n + 1.
Nat.lt_of_succ_le
If n + 1 ≤ m, then n < m for natural numbers.
Nat.mul_le_mul_right
Multiplying both sides of an inequality n ≤ m on the right by k preserves the inequality: n * k ≤ m * k.
Nat.le_of_mul_le_mul_left
Left cancellation for natural multiplication: if c * a ≤ c * b and 0 < c, then a ≤ b.
polynomial_log_concave_interval_support_unimodal_step
For a log-concave sequence a, if a(k+1) ≤ a(k) and 0 < a(k+1), then a(k+2) ≤ a(k+1).
lt_of_le_of_lt
Combining weak and strict inequalities: if a ≤ b and b < c, then a < c.
Nat.zero_le
Zero is less than or equal to every natural number: 0 ≤ n.
Nat.pos_of_ne_zero
A non-zero natural number is strictly positive: n ≠ 0 implies 0 < n.
le_of_lt
A strict inequality a < b implies the weak inequality a ≤ b.
Polynomial.coeff_natDegree
The coefficient of a polynomial at its degree is its leading coefficient.
Polynomial.leadingCoeff_ne_zero.mpr
A non-zero polynomial has a non-zero leading coefficient.
Polynomial.coeff_eq_zero_of_natDegree_lt
Any coefficient of a polynomial at an index strictly greater than its degree is zero.
Nat.lt_succ_self
Any natural number n is strictly less than its successor n + 1.
Nat.find_spec
The witness returned by Nat.find satisfies the given predicate.
polynomial_log_concave_interval_support_unimodal_halves
A sequence that weakly increases up to m and weakly decreases from m onward is unimodal with mode m.
le_of_not_gt
In a linear order, if b is not strictly less than a, then a ≤ b.
Nat.find_min
Any index strictly smaller than Nat.find does not satisfy the predicate.
lt_or_eq_of_le
If a ≤ b, then either a < b or a = b.
polynomial_log_concave_interval_support_unimodal_no_inc
For a log-concave sequence with interval support, a strict decrease at index k implies weak decreases at all subsequent indices k' > k.

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

private lemma polynomial_log_concave_interval_support_unimodal_halves    (a : ℕ → ℕ) (m : ℕ)    (hlo : ∀ i, i < m → a i ≤ a (i+1))    (hhi : ∀ j, m ≤ j → a (j+1) ≤ a j) :    ∃ m, (∀ i j, i ≤ j → j ≤ m → a i ≤ a j) ∧ (∀ i j, m ≤ i → i ≤ j → a j ≤ a i) := by  refine ⟨m, ?_, ?_⟩  · intro i j hij hjm    have key : ∀ t, i ≤ t → t ≤ m → a i ≤ a t := by      intro t hit      induction t, hit using Nat.le_induction with      | base => intro _; exact le_rfl      | succ t hit ih =>          intro htm          have htm' : t ≤ m := le_trans (Nat.le_succ t) htm          have hlt : t < m := Nat.lt_of_succ_le htm          exact le_trans (ih htm') (hlo t hlt)    exact key j hij hjm  · intro i j hmi hij    have key : ∀ t, i ≤ t → a t ≤ a i := by      intro t hit      induction t, hit using Nat.le_induction with      | base => exact le_rfl      | succ t hit ih =>          have hmt : m ≤ t := le_trans hmi hit          exact le_trans (hhi t hmt) ih    exact key j hijprivate lemma polynomial_log_concave_interval_support_unimodal_step (a : ℕ → ℕ)    (hlc : ∀ k, a k * a (k + 2) ≤ a (k + 1) * a (k + 1))    (k : ℕ) (hmono : a (k+1) ≤ a k) (hpos : 0 < a (k+1)) :    a (k+2) ≤ a (k+1) := by  have h1 : a (k+1) * a (k+2) ≤ a k * a (k+2) := Nat.mul_le_mul_right _ hmono  have h2 : a k * a (k+2) ≤ a (k+1) * a (k+1) := hlc k  have h3 : a (k+1) * a (k+2) ≤ a (k+1) * a (k+1) := le_trans h1 h2  exact Nat.le_of_mul_le_mul_left h3 hposprivate lemma polynomial_log_concave_interval_support_unimodal_no_inc (a : ℕ → ℕ)    (hlc : ∀ k, a k * a (k+2) ≤ a (k+1) * a (k+1))    (hint : ∀ i j k, i ≤ j → j ≤ k → 0 < a i → 0 < a k → 0 < a j)    {k k' : ℕ} (hkk' : k < k') (hdec : a (k+1) < a k) :    a (k'+1) ≤ a k' := by  have hstep := polynomial_log_concave_interval_support_unimodal_step a hlc  have hkpos : 0 < a k := lt_of_le_of_lt (Nat.zero_le _) hdec  by_cases hz : a (k'+1) = 0  · rw [hz]; exact Nat.zero_le _  · have hk'pos : 0 < a (k'+1) := Nat.pos_of_ne_zero hz    have key : ∀ t, k ≤ t → t ≤ k' → a (t+1) ≤ a t := by      intro t hkt      induction t, hkt using Nat.le_induction with      | base => intro _; exact le_of_lt hdec      | succ t hkt ih =>          intro htk'          have htk : t ≤ k' := le_trans (Nat.le_succ t) htk'          have ih' : a (t+1) ≤ a t := ih htk          have hpos_t : 0 < a (t+1) := hint k (t+1) (k'+1) (by omega) (by omega) hkpos hk'pos          exact hstep t ih' hpos_t    exact key k' (le_of_lt hkk') le_rfltheorem polynomial_log_concave_interval_support_unimodal (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) : polynomial_is_unimodal p := by  by_cases hp : p = 0  · subst hp    refine ⟨0, ?_, ?_⟩    · rintro i j hij hj0      have hj : j = 0 := by omega      subst hj      have hi : i = 0 := by omega      subst hi      simp    · rintro i j hi0 hij      simp  · have hex : ∃ k, p.coeff (k+1) < p.coeff k := by      refine ⟨p.natDegree, ?_⟩      have h1 : p.coeff p.natDegree = p.leadingCoeff := Polynomial.coeff_natDegree      have h2 : p.leadingCoeff ≠ 0 := Polynomial.leadingCoeff_ne_zero.mpr hp      have h3 : p.coeff (p.natDegree + 1) = 0 :=        Polynomial.coeff_eq_zero_of_natDegree_lt (Nat.lt_succ_self _)      rw [h3, h1]      exact Nat.pos_of_ne_zero h2    let m := Nat.find hex    have hm : p.coeff (m+1) < p.coeff m := Nat.find_spec hex    exact polynomial_log_concave_interval_support_unimodal_halves p.coeff m      (fun i hi => le_of_not_gt (Nat.find_min hex hi))      (fun j hj => by        rcases lt_or_eq_of_le hj with hlt | heq        · exact polynomial_log_concave_interval_support_unimodal_no_inc p.coeff hlc hint hlt hm        · subst heq; exact le_of_lt hm)
See it in the graphDiscuss this resultChallenge it