perm_inflection_set_eq_two_of_sign_pattern
If a permutation σ has discrete second derivative that is non-negative on [2, k₁), positive at k₁, zero on (k₁, m₁), negative at m₁, non-positive on (m₁, k₂), negative at k₂, zero on (k₂, m₂), positive at m₂, and non-negative on (m₂, n-1], then perm_inflection_set σ = {(k₁, m₁), (k₂, m₂)}.
Statement
theorem perm_inflection_set_eq_two_of_sign_pattern
{n : ℕ} (σ : Equiv.Perm (Fin n)) (k₁ m₁ k₂ m₂ : ℕ)
(hk1 : 2 ≤ k₁) (h1 : k₁ < m₁) (h12 : m₁ < k₂) (h2 : k₂ < m₂) (hm2n : m₂ ≤ n - 1)
(h_pos_k1 : 0 < perm_second_derivative σ k₁)
(h_zero_1 : ∀ ℓ ∈ Finset.Ioo k₁ m₁, perm_second_derivative σ ℓ = 0)
(h_neg_m1 : perm_second_derivative σ m₁ < 0)
(h_nonpos_mid : ∀ ℓ ∈ Finset.Ioo m₁ k₂, perm_second_derivative σ ℓ ≤ 0)
(h_neg_k2 : perm_second_derivative σ k₂ < 0)
(h_zero_2 : ∀ ℓ ∈ Finset.Ioo k₂ m₂, perm_second_derivative σ ℓ = 0)
(h_pos_m2 : 0 < perm_second_derivative σ m₂)
(h_nonneg_pre : ∀ ℓ ∈ Finset.Ico 2 k₁, 0 ≤ perm_second_derivative σ ℓ)
(h_nonneg_post : ∀ ℓ ∈ Finset.Ioc m₂ (n - 1), 0 ≤ perm_second_derivative σ ℓ) :
perm_inflection_set σ = {(k₁, m₁), (k₂, m₂)}- Source
- step towards op_686_disjoint_two_element_inflection_set_admissible
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- perm_second_derivativeFor a permutation σ : Equiv.Perm (Fin n) and a natural number ℓ : ℕ, the discrete second derivative perm_second_derivative σ ℓ : ℤ is (σ…
- perm_inflection_setFor a permutation σ : Equiv.Perm (Fin n), the inflection set perm_inflection_set σ : Finset (ℕ × ℕ) is the filter of pairs (m, p) in…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The proof establishes by set extensionality that the inflection set of σ consists precisely of the pairs (k₁, m₁) and (k₂, m₂). Three preliminary helper bounds show that the discrete second derivative of σ is non-positive on (k₁, m₂) and non-negative on [2, m₁) and (k₂, n - 1], which constrains any index with a positive second derivative to [2, k₁] ∪ [m₂, n - 1] and any index with a negative second derivative to [m₁, k₂]. For the forward inclusion, an inflection pair (m, p) must have second derivatives of opposite signs; combining the index bounds with the requirement that the second derivative vanishes strictly between m and p uniquely forces either (m, p) = (k₁, m₁) or (m, p) = (k₂, m₂). The reverse inclusion then directly verifies that both candidate pairs satisfy all the conditions in the definition of an inflection pair.
The discrete second derivative of σ is non-positive everywhere on the open interval (k₁, m₂).
For any index ℓ with k₁ < ℓ < m₂, we split into cases according to where ℓ lies: if ℓ < m₁, then ℓ ∈ (k₁, m₁), where the second derivative is zero; if ℓ = m₁, it is negative (hence ≤ 0); if m₁ < ℓ < k₂, it is non-positive by assumption; if ℓ = k₂, it is negative; and if k₂ < ℓ < m₂, it belongs to (k₂, m₂), where it is zero. In all subcases, the derivative is ≤ 0.
uses
Finset.mem_Ioo,le_of_lthave h_le_zero : ∀ ℓ, k₁ < ℓ → ℓ < m₂ → perm_second_derivative σ ℓ ≤ 0 := by intro ℓ hk hmm2 by_cases hℓm1 : ℓ < m₁ · have hmem : ℓ ∈ Finset.Ioo k₁ m₁ := by simp only [Finset.mem_Ioo]; exact ⟨hk, hℓm1⟩ rw [h_zero_1 ℓ hmem] · by_cases hℓe : ℓ = m₁ · subst hℓe; exact le_of_lt h_neg_m1 · have hm1ℓ : m₁ < ℓ := by omega by_cases hℓk2 : ℓ < k₂ · exact h_nonpos_mid ℓ (by simp only [Finset.mem_Ioo]; exact ⟨hm1ℓ, hℓk2⟩) · by_cases hℓe2 : ℓ = k₂ · subst hℓe2; exact le_of_lt h_neg_k2 · have hk2ℓ : k₂ < ℓ := by omega have hmem : ℓ ∈ Finset.Ioo k₂ m₂ := by simp only [Finset.mem_Ioo]; exact ⟨hk2ℓ, hmm2⟩ rw [h_zero_2 ℓ hmem]
The discrete second derivative of σ is non-negative everywhere on the half-open interval [2, m₁).
For any index ℓ with 2 ≤ ℓ < m₁, we consider three possibilities: if ℓ < k₁, the derivative is non-negative by assumption on [2, k₁); if ℓ = k₁, the derivative is strictly positive, hence non-negative; and if k₁ < ℓ < m₁, it vanishes. Thus the derivative is ≥ 0 throughout [2, m₁).
uses
Finset.mem_Ico,le_of_lt,Finset.mem_Ioohave h_nonneg_before : ∀ ℓ, 2 ≤ ℓ → ℓ < m₁ → 0 ≤ perm_second_derivative σ ℓ := by intro ℓ h2ℓ hℓm1 by_cases hℓk1 : ℓ < k₁ · exact h_nonneg_pre ℓ (by simp only [Finset.mem_Ico]; exact ⟨h2ℓ, hℓk1⟩) · by_cases hℓe : ℓ = k₁ · subst hℓe; exact le_of_lt h_pos_k1 · have hk1ℓ : k₁ < ℓ := by omega have hmem : ℓ ∈ Finset.Ioo k₁ m₁ := by simp only [Finset.mem_Ioo]; exact ⟨hk1ℓ, hℓm1⟩ rw [h_zero_1 ℓ hmem]
The discrete second derivative of σ is non-negative everywhere on the half-open interval (k₂, n - 1].
For any index ℓ with k₂ < ℓ ≤ n - 1, we consider three possibilities: if ℓ < m₂, the derivative vanishes on (k₂, m₂); if ℓ = m₂, it is strictly positive, hence non-negative; and if m₂ < ℓ ≤ n - 1, it is non-negative by assumption on (m₂, n - 1]. Thus the derivative is ≥ 0 throughout (k₂, n - 1].
uses
Finset.mem_Ioo,le_of_lt,Finset.mem_Iochave h_nonneg_after : ∀ ℓ, k₂ < ℓ → ℓ ≤ n - 1 → 0 ≤ perm_second_derivative σ ℓ := by intro ℓ hk2ℓ hℓn by_cases hℓm2 : ℓ < m₂ · have hmem : ℓ ∈ Finset.Ioo k₂ m₂ := by simp only [Finset.mem_Ioo]; exact ⟨hk2ℓ, hℓm2⟩ rw [h_zero_2 ℓ hmem] · by_cases hℓe : ℓ = m₂ · subst hℓe; exact le_of_lt h_pos_m2 · have hm2ℓ : m₂ < ℓ := by omega exact h_nonneg_post ℓ (by simp only [Finset.mem_Ioc]; exact ⟨hm2ℓ, hℓn⟩)
Any index ℓ ∈ [2, n - 1] at which the discrete second derivative is strictly positive must satisfy ℓ ≤ k₁ or m₂ ≤ ℓ.
Suppose for contradiction that neither holds, so k₁ < ℓ < m₂. Then by the first helper lemma, the second derivative at ℓ is ≤ 0, which contradicts that it is strictly positive.
have key_pos : ∀ ℓ, 2 ≤ ℓ → ℓ ≤ n - 1 → 0 < perm_second_derivative σ ℓ → ℓ ≤ k₁ ∨ m₂ ≤ ℓ := by intro ℓ h2ℓ hℓn hpos by_contra hc push Not at hc have := h_le_zero ℓ hc.1 hc.2 linarith
Any index ℓ ∈ [2, n - 1] at which the discrete second derivative is strictly negative must satisfy m₁ ≤ ℓ ≤ k₂.
If ℓ < m₁, then because 2 ≤ ℓ, the second helper lemma gives that the second derivative is ≥ 0, contradicting negativity. Similarly, if k₂ < ℓ, then because ℓ ≤ n - 1, the third helper lemma gives that the second derivative is ≥ 0, another contradiction. Hence m₁ ≤ ℓ ≤ k₂.
have key_neg : ∀ ℓ, 2 ≤ ℓ → ℓ ≤ n - 1 → perm_second_derivative σ ℓ < 0 → m₁ ≤ ℓ ∧ ℓ ≤ k₂ := by intro ℓ h2ℓ hℓn hneg constructor · by_contra hc; push Not at hc have := h_nonneg_before ℓ h2ℓ hc linarith · by_contra hc; push Not at hc have := h_nonneg_after ℓ hc hℓn linarith
The goal reduces to proving that a pair (m, p) belongs to the inflection set if and only if (m, p) = (k₁, m₁) or (m, p) = (k₂, m₂).
We apply set extensionality to an arbitrary pair (m, p) and unfold the definition of the inflection set: (m, p) must satisfy 2 ≤ m, p ≤ n - 1, m < p, the product of their second derivatives must be negative, and the second derivative must be zero at every point strictly between m and p.
uses
Finset.mem_filter,Finset.mem_product,Finset.mem_Icc,Finset.mem_insert,Finset.mem_singleton,Prod.mk.injEqext x obtain ⟨m, p⟩ := x simp only [perm_inflection_set, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq]
If (m, p) is an inflection pair with positive derivative at m and negative derivative at p, then (m, p) = (k₁, m₁).
Since the product of the derivatives is negative, one is positive and the other negative. In this case, 0 < d(m) and d(p) < 0. Negativity at p forces m₁ ≤ p ≤ k₂ by our earlier bound on negative indices. Positivity at m forces m ≤ k₁ or m₂ ≤ m; the latter is impossible since m < p ≤ k₂ < m₂. Thus m ≤ k₁. If m < k₁, then k₁ lies strictly between m and p, so d(k₁) = 0 by the inflection condition, contradicting 0 < d(k₁); hence m = k₁. Similarly, if m₁ < p, then m₁ ∈ (m, p), forcing d(m₁) = 0, contradicting d(m₁) < 0; hence p = m₁. Therefore (m, p) = (k₁, m₁).
uses
Int.mul_neg_iff.mp,Finset.mem_Ioo,Or.inlconstructor · rintro ⟨⟨⟨hm2, hmn1⟩, hp2, hpn1⟩, hlt, hprod, hzero⟩ rcases Int.mul_neg_iff.mp hprod with ⟨hmp, hpp⟩ | ⟨hmp, hpp⟩ · -- 0 < d m, d p < 0 → (k₁, m₁) obtain ⟨hm1p, hpk2⟩ := key_neg p hp2 hpn1 hpp rcases key_pos m hm2 hmn1 hmp with hmk1 | hm2m · have hmk1' : m = k₁ := by by_contra hc have hltk : m < k₁ := by omega have := hzero k₁ (by simp only [Finset.mem_Ioo]; exact ⟨hltk, by omega⟩) linarith have hpm1' : p = m₁ := by by_contra hc have hltm : m₁ < p := by omega have := hzero m₁ (by simp only [Finset.mem_Ioo]; exact ⟨by omega, hltm⟩) linarith exact Or.inl ⟨hmk1', hpm1'⟩ · omega
If (m, p) is an inflection pair with negative derivative at m and positive derivative at p, then (m, p) = (k₂, m₂).
In the second sign case, d(m) < 0 and 0 < d(p). Negativity at m forces m₁ ≤ m ≤ k₂. Positivity at p forces p ≤ k₁ or m₂ ≤ p; the former is impossible since k₁ < m₁ ≤ m < p. Thus m₂ ≤ p. If m₂ < p, then m₂ lies strictly between m and p, forcing d(m₂) = 0 by the inflection condition, contradicting 0 < d(m₂); hence p = m₂. Similarly, if m < k₂, then k₂ ∈ (m, p), forcing d(k₂) = 0, contradicting d(k₂) < 0; hence m = k₂. Therefore (m, p) = (k₂, m₂).
uses
Finset.mem_Ioo,Or.inr· -- d m < 0, 0 < d p → (k₂, m₂) obtain ⟨hm1m, hmk2⟩ := key_neg m hm2 hmn1 hmp rcases key_pos p hp2 hpn1 hpp with hpk1 | hpm2 · omega · have hpm2' : p = m₂ := by by_contra hc have hltm : m₂ < p := by omega have := hzero m₂ (by simp only [Finset.mem_Ioo]; exact ⟨by omega, hltm⟩) linarith have hmk2' : m = k₂ := by by_contra hc have hltk : m < k₂ := by omega have := hzero k₂ (by simp only [Finset.mem_Ioo]; exact ⟨hltk, by omega⟩) linarith exact Or.inr ⟨hmk2', hpm2'⟩
Conversely, both (k₁, m₁) and (k₂, m₂) belong to the inflection set of σ.
We check each candidate pair against the definition of perm_inflection_set. For (k₁, m₁), the ordering 2 ≤ k₁ < m₁ ≤ n - 1 holds, the product of their second derivatives is negative because d(k₁) > 0 and d(m₁) < 0, and the derivative vanishes on (k₁, m₁) by hypothesis. For (k₂, m₂), the ordering 2 ≤ k₂ < m₂ ≤ n - 1 holds, the product is negative because d(k₂) < 0 and d(m₂) > 0, and the derivative vanishes on (k₂, m₂) by hypothesis.
uses
mul_neg_of_pos_of_neg,mul_neg_of_neg_of_pos· rintro (⟨hmk1, hpm1⟩ | ⟨hmk2, hpm2⟩) · rw [hmk1, hpm1] exact ⟨⟨⟨hk1, by omega⟩, by omega, by omega⟩, h1, mul_neg_of_pos_of_neg h_pos_k1 h_neg_m1, h_zero_1⟩ · rw [hmk2, hpm2] exact ⟨⟨⟨by omega, by omega⟩, by omega, hm2n⟩, h2, mul_neg_of_neg_of_pos h_neg_k2 h_pos_m2, h_zero_2⟩
Finset.mem_Ioo- An element x belongs to the open interval (a, b) if and only if a < x < b.
Finset.mem_Ico- An element x belongs to the half-open interval [a, b) if and only if a ≤ x < b.
Finset.mem_Ioc- An element x belongs to the half-open interval (a, b] if and only if a < x ≤ b.
Finset.mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
le_of_lt- In a preorder, if a < b then a ≤ b.
Finset.mem_filter- An element a belongs to {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds.
Finset.mem_product- A pair p belongs to the Cartesian product s × t if and only if p.1 ∈ s and p.2 ∈ t.
Finset.mem_insert- An element a belongs to {b} ∪ s if and only if a = b or a ∈ s.
Finset.mem_singleton- An element b belongs to the singleton set {a} if and only if b = a.
Prod.mk.injEq- Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
Int.mul_neg_iff.mp- For integers a and b, their product a * b is negative if and only if one factor is strictly positive and the other is strictly negative.
Or.inl- If a holds, then the disjunction a ∨ b holds.
Or.inr- If b holds, then the disjunction a ∨ b holds.
mul_neg_of_pos_of_neg- If a is strictly positive and b is strictly negative, then their product a * b is strictly negative.
mul_neg_of_neg_of_pos- If a is strictly negative and b is strictly positive, then their product a * b is strictly negative.
- Several ordering contradictions and index bounds are discharged by Lean's linear arithmetic solver (omega), but the mathematical contradictions (such as an index being strictly less than and greater than or equal to another) are straightforward chain inequalities.
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.
/-- If a permutation's discrete second derivative satisfies the 2-inflection sign pattern, its inflection set is exactly {(k₁, m₁), (k₂, m₂)}. -/theorem perm_inflection_set_eq_two_of_sign_pattern {n : ℕ} (σ : Equiv.Perm (Fin n)) (k₁ m₁ k₂ m₂ : ℕ) (hk1 : 2 ≤ k₁) (h1 : k₁ < m₁) (h12 : m₁ < k₂) (h2 : k₂ < m₂) (hm2n : m₂ ≤ n - 1) (h_pos_k1 : 0 < perm_second_derivative σ k₁) (h_zero_1 : ∀ ℓ ∈ Finset.Ioo k₁ m₁, perm_second_derivative σ ℓ = 0) (h_neg_m1 : perm_second_derivative σ m₁ < 0) (h_nonpos_mid : ∀ ℓ ∈ Finset.Ioo m₁ k₂, perm_second_derivative σ ℓ ≤ 0) (h_neg_k2 : perm_second_derivative σ k₂ < 0) (h_zero_2 : ∀ ℓ ∈ Finset.Ioo k₂ m₂, perm_second_derivative σ ℓ = 0) (h_pos_m2 : 0 < perm_second_derivative σ m₂) (h_nonneg_pre : ∀ ℓ ∈ Finset.Ico 2 k₁, 0 ≤ perm_second_derivative σ ℓ) (h_nonneg_post : ∀ ℓ ∈ Finset.Ioc m₂ (n - 1), 0 ≤ perm_second_derivative σ ℓ) : perm_inflection_set σ = {(k₁, m₁), (k₂, m₂)} := by have h_le_zero : ∀ ℓ, k₁ < ℓ → ℓ < m₂ → perm_second_derivative σ ℓ ≤ 0 := by intro ℓ hk hmm2 by_cases hℓm1 : ℓ < m₁ · have hmem : ℓ ∈ Finset.Ioo k₁ m₁ := by simp only [Finset.mem_Ioo]; exact ⟨hk, hℓm1⟩ rw [h_zero_1 ℓ hmem] · by_cases hℓe : ℓ = m₁ · subst hℓe; exact le_of_lt h_neg_m1 · have hm1ℓ : m₁ < ℓ := by omega by_cases hℓk2 : ℓ < k₂ · exact h_nonpos_mid ℓ (by simp only [Finset.mem_Ioo]; exact ⟨hm1ℓ, hℓk2⟩) · by_cases hℓe2 : ℓ = k₂ · subst hℓe2; exact le_of_lt h_neg_k2 · have hk2ℓ : k₂ < ℓ := by omega have hmem : ℓ ∈ Finset.Ioo k₂ m₂ := by simp only [Finset.mem_Ioo]; exact ⟨hk2ℓ, hmm2⟩ rw [h_zero_2 ℓ hmem] have h_nonneg_before : ∀ ℓ, 2 ≤ ℓ → ℓ < m₁ → 0 ≤ perm_second_derivative σ ℓ := by intro ℓ h2ℓ hℓm1 by_cases hℓk1 : ℓ < k₁ · exact h_nonneg_pre ℓ (by simp only [Finset.mem_Ico]; exact ⟨h2ℓ, hℓk1⟩) · by_cases hℓe : ℓ = k₁ · subst hℓe; exact le_of_lt h_pos_k1 · have hk1ℓ : k₁ < ℓ := by omega have hmem : ℓ ∈ Finset.Ioo k₁ m₁ := by simp only [Finset.mem_Ioo]; exact ⟨hk1ℓ, hℓm1⟩ rw [h_zero_1 ℓ hmem] have h_nonneg_after : ∀ ℓ, k₂ < ℓ → ℓ ≤ n - 1 → 0 ≤ perm_second_derivative σ ℓ := by intro ℓ hk2ℓ hℓn by_cases hℓm2 : ℓ < m₂ · have hmem : ℓ ∈ Finset.Ioo k₂ m₂ := by simp only [Finset.mem_Ioo]; exact ⟨hk2ℓ, hℓm2⟩ rw [h_zero_2 ℓ hmem] · by_cases hℓe : ℓ = m₂ · subst hℓe; exact le_of_lt h_pos_m2 · have hm2ℓ : m₂ < ℓ := by omega exact h_nonneg_post ℓ (by simp only [Finset.mem_Ioc]; exact ⟨hm2ℓ, hℓn⟩) have key_pos : ∀ ℓ, 2 ≤ ℓ → ℓ ≤ n - 1 → 0 < perm_second_derivative σ ℓ → ℓ ≤ k₁ ∨ m₂ ≤ ℓ := by intro ℓ h2ℓ hℓn hpos by_contra hc push Not at hc have := h_le_zero ℓ hc.1 hc.2 linarith have key_neg : ∀ ℓ, 2 ≤ ℓ → ℓ ≤ n - 1 → perm_second_derivative σ ℓ < 0 → m₁ ≤ ℓ ∧ ℓ ≤ k₂ := by intro ℓ h2ℓ hℓn hneg constructor · by_contra hc; push Not at hc have := h_nonneg_before ℓ h2ℓ hc linarith · by_contra hc; push Not at hc have := h_nonneg_after ℓ hc hℓn linarith ext x obtain ⟨m, p⟩ := x simp only [perm_inflection_set, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_insert, Finset.mem_singleton, Prod.mk.injEq] constructor · rintro ⟨⟨⟨hm2, hmn1⟩, hp2, hpn1⟩, hlt, hprod, hzero⟩ rcases Int.mul_neg_iff.mp hprod with ⟨hmp, hpp⟩ | ⟨hmp, hpp⟩ · -- 0 < d m, d p < 0 → (k₁, m₁) obtain ⟨hm1p, hpk2⟩ := key_neg p hp2 hpn1 hpp rcases key_pos m hm2 hmn1 hmp with hmk1 | hm2m · have hmk1' : m = k₁ := by by_contra hc have hltk : m < k₁ := by omega have := hzero k₁ (by simp only [Finset.mem_Ioo]; exact ⟨hltk, by omega⟩) linarith have hpm1' : p = m₁ := by by_contra hc have hltm : m₁ < p := by omega have := hzero m₁ (by simp only [Finset.mem_Ioo]; exact ⟨by omega, hltm⟩) linarith exact Or.inl ⟨hmk1', hpm1'⟩ · omega · -- d m < 0, 0 < d p → (k₂, m₂) obtain ⟨hm1m, hmk2⟩ := key_neg m hm2 hmn1 hmp rcases key_pos p hp2 hpn1 hpp with hpk1 | hpm2 · omega · have hpm2' : p = m₂ := by by_contra hc have hltm : m₂ < p := by omega have := hzero m₂ (by simp only [Finset.mem_Ioo]; exact ⟨by omega, hltm⟩) linarith have hmk2' : m = k₂ := by by_contra hc have hltk : m < k₂ := by omega have := hzero k₂ (by simp only [Finset.mem_Ioo]; exact ⟨hltk, by omega⟩) linarith exact Or.inr ⟨hmk2', hpm2'⟩ · rintro (⟨hmk1, hpm1⟩ | ⟨hmk2, hpm2⟩) · rw [hmk1, hpm1] exact ⟨⟨⟨hk1, by omega⟩, by omega, by omega⟩, h1, mul_neg_of_pos_of_neg h_pos_k1 h_neg_m1, h_zero_1⟩ · rw [hmk2, hpm2] exact ⟨⟨⟨by omega, by omega⟩, by omega, hm2n⟩, h2, mul_neg_of_neg_of_pos h_neg_k2 h_pos_m2, h_zero_2⟩