cycle_power_dyadic_two_full_roots_overlap_empty
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
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_tight_class_internal_neighbourEvery selected nonendpoint offset of a tight dyadic class has a selected incident dyadic edge at some positive rank below its exponent.
- 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…
- 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_full_gap_class_no_islandIn a tight exact full ordinary-coverage dyadic model, every class rooted strictly between full roots zero and g has no selected island…
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.
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.
by_contra hn have ha₀ : 0 < a := by omega have haD : a < 2^m-1 := by omega
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.
uses
cycle_power_dyadic_tight_class_internal_neighbourobtain ⟨j, hj₀, hjm, i, hi, h₀, h₁, he⟩ := cycle_power_dyadic_tight_class_internal_neighbour m hm (x (r : ℤ)) (htight (r : ℤ)) a ha₀ haD hbaThe 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.
uses
cycle_power_dyadic_two_full_roots_pair_crosseshave 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₁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.
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
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_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