cycle_power_class_label_period_of_endpoint_overlap
If a shifted class meets every other class through the old endpoint, complete palettes and label separation force the shifted class to retain its label.
Statement
theorem cycle_power_class_label_period_of_endpoint_overlap {α : Type*} (D : ℤ) (S : ℤ → ℤ → Prop) (σ : ℤ → α) (hslots : ∀ (v : ℤ) (a : α), ∃ p, S p v ∧ σ p = a) (hsep : ∀ (p q u : ℤ), S p u → S q u → σ p = σ q → p = q) (hbefore : ∀ p, ¬ S (p + D) (p + D - 1)) (hoverlap : ∀ p q, q ≠ p → S q (p + D - 1) → ∃ u, S q u ∧ S (p + D) u) : ∀ 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
- none — Lean reports it depends on no axioms
- Used by 1
- cycle_power_class_label_period_of_bounded_endpoint_overlapFor bounded Boolean classes with complete distinct palettes, endpoint overlap forces the root labels to repeat after the class radius.
The proof, explained
To show that $\sigma(p + D) = \sigma(p)$ for any integer $p$, we evaluate vertex $p + D - 1$ and use palette completeness to find a class $q$ incident to this vertex with label $\sigma(p + D)$. We then distinguish whether $q = p$ or $q \neq p$. If $q = p$, the labels match immediately. If $q \neq p$, the overlap hypothesis ensures that $q$ and $p + D$ meet at some vertex, which by label separation forces $q = p + D$; this implies that $p + D$ contains $p + D - 1$, contradicting the assumption that shifted classes do not extend to that endpoint.
For an arbitrary class $p$, there exists a class $q$ covering vertex $p + D - 1$ with label $\sigma(q) = \sigma(p + D)$.
Fix an arbitrary class $p$. Applying palette completeness (`hslots`) to the vertex $p + D - 1$ and the target label $\sigma(p + D)$ provides a class $q$ that contains $p + D - 1$ and has label $\sigma(q) = \sigma(p + D)$.
intro p obtain ⟨q, hq, hσ⟩ := hslots (p + D - 1) (σ (p + D))
If $q = p$, the required periodicity $\sigma(p + D) = \sigma(p)$ holds.
We split into cases based on whether $q = p$. When $q = p$, substituting $p$ for $q$ into the equality $\sigma(q) = \sigma(p + D)$ gives $\sigma(p) = \sigma(p + D)$, which establishes $\sigma(p + D) = \sigma(p)$ by symmetry.
by_cases hqp : q = p · subst q exact hσ.symm
The case $q \neq p$ is contradictory, completing the proof.
Suppose $q \neq p$. The overlap hypothesis (`hoverlap`) guarantees that $q$ and $p + D$ share some vertex $u$. Since both classes cover $u$ and share the label $\sigma(q) = \sigma(p + D)$, label separation (`hsep`) implies that $q = p + D$. Consequently, $p + D$ covers $p + D - 1$, directly contradicting the assumption `hbefore`. The contradiction concludes this branch via `False.elim`.
uses
False.elimobtain ⟨u, hqu, hnew⟩ := hoverlap p q hqp hq have heq := hsep q (p + D) u hqu hnew hσ rw [heq] at hq exact False.elim (hbefore p hq)
False.elim- From a proof of False, any proposition follows (the principle of explosion).
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_class_label_period_of_endpoint_overlap {α : Type*} (D : ℤ) (S : ℤ → ℤ → Prop) (σ : ℤ → α) (hslots : ∀ (v : ℤ) (a : α), ∃ p, S p v ∧ σ p = a) (hsep : ∀ (p q u : ℤ), S p u → S q u → σ p = σ q → p = q) (hbefore : ∀ p, ¬ S (p + D) (p + D - 1)) (hoverlap : ∀ p q, q ≠ p → S q (p + D - 1) → ∃ u, S q u ∧ S (p + D) u) : ∀ 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 obtain ⟨u, hqu, hnew⟩ := hoverlap p q hqp hq have heq := hsep q (p + D) u hqu hnew hσ rw [heq] at hq exact False.elim (hbefore p hq)