AFTD Auto-Formalizing Theoretical Domains

prefix_reversal_six_five_three_not_top

theoremverified

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

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.

  1. The identity permutation belongs to K.

    The identity permutation leaves every index unchanged, so the parity shift is c = 0, which Lean simplifies directly.

    lines 5–8

      one_mem' := by
        refine ⟨0, ?_⟩
        intro x
        simp
  2. 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.

    lines 9–15

      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
  3. 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.

    lines 16–22

      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
  4. 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.

    line 27

      intro htop
  5. The 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`.

    lines 28–38

    uses Set.mem_insert_iff, Set.mem_singleton_iff

      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
  6. 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.

    lines 39–42

    uses Subgroup.closure_le

      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
  7. 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 = ⊤.

    lines 43–45

    uses le_antisymm, le_top

      have htopK : prefix_reversal_six_five_three_not_top_K = ⊤ := by
        rw [htop] at hle
        exact le_antisymm le_top hle
  8. 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`.

    lines 46–48

      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
  9. The transposition (0 1) belongs to K.

    Since K = ⊤, every permutation belongs to K by `Subgroup.mem_top`, in particular the transposition (0 1).

    lines 49–51

    uses Subgroup.mem_top

      have hmem : (Equiv.swap (0 : Fin 6) 1) ∈ prefix_reversal_six_five_three_not_top_K := by
        rw [htopK]
        exact Subgroup.mem_top _
  10. Contradiction.

    The fact that (0 1) ∈ K contradicts the established fact that (0 1) ∉ K, finishing the proof.

    line 52

      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 ⊤.

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

/-- 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
See it in the graphDiscuss this resultChallenge it