AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_two_full_roots_pair_crosses

theoremverified

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
Used by 2

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.

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

    lines 16–18

    uses Nat.pow_le_pow_right, Nat.le_of_lt

      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
  2. 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`.

    lines 19–26

    uses cycle_power_full_class_internal_exact_pair_impossible, ne_of_lt

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

    lines 27–34

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

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