not_prefix_reversal_sum_bound_necessary
The statement prefix_reversal_sum_bound_necessary is false: The statement claims that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n. However, for (k, m, n) = (2, 3, 5), the prefix reversals of lengths 2, 3, 5 generate the entire symmetric group S_5 (order 120), yet m + k = 5 < 6 = n + 1. Further counterexamples include (k, m, n) = (2, 4, 7), (3, 4, 7), (2, 5, 7), (2, 7, 9), (4, 6, 11), (5, 6, 11), (4, 7, 11), (3, 8, 11), (2, 9, 11).
Statement
theorem not_prefix_reversal_sum_bound_necessary : ¬ (∀ (k m n : ℕ)
(hk : 2 ≤ k) (hkm : k < m) (hmn : m < n)
(hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤), m + k ≥ n + 1)- Related work
- refutes `prefix_reversal_sum_bound_necessary`
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- prefixReversalFor integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements…
The proof, explained
The theorem refutes the claim that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n by producing the counterexample (k, m, n) = (2, 3, 5). It shows that the prefix reversals of lengths 2, 3, and 5 generate the entire symmetric group S_5 by explicitly expressing every adjacent transposition as a word in the three generators. Since S_5 is generated yet 3 + 2 = 5 < 6 = 5 + 1, the asserted necessity condition fails.
Assume for contradiction that m + k ≥ n + 1 is a necessary condition for prefix reversals of lengths k, m, n to generate S_n.
We introduce the assumed universal statement h, which asserts that whenever 2 ≤ k < m < n and the prefix reversals of lengths k, m, and n generate S_n, the sum inequality m + k ≥ n + 1 must hold.
intro hThe prefix reversals of lengths 2, 3, and 5 belong to the subgroup they generate in S_5.
To disprove the claim, we construct the counterexample (k, m, n) = (2, 3, 5). We begin proving that these three prefix reversals generate the entire symmetric group S_5 (goal `g5_eq_top`). As immediate premises, each of the three generating reversals belongs to their subgroup closure by `Subgroup.subset_closure`.
uses
Subgroup.subset_closurehave g5_eq_top : Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} = (⊤ : Subgroup (Equiv.Perm (Fin 5))) := by open Equiv Perm in have ha : prefixReversal 5 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp) have hb : prefixReversal 5 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp) have hc : prefixReversal 5 5 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp)
All four adjacent transpositions (0 1), (1 2), (2 3), and (3 4) belong to the subgroup generated by the prefix reversals of lengths 2, 3, and 5.
Each adjacent transposition is explicitly decomposed into products of the generators: (0 1) is the reversal of length 2; (1 2) is the conjugate (2)(3)(2); (2 3) is the conjugate (5)((2)(3)(2))(5); and (3 4) is (5)(2)(5). Each identity between permutations of 5 elements is verified by finite evaluation (`decide`), and subgroup closure under multiplication (`Subgroup.mul_mem`) establishes that each transposition belongs to the subgroup.
uses
Subgroup.mul_memhave ht0 : swap 0 1 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 2 = swap 0 1 := by decide rwa [← this] have ht1 : swap 1 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2 = swap 1 2 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha have ht2 : swap 2 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 5 * (prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2) * prefixReversal 5 5 = swap 2 3 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc (Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha)) hc have ht3 : swap 3 4 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 5 * prefixReversal 5 2 * prefixReversal 5 5 = swap 3 4 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc ha) hc
Every adjacent transposition (i i+1) for i < 4 belongs to the submonoid underlying the generated subgroup.
Given an arbitrary adjacent transposition (i i+1) with i < 4, case analysis on i ∈ {0, 1, 2, 3} (`interval_cases`) matches each case with one of the four adjacent transpositions verified in the previous step.
have hrange : Set.range (fun i : Fin 4 => swap i.castSucc i.succ) ⊆ ((Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid : Set (Perm (Fin 5))) := by intro x hx rcases hx with ⟨⟨i, hi⟩, rfl⟩ interval_cases i · exact ht0 · exact ht1 · exact ht2 · exact ht3
The subgroup generated by prefix reversals of lengths 2, 3, and 5 is the full symmetric group S_5.
Because adjacent transpositions generate the full symmetric group as a monoid (`mclosure_swap_castSucc_succ`), the fact that every adjacent transposition is contained in the underlying submonoid implies that the submonoid is top (`Submonoid.closure_le`, `eq_top_iff`). Passing between subgroup and submonoid membership (`Subgroup.mem_toSubmonoid`) and applying extensionality (`ext`) yields that the generated subgroup is all of S_5.
uses
eq_top_iff,mclosure_swap_castSucc_succ,Submonoid.closure_le,Subgroup.mem_toSubmonoidhave htopM : (Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid = ⊤ := by rw [eq_top_iff, ← mclosure_swap_castSucc_succ 4, Submonoid.closure_le] exact hrange ext x simp [← Subgroup.mem_toSubmonoid, htopM]
Contradiction: the sum bound fails for (k, m, n) = (2, 3, 5).
Instantiating the assumption h with k = 2, m = 3, and n = 5 alongside the fact that they generate S_5 produces the inequality 3 + 2 ≥ 5 + 1 (i.e. 5 ≥ 6). Linear integer arithmetic (`omega`) deduces False, completing the proof.
have hfalse := h 2 3 5 (by omega) (by omega) (by omega) g5_eq_top omega
Subgroup.subset_closure- Any subset of a group is contained in the subgroup generated by that subset.
Subgroup.mul_mem- If two elements belong to a subgroup, their product also belongs to the subgroup.
eq_top_iff- An element in a preordered type with a top element ⊤ equals ⊤ if and only if it is greater than or equal to ⊤.
mclosure_swap_castSucc_succ- The submonoid generated by all adjacent transpositions on n + 1 elements is the entire symmetric group.
Submonoid.closure_le- The submonoid generated by a set s is contained in a submonoid S if and only if s is a subset of S.
Subgroup.mem_toSubmonoid- An element belongs to a subgroup if and only if it belongs to its underlying submonoid.
- Permutation identities expressing adjacent transpositions in terms of prefix reversals (lines 14, 17, 21, 25) are verified by Lean's `decide` tactic via exhaustive computation on the finite domain `Fin 5`.
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.
theorem not_prefix_reversal_sum_bound_necessary : ¬ (∀ (k m n : ℕ) (hk : 2 ≤ k) (hkm : k < m) (hmn : m < n) (hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤), m + k ≥ n + 1) := by intro h have g5_eq_top : Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} = (⊤ : Subgroup (Equiv.Perm (Fin 5))) := by open Equiv Perm in have ha : prefixReversal 5 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp) have hb : prefixReversal 5 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp) have hc : prefixReversal 5 5 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := Subgroup.subset_closure (by simp) have ht0 : swap 0 1 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 2 = swap 0 1 := by decide rwa [← this] have ht1 : swap 1 2 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2 = swap 1 2 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha have ht2 : swap 2 3 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 5 * (prefixReversal 5 2 * prefixReversal 5 3 * prefixReversal 5 2) * prefixReversal 5 5 = swap 2 3 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc (Subgroup.mul_mem _ (Subgroup.mul_mem _ ha hb) ha)) hc have ht3 : swap 3 4 ∈ Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5} := by have : prefixReversal 5 5 * prefixReversal 5 2 * prefixReversal 5 5 = swap 3 4 := by decide rw [← this] exact Subgroup.mul_mem _ (Subgroup.mul_mem _ hc ha) hc have hrange : Set.range (fun i : Fin 4 => swap i.castSucc i.succ) ⊆ ((Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid : Set (Perm (Fin 5))) := by intro x hx rcases hx with ⟨⟨i, hi⟩, rfl⟩ interval_cases i · exact ht0 · exact ht1 · exact ht2 · exact ht3 have htopM : (Subgroup.closure {prefixReversal 5 2, prefixReversal 5 3, prefixReversal 5 5}).toSubmonoid = ⊤ := by rw [eq_top_iff, ← mclosure_swap_castSucc_succ 4, Submonoid.closure_le] exact hrange ext x simp [← Subgroup.mem_toSubmonoid, htopM] have hfalse := h 2 3 5 (by omega) (by omega) (by omega) g5_eq_top omega