AFTD Auto-Formalizing Theoretical Domains

simple_graph_normalized_hop_group_square_inv

theoremverified

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
Used by 4

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.

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

    lines 4–5

    uses Subgroup.subset_closure

      apply Subgroup.subset_closure
      change simple_graph_is_hop G (h₀*(h₀⁻¹*h₀⁻¹))
  2. 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.

    line 6

    uses mul_assoc, simple_graph_is_hop_inv

      simpa [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

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