kayak_paddle_leap_group_not_eq_top_or_alternating
No: KP(3, 4, 1) (a triangle and a 4-cycle joined by an edge, 7 vertices) admits a hop, but its leap group is neither S_7 nor A_7. Every hop of KP(3,4,1) maps the triangle {0,1,2} to itself, so the leap group fixes that set (it has order 24).
Statement
theorem kayak_paddle_leap_group_not_eq_top_or_alternating :
¬ ∀ k m l : ℕ, 3 ≤ k → 3 ≤ m → 1 ≤ l →
(∃ h, simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) →
simple_graph_leap_group (simple_graph_kayak_paddle k m l) = ⊤ ∨
simple_graph_leap_group (simple_graph_kayak_paddle k m l) = alternatingGroup _- Related work
- arXiv:2610.18463 (The group generated by a graph's derangements), Question 2.20 (and the sentence before it: 'We believe that many, if not all, kayak paddle graphs have leap group equal to either S_n or A_n'); list entry OP-301. Computation (exhaustive hop enumeration and Schreier-Sims) shows the leap group of KP(k,m,l) is S_N or A_N exactly when k and m are both odd, for all N ≤ 13; with an even cycle it is small (KP(3,4,1): order 24).
- Verified
- 20 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
We refute the universal claim by showing that the kayak paddle graph KP(3, 4, 1) on 7 vertices is a counterexample. Any hop of KP(3, 4, 1) preserves the triangle {0, 1, 2}, so all hops—and therefore the entire leap group—are contained in the subgroup S of S_7 consisting of permutations that fix {0, 1, 2} setwise. Although KP(3, 4, 1) admits a hop, its leap group cannot be S_7 or A_7 because both groups contain permutations (such as (0 3) or (0 3)(3 4)) that move 0 outside the triangle.
Assume for contradiction that every kayak paddle graph with a hop has leap group equal to the full symmetric group or the alternating group, and establish decidability of adjacency on KP(3, 4, 1).
We argue by contradiction: let H be the assumed universal statement that every kayak paddle graph KP(k, m, l) with k, m ≥ 3 and l ≥ 1 that admits a hop has leap group equal to S_n or A_n. We refute this using the graph KP(3, 4, 1) on 7 vertices, whose adjacency relation is decidable.
intro H letI : DecidableRel (simple_graph_kayak_paddle 3 4 1).Adj := by unfold simple_graph_kayak_paddle; infer_instance
The set S of permutations of {0, ..., 6} that preserve the triangle {0, 1, 2} forms a subgroup of S_7.
We define S as the set of permutations g satisfying g(v) < 3 ↔ v < 3. We check the subgroup axioms: closure under multiplication follows from Set.mem_setOf_eq and Equiv.Perm.mul_apply; the identity permutation trivially preserves the condition; and closure under inverses follows from Equiv.Perm.inv_def and Equiv.apply_symm_apply.
uses
Set.mem_setOf_eq,Equiv.Perm.mul_apply,Equiv.Perm.inv_def,Equiv.apply_symm_applylet S : Subgroup (Equiv.Perm (Fin 7)) := { carrier := {g | ∀ v, (g v).val < 3 ↔ v.val < 3} mul_mem' := fun {a b} ha hb v => by simp only [Set.mem_setOf_eq, Equiv.Perm.mul_apply] at * rw [ha, hb] one_mem' := fun v => by simp inv_mem' := fun {a} ha v => by simp only [Set.mem_setOf_eq] at * have := ha (a⁻¹ v) simp only [Equiv.Perm.inv_def, Equiv.apply_symm_apply] at this ⊢ exact this.symm }
In KP(3, 4, 1), neighbors of 1 and 2 lie in {0, 1, 2}, neighbors of 0, 4, and 6 cannot all lie outside {0, 1, 2}, and {0, 1, 2} contains only 0, 1, and 2. automation
Four finite properties of KP(3, 4, 1) are verified by exhaustive case checking (decide): any neighbor of 1 or 2 is in {0, 1, 2}; if a_0, a_4, a_6 are distinct neighbors of 0, 4, 6 respectively, then a_0 < 3; and any three distinct elements of {0, 1, 2} exhaust the entire set.
have k0 : ∀ a0 a4 a6 : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 0 a0 → (simple_graph_kayak_paddle 3 4 1).Adj 4 a4 → (simple_graph_kayak_paddle 3 4 1).Adj 6 a6 → a4 ≠ a6 → a0 ≠ a4 → a0 ≠ a6 → a0.val < 3 := by decide have k1 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 1 a → a.val < 3 := by decide have k2 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 2 a → a.val < 3 := by decide have k3 : ∀ a0 a1 a2 b : Fin 7, a0.val < 3 → a1.val < 3 → a2.val < 3 → a0 ≠ a1 → a0 ≠ a2 → a1 ≠ a2 → b.val < 3 → b = a0 ∨ b = a1 ∨ b = a2 := by decide
Every hop of KP(3, 4, 1) preserves the triangle {0, 1, 2}, hence belongs to S.
Let h be a hop of KP(3, 4, 1), so v ~ h(v) for all v. By injectivity of h, h(0), h(4), and h(6) are pairwise distinct, so applying k0 gives h(0) < 3; applying k1 and k2 gives h(1) < 3 and h(2) < 3. To see that h preserves {0, 1, 2}, note that if h(v) < 3, then h(v) must be one of h(0), h(1), h(2) by k3, so v ∈ {0, 1, 2} by injectivity; conversely, if v < 3 then v ∈ {0, 1, 2}, and in each case h(v) < 3 was already established.
have hop_pres : ∀ h : Equiv.Perm (Fin 7), simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h → h ∈ S := by intro h hh v have inj := h.injective have l0 := k0 (h 0) (h 4) (h 6) (hh 0) (hh 4) (hh 6) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) have l1 := k1 (h 1) (hh 1) have l2 := k2 (h 2) (hh 2) constructor · intro hv rcases k3 (h 0) (h 1) (h 2) (h v) l0 l1 l2 (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) hv with e | e | e <;> rw [inj e] <;> decide · intro hv fin_cases v · exact l0 · exact l1 · exact l2 all_goals exact absurd hv (by decide)
The leap group of KP(3, 4, 1) is contained in S.
The leap group is defined as the subgroup generated by all hops. Since every hop belongs to S, Subgroup.closure_le ensures that the generated subgroup is also contained in S.
uses
Subgroup.closure_lehave hS : simple_graph_leap_group (simple_graph_kayak_paddle 3 4 1) ≤ S := (Subgroup.closure_le S).mpr fun h hh => hop_pres h hh
The graph KP(3, 4, 1) admits at least one hop.
An explicit hop is provided by the permutation (0 1)(1 2)(3 4)(4 5)(5 6), and verifying that v ~ h(v) for all 7 vertices is a finite check.
have hex : ∃ h, simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h := ⟨Equiv.swap (0 : Fin 7) 1 * Equiv.swap 1 2 * Equiv.swap 3 4 * Equiv.swap 4 5 * Equiv.swap 5 6, by unfold simple_graph_is_hop; decide⟩
Instantiating the universal assumption H shows that the leap group cannot be S_7.
Applying H to k=3, m=4, l=1 with the witness hop leaves two cases: the leap group is either ⊤ = S_7 or A_7. If it were S_7, the transposition (0 3) would belong to S (by Subgroup.mem_top and the inclusion in S), but (0 3) maps 0 to 3, contradicting the condition 0 < 3 ↔ (0 3)(0) < 3.
uses
le_rfl,Subgroup.mem_toprcases H 3 4 1 (by norm_num) (by norm_num) le_rfl hex with htop | halt · have hmem : Equiv.swap (0 : Fin 7) 3 ∈ S := hS (htop ▸ Subgroup.mem_top _) exact absurd (hmem 0) (by decide)
The leap group cannot be the alternating group A_7 either, completing the contradiction.
If the leap group were A_7, the permutation (0 3)(3 4) would belong to A_7 because its sign is (-1) * (-1) = 1 (by Equiv.Perm.sign_mul, Equiv.Perm.sign_swap, and Equiv.Perm.mem_alternatingGroup). Hence it would belong to S, but evaluating it at 0 yields (0 3)(0) = 3 ≮ 3, again contradicting membership in S. Both cases lead to a contradiction, refuting H.
uses
Equiv.Perm.mem_alternatingGroup,Equiv.Perm.sign_mul,Equiv.Perm.sign_swap· have halt' : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ alternatingGroup (Fin 7) := by rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap (by decide), Equiv.Perm.sign_swap (by decide)] rfl have hmem : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ S := hS (halt ▸ halt') exact absurd (hmem 0) (by decide)
Set.mem_setOf_eq- An element x belongs to the set defined by a predicate p if and only if p(x) holds.
Equiv.Perm.mul_apply- The product of two permutations acts as their composition: (f * g)(x) = f(g(x)).
Equiv.Perm.inv_def- The group inverse of a permutation is its inverse bijection.
Equiv.apply_symm_apply- Applying a bijection to the image of an element under its inverse yields the element: e(e.symm(x)) = x.
Subgroup.closure_le- The subgroup generated by a set k is contained in a subgroup K if and only if k ⊆ K.
le_rfl- The inequality relation ≤ is reflexive: a ≤ a.
Subgroup.mem_top- Every element of a group belongs to the top subgroup ⊤.
Equiv.Perm.mem_alternatingGroup- A permutation belongs to the alternating group if and only if its sign is 1.
Equiv.Perm.sign_mul- The sign of a product of permutations is the product of their signs.
Equiv.Perm.sign_swap- A transposition of two distinct elements has sign -1.
- Finite combinatorial properties and the existence of a hop on KP(3, 4, 1) are checked by the `decide` tactic, which exhaustively verifies all cases on the 7-element vertex set.
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_leap_group_not_eq_top_or_alternating : ¬ ∀ k m l : ℕ, 3 ≤ k → 3 ≤ m → 1 ≤ l → (∃ h, simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) → simple_graph_leap_group (simple_graph_kayak_paddle k m l) = ⊤ ∨ simple_graph_leap_group (simple_graph_kayak_paddle k m l) = alternatingGroup _ := by intro H letI : DecidableRel (simple_graph_kayak_paddle 3 4 1).Adj := by unfold simple_graph_kayak_paddle; infer_instance let S : Subgroup (Equiv.Perm (Fin 7)) := { carrier := {g | ∀ v, (g v).val < 3 ↔ v.val < 3} mul_mem' := fun {a b} ha hb v => by simp only [Set.mem_setOf_eq, Equiv.Perm.mul_apply] at * rw [ha, hb] one_mem' := fun v => by simp inv_mem' := fun {a} ha v => by simp only [Set.mem_setOf_eq] at * have := ha (a⁻¹ v) simp only [Equiv.Perm.inv_def, Equiv.apply_symm_apply] at this ⊢ exact this.symm } have k0 : ∀ a0 a4 a6 : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 0 a0 → (simple_graph_kayak_paddle 3 4 1).Adj 4 a4 → (simple_graph_kayak_paddle 3 4 1).Adj 6 a6 → a4 ≠ a6 → a0 ≠ a4 → a0 ≠ a6 → a0.val < 3 := by decide have k1 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 1 a → a.val < 3 := by decide have k2 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 2 a → a.val < 3 := by decide have k3 : ∀ a0 a1 a2 b : Fin 7, a0.val < 3 → a1.val < 3 → a2.val < 3 → a0 ≠ a1 → a0 ≠ a2 → a1 ≠ a2 → b.val < 3 → b = a0 ∨ b = a1 ∨ b = a2 := by decide have hop_pres : ∀ h : Equiv.Perm (Fin 7), simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h → h ∈ S := by intro h hh v have inj := h.injective have l0 := k0 (h 0) (h 4) (h 6) (hh 0) (hh 4) (hh 6) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) have l1 := k1 (h 1) (hh 1) have l2 := k2 (h 2) (hh 2) constructor · intro hv rcases k3 (h 0) (h 1) (h 2) (h v) l0 l1 l2 (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) hv with e | e | e <;> rw [inj e] <;> decide · intro hv fin_cases v · exact l0 · exact l1 · exact l2 all_goals exact absurd hv (by decide) have hS : simple_graph_leap_group (simple_graph_kayak_paddle 3 4 1) ≤ S := (Subgroup.closure_le S).mpr fun h hh => hop_pres h hh have hex : ∃ h, simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h := ⟨Equiv.swap (0 : Fin 7) 1 * Equiv.swap 1 2 * Equiv.swap 3 4 * Equiv.swap 4 5 * Equiv.swap 5 6, by unfold simple_graph_is_hop; decide⟩ rcases H 3 4 1 (by norm_num) (by norm_num) le_rfl hex with htop | halt · have hmem : Equiv.swap (0 : Fin 7) 3 ∈ S := hS (htop ▸ Subgroup.mem_top _) exact absurd (hmem 0) (by decide) · have halt' : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ alternatingGroup (Fin 7) := by rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap (by decide), Equiv.Perm.sign_swap (by decide)] rfl have hmem : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ S := hS (halt ▸ halt') exact absurd (hmem 0) (by decide)