cycle_power_dyadic_outer_eighth_corner
In a tight exact fully ordinarily covered dyadic model of radius2^(k+3), suppose all outer eighths are monotone. For every root p and cut1<=h<2^k, if offset h-1 is selected, then either offset h is selected too or root p+h selects offset2^(k+3)-h-1. Counts and periodicity are not assumed.
Statement
theorem cycle_power_dyadic_outer_eighth_corner (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) = (range (2^(k+3))).sum (fun a => (x p a).toNat)) (hexact : ∀ 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) (hcover : ∀ 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) (houter : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) → x p a = true → x p b = true)) : ∀ (p : ℤ) (h : ℕ), 1 ≤ h → h < 2^k → x p (h-1) = true → x p h = true ∨ x (p+(h : ℤ)) (2^(k+3)-h-1) = true
- Source
- Uniform structural helpers for OP-205 / RT-1, following arXiv:2610.15635. The new eight-block local extension remains unproved. These lemmas retain explicit shape/selected-missing hypotheses and do not settle any graph covering value; no research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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_no_island_cornerConditional uniform strong corner law for every cut of every dyadic radius in a tight two-interval full-cover model with exact dyadic…
The proof, explained
The proof reduces the dyadic model of scale $2^{k+3} = 8 \cdot 2^k$ to a model of scale $2^{k+1} = 2 \cdot 2^k$ by pruning it twice. This double pruning discards the middle six eighths, splicing the bottom eighth $[0, 2^k)$ and top eighth $[7 \cdot 2^k, 8 \cdot 2^k)$ together into a smaller model $z$. The model $z$ inherits tightness, exactness, and covering from $x$, while the assumed outer-eighth monotonicity of $x$ ensures that $z$ satisfies the no-island shape condition. Applying `cycle_power_dyadic_no_island_corner` to $z$ yields the corner alternative, which directly translates back to the outer eighths of $x$.
Letting $q = 2^k$, express the dyadic scales $2^{k+1}$, $2^{k+2}$, and $2^{k+3}$ as $2q$, $4q$, and $8q$ respectively, with $q > 0$.
We define $q = 2^k$ and note that $q > 0$ by `Nat.two_pow_pos`. Using the inductive step for powers $2^{n+1} = 2^n \cdot 2$ (`pow_succ`) and linear arithmetic (`omega`), we establish that $2^{k+1} = 2q$, $2^{k+2} = 4q$, and $2^{k+3} = 8q$.
uses
Nat.two_pow_pos,pow_succlet 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
Construct the twice-pruned model $z$ of scale $2^{k+1}$ from $x$ and verify that $z$ is tight, exact, and covered.
We apply the dyadic pruning operator `cycle_power_dyadic_b_lift (k+1)` to $x$, producing an intermediate model $y$ at scale $k+2$ that inherits tightness (`hyT`), exactness (`hyE`), and covering (`hyC`). A second application of pruning at parameter $k$ reduces $y$ to $z$ at scale $k+1$, which similarly inherits tightness (`hzT`), exactness (`hzE`), and covering (`hzC`) via `cycle_power_dyadic_tight_class_prune`, `cycle_power_dyadic_prune_exact`, and `cycle_power_dyadic_prune_cover`.
uses
cycle_power_dyadic_b_lift,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) let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p) have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p) have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p) have hzE := cycle_power_dyadic_prune_exact k y hyE have hzC := cycle_power_dyadic_prune_cover k y hyT hyC
The reduced model $z$ equals $x$ on the lower interval $[0, q)$ and equals $x$ shifted by $6q$ on $[q, 2q)$ (the top eighth $[7q, 8q)$ of $x$).
Unfolding `z`, `y`, and `cycle_power_dyadic_b_lift`, an offset $i < q$ satisfies the condition $i < 2^k$ and $i < 2^{k+1}$, selecting the identity branch at both pruning stages via `if_pos` (`hzLow`). An offset $q \le i < 2q$ takes the shifted branch at both stages via `if_neg`, shifting the offset by $2^{k+1} + 2^{k+2} = 2q + 4q = 6q$, so $z(p, i) = x(p, i + 6q)$ (`hzHigh`).
uses
cycle_power_dyadic_b_lift,if_pos,if_neghave hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_pos hi,if_pos (by omega)] have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) : z p i = x p (i+6*q) := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_neg (by omega),if_neg (by omega)] congr 1 omega
The model $z$ satisfies the shape (no-island) condition: if $a < b < c < 2^{k+1}$ with $z(p, a) = \text{false}$ and $z(p, b) = \text{true}$, then $z(p, c) = \text{true}$.
We split into cases on whether $b < q$. If $b < q$, then $a < b < q$, so both $a$ and $b$ lie in the first eighth $[0, q)$; by downward monotonicity of $x$ on $[0, q)$ (`houter`), $z(p, b) = \text{true}$ implies $z(p, a) = x(p, a) = \text{true}$, contradicting $z(p, a) = \text{false}$. If $b \ge q$, then $q \le b < c < 2q$, so $b$ and $c$ correspond to offsets $b+6q$ and $c+6q$ in the top eighth $[7q, 8q)$; by upward monotonicity of $x$ on $[7q, 8q)$ (`houter`), $z(p, b) = \text{true}$ implies $z(p, c) = x(p, c+6q) = \text{true}$.
have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) → z p a = false → z p b = true → z p c = true := by intro p a b c hab hbc hc ha hb by_cases hbq : b < q · have haq : a < q := by omega rw [hzLow p a haq] at ha rw [hzLow p b hbq] at hb have hh := (houter p).1 a b (by omega) hbq hb rw [ha] at hh contradiction · have hcb : q ≤ c := by omega rw [hzHigh p b (by omega) (by omega)] at hb rw [hzHigh p c hcb (by omega)] exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega) (by omega) (by omega) hb
For $1 \le h < q$, if $x(p, h-1) = \text{true}$, then either $z(p, h) = \text{true}$ or $z(p+h, 2^{k+1}-h-1) = \text{true}$.
Since $h - 1 < q$, $x(p, h-1) = \text{true}$ translates to $z(p, h-1) = \text{true}$ via `hzLow`. Because $z$ is tight, exact, covered, and satisfies the shape condition at scale $2^{k+1}$, applying `cycle_power_dyadic_no_island_corner` with cut $h < q < 2^{k+1}$ gives that either $z(p, h) = \text{true}$ or root $p+h$ selects the corner offset $2^{k+1}-h-1$ in $z$.
uses
cycle_power_dyadic_no_island_cornerintro p h hh₀ hh₁ hp have hpz : z p (h-1) = true := by simpa only [hzLow p (h-1) (by dsimp [q]; omega)] using hp have hc := cycle_power_dyadic_no_island_corner (k+1) z hzT hzE hzShape hzC p h hh₀ (by omega) hpz
Either $x(p, h) = \text{true}$ or $x(p+h, 2^{k+3}-h-1) = \text{true}$.
We case-split on the conclusion of `cycle_power_dyadic_no_island_corner`. If $z(p, h) = \text{true}$, then since $h < q$, `hzLow` gives $x(p, h) = \text{true}$, yielding the left disjunct via `Or.inl`. If $z(p+h, 2^{k+1}-h-1) = \text{true}$, then because $q \le 2^{k+1}-h-1 < 2q$, `hzHigh` rewrites this to $x(p+h, (2^{k+1}-h-1) + 6q)$; arithmetic simplifies this offset to $2^{k+3}-h-1$, yielding the right disjunct.
uses
Or.inlrcases hc with hc | hc · exact Or.inl (by simpa only [hzLow p h hh₁] using hc) · right rw [hzHigh (p+(h : ℤ)) (2^(k+1)-h-1) (by dsimp [q] at *; omega) (by omega)] at hc have he : 2^(k+1)-h-1+6*q=2^(k+3)-h-1 := by omega simpa only [he] using hc
Nat.two_pow_pos- For any natural number $w$, $2^w > 0$.
pow_succ- In any monoid, $a^{n+1} = a^n \cdot a$.
cycle_power_dyadic_b_lift- The dyadic pruning operation that keeps the bottom interval $[0, 2^k)$ unchanged and shifts the top interval $[2^k, 2^{k+1})$ by $2^{k+1}$, excising the middle.
cycle_power_dyadic_tight_class_prune- Pruning a tight configuration at scale $k+2$ yields a tight configuration at scale $k+1$.
cycle_power_dyadic_prune_exact- Pruning an exact model of scale $2^{k+2}$ preserves exactness at scale $2^{k+1}$.
cycle_power_dyadic_prune_cover- Pruning a tight, covered model of scale $2^{k+2}$ produces a covered model of scale $2^{k+1}$.
if_pos- If the branching condition is true, an `if-then-else` expression reduces to its 'then' branch.
if_neg- If the branching condition is false, an `if-then-else` expression reduces to its 'else' branch.
cycle_power_dyadic_no_island_corner- In a tight, exact, covered dyadic model of scale $2^m$ satisfying the no-island shape condition, if offset $h-1$ is selected at root $p$, then either offset $h$ is selected at $p$ or the complementary corner offset $2^m - h - 1$ is selected at root $p+h$.
Or.inl- From a proof of $A$, deduce the disjunction $A \lor B$.
- The proof relies on linear arithmetic (`omega`) to verify dyadic index bounds and power-of-two arithmetic, including the index identity $(2^{k+1} - h - 1) + 6 \cdot 2^k = 2^{k+3} - h - 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
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_eighth_corner (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) = (range (2^(k+3))).sum (fun a => (x p a).toNat)) (hexact : ∀ 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) (hcover : ∀ 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) (houter : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) → x p a = true → x p b = true)) : ∀ (p : ℤ) (h : ℕ), 1 ≤ h → h < 2^k → x p (h-1) = true → x p h = true ∨ x (p+(h : ℤ)) (2^(k+3)-h-1) = true := by 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 let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p) let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p) have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p) have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p) have hzE := cycle_power_dyadic_prune_exact k y hyE have hzC := cycle_power_dyadic_prune_cover k y hyT hyC have hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_pos hi,if_pos (by omega)] have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) : z p i = x p (i+6*q) := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_neg (by omega),if_neg (by omega)] congr 1 omega have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) → z p a = false → z p b = true → z p c = true := by intro p a b c hab hbc hc ha hb by_cases hbq : b < q · have haq : a < q := by omega rw [hzLow p a haq] at ha rw [hzLow p b hbq] at hb have hh := (houter p).1 a b (by omega) hbq hb rw [ha] at hh contradiction · have hcb : q ≤ c := by omega rw [hzHigh p b (by omega) (by omega)] at hb rw [hzHigh p c hcb (by omega)] exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega) (by omega) (by omega) hb intro p h hh₀ hh₁ hp have hpz : z p (h-1) = true := by simpa only [hzLow p (h-1) (by dsimp [q]; omega)] using hp have hc := cycle_power_dyadic_no_island_corner (k+1) z hzT hzE hzShape hzC p h hh₀ (by omega) hpz rcases hc with hc | hc · exact Or.inl (by simpa only [hzLow p h hh₁] using hc) · right rw [hzHigh (p+(h : ℤ)) (2^(k+1)-h-1) (by dsimp [q] at *; omega) (by omega)] at hc have he : 2^(k+1)-h-1+6*q=2^(k+3)-h-1 := by omega simpa only [he] using hc