kayak_paddle_hop_maps_second_cycle
In KP(k, m, l) with m even, every hop maps the vertex set of the second cycle (the m-cycle) into itself.
Statement
theorem kayak_paddle_hop_maps_second_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)
(he : Even m) (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 : k + l - 1 ≤ (v : ℕ)) : k + l - 1 ≤ (h v : ℕ)- 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_secondIf the second cycle of KP(k, m, l) has even length m, its leap group is neither the symmetric nor the alternating group.
The proof, explained
The vertex set of the second cycle C_m in the kayak paddle graph KP(k, m, l) consists of all vertices with index at least the junction s = k + l - 1. The proof shows that any hop h preserves this set by first showing that neighbours of the open path T = {v | s < v} cannot leave the second cycle, and that adjacency inside T is simply path adjacency. It then proves that the junction vertex s cannot be mapped out of the second cycle: if h s < s, the inverse hop g = h⁻¹ would map T into itself by shifting each vertex by ±1, which would injectively map the m/2 vertices with odd offset from s into the m/2 - 1 vertices with even offset, violating the pigeonhole principle since m is even. Finally, combining the junction property with the path neighbour property ensures every vertex with s ≤ v satisfies s ≤ h v.
Any neighbour of a vertex in the open path T = {w | s < w} belongs to the second cycle (has index at least s).
We define the junction vertex s = k + l - 1, which connects the handle path to the second cycle C_m. Any vertex w with s < w lies strictly inside C_m. Unfolding the definition of adjacency in the kayak paddle graph (simple_graph_kayak_paddle, SimpleGraph.fromRel_adj), the only edges incident to w are within C_m, connecting to vertices with index at least s. Linear arithmetic (omega) verifies that no edges to the handle or the first cycle can reach w.
uses
simple_graph_kayak_paddle,SimpleGraph.fromRel_adjset s := k + l - 1 with hs -- neighbours of the open path T = {v | s < v} stay in the second cycle have stepA : ∀ u w : Fin (k + m + l - 1), s < (w : ℕ) → (simple_graph_kayak_paddle k m l).Adj w u → s ≤ (u : ℕ) := by intro u w hw hadj simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj omega
Any two adjacent vertices in the open path T are consecutive along the path (w = u + 1 or u = w + 1).
Suppose u and w both lie strictly beyond s and are adjacent. From the kayak paddle relation, the only possible adjacency between them is within C_m, where their offsets from s satisfy (w - s) = (u - s + 1) % m (or symmetrically). By splitting on whether (u - s + 1) < m or ≥ m (Nat.lt_or_ge): if it is less than m, the modulo is the identity (Nat.mod_eq_of_lt), so w = u + 1; if it is at least m, since u < k + m + l - 1, the offset equals m, making the modulo zero (Nat.mod_self), which would mean w = s, contradicting s < w. The symmetric case is identical.
uses
simple_graph_kayak_paddle,SimpleGraph.fromRel_adj,Nat.lt_or_ge,Nat.mod_eq_of_lt,Nat.mod_selfhave stepB : ∀ u w : Fin (k + m + l - 1), s < (u : ℕ) → s < (w : ℕ) → (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by intro u w hu hw hadj have hu' := u.isLt have hw' := w.isLt simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj obtain ⟨-, h1 | h1⟩ := hadj · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩ · omega · omega · omega · rcases Nat.lt_or_ge ((u : ℕ) - s + 1) m with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (u : ℕ) - s + 1 = m := by omega rw [this, Nat.mod_self] at h1; omega · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩ · omega · omega · omega · rcases Nat.lt_or_ge ((w : ℕ) - s + 1) m with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (w : ℕ) - s + 1 = m := by omega rw [this, Nat.mod_self] at h1; omega
Set up proof by contradiction that the junction vertex s remains in the second cycle, s ≤ h s.
We note that s is strictly less than the total number of vertices (hN). To prove that h maps s into the second cycle (s ≤ h s), we suppose for contradiction that h s < s (by_contra, not_le), and unpack the hypothesis that m is even.
uses
not_lehave hN : s < k + m + l - 1 := by omega have hjun : s ≤ (h ⟨s, hN⟩ : ℕ) := by by_contra hlt rw [not_le] at hlt obtain ⟨m2, hm2⟩ := he
The inverse permutation g = h⁻¹ maps the open path T into itself, shifting each vertex by ±1 along the path.
Since h is a hop, g t is adjacent to h (g t) = t. For any t in T (s < t), stepA implies s ≤ g t. If g t were s, then applying h would yield t = h s < s, contradicting s < t (Fin.ext). Hence s < g t, so g t is in T. Since both t and g t are in T and adjacent, stepB ensures that g t = t + 1 or t = g t + 1.
uses
Fin.extset g := h⁻¹ with hg have gT : ∀ t : Fin (k + m + l - 1), s < (t : ℕ) → s < (g t : ℕ) ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by intro t ht have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by have := hh (g t) simpa [hg] using this have h1 : s ≤ (g t : ℕ) := stepA (g t) t ht hadj.symm have h2 : (g t : ℕ) ≠ s := by intro heq have : g t = ⟨s, hN⟩ := Fin.ext heq have hgt : h (g t) = t := by simp [hg] rw [this] at hgt rw [hgt] at hlt omega have h3 : s < (g t : ℕ) := by omega exact ⟨h3, (stepB (g t) t h3 ht hadj).symm⟩
The assumption h s < s leads to a contradiction via a parity counting argument on T.
We consider the action ψ of g on indices, restricted to the set A of odd offsets from s (size m / 2) and the set B of even offsets from s (size m / 2 - 1) (Finset.card_image_of_injective, Finset.card_range). Since g shifts each vertex by ±1, it flips parity, mapping elements of A into B (Finset.mem_image, Finset.mem_range, dif_pos, Fin.val_mk). Because g is a permutation, ψ is injective on A (Set.InjOn, Finset.coe_image, Set.mem_image, Finset.mem_coe, Fin.ext, congrArg, Fin.val). By the pigeonhole principle (Finset.card_le_card_of_injOn), |A| ≤ |B|, meaning m / 2 ≤ m / 2 - 1, which is impossible (omega). Thus s ≤ h s.
uses
Finset.card_image_of_injective,Finset.card_range,Finset.mem_image,Finset.mem_range,Fin.val_mk,dif_pos,Finset.coe_image,Set.mem_image,Finset.mem_coe,Fin.ext,congrArg,Fin.val,Finset.card_le_card_of_injOnlet ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0 let A : Finset ℕ := (Finset.range (m / 2)).image (fun t => s + 1 + 2 * t) let B : Finset ℕ := (Finset.range (m / 2 - 1)).image (fun t => s + 2 + 2 * t) have hA : A.card = m / 2 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hB : B.card = m / 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' : s + 1 + 2 * t < k + m + l - 1 := by omega have hgt := gT ⟨s + 1 + 2 * t, hlt'⟩ (by show s < s + 1 + 2 * t; omega) simp only [Fin.val_mk] at hgt have hbound := (g ⟨s + 1 + 2 * t, hlt'⟩).isLt simp only [ψ, B, Finset.mem_image, Finset.mem_range] rw [dif_pos hlt'] generalize hx : ((g ⟨s + 1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt hbound ⊢ rcases hgt with ⟨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 : s + 1 + 2 * t < k + m + l - 1 := by omega have h2 : s + 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
Every vertex in the second cycle (s ≤ v) is mapped into the second cycle (s ≤ h v).
We split into cases on whether v = s or s < v (Nat.eq_or_lt_of_le). If v = s, then h v = h s ≥ s by the junction property established above (Fin.ext). If s < v, then v lies in the open path T; since h v is adjacent to v by the hop hypothesis, stepA directly implies s ≤ h v.
uses
Nat.eq_or_lt_of_le,Fin.extrcases Nat.eq_or_lt_of_le hv with hv' | hv' · have : v = ⟨s, hN⟩ := Fin.ext hv'.symm rw [this]; exact hjun · exact stepA (h v) v hv' (hh v)
simple_graph_kayak_paddle- definition of the kayak paddle graph KP(k, m, l), consisting of a k-cycle, a path of length l, and an m-cycle
SimpleGraph.fromRel_adj- two vertices in a graph built from a relation are adjacent if and only if they are distinct and related in either direction
Nat.lt_or_ge- for any natural numbers n and m, either n < m or n ≥ m
Nat.mod_eq_of_lt- if a < b, then a % b = a
Nat.mod_self- for any natural number n, n % n = 0
not_le- in a linear order, ¬(a ≤ b) is equivalent to b < a
Fin.ext- two elements of Fin n are equal if their underlying natural values are equal
Finset.card_image_of_injective- the image of a finite set under an injective map 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 is in the image of a finite set under f if and only if it is f(a) for some element a in the set
Finset.mem_range- a natural number m is in range n if and only if m < n
Fin.val_mk- the underlying natural value of ⟨m, h⟩ in Fin n is m
dif_pos- a dependent if-then-else expression evaluates to the then-branch when the condition is true
Finset.coe_image- the set coercion of the image of a finite set is the image of the set coercion
Set.mem_image- an element y is in f '' s if and only if y = f x for some x in s
Finset.mem_coe- an element is in the set coercion of a finite set if and only if it is in the finite set
congrArg- if two inputs are equal, then the values of a function applied to them are equal
Fin.val- the canonical projection from Fin n to ℕ giving its underlying value
Finset.card_le_card_of_injOn- an injective map from a finite set s into a finite set t implies |s| ≤ |t|
Nat.eq_or_lt_of_le- if n ≤ m, then n = m or n < m
- Linear arithmetic and graph edge conditions are handled by `omega`, which dispatches inequalities to verify that vertices in the open path cannot connect to the first cycle or handle.
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_second_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) (he : Even m) (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 : k + l - 1 ≤ (v : ℕ)) : k + l - 1 ≤ (h v : ℕ) := by set s := k + l - 1 with hs -- neighbours of the open path T = {v | s < v} stay in the second cycle have stepA : ∀ u w : Fin (k + m + l - 1), s < (w : ℕ) → (simple_graph_kayak_paddle k m l).Adj w u → s ≤ (u : ℕ) := by intro u w hw 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), s < (u : ℕ) → s < (w : ℕ) → (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by intro u w hu hw hadj have hu' := u.isLt have hw' := w.isLt simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj obtain ⟨-, h1 | h1⟩ := hadj · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩ · omega · omega · omega · rcases Nat.lt_or_ge ((u : ℕ) - s + 1) m with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (u : ℕ) - s + 1 = m := by omega rw [this, Nat.mod_self] at h1; omega · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩ · omega · omega · omega · rcases Nat.lt_or_ge ((w : ℕ) - s + 1) m with h2 | h2 · rw [Nat.mod_eq_of_lt h2] at h1; omega · have : (w : ℕ) - s + 1 = m := by omega rw [this, Nat.mod_self] at h1; omega -- first: h s lies in the second cycle have hN : s < k + m + l - 1 := by omega have hjun : s ≤ (h ⟨s, hN⟩ : ℕ) := by by_contra hlt rw [not_le] at hlt obtain ⟨m2, hm2⟩ := he -- g = h⁻¹ maps T into T, moving each point by one along the path set g := h⁻¹ with hg have gT : ∀ t : Fin (k + m + l - 1), s < (t : ℕ) → s < (g t : ℕ) ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by intro t ht have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by have := hh (g t) simpa [hg] using this have h1 : s ≤ (g t : ℕ) := stepA (g t) t ht hadj.symm have h2 : (g t : ℕ) ≠ s := by intro heq have : g t = ⟨s, hN⟩ := Fin.ext heq have hgt : h (g t) = t := by simp [hg] rw [this] at hgt rw [hgt] at hlt omega have h3 : s < (g t : ℕ) := by omega exact ⟨h3, (stepB (g t) t h3 ht hadj).symm⟩ -- counting: odd offsets map injectively to even offsets let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0 let A : Finset ℕ := (Finset.range (m / 2)).image (fun t => s + 1 + 2 * t) let B : Finset ℕ := (Finset.range (m / 2 - 1)).image (fun t => s + 2 + 2 * t) have hA : A.card = m / 2 := by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range] have hB : B.card = m / 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' : s + 1 + 2 * t < k + m + l - 1 := by omega have hgt := gT ⟨s + 1 + 2 * t, hlt'⟩ (by show s < s + 1 + 2 * t; omega) simp only [Fin.val_mk] at hgt have hbound := (g ⟨s + 1 + 2 * t, hlt'⟩).isLt simp only [ψ, B, Finset.mem_image, Finset.mem_range] rw [dif_pos hlt'] generalize hx : ((g ⟨s + 1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt hbound ⊢ rcases hgt with ⟨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 : s + 1 + 2 * t < k + m + l - 1 := by omega have h2 : s + 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 -- then every vertex of the second cycle stays there rcases Nat.eq_or_lt_of_le hv with hv' | hv' · have : v = ⟨s, hN⟩ := Fin.ext hv'.symm rw [this]; exact hjun · exact stepA (h v) v hv' (hh v)