cycle_power_eight_block_gap_owner_transfer
Let t<s<q. Under prefix first eighths, the6q parent implications and exact6q/7q ownership, suppose root0 selects t andq+t but misses s, and edge(s,7q+t) is covered. Some u<s-t gives root s-q-u selecting q+u and7q+u but missing q+u-(s-t). Thus the new overlap gap is q-(s-t). This generalizes the accepted boundary transfer without assuming current4q exactness.
Statement
theorem cycle_power_eight_block_gap_owner_transfer (q t s : ℕ) (hq : 0 < q) (hts : t < s) (hsq : s < 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 t = true) (hchild : x 0 (q+t) = true) (hmiss : x 0 s = false) (hcover : ∃ a : ℕ, a < q+(s-t) ∧ x ((s : ℤ)-(a : ℤ)) a = true ∧ x ((s : ℤ)-(a : ℤ)) (a+7*q+t-s) = true) : ∃ u : ℕ, u < s-t ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u-(s-t)) = false
- 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 1
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- Used by 1
- cycle_power_eight_block_gap_owner_transfer_atTranslation of the accepted gap-owner transfer to any integer root, with full ordinary coverage supplying the required edge.
The proof, explained
The theorem proves that an overlap gap of size s - t at root 0 transfers to an overlap gap of size q - (s - t) at a shifted root s - q - u with u < s - t, using a covering pair for the edge between s and 7*q + t. The critical step is showing that the covering offset a satisfies a ≥ q, as any smaller offset would create a duplicate 6q-pair or 7q-pair, violating exact ownership. Setting u = a - q, the 6q parent implication ensures that root s - q - u selects both q + u and 7*q + u, while exact 7q-ownership forces it to miss q + u - (s - t).
Define the gap length L = s - t and establish the bounds 0 < L < q and t < q.
We introduce L = s - t. Given the hypotheses 0 < q, t < s, and s < q, linear integer arithmetic immediately yields 0 < L < q and t < q.
let L := s-t have hL₀ : 0 < L := by dsimp [L]; omega have hLq : L < q := by dsimp [L]; omega have htq : t < q := by omega
Root 0 selects 7*q + t.
Because root 0 selects the child q + t (hchild) and q ≤ q + t < 2*q, the second clause of the 6q parent implication (hparent) applies at root 0, giving x 0 (q + t + 6*q) = true, which simplifies to x 0 (7*q + t) = true.
have hB : x 0 (7*q+t) = true := by have h := (hparent 0 (q+t) (by omega)).2 (by omega) hchild convert h using 1 <;> congr 1 <;> omega
Rephrase the exact ownership conditions h6 and h7 to match cycle parameter 8*q.
We rewrite 6*q as 8*q - 2*q and 7*q as 8*q - q in the summation bounds. This puts the exact ownership hypotheses into the form required by cycle_power_exact_pair_unique with total cycle parameter D = 8*q and window R = 2*q or R = q.
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
Extract the covering offset a from the covering hypothesis.
From the hypothesis hcover, we obtain an offset a < q + L such that root s - a selects both a and a + 7*q + t - s.
obtain ⟨a, ha, ha₀, ha₁⟩ := hcoverIn the contradiction argument for q ≤ a, rule out the subcase a < L.
Assume for contradiction that a < q, and suppose first that a < L. Defining b = q - L + a, we have b < q and (q + t) - b = s - a. The second covering selection becomes x ((q + t) - b) (b + 6*q) = true. Since b < q, the first clause of the parent implication hparent gives x ((q + t) - b) b = true, so b is a 6q-pair for vertex q + t. However, root 0 already provides a 6q-pair for vertex q + t at offset q + t via hchild and the selection at 7*q + t. By uniqueness of 6q-pairs (cycle_power_exact_pair_unique), b = q + t. But b < q ≤ q + t, a contradiction.
uses
cycle_power_exact_pair_unique,sub_selfhave 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+t : ℕ) : ℤ)-(b : ℤ)=(s : ℤ)-(a : ℤ) := by dsimp [b,L]; omega have hi : b+6*q=a+7*q+t-s := by dsimp [b,L]; omega have hb₁ : x (((q+t : ℕ) : ℤ)-(b : ℤ)) (b+6*q) = true := by simpa only [hp,hi] using ha₁ have hb₀ := (hparent (((q+t : ℕ) : ℤ)-(b : ℤ)) b (by omega)).1 hbq hb₁ have huniq := cycle_power_exact_pair_unique (8*q) (2*q) x h6' ((q+t : ℕ) : ℤ) b (q+t) (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+t)+8*q-2*q=7*q+t by omega] using hB) omega
Rule out the remaining subcase a ≥ L, establishing q ≤ a.
In the remaining subcase L ≤ a < q, set b = a - L. Then b < q and t - b = s - a. Since b ≤ a < q, the prefix property hprefix gives x (t - b) b = true from the first covering selection, while the second covering selection gives x (t - b) (b + 7*q) = true. Hence b is a 7q-pair for vertex t. But offset t is also a 7q-pair for vertex t via hroot and x 0 (7*q + t) = true. By uniqueness of 7q-pairs (cycle_power_exact_pair_unique), b = t, which implies a = t + L = s. Substituting a = s into x (s - a) a = true gives x 0 s = true, contradicting hmiss (x 0 s = false). Both subcases of a < q are impossible, so q ≤ a.
uses
cycle_power_exact_pair_unique,sub_self· let b := a-L have hbq : b < q := by dsimp [b]; omega have hp : (t : ℤ)-(b : ℤ)=(s : ℤ)-(a : ℤ) := by dsimp [b,L]; omega have hb₀ : x ((t : ℤ)-(b : ℤ)) b = true := by have h := hprefix ((s : ℤ)-(a : ℤ)) b a (by dsimp [b]; omega) haq ha₀ simpa only [hp] using h have hb₁ : x ((t : ℤ)-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q+t-s := by dsimp [b,L]; omega simpa only [hp,hi] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (t : ℤ) b t hbq htq hb₀ (by simpa only [show b+8*q-q=b+7*q by omega] using hb₁) (by simpa only [sub_self] using hroot) (by simpa only [sub_self,show t+8*q-q=7*q+t by omega] using hB) have haeq : a=s := by dsimp [b,L] at huniq; omega subst a have hlow : x 0 s = true := by simpa only [sub_self] using ha₀ rw [hmiss] at hlow contradiction
Define the witness u = a - q and show that root s - q - u selects q + u and 7*q + u with u < s - t.
Setting u = a - q, the inequalities q ≤ a < q + (s - t) yield u < s - t and a = q + u. The first covering condition translates directly to x (s - q - u) (q + u) = true. Because q ≤ q + u < 2*q, the second clause of hparent upgrades this selection to x (s - q - u) (7*q + u) = true.
let u := a-q have hu : u < s-t := by dsimp [u]; omega have haeq : a=q+u := by dsimp [u]; omega have hp : (s : ℤ)-(a : ℤ)=(s : ℤ)-(q : ℤ)-(u : ℤ) := by omega have hC : x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true := by simpa only [← haeq,← hp] using ha₀ have hB' : x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true := by have h := (hparent ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) (by omega)).2 (by omega) hC convert h using 1 <;> congr 1 <;> omega
Show that root s - q - u misses q + u - (s - t), completing the witness u.
We provide u as the witness. It remains to show that x (s - q - u) (q + u - L) = false, which by Bool.eq_false_iff.mpr reduces to showing it cannot be true. If it were true, setting b = q + u - L gives t < b < q and t - b = s - q - u. The second covering condition then gives x (t - b) (b + 7*q) = true, making b a 7q-pair for vertex t. By uniqueness of 7q-pairs (cycle_power_exact_pair_unique), b = t. But this contradicts t < b. Therefore, root s - q - u misses q + u - (s - t).
uses
Bool.eq_false_iff.mpr,cycle_power_exact_pair_unique,sub_selfrefine ⟨u, hu, hC, hB', ?_⟩ apply Bool.eq_false_iff.mpr intro hA let b := q+u-L have hbt : t < b := by dsimp [b,L]; omega have hbq : b < q := by dsimp [b,L]; omega have hp' : (t : ℤ)-(b : ℤ)=(s : ℤ)-(q : ℤ)-(u : ℤ) := by dsimp [b,L]; omega have hb₁ : x ((t : ℤ)-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q+t-s := by dsimp [b,L]; omega simpa only [hp',hi,← hp] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (t : ℤ) b t hbq htq (by simpa only [hp',b,L] using hA) (by simpa only [show b+8*q-q=b+7*q by omega] using hb₁) (by simpa only [sub_self] using hroot) (by simpa only [sub_self,show t+8*q-q=7*q+t by omega] using hB) omega
cycle_power_exact_pair_unique- If an offset pair with separation D - R appears exactly once in the index range [0, R) for every vertex v, then any two such pairs for the same vertex v must have identical offsets.
sub_self- Subtracting an element from itself yields zero: a - a = 0.
Bool.eq_false_iff.mpr- A boolean value that is not true must be false.
- The reformulations h6' and h7' rewrite 6*q and 7*q as 8*q - 2*q and 8*q - q solely to match the generic parameter D - R in the uniqueness lemma cycle_power_exact_pair_unique.
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_gap_owner_transfer (q t s : ℕ) (hq : 0 < q) (hts : t < s) (hsq : s < 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 t = true) (hchild : x 0 (q+t) = true) (hmiss : x 0 s = false) (hcover : ∃ a : ℕ, a < q+(s-t) ∧ x ((s : ℤ)-(a : ℤ)) a = true ∧ x ((s : ℤ)-(a : ℤ)) (a+7*q+t-s) = true) : ∃ u : ℕ, u < s-t ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true ∧ x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u-(s-t)) = false := by let L := s-t have hL₀ : 0 < L := by dsimp [L]; omega have hLq : L < q := by dsimp [L]; omega have htq : t < q := by omega have hB : x 0 (7*q+t) = true := by have h := (hparent 0 (q+t) (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+t : ℕ) : ℤ)-(b : ℤ)=(s : ℤ)-(a : ℤ) := by dsimp [b,L]; omega have hi : b+6*q=a+7*q+t-s := by dsimp [b,L]; omega have hb₁ : x (((q+t : ℕ) : ℤ)-(b : ℤ)) (b+6*q) = true := by simpa only [hp,hi] using ha₁ have hb₀ := (hparent (((q+t : ℕ) : ℤ)-(b : ℤ)) b (by omega)).1 hbq hb₁ have huniq := cycle_power_exact_pair_unique (8*q) (2*q) x h6' ((q+t : ℕ) : ℤ) b (q+t) (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+t)+8*q-2*q=7*q+t by omega] using hB) omega · let b := a-L have hbq : b < q := by dsimp [b]; omega have hp : (t : ℤ)-(b : ℤ)=(s : ℤ)-(a : ℤ) := by dsimp [b,L]; omega have hb₀ : x ((t : ℤ)-(b : ℤ)) b = true := by have h := hprefix ((s : ℤ)-(a : ℤ)) b a (by dsimp [b]; omega) haq ha₀ simpa only [hp] using h have hb₁ : x ((t : ℤ)-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q+t-s := by dsimp [b,L]; omega simpa only [hp,hi] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (t : ℤ) b t hbq htq hb₀ (by simpa only [show b+8*q-q=b+7*q by omega] using hb₁) (by simpa only [sub_self] using hroot) (by simpa only [sub_self,show t+8*q-q=7*q+t by omega] using hB) have haeq : a=s := by dsimp [b,L] at huniq; omega subst a have hlow : x 0 s = true := by simpa only [sub_self] using ha₀ rw [hmiss] at hlow contradiction let u := a-q have hu : u < s-t := by dsimp [u]; omega have haeq : a=q+u := by dsimp [u]; omega have hp : (s : ℤ)-(a : ℤ)=(s : ℤ)-(q : ℤ)-(u : ℤ) := by omega have hC : x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true := by simpa only [← haeq,← hp] using ha₀ have hB' : x ((s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true := by have h := (hparent ((s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) (by omega)).2 (by omega) hC convert h using 1 <;> congr 1 <;> omega refine ⟨u, hu, hC, hB', ?_⟩ apply Bool.eq_false_iff.mpr intro hA let b := q+u-L have hbt : t < b := by dsimp [b,L]; omega have hbq : b < q := by dsimp [b,L]; omega have hp' : (t : ℤ)-(b : ℤ)=(s : ℤ)-(q : ℤ)-(u : ℤ) := by dsimp [b,L]; omega have hb₁ : x ((t : ℤ)-(b : ℤ)) (b+7*q) = true := by have hi : b+7*q=a+7*q+t-s := by dsimp [b,L]; omega simpa only [hp',hi,← hp] using ha₁ have huniq := cycle_power_exact_pair_unique (8*q) q x h7' (t : ℤ) b t hbq htq (by simpa only [hp',b,L] using hA) (by simpa only [show b+8*q-q=b+7*q by omega] using hb₁) (by simpa only [sub_self] using hroot) (by simpa only [sub_self,show t+8*q-q=7*q+t by omega] using hB) omega