simple_graph_normalized_hop_group_square_inv
The inverse square of a baseline hop belongs to the normalized subgroup.
Statement
theorem simple_graph_normalized_hop_group_square_inv {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : h₀⁻¹*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀
- 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 4
- simple_graph_normalized_hop_groupThe subgroup generated by permutations allowed relative to a fixed baseline hop.
- 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…
- Used by 4
- simple_graph_normalized_hop_group_conjugate_invConjugation by the inverse baseline also preserves the normalized subgroup.
- simple_graph_normalized_hop_conjugate_memConjugating one normalized allowed permutation by the baseline yields an element of the normalized SUBGROUP, without claiming it stays in…
- simple_graph_normalized_hop_group_squareThe square of a baseline hop belongs to the normalized subgroup.
- simple_graph_leap_group_normalized_cosetsEvery leap lies in the normalized subgroup or in its left coset by the baseline hop. Together with containment, this gives index at most…
The proof, explained
The normalized hop group is defined as the subgroup generated by permutations p such that h₀ * p is a hop. To show that h₀⁻¹ * h₀⁻¹ belongs to this subgroup, the proof shows it belongs directly to the generating set, which requires h₀ * (h₀⁻¹ * h₀⁻¹) to be a hop. By group cancellation, this product simplifies to h₀⁻¹, which is a hop because the inverse of any hop is a hop.
It suffices to show that h₀ * (h₀⁻¹ * h₀⁻¹) is a hop on G.
The normalized hop group is defined as the subgroup generated by all permutations p for which h₀ * p is a hop. By Subgroup.subset_closure, any element belonging to this generating set is in the subgroup. Specializing to p = h₀⁻¹ * h₀⁻¹ and unfolding the definition of a normalized hop, the goal reduces to showing that h₀ * (h₀⁻¹ * h₀⁻¹) is a hop on G.
uses
Subgroup.subset_closureapply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*h₀⁻¹))
The permutation h₀ * (h₀⁻¹ * h₀⁻¹) is a hop on G, completing the proof.
Using associativity (mul_assoc) and group inverse cancellation, h₀ * (h₀⁻¹ * h₀⁻¹) simplifies to (h₀ * h₀⁻¹) * h₀⁻¹ = h₀⁻¹. By simple_graph_is_hop_inv, the inverse of the hop h₀ is itself a hop, which matches the simplified goal.
uses
mul_assoc,simple_graph_is_hop_invsimpa [mul_assoc] using simple_graph_is_hop_inv G h₀ hh₀
Subgroup.subset_closure- Any subset of a group is contained in the subgroup that it generates.
mul_assoc- Multiplication in a group (or semigroup) is associative: (a * b) * c = a * (b * c).
simple_graph_is_hop_inv- If a permutation h is a hop on a graph G, then its inverse h⁻¹ is also a hop on G.
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_square_inv {V : Type*} (G : SimpleGraph V) (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) : h₀⁻¹*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀ := by apply Subgroup.subset_closure change simple_graph_is_hop G (h₀*(h₀⁻¹*h₀⁻¹)) simpa [mul_assoc] using simple_graph_is_hop_inv G h₀ hh₀