cycle_power_dyadic_full_gap_class_no_island
In a tight exact full ordinary-coverage dyadic model, every class rooted strictly between full roots zero and g has no selected island between missing offsets, when g lies between half and the full radius.
Statement
theorem cycle_power_dyadic_full_gap_class_no_island (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) (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) : ∀ r : ℕ, 0 < r → r < g → ∀ a b c : ℕ, a < b → b < c → c < 2^m → x (r : ℤ) a = false → x (r : ℤ) b = true → x (r : ℤ) 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 6
- 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_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…
- cycle_power_dyadic_exact_endpointsExact ownership of all dyadic distances in a radius-2^m model with positive exponent forces both endpoints of every rooted class to be…
- cycle_power_gap_left_sideThe lower-block vertices of a rooted profile, represented by their absolute positions in Fin g.
- cycle_power_gap_right_sideThe upper-block vertices of a rooted profile, represented in Fin g after subtracting the radius.
- cycle_power_dyadic_full_gap_sides_convexIn a tight exact full ordinary-coverage dyadic model, all compressed sides between full roots zero and g are intervals when g lies between…
- Used by 1
- cycle_power_dyadic_class_no_island_of_full_class_coverA positive-exponent integer dyadic rooted-class model with tight weights, exact dyadic pair ownership, all ordinary distance coverage, and…
The proof, explained
To show that a missing offset a cannot be followed by an isolated selected offset b without all subsequent offsets c > b also being selected, the proof uses the convexity of the gap sides of intermediate root classes. An overlap-gap lemma partitions the possibilities for the selected offset b into either the left gap side (r + b < g) or the right gap side (2^m ≤ r + b). If b were on the left side, convexity between the endpoint offset 0 and b would force offset a to be selected, contradicting that a is missing. Thus b must lie on the right side, where convexity between b and the right endpoint 2^m - 1 forces any subsequent offset c to be selected.
The left and right gap sides of each root class r ∈ (0, g) are convex subsets of Fin g.
Using the hypotheses that the dyadic model is tight, exact, and covering, with full roots at 0 and g satisfying 2^(m-1) ≤ g ≤ 2^m, lemma cycle_power_dyadic_full_gap_sides_convex establishes that for every intermediate root class r, both the left gap side (offsets i - r for r ≤ i < g) and the right gap side (offsets 2^m + i - r for i < r) are order-convex in Fin g.
uses
cycle_power_dyadic_full_gap_sides_convexclassical have hconv := cycle_power_dyadic_full_gap_sides_convex m hm x htight hexact hcover g hlo hg hfull₀ hfullgFix an intermediate root r ∈ (0, g) and three ordered offsets a < b < c < 2^m with x(r, a) = false and x(r, b) = true.
We introduce the root r with 0 < r < g, the offsets a < b < c < 2^m, and the assumptions that a is unselected (x(r, a) = false) while b is selected (x(r, b) = true); the remaining goal is to prove that c must also be selected (x(r, c) = true).
intro r hr₀ hrg a b c hab hbc hcD hxa hxbThe endpoint offsets 0 and 2^m - 1 are selected, and either r + b < g or 2^m ≤ r + b.
We represent r as q.val + 1 with q ∈ Fin (g - 1) via linear arithmetic. Lemma cycle_power_dyadic_exact_endpoints shows that the exactness hypothesis forces x(r, 0) = true and x(r, 2^m - 1) = true. Lemma cycle_power_dyadic_two_full_roots_overlap_empty applied to the selected offset b proves that b cannot lie in the overlap gap, giving the disjunction r + b < g ∨ 2^m ≤ r + b. Finally, rcases splits the proof into these two cases.
uses
cycle_power_dyadic_exact_endpoints,cycle_power_dyadic_two_full_roots_overlap_emptylet q : Fin (g-1) := ⟨r-1, by omega⟩ have hq : q.val+1 = r := by dsimp [q]; omega have hends := cycle_power_dyadic_exact_endpoints m hm x hexact (r : ℤ) have hgap := cycle_power_dyadic_two_full_roots_overlap_empty m hm x htight hexact g hg hfull₀ hfullg r hr₀ hrg b (by omega) hxb rcases hgap with hleft | hright
The case r + b < g is impossible.
In the first case where r + b < g, we consider the elements i = r, j = r + a, and k = r + b in Fin g, which satisfy i ≤ j ≤ k because a < b. The index i belongs to the left gap side because its offset is i - r = 0 (by Nat.sub_self) and x(r, 0) = true. The index k belongs to the left gap side because its offset is k - r = b (by Nat.add_sub_cancel_left) and x(r, b) = true. By the convexity of the left gap side, the intermediate index j must also belong to the left gap side, which means x(r, j - r) = x(r, a) = true. This contradicts the assumption x(r, a) = false.
uses
mem_filter.mpr,mem_univ,le_rfl,Nat.sub_self,Nat.add_sub_cancel_left,mem_filter.mp· let i : Fin g := ⟨r, hrg⟩ let j : Fin g := ⟨r+a, by omega⟩ let k : Fin g := ⟨r+b, hleft⟩ have hi : i ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, le_rfl, ?_⟩ simpa only [i, Nat.sub_self] using hends.1 have hk : k ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩ simpa only [k, Nat.add_sub_cancel_left] using hxb have hi' : i ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi have hk' : k ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk have hj := hconv.1 q i j k (by change r ≤ r+a; omega) (by change r+a ≤ r+b; omega) hi' hk' have hj' : j ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by simpa only [hq] using hj have he := (mem_filter.mp hj').2.2 have ha : x (r : ℤ) a = true := by simpa only [j, Nat.add_sub_cancel_left] using he rw [hxa] at ha contradiction
In the case 2^m ≤ r + b, the offset c is selected: x(r, c) = true.
In the second case where 2^m ≤ r + b, we define indices i = r + b - 2^m, j = r + c - 2^m, and k = r - 1 in Fin g, which satisfy i ≤ j ≤ k because b < c < 2^m. The index i belongs to the right gap side because its corresponding offset is 2^m + i - r = b and x(r, b) = true. The index k belongs to the right gap side because its corresponding offset is 2^m + k - r = 2^m - 1 and x(r, 2^m - 1) = true. By the convexity of the right gap side, the intermediate index j also belongs to the right gap side, which implies its offset 2^m + j - r = c is selected, giving x(r, c) = true.
uses
mem_filter.mpr,mem_univ,mem_filter.mp· let i : Fin g := ⟨r+b-2^m, by omega⟩ let j : Fin g := ⟨r+c-2^m, by omega⟩ let k : Fin g := ⟨r-1, by omega⟩ have hi : i ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [i]; omega, ?_⟩ have he : 2^m+i.val-r = b := by dsimp [i]; omega simpa only [he] using hxb have hk : k ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩ have he : 2^m+k.val-r = 2^m-1 := by dsimp [k]; omega simpa only [he] using hends.2 have hi' : i ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi have hk' : k ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk have hj := hconv.2 q i j k (by change r+b-2^m ≤ r+c-2^m; omega) (by change r+c-2^m ≤ r-1; omega) hi' hk' have hj' : j ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by simpa only [hq] using hj have he := (mem_filter.mp hj').2.2 have hoff : 2^m+j.val-r = c := by dsimp [j]; omega simpa only [hoff] using he
cycle_power_dyadic_full_gap_sides_convex- In a tight, exact, covering dyadic model with full roots at 0 and g, both the left gap side and the right gap side of any intermediate root class are order-convex subsets of Fin g.
cycle_power_dyadic_exact_endpoints- Under the exactness condition, every class has its extreme offsets 0 and 2^m - 1 selected.
cycle_power_dyadic_two_full_roots_overlap_empty- For any intermediate root class r between full roots 0 and g, any selected offset a satisfies either r + a < g or 2^m ≤ r + a.
mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base finset and satisfies the filtering predicate.
mem_filter.mp- If an element belongs to a filtered finset, it belongs to the base finset and satisfies the filtering predicate.
mem_univ- Every element of a finite type belongs to the universal finset univ.
le_rfl- The ordering relation ≤ is reflexive: a ≤ a for every element a.
Nat.sub_self- Subtracting a natural number from itself gives zero: n - n = 0.
Nat.add_sub_cancel_left- Adding and then subtracting the same natural number cancels: (n + m) - n = m.
- The convexity lemma indexes intermediate roots by q ∈ Fin (g - 1) where r = q.val + 1, which requires slight index bookkeeping between r and q.
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_full_gap_class_no_island (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) (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) : ∀ r : ℕ, 0 < r → r < g → ∀ a b c : ℕ, a < b → b < c → c < 2^m → x (r : ℤ) a = false → x (r : ℤ) b = true → x (r : ℤ) c = true := by classical have hconv := cycle_power_dyadic_full_gap_sides_convex m hm x htight hexact hcover g hlo hg hfull₀ hfullg intro r hr₀ hrg a b c hab hbc hcD hxa hxb let q : Fin (g-1) := ⟨r-1, by omega⟩ have hq : q.val+1 = r := by dsimp [q]; omega have hends := cycle_power_dyadic_exact_endpoints m hm x hexact (r : ℤ) have hgap := cycle_power_dyadic_two_full_roots_overlap_empty m hm x htight hexact g hg hfull₀ hfullg r hr₀ hrg b (by omega) hxb rcases hgap with hleft | hright · let i : Fin g := ⟨r, hrg⟩ let j : Fin g := ⟨r+a, by omega⟩ let k : Fin g := ⟨r+b, hleft⟩ have hi : i ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, le_rfl, ?_⟩ simpa only [i, Nat.sub_self] using hends.1 have hk : k ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩ simpa only [k, Nat.add_sub_cancel_left] using hxb have hi' : i ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi have hk' : k ∈ cycle_power_gap_left_side g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk have hj := hconv.1 q i j k (by change r ≤ r+a; omega) (by change r+a ≤ r+b; omega) hi' hk' have hj' : j ∈ cycle_power_gap_left_side g r (x (r : ℤ)) := by simpa only [hq] using hj have he := (mem_filter.mp hj').2.2 have ha : x (r : ℤ) a = true := by simpa only [j, Nat.add_sub_cancel_left] using he rw [hxa] at ha contradiction · let i : Fin g := ⟨r+b-2^m, by omega⟩ let j : Fin g := ⟨r+c-2^m, by omega⟩ let k : Fin g := ⟨r-1, by omega⟩ have hi : i ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [i]; omega, ?_⟩ have he : 2^m+i.val-r = b := by dsimp [i]; omega simpa only [he] using hxb have hk : k ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by apply mem_filter.mpr refine ⟨mem_univ _, by dsimp [k]; omega, ?_⟩ have he : 2^m+k.val-r = 2^m-1 := by dsimp [k]; omega simpa only [he] using hends.2 have hi' : i ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hi have hk' : k ∈ cycle_power_gap_right_side (2^m) g (q.val+1) (x ((q.val+1 : ℕ) : ℤ)) := by simpa only [hq] using hk have hj := hconv.2 q i j k (by change r+b-2^m ≤ r+c-2^m; omega) (by change r+c-2^m ≤ r-1; omega) hi' hk' have hj' : j ∈ cycle_power_gap_right_side (2^m) g r (x (r : ℤ)) := by simpa only [hq] using hj have he := (mem_filter.mp hj').2.2 have hoff : 2^m+j.val-r = c := by dsimp [j]; omega simpa only [hoff] using he