AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_leap_group_not_eq_top_or_alternating

theoremverifiedoriginal

No: KP(3, 4, 1) (a triangle and a 4-cycle joined by an edge, 7 vertices) admits a hop, but its leap group is neither S_7 nor A_7. Every hop of KP(3,4,1) maps the triangle {0,1,2} to itself, so the leap group fixes that set (it has order 24).

Statement

theorem kayak_paddle_leap_group_not_eq_top_or_alternating :
    ¬ ∀ k m l : ℕ, 3 ≤ k → 3 ≤ m → 1 ≤ l →
      (∃ h, simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) →
      simple_graph_leap_group (simple_graph_kayak_paddle k m l) = ⊤ ∨
        simple_graph_leap_group (simple_graph_kayak_paddle k m l) = alternatingGroup _
Related work
arXiv:2610.18463 (The group generated by a graph's derangements), Question 2.20 (and the sentence before it: 'We believe that many, if not all, kayak paddle graphs have leap group equal to either S_n or A_n'); list entry OP-301. Computation (exhaustive hop enumeration and Schreier-Sims) shows the leap group of KP(k,m,l) is S_N or A_N exactly when k and m are both odd, for all N ≤ 13; with an even cycle it is small (KP(3,4,1): order 24).
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
  • 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,…

The proof, explained

We refute the universal claim by showing that the kayak paddle graph KP(3, 4, 1) on 7 vertices is a counterexample. Any hop of KP(3, 4, 1) preserves the triangle {0, 1, 2}, so all hops—and therefore the entire leap group—are contained in the subgroup S of S_7 consisting of permutations that fix {0, 1, 2} setwise. Although KP(3, 4, 1) admits a hop, its leap group cannot be S_7 or A_7 because both groups contain permutations (such as (0 3) or (0 3)(3 4)) that move 0 outside the triangle.

  1. Assume for contradiction that every kayak paddle graph with a hop has leap group equal to the full symmetric group or the alternating group, and establish decidability of adjacency on KP(3, 4, 1).

    We argue by contradiction: let H be the assumed universal statement that every kayak paddle graph KP(k, m, l) with k, m ≥ 3 and l ≥ 1 that admits a hop has leap group equal to S_n or A_n. We refute this using the graph KP(3, 4, 1) on 7 vertices, whose adjacency relation is decidable.

    lines 6–8

      intro H
      letI : DecidableRel (simple_graph_kayak_paddle 3 4 1).Adj := by
        unfold simple_graph_kayak_paddle; infer_instance
  2. The set S of permutations of {0, ..., 6} that preserve the triangle {0, 1, 2} forms a subgroup of S_7.

    We define S as the set of permutations g satisfying g(v) < 3 ↔ v < 3. We check the subgroup axioms: closure under multiplication follows from Set.mem_setOf_eq and Equiv.Perm.mul_apply; the identity permutation trivially preserves the condition; and closure under inverses follows from Equiv.Perm.inv_def and Equiv.apply_symm_apply.

    lines 9–19

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

      let S : Subgroup (Equiv.Perm (Fin 7)) :=
        { carrier := {g | ∀ v, (g v).val < 3 ↔ v.val < 3}
          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 }
  3. In KP(3, 4, 1), neighbors of 1 and 2 lie in {0, 1, 2}, neighbors of 0, 4, and 6 cannot all lie outside {0, 1, 2}, and {0, 1, 2} contains only 0, 1, and 2. automation

    Four finite properties of KP(3, 4, 1) are verified by exhaustive case checking (decide): any neighbor of 1 or 2 is in {0, 1, 2}; if a_0, a_4, a_6 are distinct neighbors of 0, 4, 6 respectively, then a_0 < 3; and any three distinct elements of {0, 1, 2} exhaust the entire set.

    lines 20–26

      have k0 : ∀ a0 a4 a6 : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 0 a0 →
          (simple_graph_kayak_paddle 3 4 1).Adj 4 a4 → (simple_graph_kayak_paddle 3 4 1).Adj 6 a6 →
          a4 ≠ a6 → a0 ≠ a4 → a0 ≠ a6 → a0.val < 3 := by decide
      have k1 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 1 a → a.val < 3 := by decide
      have k2 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 2 a → a.val < 3 := by decide
      have k3 : ∀ a0 a1 a2 b : Fin 7, a0.val < 3 → a1.val < 3 → a2.val < 3 → a0 ≠ a1 → a0 ≠ a2 →
          a1 ≠ a2 → b.val < 3 → b = a0 ∨ b = a1 ∨ b = a2 := by decide
  4. Every hop of KP(3, 4, 1) preserves the triangle {0, 1, 2}, hence belongs to S.

    Let h be a hop of KP(3, 4, 1), so v ~ h(v) for all v. By injectivity of h, h(0), h(4), and h(6) are pairwise distinct, so applying k0 gives h(0) < 3; applying k1 and k2 gives h(1) < 3 and h(2) < 3. To see that h preserves {0, 1, 2}, note that if h(v) < 3, then h(v) must be one of h(0), h(1), h(2) by k3, so v ∈ {0, 1, 2} by injectivity; conversely, if v < 3 then v ∈ {0, 1, 2}, and in each case h(v) < 3 was already established.

    lines 27–46

      have hop_pres : ∀ h : Equiv.Perm (Fin 7),
          simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h → h ∈ S := by
        intro h hh v
        have inj := h.injective
        have l0 := k0 (h 0) (h 4) (h 6) (hh 0) (hh 4) (hh 6)
          (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide))
          (fun e => absurd (inj e) (by decide))
        have l1 := k1 (h 1) (hh 1)
        have l2 := k2 (h 2) (hh 2)
        constructor
        · intro hv
          rcases k3 (h 0) (h 1) (h 2) (h v) l0 l1 l2 (fun e => absurd (inj e) (by decide))
            (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) hv with
            e | e | e <;> rw [inj e] <;> decide
        · intro hv
          fin_cases v
          · exact l0
          · exact l1
          · exact l2
          all_goals exact absurd hv (by decide)
  5. The leap group of KP(3, 4, 1) is contained in S.

    The leap group is defined as the subgroup generated by all hops. Since every hop belongs to S, Subgroup.closure_le ensures that the generated subgroup is also contained in S.

    lines 47–48

    uses Subgroup.closure_le

      have hS : simple_graph_leap_group (simple_graph_kayak_paddle 3 4 1) ≤ S :=
        (Subgroup.closure_le S).mpr fun h hh => hop_pres h hh
  6. The graph KP(3, 4, 1) admits at least one hop.

    An explicit hop is provided by the permutation (0 1)(1 2)(3 4)(4 5)(5 6), and verifying that v ~ h(v) for all 7 vertices is a finite check.

    lines 49–51

      have hex : ∃ h, simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h :=
        ⟨Equiv.swap (0 : Fin 7) 1 * Equiv.swap 1 2 * Equiv.swap 3 4 * Equiv.swap 4 5 * Equiv.swap 5 6,
          by unfold simple_graph_is_hop; decide⟩
  7. Instantiating the universal assumption H shows that the leap group cannot be S_7.

    Applying H to k=3, m=4, l=1 with the witness hop leaves two cases: the leap group is either ⊤ = S_7 or A_7. If it were S_7, the transposition (0 3) would belong to S (by Subgroup.mem_top and the inclusion in S), but (0 3) maps 0 to 3, contradicting the condition 0 < 3 ↔ (0 3)(0) < 3.

    lines 52–54

    uses le_rfl, Subgroup.mem_top

      rcases H 3 4 1 (by norm_num) (by norm_num) le_rfl hex with htop | halt
      · have hmem : Equiv.swap (0 : Fin 7) 3 ∈ S := hS (htop ▸ Subgroup.mem_top _)
        exact absurd (hmem 0) (by decide)
  8. The leap group cannot be the alternating group A_7 either, completing the contradiction.

    If the leap group were A_7, the permutation (0 3)(3 4) would belong to A_7 because its sign is (-1) * (-1) = 1 (by Equiv.Perm.sign_mul, Equiv.Perm.sign_swap, and Equiv.Perm.mem_alternatingGroup). Hence it would belong to S, but evaluating it at 0 yields (0 3)(0) = 3 ≮ 3, again contradicting membership in S. Both cases lead to a contradiction, refuting H.

    lines 55–60

    uses Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap

      · have halt' : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ alternatingGroup (Fin 7) := by
          rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap (by decide),
            Equiv.Perm.sign_swap (by decide)]
          rfl
        have hmem : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ S := hS (halt ▸ halt')
        exact absurd (hmem 0) (by decide)
Set.mem_setOf_eq
An element x belongs to the set defined by a predicate p if and only if p(x) holds.
Equiv.Perm.mul_apply
The product of two permutations acts as their composition: (f * g)(x) = f(g(x)).
Equiv.Perm.inv_def
The group inverse of a permutation is its inverse bijection.
Equiv.apply_symm_apply
Applying a bijection to the image of an element under its inverse yields the element: e(e.symm(x)) = x.
Subgroup.closure_le
The subgroup generated by a set k is contained in a subgroup K if and only if k ⊆ K.
le_rfl
The inequality relation ≤ is reflexive: a ≤ a.
Subgroup.mem_top
Every element of a group belongs to the top subgroup ⊤.
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
A transposition of two distinct elements has sign -1.

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_not_eq_top_or_alternating :    ¬ ∀ k m l : ℕ, 3 ≤ k → 3 ≤ m → 1 ≤ l →      (∃ h, simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) →      simple_graph_leap_group (simple_graph_kayak_paddle k m l) = ⊤ ∨        simple_graph_leap_group (simple_graph_kayak_paddle k m l) = alternatingGroup _ := by  intro H  letI : DecidableRel (simple_graph_kayak_paddle 3 4 1).Adj := by    unfold simple_graph_kayak_paddle; infer_instance  let S : Subgroup (Equiv.Perm (Fin 7)) :=    { carrier := {g | ∀ v, (g v).val < 3 ↔ v.val < 3}      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 k0 : ∀ a0 a4 a6 : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 0 a0 →      (simple_graph_kayak_paddle 3 4 1).Adj 4 a4 → (simple_graph_kayak_paddle 3 4 1).Adj 6 a6 →      a4 ≠ a6 → a0 ≠ a4 → a0 ≠ a6 → a0.val < 3 := by decide  have k1 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 1 a → a.val < 3 := by decide  have k2 : ∀ a : Fin 7, (simple_graph_kayak_paddle 3 4 1).Adj 2 a → a.val < 3 := by decide  have k3 : ∀ a0 a1 a2 b : Fin 7, a0.val < 3 → a1.val < 3 → a2.val < 3 → a0 ≠ a1 → a0 ≠ a2 →      a1 ≠ a2 → b.val < 3 → b = a0 ∨ b = a1 ∨ b = a2 := by decide  have hop_pres : ∀ h : Equiv.Perm (Fin 7),      simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h → h ∈ S := by    intro h hh v    have inj := h.injective    have l0 := k0 (h 0) (h 4) (h 6) (hh 0) (hh 4) (hh 6)      (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide))      (fun e => absurd (inj e) (by decide))    have l1 := k1 (h 1) (hh 1)    have l2 := k2 (h 2) (hh 2)    constructor    · intro hv      rcases k3 (h 0) (h 1) (h 2) (h v) l0 l1 l2 (fun e => absurd (inj e) (by decide))        (fun e => absurd (inj e) (by decide)) (fun e => absurd (inj e) (by decide)) hv with        e | e | e <;> rw [inj e] <;> decide    · intro hv      fin_cases v      · exact l0      · exact l1      · exact l2      all_goals exact absurd hv (by decide)  have hS : simple_graph_leap_group (simple_graph_kayak_paddle 3 4 1) ≤ S :=    (Subgroup.closure_le S).mpr fun h hh => hop_pres h hh  have hex : ∃ h, simple_graph_is_hop (simple_graph_kayak_paddle 3 4 1) h :=    ⟨Equiv.swap (0 : Fin 7) 1 * Equiv.swap 1 2 * Equiv.swap 3 4 * Equiv.swap 4 5 * Equiv.swap 5 6,      by unfold simple_graph_is_hop; decide⟩  rcases H 3 4 1 (by norm_num) (by norm_num) le_rfl hex with htop | halt  · have hmem : Equiv.swap (0 : Fin 7) 3 ∈ S := hS (htop ▸ Subgroup.mem_top _)    exact absurd (hmem 0) (by decide)  · have halt' : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ alternatingGroup (Fin 7) := by      rw [Equiv.Perm.mem_alternatingGroup, Equiv.Perm.sign_mul, Equiv.Perm.sign_swap (by decide),        Equiv.Perm.sign_swap (by decide)]      rfl    have hmem : Equiv.swap (0 : Fin 7) 3 * Equiv.swap 3 4 ∈ S := hS (halt ▸ halt')    exact absurd (hmem 0) (by decide)
See it in the graphDiscuss this resultChallenge it