AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_end_shell_fullness

theoremverified

In a tight exact full-coverage model, class no-island shape follows from the explicit shell condition: selecting either offset a or its reflection with 2^r≤a<2^(r+1) forces both complete end blocks of width2^r, for EVERY r below the top half-radius. This does not derive shell fullness from optimal counts.

Statement

theorem cycle_power_dyadic_no_island_of_end_shell_fullness
    (M : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (M+1) (x p) =
      (range (2^(M+1))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < M+1, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(M+1)-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(M+1) → ∀ v : ℤ,
      ∃ c : ℕ, c < 2^(M+1)-d ∧ x (v-(c : ℤ)) c = true ∧
        x (v-(c : ℤ)) (c+d) = true)
    (hshell : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 2^(r+1) →
      (x p a = true ∨ x p (2^(M+1)-1-a) = true) →
      ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true) :
    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) →
      x p a = false → x p b = true → x p c = 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
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The proof reduces the no-island property to a scale-by-scale projection fullness condition via cycle_power_dyadic_no_island_of_outer_projection_fullness. Given a true bit in the scale-(r+1) outer projection at an offset a ∈ [2^r, 3·2^r), the index falls either in the left shell [2^r, 2^(r+1)) or its reflection across the dyadic midpoint does. The shell fullness hypothesis hshell then guarantees that both width-2^r end blocks of the configuration are entirely true. Because the scale-r outer projection consists precisely of these two blocks, it is identically true on all 2^(r+1) positions, completing the reduction.

  1. It suffices to show that whenever the outer projection at scale r+1 is true at some index a ∈ [2^r, 3·2^r), the outer projection at scale r is identically true on all indices i < 2^(r+1).

    We apply cycle_power_dyadic_no_island_of_outer_projection_fullness, which establishes the no-island property from this projection fullness condition across dyadic scales. We then fix an arbitrary scale r < M, class p, and offset a with 2^r ≤ a < 3·2^r such that the scale-(r+1) outer projection is true at a.

    lines 17–18

    uses cycle_power_dyadic_no_island_of_outer_projection_fullness

      apply cycle_power_dyadic_no_island_of_outer_projection_fullness M x htight hexact hcover
      intro r hr p a ha0 ha1 hxa
  2. The power-of-two relations 2^(r+2) ≤ 2^(M+1), 2^(r+1) = 2·2^r, and 2^(r+2) = 2·2^(r+1) hold.

    Since r < M, linear arithmetic gives r + 2 ≤ M + 1, so 2^(r+2) ≤ 2^(M+1) by monotonicity of powers of 2 (Nat.pow_le_pow_right). The doubling relations 2^(k+1) = 2·2^k follow from pow_succ and arithmetic.

    lines 19–21

    uses Nat.pow_le_pow_right, pow_succ

      have hp : 2^(r+2) ≤ 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
      have hD : 2^(r+2)=2*2^(r+1) := by rw [pow_succ]; omega
  3. Both end blocks of width 2^r in x(p) are completely full: for all i < 2^r, x(p, i) = true and x(p, 2^(M+1)-1-i) = true.

    We split on whether a < 2^(r+1). If a < 2^(r+1), then a is in the left shell [2^r, 2^(r+1)); simplifying the outer projection definition with if_pos yields x(p, a) = true, and the shell hypothesis hshell via Or.inl forces both end blocks of width 2^r to be entirely true. If instead a ≥ 2^(r+1), the reflected index j = 2^(r+2)-1-a satisfies 2^r ≤ j < 2^(r+1) and the projection's right-half offset simplifies via if_neg to the reflected shell bit x(p, 2^(M+1)-1-j) = true. Applying hshell via Or.inr again yields that both end blocks of width 2^r are entirely true.

    lines 22–33

    uses cycle_power_dyadic_outer_projection, if_pos, if_neg, Or.inl, Or.inr

      have houter : ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true := by
        by_cases hal : a < 2^(r+1)
        · have hx : x p a = true := by
            simpa only [cycle_power_dyadic_outer_projection,if_pos hal] using hxa
          exact hshell r hr p a ha0 hal (Or.inl hx)
        · let j := 2^(r+2)-1-a
          have hj0 : 2^r ≤ j := by dsimp [j]; omega
          have hj1 : j < 2^(r+1) := by dsimp [j]; omega
          have hi : a+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-j := by dsimp [j]; omega
          have hx : x p (2^(M+1)-1-j) = true := by
            simpa only [cycle_power_dyadic_outer_projection,if_neg hal,hi] using hxa
          exact hshell r hr p j hj0 hj1 (Or.inr hx)
  4. For every i < 2^(r+1), the outer projection at scale r takes value true.

    For an index i < 2^(r+1), we split on i < 2^r. If i < 2^r, the outer projection simplifies by if_pos to x(p, i), which is true by the left end block. If i ≥ 2^r, the outer projection simplifies by if_neg to x(p, i + 2^(M+1) - 2^(r+1)). Setting j = 2^(r+1)-1-i gives j < 2^r and rewrites this index as the reflected coordinate 2^(M+1)-1-j, which is true by the right end block. This establishes projection fullness at scale r and completes the proof.

    lines 34–40

    uses cycle_power_dyadic_outer_projection, if_pos, if_neg

      intro i hi
      by_cases hil : i < 2^r
      · simpa only [cycle_power_dyadic_outer_projection,if_pos hil] using (houter i hil).1
      · let j := 2^(r+1)-1-i
        have hj : j < 2^r := by dsimp [j]; omega
        have he : i+2^(M+1)-2^(r+1)=2^(M+1)-1-j := by dsimp [j]; omega
        simpa only [cycle_power_dyadic_outer_projection,if_neg hil,he] using (houter j hj).2
cycle_power_dyadic_no_island_of_outer_projection_fullness
In a tight, exact, and covering dyadic model, the no-island property holds for every class configuration provided that whenever the outer projection at scale r+1 is true at some a ∈ [2^r, 3·2^r), the outer projection at scale r is identically true on [0, 2^(r+1)).
Nat.pow_le_pow_right
For any positive integer base n, powers are monotonic: if i ≤ j, then n^i ≤ n^j.
pow_succ
In any monoid, the (n+1)-th power satisfies a^(n+1) = a^n * a.
cycle_power_dyadic_outer_projection
The outer projection of a sequence b of length 2^m at scale r evaluated at a: it equals b(a) if a < 2^r, and b(a + 2^m - 2^(r+1)) otherwise.
if_pos
If the condition c is true, the conditional expression (if c then t else e) evaluates to t.
if_neg
If the condition c is false (¬c), the conditional expression (if c then t else e) evaluates to e.
Or.inl
Constructs a proof of a ∨ b from a proof of the left disjunct a.
Or.inr
Constructs a proof of a ∨ b from a proof of the right disjunct b.

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_no_island_of_end_shell_fullness    (M : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (M+1) (x p) =      (range (2^(M+1))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < M+1, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(M+1)-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(M+1) → ∀ v : ℤ,      ∃ c : ℕ, c < 2^(M+1)-d ∧ x (v-(c : ℤ)) c = true ∧        x (v-(c : ℤ)) (c+d) = true)    (hshell : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 2^(r+1) →      (x p a = true ∨ x p (2^(M+1)-1-a) = true) →      ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) →      x p a = false → x p b = true → x p c = true := by  apply cycle_power_dyadic_no_island_of_outer_projection_fullness M x htight hexact hcover  intro r hr p a ha0 ha1 hxa  have hp : 2^(r+2) ≤ 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  have hD : 2^(r+2)=2*2^(r+1) := by rw [pow_succ]; omega  have houter : ∀ i < 2^r, x p i = true ∧ x p (2^(M+1)-1-i) = true := by    by_cases hal : a < 2^(r+1)    · have hx : x p a = true := by        simpa only [cycle_power_dyadic_outer_projection,if_pos hal] using hxa      exact hshell r hr p a ha0 hal (Or.inl hx)    · let j := 2^(r+2)-1-a      have hj0 : 2^r ≤ j := by dsimp [j]; omega      have hj1 : j < 2^(r+1) := by dsimp [j]; omega      have hi : a+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-j := by dsimp [j]; omega      have hx : x p (2^(M+1)-1-j) = true := by        simpa only [cycle_power_dyadic_outer_projection,if_neg hal,hi] using hxa      exact hshell r hr p j hj0 hj1 (Or.inr hx)  intro i hi  by_cases hil : i < 2^r  · simpa only [cycle_power_dyadic_outer_projection,if_pos hil] using (houter i hil).1  · let j := 2^(r+1)-1-i    have hj : j < 2^r := by dsimp [j]; omega    have he : i+2^(M+1)-2^(r+1)=2^(M+1)-1-j := by dsimp [j]; omega    simpa only [cycle_power_dyadic_outer_projection,if_neg hil,he] using (houter j hj).2
See it in the graphDiscuss this resultChallenge it