AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_leap_group_ne_of_even_second

theoremverified

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

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.

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

    lines 5–17

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

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

    lines 18–43

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

    lines 44–51

    uses Fin.ext_iff

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

    lines 52–57

    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])
        rw [Equiv.swap_apply_left] at this
        simp [b] at this
        omega
  5. 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.

    lines 58–66

    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.

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