AFTD Auto-Formalizing Theoretical Domains

cycle_power_eight_block_boundary_owner_transfer

theoremverified

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

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.

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

    lines 25–27

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

    lines 28–37

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

    lines 38–75

    uses cycle_power_exact_pair_unique, sub_self, zero_sub, Nat.cast_zero, sub_zero, zero_add

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

    lines 76–86

      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', ?_⟩
  5. 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.

    lines 87–102

    uses Bool.eq_false_iff.mpr, cycle_power_exact_pair_unique, zero_sub, Nat.cast_zero, sub_zero, zero_add

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

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