AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_leap_group_ne_of_even_first

theoremverified

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

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.

  1. 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)$).

    lines 5–15

    uses Set.mem_setOf_eq, Equiv.Perm.mul_apply, Equiv.Perm.inv_def, Equiv.apply_symm_apply

      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 }
  2. 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.

    lines 16–39

    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.mp

      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
  3. 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$.

    lines 40–48

    uses Fin.ext_iff

      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
  4. 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$.

    lines 49–54

    uses Subgroup.mem_top, Equiv.swap_apply_left

      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
  5. 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$.

    lines 55–63

    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$.

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

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
See it in the graphDiscuss this resultChallenge it