cycle_power_alternating_paired_endpoint_label_period
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.
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).
intro p let w : ℤ := 2 * p + 2 * (h : ℤ) obtain ⟨j, hj, hxj, hσ⟩ := hslots w (σ (2 * p))
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).
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σ
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.
· 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
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.
uses
Or.inrlet 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)
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.
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
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_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