kayak_paddle_leap_group_ne_of_even_first
If the first cycle of KP(k, m, l) has even length k, its leap group is neither the symmetric nor the alternating group.
Statement
theorem kayak_paddle_leap_group_ne_of_even_first (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m)
(hl : 1 ≤ l) (he : Even k) :
simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ ⊤ ∧
simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ alternatingGroup _- Source
- Serves kayak_paddle_leap_group_ne_of_even_cycle; arXiv:2610.18463 (The group generated by a graph's derangements), Question 2.20 (list entry OP-301).
- Verified
- 15 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- kayak_paddle_hop_maps_first_cycleIn KP(k, m, l) with k even, every hop maps the vertex set of the first cycle (the k-cycle) into itself.
- 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_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,…
- Used by 1
- kayak_paddle_leap_group_ne_of_even_cycleIf one of the two cycles of the kayak paddle graph KP(k, m, l) has even length, its leap group is neither the symmetric nor the…
The proof, explained
The proof establishes that the leap group of a kayak paddle graph $\mathrm{KP}(k, m, l)$ with even $k$ is neither the full symmetric group nor the alternating group. It defines a subgroup $S$ consisting of all permutations that setwise stabilize the first cycle $C_k = \{v \mid v < k\}$, and proves that every hop belongs to $S$ using the fact that hops map $C_k$ into itself together with a counting argument on finite sets. It then constructs a transposition and an even permutation that move a vertex from $C_k$ outside $C_k$, showing neither can belong to $S$ and thereby ruling out both candidate groups.
The set $S$ of permutations that setwise stabilize the first cycle $\{v \mid v < k\}$ forms a subgroup.
Define $S$ as the set of permutations $g$ satisfying $g(v) < k \iff v < k$ for every vertex $v$. It is verified that $S$ is closed under multiplication (since $(a * b)(v) < k \iff b(v) < k \iff v < k$), contains the identity permutation, and is closed under inverses (by applying the membership condition for $a$ to $a^{-1}(v)$).
uses
Set.mem_setOf_eq,Equiv.Perm.mul_apply,Equiv.Perm.inv_def,Equiv.apply_symm_applylet S : Subgroup (Equiv.Perm (Fin (k + m + l - 1))) := { carrier := {g | ∀ v, (g v : ℕ) < k ↔ (v : ℕ) < k} 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 }
The leap group of the kayak paddle graph is contained in $S$.
By `Subgroup.closure_le`, it suffices to show that every hop $h$ belongs to $S$, i.e., $h(v) < k \iff v < k$. The right-to-left implication is the lemma `kayak_paddle_hop_maps_first_cycle`, which states that hops map the first cycle into itself when $k$ is even. For the left-to-right implication, suppose for contradiction that $h(v) < k$ but $v \ge k$. Letting $C = \{w \mid w < k\}$, $h(C) \subseteq C$. Because $h$ is injective and $C$ is finite, $|h(C)| = |C|$, which implies $h(C) = C$. Thus $h(v) \in C = h(C)$, so $h(v) = h(w)$ for some $w \in C$. Injectivity of $h$ gives $v = w < k$, a contradiction.
uses
Subgroup.closure_le,kayak_paddle_hop_maps_first_cycle,Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,Finset.eq_of_subset_of_card_le,Finset.card_image_of_injective,Finset.mem_image.mphave hle : simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≤ S := by refine (Subgroup.closure_le S).mpr fun h hh v => ?_ constructor · intro hv by_contra hv' have hinto : ∀ w : Fin (k + m + l - 1), (w : ℕ) < k → (h w : ℕ) < k := fun w hw => kayak_paddle_hop_maps_first_cycle k m l hk hm hl he h hh w hw let C : Finset (Fin (k + m + l - 1)) := Finset.univ.filter fun w => (w : ℕ) < k have hsub : C.image h ⊆ C := by intro x hx simp only [C, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ obtain ⟨w, hw, rfl⟩ := hx exact hinto w hw have heq : C.image h = C := Finset.eq_of_subset_of_card_le hsub (by rw [Finset.card_image_of_injective _ h.injective]) have hmem : h v ∈ C.image h := by rw [heq]; simp [C, hv] obtain ⟨w, hw, hwv⟩ := Finset.mem_image.mp hmem have := h.injective hwv subst this simp [C] at hw omega · intro hv exact kayak_paddle_hop_maps_first_cycle k m l hk hm hl he h hh v hv
The vertices $a = 0$, $b = k + l - 1$, and $c = k + l$ are valid and pairwise distinct.
From $k \ge 3$, $m \ge 3$, and $l \ge 1$, linear arithmetic shows that $0$, $k + l - 1$, and $k + l$ are strictly less than the total number of vertices $k + m + l - 1$. Defining $a, b, c$ as the corresponding elements of `Fin (k + m + l - 1)`, they are pairwise distinct because $0 < k \le k + l - 1 < k + l$.
uses
Fin.ext_iffhave h0 : (0 : ℕ) < k + m + l - 1 := by omega have h1 : k + l - 1 < k + m + l - 1 := by omega have h2 : k + l < k + m + l - 1 := by omega let a : Fin (k + m + l - 1) := ⟨0, h0⟩ let b : Fin (k + m + l - 1) := ⟨k + l - 1, h1⟩ let c : Fin (k + m + l - 1) := ⟨k + l, h2⟩ have hab : a ≠ b := by simp [a, b, Fin.ext_iff]; omega have hbc : b ≠ c := by simp [b, c, Fin.ext_iff]; omega have hac : a ≠ c := by simp [a, c, Fin.ext_iff]; omega
The leap group cannot be the full symmetric group $\top$.
Assuming for contradiction that the leap group equals $\top$, the transposition $(a\ b)$ must belong to the leap group, hence to $S$. Since $(a\ b)(a) = b$ and $a = 0 < k$, membership in $S$ requires $b < k$, which means $k + l - 1 < k$. This contradicts $l \ge 1$.
uses
Subgroup.mem_top,Equiv.swap_apply_leftrefine ⟨fun htop => ?_, fun halt => ?_⟩ · have hmem : Equiv.swap a b ∈ S := hle (htop ▸ Subgroup.mem_top _) have := (hmem a).mpr (by simp [a]; omega) rw [Equiv.swap_apply_left] at this simp [b] at this omega
The leap group cannot be the alternating group.
Assuming for contradiction that the leap group is the alternating group, the product of transpositions $(a\ b)(b\ c)$ has sign $(-1)(-1) = 1$, so it belongs to the alternating group and thus to $S$. Because $a \ne b$ and $a \ne c$, the transposition $(b\ c)$ fixes $a$, and then $(a\ b)$ sends $a$ to $b$. Since this permutation belongs to $S$ and $a < k$, we must have $b < k$, which again asserts $k + l - 1 < k$, contradicting $l \ge 1$.
uses
Equiv.Perm.mem_alternatingGroup,Equiv.Perm.sign_mul,Equiv.Perm.sign_swap,Equiv.Perm.mul_apply,Equiv.swap_apply_of_ne_of_ne,Equiv.swap_apply_left· have halt' : Equiv.swap a b * Equiv.swap b c ∈ alternatingGroup (Fin (k + m + l - 1)) := by rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap hab, Equiv.Perm.sign_swap hbc] rfl have hmem : Equiv.swap a b * Equiv.swap b c ∈ S := hle (halt ▸ halt') have := (hmem a).mpr (by simp [a]; omega) rw [Equiv.Perm.mul_apply, Equiv.swap_apply_of_ne_of_ne hab hac, Equiv.swap_apply_left] at this simp [b] at this omega
Set.mem_setOf_eq- An element $x$ belongs to $\{y \mid P(y)\}$ if and only if $P(x)$ holds.
Equiv.Perm.mul_apply- The group operation on permutations is composition: $(f * g)(x) = f(g(x))$.
Equiv.Perm.inv_def- The group inverse of a permutation is its inverse equivalence ($f^{-1} = f.\mathrm{symm}$).
Equiv.apply_symm_apply- Applying an equivalence to its inverse value yields the original element: $e(e^{-1}(x)) = x$.
Subgroup.closure_le- The subgroup generated by a subset $k$ is contained in a subgroup $K$ if and only if $k \subseteq K$.
kayak_paddle_hop_maps_first_cycle- In a kayak paddle graph $\mathrm{KP}(k, m, l)$ with $k \ge 3$ even, $m \ge 3$, and $l \ge 1$, every hop permutation maps vertices of the first cycle $\{v \mid v < k\}$ into the first cycle.
Finset.mem_image- An element $b$ belongs to the image $f(s)$ of a finite set $s$ if and only if $b = f(a)$ for some $a \in s$.
Finset.mem_filter- An element $a$ belongs to the filtered set $\{x \in s \mid P(x)\}$ if and only if $a \in s$ and $P(a)$ holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and- The logical simplification $(\mathrm{True} \land p) = p$.
Finset.eq_of_subset_of_card_le- If $s \subseteq t$ are finite sets and $|t| \le |s|$, then $s = t$.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the domain set.
Finset.mem_image.mp- If an element is in the image $f(s)$, then it equals $f(a)$ for some $a \in s$.
Fin.ext_iff- Two elements of `Fin n` are equal if and only if their underlying natural numbers are equal.
Subgroup.mem_top- Every element of a group belongs to the top subgroup $\top$.
Equiv.swap_apply_left- The transposition $(a\ b)$ maps $a$ to $b$.
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: $\mathrm{sign}(f * g) = \mathrm{sign}(f)\mathrm{sign}(g)$.
Equiv.Perm.sign_swap- The sign of a transposition of two distinct elements is $-1$.
Equiv.swap_apply_of_ne_of_ne- A transposition $(a\ b)$ fixes any element distinct from both $a$ and $b$.
- In the formal definition of the kayak paddle graph $\mathrm{KP}(k, m, l)$, vertices are indexed by `Fin (k + m + l - 1)`. The condition $(v : \mathbb{N}) < k$ identifies the vertices of the first cycle.
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_ne_of_even_first (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) (he : Even k) : simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ ⊤ ∧ simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ alternatingGroup _ := by let S : Subgroup (Equiv.Perm (Fin (k + m + l - 1))) := { carrier := {g | ∀ v, (g v : ℕ) < k ↔ (v : ℕ) < k} 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 hle : simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≤ S := by refine (Subgroup.closure_le S).mpr fun h hh v => ?_ constructor · intro hv by_contra hv' have hinto : ∀ w : Fin (k + m + l - 1), (w : ℕ) < k → (h w : ℕ) < k := fun w hw => kayak_paddle_hop_maps_first_cycle k m l hk hm hl he h hh w hw let C : Finset (Fin (k + m + l - 1)) := Finset.univ.filter fun w => (w : ℕ) < k have hsub : C.image h ⊆ C := by intro x hx simp only [C, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ obtain ⟨w, hw, rfl⟩ := hx exact hinto w hw have heq : C.image h = C := Finset.eq_of_subset_of_card_le hsub (by rw [Finset.card_image_of_injective _ h.injective]) have hmem : h v ∈ C.image h := by rw [heq]; simp [C, hv] obtain ⟨w, hw, hwv⟩ := Finset.mem_image.mp hmem have := h.injective hwv subst this simp [C] at hw omega · intro hv exact kayak_paddle_hop_maps_first_cycle k m l hk hm hl he h hh v hv have h0 : (0 : ℕ) < k + m + l - 1 := by omega have h1 : k + l - 1 < k + m + l - 1 := by omega have h2 : k + l < k + m + l - 1 := by omega let a : Fin (k + m + l - 1) := ⟨0, h0⟩ let b : Fin (k + m + l - 1) := ⟨k + l - 1, h1⟩ let c : Fin (k + m + l - 1) := ⟨k + l, h2⟩ have hab : a ≠ b := by simp [a, b, Fin.ext_iff]; omega have hbc : b ≠ c := by simp [b, c, Fin.ext_iff]; omega have hac : a ≠ c := by simp [a, c, Fin.ext_iff]; omega refine ⟨fun htop => ?_, fun halt => ?_⟩ · have hmem : Equiv.swap a b ∈ S := hle (htop ▸ Subgroup.mem_top _) have := (hmem a).mpr (by simp [a]; omega) rw [Equiv.swap_apply_left] at this simp [b] at this omega · have halt' : Equiv.swap a b * Equiv.swap b c ∈ alternatingGroup (Fin (k + m + l - 1)) := by rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap hab, Equiv.Perm.sign_swap hbc] rfl have hmem : Equiv.swap a b * Equiv.swap b c ∈ S := hle (halt ▸ halt') have := (hmem a).mpr (by simp [a]; omega) rw [Equiv.Perm.mul_apply, Equiv.swap_apply_of_ne_of_ne hab hac, Equiv.swap_apply_left] at this simp [b] at this omega