AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_projection_no_island

theoremverified

Direct outer projection preserves no-island shape.

Statement

theorem cycle_power_dyadic_outer_projection_no_island
    (M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool)
    (hshape : ∀ a c d : ℕ, a < c → c < d → d < 2^(M+1) →
      b a = false → b c = true → b d = true) :
    ∀ a c d : ℕ, a < c → c < d → d < 2^(r+1) →
      cycle_power_dyadic_outer_projection (M+1) r b a = false →
      cycle_power_dyadic_outer_projection (M+1) r b c = true →
      cycle_power_dyadic_outer_projection (M+1) r b d = 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
Quot.soundpropext
Built on 1
  • 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…
Used by 1

The proof, explained

The proof shows that the dyadic outer projection of b can be expressed as b ∘ f for an explicit piecewise map f that leaves [0, 2^r) unchanged and translates [2^r, 2^(r+1)) to the top of [0, 2^(M+1)). Because r ≤ M, the map f is strictly increasing and its image remains strictly bounded by 2^(M+1). Applying the no-island hypothesis for b to the reindexed points f(a) < f(c) < f(d) then directly yields the result for the projected sequence.

  1. 2^(r+1) ≤ 2^(M+1) and 2^(r+1) = 2 * 2^r

    Since r ≤ M, we have r + 1 ≤ M + 1, so by monotonicity of powers of 2 (Nat.pow_le_pow_right), 2^(r+1) ≤ 2^(M+1). We also rewrite 2^(r+1) as 2 * 2^r using pow_succ and linear arithmetic.

    lines 11–12

    uses Nat.pow_le_pow_right, pow_succ

      have hp : 2^(r+1) ≤ 2^(M+1) := Nat.pow_le_pow_right (by decide) (by omega)
      have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega
  2. The outer projection of b at index i equals b(f(i)), where f(i) = i for i < 2^r and f(i) = i + 2^(M+1) - 2^(r+1) for i ≥ 2^r

    We define the reindexing map f that leaves the lower dyadic block [0, 2^r) fixed and shifts the upper block [2^r, 2^(r+1)) to the top of [0, 2^(M+1)). Unfolding the definition of cycle_power_dyadic_outer_projection and f, both sides are identical by definition in each case.

    lines 13–16

      let f : ℕ → ℕ := fun i => if i < 2^r then i else i+2^(M+1)-2^(r+1)
      have he (i : ℕ) : cycle_power_dyadic_outer_projection (M+1) r b i = b (f i) := by
        dsimp [cycle_power_dyadic_outer_projection,f]
        split_ifs <;> rfl
  3. For arbitrary a < c < d < 2^(r+1) with b(f(a)) = false and b(f(c)) = true, it suffices to show b(f(d)) = true

    We introduce the variables and assumptions, then rewrite all occurrences of outer projection in the hypotheses and goal using the reindexing identity b(f(·)).

    lines 17–18

      intro a c d hac hcd hd ha hc
      rw [he] at ha hc ⊢
  4. Applying the no-island property hshape at f(a), f(c), and f(d) reduces the goal to showing f(a) < f(c), f(c) < f(d), and f(d) < 2^(M+1)

    The hypothesis hshape guarantees that any false-to-true transition on [0, 2^(M+1)) remains true at later positions. Applying it to the images f(a), f(c), f(d) yields five subgoals: the two truth-value conditions (which hold by assumption) and the three inequalities ensuring that f preserves the ordering and stays within range.

    line 19

      apply hshape (f a) (f c) (f d)
  5. f(a) < f(c)

    Unfolding f and case-splitting on whether a < 2^r and c < 2^r, linear arithmetic (omega) proves f(a) < f(c) in every case using a < c and 2^(r+1) ≤ 2^(M+1).

    line 20

      · dsimp [f]; split_ifs <;> omega
  6. f(c) < f(d)

    Similarly, unfolding f and case-splitting on whether c < 2^r and d < 2^r, linear arithmetic (omega) proves f(c) < f(d) from c < d and 2^(r+1) ≤ 2^(M+1).

    line 21

      · dsimp [f]; split_ifs <;> omega
  7. f(d) < 2^(M+1)

    Unfolding f, if d < 2^r then d < 2^(r+1) ≤ 2^(M+1); if d ≥ 2^r, then d < 2^(r+1) implies d + 2^(M+1) - 2^(r+1) < 2^(M+1). Linear arithmetic (omega) verifies both cases.

    line 22

      · dsimp [f]; split_ifs <;> omega
  8. b(f(a)) = false and b(f(c)) = true

    These match the rewritten hypotheses ha and hc directly.

    lines 23–24

      · exact ha
      · exact hc
Nat.pow_le_pow_right
For any base n > 0, exponentiation is monotone: if i ≤ j, then n^i ≤ n^j.
pow_succ
In any monoid, a^(n + 1) = a^n * a.

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_no_island    (M r : ℕ) (hr : r ≤ M) (b : ℕ → Bool)    (hshape : ∀ a c d : ℕ, a < c → c < d → d < 2^(M+1) →      b a = false → b c = true → b d = true) :    ∀ a c d : ℕ, a < c → c < d → d < 2^(r+1) →      cycle_power_dyadic_outer_projection (M+1) r b a = false →      cycle_power_dyadic_outer_projection (M+1) r b c = true →      cycle_power_dyadic_outer_projection (M+1) r b d = true := by  have hp : 2^(r+1) ≤ 2^(M+1) := Nat.pow_le_pow_right (by decide) (by omega)  have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega  let f : ℕ → ℕ := fun i => if i < 2^r then i else i+2^(M+1)-2^(r+1)  have he (i : ℕ) : cycle_power_dyadic_outer_projection (M+1) r b i = b (f i) := by    dsimp [cycle_power_dyadic_outer_projection,f]    split_ifs <;> rfl  intro a c d hac hcd hd ha hc  rw [he] at ha hc ⊢  apply hshape (f a) (f c) (f d)  · dsimp [f]; split_ifs <;> omega  · dsimp [f]; split_ifs <;> omega  · dsimp [f]; split_ifs <;> omega  · exact ha  · exact hc
See it in the graphDiscuss this resultChallenge it