op_543_completeGraph_three_hop_word_length_le_one
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
decidability
unfold and infer
unfold simple_graph_is_hop infer_instance
Hmul automation
decide
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
Hinv automation
decide
have Hinv : ∀ x : Equiv.Perm (Fin 3), (x = 1 ∨ simple_graph_is_hop ⊤ x) → (x⁻¹ = 1 ∨ simple_graph_is_hop ⊤ (x⁻¹)) := by decide
induction
closure induction
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
cases
word length
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
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.
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⟩