AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_projection_comp_prune

theoremverified

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
Used by 1

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.

  1. $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\}$.

    lines 7–10

    uses Nat.pow_le_pow_right, pow_succ

      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
  2. 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$.

    line 11

      funext a
  3. When $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)$.

    lines 12–15

    uses cycle_power_dyadic_outer_projection, cycle_power_dyadic_b_lift, if_pos

      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]
  4. 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`).

    lines 16–20

    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.

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

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
See it in the graphDiscuss this resultChallenge it