AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_two_full_roots_overlap_empty

theoremverified

In 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 overlap of those two full blocks.

Statement

theorem cycle_power_dyadic_two_full_roots_overlap_empty
    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =
      (range (2^m)).sum (fun i => (x p i).toNat))
    (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)
    (a : ℕ) (ha : a < 2^m) (hba : x (r : ℤ) a = true) :
    r+a < g ∨ 2^m ≤ r+a
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 3
Used by 2

The proof, explained

The proof proceeds by contradiction. If an active coordinate a in an intermediate class r between full roots 0 and g fell in their overlap (meaning g ≤ r + a < 2^m), then a would be strictly interior (0 < a < 2^m - 1). By tightness, such an interior vertex must belong to an active dyadic pair at some scale j < m; but by the crossing lemma for two full roots, every such pair must have its lower endpoint strictly below g and its upper endpoint at or above 2^m, which contradicts a being either endpoint.

  1. Assuming for contradiction that r + a lies in the overlap [g, 2^m - 1], the coordinate a is strictly interior: 0 < a and a < 2^m - 1.

    We assume for contradiction the negation ¬(r + a < g ∨ 2^m ≤ r + a), which means g ≤ r + a and r + a < 2^m. Since 0 < r < g, the inequality g ≤ r + a implies a > 0. Similarly, since r > 0 and r + a < 2^m, we have a < 2^m - 1. Linear integer arithmetic (omega) derives both inequalities.

    lines 17–19

      by_contra hn
      have ha₀ : 0 < a := by omega
      have haD : a < 2^m-1 := by omega
  2. The coordinate a is an endpoint of an active dyadic pair in class r at some scale 1 ≤ j < m.

    Because class r is tight and a is an interior active element (0 < a < 2^m - 1 with x r a = true), cycle_power_dyadic_tight_class_internal_neighbour produces a scale 1 ≤ j < m and an offset i < 2^j such that both i and i + 2^m - 2^j are active in class r, with a equal to one of these two endpoints.

    lines 20–22

    uses cycle_power_dyadic_tight_class_internal_neighbour

      obtain ⟨j, hj₀, hjm, i, hi, h₀, h₁, he⟩ :=
        cycle_power_dyadic_tight_class_internal_neighbour m hm (x (r : ℤ))
          (htight (r : ℤ)) a ha₀ haD hba
  3. The dyadic pair crosses the overlap: r + i < g and r + (i + 2^m - 2^j) ≥ 2^m.

    Applying cycle_power_dyadic_two_full_roots_pair_crosses to the intermediate class r between full roots 0 and g shows that the lower endpoint satisfies r + i < g and the upper endpoint satisfies r + (i + 2^m - 2^j) ≥ 2^m.

    lines 23–24

    uses cycle_power_dyadic_two_full_roots_pair_crosses

      have hcross := cycle_power_dyadic_two_full_roots_pair_crosses
        m x hexact g hg hfull₀ hfullg r hr₀ hrg j hjm i hi h₀ h₁
  4. Contradiction.

    We case-split on whether a = i or a = i + 2^m - 2^j. If a = i, then r + a = r + i < g, contradicting g ≤ r + a. If a = i + 2^m - 2^j, then r + a ≥ 2^m, contradicting r + a < 2^m. In both cases, linear integer arithmetic (omega) finishes the proof by contradiction.

    line 25

      rcases he with he | he <;> omega
cycle_power_dyadic_tight_class_internal_neighbour
In a tight class, any active coordinate strictly between 0 and 2^m - 1 is an endpoint of an active dyadic pair at some scale j with 1 ≤ j < m.
cycle_power_dyadic_two_full_roots_pair_crosses
In an exact dyadic model with full root classes at 0 and g ≤ 2^m, any active dyadic pair at scale j < m in an intermediate class 0 < r < g crosses the gap: its lower endpoint shifts to r + a < g and its upper endpoint shifts to r + (a + 2^m - 2^j) ≥ 2^m.

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_overlap_empty    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =      (range (2^m)).sum (fun i => (x p i).toNat))    (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)    (a : ℕ) (ha : a < 2^m) (hba : x (r : ℤ) a = true) :    r+a < g ∨ 2^m ≤ r+a := by  by_contra hn  have ha₀ : 0 < a := by omega  have haD : a < 2^m-1 := by omega  obtain ⟨j, hj₀, hjm, i, hi, h₀, h₁, he⟩ :=    cycle_power_dyadic_tight_class_internal_neighbour m hm (x (r : ℤ))      (htight (r : ℤ)) a ha₀ haD hba  have hcross := cycle_power_dyadic_two_full_roots_pair_crosses    m x hexact g hg hfull₀ hfullg r hr₀ hrg j hjm i hi h₀ h₁  rcases he with he | he <;> omega
See it in the graphDiscuss this resultChallenge it