AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_conjugate_mem

theoremverified

Conjugating one normalized allowed permutation by the baseline yields an element of the normalized SUBGROUP, without claiming it stays in the normalized generating set.

Statement

theorem simple_graph_normalized_hop_conjugate_mem {V : Type*}
    (G : SimpleGraph V) (h₀ p : Equiv.Perm V)
    (hh₀ : simple_graph_is_hop G h₀) (hp : simple_graph_normalized_hop G h₀ p) :
    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 5
Used by 1

The proof, explained

To show that the conjugate h₀ * p * h₀⁻¹ belongs to the normalized hop subgroup K, the proof factors it as q⁻¹ * s, where q = h₀⁻¹ * (h₀ * p)⁻¹ and s = h₀⁻¹ * h₀⁻¹. The factor q belongs to K because h₀ * q = (h₀ * p)⁻¹ is the inverse of a hop and therefore an element of the generating set. Since s also belongs to K by a prior lemma, subgroup closure implies q⁻¹ * s ∈ K, and simplifying q⁻¹ * s yields the desired conjugate h₀ * p * h₀⁻¹.

  1. The element h₀⁻¹ * (h₀ * p)⁻¹ belongs to the normalized hop subgroup K.

    Let K denote simple_graph_normalized_hop_group G h₀, the subgroup generated by permutations x such that h₀ * x is a hop. By Subgroup.subset_closure, to show h₀⁻¹ * (h₀ * p)⁻¹ ∈ K it suffices to show that h₀ * (h₀⁻¹ * (h₀ * p)⁻¹) is a hop. By associativity (mul_assoc), this product simplifies to (h₀ * p)⁻¹. Since h₀ * p is a hop by hypothesis hp, its inverse (h₀ * p)⁻¹ is also a hop by simple_graph_is_hop_inv.

    lines 5–9

    uses Subgroup.subset_closure, mul_assoc, simple_graph_is_hop_inv

      let K := simple_graph_normalized_hop_group G h₀
      have hq : h₀⁻¹*(h₀*p)⁻¹ ∈ K := by
        apply Subgroup.subset_closure
        change simple_graph_is_hop G (h₀*(h₀⁻¹*(h₀*p)⁻¹))
        simpa [mul_assoc] using simple_graph_is_hop_inv G (h₀*p) hp
  2. The square h₀⁻¹ * h₀⁻¹ belongs to K.

    By simple_graph_normalized_hop_group_square_inv, the element h₀⁻¹ * h₀⁻¹ belongs to K because h₀ is a hop (hypothesis hh₀).

    lines 10–11

    uses simple_graph_normalized_hop_group_square_inv

      have hs : h₀⁻¹*h₀⁻¹ ∈ K :=
        simple_graph_normalized_hop_group_square_inv G h₀ hh₀
  3. The conjugate h₀ * p * h₀⁻¹ belongs to K.

    Since K is a subgroup containing q = h₀⁻¹ * (h₀ * p)⁻¹ and s = h₀⁻¹ * h₀⁻¹, it contains q⁻¹ * s. Expanding q⁻¹ * s in group theory gives (h₀⁻¹ * (h₀ * p)⁻¹)⁻¹ * (h₀⁻¹ * h₀⁻¹) = (h₀ * p) * h₀ * h₀⁻¹ * h₀⁻¹ = h₀ * p * h₀⁻¹, which establishes the goal.

    line 12

      convert K.mul_mem (K.inv_mem hq) hs using 1 <;> group
Subgroup.subset_closure
Every element of a generating set is contained in the subgroup it generates.
mul_assoc
Multiplication in a group is associative: (a * b) * c = a * (b * c).
simple_graph_is_hop_inv
If a permutation is a hop on a simple graph (maps every vertex to an adjacent vertex), then its inverse is also a hop.
simple_graph_normalized_hop_group_square_inv
If h₀ is a hop, then the square h₀⁻¹ * h₀⁻¹ belongs to the normalized hop subgroup associated with h₀.

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

theorem simple_graph_normalized_hop_conjugate_mem {V : Type*}    (G : SimpleGraph V) (h₀ p : Equiv.Perm V)    (hh₀ : simple_graph_is_hop G h₀) (hp : simple_graph_normalized_hop G h₀ p) :    h₀*p*h₀⁻¹ ∈ simple_graph_normalized_hop_group G h₀ := by  let K := simple_graph_normalized_hop_group G h₀  have hq : h₀⁻¹*(h₀*p)⁻¹ ∈ K := by    apply Subgroup.subset_closure    change simple_graph_is_hop G (h₀*(h₀⁻¹*(h₀*p)⁻¹))    simpa [mul_assoc] using simple_graph_is_hop_inv G (h₀*p) hp  have hs : h₀⁻¹*h₀⁻¹ ∈ K :=    simple_graph_normalized_hop_group_square_inv G h₀ hh₀  convert K.mul_mem (K.inv_mem hq) hs using 1 <;> group
See it in the graphDiscuss this resultChallenge it