AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_three_three_one_leap_group_eq_top

theoremverifiedformalization

The kayak paddle graph KP(3, 3, 1) (two triangles joined by an edge, 6 vertices) has full leap group S_6.

Statement

theorem kayak_paddle_three_three_one_leap_group_eq_top :
    simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) = ⊤
Formalizes
arXiv:2610.18463 (The group generated by a graph's derangements), Lemma 2.19 with n = 3 (two triangles joined by a path of length 2n − 5 = 1); a case of the odd-cycle half of list entry OP-301. Proof differs from the paper's (explicit generators instead of 2-transitivity and Jordan's theorem).
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
  • simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
  • simple_graph_kayak_paddleThe kayak paddle graph KP(k, m, l) (k, m ≥ 3, l ≥ 1) on N = k + m + l − 1 vertices: a cycle on 0, …, k−1, a cycle on k+l−1, …, k+l+m−2,…

The proof, explained

The leap group of a graph is the subgroup of the symmetric group generated by all hops (permutations sending every vertex to a neighbour). For the kayak paddle graph KP(3, 3, 1) on 6 vertices, four hops are identified and checked computationally. Multiplying these hops produces a full 6-cycle σ = (0 5 2 4 1 3) and a transposition τ = (0 5) swapping adjacent elements under σ. Because any full cycle and adjacent transposition generate the entire symmetric group S₆, the leap group is all of S₆.

  1. Adjacency in the kayak paddle graph KP(3, 3, 1) is decidable

    Unfolding the definition of KP(3, 3, 1) allows Lean's typeclass synthesis to establish that adjacency between vertices is decidable, enabling decision procedures to verify graph properties by finite case evaluation.

    lines 3–4

      letI : DecidableRel (simple_graph_kayak_paddle 3 3 1).Adj := by
        unfold simple_graph_kayak_paddle; infer_instance
  2. Define four candidate permutations H₀, H₁, H₂, H₄ on the 6 vertices

    We define permutations H₀ = (0 1 2)(3 4 5), H₁ = (0 1 2)(3 5 4), H₂ = (0 2 1)(3 4 5), and H₄ = (0 3)(1 2)(4 5) in S₆. These correspond to cycling the two triangles independently and reflecting/swapping across the bridge.

    lines 5–8

      let H0 : Equiv.Perm (Fin 6) := List.formPerm [0, 1, 2] * List.formPerm [3, 4, 5]
      let H1 : Equiv.Perm (Fin 6) := List.formPerm [0, 1, 2] * List.formPerm [3, 5, 4]
      let H2 : Equiv.Perm (Fin 6) := List.formPerm [0, 2, 1] * List.formPerm [3, 4, 5]
      let H4 : Equiv.Perm (Fin 6) := Equiv.swap 0 3 * Equiv.swap 1 2 * Equiv.swap 4 5
  3. The permutations H₀, H₁, H₂, H₄ are hops and belong to the leap group

    For each of the four permutations, decision procedures verify by exhaustive evaluation that every vertex is mapped to an adjacent vertex, satisfying the definition of a hop. Since the leap group is defined as the subgroup generated by all hops, Subgroup.subset_closure places each permutation in the leap group.

    lines 9–16

    uses Subgroup.subset_closure

      have m0 : H0 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=
        Subgroup.subset_closure (show simple_graph_is_hop _ H0 by unfold simple_graph_is_hop; decide)
      have m1 : H1 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=
        Subgroup.subset_closure (show simple_graph_is_hop _ H1 by unfold simple_graph_is_hop; decide)
      have m2 : H2 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=
        Subgroup.subset_closure (show simple_graph_is_hop _ H2 by unfold simple_graph_is_hop; decide)
      have m4 : H4 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=
        Subgroup.subset_closure (show simple_graph_is_hop _ H4 by unfold simple_graph_is_hop; decide)
  4. Explicit words in H₀, H₁, H₂, H₄ equal the 6-cycle σ = (0 5 2 4 1 3) and the transposition τ = (0 5) automation

    Direct composition of the permutations evaluated by kernel computation shows that H₄ * H₂ * H₄ * H₁ * H₄ * H₀ is the 6-cycle σ = (0 5 2 4 1 3), and H₄ * H₂ * H₄ * H₁ * H₀ * H₄ * H₁ * H₀ is the transposition τ = (0 5).

    lines 17–20

      have hσ : H4 * H2 * H4 * H1 * H4 * H0 = List.formPerm [0, 5, 2, 4, 1, 3] := by
        decide +kernel
      have hτ : H4 * H2 * H4 * H1 * H0 * H4 * H1 * H0 = Equiv.swap 0 5 := by
        decide +kernel
  5. The cycle σ and the transposition τ belong to the leap group

    Because σ and τ are products of H₀, H₁, H₂, and H₄, which were shown to be in the leap group, repeated application of subgroup closure under multiplication (mul_mem) shows that both σ and τ belong to the leap group.

    lines 21–27

    uses mul_mem

      have mσ : List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6)) ∈
          simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) := by
        rw [← hσ]
        exact mul_mem (mul_mem (mul_mem (mul_mem (mul_mem m4 m2) m4) m1) m4) m0
      have mτ : Equiv.swap (0 : Fin 6) 5 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) := by
        rw [← hτ]
        exact mul_mem (mul_mem (mul_mem (mul_mem (mul_mem (mul_mem (mul_mem m4 m2) m4) m1) m0) m4) m1) m0
  6. σ is a full-support cycle on Fin 6 with σ(0) = 5

    The list [0, 5, 2, 4, 1, 3] has no duplicates and length 6 ≥ 2, so by List.isCycle_formPerm its associated permutation is a cycle. Because the list exhausts all 6 vertices, List.support_formPerm_of_nodup shows its support is ⊤. Finally, direct evaluation shows σ(0) = 5.

    lines 28–33

    uses List.isCycle_formPerm, List.support_formPerm_of_nodup

      have hcyc : (List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6))).IsCycle :=
        List.isCycle_formPerm (by decide) (by decide)
      have hsupp : (List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6))).support = ⊤ := by
        rw [List.support_formPerm_of_nodup _ (by decide) (by decide)]
        decide
      have h05 : List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6)) 0 = 5 := by decide
  7. The leap group of KP(3, 3, 1) is the full symmetric group ⊤

    A classical theorem of symmetric groups states that a full cycle together with a transposition of two adjacent elements in the cycle generates the full symmetric group (Equiv.Perm.closure_cycle_adjacent_swap). Here σ is a full 6-cycle and τ = (0 5) = (0 σ(0)) swaps adjacent vertices, so the subgroup generated by {σ, τ} is ⊤. By Subgroup.closure_le, showing the leap group equals ⊤ reduces to showing that both generators σ and τ lie in the leap group, which holds by the previous steps.

    lines 34–38

    uses eq_top_iff, Equiv.Perm.closure_cycle_adjacent_swap, Subgroup.closure_le

      rw [eq_top_iff, ← Equiv.Perm.closure_cycle_adjacent_swap hcyc hsupp 0, h05, Subgroup.closure_le]
      intro g hg
      rcases hg with rfl | rfl
      · exact mσ
      · exact mτ
Subgroup.subset_closure
Any generating set of a group is contained in the subgroup it generates.
mul_mem
If two elements belong to a sub-algebraic structure closed under multiplication, their product also belongs to it.
List.isCycle_formPerm
The cyclic permutation formed from a list is a cycle if the list contains no duplicates and has length at least 2.
List.support_formPerm_of_nodup
The support of the permutation formed from a duplicate-free list that is not a singleton is the set of elements in the list.
eq_top_iff
An element in a bounded-above partial order equals the top element if and only if it is greater than or equal to the top element.
Equiv.Perm.closure_cycle_adjacent_swap
A full-support cycle and a transposition of two adjacent elements in the cycle generate the entire symmetric group.
Subgroup.closure_le
The subgroup generated by a set k is contained in a subgroup K if and only if k ⊆ K.

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 kayak_paddle_three_three_one_leap_group_eq_top :    simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) = ⊤ := by  letI : DecidableRel (simple_graph_kayak_paddle 3 3 1).Adj := by    unfold simple_graph_kayak_paddle; infer_instance  let H0 : Equiv.Perm (Fin 6) := List.formPerm [0, 1, 2] * List.formPerm [3, 4, 5]  let H1 : Equiv.Perm (Fin 6) := List.formPerm [0, 1, 2] * List.formPerm [3, 5, 4]  let H2 : Equiv.Perm (Fin 6) := List.formPerm [0, 2, 1] * List.formPerm [3, 4, 5]  let H4 : Equiv.Perm (Fin 6) := Equiv.swap 0 3 * Equiv.swap 1 2 * Equiv.swap 4 5  have m0 : H0 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=    Subgroup.subset_closure (show simple_graph_is_hop _ H0 by unfold simple_graph_is_hop; decide)  have m1 : H1 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=    Subgroup.subset_closure (show simple_graph_is_hop _ H1 by unfold simple_graph_is_hop; decide)  have m2 : H2 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=    Subgroup.subset_closure (show simple_graph_is_hop _ H2 by unfold simple_graph_is_hop; decide)  have m4 : H4 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) :=    Subgroup.subset_closure (show simple_graph_is_hop _ H4 by unfold simple_graph_is_hop; decide)  have hσ : H4 * H2 * H4 * H1 * H4 * H0 = List.formPerm [0, 5, 2, 4, 1, 3] := by    decide +kernel  have hτ : H4 * H2 * H4 * H1 * H0 * H4 * H1 * H0 = Equiv.swap 0 5 := by    decide +kernel  have mσ : List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6)) ∈      simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) := by    rw [← hσ]    exact mul_mem (mul_mem (mul_mem (mul_mem (mul_mem m4 m2) m4) m1) m4) m0  have mτ : Equiv.swap (0 : Fin 6) 5 ∈ simple_graph_leap_group (simple_graph_kayak_paddle 3 3 1) := by    rw [← hτ]    exact mul_mem (mul_mem (mul_mem (mul_mem (mul_mem (mul_mem (mul_mem m4 m2) m4) m1) m0) m4) m1) m0  have hcyc : (List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6))).IsCycle :=    List.isCycle_formPerm (by decide) (by decide)  have hsupp : (List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6))).support = ⊤ := by    rw [List.support_formPerm_of_nodup _ (by decide) (by decide)]    decide  have h05 : List.formPerm ([0, 5, 2, 4, 1, 3] : List (Fin 6)) 0 = 5 := by decide  rw [eq_top_iff, ← Equiv.Perm.closure_cycle_adjacent_swap hcyc hsupp 0, h05, Subgroup.closure_le]  intro g hg  rcases hg with rfl | rfl  · exact mσ  · exact mτ
See it in the graphDiscuss this resultChallenge it