AFTD Auto-Formalizing Theoretical Domains

cycle_power_alternating_paired_endpoint_label_period

theoremverified

For classes on the integer line of any positive even arc length 2h, assume even-start classes contain exactly their two endpoints, odd-start classes have equal consecutive bits, every label occurs in a class at each vertex, and classes with the same label cannot overlap. Then each even-start label repeats after 2h. The label type is arbitrary.

Statement

theorem cycle_power_alternating_paired_endpoint_label_period
    {α : Type*} (h : ℕ) (hh : 0 < h)
    (x : ℤ → ℕ → Bool) (σ : ℤ → α)
    (heven : ∀ p : ℤ, ∀ j < 2 * h,
      x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1)
    (hpair : ∀ p : ℤ, ∀ j < h,
      x (2 * p + 1) (2 * j) = x (2 * p + 1) (2 * j + 1))
    (hslots : ∀ (v : ℤ) (a : α), ∃ j < 2 * h,
      x (v - (j : ℤ)) j = true ∧ σ (v - (j : ℤ)) = a)
    (hsep : ∀ (v : ℤ) (j k : ℕ), j < 2 * h → k < 2 * h →
      x (v - (j : ℤ)) j = true → x (v - (k : ℤ)) k = true →
      σ (v - (j : ℤ)) = σ (v - (k : ℤ)) → j = k) :
    ∀ p : ℤ, σ (2 * p + 2 * (h : ℤ)) = σ (2 * p)
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635, Section 3. These conditional class-system and pruning lemmas do not establish the unresolved graph covering bound. The earlier fixed-radius helpers handle radii eight and sixteen; this session works with arbitrary dyadic radii. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that the label of an even-start class repeats after 2h, we look at the vertex w = 2p + 2h, where the label σ(2p) must appear in some active class starting at w - j with offset j < 2h. If j is even, the start point w - j is even, so the two-endpoint condition forces j = 0, directly giving σ(2p + 2h) = σ(2p). If j is odd, the paired-bit condition on odd-start classes implies that offset j - 1 is also active in that class. Shifting attention to the vertex v = w - 1, both this class and the class starting at 2p contain v with the same label σ(2p), so the non-overlap hypothesis forces j - 1 = 2h - 1, which contradicts j < 2h.

  1. At vertex w = 2p + 2h, there is an active class starting at w - j with offset j < 2h carrying the label σ(2p).

    Fix an integer p and set w = 2p + 2h. By the slot-filling hypothesis (hslots), every label occurs in some active class at every vertex. In particular, the label σ(2p) must appear at vertex w, meaning there is an offset j < 2h such that the class starting at w - j has bit j active (x(w - j, j) = true) and carries label σ(w - j) = σ(2p).

    lines 16–18

      intro p
      let w : ℤ := 2 * p + 2 * (h : ℤ)
      obtain ⟨j, hj, hxj, hσ⟩ := hslots w (σ (2 * p))
  2. When j is even, the label identity σ(2p + 2h) = σ(2p) holds.

    Split into cases on whether j is even or odd. If j is even, the start point w - j = 2(p + h - j/2) is an even integer. By the even-start hypothesis (heven), an active offset in an even-start class must be 0 or 2h - 1. Because j is even while 2h - 1 is odd (since h > 0), j cannot equal 2h - 1, forcing j = 0. Substituting j = 0 into σ(w - j) = σ(2p) immediately yields σ(w) = σ(2p), which is σ(2p + 2h) = σ(2p).

    lines 19–26

      by_cases he : j % 2 = 0
      · have hwj : w - (j : ℤ) = 2 * (p + (h : ℤ) - (j / 2 : ℕ)) := by
          dsimp [w]; omega
        rw [hwj] at hxj
        have hz := (heven _ j hj).mp hxj
        have hjz : j = 0 := by omega
        subst j
        simpa [w] using hσ
  3. When j is odd, the predecessor offset j - 1 in the class starting at w - j is also active.

    When j is odd, write j = 2(j/2) + 1 with j/2 < h. Since w is even and j is odd, the start vertex w - j is odd, of the form 2q + 1 with q = p + h - (j/2) - 1. The pairing hypothesis (hpair) for odd-start classes ensures that bits 2(j/2) and 2(j/2) + 1 take identical values. Since bit j = 2(j/2) + 1 is active, the adjacent bit j - 1 = 2(j/2) must also be active: x(w - j, j - 1) = true.

    lines 27–35

      · have hjodd : j = 2 * (j / 2) + 1 := by omega
        have hr : j / 2 < h := by omega
        let q : ℤ := p + (h : ℤ) - (j / 2 : ℕ) - 1
        have hwj : w - (j : ℤ) = 2 * q + 1 := by
          dsimp [w, q]; omega
        have hjm : j - 1 = 2 * (j / 2) := by omega
        have hprev : x (w - (j : ℤ)) (j - 1) = true := by
          rw [hwj, hjm, hpair q (j / 2) hr]
          simpa [hwj, ← hjodd] using hxj
  4. At vertex v = w - 1, the class starting at 2p is active at offset 2h - 1.

    Consider the predecessor vertex v = w - 1. The class starting at w - j reaches v at offset (w - 1) - (w - j) = j - 1. Meanwhile, the class starting at 2p reaches v at offset (w - 1) - 2p = 2h - 1. Because 2p is an even start and 2h - 1 < 2h, the even-start hypothesis (heven) shows that bit 2h - 1 is active (x(2p, 2h - 1) = true), using Or.inr to select the right endpoint condition.

    lines 36–44

    uses Or.inr

        let v : ℤ := w - 1
        have hstart : v - ((j - 1 : ℕ) : ℤ) = w - (j : ℤ) := by
          dsimp [v]; omega
        have hendstart : v - ((2 * h - 1 : ℕ) : ℤ) = 2 * p := by
          dsimp [v, w]; omega
        have heidx : 2 * h - 1 < 2 * h := by omega
        have hend : x (v - ((2 * h - 1 : ℕ) : ℤ)) (2 * h - 1) = true := by
          rw [hendstart]
          exact (heven p (2 * h - 1) heidx).mpr (Or.inr rfl)
  5. The assumption that j is odd leads to a contradiction, which completes the proof.

    At vertex v = w - 1, both the class starting at w - j (at offset j - 1) and the class starting at 2p (at offset 2h - 1) are active and share the label σ(2p). By the non-overlap hypothesis (hsep), two active classes at the same vertex with identical labels must have identical offsets, so j - 1 = 2h - 1. This implies j = 2h, directly contradicting j < 2h. Linear arithmetic detects this contradiction and closes the remaining goal.

    lines 45–48

        have heq := hsep v (j - 1) (2 * h - 1) (by omega) heidx
          (by simpa only [hstart] using hprev) hend
          (by simpa only [hstart, hendstart] using hσ)
        omega
Or.inr
proves a disjunction a ∨ b from a proof of the right disjunct b

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_alternating_paired_endpoint_label_period    {α : Type*} (h : ℕ) (hh : 0 < h)    (x : ℤ → ℕ → Bool) (σ : ℤ → α)    (heven : ∀ p : ℤ, ∀ j < 2 * h,      x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1)    (hpair : ∀ p : ℤ, ∀ j < h,      x (2 * p + 1) (2 * j) = x (2 * p + 1) (2 * j + 1))    (hslots : ∀ (v : ℤ) (a : α), ∃ j < 2 * h,      x (v - (j : ℤ)) j = true ∧ σ (v - (j : ℤ)) = a)    (hsep : ∀ (v : ℤ) (j k : ℕ), j < 2 * h → k < 2 * h →      x (v - (j : ℤ)) j = true → x (v - (k : ℤ)) k = true →      σ (v - (j : ℤ)) = σ (v - (k : ℤ)) → j = k) :    ∀ p : ℤ, σ (2 * p + 2 * (h : ℤ)) = σ (2 * p) := by  intro p  let w : ℤ := 2 * p + 2 * (h : ℤ)  obtain ⟨j, hj, hxj, hσ⟩ := hslots w (σ (2 * p))  by_cases he : j % 2 = 0  · have hwj : w - (j : ℤ) = 2 * (p + (h : ℤ) - (j / 2 : ℕ)) := by      dsimp [w]; omega    rw [hwj] at hxj    have hz := (heven _ j hj).mp hxj    have hjz : j = 0 := by omega    subst j    simpa [w] using hσ  · have hjodd : j = 2 * (j / 2) + 1 := by omega    have hr : j / 2 < h := by omega    let q : ℤ := p + (h : ℤ) - (j / 2 : ℕ) - 1    have hwj : w - (j : ℤ) = 2 * q + 1 := by      dsimp [w, q]; omega    have hjm : j - 1 = 2 * (j / 2) := by omega    have hprev : x (w - (j : ℤ)) (j - 1) = true := by      rw [hwj, hjm, hpair q (j / 2) hr]      simpa [hwj, ← hjodd] using hxj    let v : ℤ := w - 1    have hstart : v - ((j - 1 : ℕ) : ℤ) = w - (j : ℤ) := by      dsimp [v]; omega    have hendstart : v - ((2 * h - 1 : ℕ) : ℤ) = 2 * p := by      dsimp [v, w]; omega    have heidx : 2 * h - 1 < 2 * h := by omega    have hend : x (v - ((2 * h - 1 : ℕ) : ℤ)) (2 * h - 1) = true := by      rw [hendstart]      exact (heven p (2 * h - 1) heidx).mpr (Or.inr rfl)    have heq := hsep v (j - 1) (2 * h - 1) (by omega) heidx      (by simpa only [hstart] using hprev) hend      (by simpa only [hstart, hendstart] using hσ)    omega
See it in the graphDiscuss this resultChallenge it