cycle_power_dyadic_class_no_island_of_full_class_cover
A positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and a full class covering every vertex has no selected island between two missing offsets in any class.
Statement
theorem cycle_power_dyadic_class_no_island_of_full_class_cover (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) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m → x p a = false → x p b = true → x p c = true
- 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 4
- 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_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…
- int_dense_marks_bracketIf every integer lies at distance less than D after a marked integer, every unmarked integer lies strictly between two marked integers…
- cycle_power_two_full_roots_half_separatedWhen D is twice R and every distance-R pair has a unique root owner, distinct full classes rooted at zero and a positive g must have g at…
- Used by 1
- cycle_power_dyadic_half_monotone_of_full_class_coverA tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately…
The proof, explained
The theorem establishes that no class in the model can contain an 'island'—a true value flanked by false values at lower and higher offsets. Because class p has a false offset at a, it is not completely full, and the full-class covering hypothesis brackets p strictly between two full classes at distance at most 2^m. After shifting coordinates so the left full class is at the origin, the exact dyadic ownership condition forces the gap between the two full classes to be at least 2^(m - 1). The structural theorem for dyadic models within such a full-class gap then guarantees that the intermediate class p cannot contain an island, forcing offset c to be true.
Fix an arbitrary class index p and increasing offsets a < b < c < 2^m, assuming x(p, a) = false and x(p, b) = true.
We introduce the universal variables and hypotheses, setting the goal to prove that offset c is true (x(p, c) = true).
classical intro p a b c hab hbc hcD hxa hxbClass p is not completely full (it does not have all offsets < 2^m set to true).
If every offset in class p were true, then in particular offset a would be true, directly contradicting the assumption that x(p, a) = false.
have hp : ¬(∀ i < 2^m, x p i = true) := by intro h have := h a (by omega) rw [hxa] at this contradiction
There exist positive offsets l, r > 0 with l + r ≤ 2^m such that classes p - l and p + r are both completely full.
Because full classes cover every integer within distance 2^m (by hypothesis hfullcover) and p is not itself a full class, int_dense_marks_bracket ensures that p is strictly bracketed between a full class p - l to its left and a full class p + r to its right, with total separation l + r ≤ 2^m.
uses
int_dense_marks_bracketobtain ⟨l, r, hl₀, hr₀, hlr, hFl, hFr⟩ := int_dense_marks_bracket (2^m) (fun q => ∀ i < 2^m, x q i = true) hfullcover p hp
Define the shifted configuration y(q, i) = x(p - l + q, i), under which y(l) coincides with x(p).
We shift the class coordinates by p - l so that the left full class p - l is positioned at the origin 0, placing class p at coordinate l.
let y : ℤ → ℕ → Bool := fun q i => x ((p-(l : ℤ))+q) i have hyroot : ∀ i, y (l : ℤ) i = x p i := by intro i; dsimp [y]; congr 1; omega
The shifted configuration y inherits the tight-weight, exact dyadic pair ownership, and distance coverage conditions.
The model conditions are translation-invariant along the integers. Reassociating integer subtraction via add_sub_assoc shows that shifting by p - l preserves all three properties.
uses
add_sub_assochave hytight : ∀ q : ℤ, cycle_power_dyadic_class_weight m (y q) = (range (2^m)).sum (fun i => (y q i).toNat) := by intro q exact htight ((p-(l : ℤ))+q) have hyexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 := by intro j hj v simpa only [y, add_sub_assoc] using hexact j hj ((p-(l : ℤ))+v) have hycover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧ y (v-(a : ℤ)) (a+d) = true := by intro d hd₀ hdD v simpa only [y, add_sub_assoc] using hcover d hd₀ hdD ((p-(l : ℤ))+v)
The shifted configuration y has full classes at coordinate 0 and coordinate l + r.
Coordinate 0 in y corresponds to p - l (using add_zero), which is full by the definition of l. Coordinate l + r corresponds to (p - l) + (l + r) = p + r, which is full by the definition of r.
uses
add_zerohave hyfull₀ : ∀ i < 2^m, y 0 i = true := by intro i hi simpa only [y, add_zero] using hFl i hi have hyfullg : ∀ i < 2^m, y ((l+r : ℕ) : ℤ) i = true := by intro i hi have hroot : (p-(l : ℤ))+((l+r : ℕ) : ℤ) = p+(r : ℤ) := by omega simpa only [y, hroot] using hFr i hi
The separation between the two full classes satisfies 2^(m - 1) ≤ l + r.
Using pow_succ and ring arithmetic, 2^m = 2 * 2^(m - 1). Applying cycle_power_two_full_roots_half_separated at the largest dyadic scale j = m - 1, the presence of two full classes at 0 and l + r > 0 under exact dyadic ownership implies that the gap l + r must be at least 2^(m - 1).
uses
pow_succ,cycle_power_two_full_roots_half_separatedhave hD : 2^m = 2*2^(m-1) := by have he : m = (m-1)+1 := by omega conv_lhs => rw [he, pow_succ] ring have hlo := cycle_power_two_full_roots_half_separated (2^m) (2^(m-1)) hD y (hyexact (m-1) (by omega)) (l+r) (by omega) hyfull₀ hyfullg
x(p, c) = true, showing that no island occurs.
By cycle_power_dyadic_full_gap_class_no_island, any intermediate class strictly between two full classes separated by a gap g with 2^(m - 1) ≤ g ≤ 2^m cannot have an isolated true value. Since 0 < l < l + r, class l is intermediate; since y(l, a) = false and y(l, b) = true, offset c must be true in y(l). Since y(l) = x(p), we conclude x(p, c) = true.
uses
cycle_power_dyadic_full_gap_class_no_islandhave hshape := cycle_power_dyadic_full_gap_class_no_island m hm y hytight hyexact hycover (l+r) hlo hlr hyfull₀ hyfullg l hl₀ (by omega) a b c hab hbc hcD (by simpa only [hyroot] using hxa) (by simpa only [hyroot] using hxb) simpa only [hyroot] using hshape
int_dense_marks_bracket- If every integer is within distance D of some integer satisfying property F, then any point p not satisfying F is strictly bracketed by points p - l and p + r satisfying F, with l, r > 0 and l + r ≤ D.
add_sub_assoc- In any additive group or monoid with subtraction, a + b - c = a + (b - c).
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
cycle_power_two_full_roots_half_separated- In a block of length D = 2R where exact ownership holds for offset difference D - R = R, any two full classes at 0 and g > 0 must be separated by at least R (that is, R ≤ g).
cycle_power_dyadic_full_gap_class_no_island- In a tight dyadic class model with full classes at 0 and g separated by 2^(m - 1) ≤ g ≤ 2^m, every intermediate class r strictly between 0 and g has no isolated true values: if a < b < c < 2^m with offset a false and offset b true, then offset c must be true.
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_class_no_island_of_full_class_cover (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) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m → x p a = false → x p b = true → x p c = true := by classical intro p a b c hab hbc hcD hxa hxb have hp : ¬(∀ i < 2^m, x p i = true) := by intro h have := h a (by omega) rw [hxa] at this contradiction obtain ⟨l, r, hl₀, hr₀, hlr, hFl, hFr⟩ := int_dense_marks_bracket (2^m) (fun q => ∀ i < 2^m, x q i = true) hfullcover p hp let y : ℤ → ℕ → Bool := fun q i => x ((p-(l : ℤ))+q) i have hyroot : ∀ i, y (l : ℤ) i = x p i := by intro i; dsimp [y]; congr 1; omega have hytight : ∀ q : ℤ, cycle_power_dyadic_class_weight m (y q) = (range (2^m)).sum (fun i => (y q i).toNat) := by intro q exact htight ((p-(l : ℤ))+q) have hyexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a => (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 := by intro j hj v simpa only [y, add_sub_assoc] using hexact j hj ((p-(l : ℤ))+v) have hycover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ y (v-(a : ℤ)) a = true ∧ y (v-(a : ℤ)) (a+d) = true := by intro d hd₀ hdD v simpa only [y, add_sub_assoc] using hcover d hd₀ hdD ((p-(l : ℤ))+v) have hyfull₀ : ∀ i < 2^m, y 0 i = true := by intro i hi simpa only [y, add_zero] using hFl i hi have hyfullg : ∀ i < 2^m, y ((l+r : ℕ) : ℤ) i = true := by intro i hi have hroot : (p-(l : ℤ))+((l+r : ℕ) : ℤ) = p+(r : ℤ) := by omega simpa only [y, hroot] using hFr i hi have hD : 2^m = 2*2^(m-1) := by have he : m = (m-1)+1 := by omega conv_lhs => rw [he, pow_succ] ring have hlo := cycle_power_two_full_roots_half_separated (2^m) (2^(m-1)) hD y (hyexact (m-1) (by omega)) (l+r) (by omega) hyfull₀ hyfullg have hshape := cycle_power_dyadic_full_gap_class_no_island m hm y hytight hyexact hycover (l+r) hlo hlr hyfull₀ hyfullg l hl₀ (by omega) a b c hab hbc hcD (by simpa only [hyroot] using hxa) (by simpa only [hyroot] using hxb) simpa only [hyroot] using hshape