AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_outer_projection_fullness

theoremverified

A tight exact full-coverage model has no-island class shape if every selected middle bit at EVERY direct outer projection level forces the next prune to be full. Those all-scale fullness hypotheses remain explicit.

Statement

theorem cycle_power_dyadic_no_island_of_outer_projection_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)
    (hfull : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →
      cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) a = true →
      ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) 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 8
Used by 1

The proof, explained

The proof establishes that $x$ satisfies the no-island property on $[0, 2^{M+1})$ by showing that each row $x(p)$ is half-monotone (decreasing on $[0, 2^M)$ and increasing on $[2^M, 2^{M+1})$). It constructs the dyadic outer projection hierarchy $B(r, p)$ for $r \le M$, verifies that each level inherits the tight exact coverage model properties and satisfies the pruning relation, and applies hierarchy induction driven by the all-scale fullness hypothesis. Because the top-level outer projection at $r = M$ is $x$ itself, $x$ inherits half-monotonicity, which directly rules out any internal island of true bits.

  1. The family of outer projections $B(r, p)$ satisfies the tightness, exactness, and coverage model properties at every level $r \le M$.

    We define $B(r, p)$ as the outer projection of $x(p)$ from scale $M+1$ to scale $r$. Applying `cycle_power_dyadic_outer_projection_model` to the global hypotheses (tightness, exactness, and coverage) shows that for every scale $r \le M$, the projected configuration $B(r, \cdot)$ is a valid dyadic model at scale $r+1$.

    lines 17–18

    uses cycle_power_dyadic_outer_projection_model

      let B : ℕ → ℤ → ℕ → Bool := fun r p => cycle_power_dyadic_outer_projection (M+1) r (x p)
      have hmodel := fun r hr => cycle_power_dyadic_outer_projection_model M r hr x htight hexact hcover
  2. Each projection level $r < M$ is obtained from level $r+1$ by the dyadic pruning operation: $B(r, p, a) = \text{lift}_r(B(r+1, p))(a)$.

    We apply `cycle_power_dyadic_outer_projection_prune` with scale $M+1$ and level $r$, where the side condition $r+2 \le M+1$ follows from $r < M$ by linear integer arithmetic (`omega`). Evaluating both sides at $a$ with `congrFun` and taking symmetry gives the desired pointwise pruning identity.

    lines 19–22

    uses cycle_power_dyadic_outer_projection_prune, congrFun

      have hpr (r : ℕ) (hr : r < M) (p : ℤ) (a : ℕ) :
          B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a := by
        have hh := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p)
        exact (congrFun hh a).symm
  3. At every level $r \le M$, the projection $B(r, p)$ is half-monotone: decreasing on $[0, 2^r)$ and increasing on $[2^r, 2^{r+1})$.

    We invoke the hierarchy induction theorem `cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune`. Its premises—the model properties across all $r \le M$, the pruning consistency `hpr`, the middle-bit fullness condition `hfull`, and the trivial bound $M \le M$ (via `omega`)—are all satisfied, yielding half-monotonicity at all levels $r \le M$.

    lines 23–25

    uses cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune

      have hh := cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune M B
        (fun r hr => (hmodel r hr).1) (fun r hr => (hmodel r hr).2.1)
        (fun r hr => (hmodel r hr).2.2) hpr hfull M (by omega)
  4. The original configuration $x(p)$ is half-monotone: decreasing on $[0, 2^M)$ and increasing on $[2^M, 2^{M+1})$. automation

    By `cycle_power_dyadic_outer_projection_self`, projecting a sequence of length $2^{M+1}$ to level $M$ is the identity, so $B(M, p) = x(p)$. The `simpa` tactic unfolds $B$, rewrites with this identity, and specializes the hierarchy half-monotonicity result to level $r = M$.

    lines 26–30

    uses cycle_power_dyadic_outer_projection_self

      have hx : ∀ p : ℤ,
          (∀ a b : ℕ, a ≤ b → b < 2^M → x p b = true → x p a = true) ∧
          (∀ a b : ℕ, 2^M ≤ a → a ≤ b → b < 2^(M+1) →
            x p a = true → x p b = true) := by
        simpa only [B,cycle_power_dyadic_outer_projection_self] using hh
  5. The configuration $x$ satisfies the no-island property on $[0, 2^{M+1})$.

    Applying `cycle_power_no_island_of_half_monotone` with split point $H = 2^M$ and domain size $D = 2^{M+1}$ shows that any half-monotone boolean sequence cannot take the values false at $a$, true at $b$, and false at $c$ for $a < b < c < 2^{M+1}$.

    line 31

    uses cycle_power_no_island_of_half_monotone

      exact cycle_power_no_island_of_half_monotone (2^M) (2^(M+1)) x hx
cycle_power_dyadic_outer_projection_model
For any $r \le M$, the outer projection of a tight, exact, covering model of scale $M+1$ down to scale $r$ remains a tight, exact, covering model of scale $r+1$.
cycle_power_dyadic_outer_projection_prune
Pruning (lifting) the outer projection at scale $r+1$ of a sequence of length $2^m$ produces its outer projection at scale $r$, provided $r+2 \le m$.
congrFun
If two functions are equal, their values are equal at every input.
cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune
In a hierarchy of tight, exact, covering models satisfying the dyadic pruning relation, if every true middle bit at scale $r+1$ forces the pruned level $r$ to be identically true, then at every scale $r \le M$, the model is half-monotone (decreasing on $[0, 2^r)$ and increasing on $[2^r, 2^{r+1})$).
cycle_power_dyadic_outer_projection_self
The outer projection of a sequence of length $2^{r+1}$ down to level $r$ is the original sequence itself.
cycle_power_no_island_of_half_monotone
A boolean sequence on $[0, D)$ that is decreasing on $[0, H)$ and increasing on $[H, D)$ cannot take the values false at $a$, true at $b$, and false at $c$ for $a < b < c < D$.

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_outer_projection_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)    (hfull : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →      cycle_power_dyadic_outer_projection (M+1) (r+1) (x p) a = true →      ∀ i < 2^(r+1), cycle_power_dyadic_outer_projection (M+1) r (x p) 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  let B : ℕ → ℤ → ℕ → Bool := fun r p => cycle_power_dyadic_outer_projection (M+1) r (x p)  have hmodel := fun r hr => cycle_power_dyadic_outer_projection_model M r hr x htight hexact hcover  have hpr (r : ℕ) (hr : r < M) (p : ℤ) (a : ℕ) :      B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a := by    have hh := cycle_power_dyadic_outer_projection_prune (M+1) r (by omega) (x p)    exact (congrFun hh a).symm  have hh := cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune M B    (fun r hr => (hmodel r hr).1) (fun r hr => (hmodel r hr).2.1)    (fun r hr => (hmodel r hr).2.2) hpr hfull M (by omega)  have hx : ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^M → x p b = true → x p a = true) ∧      (∀ a b : ℕ, 2^M ≤ a → a ≤ b → b < 2^(M+1) →        x p a = true → x p b = true) := by    simpa only [B,cycle_power_dyadic_outer_projection_self] using hh  exact cycle_power_no_island_of_half_monotone (2^M) (2^(M+1)) x hx
See it in the graphDiscuss this resultChallenge it