AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_projection_prune

theoremverified

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

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.

  1. 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).

    lines 7–9

    uses Nat.pow_le_pow_right, pow_succ

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

    line 10

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

    lines 11–14

    uses cycle_power_dyadic_b_lift, cycle_power_dyadic_outer_projection, if_pos

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

    lines 15–17

    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]
  5. 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).

    lines 18–19

        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

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