AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_quarter_monotone_of_eight_block_extension

theoremverified

Assuming the local eight-block extension predicate at every positive block size, every tight exact fully ordinarily covered dyadic model has initial first quarters and terminal last quarters. The extension principle is an explicit unproved hypothesis, so this is a conditional reduction of target I.

Statement

theorem cycle_power_dyadic_outer_quarter_monotone_of_eight_block_extension
    (hstep : ∀ q : ℕ, 0 < q → cycle_power_eight_block_extension_at q)
    (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)
    (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 : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧
      (∀ a b : ℕ, 3*2^k ≤ a → a ≤ b → b < 2^(k+2) →
        x p a = true → x p b = true)
Source
Uniform local structural route for OP-205 / RT-1, following arXiv:2610.15635. The Boolean eight-block extension remains conjectured; the induction result keeps it as an explicit hypothesis. Finite guarded computations are evidence only, and no graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • cycle_power_eight_block_extension_atThe local Boolean extension predicate at block size q: for every integer rooted-profile model of radius8q, selected endpoints, parent…
  • cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
  • cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
  • cycle_power_dyadic_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
  • cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
  • cycle_power_dyadic_prune_exactDeleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class…
  • cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
  • cycle_power_dyadic_exact_endpointsExact ownership of all dyadic distances in a radius-2^m model with positive exponent forces both endpoints of every rooted class to be…

The proof, explained

The theorem is proved by induction on $k$. The base case $k = 0$ holds vacuously because in a configuration of length $4$, the first quarter $[0, 1)$ and terminal quarter $[3, 4)$ each contain at most a single index. In the inductive step, setting $q = 2^k$, we prune the middle half of the dyadic configuration of length $8q$ down to length $4q$, which preserves tightness, exactness, and coverage. The induction hypothesis on this pruned model establishes monotonicity on the outermost eighths, $[0, q)$ and $[7q, 8q)$. Finally, assuming the eight-block extension predicate at scale $q$, this outer monotonicity extends to the full first and fourth quarters, $[0, 2q)$ and $[6q, 8q)$, completing the reduction.

  1. In the base case $k = 0$, both monotonicity conditions hold vacuously.

    We proceed by induction on $k$. For $k = 0$, the domain has length $2^{0+2} = 4$. The first quarter consists of indices $b < 2^0 = 1$, so $a \le b$ forces $a = b = 0$, making the downward-closure condition trivial. The fourth quarter consists of indices $3 \cdot 2^0 \le a \le b < 2^2 = 4$, which forces $a = b = 3$, so the upward-closure condition holds trivially as well.

    lines 19–28

      induction k generalizing x with
      | zero =>
        intro p
        constructor
        · intro a b hab hb hx
          have he : a=b := by norm_num at hb; omega
          rwa [he]
        · intro a b ha hab hb hx
          have he : a=b := by norm_num at ha hb; omega
          rwa [← he]
  2. In the inductive step, set $q = 2^k$ and express powers of 2 and hypotheses at scale $k+3$ in terms of $q$.

    For the induction step from $k$ to $k+1$, we set $q = 2^k > 0$. The powers of 2 at the relevant dyadic scales are $2^{k+1} = 2q$, $2^{k+2} = 4q$, and $2^{k+3} = 8q$. We record the given hypotheses at scale $(k+1)+2 = k+3$: tightness of the dyadic class weight (`ht`), exactness of inner products at all scales $j < k+3$ (`he`), and coverage for all positive distances $d < 8q$ (`hc`).

    lines 29–41

    uses Nat.two_pow_pos, pow_succ

      | succ k ih =>
        let q := 2^k
        have hq : 0 < q := Nat.two_pow_pos _
        have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega
        have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega
        have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega
        have ht : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) =
          (range (2^(k+3))).sum (fun a => (x p a).toNat) := htight
        have he : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a =>
          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1 := hexact
        have hc : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ,
          ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧
            x (v-(a : ℤ)) (a+d) = true := hcover
  3. The induction hypothesis applies to the pruned configuration $y$, yielding outer monotonicity at scale $q$.

    We define the pruned configuration $y$ by cutting out the middle half of $x$ using `cycle_power_dyadic_b_lift` at scale $k+1$, halving the length from $8q$ to $4q = 2^{k+2}$. Tightness, exactness, and coverage all transfer to $y$ via `cycle_power_dyadic_tight_class_prune`, `cycle_power_dyadic_prune_exact`, and `cycle_power_dyadic_prune_cover`. The induction hypothesis applied to $y$ establishes that $y(p)$ is monotone decreasing on $[0, q)$ and monotone increasing on $[3q, 4q)$.

    lines 42–46

    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+1) (x p)
        have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (ht p)
        have hyE := cycle_power_dyadic_prune_exact (k+1) x he
        have hyC := cycle_power_dyadic_prune_cover (k+1) x ht hc
        have hy := ih y hyT hyE hyC
  4. The endpoints, parent relations at scales $4q$ and $2q$, and exactness sums at scales $q, 2q, 4q$ all hold for $x$.

    We verify the structural conditions required by the eight-block extension predicate at scale $q$: endpoints are true at $0$ and $8q - 1$ by `cycle_power_dyadic_exact_endpoints`; tightness implies parent-child implications across offset $4q$ (for $j = k+2$) and across offset $6q$ (for $j = k+1$) by `cycle_power_dyadic_tight_class_parent`; and the exactness sums for block lengths $L \in \{q, 2q, 4q\}$ hold directly from the hypothesis `he` evaluated at $j = k, k+1, k+2$.

    lines 47–75

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_tight_class_parent, Nat.add_sub_cancel

        have hs := hstep q hq x
        have hends : ∀ p, x p 0 = true ∧ x p (8*q-1) = true := by
          simpa only [hP₃] using cycle_power_dyadic_exact_endpoints (k+3) (by omega) x he
        have hp4 : ∀ p a, a < 4*q →
            (a < 2*q → x p (a+4*q) = true → x p a = true) ∧
            (2*q ≤ a → x p a = true → x p (a+4*q) = true) := by
          intro p a ha
          have hh := cycle_power_dyadic_tight_class_parent (k+3) (k+2)
            (by omega) (by omega) (x p) (ht p) a (by simpa only [hP₂] using ha)
          have hp : 2^(k+2-1)=2*q := by simpa only [show k+2-1=k+1 by omega] using hP₁
          have hi : a+8*q-4*q=a+4*q := by omega
          simpa only [hp,hP₃,hP₂,hi] using hh
        have hp6 : ∀ p a, a < 2*q →
            (a < q → x p (a+6*q) = true → x p a = true) ∧
            (q ≤ a → x p a = true → x p (a+6*q) = true) := by
          intro p a ha
          have hh := cycle_power_dyadic_tight_class_parent (k+3) (k+1)
            (by omega) (by omega) (x p) (ht p) a (by simpa only [hP₁] using ha)
          have hp : 2^(k+1-1)=q := by simp only [Nat.add_sub_cancel]; rfl
          have hi : a+8*q-2*q=a+6*q := by omega
          simpa only [hp,hP₃,hP₁,hi] using hh
        have hEx : ∀ L : ℕ, (L=q ∨ L=2*q ∨ L=4*q) → ∀ v : ℤ,
            (range L).sum (fun a =>
              (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-L)).toNat) = 1 := by
          intro L hL v
          rcases hL with rfl | rfl | rfl
          · simpa only [hP₃] using he k (by omega) v
          · simpa only [hP₃,hP₁] using he (k+1) (by omega) v
          · simpa only [hP₃,hP₂] using he (k+2) (by omega) v
  5. $x(p)$ is monotone decreasing on the first eighth $[0, q)$ and monotone increasing on the eighth eighth $[7q, 8q)$.

    We pull back the monotonicity of $y(p)$ obtained from the induction hypothesis to $x(p)$. For $b < q < 2^{k+1}$, `cycle_power_dyadic_b_lift` leaves $x(p, b)$ unchanged, so $x(p)$ is decreasing on $[0, q)$. For indices in the last eighth $7q \le a \le b < 8q$, shifting by $4q$ places them in $[3q, 4q) \subseteq [2^{k+1}, 2^{k+2})$, where `cycle_power_dyadic_b_lift` samples from $x(p, \cdot + 4q)$. The monotonicity of $y(p)$ on $[3q, 4q)$ thus implies monotonicity of $x(p)$ on $[7q, 8q)$.

    lines 76–99

    uses if_pos, if_neg

        have hOut : ∀ p : ℤ,
            (∀ a b : ℕ, a ≤ b → b < q → x p b = true → x p a = true) ∧
            (∀ a b : ℕ, 7*q ≤ a → a ≤ b → b < 8*q →
              x p a = true → x p b = true) := by
          intro p
          constructor
          · intro a b hab hb hx
            have hb' : y p b = true := by
              dsimp [y,cycle_power_dyadic_b_lift]
              rw [if_pos (by omega)]
              exact hx
            have ha' := (hy p).1 a b hab hb hb'
            dsimp [y,cycle_power_dyadic_b_lift] at ha'
            rwa [if_pos (by omega)] at ha'
          · intro a b ha hab hb hx
            have ha' : y p (a-4*q) = true := by
              dsimp [y,cycle_power_dyadic_b_lift]
              rw [if_neg (by omega)]
              convert hx using 1 <;> congr 1 <;> omega
            have hb' := (hy p).2 (a-4*q) (b-4*q) (by dsimp [q] at *; omega)
              (by omega) (by omega) ha'
            dsimp [y,cycle_power_dyadic_b_lift] at hb'
            rw [if_neg (by omega)] at hb'
            convert hb' using 1 <;> congr 1 <;> omega
  6. The eight-block extension predicate extends monotonicity to the outer quarters $[0, 2q)$ and $[6q, 8q)$, completing the induction.

    Coverage for distances $d < 8q$ follows immediately from `hc`. With endpoints, parent relations, exactness sums, outermost-eighth monotonicity, and coverage all verified, applying the assumed eight-block extension predicate `hstep q hq x` yields monotonicity of $x(p)$ on the first quarter $[0, 2q) = [0, 2^{k+1})$ and terminal quarter $[6q, 8q) = [3 \cdot 2^{k+1}, 2^{k+3})$. Simplifying the bounds closes the successor goal.

    lines 100–106

    uses Nat.succ_eq_add_one

        have hCov : ∀ d : ℕ, 1 ≤ d → d < 8*q → ∀ v : ℤ,
            ∃ a : ℕ, a < 8*q-d ∧ x (v-(a : ℤ)) a = true ∧
              x (v-(a : ℤ)) (a+d) = true := by simpa only [hP₃] using hc
        have hres := hs hends hp4 hp6 hEx hOut hCov
        have hLast : 3*2^(k+1)=6*q := by rw [hP₁]; omega
        have hLast' : 3*(2*q)=6*q := by omega
        simpa only [Nat.succ_eq_add_one,show k+1+2=k+3 by omega,hP₁,hP₃,hLast'] using hres
Nat.two_pow_pos
Every power of 2 is strictly positive: $2^w > 0$ for all natural numbers $w$.
pow_succ
The power successor rule in any monoid: $a^{n+1} = a^n \cdot a$.
cycle_power_dyadic_tight_class_prune
Pruning the middle half of a tight dyadic configuration at scale $k+2$ yields a tight configuration at scale $k+1$.
cycle_power_dyadic_prune_exact
Pruning the middle half of an exact dyadic configuration at scale $k+2$ yields an exact configuration at scale $k+1$.
cycle_power_dyadic_prune_cover
Pruning the middle half of a tight, covered dyadic configuration at scale $k+2$ yields a covered configuration at scale $k+1$.
cycle_power_dyadic_exact_endpoints
In an exact dyadic configuration of positive scale $m$, the endpoints at $0$ and $2^m - 1$ both evaluate to true.
cycle_power_dyadic_tight_class_parent
In a tight dyadic configuration of scale $m$, indices below $2^j$ satisfy parent-child implication constraints with $a + 2^m - 2^j$, split at $2^{j-1}$.
Nat.add_sub_cancel
Subtracting $m$ from $n + m$ returns $n$.
if_pos
When the condition $c$ is true, the expression `if c then t else e` evaluates to $t$.
if_neg
When the condition $c$ is false, the expression `if c then t else e` evaluates to $e$.
Nat.succ_eq_add_one
The successor of a natural number $n$ equals $n + 1$.

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_outer_quarter_monotone_of_eight_block_extension    (hstep : ∀ q : ℕ, 0 < q → cycle_power_eight_block_extension_at q)    (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)    (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 : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧      (∀ a b : ℕ, 3*2^k ≤ a → a ≤ b → b < 2^(k+2) →        x p a = true → x p b = true) := by  induction k generalizing x with  | zero =>    intro p    constructor    · intro a b hab hb hx      have he : a=b := by norm_num at hb; omega      rwa [he]    · intro a b ha hab hb hx      have he : a=b := by norm_num at ha hb; omega      rwa [← he]  | succ k ih =>    let q := 2^k    have hq : 0 < q := Nat.two_pow_pos _    have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega    have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega    have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega    have ht : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) =      (range (2^(k+3))).sum (fun a => (x p a).toNat) := htight    have he : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1 := hexact    have hc : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true := hcover    let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p)    have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (ht p)    have hyE := cycle_power_dyadic_prune_exact (k+1) x he    have hyC := cycle_power_dyadic_prune_cover (k+1) x ht hc    have hy := ih y hyT hyE hyC    have hs := hstep q hq x    have hends : ∀ p, x p 0 = true ∧ x p (8*q-1) = true := by      simpa only [hP₃] using cycle_power_dyadic_exact_endpoints (k+3) (by omega) x he    have hp4 : ∀ p a, a < 4*q →        (a < 2*q → x p (a+4*q) = true → x p a = true) ∧        (2*q ≤ a → x p a = true → x p (a+4*q) = true) := by      intro p a ha      have hh := cycle_power_dyadic_tight_class_parent (k+3) (k+2)        (by omega) (by omega) (x p) (ht p) a (by simpa only [hP₂] using ha)      have hp : 2^(k+2-1)=2*q := by simpa only [show k+2-1=k+1 by omega] using hP₁      have hi : a+8*q-4*q=a+4*q := by omega      simpa only [hp,hP₃,hP₂,hi] using hh    have hp6 : ∀ p a, a < 2*q →        (a < q → x p (a+6*q) = true → x p a = true) ∧        (q ≤ a → x p a = true → x p (a+6*q) = true) := by      intro p a ha      have hh := cycle_power_dyadic_tight_class_parent (k+3) (k+1)        (by omega) (by omega) (x p) (ht p) a (by simpa only [hP₁] using ha)      have hp : 2^(k+1-1)=q := by simp only [Nat.add_sub_cancel]; rfl      have hi : a+8*q-2*q=a+6*q := by omega      simpa only [hp,hP₃,hP₁,hi] using hh    have hEx : ∀ L : ℕ, (L=q ∨ L=2*q ∨ L=4*q) → ∀ v : ℤ,        (range L).sum (fun a =>          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-L)).toNat) = 1 := by      intro L hL v      rcases hL with rfl | rfl | rfl      · simpa only [hP₃] using he k (by omega) v      · simpa only [hP₃,hP₁] using he (k+1) (by omega) v      · simpa only [hP₃,hP₂] using he (k+2) (by omega) v    have hOut : ∀ p : ℤ,        (∀ a b : ℕ, a ≤ b → b < q → x p b = true → x p a = true) ∧        (∀ a b : ℕ, 7*q ≤ a → a ≤ b → b < 8*q →          x p a = true → x p b = true) := by      intro p      constructor      · intro a b hab hb hx        have hb' : y p b = true := by          dsimp [y,cycle_power_dyadic_b_lift]          rw [if_pos (by omega)]          exact hx        have ha' := (hy p).1 a b hab hb hb'        dsimp [y,cycle_power_dyadic_b_lift] at ha'        rwa [if_pos (by omega)] at ha'      · intro a b ha hab hb hx        have ha' : y p (a-4*q) = true := by          dsimp [y,cycle_power_dyadic_b_lift]          rw [if_neg (by omega)]          convert hx using 1 <;> congr 1 <;> omega        have hb' := (hy p).2 (a-4*q) (b-4*q) (by dsimp [q] at *; omega)          (by omega) (by omega) ha'        dsimp [y,cycle_power_dyadic_b_lift] at hb'        rw [if_neg (by omega)] at hb'        convert hb' using 1 <;> congr 1 <;> omega    have hCov : ∀ d : ℕ, 1 ≤ d → d < 8*q → ∀ v : ℤ,        ∃ a : ℕ, a < 8*q-d ∧ x (v-(a : ℤ)) a = true ∧          x (v-(a : ℤ)) (a+d) = true := by simpa only [hP₃] using hc    have hres := hs hends hp4 hp6 hEx hOut hCov    have hLast : 3*2^(k+1)=6*q := by rw [hP₁]; omega    have hLast' : 3*(2*q)=6*q := by omega    simpa only [Nat.succ_eq_add_one,show k+1+2=k+3 by omega,hP₁,hP₃,hLast'] using hres
See it in the graphDiscuss this resultChallenge it