cycle_power_dyadic_no_island_of_outer_projection_fullness
A tight exact full-coverage model has no-island class shape if every selected middle bit at EVERY direct outer projection level forces the next prune to be full. Those all-scale fullness hypotheses remain explicit.
Statement
theorem cycle_power_dyadic_no_island_of_outer_projection_fullness (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) (hfull : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) a = true → ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) → x p a = false → x p b = true → x p c = 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 8
- cycle_power_no_island_of_half_monotoneA Boolean class which is monotone toward the left endpoint on the left half and toward the right endpoint on the right half has no…
- cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_pruneA compatible hierarchy of tight exact full-coverage dyadic models has monotone endpoint halves at every level, provided every selected…
- 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_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_selfAt its original radius, direct outer projection is the identity on every offset.
- 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_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_no_island_of_end_shell_fullnessIn a tight exact full-coverage model, class no-island shape follows from the explicit shell condition: selecting either offset a or its…
The proof, explained
The proof establishes that $x$ satisfies the no-island property on $[0, 2^{M+1})$ by showing that each row $x(p)$ is half-monotone (decreasing on $[0, 2^M)$ and increasing on $[2^M, 2^{M+1})$). It constructs the dyadic outer projection hierarchy $B(r, p)$ for $r \le M$, verifies that each level inherits the tight exact coverage model properties and satisfies the pruning relation, and applies hierarchy induction driven by the all-scale fullness hypothesis. Because the top-level outer projection at $r = M$ is $x$ itself, $x$ inherits half-monotonicity, which directly rules out any internal island of true bits.
The family of outer projections $B(r, p)$ satisfies the tightness, exactness, and coverage model properties at every level $r \le M$.
We define $B(r, p)$ as the outer projection of $x(p)$ from scale $M+1$ to scale $r$. Applying `cycle_power_dyadic_outer_projection_model` to the global hypotheses (tightness, exactness, and coverage) shows that for every scale $r \le M$, the projected configuration $B(r, \cdot)$ is a valid dyadic model at scale $r+1$.
uses
cycle_power_dyadic_outer_projection_modellet B : ℕ → ℤ → ℕ → Bool := fun r p => cycle_power_dyadic_outer_projection (M+1) r (x p) have hmodel := fun r hr => cycle_power_dyadic_outer_projection_model M r hr x htight hexact hcover
Each projection level $r < M$ is obtained from level $r+1$ by the dyadic pruning operation: $B(r, p, a) = \text{lift}_r(B(r+1, p))(a)$.
We apply `cycle_power_dyadic_outer_projection_prune` with scale $M+1$ and level $r$, where the side condition $r+2 \le M+1$ follows from $r < M$ by linear integer arithmetic (`omega`). Evaluating both sides at $a$ with `congrFun` and taking symmetry gives the desired pointwise pruning identity.
uses
cycle_power_dyadic_outer_projection_prune,congrFunhave hpr (r : ℕ) (hr : r < M) (p : ℤ) (a : ℕ) : B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a := by have hh := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p) exact (congrFun hh a).symm
At every level $r \le M$, the projection $B(r, p)$ is half-monotone: decreasing on $[0, 2^r)$ and increasing on $[2^r, 2^{r+1})$.
We invoke the hierarchy induction theorem `cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune`. Its premises—the model properties across all $r \le M$, the pruning consistency `hpr`, the middle-bit fullness condition `hfull`, and the trivial bound $M \le M$ (via `omega`)—are all satisfied, yielding half-monotonicity at all levels $r \le M$.
uses
cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prunehave hh := cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune M B (fun r hr => (hmodel r hr).1) (fun r hr => (hmodel r hr).2.1) (fun r hr => (hmodel r hr).2.2) hpr hfull M (by omega)
The original configuration $x(p)$ is half-monotone: decreasing on $[0, 2^M)$ and increasing on $[2^M, 2^{M+1})$. automation
By `cycle_power_dyadic_outer_projection_self`, projecting a sequence of length $2^{M+1}$ to level $M$ is the identity, so $B(M, p) = x(p)$. The `simpa` tactic unfolds $B$, rewrites with this identity, and specializes the hierarchy half-monotonicity result to level $r = M$.
uses
cycle_power_dyadic_outer_projection_selfhave hx : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^M → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^M ≤ a → a ≤ b → b < 2^(M+1) → x p a = true → x p b = true) := by simpa only [B,cycle_power_dyadic_outer_projection_self] using hh
The configuration $x$ satisfies the no-island property on $[0, 2^{M+1})$.
Applying `cycle_power_no_island_of_half_monotone` with split point $H = 2^M$ and domain size $D = 2^{M+1}$ shows that any half-monotone boolean sequence cannot take the values false at $a$, true at $b$, and false at $c$ for $a < b < c < 2^{M+1}$.
uses
cycle_power_no_island_of_half_monotoneexact cycle_power_no_island_of_half_monotone (2^M) (2^(M+1)) x hx
cycle_power_dyadic_outer_projection_model- For any $r \le M$, the outer projection of a tight, exact, covering model of scale $M+1$ down to scale $r$ remains a tight, exact, covering model of scale $r+1$.
cycle_power_dyadic_outer_projection_prune- Pruning (lifting) the outer projection at scale $r+1$ of a sequence of length $2^m$ produces its outer projection at scale $r$, provided $r+2 \le m$.
congrFun- If two functions are equal, their values are equal at every input.
cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune- In a hierarchy of tight, exact, covering models satisfying the dyadic pruning relation, if every true middle bit at scale $r+1$ forces the pruned level $r$ to be identically true, then at every scale $r \le M$, the model is half-monotone (decreasing on $[0, 2^r)$ and increasing on $[2^r, 2^{r+1})$).
cycle_power_dyadic_outer_projection_self- The outer projection of a sequence of length $2^{r+1}$ down to level $r$ is the original sequence itself.
cycle_power_no_island_of_half_monotone- A boolean sequence on $[0, D)$ that is decreasing on $[0, H)$ and increasing on $[H, D)$ cannot take the values false at $a$, true at $b$, and false at $c$ for $a < b < c < D$.
- The 'no-island' property rules out the pattern false-true-false on $[0, 2^{M+1})$; that is, if a configuration is false at a smaller index and true at an intermediate index, it cannot turn false again at a larger index.
- Linear arithmetic side conditions ($r + 2 \le M + 1$ and $M \le M$) are discharged silently by the `omega` tactic.
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_no_island_of_outer_projection_fullness (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) (hfull : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r → cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) a = true → ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true) : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) → x p a = false → x p b = true → x p c = true := by let B : ℕ → ℤ → ℕ → Bool := fun r p => cycle_power_dyadic_outer_projection (M+1) r (x p) have hmodel := fun r hr => cycle_power_dyadic_outer_projection_model M r hr x htight hexact hcover have hpr (r : ℕ) (hr : r < M) (p : ℤ) (a : ℕ) : B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a := by have hh := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p) exact (congrFun hh a).symm have hh := cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune M B (fun r hr => (hmodel r hr).1) (fun r hr => (hmodel r hr).2.1) (fun r hr => (hmodel r hr).2.2) hpr hfull M (by omega) have hx : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^M → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 2^M ≤ a → a ≤ b → b < 2^(M+1) → x p a = true → x p b = true) := by simpa only [B,cycle_power_dyadic_outer_projection_self] using hh exact cycle_power_no_island_of_half_monotone (2^M) (2^(M+1)) x hx