AFTD Auto-Formalizing Theoretical Domains

cycle_power_class_overlap_two_steps

theoremverified

At every radius at least four, an old class containing its first neighbour intersects the class two starts later, at the new root or at the old endpoint, provided the distance-D-2 exact balance and distance-D-3 coverage hold.

Statement

theorem cycle_power_class_overlap_two_steps
    (D : ℕ) (hD : 4 ≤ D) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (x v (D - 2)).toNat + (x (v - 1) 1).toNat = 1)
    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 3 ∧ x (v - (a : ℤ)) a = true ∧
      x (v - (a : ℤ)) (a + D - 3) = true) :
    ∀ p : ℤ, x p 1 = true → x p 2 = true ∨ x (p + 2) (D - 3) = true
Source
Uniform local base case for the endpoint-overlap route of OP-205 / RT-1, arXiv:2610.15635. This is an elementary consequence of the tight-model conditions, not a research advance.
Verified
27 Oct 2026
Axioms
Quot.soundpropext

The proof, explained

We fix a vertex $p$ with $x(p, 1) = \text{true}$ and apply the coverage hypothesis at $p + 2$, obtaining an offset $a \in \{0, 1, 2\}$ whose endpoints are both true. When $a = 0$, the upper endpoint simplifies to $x(p + 2, D - 3) = \text{true}$, satisfying the right disjunct. When $a = 2$, the lower endpoint simplifies to $x(p, 2) = \text{true}$, satisfying the left disjunct. The intermediate case $a = 1$ is ruled out because it forces both $x(p + 1, D - 2)$ and $x(p, 1)$ to be true, contradicting the exact balance condition at $p + 1$.

  1. Given a vertex $p$ with $x(p, 1) = \text{true}$, coverage at $p + 2$ provides an offset $a \in \{0, 1, 2\}$ such that both $x(p + 2 - a, a) = \text{true}$ and $x(p + 2 - a, a + D - 3) = \text{true}$, reducing the proof to these three cases.

    We fix a vertex $p$ and assume $x(p, 1) = \text{true}$. Applying the coverage hypothesis `hcover` at $p + 2$ yields a natural number $a < 3$ satisfying both coverage conditions $x(p + 2 - a, a) = \text{true}$ and $x(p + 2 - a, a + D - 3) = \text{true}$. The tactic `interval_cases` splits $a < 3$ into the three cases $a = 0$, $a = 1$, and $a = 2$.

    lines 7–9

      intro p hp
      rcases hcover (p + 2) with ⟨a, ha, h1, h2⟩
      interval_cases a
  2. In the case $a = 0$, the second disjunct holds: $x(p + 2, D - 3) = \text{true}$.

    We select the right disjunct $x(p + 2, D - 3) = \text{true}$. For $a = 0$, the second coverage condition states that $x(p + 2 - 0, 0 + D - 3) = \text{true}$. Elementary arithmetic ($p + 2 - 0 = p + 2$ and $0 + D - 3 = D - 3$) rewrites this hypothesis to $x(p + 2, D - 3) = \text{true}$, which closes this case.

    lines 10–15

      · right
        have : (p + 2 - (0 : ℤ)) = p + 2 := by ring
        have hD' : 0 + D - 3 = D - 3 := by omega
        change x (p + 2 - 0) (0 + D - 3) = true at h2
        rw [this, hD'] at h2
        exact h2
  3. The case $a = 1$ is impossible because it violates the exact balance condition.

    When $a = 1$, the second coverage condition gives $x(p + 2 - 1, 1 + D - 3) = \text{true}$. Since $p + 2 - 1 = p + 1$ and $1 + D - 3 = D - 2$ (using $D \ge 4$), this means $x(p + 1, D - 2) = \text{true}$. However, the exact balance hypothesis `hexact` at $v = p + 1$ requires the boolean values $x(p + 1, D - 2)$ and $x(p + 1 - 1, 1) = x(p, 1)$ to sum to $1$ when converted to natural numbers. Since both values are true, this forces $1 + 1 = 1$, a contradiction derived by `decide`.

    lines 16–25

      · exfalso
        have hidx : p + 2 - (1 : ℤ) = p + 1 := by ring
        have hD' : 1 + D - 3 = D - 2 := by omega
        change x (p + 2 - 1) (1 + D - 3) = true at h2
        rw [hidx, hD'] at h2
        have hex := hexact (p + 1)
        have hidx2 : p + 1 - 1 = p := by ring
        rw [hidx2, hp, h2] at hex
        revert hex
        decide
  4. In the case $a = 2$, the first disjunct holds: $x(p, 2) = \text{true}$.

    We select the left disjunct $x(p, 2) = \text{true}$. For $a = 2$, the first coverage condition is $x(p + 2 - 2, 2) = \text{true}$. Because $p + 2 - 2 = p$, this simplifies directly to $x(p, 2) = \text{true}$, completing the proof.

    lines 26–30

      · left
        have : p + 2 - (2 : ℤ) = p := by ring
        change x (p + 2 - 2) 2 = true at h1
        rw [this] at h1
        exact 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

theorem cycle_power_class_overlap_two_steps    (D : ℕ) (hD : 4 ≤ D) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (x v (D - 2)).toNat + (x (v - 1) 1).toNat = 1)    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 3 ∧ x (v - (a : ℤ)) a = true ∧      x (v - (a : ℤ)) (a + D - 3) = true) :    ∀ p : ℤ, x p 1 = true → x p 2 = true ∨ x (p + 2) (D - 3) = true := by  intro p hp  rcases hcover (p + 2) with ⟨a, ha, h1, h2⟩  interval_cases a  · right    have : (p + 2 - (0 : ℤ)) = p + 2 := by ring    have hD' : 0 + D - 3 = D - 3 := by omega    change x (p + 2 - 0) (0 + D - 3) = true at h2    rw [this, hD'] at h2    exact h2  · exfalso    have hidx : p + 2 - (1 : ℤ) = p + 1 := by ring    have hD' : 1 + D - 3 = D - 2 := by omega    change x (p + 2 - 1) (1 + D - 3) = true at h2    rw [hidx, hD'] at h2    have hex := hexact (p + 1)    have hidx2 : p + 1 - 1 = p := by ring    rw [hidx2, hp, h2] at hex    revert hex    decide  · left    have : p + 2 - (2 : ℤ) = p := by ring    change x (p + 2 - 2) 2 = true at h1    rw [this] at h1    exact h1
See it in the graphDiscuss this resultChallenge it