AFTD Auto-Formalizing Theoretical Domains

cycle_power_class_label_period_of_bounded_endpoint_overlap

theoremverified

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
Used by 1

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.

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

    lines 15–17

    uses cycle_power_class_label_period_of_endpoint_overlap

      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
  2. 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.

    lines 18–20

    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⟩
  3. 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.

    lines 21–29

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

    lines 30–32

      · intro p
        rintro ⟨a, ha, he, hx⟩
        omega
  5. 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.

    lines 33–42

      · 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
  6. 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.

    lines 43–47

        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

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