AFTD Auto-Formalizing Theoretical Domains

cycle_power_eight_block_gap_owner_transfer

theoremverified

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
Used by 1

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).

  1. 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.

    lines 25–28

      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
  2. 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.

    lines 29–31

      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
  3. 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.

    lines 32–41

      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
  4. 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.

    line 42

      obtain ⟨a, ha, ha₀, ha₁⟩ := hcover
  5. In 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.

    lines 43–60

    uses cycle_power_exact_pair_unique, sub_self

      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
  6. 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.

    lines 61–79

    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
  7. 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.

    lines 80–89

      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
  8. 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).

    lines 90–106

    uses Bool.eq_false_iff.mpr, cycle_power_exact_pair_unique, sub_self

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it