kayak_paddle_hop_maps_first_cycle
In KP(k, m, l) with k even, every hop maps the vertex set of the first cycle (the k-cycle) into itself.
Statement
theorem kayak_paddle_hop_maps_first_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)
(he : Even k) (h : Equiv.Perm (Fin (k + m + l - 1)))
(hh : simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) (v : Fin (k + m + l - 1))
(hv : (v : ℕ) < k) : (h v : ℕ) < k- 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 2
- 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_firstIf the first cycle of KP(k, m, l) has even length k, its leap group is neither the symmetric nor the alternating group.
The proof, explained
The kayak paddle graph KP(k, m, l) consists of a k-cycle, an m-cycle, and a path of length l connecting them, attached to the first cycle at vertex 0. The remaining vertices 1, ..., k-1 of the first cycle form an open path whose neighbors remain inside the cycle. To show every hop h preserves the cycle, it suffices to show h(0) < k, since hops from any other cycle vertex cannot escape. If h(0) ≥ k, the inverse permutation g = h⁻¹ must preserve the open path and shift every vertex by ±1, toggling parity. But for even k, the open path has k/2 odd vertices and only k/2 - 1 even vertices, making an injective parity-reversing map impossible.
Any neighbor in KP(k, m, l) of a vertex in the open path T = {w | 0 < w < k} belongs to the first cycle (has index < k).
By definition of the kayak paddle graph, the only vertex in the first cycle with edges outside that cycle is the junction vertex 0, which connects to the path at vertex k. Since 0 < w < k, w cannot be 0, so every edge incident to w must lead to another vertex in the first cycle. Linear arithmetic (omega) verifies that all clauses of the adjacency relation outside the first cycle require one endpoint to be at least k, which is incompatible with w < k and w > 0.
uses
SimpleGraph.fromRel_adjhave stepA : ∀ u w : Fin (k + m + l - 1), 0 < (w : ℕ) → (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj w u → (u : ℕ) < k := by intro u w hw hwk hadj simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj omega
Adjacency between any two vertices in the open path T is standard path adjacency: |u - w| = 1.
Adjacent vertices in the first cycle must satisfy w ≡ u + 1 (mod k) or u ≡ w + 1 (mod k). Because both u and w are strictly positive and strictly less than k, neither is 0. Consequently, the modular wrap-around case (k - 1) + 1 ≡ 0 (mod k) cannot occur. Simplifying the modular arithmetic across all cases proves that w = u + 1 or u = w + 1.
uses
SimpleGraph.fromRel_adj,Nat.lt_or_ge,Nat.mod_eq_of_lt,Nat.mod_selfhave stepB : ∀ u w : Fin (k + m + l - 1), 0 < (u : ℕ) → (u : ℕ) < k → 0 < (w : ℕ) → (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by intro u w hu huk hw hwk hadj simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj obtain ⟨-, h1 | h1⟩ := hadj · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1 · rcases Nat.lt_or_ge ((u : ℕ) + 1) k with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (u : ℕ) + 1 = k := by omega rw [this, Nat.mod_self] at h1; omega · omega · omega · omega · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1 · rcases Nat.lt_or_ge ((w : ℕ) + 1) k with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (w : ℕ) + 1 = k := by omega rw [this, Nat.mod_self] at h1; omega · omega · omega · omega
Under the assumption that h(0) ≥ k, the inverse permutation g = h⁻¹ maps the open path T into itself and acts as a path neighbor: g(t) = t + 1 or t = g(t) + 1.
Assume for contradiction that h(0) ≥ k. Setting g = h⁻¹, every vertex t is adjacent to g(t) because g(t) is adjacent to h(g(t)) = t. For any t in the open path T (0 < t < k), its neighbor g(t) must satisfy g(t) < k by stepA. Furthermore, g(t) cannot be 0, as g(t) = 0 would imply h(0) = h(g(t)) = t < k, contradicting h(0) ≥ k. Thus 0 < g(t) < k, meaning g(t) ∈ T. Applying stepB to the adjacent vertices t and g(t) in T shows that g(t) = t + 1 or t = g(t) + 1.
uses
not_lt,Fin.exthave hN : 0 < k + m + l - 1 := by omega have hjun : (h ⟨0, hN⟩ : ℕ) < k := by by_contra hlt rw [not_lt] at hlt obtain ⟨k2, hk2⟩ := he set g := h⁻¹ with hg have gT : ∀ t : Fin (k + m + l - 1), 0 < (t : ℕ) → (t : ℕ) < k → 0 < (g t : ℕ) ∧ (g t : ℕ) < k ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by intro t ht htk have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by have := hh (g t) simpa [hg] using this have h1 : (g t : ℕ) < k := stepA (g t) t ht htk hadj.symm have h2 : (g t : ℕ) ≠ 0 := by intro heq have : g t = ⟨0, hN⟩ := Fin.ext heq have hgt : h (g t) = t := by simp [hg] rw [this] at hgt rw [hgt] at hlt omega have h3 : 0 < (g t : ℕ) := by omega exact ⟨h3, h1, (stepB (g t) t h3 h1 ht htk hadj).symm⟩
The map ψ induced by g maps the odd vertices A ⊆ T into the even vertices B ⊆ T.
Let A = {1 + 2t | 0 ≤ t < k/2} be the odd vertices in T and B = {2 + 2t | 0 ≤ t < k/2 - 1} be the even vertices in T. Since the affine maps t ↦ 1 + 2t and t ↦ 2 + 2t are injective, |A| = k/2 and |B| = k/2 - 1. For any a ∈ A, a is odd and in T, so g(a) ∈ T differs from a by 1. Being adjacent to an odd vertex along the path, g(a) must be an even vertex strictly between 0 and k, which places it in B.
uses
Finset.card_image_of_injective,Finset.card_range,Finset.mem_image,Finset.mem_range,dif_poslet ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0 let A : Finset ℕ := (Finset.range (k / 2)).image (fun t => 1 + 2 * t) let B : Finset ℕ := (Finset.range (k / 2 - 1)).image (fun t => 2 + 2 * t) have hA : A.card = k / 2 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hB : B.card = k / 2 - 1 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hmaps : ∀ a ∈ A, ψ a ∈ B := by intro a ha simp only [A, Finset.mem_image, Finset.mem_range] at ha obtain ⟨t, ht, rfl⟩ := ha have hlt' : 1 + 2 * t < k + m + l - 1 := by omega have hgt := gT ⟨1 + 2 * t, hlt'⟩ (by show 0 < 1 + 2 * t; omega) (by show 1 + 2 * t < k; omega) simp only at hgt simp only [ψ, B, Finset.mem_image, Finset.mem_range] rw [dif_pos hlt'] generalize hx : ((g ⟨1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt ⊢ rcases hgt with ⟨h1, h1', h2 | h2⟩ · exact ⟨t, by omega, by omega⟩ · exact ⟨t - 1, by omega, by omega⟩
The map ψ is injective on A, which forces |A| ≤ |B| and yields a contradiction, proving h(0) < k.
Since g is a permutation, it is injective, so ψ is injective on A. By the pigeonhole principle (Finset.card_le_card_of_injOn), this injection implies |A| ≤ |B|, which means k/2 ≤ k/2 - 1. Linear arithmetic flags this contradiction, refuting the assumption h(0) ≥ k and concluding that h(0) < k.
uses
Finset.coe_image,Set.mem_image,Finset.mem_coe,Finset.mem_range,dif_pos,Fin.ext,congrArg,Fin.val,Finset.card_le_card_of_injOnhave hinj : Set.InjOn ψ A := by intro a ha b hb hab simp only [A, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_range] at ha hb obtain ⟨t, ht, rfl⟩ := ha obtain ⟨u, hu, rfl⟩ := hb have h1 : 1 + 2 * t < k + m + l - 1 := by omega have h2 : 1 + 2 * u < k + m + l - 1 := by omega simp only [ψ] at hab rw [dif_pos h1, dif_pos h2] at hab have := g.injective (Fin.ext hab) simpa using congrArg Fin.val this have := Finset.card_le_card_of_injOn ψ hmaps hinj rw [hA, hB] at this omega
For every vertex v with v < k, h(v) < k.
We split into cases on whether v = 0 or v > 0. If v = 0, h(v) < k is the junction result h(0) < k just established. If v > 0, then 0 < v < k, so v belongs to the open path T. Since h is a hop, h(v) is adjacent to v, so stepA immediately gives h(v) < k.
uses
Nat.eq_zero_or_pos,Fin.extrcases Nat.eq_zero_or_pos (v : ℕ) with hv' | hv' · have : v = ⟨0, hN⟩ := Fin.ext hv' rw [this]; exact hjun · exact stepA (h v) v hv' hv (hh v)
SimpleGraph.fromRel_adj- In a graph defined from a relation r, two vertices v and w are adjacent if and only if v ≠ w and either r(v, w) or r(w, v) holds.
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
Nat.mod_eq_of_lt- If a natural number a is strictly less than b, then a % b = a.
Nat.mod_self- For any natural number n, n % n = 0.
not_lt- In a linear order, a is not strictly less than b if and only if b ≤ a.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_range- The finite set range n = {0, 1, ..., n - 1} has cardinality n.
Finset.mem_image- An element b belongs to the image of a finite set s under f if and only if b = f a for some a ∈ s.
Finset.mem_range- A natural number m belongs to range n if and only if m < n.
dif_pos- When a decidable condition c holds, the dependent conditional if c then t else e reduces to the then-branch.
Finset.coe_image- Coercing the image of a finite set to a set yields the set-theoretic image of the coerced set.
Set.mem_image- An element y belongs to the set image f '' s if and only if y = f x for some x ∈ s.
Finset.mem_coe- An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
congrArg- If two values are equal, then applying any function f to both yields equal results.
Fin.val- The canonical embedding mapping an element of Fin n to its underlying natural number.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
Nat.eq_zero_or_pos- Every natural number is either equal to 0 or strictly positive.
- To apply Mathlib's finite set cardinality lemmas to the permutation g = h⁻¹ (which acts on Fin (k + m + l - 1)), the formal proof defines an auxiliary function ψ : ℕ → ℕ using a dependent if-then-else (dite), extending g by zero outside its domain.
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_hop_maps_first_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) (he : Even k) (h : Equiv.Perm (Fin (k + m + l - 1))) (hh : simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) (v : Fin (k + m + l - 1)) (hv : (v : ℕ) < k) : (h v : ℕ) < k := by -- neighbours of the open path T = {v | 0 < v < k} stay in the first cycle have stepA : ∀ u w : Fin (k + m + l - 1), 0 < (w : ℕ) → (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj w u → (u : ℕ) < k := by intro u w hw hwk hadj simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj omega -- adjacency inside T is adjacency along the path have stepB : ∀ u w : Fin (k + m + l - 1), 0 < (u : ℕ) → (u : ℕ) < k → 0 < (w : ℕ) → (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by intro u w hu huk hw hwk hadj simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj obtain ⟨-, h1 | h1⟩ := hadj · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1 · rcases Nat.lt_or_ge ((u : ℕ) + 1) k with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (u : ℕ) + 1 = k := by omega rw [this, Nat.mod_self] at h1; omega · omega · omega · omega · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1 · rcases Nat.lt_or_ge ((w : ℕ) + 1) k with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (w : ℕ) + 1 = k := by omega rw [this, Nat.mod_self] at h1; omega · omega · omega · omega have hN : 0 < k + m + l - 1 := by omega have hjun : (h ⟨0, hN⟩ : ℕ) < k := by by_contra hlt rw [not_lt] at hlt obtain ⟨k2, hk2⟩ := he set g := h⁻¹ with hg have gT : ∀ t : Fin (k + m + l - 1), 0 < (t : ℕ) → (t : ℕ) < k → 0 < (g t : ℕ) ∧ (g t : ℕ) < k ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by intro t ht htk have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by have := hh (g t) simpa [hg] using this have h1 : (g t : ℕ) < k := stepA (g t) t ht htk hadj.symm have h2 : (g t : ℕ) ≠ 0 := by intro heq have : g t = ⟨0, hN⟩ := Fin.ext heq have hgt : h (g t) = t := by simp [hg] rw [this] at hgt rw [hgt] at hlt omega have h3 : 0 < (g t : ℕ) := by omega exact ⟨h3, h1, (stepB (g t) t h3 h1 ht htk hadj).symm⟩ let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0 let A : Finset ℕ := (Finset.range (k / 2)).image (fun t => 1 + 2 * t) let B : Finset ℕ := (Finset.range (k / 2 - 1)).image (fun t => 2 + 2 * t) have hA : A.card = k / 2 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hB : B.card = k / 2 - 1 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hmaps : ∀ a ∈ A, ψ a ∈ B := by intro a ha simp only [A, Finset.mem_image, Finset.mem_range] at ha obtain ⟨t, ht, rfl⟩ := ha have hlt' : 1 + 2 * t < k + m + l - 1 := by omega have hgt := gT ⟨1 + 2 * t, hlt'⟩ (by show 0 < 1 + 2 * t; omega) (by show 1 + 2 * t < k; omega) simp only at hgt simp only [ψ, B, Finset.mem_image, Finset.mem_range] rw [dif_pos hlt'] generalize hx : ((g ⟨1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt ⊢ rcases hgt with ⟨h1, h1', h2 | h2⟩ · exact ⟨t, by omega, by omega⟩ · exact ⟨t - 1, by omega, by omega⟩ have hinj : Set.InjOn ψ A := by intro a ha b hb hab simp only [A, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_range] at ha hb obtain ⟨t, ht, rfl⟩ := ha obtain ⟨u, hu, rfl⟩ := hb have h1 : 1 + 2 * t < k + m + l - 1 := by omega have h2 : 1 + 2 * u < k + m + l - 1 := by omega simp only [ψ] at hab rw [dif_pos h1, dif_pos h2] at hab have := g.injective (Fin.ext hab) simpa using congrArg Fin.val this have := Finset.card_le_card_of_injOn ψ hmaps hinj rw [hA, hB] at this omega rcases Nat.eq_zero_or_pos (v : ℕ) with hv' | hv' · have : v = ⟨0, hN⟩ := Fin.ext hv' rw [this]; exact hjun · exact stepA (h v) v hv' hv (hh v)