cycle_power_dyadic_end_shell_fullness_of_no_island
Conversely, no-island shape in a tight exact full-coverage dyadic model forces both complete dyadic end blocks whenever either next-shell offset is selected. Together with the converse theorem this is a flat structural characterization.
Statement
theorem cycle_power_dyadic_end_shell_fullness_of_no_island (M : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (M+1) (x p) = (range (2^(M+1))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < M+1, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(M+1)-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(M+1) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(M+1)-d ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+d) = true) (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) → x p a = false → x p b = true → x p c = true) : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 2^(r+1) → (x p a = true ∨ x p (2^(M+1)-1-a) = true) → ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true
- Source
- Uniform structural reduction for OP-205 / RT-1 following arXiv:2610.15635 Section 3. The all-scale shell fullness conditions are explicit hypotheses when used; they have not been derived from optimal active counts. No graph covering value or research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_no_island_middle_imp_full_pruneIf a tight dyadic two-interval class contains any middle-quarter vertex, deleting the middle two quarters leaves a full smaller class.…
- cycle_power_dyadic_outer_projectionProject a radius-2^m Boolean class to its first and last 2^r offsets, compressing them to a radius-2^(r+1) profile. The intended range is…
- cycle_power_dyadic_outer_projection_pruneSuccessive direct outer projections form a compatible middle-quarter pruning hierarchy.
- cycle_power_dyadic_outer_projection_modelEvery valid direct outer projection preserves tight dyadic weight, exact dyadic edges and full ordinary coverage. No scalar active-count…
- cycle_power_dyadic_outer_projection_no_islandDirect outer projection preserves no-island shape.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- Used by 1
- cycle_power_dyadic_class_no_island_iff_end_shell_fullnessIn any tight exact full-coverage dyadic class model, two-end-interval/no-island shape is equivalent to this explicit condition on the…
The proof, explained
The theorem establishes that in a tight, exact, full-coverage dyadic model satisfying the no-island condition, if either index in the (r+1)-st dyadic shell is selected in a fiber, then both complete dyadic end blocks of length 2^r (the prefix and the suffix) are completely true. The proof projects the fiber to scale r+1, which preserves tightness and the no-island condition. The selected index or its symmetric reflection lands in the middle range [2^r, 3 * 2^r) of this projection, where a middle-fullness lemma forces its dyadic lift to be identically true. Since pruning commutes with outer projection, this identifies the scale-r outer projection as identically true, which directly unfolds to fullness of both dyadic end blocks.
Introduce parameters and establish dyadic exponent inequalities.
Fix a scale r < M, a fiber p, an index a ∈ [2^r, 2^(r+1)), and assume that either x(p, a) = true or x(p, 2^(M+1) - 1 - a) = true. Since r < M, we have r + 2 ≤ M + 1, which implies 2^(r+2) ≤ 2^(M+1) by monotonicity of powers of 2 (Nat.pow_le_pow_right). The identities 2^(r+1) = 2 * 2^r and 2^(r+2) = 2 * 2^(r+1) follow from pow_succ.
uses
Nat.pow_le_pow_right,pow_succintro r hr p a ha0 ha1 hx have hp : 2^(r+2) ≤ 2^(M+1) := Nat.pow_le_pow_right (by decide) (by omega) have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hD : 2^(r+2)=2*2^(r+1) := by rw [pow_succ]; omega
The outer projection b of fiber x(p) to scale r+1 inherits tightness and the no-island shape.
Define b to be the outer projection of fiber x(p) from dimension M+1 to scale r+1. Because r + 1 ≤ M, the projection preserves model tightness at dimension r+2 by cycle_power_dyadic_outer_projection_model. Furthermore, cycle_power_dyadic_outer_projection_no_island ensures that b inherits the no-island condition on [0, 2^(r+2)).
uses
cycle_power_dyadic_outer_projection_model,cycle_power_dyadic_outer_projection_no_islandlet b := cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) have htb : cycle_power_dyadic_class_weight (r+2) b = (range (2^(r+2))).sum (fun a => (b a).toNat) := (cycle_power_dyadic_outer_projection_model M (r+1) (by omega) x htight hexact hcover).1 p have hsb := cycle_power_dyadic_outer_projection_no_island M (r+1) (by omega) (x p) (hshape p)
The pruned dyadic lift of b at scale r is identically true on all indices below 2^(r+1).
We split into cases depending on which offset in the hypothesis is true. If x(p, a) = true, then because a < 2^(r+1), the definition of outer projection gives b(a) = true by if_pos; since 2^r ≤ a < 3 * 2^r, cycle_power_dyadic_no_island_middle_imp_full_prune shows the lift is identically true. If x(p, 2^(M+1) - 1 - a) = true, setting j = 2^(r+2) - 1 - a yields an index with 2^(r+1) ≤ j < 3 * 2^r, and the outer projection gives b(j) = true by if_neg, so the same lemma forces the lift to be identically true.
uses
if_pos,cycle_power_dyadic_no_island_middle_imp_full_prune,if_neghave hbf : ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r b i = true := by rcases hx with hx | hx · have hba : b a = true := by simpa only [b,cycle_power_dyadic_outer_projection,if_pos ha1] using hx exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb a ha0 (by omega) hba · let j := 2^(r+2)-1-a have hj0 : 2^(r+1) ≤ j := by dsimp [j]; omega have hj1 : j < 3*2^r := by dsimp [j]; omega have hi : j+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-a := by dsimp [j]; omega have hbj : b j = true := by simpa only [b,cycle_power_dyadic_outer_projection,if_neg (by omega : ¬j<2^(r+1)),hi] using hx exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb j (by omega) hj1 hbj
The outer projection of x(p) at scale r is identically true on [0, 2^(r+1)).
By cycle_power_dyadic_outer_projection_prune, the dyadic lift of the scale-(r+1) projection at scale r equals the scale-r outer projection. Applying this rewrite to the fullness established in the previous step shows that the outer projection at scale r is true at every i < 2^(r+1).
uses
cycle_power_dyadic_outer_projection_prunehave he := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p) have hproj : ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true := by intro i hi have hh := hbf i hi change cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)) i = true at hh rw [he] at hh exact hh
Both dyadic end blocks of length 2^r in x(p) are completely true.
For any index i < 2^r, we evaluate the scale-r outer projection. For the prefix, i < 2^r, so if_pos reduces the projection at i directly to x(p, i) = true. For the suffix, setting j = 2^(r+1) - 1 - i satisfies 2^r ≤ j < 2^(r+1), so if_neg evaluates the projection at j to x(p, j + 2^(M+1) - 2^(r+1)) = x(p, 2^(M+1) - 1 - i) = true. Therefore, both x(p, i) and x(p, 2^(M+1) - 1 - i) are true.
uses
if_pos,if_negintro i hi constructor · simpa only [cycle_power_dyadic_outer_projection,if_pos hi] using hproj i (by omega) · let j := 2^(r+1)-1-i have hj : j < 2^(r+1) := by dsimp [j]; omega have hjq : ¬j < 2^r := by dsimp [j]; omega have hi' : j+2^(M+1)-2^(r+1)=2^(M+1)-1-i := by dsimp [j]; omega simpa only [cycle_power_dyadic_outer_projection,if_neg hjq,hi'] using hproj j hj
Nat.pow_le_pow_right- For any positive base n and exponents i ≤ j, n^i ≤ n^j.
pow_succ- The (n+1)-st power of a equals a^n * a.
cycle_power_dyadic_outer_projection_model- Outer projection of a tight, exact, full-coverage dyadic model from scale M+1 to scale r ≤ M preserves tightness, exactness, and full coverage at scale r+1.
cycle_power_dyadic_outer_projection_no_island- The outer projection of a sequence satisfying the no-island property also satisfies the no-island property.
cycle_power_dyadic_no_island_middle_imp_full_prune- In a tight model of dimension k+2 satisfying the no-island shape condition, having any true bit in the middle range [2^k, 3 * 2^k) forces the dyadic pruned lift at scale k to be true everywhere on [0, 2^(k+1)).
cycle_power_dyadic_outer_projection_prune- Pruning (lifting) an outer projection of scale r+1 at scale r recovers the outer projection at scale r.
if_pos- An if-then-else expression evaluates to the then-branch when the condition holds.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
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 Finsettheorem cycle_power_dyadic_end_shell_fullness_of_no_island (M : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (M+1) (x p) = (range (2^(M+1))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < M+1, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(M+1)-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(M+1) → ∀ v : ℤ, ∃ c : ℕ, c < 2^(M+1)-d ∧ x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+d) = true) (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) → x p a = false → x p b = true → x p c = true) : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 2^(r+1) → (x p a = true ∨ x p (2^(M+1)-1-a) = true) → ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true := by intro r hr p a ha0 ha1 hx have hp : 2^(r+2) ≤ 2^(M+1) := Nat.pow_le_pow_right (by decide) (by omega) have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hD : 2^(r+2)=2*2^(r+1) := by rw [pow_succ]; omega let b := cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) have htb : cycle_power_dyadic_class_weight (r+2) b = (range (2^(r+2))).sum (fun a => (b a).toNat) := (cycle_power_dyadic_outer_projection_model M (r+1) (by omega) x htight hexact hcover).1 p have hsb := cycle_power_dyadic_outer_projection_no_island M (r+1) (by omega) (x p) (hshape p) have hbf : ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r b i = true := by rcases hx with hx | hx · have hba : b a = true := by simpa only [b,cycle_power_dyadic_outer_projection,if_pos ha1] using hx exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb a ha0 (by omega) hba · let j := 2^(r+2)-1-a have hj0 : 2^(r+1) ≤ j := by dsimp [j]; omega have hj1 : j < 3*2^r := by dsimp [j]; omega have hi : j+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-a := by dsimp [j]; omega have hbj : b j = true := by simpa only [b,cycle_power_dyadic_outer_projection,if_neg (by omega : ¬j<2^(r+1)),hi] using hx exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb j (by omega) hj1 hbj have he := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p) have hproj : ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true := by intro i hi have hh := hbf i hi change cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)) i = true at hh rw [he] at hh exact hh intro i hi constructor · simpa only [cycle_power_dyadic_outer_projection,if_pos hi] using hproj i (by omega) · let j := 2^(r+1)-1-i have hj : j < 2^(r+1) := by dsimp [j]; omega have hjq : ¬j < 2^r := by dsimp [j]; omega have hi' : j+2^(M+1)-2^(r+1)=2^(M+1)-1-i := by dsimp [j]; omega simpa only [cycle_power_dyadic_outer_projection,if_neg hjq,hi'] using hproj j hj