simple_graph_leap_word_bound_of_normalized
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
- simple_graph_normalized_hop_groupThe subgroup generated by permutations allowed relative to a fixed baseline hop.
- 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…
- simple_graph_normalized_word_to_hop_wordEvery signed normalized word lifts to an actual hop word with exactly twice its length and the same product.
- 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…
- simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
- 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.
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.
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.
uses
simple_graph_leap_group_normalized_cosetsintro g hg rcases simple_graph_leap_group_normalized_cosets G h₀ hh₀ g hg with h1 | h2
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.
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
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.
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, ?_, ?_, ?_⟩
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.
uses
List.mem_cons.mp· intro h hh rcases List.mem_cons.mp hh with rfl | hh · exact hh₀ · exact hu h hh
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.
uses
List.length_cons· simp only [List.length_cons] omega
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.
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
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_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]