cycle_power_alternating_paired_compression_cover
If all even-start classes are endpoint-only and all original distances less than 2h are covered, the odd-start classes, compressed to their even ages, cover every distance less than h.
Statement
theorem cycle_power_alternating_paired_compression_cover
(h : ℕ) (x : ℤ → ℕ → Bool)
(heven : ∀ p : ℤ, ∀ j < 2 * h,
x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1)
(hcover : ∀ d, 1 ≤ d → d < 2 * h → ∀ u : ℤ,
∃ a < 2 * h - d, x (u - (a : ℤ)) a = true ∧
x (u - (a : ℤ)) (a + d) = true) :
∀ d, 1 ≤ d → d < h → ∀ u : ℤ,
∃ a < h - d, x (2 * (u - (a : ℤ)) + 1) (2 * a) = true ∧
x (2 * (u - (a : ℤ)) + 1) (2 * (a + d)) = true- 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
Quot.soundpropext- Used by 1
- cycle_power_dyadic_no_island_of_alternating_pairedUniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily…
The proof, explained
To show that the odd-start classes, when compressed to even ages, cover every distance $d < h$, we invoke the global coverage assumption at doubled distance $2d$ along the odd diagonal $2u + 1$, yielding an offset $a < 2h - 2d$. A parity argument shows that $a$ must be even: if $a$ were odd, the row index $2u + 1 - a$ would be even, forcing $a \in \{0, 2h - 1\}$ by the endpoint-only assumption on even rows, which contradicts $a$ being odd and strictly less than $2h - 2d$. Halving the offset then yields $a/2 < h - d$, whose even ages $2(a/2) = a$ and $2(a/2 + d) = a + 2d$ directly match the two true entries on the odd-start class.
Given $1 \le d < h$ and $u \in \mathbb{Z}$, there exists an offset $a < 2h - 2d$ covering distance $2d$ along the odd diagonal $2u + 1$.
We introduce the distance $d$, the hypotheses $1 \le d$ and $d < h$, and the diagonal index $u$. Since $1 \le 2d < 2h$ by linear arithmetic, we instantiate the coverage assumption `hcover` with distance $2d$ and index $2u + 1$. This yields an offset $a < 2h - 2d$ such that $x(2u + 1 - a, a) = \text{true}$ and $x(2u + 1 - a, a + 2d) = \text{true}$.
intro d hd hdh u obtain ⟨a, ha, h0, h1⟩ := hcover (2 * d) (by omega) (by omega) (2 * u + 1)
The offset $a$ must be even.
Suppose for contradiction that $a$ is odd, so $a = 2(a / 2) + 1$. Then the row index $2u + 1 - a$ equals $2(u - a/2)$, which is an even integer. Therefore, the hypothesis `heven` applies at age $a < 2h$, implying that $a = 0$ or $a = 2h - 1$. But $a$ cannot be $0$ (since it is odd) and cannot be $2h - 1$ (since $a < 2h - 2d \le 2h - 2$ as $d \ge 1$). This contradiction proves that $a$ is even, so $a \pmod 2 = 0$.
have he : a % 2 = 0 := by by_contra hodd have har : a = 2 * (a / 2) + 1 := by omega have hstart : 2 * u + 1 - (a : ℤ) = 2 * (u - (a / 2 : ℕ)) := by omega rw [hstart] at h0 have hh := (heven _ a (by omega)).mp h0 omega
The candidate witness $a / 2$ satisfies $a / 2 < h - d$.
Because $a$ is even, $a = 2(a / 2)$, and the row index rewrites as $2(u - a/2) + 1$. Dividing the inequality $a < 2h - 2d$ by $2$ gives $a / 2 < h - d$. We provide $a / 2$ as the witness for the existential goal.
have har : a = 2 * (a / 2) := by omega have hstart : 2 * u + 1 - (a : ℤ) = 2 * (u - (a / 2 : ℕ)) + 1 := by omega refine ⟨a / 2, by omega, ?_, ?_⟩
The entry $x(2(u - a/2) + 1, 2(a/2))$ is true.
Since $2(a / 2) = a$ and the row index $2(u - a/2) + 1$ equals $2u + 1 - a$, this entry is identical to $x(2u + 1 - a, a)$, which is known to be true from the coverage hypothesis.
· have hi : 2 * (a / 2) = a := by omega rw [hi] simpa only [hstart] using h0
The entry $x(2(u - a/2) + 1, 2(a/2 + d))$ is true.
Since $2(a / 2 + d) = a + 2d$ and the row index is $2u + 1 - a$, this entry simplifies to $x(2u + 1 - a, a + 2d)$, which is true by the coverage hypothesis, completing the proof.
· have hi : a + 2 * d = 2 * (a / 2 + d) := by omega simpa only [hstart, hi] using h1
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_compression_cover (h : ℕ) (x : ℤ → ℕ → Bool) (heven : ∀ p : ℤ, ∀ j < 2 * h, x (2 * p) j = true ↔ j = 0 ∨ j = 2 * h - 1) (hcover : ∀ d, 1 ≤ d → d < 2 * h → ∀ u : ℤ, ∃ a < 2 * h - d, x (u - (a : ℤ)) a = true ∧ x (u - (a : ℤ)) (a + d) = true) : ∀ d, 1 ≤ d → d < h → ∀ u : ℤ, ∃ a < h - d, x (2 * (u - (a : ℤ)) + 1) (2 * a) = true ∧ x (2 * (u - (a : ℤ)) + 1) (2 * (a + d)) = true := by intro d hd hdh u obtain ⟨a, ha, h0, h1⟩ := hcover (2 * d) (by omega) (by omega) (2 * u + 1) have he : a % 2 = 0 := by by_contra hodd have har : a = 2 * (a / 2) + 1 := by omega have hstart : 2 * u + 1 - (a : ℤ) = 2 * (u - (a / 2 : ℕ)) := by omega rw [hstart] at h0 have hh := (heven _ a (by omega)).mp h0 omega have har : a = 2 * (a / 2) := by omega have hstart : 2 * u + 1 - (a : ℤ) = 2 * (u - (a / 2 : ℕ)) + 1 := by omega refine ⟨a / 2, by omega, ?_, ?_⟩ · have hi : 2 * (a / 2) = a := by omega rw [hi] simpa only [hstart] using h0 · have hi : a + 2 * d = 2 * (a / 2 + d) := by omega simpa only [hstart, hi] using h1