AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_end_shell_fullness_of_no_island

theoremverified

Conversely, no-island shape in a tight exact full-coverage dyadic model forces both complete dyadic end blocks whenever either next-shell offset is selected. Together with the converse theorem this is a flat structural characterization.

Statement

theorem cycle_power_dyadic_end_shell_fullness_of_no_island
    (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)
    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) →
      x p a = false → x p b = true → x p c = true) :
    ∀ 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
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 7
Used by 1

The proof, explained

The theorem establishes that in a tight, exact, full-coverage dyadic model satisfying the no-island condition, if either index in the (r+1)-st dyadic shell is selected in a fiber, then both complete dyadic end blocks of length 2^r (the prefix and the suffix) are completely true. The proof projects the fiber to scale r+1, which preserves tightness and the no-island condition. The selected index or its symmetric reflection lands in the middle range [2^r, 3 * 2^r) of this projection, where a middle-fullness lemma forces its dyadic lift to be identically true. Since pruning commutes with outer projection, this identifies the scale-r outer projection as identically true, which directly unfolds to fullness of both dyadic end blocks.

  1. Introduce parameters and establish dyadic exponent inequalities.

    Fix a scale r < M, a fiber p, an index a ∈ [2^r, 2^(r+1)), and assume that either x(p, a) = true or x(p, 2^(M+1) - 1 - a) = true. Since r < M, we have r + 2 ≤ M + 1, which implies 2^(r+2) ≤ 2^(M+1) by monotonicity of powers of 2 (Nat.pow_le_pow_right). The identities 2^(r+1) = 2 * 2^r and 2^(r+2) = 2 * 2^(r+1) follow from pow_succ.

    lines 17–20

    uses Nat.pow_le_pow_right, pow_succ

      intro r hr p a ha0 ha1 hx
      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
  2. The outer projection b of fiber x(p) to scale r+1 inherits tightness and the no-island shape.

    Define b to be the outer projection of fiber x(p) from dimension M+1 to scale r+1. Because r + 1 ≤ M, the projection preserves model tightness at dimension r+2 by cycle_power_dyadic_outer_projection_model. Furthermore, cycle_power_dyadic_outer_projection_no_island ensures that b inherits the no-island condition on [0, 2^(r+2)).

    lines 21–25

    uses cycle_power_dyadic_outer_projection_model, cycle_power_dyadic_outer_projection_no_island

      let b := cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)
      have htb : cycle_power_dyadic_class_weight (r+2) b =
          (range (2^(r+2))).sum (fun a => (b a).toNat) :=
        (cycle_power_dyadic_outer_projection_model M (r+1) (by omega) x htight hexact hcover).1 p
      have hsb := cycle_power_dyadic_outer_projection_no_island M (r+1) (by omega) (x p) (hshape p)
  3. The pruned dyadic lift of b at scale r is identically true on all indices below 2^(r+1).

    We split into cases depending on which offset in the hypothesis is true. If x(p, a) = true, then because a < 2^(r+1), the definition of outer projection gives b(a) = true by if_pos; since 2^r ≤ a < 3 * 2^r, cycle_power_dyadic_no_island_middle_imp_full_prune shows the lift is identically true. If x(p, 2^(M+1) - 1 - a) = true, setting j = 2^(r+2) - 1 - a yields an index with 2^(r+1) ≤ j < 3 * 2^r, and the outer projection gives b(j) = true by if_neg, so the same lemma forces the lift to be identically true.

    lines 26–39

    uses if_pos, cycle_power_dyadic_no_island_middle_imp_full_prune, if_neg

      have hbf : ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r b i = true := by
        rcases hx with hx | hx
        · have hba : b a = true := by
            simpa only [b,cycle_power_dyadic_outer_projection,if_pos ha1] using hx
          exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb a
            ha0 (by omega) hba
        · let j := 2^(r+2)-1-a
          have hj0 : 2^(r+1) ≤ j := by dsimp [j]; omega
          have hj1 : j < 3*2^r := by dsimp [j]; omega
          have hi : j+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-a := by dsimp [j]; omega
          have hbj : b j = true := by
            simpa only [b,cycle_power_dyadic_outer_projection,if_neg (by omega : ¬j<2^(r+1)),hi] using hx
          exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb j
            (by omega) hj1 hbj
  4. The outer projection of x(p) at scale r is identically true on [0, 2^(r+1)).

    By cycle_power_dyadic_outer_projection_prune, the dyadic lift of the scale-(r+1) projection at scale r equals the scale-r outer projection. Applying this rewrite to the fullness established in the previous step shows that the outer projection at scale r is true at every i < 2^(r+1).

    lines 40–46

    uses cycle_power_dyadic_outer_projection_prune

      have he := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p)
      have hproj : ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true := by
        intro i hi
        have hh := hbf i hi
        change cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)) i = true at hh
        rw [he] at hh
        exact hh
  5. Both dyadic end blocks of length 2^r in x(p) are completely true.

    For any index i < 2^r, we evaluate the scale-r outer projection. For the prefix, i < 2^r, so if_pos reduces the projection at i directly to x(p, i) = true. For the suffix, setting j = 2^(r+1) - 1 - i satisfies 2^r ≤ j < 2^(r+1), so if_neg evaluates the projection at j to x(p, j + 2^(M+1) - 2^(r+1)) = x(p, 2^(M+1) - 1 - i) = true. Therefore, both x(p, i) and x(p, 2^(M+1) - 1 - i) are true.

    lines 47–54

    uses if_pos, if_neg

      intro i hi
      constructor
      · simpa only [cycle_power_dyadic_outer_projection,if_pos hi] using hproj i (by omega)
      · let j := 2^(r+1)-1-i
        have hj : j < 2^(r+1) := by dsimp [j]; omega
        have hjq : ¬j < 2^r := by dsimp [j]; omega
        have hi' : j+2^(M+1)-2^(r+1)=2^(M+1)-1-i := by dsimp [j]; omega
        simpa only [cycle_power_dyadic_outer_projection,if_neg hjq,hi'] using hproj j hj
Nat.pow_le_pow_right
For any positive base n and exponents i ≤ j, n^i ≤ n^j.
pow_succ
The (n+1)-st power of a equals a^n * a.
cycle_power_dyadic_outer_projection_model
Outer projection of a tight, exact, full-coverage dyadic model from scale M+1 to scale r ≤ M preserves tightness, exactness, and full coverage at scale r+1.
cycle_power_dyadic_outer_projection_no_island
The outer projection of a sequence satisfying the no-island property also satisfies the no-island property.
cycle_power_dyadic_no_island_middle_imp_full_prune
In a tight model of dimension k+2 satisfying the no-island shape condition, having any true bit in the middle range [2^k, 3 * 2^k) forces the dyadic pruned lift at scale k to be true everywhere on [0, 2^(k+1)).
cycle_power_dyadic_outer_projection_prune
Pruning (lifting) an outer projection of scale r+1 at scale r recovers the outer projection at scale r.
if_pos
An if-then-else expression evaluates to the then-branch when the condition holds.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.

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_end_shell_fullness_of_no_island    (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)    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(M+1) →      x p a = false → x p b = true → x p c = true) :    ∀ 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 := by  intro r hr p a ha0 ha1 hx  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  let b := cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)  have htb : cycle_power_dyadic_class_weight (r+2) b =      (range (2^(r+2))).sum (fun a => (b a).toNat) :=    (cycle_power_dyadic_outer_projection_model M (r+1) (by omega) x htight hexact hcover).1 p  have hsb := cycle_power_dyadic_outer_projection_no_island M (r+1) (by omega) (x p) (hshape p)  have hbf : ∀ i < 2^(r+1), cycle_power_dyadic_b_lift r b i = true := by    rcases hx with hx | hx    · have hba : b a = true := by        simpa only [b,cycle_power_dyadic_outer_projection,if_pos ha1] using hx      exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb a        ha0 (by omega) hba    · let j := 2^(r+2)-1-a      have hj0 : 2^(r+1) ≤ j := by dsimp [j]; omega      have hj1 : j < 3*2^r := by dsimp [j]; omega      have hi : j+2^(M+1)-2^((r+1)+1)=2^(M+1)-1-a := by dsimp [j]; omega      have hbj : b j = true := by        simpa only [b,cycle_power_dyadic_outer_projection,if_neg (by omega : ¬j<2^(r+1)),hi] using hx      exact cycle_power_dyadic_no_island_middle_imp_full_prune r b htb hsb j        (by omega) hj1 hbj  have he := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p)  have hproj : ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) i = true := by    intro i hi    have hh := hbf i hi    change cycle_power_dyadic_b_lift r (cycle_power_dyadic_outer_projection (M+1) (r+1) (x p)) i = true at hh    rw [he] at hh    exact hh  intro i hi  constructor  · simpa only [cycle_power_dyadic_outer_projection,if_pos hi] using hproj i (by omega)  · let j := 2^(r+1)-1-i    have hj : j < 2^(r+1) := by dsimp [j]; omega    have hjq : ¬j < 2^r := by dsimp [j]; omega    have hi' : j+2^(M+1)-2^(r+1)=2^(M+1)-1-i := by dsimp [j]; omega    simpa only [cycle_power_dyadic_outer_projection,if_neg hjq,hi'] using hproj j hj
See it in the graphDiscuss this resultChallenge it