AFTD Auto-Formalizing Theoretical Domains

cycle_power_alternating_paired_compression_cover

theoremverified

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

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.

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

    lines 13–14

      intro d hd hdh u
      obtain ⟨a, ha, h0, h1⟩ := hcover (2 * d) (by omega) (by omega) (2 * u + 1)
  2. 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$.

    lines 15–21

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

    lines 22–24

      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, ?_, ?_⟩
  4. 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.

    lines 25–27

      · have hi : 2 * (a / 2) = a := by omega
        rw [hi]
        simpa only [hstart] using h0
  5. 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.

    lines 28–29

      · 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

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