cycle_power_dyadic_outer_projection_prune
Successive direct outer projections form a compatible middle-quarter pruning hierarchy.
Statement
theorem cycle_power_dyadic_outer_projection_prune
(m r : ℕ) (hr : r+2 ≤ m) (b : ℕ → Bool) :
cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection m (r+1) b) =
cycle_power_dyadic_outer_projection m 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 2
- cycle_power_dyadic_no_island_of_outer_projection_fullnessA tight exact full-coverage model has no-island class shape if every selected middle bit at EVERY direct outer projection level forces the…
- 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 theorem asserts that lifting the direct outer projection at scale r + 1 by scale r recovers the outer projection at scale r. The proof applies function extensionality and splits on whether the input a is less than 2^r. When a < 2^r, both sides simplify directly to b a; when a ≥ 2^r, both sides take their second branch, and the resulting index arguments to b match by linear integer arithmetic.
2^(r+2) ≤ 2^m, 2^(r+1) = 2 * 2^r, and 2^(r+2) = 2 * 2^(r+1)
We establish preliminary bounds and recurrence relations for powers of two: since 2 > 0 and r + 2 ≤ m, monotonicity of powers (Nat.pow_le_pow_right) gives 2^(r+2) ≤ 2^m; and using pow_succ, 2^(r+1) = 2 * 2^r and 2^(r+2) = 2 * 2^(r+1).
uses
Nat.pow_le_pow_right,pow_succhave hp : 2^(r+2) ≤ 2^m := Nat.pow_le_pow_right (by decide) hr 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
It suffices to show the two functions agree on an arbitrary input a ∈ ℕ
By function extensionality (funext), two functions are equal if their values agree pointwise on every input a.
funext aWhen a < 2^r, both sides evaluate to b a
We split into cases on whether a < 2^r. In the positive case, a < 2^r implies a < 2^(r+1). Unfolding the definitions of cycle_power_dyadic_b_lift and cycle_power_dyadic_outer_projection, both the lift and the projections satisfy their branch conditions, simplifying both sides directly to b a via if_pos.
uses
cycle_power_dyadic_b_lift,cycle_power_dyadic_outer_projection,if_posby_cases ha : a < 2^r · have hi : a < 2^(r+1) := by omega simp only [cycle_power_dyadic_b_lift,if_pos ha, cycle_power_dyadic_outer_projection,if_pos hi,if_pos ha]
When a ≥ 2^r, the left-hand side reduces to b (a + 2^(r+1) + 2^m - 2^(r+2)) and the right-hand side reduces to b (a + 2^m - 2^(r+1))
When a ≥ 2^r, the lift takes its second branch, replacing the argument with a + 2^(r+1). Since a + 2^(r+1) ≥ 2^(r+1), the outer projection at scale r+1 also takes its second branch via if_neg. On the right-hand side, since a ≥ 2^r, the outer projection at scale r directly takes its second branch via if_neg.
uses
cycle_power_dyadic_b_lift,cycle_power_dyadic_outer_projection,if_neg· have hi : ¬a+2^(r+1) < 2^(r+1) := by omega simp only [cycle_power_dyadic_b_lift,if_neg ha, cycle_power_dyadic_outer_projection,if_neg hi,if_neg ha]
The index arguments to b are equal, completing the proof
Applying congruence (congr 1) reduces equality to showing that a + 2^(r+1) + 2^m - 2^(r+1+1) = a + 2^m - 2^(r+1). Since 2^(r+2) = 2 * 2^(r+1) ≤ 2^m, the natural number subtractions do not underflow, and the identity is closed by Presburger arithmetic (omega).
congr 1 omega
Nat.pow_le_pow_right- powers with base n > 0 are monotone in the exponent: if i ≤ j then n^i ≤ n^j
pow_succ- in any monoid, a^(n+1) = a^n * a
cycle_power_dyadic_b_lift- the dyadic lifting operation on a bit sequence b at scale k, sending x to b x if x < 2^k and b (x + 2^(k+1)) otherwise
cycle_power_dyadic_outer_projection- the direct outer projection at scale r, sending a to b a if a < 2^r and b (a + 2^m - 2^(r+1)) otherwise
if_pos- if the condition c is true, then (if c then t else e) = t
if_neg- if the condition c is false (¬c), then (if c then t else e) = e
- The preliminary identities and bounds on powers of two proved on lines 7–9 are not strictly needed by the subsequent arithmetic tactic `omega`, which can handle these relationships automatically, but they were kept in the proof script.
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_prune (m r : ℕ) (hr : r+2 ≤ m) (b : ℕ → Bool) : cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection m (r+1) b) = cycle_power_dyadic_outer_projection m r b := by have hp : 2^(r+2) ≤ 2^m := Nat.pow_le_pow_right (by decide) hr 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 funext a by_cases ha : a < 2^r · have hi : a < 2^(r+1) := by omega simp only [cycle_power_dyadic_b_lift,if_pos ha, cycle_power_dyadic_outer_projection,if_pos hi,if_pos ha] · have hi : ¬a+2^(r+1) < 2^(r+1) := by omega simp only [cycle_power_dyadic_b_lift,if_neg ha, cycle_power_dyadic_outer_projection,if_neg hi,if_neg ha] congr 1 omega