kayak_paddle_three_three_one_leap_group_eq_top
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₆.
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.
letI : DecidableRel (simple_graph_kayak_paddle 3 3 1).Adj := by unfold simple_graph_kayak_paddle; infer_instance
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.
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
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.
uses
Subgroup.subset_closurehave 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)
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).
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
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.
uses
mul_memhave 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
σ 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.
uses
List.isCycle_formPerm,List.support_formPerm_of_noduphave 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
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.
uses
eq_top_iff,Equiv.Perm.closure_cycle_adjacent_swap,Subgroup.closure_lerw [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.
- Verification that the candidate permutations are hops, the algebraic simplification of permutation products into a 6-cycle and an adjacent transposition, and the support calculations are discharged by computational reflection (`decide` and `decide +kernel`).
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 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τ