cycle_power_dyadic_outer_projection_no_island
Direct outer projection preserves no-island shape.
Statement
theorem cycle_power_dyadic_outer_projection_no_island
(M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool)
(hshape : ∀ a c d : ℕ, a < c → c < d → d < 2^(M+1) →
b a = false → b c = true → b d = true) :
∀ a c d : ℕ, a < c → c < d → d < 2^(r+1) →
cycle_power_dyadic_outer_projection (M+1) r b a = false →
cycle_power_dyadic_outer_projection (M+1) r b c = true →
cycle_power_dyadic_outer_projection (M+1) r b d = 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
Quot.soundpropext- Built on 1
- 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…
- Used by 1
- cycle_power_dyadic_end_shell_fullness_of_no_islandConversely, no-island shape in a tight exact full-coverage dyadic model forces both complete dyadic end blocks whenever either next-shell…
The proof, explained
The proof shows that the dyadic outer projection of b can be expressed as b ∘ f for an explicit piecewise map f that leaves [0, 2^r) unchanged and translates [2^r, 2^(r+1)) to the top of [0, 2^(M+1)). Because r ≤ M, the map f is strictly increasing and its image remains strictly bounded by 2^(M+1). Applying the no-island hypothesis for b to the reindexed points f(a) < f(c) < f(d) then directly yields the result for the projected sequence.
2^(r+1) ≤ 2^(M+1) and 2^(r+1) = 2 * 2^r
Since r ≤ M, we have r + 1 ≤ M + 1, so by monotonicity of powers of 2 (Nat.pow_le_pow_right), 2^(r+1) ≤ 2^(M+1). We also rewrite 2^(r+1) as 2 * 2^r using pow_succ and linear arithmetic.
uses
Nat.pow_le_pow_right,pow_succhave hp : 2^(r+1) ≤ 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
The outer projection of b at index i equals b(f(i)), where f(i) = i for i < 2^r and f(i) = i + 2^(M+1) - 2^(r+1) for i ≥ 2^r
We define the reindexing map f that leaves the lower dyadic block [0, 2^r) fixed and shifts the upper block [2^r, 2^(r+1)) to the top of [0, 2^(M+1)). Unfolding the definition of cycle_power_dyadic_outer_projection and f, both sides are identical by definition in each case.
let f : ℕ → ℕ := fun i => if i < 2^r then i else i+2^(M+1)-2^(r+1) have he (i : ℕ) : cycle_power_dyadic_outer_projection (M+1) r b i = b (f i) := by dsimp [cycle_power_dyadic_outer_projection,f] split_ifs <;> rfl
For arbitrary a < c < d < 2^(r+1) with b(f(a)) = false and b(f(c)) = true, it suffices to show b(f(d)) = true
We introduce the variables and assumptions, then rewrite all occurrences of outer projection in the hypotheses and goal using the reindexing identity b(f(·)).
intro a c d hac hcd hd ha hc rw [he] at ha hc ⊢
Applying the no-island property hshape at f(a), f(c), and f(d) reduces the goal to showing f(a) < f(c), f(c) < f(d), and f(d) < 2^(M+1)
The hypothesis hshape guarantees that any false-to-true transition on [0, 2^(M+1)) remains true at later positions. Applying it to the images f(a), f(c), f(d) yields five subgoals: the two truth-value conditions (which hold by assumption) and the three inequalities ensuring that f preserves the ordering and stays within range.
apply hshape (f a) (f c) (f d)f(a) < f(c)
Unfolding f and case-splitting on whether a < 2^r and c < 2^r, linear arithmetic (omega) proves f(a) < f(c) in every case using a < c and 2^(r+1) ≤ 2^(M+1).
· dsimp [f]; split_ifs <;> omega
f(c) < f(d)
Similarly, unfolding f and case-splitting on whether c < 2^r and d < 2^r, linear arithmetic (omega) proves f(c) < f(d) from c < d and 2^(r+1) ≤ 2^(M+1).
· dsimp [f]; split_ifs <;> omega
f(d) < 2^(M+1)
Unfolding f, if d < 2^r then d < 2^(r+1) ≤ 2^(M+1); if d ≥ 2^r, then d < 2^(r+1) implies d + 2^(M+1) - 2^(r+1) < 2^(M+1). Linear arithmetic (omega) verifies both cases.
· dsimp [f]; split_ifs <;> omega
b(f(a)) = false and b(f(c)) = true
These match the rewritten hypotheses ha and hc directly.
· exact ha · exact hc
Nat.pow_le_pow_right- For any base n > 0, exponentiation is monotone: if i ≤ j, then n^i ≤ n^j.
pow_succ- In any monoid, a^(n + 1) = a^n * a.
- The lemma `hH` established on line 12 is placed in the local context but is not strictly necessary for the subsequent `omega` calls.
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_outer_projection_no_island (M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool) (hshape : ∀ a c d : ℕ, a < c → c < d → d < 2^(M+1) → b a = false → b c = true → b d = true) : ∀ a c d : ℕ, a < c → c < d → d < 2^(r+1) → cycle_power_dyadic_outer_projection (M+1) r b a = false → cycle_power_dyadic_outer_projection (M+1) r b c = true → cycle_power_dyadic_outer_projection (M+1) r b d = true := by have hp : 2^(r+1) ≤ 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 let f : ℕ → ℕ := fun i => if i < 2^r then i else i+2^(M+1)-2^(r+1) have he (i : ℕ) : cycle_power_dyadic_outer_projection (M+1) r b i = b (f i) := by dsimp [cycle_power_dyadic_outer_projection,f] split_ifs <;> rfl intro a c d hac hcd hd ha hc rw [he] at ha hc ⊢ apply hshape (f a) (f c) (f d) · dsimp [f]; split_ifs <;> omega · dsimp [f]; split_ifs <;> omega · dsimp [f]; split_ifs <;> omega · exact ha · exact hc