AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_group_conjugate

theoremverified

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

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.

  1. 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.

    line 6

    uses Subgroup.closure_induction

      refine Subgroup.closure_induction ?_ ?_ ?_ ?_ hp
  2. Conjugation 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.

    lines 7–8

    uses simple_graph_normalized_hop_conjugate_mem

      · intro p hp
        exact simple_graph_normalized_hop_conjugate_mem G h₀ p hh₀ hp
  3. 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.

    line 9

      · simp
  4. The 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₀⁻¹.

    lines 10–12

    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
  5. 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₀⁻¹.

    lines 13–15

    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

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
See it in the graphDiscuss this resultChallenge it