simple_graph_normalized_hop_group_conjugate
Conjugation by the baseline preserves the normalized subgroup.
Statement
theorem simple_graph_normalized_hop_group_conjugate {V : Type*} (G : SimpleGraph V) (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : p ∈ simple_graph_normalized_hop_group G h₀) : h₀*p*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_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_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_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 2
- simple_graph_normalized_hop_group_conjugate_invConjugation by the inverse baseline also preserves 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 normalized hops. By subgroup closure induction, showing that conjugation by the baseline h₀ preserves the subgroup reduces to checking generators, the identity, products, and inverses. The generator case is established by `simple_graph_normalized_hop_conjugate_mem`, while the identity, product, and inverse cases follow from subgroup axioms and standard group identities.
By induction on subgroup generation, it suffices to verify that conjugation by h₀ preserves generators, the identity, products, and inverses.
The normalized hop group is defined as the subgroup closure of the normalized hops. Applying `Subgroup.closure_induction` to the hypothesis hp reduces the goal to four cases: generators, identity, products, and inverses.
uses
Subgroup.closure_inductionrefine Subgroup.closure_induction ?_ ?_ ?_ ?_ hpConjugation of any generating normalized hop by h₀ belongs to the normalized hop group.
Assuming p is in the generating set of normalized hops, the lemma `simple_graph_normalized_hop_conjugate_mem` directly proves that h₀ * p * h₀⁻¹ belongs to the normalized hop group.
uses
simple_graph_normalized_hop_conjugate_mem· intro p hp exact simple_graph_normalized_hop_conjugate_mem G h₀ p hh₀ hp
Conjugation of the identity by h₀ belongs to the normalized hop group.
The conjugate h₀ * 1 * h₀⁻¹ simplifies directly to 1, which belongs to any subgroup.
· simpThe conjugation property is preserved under products.
Assuming the induction hypotheses that h₀ * x * h₀⁻¹ and h₀ * y * h₀⁻¹ belong to the subgroup, their product (h₀ * x * h₀⁻¹) * (h₀ * y * h₀⁻¹) also belongs to the subgroup by closure under multiplication (`mul_mem`). By group simplification, this product equals h₀ * (x * y) * h₀⁻¹.
uses
mul_mem· intro x y hx hy hcx hcy have hh := (simple_graph_normalized_hop_group G h₀).mul_mem hcx hcy convert hh using 1 <;> group
The conjugation property is preserved under inverses.
Assuming the induction hypothesis that h₀ * x * h₀⁻¹ belongs to the subgroup, its inverse (h₀ * x * h₀⁻¹)⁻¹ also belongs to the subgroup by closure under inverses (`inv_mem`). By group simplification, this inverse equals h₀ * x⁻¹ * h₀⁻¹.
uses
inv_mem· intro x hx hcx have hh := (simple_graph_normalized_hop_group G h₀).inv_mem hcx convert hh using 1 <;> group
Subgroup.closure_induction- If a property holds for all generators in k, holds for the identity 1, and is preserved under multiplication and inverses, then it holds for all elements of the subgroup closure ⟨k⟩.
simple_graph_normalized_hop_conjugate_mem- If h₀ is a hop of G and p is a normalized hop with respect to h₀, then the conjugate h₀*p*h₀⁻¹ belongs to the normalized hop group.
mul_mem- A subgroup is closed under multiplication: if a ∈ s and b ∈ s, then a * b ∈ s.
inv_mem- A subgroup is closed under inversion: if x ∈ s, then x⁻¹ ∈ s.
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_conjugate {V : Type*} (G : SimpleGraph V) (h₀ p : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (hp : p ∈ simple_graph_normalized_hop_group G h₀) : h₀*p*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀ := by refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hp · intro p hp exact simple_graph_normalized_hop_conjugate_mem G h₀ p hh₀ hp · simp · intro x y hx hy hcx hcy have hh := (simple_graph_normalized_hop_group G h₀).mul_mem hcx hcy convert hh using 1 <;> group · intro x hx hcx have hh := (simple_graph_normalized_hop_group G h₀).inv_mem hcx convert hh using 1 <;> group