AFTD Auto-Formalizing Theoretical Domains

cycle_power_class_label_period_of_endpoint_overlap

theoremverified

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

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.

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

    lines 11–12

      intro p
      obtain ⟨q, hq, hσ⟩ := hslots (p + D - 1) (σ (p + D))
  2. 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.

    lines 13–15

      by_cases hqp : q = p
      · subst q
        exact hσ.symm
  3. 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`.

    lines 16–19

    uses False.elim

      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)
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

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