cycle_power_full_class_internal_exact_pair_impossible
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
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- Used by 1
- cycle_power_dyadic_two_full_roots_pair_crossesBetween full classes rooted at zero and g with g at most the dyadic radius, every selected dyadic pair of an interior root has its lower…
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$.
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`).
uses
Int.toNat_of_nonneglet b := (p+(a : ℤ)-q).toNat have hbcast : (b : ℤ) = p+(a : ℤ)-q := Int.toNat_of_nonneg (by omega)
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$.
uses
Nat.cast_sub,Nat.cast_addhave 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
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$.
have hp : p+(a : ℤ)-(a : ℤ) = p := by omega have hq : p+(a : ℤ)-(b : ℤ) = q := by omega
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$.
uses
cycle_power_exact_pair_uniquehave 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)
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.
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.
- On paper, casting natural subtraction $a + D - R$ to integers (lines 14–16) is trivial because $R \le D \le a + D$, but in Lean it requires explicit rewrite lemmas (`Nat.cast_sub` and `Nat.cast_add`) before `omega` can work with it.
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 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