AFTD Auto-Formalizing Theoretical Domains

simple_graph_leap_word_bound_of_normalized

theoremverified

A signed normalized-word diameter bound D implies an actual hop-word diameter bound 2D+1. The normalized diameter bound remains an explicit hypothesis.

Statement

theorem simple_graph_leap_word_bound_of_normalized {V : Type*} (G : SimpleGraph V)
    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (D : ℕ)
    (hD : ∀ k ∈ simple_graph_normalized_hop_group G h₀,
      ∃ w : List (Equiv.Perm V),
        (∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨
          simple_graph_normalized_hop G h₀ p⁻¹) ∧ w.length ≤ D ∧ w.prod = k) :
    ∀ g ∈ simple_graph_leap_group G,
      ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧
        u.length ≤ 2*D+1 ∧ u.prod = g
Source
Routine word-metric/cycle-factor assembly for IN-262 / OP-543, using the verified baseline normalization. The remaining quadratic diameter theorem is conjectural; no diameter assumption is silently discharged and no research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

The proof shows that any element g of the leap group has hop word length at most 2D + 1 by coset decomposition with respect to a base hop h₀. By simple_graph_leap_group_normalized_cosets, either g or h₀⁻¹ * g lies in the normalized hop group. In either case, the normalized element is expressed as a normalized word of length at most D, which expands into a hop word of length at most 2D; in the second coset, prepending h₀ yields a hop word of length at most 2D + 1 representing g.

  1. The leap group element g is split into cosets: either g or h₀⁻¹ * g belongs to the normalized hop group.

    Let g be an arbitrary element of the leap group. By simple_graph_leap_group_normalized_cosets, the leap group is partitioned into two cosets relative to the normalized hop group: either g is itself in the normalized hop group, or h₀⁻¹ * g is.

    lines 10–11

    uses simple_graph_leap_group_normalized_cosets

      intro g hg
      rcases simple_graph_leap_group_normalized_cosets G h₀ hh₀ g hg with h1 | h2
  2. If g is in the normalized hop group, it can be written as a hop word of length at most 2D ≤ 2D + 1.

    By the normalized diameter bound hD, g is the product of a word w of at most D normalized hops or inverses. By simple_graph_normalized_word_to_hop_word, w converts into a list u of actual hops with length 2 * length w and prod u = prod w = g. Since length w ≤ D, linear arithmetic establishes that length u ≤ 2D ≤ 2D + 1.

    lines 12–15

    uses simple_graph_normalized_word_to_hop_word

      · obtain ⟨w, hw, hlen, hprod⟩ := hD g h1
        obtain ⟨u, hu, hulen, huprod⟩ := simple_graph_normalized_word_to_hop_word G h₀ hh₀ w hw
        refine ⟨u, hu, ?_, by rw [huprod, hprod]⟩
        omega
  3. If h₀⁻¹ * g is in the normalized hop group, construct a candidate hop word for g by prepending h₀ to a hop word for h₀⁻¹ * g.

    Applying hypothesis hD to h₀⁻¹ * g yields a normalized word w of length at most D. Applying simple_graph_normalized_word_to_hop_word converts w into a hop word u of length 2 * length w with prod u = h₀⁻¹ * g. Prepending h₀ gives the candidate word h₀ :: u for g.

    lines 16–18

    uses simple_graph_normalized_word_to_hop_word

      · obtain ⟨w, hw, hlen, hprod⟩ := hD (h₀⁻¹ * g) h2
        obtain ⟨u, hu, hulen, huprod⟩ := simple_graph_normalized_word_to_hop_word G h₀ hh₀ w hw
        refine ⟨h₀ :: u, ?_, ?_, ?_⟩
  4. Every letter in the candidate list h₀ :: u is a hop.

    For any element h of h₀ :: u, List.mem_cons.mp breaks into cases: either h = h₀, which is a hop by assumption hh₀, or h ∈ u, which is a hop by the properties of u.

    lines 19–22

    uses List.mem_cons.mp

        · intro h hh
          rcases List.mem_cons.mp hh with rfl | hh
          · exact hh₀
          · exact hu h hh
  5. The length of h₀ :: u is at most 2D + 1.

    By List.length_cons, the length of h₀ :: u is length u + 1 = 2 * length w + 1. Since length w ≤ D, linear arithmetic verifies that 2 * length w + 1 ≤ 2D + 1.

    lines 23–24

    uses List.length_cons

        · simp only [List.length_cons]
          omega
  6. The product of h₀ :: u equals g.

    By List.prod_cons, prod (h₀ :: u) = h₀ * prod u. Since prod u = h₀⁻¹ * g, this evaluates to h₀ * (h₀⁻¹ * g) = g by mul_inv_cancel_left.

    line 25

    uses List.prod_cons, mul_inv_cancel_left

        · simp only [List.prod_cons, huprod, hprod, mul_inv_cancel_left]
simple_graph_leap_group_normalized_cosets
For any base hop h₀, every element g of the leap group belongs either to the normalized hop group or to its coset h₀ * (normalized hop group), meaning h₀⁻¹ * g is in the normalized hop group.
simple_graph_normalized_word_to_hop_word
Any word w whose letters are normalized hops (or their inverses) can be expanded into a list of actual hops u having twice the length (length u = 2 * length w) and the same product (prod u = prod w).
List.mem_cons.mp
An element x belongs to the list a :: as if and only if x = a or x belongs to as.
List.length_cons
The length of a prepended list a :: as is length as + 1.
List.prod_cons
The product of a prepended list a :: l is a * prod l.
mul_inv_cancel_left
In any group, a * (a⁻¹ * b) = b.

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_leap_word_bound_of_normalized {V : Type*} (G : SimpleGraph V)    (h₀ : Equiv.Perm V) (hh₀ : simple_graph_is_hop G h₀) (D : ℕ)    (hD : ∀ k ∈ simple_graph_normalized_hop_group G h₀,      ∃ w : List (Equiv.Perm V),        (∀ p ∈ w, simple_graph_normalized_hop G h₀ p ∨          simple_graph_normalized_hop G h₀ p⁻¹) ∧ w.length ≤ D ∧ w.prod = k) :    ∀ g ∈ simple_graph_leap_group G,      ∃ u : List (Equiv.Perm V), (∀ h ∈ u, simple_graph_is_hop G h) ∧        u.length ≤ 2*D+1 ∧ u.prod = g := by  intro g hg  rcases simple_graph_leap_group_normalized_cosets G h₀ hh₀ g hg with h1 | h2  · obtain ⟨w, hw, hlen, hprod⟩ := hD g h1    obtain ⟨u, hu, hulen, huprod⟩ := simple_graph_normalized_word_to_hop_word G h₀ hh₀ w hw    refine ⟨u, hu, ?_, by rw [huprod, hprod]⟩    omega  · obtain ⟨w, hw, hlen, hprod⟩ := hD (h₀⁻¹ * g) h2    obtain ⟨u, hu, hulen, huprod⟩ := simple_graph_normalized_word_to_hop_word G h₀ hh₀ w hw    refine ⟨h₀ :: u, ?_, ?_, ?_⟩    · intro h hh      rcases List.mem_cons.mp hh with rfl | hh      · exact hh₀      · exact hu h hh    · simp only [List.length_cons]      omega    · simp only [List.prod_cons, huprod, hprod, mul_inv_cancel_left]
See it in the graphDiscuss this resultChallenge it