cycle_power_dyadic_outer_quarter_monotone_of_eight_block_extension
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.
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.
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]
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`).
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 := hcoverThe 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)$.
uses
cycle_power_dyadic_tight_class_prune,cycle_power_dyadic_prune_exact,cycle_power_dyadic_prune_coverlet 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
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$.
uses
cycle_power_dyadic_exact_endpoints,cycle_power_dyadic_tight_class_parent,Nat.add_sub_cancelhave 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
$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)$.
uses
if_pos,if_neghave 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
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.
uses
Nat.succ_eq_add_onehave 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$.
- The proof is conditional on the unproved hypothesis `hstep`, which assumes the local eight-block extension property `cycle_power_eight_block_extension_at q` holds at every positive block size `q`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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