prefix_reversal_six_five_three_not_top
In the symmetric group Equiv.Perm (Fin 6), the subgroup generated by the three prefix reversals of lengths 3, 5, and 6 does not equal the full symmetric group.
Statement
theorem prefix_reversal_six_five_three_not_top :
Subgroup.closure {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ≠ (⊤ : Subgroup (Equiv.Perm (Fin 6)))- Source
- arXiv:2610.30892
- 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…
- Used by 1
- prefix_reversal_necessary_conditions_not_sufficientIt is not the case that for all natural numbers 2 ≤ k < m < n satisfying 2 * m > n, at least one of k, m, n even, at least one of k, m, n…
Read back from the Lean
The subgroup of the symmetric group on 6 elements (Equiv.Perm (Fin 6)) generated by the set {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} is not equal to the full symmetric group ⊤.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that the subgroup generated by prefix reversals of lengths 3, 5, and 6 in Perm (Fin 6) is proper, we consider the subgroup K of permutations that change the parity of every index by a fixed constant c in ZMod 2. We first verify that K is indeed a subgroup by showing it contains the identity and is closed under multiplication and inverses. By direct evaluation, each of the three generating prefix reversals preserves or flips all parities uniformly, so the generated subgroup is contained in K. If the generated subgroup were the entire symmetric group ⊤, K would equal ⊤; but the transposition (0 1) changes parities non-uniformly and thus cannot belong to K, giving a contradiction.
The identity permutation belongs to K.
The identity permutation leaves every index unchanged, so the parity shift is c = 0, which Lean simplifies directly.
one_mem' := by refine ⟨0, ?_⟩ intro x simp
The set K is closed under permutation composition.
If σ shifts parities by c and τ shifts parities by d, their composition (σ * τ)(x) = σ(τ(x)) shifts the parity of x by c + d. Rewriting with the definitions of σ and τ, this identity in ZMod 2 holds by ring arithmetic.
mul_mem' := by rintro σ τ ⟨c, hc⟩ ⟨d, hd⟩ refine ⟨c + d, ?_⟩ intro x show (((σ * τ) x).val : ZMod 2) = (x.val : ZMod 2) + (c + d) rw [show (σ * τ) x = σ (τ x) from rfl, hc, hd] ring
The set K is closed under inverses.
If σ shifts parities by c, applying this condition to σ⁻¹(x) gives x ≡ σ⁻¹(x) + c (mod 2). Rearranging shows σ⁻¹ shifts parities by -c, which ring arithmetic verifies.
inv_mem' := by rintro σ ⟨c, hc⟩ refine ⟨-c, ?_⟩ intro x have h : ((x.val : ZMod 2)) = ((σ⁻¹ x).val : ZMod 2) + c := by simpa using hc (σ⁻¹ x) rw [h] ring
Assume for contradiction that the subgroup generated by the three prefix reversals equals the full symmetric group ⊤.
We introduce the assumption htop for a proof by contradiction.
intro htopThe generating set of the three prefix reversals is contained in the subgroup K. automation
We check that each generator belongs to K by case analysis on the three prefix reversals. For lengths 3 and 5, the parity of every index is preserved (c = 0). For length 6, the parity of every index is flipped (c = 1). Each case is verified by finite computation via `decide`.
uses
Set.mem_insert_iff,Set.mem_singleton_iffhave hgen : {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ⊆ (prefix_reversal_six_five_three_not_top_K : Set (Equiv.Perm (Fin 6))) := by intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl | rfl · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 3 x).val : ZMod 2) = (x.val : ZMod 2) + c decide · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 5 x).val : ZMod 2) = (x.val : ZMod 2) + c decide · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 6 x).val : ZMod 2) = (x.val : ZMod 2) + c decide
The subgroup generated by the three prefix reversals is contained in K.
By `Subgroup.closure_le`, the subgroup generated by a set is contained in K if and only if the generating set is a subset of K, which was just shown.
uses
Subgroup.closure_lehave hle : Subgroup.closure {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ≤ prefix_reversal_six_five_three_not_top_K := by rw [Subgroup.closure_le] exact hgen
The subgroup K equals the full symmetric group ⊤.
Substituting the assumption htop into the inclusion gives ⊤ ≤ K. Since K ≤ ⊤ always holds by `le_top`, antisymmetry of the order (`le_antisymm`) yields K = ⊤.
uses
le_antisymm,le_tophave htopK : prefix_reversal_six_five_three_not_top_K = ⊤ := by rw [htop] at hle exact le_antisymm le_top hle
The transposition (0 1) does not belong to K. automation
The transposition (0 1) swaps 0 and 1 (changing parity by 1) while fixing 2 (changing parity by 0), so no constant c in ZMod 2 works for all indices. Lean checks this non-existence exhaustively with `decide`.
have hswap : (Equiv.swap (0 : Fin 6) 1) ∉ prefix_reversal_six_five_three_not_top_K := by change ¬ (∃ c : ZMod 2, ∀ x : Fin 6, (((Equiv.swap (0 : Fin 6) 1) x).val : ZMod 2) = (x.val : ZMod 2) + c) decide
The transposition (0 1) belongs to K.
Since K = ⊤, every permutation belongs to K by `Subgroup.mem_top`, in particular the transposition (0 1).
uses
Subgroup.mem_tophave hmem : (Equiv.swap (0 : Fin 6) 1) ∈ prefix_reversal_six_five_three_not_top_K := by rw [htopK] exact Subgroup.mem_top _
Contradiction.
The fact that (0 1) ∈ K contradicts the established fact that (0 1) ∉ K, finishing the proof.
exact hswap hmem
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton {b} if and only if it equals b.
Subgroup.closure_le- The subgroup generated by a set k is less than or equal to a subgroup K if and only if k is a subset of K.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
le_top- Every element in an order with a top element is less than or equal to ⊤.
Subgroup.mem_top- Every element of a group belongs to the top subgroup ⊤.
- The membership of each generator in K and the non-membership of the transposition (0 1) in K are verified by Lean's computational decider (`decide`), which checks the condition by exhaustive evaluation on the finite domain Fin 6.
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.
/-- The subgroup of `Equiv.Perm (Fin 6)` consisting of the permutations that change the parityof every index by one fixed constant `c` (a homomorphism to `ZMod 2`). -/def prefix_reversal_six_five_three_not_top_K : Subgroup (Equiv.Perm (Fin 6)) where carrier := {σ | ∃ c : ZMod 2, ∀ x : Fin 6, ((σ x).val : ZMod 2) = (x.val : ZMod 2) + c} one_mem' := by refine ⟨0, ?_⟩ intro x simp mul_mem' := by rintro σ τ ⟨c, hc⟩ ⟨d, hd⟩ refine ⟨c + d, ?_⟩ intro x show (((σ * τ) x).val : ZMod 2) = (x.val : ZMod 2) + (c + d) rw [show (σ * τ) x = σ (τ x) from rfl, hc, hd] ring inv_mem' := by rintro σ ⟨c, hc⟩ refine ⟨-c, ?_⟩ intro x have h : ((x.val : ZMod 2)) = ((σ⁻¹ x).val : ZMod 2) + c := by simpa using hc (σ⁻¹ x) rw [h] ring/-- The subgroup of Equiv.Perm (Fin 6) generated by prefix reversals of lengths 3, 5, 6 is a proper subgroup. -/theorem prefix_reversal_six_five_three_not_top : Subgroup.closure {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ≠ (⊤ : Subgroup (Equiv.Perm (Fin 6))) := by intro htop have hgen : {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ⊆ (prefix_reversal_six_five_three_not_top_K : Set (Equiv.Perm (Fin 6))) := by intro x hx simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hx rcases hx with rfl | rfl | rfl · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 3 x).val : ZMod 2) = (x.val : ZMod 2) + c decide · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 5 x).val : ZMod 2) = (x.val : ZMod 2) + c decide · change ∃ c : ZMod 2, ∀ x : Fin 6, ((prefixReversal 6 6 x).val : ZMod 2) = (x.val : ZMod 2) + c decide have hle : Subgroup.closure {prefixReversal 6 3, prefixReversal 6 5, prefixReversal 6 6} ≤ prefix_reversal_six_five_three_not_top_K := by rw [Subgroup.closure_le] exact hgen have htopK : prefix_reversal_six_five_three_not_top_K = ⊤ := by rw [htop] at hle exact le_antisymm le_top hle have hswap : (Equiv.swap (0 : Fin 6) 1) ∉ prefix_reversal_six_five_three_not_top_K := by change ¬ (∃ c : ZMod 2, ∀ x : Fin 6, (((Equiv.swap (0 : Fin 6) 1) x).val : ZMod 2) = (x.val : ZMod 2) + c) decide have hmem : (Equiv.swap (0 : Fin 6) 1) ∈ prefix_reversal_six_five_three_not_top_K := by rw [htopK] exact Subgroup.mem_top _ exact hswap hmem