AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_of_middle_full_prune

theoremverified

In a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no selected island between missing offsets. Smaller-scale fullness and active-count hypotheses are not assumed.

Statement

theorem cycle_power_dyadic_no_island_of_middle_full_prune
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =
      (range (2^(k+2))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1)
    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →
      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) :
    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) →
      x p a = false → x p b = true → x p c = true
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10

The proof, explained

The proof reduces the problem from scale k + 2 to scale k + 1 by considering the pruned lift y(p) = cycle_power_dyadic_b_lift k (x p). The pruned model inherits tightness, exactness, and ordinary cover, while middle-bit fullness converts the half-distance exact cover of the original model into a full class cover for y. Applying a classification theorem establishes that the pruned model is half-monotone, which lifts back to half-monotonicity of x at scale k + 2; from half-monotonicity, the absence of isolated true islands is immediate.

  1. The pruned model y at scale k + 1 inherits tightness, exactness, and the ordinary cover property from x.

    We define y(p) = cycle_power_dyadic_b_lift k (x p) as the pruned lift of each class at scale k + 1 (line 17). By cycle_power_dyadic_tight_class_prune, each class of y inherits tightness from the tightness of x at scale k + 2 (line 18). By cycle_power_dyadic_prune_exact, y inherits exactness for all scales j < k + 1 (line 19). By cycle_power_dyadic_prune_cover, the ordinary cover property for all distances 1 ≤ d < 2^(k + 1) transfers from x to y (line 20).

    lines 17–20

    uses cycle_power_dyadic_tight_class_prune, cycle_power_dyadic_prune_exact, cycle_power_dyadic_prune_cover

      let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)
      have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)
      have hye := cycle_power_dyadic_prune_exact k x hexact
      have hyc := cycle_power_dyadic_prune_cover k x htight hcover
  2. The pruned model y satisfies the full class cover property at scale k + 1.

    By cycle_power_dyadic_exact_half_cover, the exactness of x guarantees that every line v contains an active pair separated by distance 2^(k + 1) (line 22). Because this separation reaches into the middle range, cycle_power_dyadic_prune_full_class_cover_of_middle_fullness uses the middle-bit fullness hypothesis (hmid) to deduce that every line v intersects a class whose pruned lift is identically true across the entire range [0, 2^(k + 1)) (line 21).

    lines 21–22

    uses cycle_power_dyadic_prune_full_class_cover_of_middle_fullness, cycle_power_dyadic_exact_half_cover

      have hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid
        (cycle_power_dyadic_exact_half_cover k x hexact)
  3. The pruned model y is half-monotone at scale k + 1.

    With 1 ≤ k + 1 verified by linear arithmetic (omega on line 24), y satisfies all hypotheses of cycle_power_dyadic_half_monotone_of_full_class_cover: tightness (hyt), exactness (hye), ordinary cover (hyc), and full class cover (hyf). Therefore, for every class p, y(p) is decreasing on [0, 2^k) and increasing on [2^k, 2^(k + 1)) (line 23).

    lines 23–24

    uses cycle_power_dyadic_half_monotone_of_full_class_cover

      have hprev := cycle_power_dyadic_half_monotone_of_full_class_cover (k+1)
        (by omega) y hyt hye hyc hyf
  4. The pruned lift cycle_power_dyadic_b_lift k (x p) is explicitly decreasing on [0, 2^k) and increasing on [2^k, 2^(k + 1)).

    We unfold the definition of y and simplify the exponent (k + 1) - 1 to k using Nat.add_sub_cancel via simpa, restating the half-monotonicity directly in terms of the lift of x (lines 25–30).

    lines 25–30

    uses Nat.add_sub_cancel

      have hprev' : ∀ p : ℤ,
          (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →
            cycle_power_dyadic_b_lift k (x p) a = true) ∧
          (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →
            cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = true) := by
        simpa only [y, Nat.add_sub_cancel] using hprev
  5. For every class p and offsets a < b < c < 2^(k + 2), if x(p, a) = false and x(p, b) = true, then x(p, c) = true.

    Using cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono, the half-monotonicity of the pruned lift (hprev') combines with middle-bit fullness and the scale k + 2 properties to prove that x itself is half-monotone at scale k + 2, split at 2^(k + 1) (lines 32–33). Then cycle_power_no_island_of_half_monotone with threshold H = 2^(k + 1) and length D = 2^(k + 2) concludes that no class can possess an isolated true value: once a value becomes true after a false bit, all subsequent bits must remain true (line 31).

    lines 31–33

    uses cycle_power_no_island_of_half_monotone, cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono

      exact cycle_power_no_island_of_half_monotone (2^(k+1)) (2^(k+2)) x
        (cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono
          k x htight hexact hmid hcover hprev')
cycle_power_dyadic_tight_class_prune
If a class is tight at scale k + 2, its pruned lift at scale k is tight at scale k + 1.
cycle_power_dyadic_prune_exact
If a model is exact at scale k + 2, its pruned lift is exact at scale k + 1.
cycle_power_dyadic_prune_cover
If a model is tight and satisfies ordinary cover at scale k + 2, its pruned lift satisfies ordinary cover at scale k + 1.
cycle_power_dyadic_exact_half_cover
In an exact model at scale k + 2, every line contains a pair of active bits separated by distance 2^(k + 1).
cycle_power_dyadic_prune_full_class_cover_of_middle_fullness
In a model with middle-bit fullness and a half-distance cover, every line intersects a class whose pruned lift is identically true on all offsets up to 2^(k + 1).
cycle_power_dyadic_half_monotone_of_full_class_cover
A tight, exact model at scale m ≥ 1 with ordinary cover and full class cover is half-monotone (decreasing on [0, 2^(m - 1)) and increasing on [2^(m - 1), 2^m)).
Nat.add_sub_cancel
For natural numbers n and m, (n + m) - m = n.
cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono
If the pruned lift of a tight, exact, cover-satisfying model with middle-bit fullness is half-monotone at scale k + 1, then the model itself is half-monotone at scale k + 2.
cycle_power_no_island_of_half_monotone
A sequence that is decreasing on [0, H) and increasing on [H, D) cannot contain an isolated true bit between false bits: if a < b < c < D with x(a) = false and x(b) = true, then x(c) = true.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_no_island_of_middle_full_prune    (k : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =      (range (2^(k+2))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1)    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) →      x p a = false → x p b = true → x p c = true := by  let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)  have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)  have hye := cycle_power_dyadic_prune_exact k x hexact  have hyc := cycle_power_dyadic_prune_cover k x htight hcover  have hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid    (cycle_power_dyadic_exact_half_cover k x hexact)  have hprev := cycle_power_dyadic_half_monotone_of_full_class_cover (k+1)    (by omega) y hyt hye hyc hyf  have hprev' : ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →        cycle_power_dyadic_b_lift k (x p) a = true) ∧      (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →        cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = true) := by    simpa only [y, Nat.add_sub_cancel] using hprev  exact cycle_power_no_island_of_half_monotone (2^(k+1)) (2^(k+2)) x    (cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono      k x htight hexact hmid hcover hprev')
See it in the graphDiscuss this resultChallenge it