cycle_power_class_label_period_of_bounded_endpoint_overlap
For bounded Boolean classes with complete distinct palettes, endpoint overlap forces the root labels to repeat after the class radius.
Statement
theorem cycle_power_class_label_period_of_bounded_endpoint_overlap (D t : ℕ) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin t) (hcount : ∀ v : ℤ, (range D).sum (fun a => (x (v-(a : ℤ)) a).toNat) = t) (hsep : ∀ (v : ℤ) (a b : ℕ), a < D → b < D → a ≠ b → x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true → ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) (hoverlap : ∀ (p : ℤ) (q : ℕ), 1 ≤ q → q < D → x (p+(q : ℤ)) (D-1-q) = true → ∃ a : ℕ, a < q ∧ x (p+(q : ℤ)) (D-q+a) = true ∧ x (p+(D : ℤ)) a = true) : Function.Periodic ell (D : ℤ)
- Source
- Uniform helpers for OP-205 / RT-1 following arXiv:2610.15635, Section 3. The neighbour-weight induction and central occurrence are class-model helpers; they do not prove the unresolved covering number. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_class_palette_of_countExactly t active classes with distinct labels in Fin t use every label at each vertex.
- cycle_power_class_label_period_of_endpoint_overlapIf a shifted class meets every other class through the old endpoint, complete palettes and label separation force the shifted class to…
- Used by 1
- cycle_power_dyadic_model_dvd_of_endpoint_overlapA periodic optimal dyadic class model whose old active classes intersect the next endpoint class has period divisible by the dyadic…
The proof, explained
The proof establishes that the labeling ℓ is periodic with period D by applying the general endpoint overlap criterion, cycle_power_class_label_period_of_endpoint_overlap, to the class support relation S(p, v) : ∃ a < D, v = p + a ∧ x(p, a) = true. Palette completeness is supplied by cycle_power_class_palette_of_count, and label separation follows from the assumption that distinct offsets at the same vertex receive different labels. The boundary point p + D - 1 cannot belong to the class at p + D for parity/sign reasons, and when another root q covers that boundary point, the bounded overlap hypothesis hoverlap provides a shared vertex u = p + D + a witnessing the overlap.
The periodicity of ℓ with period D reduces to four structural conditions on the class membership relation S.
We define the membership relation S(p, v) to mean that vertex v belongs to the class rooted at p, which holds when v = p + a for some offset a < D with x(p, a) = true. Applying cycle_power_class_label_period_of_endpoint_overlap reduces the periodic labeling goal to four conditions: (1) full palette coverage at every vertex, (2) separation of distinct roots covering the same vertex, (3) non-containment of the boundary vertex p + D - 1 in the class rooted at p + D, and (4) that any other class covering p + D - 1 overlaps with the class rooted at p + D.
uses
cycle_power_class_label_period_of_endpoint_overlaplet S : ℤ → ℤ → Prop := fun p v => ∃ a : ℕ, a < D ∧ v = p+(a : ℤ) ∧ x p a = true apply cycle_power_class_label_period_of_endpoint_overlap (D : ℤ) S ell
Every vertex v and palette label s ∈ Fin t are covered by some root p.
Given a vertex v and a target label s, the lemma cycle_power_class_palette_of_count provides an offset a < D such that x(v - a, a) = true and ℓ(v - a) = s. Choosing the root p = v - a, we have v = p + a, so S(p, v) holds and ℓ(p) = s.
uses
cycle_power_class_palette_of_count· intro v s obtain ⟨a, ha, hx, hs⟩ := cycle_power_class_palette_of_count D t x ell hcount hsep v s exact ⟨v-(a : ℤ), ⟨a, ha, by omega, hx⟩, hs⟩
Distinct roots covering the same vertex cannot share the same label.
Suppose roots p and q both cover vertex v with ℓ(p) = ℓ(q). By definition of S, there are offsets a, b < D such that v = p + a and v = q + b, so p = v - a and q = v - b. If a = b, then p = q. If a ≠ b, the separation hypothesis hsep gives ℓ(v - a) ≠ ℓ(v - b), which contradicts ℓ(p) = ℓ(q). The impossible branch is dismissed using False.elim.
uses
False.elim· intro p q v hp hq he obtain ⟨a, ha, hva, hxa⟩ := hp obtain ⟨b, hb, hvb, hxb⟩ := hq have hpa : p = v-(a : ℤ) := by omega have hqb : q = v-(b : ℤ) := by omega by_cases hab : a=b · subst b; omega subst p q exact False.elim (hsep v a b ha hb hab hxa hxb he)
A root at p + D never covers the boundary vertex p + D - 1.
Suppose for contradiction that S(p + D, p + D - 1) holds. By definition of S, there is an offset a ∈ ℕ with p + D - 1 = (p + D) + a, which simplifies to a = -1, an impossibility for a natural number. Linear arithmetic (omega) closes this goal.
· intro p rintro ⟨a, ha, he, hx⟩ omega
An active offset a < r exists for p + D and q, where r = D - 1 - b.
Given q ≠ p with S(q, p + D - 1), we obtain an offset b < D such that p + D - 1 = q + b and x(q, b) = true. Setting r = D - 1 - b, arithmetic shows 1 ≤ r < D, q = p + r, and D - 1 - r = b, so x(p + r, D - 1 - r) = true. The bounded overlap hypothesis hoverlap applied to p and r yields an offset a < r such that x(p + r, D - r + a) = true and x(p + D, a) = true.
· intro p q hne hq obtain ⟨b, hb, hvb, hxb⟩ := hq let r := D-1-b have hD : 0 < D := by omega have hr0 : 1 ≤ r := by dsimp [r]; omega have hrD : r < D := by dsimp [r]; omega have hqr : q=p+(r : ℤ) := by dsimp [r]; omega have hage : D-1-r=b := by dsimp [r]; omega have hx : x (p+(r : ℤ)) (D-1-r) = true := by rw [← hqr, hage]; exact hxb obtain ⟨a, ha, hxa, hxnew⟩ := hoverlap p r hr0 hrD hx
The vertex u = p + D + a is covered by both q and p + D, witnessing the class overlap.
We choose the intersection witness u = p + D + a. For the root q = p + r, the offset D - r + a is strictly less than D (since a < r) and satisfies q + (D - r + a) = u with x(q, D - r + a) = true. For the root p + D, the offset a satisfies a < D, (p + D) + a = u, and x(p + D, a) = true.
refine ⟨p+(D : ℤ)+(a : ℤ), ?_, ?_⟩ · refine ⟨D-r+a, by omega, ?_, ?_⟩ · dsimp [r] at *; omega · simpa only [hqr] using hxa · exact ⟨a, by omega, by omega, hxnew⟩
cycle_power_class_label_period_of_endpoint_overlap- If a relation S on ℤ satisfies slot coverage, label separation on shared vertices, boundary non-containment ¬S (p + D) (p + D - 1), and endpoint overlap whenever another root covers p + D - 1, then the labeling function is periodic with period D.
cycle_power_class_palette_of_count- Under the offset count and separation hypotheses, every vertex sees every label in Fin t at some active offset in range D.
False.elim- From False, any proposition follows (ex falso quodlibet).
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_bounded_endpoint_overlap (D t : ℕ) (x : ℤ → ℕ → Bool) (ell : ℤ → Fin t) (hcount : ∀ v : ℤ, (range D).sum (fun a => (x (v-(a : ℤ)) a).toNat) = t) (hsep : ∀ (v : ℤ) (a b : ℕ), a < D → b < D → a ≠ b → x (v-(a : ℤ)) a = true → x (v-(b : ℤ)) b = true → ell (v-(a : ℤ)) ≠ ell (v-(b : ℤ))) (hoverlap : ∀ (p : ℤ) (q : ℕ), 1 ≤ q → q < D → x (p+(q : ℤ)) (D-1-q) = true → ∃ a : ℕ, a < q ∧ x (p+(q : ℤ)) (D-q+a) = true ∧ x (p+(D : ℤ)) a = true) : Function.Periodic ell (D : ℤ) := by let S : ℤ → ℤ → Prop := fun p v => ∃ a : ℕ, a < D ∧ v = p+(a : ℤ) ∧ x p a = true apply cycle_power_class_label_period_of_endpoint_overlap (D : ℤ) S ell · intro v s obtain ⟨a, ha, hx, hs⟩ := cycle_power_class_palette_of_count D t x ell hcount hsep v s exact ⟨v-(a : ℤ), ⟨a, ha, by omega, hx⟩, hs⟩ · intro p q v hp hq he obtain ⟨a, ha, hva, hxa⟩ := hp obtain ⟨b, hb, hvb, hxb⟩ := hq have hpa : p = v-(a : ℤ) := by omega have hqb : q = v-(b : ℤ) := by omega by_cases hab : a=b · subst b; omega subst p q exact False.elim (hsep v a b ha hb hab hxa hxb he) · intro p rintro ⟨a, ha, he, hx⟩ omega · intro p q hne hq obtain ⟨b, hb, hvb, hxb⟩ := hq let r := D-1-b have hD : 0 < D := by omega have hr0 : 1 ≤ r := by dsimp [r]; omega have hrD : r < D := by dsimp [r]; omega have hqr : q=p+(r : ℤ) := by dsimp [r]; omega have hage : D-1-r=b := by dsimp [r]; omega have hx : x (p+(r : ℤ)) (D-1-r) = true := by rw [← hqr, hage]; exact hxb obtain ⟨a, ha, hxa, hxnew⟩ := hoverlap p r hr0 hrD hx refine ⟨p+(D : ℤ)+(a : ℤ), ?_, ?_⟩ · refine ⟨D-r+a, by omega, ?_, ?_⟩ · dsimp [r] at *; omega · simpa only [hqr] using hxa · exact ⟨a, by omega, by omega, hxnew⟩