simple_graph_normalized_hop_group_le
For a fixed baseline hop, its normalized subgroup is contained in the original leap group.
Statement
theorem simple_graph_normalized_hop_group_le {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : simple_graph_normalized_hop_group G h₀ ≤ simple_graph_leap_group G
- Source
- Uniform structural helper for IN-262 / OP-543, using the hop and leap-group definitions of arXiv:2610.18463. The universal quadratic word bound is a question proposed here, not a theorem of that paper. No diameter estimate or research advance is claimed by this algebraic normalization.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_normalized_hop_groupThe subgroup generated by permutations allowed relative to a fixed baseline hop.
- 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.
- simple_graph_is_hop_invThe inverse of a hop is a hop (the graph is undirected).
- simple_graph_normalized_hopA permutation p is allowed relative to baseline h0 when h0*p is an actual hop. Relative p may fix vertices; the resulting actual hop still…
The proof, explained
To show that the normalized hop group generated by {p | h₀ * p is a hop} is contained in the leap group generated by all hops, it suffices to show that every generating permutation p belongs to the leap group. Since h₀ is a hop, its inverse h₀⁻¹ is also a hop, and thus both h₀⁻¹ and h₀ * p belong to the leap group. The claim follows because the leap group is closed under multiplication, so it contains the product h₀⁻¹ * (h₀ * p) = p.
It suffices to show that every generator of the normalized hop group belongs to the leap group.
We unfold the definition of simple_graph_normalized_hop_group, which is the subgroup closure of the normalized hops {p | h₀ * p is a hop}, and rewrite with Subgroup.closure_le to reduce the subgroup inclusion to proving that every generator p belongs to the leap group. We then fix an arbitrary permutation p and assume h₀ * p is a hop (hypothesis hp).
uses
simple_graph_normalized_hop_group,Subgroup.closure_lerw [simple_graph_normalized_hop_group, Subgroup.closure_le] intro p hp
Both h₀⁻¹ and h₀ * p belong to the leap group of G.
Since h₀ is a hop by assumption, its inverse h₀⁻¹ is also a hop by simple_graph_is_hop_inv, and therefore belongs to the leap group because any generator belongs to its subgroup closure (Subgroup.subset_closure). Similarly, by the assumption hp that p is a normalized hop, h₀ * p is a hop, so it also belongs to the leap group by Subgroup.subset_closure.
uses
Subgroup.subset_closure,simple_graph_is_hop_invhave ha : h₀⁻¹ ∈ simple_graph_leap_group G := Subgroup.subset_closure (simple_graph_is_hop_inv G h₀ hh₀) have hb : h₀*p ∈ simple_graph_leap_group G := Subgroup.subset_closure hp
The permutation p belongs to the leap group of G, completing the proof.
Because the leap group is a subgroup, it contains the product h₀⁻¹ * (h₀ * p) by closure under multiplication (mul_mem). Using associativity (mul_assoc) and group inverse cancellation, h₀⁻¹ * (h₀ * p) simplifies to p, proving that p belongs to the leap group.
uses
mul_assoc,mul_memsimpa [mul_assoc] using (simple_graph_leap_group G).mul_mem ha hb
simple_graph_normalized_hop_group- The definition of the normalized hop group with respect to a base hop h₀, defined as the subgroup generated by all permutations p such that h₀ * p is a hop.
Subgroup.closure_le- A subgroup closure ⟨k⟩ is contained in a subgroup K if and only if the generating set k is a subset of K.
Subgroup.subset_closure- Every element of a generating set k is contained in the subgroup closure ⟨k⟩.
simple_graph_is_hop_inv- If a permutation h is a hop on a simple graph G, then its inverse h⁻¹ is also a hop on G.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_mem- If two elements belong to a subgroup (or any set closed under multiplication), their product also belongs to it.
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.
theorem simple_graph_normalized_hop_group_le {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : simple_graph_normalized_hop_group G h₀ ≤ simple_graph_leap_group G := by rw [simple_graph_normalized_hop_group, Subgroup.closure_le] intro p hp have ha : h₀⁻¹ ∈ simple_graph_leap_group G := Subgroup.subset_closure (simple_graph_is_hop_inv G h₀ hh₀) have hb : h₀*p ∈ simple_graph_leap_group G := Subgroup.subset_closure hp simpa [mul_assoc] using (simple_graph_leap_group G).mul_mem ha hb