cycle_power_dyadic_outer_projection_comp_prune
A direct projection after deleting the original middle quarters equals the same direct projection of the original class at every smaller valid radius.
Statement
theorem cycle_power_dyadic_outer_projection_comp_prune
(M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool) :
cycle_power_dyadic_outer_projection (M+1) r (cycle_power_dyadic_b_lift M b) =
cycle_power_dyadic_outer_projection (M+2) r b- 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 2
- 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_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_outer_projection_modelEvery valid direct outer projection preserves tight dyadic weight, exact dyadic edges and full ordinary coverage. No scalar active-count…
The proof, explained
The theorem states that applying a dyadic lift at scale $M$ followed by an outer projection at scale $M+1$ with radius $r \le M$ produces the exact same function as a direct outer projection at scale $M+2$ with radius $r$. By functional extensionality, it suffices to show that both sides agree on every natural number $a$. When $a < 2^r$, both operations take their unshifted branches, trivially evaluating to $b(a)$. When $a \ge 2^r$, the outer projection on the left shifts $a$ past $2^M$, which triggers the shifted branch of the lift; the two shifts $(2^{M+1} - 2^{r+1})$ and $2^{M+1}$ sum to $2^{M+2} - 2^{r+1}$, matching the single shift performed by the outer projection on the right.
$2^r \le 2^M$, and the powers of two satisfy $2^{r+1} = 2 \cdot 2^r$, $2^{M+1} = 2 \cdot 2^M$, and $2^{M+2} = 2 \cdot 2^{M+1}$.
Since $r \le M$ and $2 > 0$, monotonicity of powers (`Nat.pow_le_pow_right`) yields $2^r \le 2^M$. Rewriting with `pow_succ` decomposes $2^{k+1}$ into $2^k \cdot 2$, and commutativity of multiplication is resolved by linear arithmetic (`omega`) for $k \in \{r, M, M+1\}$.
uses
Nat.pow_le_pow_right,pow_succhave hp : 2^r ≤ 2^M := Nat.pow_le_pow_right (by decide) hr have hR : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hH : 2^(M+1)=2*2^M := by rw [pow_succ]; omega have hD : 2^(M+2)=2*2^(M+1) := by rw [pow_succ]; omega
It suffices to show that both sides agree pointwise on every argument $a \in \mathbb{N}$.
By functional extensionality (`funext`), two functions on $\mathbb{N}$ are equal if they evaluate to the same value on every input $a$.
funext aWhen $a < 2^r$, both sides evaluate to $b(a)$.
We split into cases on whether $a < 2^r$. When $a < 2^r$, we also have $a < 2^M$ since $2^r \le 2^M$ (deduced by `omega`). Unfolding `cycle_power_dyadic_outer_projection` and `cycle_power_dyadic_b_lift`, both conditions $a < 2^r$ and $a < 2^M$ hold, so `if_pos` selects the initial branch in both definitions, simplifying each side directly to $b(a)$.
uses
cycle_power_dyadic_outer_projection,cycle_power_dyadic_b_lift,if_posby_cases ha : a < 2^r · have haM : a < 2^M := by omega simp only [cycle_power_dyadic_outer_projection,if_pos ha, cycle_power_dyadic_b_lift,if_pos haM]
When $a \ge 2^r$, both sides evaluate to $b(a + 2^{M+2} - 2^{r+1})$.
In the second case where $a \ge 2^r$, linear arithmetic (`omega`) establishes that the shifted index $a + 2^{M+1} - 2^{r+1}$ is at least $2^M$. Consequently, `if_neg` selects the 'else' branch for both the outer projection and the dyadic lift, reducing the left-hand side to $b(a + 2^{M+1} - 2^{r+1} + 2^{M+1})$ and the right-hand side to $b(a + 2^{M+2} - 2^{r+1})$. By congruence (`congr 1`), it remains to check that the two index expressions are equal; this holds because $2^{M+1} + 2^{M+1} = 2 \cdot 2^{M+1} = 2^{M+2}$, which is closed by linear arithmetic (`omega`).
uses
cycle_power_dyadic_outer_projection,cycle_power_dyadic_b_lift,if_neg· have hi : ¬a+2^(M+1)-2^(r+1) < 2^M := by omega simp only [cycle_power_dyadic_outer_projection,if_neg ha, cycle_power_dyadic_b_lift,if_neg hi] congr 1 omega
Nat.pow_le_pow_right- For any positive natural base $n$, if $i \le j$ then $n^i \le n^j$.
pow_succ- In any monoid, $a^{n+1} = a^n \cdot a$.
if_pos- If the condition $c$ is true, then `if c then t else e` equals $t$.
if_neg- If the condition $c$ is false, then `if c then t else e` equals $e$.
cycle_power_dyadic_outer_projection- The outer projection of a sequence $b$ at scale $m$ and radius $r$, mapping an input $a$ to $b(a)$ when $a < 2^r$ and to $b(a + 2^m - 2^{r+1})$ otherwise.
cycle_power_dyadic_b_lift- The lift of a sequence $b$ at scale $k$, mapping an input $x$ to $b(x)$ when $x < 2^k$ and to $b(x + 2^{k+1})$ otherwise.
- The natural number subtractions in the shifted index expressions, such as $a + 2^{M+1} - 2^{r+1}$, require that $2^{r+1} \le 2^{M+1}$ (guaranteed by $r \le M$) to avoid underflow at zero in $\mathbb{N}$; the tactic `omega` verifies this non-underflow automatically.
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_comp_prune (M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool) : cycle_power_dyadic_outer_projection (M+1) r (cycle_power_dyadic_b_lift M b) = cycle_power_dyadic_outer_projection (M+2) r b := by have hp : 2^r ≤ 2^M := Nat.pow_le_pow_right (by decide) hr have hR : 2^(r+1)=2*2^r := by rw [pow_succ]; omega have hH : 2^(M+1)=2*2^M := by rw [pow_succ]; omega have hD : 2^(M+2)=2*2^(M+1) := by rw [pow_succ]; omega funext a by_cases ha : a < 2^r · have haM : a < 2^M := by omega simp only [cycle_power_dyadic_outer_projection,if_pos ha, cycle_power_dyadic_b_lift,if_pos haM] · have hi : ¬a+2^(M+1)-2^(r+1) < 2^M := by omega simp only [cycle_power_dyadic_outer_projection,if_neg ha, cycle_power_dyadic_b_lift,if_neg hi] congr 1 omega