cycle_power_aligned_end_blocks_label_period
In an aligned nested end-block family of arbitrary arc length, complete palettes at each vertex and separation of classes sharing a label force label period equal to the arc length.
Statement
theorem cycle_power_aligned_end_blocks_label_period {α : Type*} (D c : ℤ) (w : ℤ → ℤ) (σ : ℤ → α) (hpos : ∀ p, 0 < w p) (hbound : ∀ p, 2 * w p ≤ D) (hdiv : ∀ p, 2 * w p ∣ D) (hchain : ∀ p q, w p = w q ∨ 2 * w p ∣ w q ∨ 2 * w q ∣ w p) (halign : ∀ p, w p ∣ p + c) (hodd : ∀ p, 2 * w p < D → 2 * w p ∣ p + c - w p) (hwperiod : ∀ p, w (p + D) = w p) (hslots : ∀ (v : ℤ) (a : α), ∃ p, cycle_power_end_blocks D (w p) p v ∧ σ p = a) (hsep : ∀ (p q u : ℤ), p ≠ q → cycle_power_end_blocks D (w p) p u → cycle_power_end_blocks D (w q) q u → σ p ≠ σ q) : ∀ p, σ (p + D) = σ p
- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_end_blocksThe union of the first and last a integer positions of a class with origin p and arc length D.
- cycle_power_aligned_end_blocks_endpoint_overlapFor nested aligned end-block widths, every class through the last point of a different old class intersects the translated new class one…
The proof, explained
To prove that the labeling σ has period D (that is, σ(p + D) = σ p for all p), the proof uses the complete palette hypothesis at the boundary vertex p + D - 1 to find a representative q with σ q = σ(p + D). If q = p, the equality is immediate. Otherwise, q cannot equal p + D by the width bounds, and the aligned end-blocks endpoint overlap theorem yields a vertex u where the end-blocks of q and p + D meet, contradicting the hypothesis that different representatives with overlapping end-blocks must carry distinct labels.
Fix an arbitrary point p and find a representative q whose end-blocks cover p + D - 1 and whose label is σ(p + D).
Fix p ∈ ℤ. By the complete palette hypothesis (`hslots`), every vertex v sees every palette label. Applying this to the vertex v = p + D - 1 and the target label a = σ(p + D) yields a representative q such that p + D - 1 lies in the end-blocks of q (with width w q) and σ q = σ(p + D).
intro p obtain ⟨q, hq, hσ⟩ := hslots (p + D - 1) (σ (p + D))
If q = p, then σ(p + D) = σ p directly.
Under the case assumption q = p, substituting p for q into σ q = σ(p + D) immediately gives σ(p + D) = σ p by symmetry.
by_cases hqp : q = p · subst q exact hσ.symm
In the remaining case where q ≠ p, it must also hold that q ≠ p + D.
Suppose for contradiction that q = p + D. Then p + D - 1 would have to belong to the end-blocks of p + D with width w(p + D), which are [p + D, p + D + w(p + D)) and [p + 2D - w(p + D), p + 2D). The first interval is impossible because p + D ≤ p + D - 1 is contradictory, and the second interval is impossible because 2 * w(p + D) ≤ D and 0 < w(p + D) force p + 2D - w(p + D) > p + D - 1. Both arithmetic contradictions are resolved by `omega`.
have hqnew : q ≠ p + D := by intro he subst q have hb := hbound (p + D) have hp := hpos (p + D) unfold cycle_power_end_blocks at hq rcases hq with hq | hq <;> omega
There exists a vertex u belonging simultaneously to the end-blocks of q and to the end-blocks of p + D with width w p.
Because q ≠ p and the end-blocks of q cover p + D - 1, the endpoint overlap theorem (`cycle_power_aligned_end_blocks_endpoint_overlap`) applies with the positivity, bound, divisibility, chain, and parity alignment hypotheses, providing a common vertex u in both cycle_power_end_blocks D (w q) q u and cycle_power_end_blocks D (w p) (p + D) u.
uses
cycle_power_aligned_end_blocks_endpoint_overlapobtain ⟨u, hqu, hnewu⟩ := cycle_power_aligned_end_blocks_endpoint_overlap D (w p) (w q) p q c (hpos p) (hpos q) (hbound p) (hbound q) (hdiv p) (hdiv q) (hchain p q) (halign p) (hodd p) (halign q) (hodd q) hq hqpThe vertex u lies in the end-blocks of p + D with its proper width w(p + D).
By the period-D invariance of the width function (`hwperiod`), w(p + D) = w p. Rewriting w p to w(p + D) shows that u belongs to the end-blocks of p + D of width w(p + D).
have hnew : cycle_power_end_blocks D (w (p + D)) (p + D) u := by rw [hwperiod p] exact hnewu
The separation hypothesis forces a contradiction, completing the proof.
Since q ≠ p + D and their end-blocks both contain u, the separation hypothesis (`hsep`) requires that σ q ≠ σ(p + D). But q was chosen specifically to have σ q = σ(p + D). This contradiction is eliminated using `False.elim` to conclude the goal.
uses
False.elimexact False.elim ((hsep q (p + D) u hqnew hqu hnew) hσ)
cycle_power_aligned_end_blocks_endpoint_overlap- In an aligned end-block system on a cycle of length D satisfying the divisibility, bound, chain, and parity conditions, if q ≠ p and the end-blocks of q contain p + D - 1, then the end-blocks of q (with width w q) and of p + D (with width w p) share at least one vertex u.
False.elim- From False, any proposition follows (principle of explosion / ex falso quodlibet).
- The technical heart of the geometric overlap—showing that covering the boundary point p + D - 1 forces an overlap with the end-blocks of p + D—is encapsulated in the knowledge-base theorem cycle_power_aligned_end_blocks_endpoint_overlap.
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.
open Finsettheorem cycle_power_aligned_end_blocks_label_period {α : Type*} (D c : ℤ) (w : ℤ → ℤ) (σ : ℤ → α) (hpos : ∀ p, 0 < w p) (hbound : ∀ p, 2 * w p ≤ D) (hdiv : ∀ p, 2 * w p ∣ D) (hchain : ∀ p q, w p = w q ∨ 2 * w p ∣ w q ∨ 2 * w q ∣ w p) (halign : ∀ p, w p ∣ p + c) (hodd : ∀ p, 2 * w p < D → 2 * w p ∣ p + c - w p) (hwperiod : ∀ p, w (p + D) = w p) (hslots : ∀ (v : ℤ) (a : α), ∃ p, cycle_power_end_blocks D (w p) p v ∧ σ p = a) (hsep : ∀ (p q u : ℤ), p ≠ q → cycle_power_end_blocks D (w p) p u → cycle_power_end_blocks D (w q) q u → σ p ≠ σ q) : ∀ p, σ (p + D) = σ p := by intro p obtain ⟨q, hq, hσ⟩ := hslots (p + D - 1) (σ (p + D)) by_cases hqp : q = p · subst q exact hσ.symm have hqnew : q ≠ p + D := by intro he subst q have hb := hbound (p + D) have hp := hpos (p + D) unfold cycle_power_end_blocks at hq rcases hq with hq | hq <;> omega obtain ⟨u, hqu, hnewu⟩ := cycle_power_aligned_end_blocks_endpoint_overlap D (w p) (w q) p q c (hpos p) (hpos q) (hbound p) (hbound q) (hdiv p) (hdiv q) (hchain p q) (halign p) (hodd p) (halign q) (hodd q) hq hqp have hnew : cycle_power_end_blocks D (w (p + D)) (p + D) u := by rw [hwperiod p] exact hnewu exact False.elim ((hsep q (p + D) u hqnew hqu hnew) hσ)