cycle_power_dyadic_two_full_roots_pair_crosses
Between 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 absolute endpoint below g and upper absolute endpoint at least the radius.
Statement
theorem cycle_power_dyadic_two_full_roots_pair_crosses (m : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (g : ℕ) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) (r : ℕ) (hr₀ : 0 < r) (hrg : r < g) (j : ℕ) (hj : j < m) (a : ℕ) (ha : a < 2^j) (h₀ : x (r : ℤ) a = true) (h₁ : x (r : ℤ) (a+2^m-2^j) = true) : r+a < g ∧ 2^m ≤ r+(a+2^m-2^j)
- 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_full_class_internal_exact_pair_impossibleIn 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…
- Used by 2
- cycle_power_dyadic_gap_side_treeBetween two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity:…
- cycle_power_dyadic_two_full_roots_overlap_emptyIn a tight exact dyadic model, an interior class between full roots zero and g, with g at most the radius, cannot select a vertex in the…
The proof, explained
The goal is split into two inequalities: the lower endpoint bound $r + a < g$ and the upper endpoint bound $2^m \le r + (a + 2^m - 2^j)$. Each inequality is established by contradiction using the lemma `cycle_power_full_class_internal_exact_pair_impossible`, which asserts that an exact pair at an interior root $r$ cannot fall entirely within the coordinate interval of a full root. If $r + a \ge g$, the pair is trapped within $[g, g + 2^m)$ of the full root $g$, and if $r + (a + 2^m - 2^j) < 2^m$, it is trapped within $[0, 2^m)$ of the full root $0$; both scenarios are impossible.
The dyadic radius at scale $j$ is bounded by the full radius ($2^j \le 2^m$), and both pair indices $a$ and $a + 2^m - 2^j$ are strictly less than $2^m$.
From the hypothesis $j < m$, monotonicity of exponentiation for base 2 (`Nat.pow_le_pow_right` and `Nat.le_of_lt`) gives $2^j \le 2^m$. Linear arithmetic using $a < 2^j \le 2^m$ then establishes that both $a$ and $a + 2^m - 2^j$ are strictly less than $2^m$.
uses
Nat.pow_le_pow_right,Nat.le_of_lthave hRD : 2^j ≤ 2^m := Nat.pow_le_pow_right (by decide) (Nat.le_of_lt hj) have haD : a < 2^m := by omega have hbD : a+2^m-2^j < 2^m := by omega
The lower absolute endpoint is strictly below $g$, that is, $r + a < g$.
We split the conjunction into its two goals and assume for contradiction that $r + a \ge g$. Under this assumption, the pair's lower endpoint satisfies $g \le r + a$, while its upper endpoint satisfies $r + (a + 2^m - 2^j) < g + 2^m$ (since $r < g$ and $a < 2^j \le 2^m$). This means the pair at root $r$ falls completely inside the coordinate window $[g, g + 2^m)$ where class $g$ is full. Since $r < g$ implies $r \ne g$ (by `ne_of_lt`), this contradicts `cycle_power_full_class_internal_exact_pair_impossible`.
uses
cycle_power_full_class_internal_exact_pair_impossible,ne_of_ltconstructor · by_contra hn have hlo : (g : ℤ) ≤ (r : ℤ)+(a : ℤ) := by exact_mod_cast (show g ≤ r+a by omega) have hhi : (r : ℤ)+((a+2^m-2^j : ℕ) : ℤ) < (g : ℤ)+(2^m : ℕ) := by exact_mod_cast (show r+(a+2^m-2^j) < g+2^m by omega) exact cycle_power_full_class_internal_exact_pair_impossible (2^m) (2^j) hRD x (hexact j hj) (r : ℤ) (g : ℤ) (by exact_mod_cast (ne_of_lt hrg)) hfullg a ha h₀ h₁ hlo hhi
The upper absolute endpoint is at least the full radius, that is, $2^m \le r + (a + 2^m - 2^j)$.
For the second goal, we assume for contradiction that $r + (a + 2^m - 2^j) < 2^m$. Since $r, a \ge 0$, the lower endpoint satisfies $0 \le r + a$. Rewriting $2^m$ as $0 + 2^m$ via `zero_add`, the upper endpoint satisfies $r + (a + 2^m - 2^j) < 0 + 2^m$. Consequently, the pair at root $r$ would fall entirely within the window $[0, 2^m)$ where root $0$ is full. Because $0 < r$ implies $r \ne 0$ (by `Nat.ne_of_gt`), `cycle_power_full_class_internal_exact_pair_impossible` produces the final contradiction.
uses
cycle_power_full_class_internal_exact_pair_impossible,zero_add,Nat.ne_of_gt· by_contra hn have hlo : (0 : ℤ) ≤ (r : ℤ)+(a : ℤ) := by positivity have hhi : (r : ℤ)+((a+2^m-2^j : ℕ) : ℤ) < (0 : ℤ)+(2^m : ℕ) := by simp only [zero_add] exact_mod_cast (show r+(a+2^m-2^j) < 2^m by omega) exact cycle_power_full_class_internal_exact_pair_impossible (2^m) (2^j) hRD x (hexact j hj) (r : ℤ) 0 (by exact_mod_cast (Nat.ne_of_gt hr₀)) hfull₀ a ha h₀ h₁ hlo hhi
Nat.pow_le_pow_right- For a positive base $n$, if $i \le j$ then $n^i \le n^j$.
Nat.le_of_lt- If $n < m$, then $n \le m$.
ne_of_lt- If $a < b$ in a preorder, then $a \ne b$.
cycle_power_full_class_internal_exact_pair_impossible- In an exact dyadic system with radius parameter $R \le D$, an active pair at root $p$ cannot lie entirely within the coordinate interval $[q, q + D)$ of a distinct full root $q \ne p$.
zero_add- Adding zero on the left is the identity: $0 + a = a$.
Nat.ne_of_gt- If $b < a$ for natural numbers, then $a \ne b$.
- The intermediate bounds `haD` ($a < 2^m$) and `hbD` ($a + 2^m - 2^j < 2^m$) derived on lines 17–18 are unused in the rest of the script, as the linear arithmetic tactic `omega` reconstructs the required bounds directly during the casts.
- Casts between natural numbers and integers (`exact_mod_cast`) are used throughout because root coordinates and offsets are embedded into $\mathbb{Z}$.
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_dyadic_two_full_roots_pair_crosses (m : ℕ) (x : ℤ → ℕ → Bool) (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) (g : ℕ) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) (r : ℕ) (hr₀ : 0 < r) (hrg : r < g) (j : ℕ) (hj : j < m) (a : ℕ) (ha : a < 2^j) (h₀ : x (r : ℤ) a = true) (h₁ : x (r : ℤ) (a+2^m-2^j) = true) : r+a < g ∧ 2^m ≤ r+(a+2^m-2^j) := by have hRD : 2^j ≤ 2^m := Nat.pow_le_pow_right (by decide) (Nat.le_of_lt hj) have haD : a < 2^m := by omega have hbD : a+2^m-2^j < 2^m := by omega constructor · by_contra hn have hlo : (g : ℤ) ≤ (r : ℤ)+(a : ℤ) := by exact_mod_cast (show g ≤ r+a by omega) have hhi : (r : ℤ)+((a+2^m-2^j : ℕ) : ℤ) < (g : ℤ)+(2^m : ℕ) := by exact_mod_cast (show r+(a+2^m-2^j) < g+2^m by omega) exact cycle_power_full_class_internal_exact_pair_impossible (2^m) (2^j) hRD x (hexact j hj) (r : ℤ) (g : ℤ) (by exact_mod_cast (ne_of_lt hrg)) hfullg a ha h₀ h₁ hlo hhi · by_contra hn have hlo : (0 : ℤ) ≤ (r : ℤ)+(a : ℤ) := by positivity have hhi : (r : ℤ)+((a+2^m-2^j : ℕ) : ℤ) < (0 : ℤ)+(2^m : ℕ) := by simp only [zero_add] exact_mod_cast (show r+(a+2^m-2^j) < 2^m by omega) exact cycle_power_full_class_internal_exact_pair_impossible (2^m) (2^j) hRD x (hexact j hj) (r : ℤ) 0 (by exact_mod_cast (Nat.ne_of_gt hr₀)) hfull₀ a ha h₀ h₁ hlo hhi