AFTD Auto-Formalizing Theoretical Domains

cycle_power_full_class_internal_exact_pair_impossible

theoremverified

In an integer rooted-class system with exact distance D-R edge ownership, a selected distance D-R pair in one root cannot lie wholly in a distinct full radius-D class.

Statement

theorem cycle_power_full_class_internal_exact_pair_impossible
    (D R : ℕ) (hRD : R ≤ D) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (range R).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1)
    (p q : ℤ) (hpq : p ≠ q) (hfull : ∀ i < D, x q i = true)
    (a : ℕ) (ha : a < R) (h₀ : x p a = true) (h₁ : x p (a+D-R) = true)
    (hlo : q ≤ p+(a : ℤ)) (hhi : p+((a+D-R : ℕ) : ℤ) < q+(D : ℤ)) : False
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof considers the vertex $v = p + a$. By hypothesis, the root $p$ witnesses that $a < R$ satisfies the distance $D-R$ pair condition at $v$. Because the pair lies strictly inside the full radius-$D$ window around root $q$, the relative offset $b = p + a - q$ satisfies $b < R$ and $b + D - R < D$, meaning the full class at $q$ also witnesses the pair condition for $b$ at the exact same vertex $v$. By the uniqueness of exact pairs at any vertex (`cycle_power_exact_pair_unique`), we must have $a = b$, which forces $p = q$, contradicting the assumption $p \neq q$.

  1. Define $b = p + a - q$ as a natural number and note that its integer cast equals $p + a - q$.

    Since $q \le p + a$ by hypothesis $hlo$, the integer difference $p + a - q$ is non-negative. Converting it to $\mathbb{N}$ via `.toNat` preserves its value, verified by `Int.toNat_of_nonneg` using linear integer arithmetic (`omega`).

    lines 12–13

    uses Int.toNat_of_nonneg

      let b := (p+(a : ℤ)-q).toNat
      have hbcast : (b : ℤ) = p+(a : ℤ)-q := Int.toNat_of_nonneg (by omega)
  2. The offset $b$ satisfies the bounds $b < R$, $b < D$, and $b + D - R < D$.

    Because $R \le D \le a + D$, the natural subtraction in $a + D - R$ casts faithfully to integer arithmetic using `Nat.cast_sub` and `Nat.cast_add`. Combining this with the upper bound $p + (a + D - R) < q + D$ ($hhi$) and $R \le D$, linear integer arithmetic (`omega`) establishes that $b < R$, which in turn implies $b < D$ and $b + D - R < D$.

    lines 14–19

    uses Nat.cast_sub, Nat.cast_add

      have hRDa : R ≤ a+D := by omega
      have hcast : ((a+D-R : ℕ) : ℤ) = (a : ℤ)+D-R := by
        rw [Nat.cast_sub hRDa, Nat.cast_add]
      have hb : b < R := by omega
      have hbD : b < D := by omega
      have hb1D : b+D-R < D := by omega
  3. The vertex $v = p + a$ can be expressed as $p + a$ and as $q + b$.

    Direct integer arithmetic (`omega`) confirms the identities $(p + a) - a = p$ and $(p + a) - b = q$.

    lines 20–21

      have hp : p+(a : ℤ)-(a : ℤ) = p := by omega
      have hq : p+(a : ℤ)-(b : ℤ) = q := by omega
  4. The indices $a$ and $b$ are equal ($a = b$).

    At the vertex $v = p + a$, both $a$ and $b$ lie in $\{0, \dots, R-1\}$. The root $p$ witnesses that $a$ satisfies the pair condition via hypotheses $h₀$ and $h₁$ (rewriting $v - a = p$). The root $q$ witnesses that $b$ satisfies the pair condition because $b < D$ and $b + D - R < D$, so the fullness hypothesis $hfull$ holds for both offsets (rewriting $v - b = q$). By uniqueness of the exact pair at vertex $v$ (`cycle_power_exact_pair_unique`), it follows that $a = b$.

    lines 22–25

    uses cycle_power_exact_pair_unique

      have he := cycle_power_exact_pair_unique D R x hexact (p+(a : ℤ)) a b ha hb
        (by simpa only [hp] using h₀) (by simpa only [hp] using h₁)
        (by simpa only [hq] using hfull b hbD)
        (by simpa only [hq] using hfull (b+D-R) hb1D)
  5. A contradiction is reached, completing the proof.

    Since $b = p + a - q$ and $a = b$, linear integer arithmetic (`omega`) yields $p = q$. Applying the hypothesis $p \neq q$ ($hpq$) completes the contradiction.

    lines 26–27

      apply hpq
      omega
Int.toNat_of_nonneg
For any non-negative integer $a \ge 0$, converting it to a natural number and casting back to $\mathbb{Z}$ yields $a$.
Nat.cast_sub
For natural numbers $m \le n$, the subtraction $n - m$ cast to an additive group with one (such as $\mathbb{Z}$) equals the difference of their casts $\uparrow n - \uparrow m$.
Nat.cast_add
The cast of the sum of natural numbers $m + n$ to an additive monoid with one equals the sum of their individual casts $\uparrow m + \uparrow n$.
cycle_power_exact_pair_unique
Under the exactness hypothesis that every integer vertex $v$ has a unique index $a < R$ satisfying the distance $D-R$ pair condition, any two such indices $a$ and $b$ for the same vertex $v$ must be equal.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_full_class_internal_exact_pair_impossible    (D R : ℕ) (hRD : R ≤ D) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (range R).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1)    (p q : ℤ) (hpq : p ≠ q) (hfull : ∀ i < D, x q i = true)    (a : ℕ) (ha : a < R) (h₀ : x p a = true) (h₁ : x p (a+D-R) = true)    (hlo : q ≤ p+(a : ℤ)) (hhi : p+((a+D-R : ℕ) : ℤ) < q+(D : ℤ)) : False := by  let b := (p+(a : ℤ)-q).toNat  have hbcast : (b : ℤ) = p+(a : ℤ)-q := Int.toNat_of_nonneg (by omega)  have hRDa : R ≤ a+D := by omega  have hcast : ((a+D-R : ℕ) : ℤ) = (a : ℤ)+D-R := by    rw [Nat.cast_sub hRDa, Nat.cast_add]  have hb : b < R := by omega  have hbD : b < D := by omega  have hb1D : b+D-R < D := by omega  have hp : p+(a : ℤ)-(a : ℤ) = p := by omega  have hq : p+(a : ℤ)-(b : ℤ) = q := by omega  have he := cycle_power_exact_pair_unique D R x hexact (p+(a : ℤ)) a b ha hb    (by simpa only [hp] using h₀) (by simpa only [hp] using h₁)    (by simpa only [hq] using hfull b hbD)    (by simpa only [hq] using hfull (b+D-R) hb1D)  apply hpq  omega
See it in the graphDiscuss this resultChallenge it