AFTD Auto-Formalizing Theoretical Domains

op_543_completeGraph_three_hop_word_length_le_one

theoremverifiedformalization

For the complete graph K₃ on 3 vertices, every element of its leap group is the product of at most 1 hop.

Statement

theorem op_543_completeGraph_three_hop_word_length_le_one :
    ∀ g ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 3)),
      ∃ w : List (Equiv.Perm (Fin 3)), (∀ h ∈ w, simple_graph_is_hop ⊤ h) ∧
        w.length ≤ 1 ∧ w.prod = g
Formalizes
arXiv:2610.18463, Proposition 2.2
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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_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.

Read back from the Lean

For every permutation $g$ in the leap group of the complete graph on $\text{Fin } 3$ (that is, the subgroup of $\text{Equiv.Perm}(\text{Fin } 3)$ generated by permutations $h$ such that $v$ is adjacent to $h(v)$ for all $v \in \text{Fin } 3$), there exists a list $w$ of permutations of $\text{Fin } 3$ such that: 1. Every element $h \in w$ is a hop in the complete graph on $\text{Fin } 3$ (i.e., $v \ne h(v)$ for all $v : \text{Fin } 3$), 2. The length of $w$ is at most 1, and 3. The product of the list $w$ equals $g$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

sketch

  1. decidability

    unfold and infer

    lines 4–5

      unfold simple_graph_is_hop
      infer_instance
  2. Hmul automation

    decide

    lines 12–14

      have Hmul : ∀ x y : Equiv.Perm (Fin 3),
          (x = 1 ∨ simple_graph_is_hop ⊤ x) → (y = 1 ∨ simple_graph_is_hop ⊤ y) →
          (x * y = 1 ∨ simple_graph_is_hop ⊤ (x * y)) := by decide
  3. Hinv automation

    decide

    lines 15–17

      have Hinv : ∀ x : Equiv.Perm (Fin 3),
          (x = 1 ∨ simple_graph_is_hop ⊤ x) →
          (x⁻¹ = 1 ∨ simple_graph_is_hop ⊤ (x⁻¹)) := by decide
  4. induction

    closure induction

    lines 18–24

      intro g hg
      have h_cases : g = 1 ∨ simple_graph_is_hop ⊤ g := by
        refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hg
        · intro x hx; exact Or.inr hx
        · exact Or.inl rfl
        · intro x y _ _ hx hy; exact Hmul x y hx hy
        · intro x _ hx; exact Hinv x hx
  5. cases

    word length

    lines 25–27

      rcases h_cases with rfl | hg_hop
      · exact ⟨[], by simp, by simp, by simp⟩
      · exact ⟨[g], by simp [hg_hop], by simp, by simp⟩

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

instance op_543_decidable_is_hop {V : Type*} [Fintype V]    (G : SimpleGraph V) [DecidableRel G.Adj] (h : Equiv.Perm V) :    Decidable (simple_graph_is_hop G h) := by  unfold simple_graph_is_hop  infer_instance/-- For the complete graph K_3 on 3 vertices, every element of its leap group is a product of at most 1 hop. -/theorem op_543_completeGraph_three_hop_word_length_le_one :    ∀ g ∈ simple_graph_leap_group (⊤ : SimpleGraph (Fin 3)),      ∃ w : List (Equiv.Perm (Fin 3)), (∀ h ∈ w, simple_graph_is_hop ⊤ h) ∧        w.length ≤ 1 ∧ w.prod = g := by  have Hmul : ∀ x y : Equiv.Perm (Fin 3),      (x = 1 ∨ simple_graph_is_hop ⊤ x) → (y = 1 ∨ simple_graph_is_hop ⊤ y) →      (x * y = 1 ∨ simple_graph_is_hop ⊤ (x * y)) := by decide  have Hinv : ∀ x : Equiv.Perm (Fin 3),      (x = 1 ∨ simple_graph_is_hop ⊤ x) →      (x⁻¹ = 1 ∨ simple_graph_is_hop ⊤ (x⁻¹)) := by decide  intro g hg  have h_cases : g = 1 ∨ simple_graph_is_hop ⊤ g := by    refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hg    · intro x hx; exact Or.inr hx    · exact Or.inl rfl    · intro x y _ _ hx hy; exact Hmul x y hx hy    · intro x _ hx; exact Hinv x hx  rcases h_cases with rfl | hg_hop  · exact ⟨[], by simp, by simp, by simp⟩  · exact ⟨[g], by simp [hg_hop], by simp, by simp⟩
See it in the graphDiscuss this resultChallenge it