kayak_paddle_leap_group_ne_of_even_second
If the second cycle of KP(k, m, l) has even length m, its leap group is neither the symmetric nor the alternating group.
Statement
theorem kayak_paddle_leap_group_ne_of_even_second (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m)
(hl : 1 ≤ l) (he : Even m) :
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_second_cycleIn KP(k, m, l) with m even, every hop maps the vertex set of the second cycle (the m-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 shows that the leap group of KP(k, m, l) is contained in the set-stabilizer subgroup S of permutations preserving the vertices of the second cycle C₂ = {v | k + l - 1 ≤ v}. Because the second cycle has even length m, every hop maps C₂ into C₂, and since C₂ is finite and hops are injective, every hop maps C₂ bijectively onto C₂; thus the entire leap group is contained in S. The proof then exhibits a transposition and a product of two transpositions that swap a vertex of C₂ with a vertex outside C₂. Neither permutation belongs to S, which implies the leap group can be neither the symmetric group nor the alternating group.
The permutations preserving the second cycle form a subgroup S of the symmetric group.
We define s = k + l - 1, which is the starting vertex index of the second cycle, and note s < k + m + l - 1. We define S as the set of all permutations g of the vertices such that s ≤ g(v) ↔ s ≤ v for every vertex v; that is, g preserves the vertex set of the second cycle and its complement. We verify that S is a subgroup: it contains the identity permutation, is closed under composition (since the equivalences chain), and is closed under inversion (by applying the equivalence for g to g⁻¹(v)).
uses
Set.mem_setOf_eq,Equiv.Perm.mul_apply,Equiv.Perm.inv_def,Equiv.apply_symm_applyset s := k + l - 1 with hs have hN : s < k + m + l - 1 := by omega let S : Subgroup (Equiv.Perm (Fin (k + m + l - 1))) := { carrier := {g | ∀ v, s ≤ (g v : ℕ) ↔ s ≤ (v : ℕ)} 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 the subgroup S.
Because the leap group is generated by hops, Subgroup.closure_le reduces the claim to showing that every hop h belongs to S, meaning s ≤ h(v) ↔ s ≤ v. The backward direction s ≤ v → s ≤ h(v) is given directly by kayak_paddle_hop_maps_second_cycle, which guarantees that when m is even, any hop sends the second cycle into itself. For the forward direction s ≤ h(v) → s ≤ v, suppose for contradiction that v < s. Letting C be the finite set of vertices with index ≥ s, h maps C into C. Since h is injective, |h(C)| = |C|, so h(C) = C. Since h(v) ∈ C = h(C), injectivity forces v ∈ C, meaning s ≤ v, which contradicts v < s.
uses
Subgroup.closure_le,not_le,kayak_paddle_hop_maps_second_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' rw [not_le] at hv' -- h maps the second cycle into itself, hence onto itself (finite), so v outside maps outside have hinto : ∀ w : Fin (k + m + l - 1), s ≤ (w : ℕ) → s ≤ (h w : ℕ) := fun w hw => kayak_paddle_hop_maps_second_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 => s ≤ (w : ℕ) 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_second_cycle k m l hk hm hl he h hh v hv
The vertices a = s, b = 0, and c = 1 are pairwise distinct.
Since k ≥ 3, m ≥ 3, and l ≥ 1, linear arithmetic confirms that 0, 1, and s = k + l - 1 are strictly less than the total number of vertices k + m + l - 1, yielding valid vertices a = s, b = 0, and c = 1 in Fin (k + m + l - 1). Moreover, s = k + l - 1 ≥ 3, so s ≠ 0 and s ≠ 1, and 0 ≠ 1. By Fin.ext_iff, the three vertices a, b, and c are pairwise distinct.
uses
Fin.ext_iffhave h0 : (0 : ℕ) < k + m + l - 1 := by omega have h1 : (1 : ℕ) < k + m + l - 1 := by omega let a : Fin (k + m + l - 1) := ⟨s, hN⟩ let b : Fin (k + m + l - 1) := ⟨0, h0⟩ let c : Fin (k + m + l - 1) := ⟨1, h1⟩ have hab : a ≠ b := by simp [a, b, Fin.ext_iff]; omega have hbc : b ≠ c := by simp [b, c, Fin.ext_iff] have hac : a ≠ c := by simp [a, c, Fin.ext_iff]; omega
The leap group is not the full symmetric group.
We split the goal into two disproofs and suppose for contradiction that the leap group equals ⊤. Then the transposition swap(a, b) would belong to the leap group, hence to S. Because s ≤ a, membership in S requires s ≤ swap(a, b)(a). By Equiv.swap_apply_left, swap(a, b)(a) = b = 0, which implies s ≤ 0. But s ≥ 3, so linear arithmetic yields a contradiction.
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]) rw [Equiv.swap_apply_left] at this simp [b] at this omega
The leap group is not the alternating group.
Supposing for contradiction that the leap group equals the alternating group, consider the product of two transpositions swap(a, b) * swap(b, c). Because a, b, c are pairwise distinct, each transposition has sign -1, so the product has sign (-1) * (-1) = 1 and thus belongs to the alternating group. It must therefore belong to S. Evaluating at a, the transposition swap(b, c) fixes a because a ≠ b and a ≠ c, and then swap(a, b) sends a to b = 0. Membership in S then implies s ≤ 0, which again contradicts s ≥ 3.
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]) 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- Membership in a set defined by comprehension {y | p y} is equivalent to the predicate p x holding.
Equiv.Perm.mul_apply- Permutation multiplication corresponds to composition: (f * g) x = f (g x).
Equiv.Perm.inv_def- The group inverse f⁻¹ of a permutation is given by its inverse equivalence f.symm.
Equiv.apply_symm_apply- Applying an equivalence after its inverse is the identity: e (e⁻¹ x) = x.
Subgroup.closure_le- The subgroup generated by a set k is contained in a subgroup K if and only if k ⊆ K.
not_le- In a linear order, ¬(a ≤ b) is equivalent to b < a.
kayak_paddle_hop_maps_second_cycle- For a kayak paddle graph with an even second cycle of length m, every hop maps vertices of the second cycle (indices ≥ k + l - 1) to vertices of the second 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 ∈ s.
Finset.mem_filter- An element a belongs to the filtered finset {x ∈ s | p x} if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The conjunction True ∧ p simplifies to p.
Finset.eq_of_subset_of_card_le- If a finite set s is a subset of t and |t| ≤ |s|, then s = t.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Finset.mem_image.mp- If an element belongs to the image f(s), there exists a preimage 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 (maximal) subgroup ⊤.
Equiv.swap_apply_left- The transposition swap(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.
Equiv.Perm.sign_swap- The transposition of two distinct elements has sign -1.
Equiv.swap_apply_of_ne_of_ne- A transposition swap(a, b) fixes any element distinct from both a and b.
- The vertex set of the kayak paddle graph is modeled by `Fin (k + m + l - 1)`, so bounds on vertex indices and their distinctness are handled by linear integer arithmetic (`omega`).
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_second (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) (he : Even m) : simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ ⊤ ∧ simple_graph_leap_group (simple_graph_kayak_paddle k m l) ≠ alternatingGroup _ := by set s := k + l - 1 with hs have hN : s < k + m + l - 1 := by omega let S : Subgroup (Equiv.Perm (Fin (k + m + l - 1))) := { carrier := {g | ∀ v, s ≤ (g v : ℕ) ↔ s ≤ (v : ℕ)} 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' rw [not_le] at hv' -- h maps the second cycle into itself, hence onto itself (finite), so v outside maps outside have hinto : ∀ w : Fin (k + m + l - 1), s ≤ (w : ℕ) → s ≤ (h w : ℕ) := fun w hw => kayak_paddle_hop_maps_second_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 => s ≤ (w : ℕ) 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_second_cycle k m l hk hm hl he h hh v hv have h0 : (0 : ℕ) < k + m + l - 1 := by omega have h1 : (1 : ℕ) < k + m + l - 1 := by omega let a : Fin (k + m + l - 1) := ⟨s, hN⟩ let b : Fin (k + m + l - 1) := ⟨0, h0⟩ let c : Fin (k + m + l - 1) := ⟨1, h1⟩ have hab : a ≠ b := by simp [a, b, Fin.ext_iff]; omega have hbc : b ≠ c := by simp [b, c, Fin.ext_iff] 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]) 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]) 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