AFTD Auto-Formalizing Theoretical Domains

prefix_reversal_group_le_iff

theoremverified

The generated subgroup is contained in H exactly when all three specified prefix reversals lie in H.

Statement

theorem prefix_reversal_group_le_iff (n k m : ℕ) (H : Subgroup (Equiv.Perm (Fin n))) :
    prefix_reversal_group n k m ≤ H ↔
      prefixReversal n k ∈ H ∧ prefixReversal n m ∈ H ∧ prefixReversal n n ∈ H
Source
Helper for the interior-triple generation question in https://arxiv.org/html/2610.30892v1; classified boundary cases and the primitive-transposition criterion are in https://arxiv.org/html/2511.16959v1, Lemma 1 and Main Theorem.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • prefix_reversal_groupThe subgroup of the symmetric group on n positions generated by prefix reversals of lengths k, m and n.
  • 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

By definition, prefix_reversal_group n k m is the subgroup generated by the three permutations prefixReversal n k, prefixReversal n m, and prefixReversal n n. A subgroup closure is contained in a subgroup H if and only if its generating set is a subset of H. Decomposing the subset condition for this three-element set immediately reduces containment to the conjunction of the three individual membership assertions.

  1. The subgroup generated by the three prefix reversals is contained in H if and only if the three-element set of generators is a subset of H.

    Expanding the definition of prefix_reversal_group writes it as the subgroup closure of the three-element set {prefixReversal n k, prefixReversal n m, prefixReversal n n}. Applying Subgroup.closure_le reduces subgroup containment to showing that this generating set is a subset of the carrier of H.

    line 4

    uses prefix_reversal_group, Subgroup.closure_le

      rw [prefix_reversal_group, Subgroup.closure_le]
  2. The generating set is contained in H if and only if all three prefix reversals individually belong to H.

    The subset condition for the explicit three-element set simplifies via Set.insert_subset_iff and Set.singleton_subset_iff to the conjunction that each generator belongs to the carrier of H. Since membership in the subgroup H is definitionally membership in its carrier set, both sides of the equivalence are definitionally identical, and reflexivity (rfl) closes the goal.

    lines 5–6

    uses Set.insert_subset_iff, Set.singleton_subset_iff

      simp only [Set.insert_subset_iff, Set.singleton_subset_iff]
      rfl
prefix_reversal_group
the subgroup of permutations of Fin n generated by the three prefix reversals with parameters k, m, and n
Subgroup.closure_le
the subgroup closure of a set s is contained in a subgroup K if and only if s is a subset of the carrier of K
Set.insert_subset_iff
the set insert a s is a subset of t if and only if a ∈ t and s ⊆ t
Set.singleton_subset_iff
the singleton set {a} is a subset of s if and only if a ∈ s

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

theorem prefix_reversal_group_le_iff (n k m : ℕ) (H : Subgroup (Equiv.Perm (Fin n))) :    prefix_reversal_group n k m ≤ H ↔      prefixReversal n k ∈ H ∧ prefixReversal n m ∈ H ∧ prefixReversal n n ∈ H := by  rw [prefix_reversal_group, Subgroup.closure_le]  simp only [Set.insert_subset_iff, Set.singleton_subset_iff]  rfl
See it in the graphDiscuss this resultChallenge it