cycle_power_eight_block_boundary_owner_transfer
Let 0<L<q. Assume first eighths are prefixes, the6q parent implications hold, and6q/7q edges have exact owners. If root0 selects0 andq but missesL and edge(L,7q) is covered, some t<L gives root L-q-t selecting q+t and7q+t but missing q+t-L. The new gap between selected and missing compressed positions equals q-L.
Statement
theorem cycle_power_eight_block_boundary_owner_transfer (q L : ℕ) (hq : 0 < q) (hL₀ : 0 < L) (hLq : L < q) (x : ℤ → ℕ → Bool) (hprefix : ∀ p : ℤ, ∀ a b : ℕ, a ≤ b → b < q → x p b = true → x p a = true) (hparent : ∀ 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)) (h6 : ∀ v : ℤ, (range (2*q)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+6*q)).toNat) = 1) (h7 : ∀ v : ℤ, (range q).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+7*q)).toNat) = 1) (hroot : x 0 0 = true) (hchild : x 0 q = true) (hmiss : x 0 L = false) (hcover : ∃ a : ℕ, a < q+L ∧ x ((L : ℤ)-(a : ℤ)) a = true ∧ x ((L : ℤ)-(a : ℤ)) (a+7*q-L) = true) : ∃ t : ℕ, t < L ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) = true ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (7*q+t) = true ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t-L) = false
- 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 1
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
The proof, explained
The theorem transfers a missing position at root 0 to a new root along a covering edge for (L, 7q). By exact-pair uniqueness along each fiber, the covering index a < q + L cannot satisfy a < L (which would produce two 6q-edges on fiber q) nor L ≤ a < q (which would force a = L and contradict that position L is missing at root 0). Hence q ≤ a, so setting t = a - q < L identifies a new root L - q - t that selects q + t and, by the parent implication, 7q + t. Finally, assuming position q + t - L were also selected at this root would yield a second 7q-edge on fiber 0 with 0 < q + t - L < q, contradicting uniqueness and thereby proving that position q + t - L must be unselected.
At root 0, position 7q is selected (x 0 (7 * q) = true).
Since root 0 selects position q (by hypothesis hchild) and q ≤ q < 2q, the second clause of the parent implication hparent ensures that position q + 6q = 7q is also selected at root 0.
have hB : x 0 (7*q) = true := by have h := (hparent 0 q (by omega)).2 (by omega) hchild convert h using 1 <;> congr 1 <;> omega
The exactness assumptions h6 and h7 are rewritten into the difference form a + D - R with D = 8q, for R = 2q and R = q respectively.
To match the form required by cycle_power_exact_pair_unique, the sums over pairs (a, a + 6q) and (a, a + 7q) are rephrased as (a, a + 8q - 2q) and (a, a + 8q - q). Applying the index arithmetic identities a + 8q - 2q = a + 6q and a + 8q - q = a + 7q transforms h6 and h7 into the rewritten forms h6' and h7'.
have h6' : ∀ v : ℤ, (range (2*q)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-2*q)).toNat) = 1 := by intro v have hi (a : ℕ) : a+8*q-2*q=a+6*q := by omega simpa only [hi] using h6 v have h7' : ∀ v : ℤ, (range q).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-q)).toNat) = 1 := by intro v have hi (a : ℕ) : a+8*q-q=a+7*q := by omega simpa only [hi] using h7 v
Unpack the covering index a < q + L from hcover and show that it must satisfy q ≤ a.
From hcover we obtain an index a < q + L such that root L - a selects both a and a + 7q - L. To prove q ≤ a, we suppose for contradiction that a < q and split into two subcases: 1. If a < L, set b = q - L + a. Then b < q < 2q, the root q - b is equal to L - a, and b + 6q = a + 7q - L, so position b + 6q is selected at root q - b. Since b < q, the first clause of hparent implies that position b is also selected at root q - b. On fiber v = q, both b and q are indices below 2q whose 6q-edges are selected. By cycle_power_exact_pair_unique, b = q, which contradicts b = q - L + a < q. 2. If L ≤ a, set b = a - L. Then b < q and root -b equals L - a. Because b ≤ a < q and position a is selected at root -b, the prefix hypothesis hprefix implies that position b is selected at root -b. In addition, b + 7q = a + 7q - L is selected. On fiber v = 0, both b and 0 are indices below q whose 7q-edges are selected. By cycle_power_exact_pair_unique, b = 0, which implies a = L. But then root 0 selects position L, contradicting hmiss (x 0 L = false). Both subcases yield a contradiction, so q ≤ a.
uses
cycle_power_exact_pair_unique,sub_self,zero_sub,Nat.cast_zero,sub_zero,zero_addobtain ⟨a, ha, ha₀, ha₁⟩ := hcover have haq : q ≤ a := by by_contra hne have haq : a < q := by omega by_cases haL : a < L · let b := q-L+a have hbq : b < q := by dsimp [b]; omega have hp : (q : ℤ)-(b : ℤ)=(L : ℤ)-(a : ℤ) := by dsimp [b]; omega have hi : b+6*q=a+7*q-L := by dsimp [b]; omega have hb₁ : x ((q : ℤ)-(b : ℤ)) (b+6*q) = true := by simpa only [hp,hi] using ha₁ have hb₀ := (hparent ((q : ℤ)-(b : ℤ)) b (by omega)).1 hbq hb₁ have huniq := cycle_power_exact_pair_unique (8*q) (2*q) x h6' (q : ℤ) b q (by omega) (by omega) hb₀ (by convert hb₁ using 1 <;> congr 1 <;> omega) (by simpa only [sub_self] using hchild) (by simpa only [sub_self,show q+8*q-2*q=7*q by omega] using hB) omega · let b := a-L have hbq : b < q := by dsimp [b]; omega have hp : -(b : ℤ)=(L : ℤ)-(a : ℤ) := by dsimp [b]; omega have hb₀ : x (-(b : ℤ)) b = true := by have h := hprefix ((L : ℤ)-(a : ℤ)) b a (by dsimp [b]; omega) haq ha₀ simpa only [hp] using h have hb₁ : x (-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q-L := by dsimp [b]; omega simpa only [hp,hi] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (0 : ℤ) b 0 hbq hq (by simpa only [zero_sub] using hb₀) (by simpa only [zero_sub,show b+8*q-q=b+7*q by omega] using hb₁) (by simpa using hroot) (by simpa only [Nat.cast_zero,sub_zero,zero_add,show 8*q-q=7*q by omega] using hB) have haeq : a=L := by dsimp [b] at huniq; omega subst a have hlow : x 0 L = true := by simpa only [sub_self] using ha₀ rw [hmiss] at hlow contradiction
With t = a - q, we have t < L, and root L - q - t selects both q + t and 7q + t; supplying t as witness reduces the theorem to showing x (L - q - t) (q + t - L) = false.
Define t = a - q. Since q ≤ a < q + L, we have t < L and a = q + t. Identifying root L - a with L - q - t, the covering assumption gives x (L - q - t) (q + t) = true. Because q ≤ q + t < 2q, the parent implication hparent establishes that position (q + t) + 6q = 7q + t is also selected at root L - q - t. Supplying t, the bound t < L, and these two selections leaves only the final condition: position q + t - L must be unselected at root L - q - t.
let t := a-q have ht : t < L := by dsimp [t]; omega have haeq : a=q+t := by dsimp [t]; omega have hp : (L : ℤ)-(a : ℤ)=(L : ℤ)-(q : ℤ)-(t : ℤ) := by omega have hC : x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) = true := by simpa only [← haeq,← hp] using ha₀ have hB' : x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (7*q+t) = true := by have h := (hparent ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) (by omega)).2 (by omega) hC convert h using 1 <;> congr 1 <;> omega refine ⟨t, ht, hC, hB', ?_⟩
Position q + t - L is unselected at root L - q - t (x (L - q - t) (q + t - L) = false), completing the proof.
To show this Boolean value is false, we assume for contradiction that it is true. Let b = q + t - L. Since 0 < L < q and t < L, we have 0 < b < q. Notice that -(b : ℤ) = L - q - t and b + 7q = a + 7q - L. Thus root -b selects both position b (by the contradiction assumption) and position b + 7q (from the covering assumption). On fiber v = 0, both b and 0 are indices below q that satisfy the 7q-edge condition. Applying cycle_power_exact_pair_unique on fiber 0 forces b = 0, which contradicts 0 < b.
uses
Bool.eq_false_iff.mpr,cycle_power_exact_pair_unique,zero_sub,Nat.cast_zero,sub_zero,zero_addapply Bool.eq_false_iff.mpr intro hA let b := q+t-L have hb₀ : 0 < b := by dsimp [b]; omega have hbq : b < q := by dsimp [b]; omega have hp' : -(b : ℤ)=(L : ℤ)-(q : ℤ)-(t : ℤ) := by dsimp [b]; omega have hb₁ : x (-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q-L := by dsimp [b]; omega simpa only [hp',hi,← hp] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (0 : ℤ) b 0 hbq hq (by simpa only [zero_sub,hp',b] using hA) (by simpa only [zero_sub,show b+8*q-q=b+7*q by omega] using hb₁) (by simpa using hroot) (by simpa only [Nat.cast_zero,sub_zero,zero_add,show 8*q-q=7*q by omega] using hB) omega
cycle_power_exact_pair_unique- If along every fiber v, exactly one pair of positions (a, a + D - R) with a < R is simultaneously selected, then any two such selected pairs on fiber v must coincide (a = b).
sub_self- Subtracting an element from itself yields zero (a - a = 0).
zero_sub- Subtracting an element from zero gives its negation (0 - a = -a).
Nat.cast_zero- The canonical cast of the natural number 0 into an additive monoid with one is 0.
sub_zero- Subtracting zero leaves an element unchanged (a - 0 = a).
zero_add- Adding zero on the left leaves an element unchanged (0 + a = a).
Bool.eq_false_iff.mpr- A Boolean value that is not equal to true must be false.
- Linear arithmetic constraints on indices and coordinate shifts are discharged automatically by omega.
- Rewrites with lemmas such as zero_sub, sub_self, Nat.cast_zero, sub_zero, and zero_add are formal algebraic simplifications to identify shifted roots with 0.
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_eight_block_boundary_owner_transfer (q L : ℕ) (hq : 0 < q) (hL₀ : 0 < L) (hLq : L < q) (x : ℤ → ℕ → Bool) (hprefix : ∀ p : ℤ, ∀ a b : ℕ, a ≤ b → b < q → x p b = true → x p a = true) (hparent : ∀ 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)) (h6 : ∀ v : ℤ, (range (2*q)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+6*q)).toNat) = 1) (h7 : ∀ v : ℤ, (range q).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+7*q)).toNat) = 1) (hroot : x 0 0 = true) (hchild : x 0 q = true) (hmiss : x 0 L = false) (hcover : ∃ a : ℕ, a < q+L ∧ x ((L : ℤ)-(a : ℤ)) a = true ∧ x ((L : ℤ)-(a : ℤ)) (a+7*q-L) = true) : ∃ t : ℕ, t < L ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) = true ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (7*q+t) = true ∧ x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t-L) = false := by have hB : x 0 (7*q) = true := by have h := (hparent 0 q (by omega)).2 (by omega) hchild convert h using 1 <;> congr 1 <;> omega have h6' : ∀ v : ℤ, (range (2*q)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-2*q)).toNat) = 1 := by intro v have hi (a : ℕ) : a+8*q-2*q=a+6*q := by omega simpa only [hi] using h6 v have h7' : ∀ v : ℤ, (range q).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+8*q-q)).toNat) = 1 := by intro v have hi (a : ℕ) : a+8*q-q=a+7*q := by omega simpa only [hi] using h7 v obtain ⟨a, ha, ha₀, ha₁⟩ := hcover have haq : q ≤ a := by by_contra hne have haq : a < q := by omega by_cases haL : a < L · let b := q-L+a have hbq : b < q := by dsimp [b]; omega have hp : (q : ℤ)-(b : ℤ)=(L : ℤ)-(a : ℤ) := by dsimp [b]; omega have hi : b+6*q=a+7*q-L := by dsimp [b]; omega have hb₁ : x ((q : ℤ)-(b : ℤ)) (b+6*q) = true := by simpa only [hp,hi] using ha₁ have hb₀ := (hparent ((q : ℤ)-(b : ℤ)) b (by omega)).1 hbq hb₁ have huniq := cycle_power_exact_pair_unique (8*q) (2*q) x h6' (q : ℤ) b q (by omega) (by omega) hb₀ (by convert hb₁ using 1 <;> congr 1 <;> omega) (by simpa only [sub_self] using hchild) (by simpa only [sub_self,show q+8*q-2*q=7*q by omega] using hB) omega · let b := a-L have hbq : b < q := by dsimp [b]; omega have hp : -(b : ℤ)=(L : ℤ)-(a : ℤ) := by dsimp [b]; omega have hb₀ : x (-(b : ℤ)) b = true := by have h := hprefix ((L : ℤ)-(a : ℤ)) b a (by dsimp [b]; omega) haq ha₀ simpa only [hp] using h have hb₁ : x (-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q-L := by dsimp [b]; omega simpa only [hp,hi] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (0 : ℤ) b 0 hbq hq (by simpa only [zero_sub] using hb₀) (by simpa only [zero_sub,show b+8*q-q=b+7*q by omega] using hb₁) (by simpa using hroot) (by simpa only [Nat.cast_zero,sub_zero,zero_add,show 8*q-q=7*q by omega] using hB) have haeq : a=L := by dsimp [b] at huniq; omega subst a have hlow : x 0 L = true := by simpa only [sub_self] using ha₀ rw [hmiss] at hlow contradiction let t := a-q have ht : t < L := by dsimp [t]; omega have haeq : a=q+t := by dsimp [t]; omega have hp : (L : ℤ)-(a : ℤ)=(L : ℤ)-(q : ℤ)-(t : ℤ) := by omega have hC : x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) = true := by simpa only [← haeq,← hp] using ha₀ have hB' : x ((L : ℤ)-(q : ℤ)-(t : ℤ)) (7*q+t) = true := by have h := (hparent ((L : ℤ)-(q : ℤ)-(t : ℤ)) (q+t) (by omega)).2 (by omega) hC convert h using 1 <;> congr 1 <;> omega refine ⟨t, ht, hC, hB', ?_⟩ apply Bool.eq_false_iff.mpr intro hA let b := q+t-L have hb₀ : 0 < b := by dsimp [b]; omega have hbq : b < q := by dsimp [b]; omega have hp' : -(b : ℤ)=(L : ℤ)-(q : ℤ)-(t : ℤ) := by dsimp [b]; omega have hb₁ : x (-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q-L := by dsimp [b]; omega simpa only [hp',hi,← hp] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (0 : ℤ) b 0 hbq hq (by simpa only [zero_sub,hp',b] using hA) (by simpa only [zero_sub,show b+8*q-q=b+7*q by omega] using hb₁) (by simpa using hroot) (by simpa only [Nat.cast_zero,sub_zero,zero_add,show 8*q-q=7*q by omega] using hB) omega