polynomial_log_concave_interval_support_unimodal
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.
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.
uses
Nat.le_induction,le_rfl,le_trans,Nat.le_succ,Nat.lt_of_succ_leprivate 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
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).
uses
Nat.mul_le_mul_right,le_trans,Nat.le_of_mul_le_mul_leftprivate 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
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').
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_rflprivate 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
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.
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
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.
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
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.
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_ltlet 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.
- The proof establishes three modular lemmas: first, that piece-wise monotonicity up to and from a peak implies unimodality; second, that log-concavity advances a weak decrease to the next index when the middle term is positive; and third, that interval support ensures positivity between the first strict decrease and any future non-zero coefficient, preventing any recovery from a descent.
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.
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)