AFTD Auto-Formalizing Theoretical Domains

cycle_power_eight_block_gap_owner_transfer_at

theoremverified

Translation of the accepted gap-owner transfer to any integer root, with full ordinary coverage supplying the required edge.

Statement

theorem cycle_power_eight_block_gap_owner_transfer_at
    (q t s : ℕ) (hq : 0 < q) (hts : t < s) (hsq : s < q)
    (x : ℤ → ℕ → Bool) (p : ℤ)
    (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)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 8*q → ∀ v : ℤ,
      ∃ a : ℕ, a < 8*q-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)
    (hroot : x p t = true) (hchild : x p (q+t) = true) (hmiss : x p s = false) :
    ∃ u : ℕ, u < s-t ∧
      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true ∧
      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true ∧
      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u-(s-t)) = false
Source
Supporting uniform structural route for OP-205 / RT-1 following arXiv:2610.15635. No unconditional shape theorem or main covering result is claimed. No advance flag.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem generalizes the gap-owner transfer result from the origin to an arbitrary integer root p, using a uniform coverage assumption to supply the necessary coverage edge. The proof defines a translated grid y(r, a) = x(p + r, a), verifies that y inherits the prefix, parent, diagonal-sum, and coverage hypotheses, and then invokes cycle_power_eight_block_gap_owner_transfer on y at root 0. Translating the resulting certificate back from y to x yields the desired gap-owner property for x.

  1. Define the translated grid y(r, a) = x(p + r, a).

    To reduce the theorem for an arbitrary integer root p to the known case at 0, we define y by shifting the first argument of x by p.

    line 23

      let y : ℤ → ℕ → Bool := fun r a => x (p+r) a
  2. The 6-step diagonal sum condition holds for y.

    For any integer v, evaluating the 6-step diagonal sum hypothesis h6 at p + v and rewriting the first index using associativity of addition and subtraction (add_sub_assoc) verifies that the diagonal sum for y at v equals 1.

    lines 24–27

    uses add_sub_assoc

      have he6 : ∀ v : ℤ, (range (2*q)).sum (fun a =>
          (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+6*q)).toNat) = 1 := by
        intro v
        simpa only [y, add_sub_assoc] using h6 (p+v)
  3. The 7-step diagonal sum condition holds for y.

    Similarly, evaluating the 7-step diagonal sum hypothesis h7 at p + v and using add_sub_assoc establishes that the 7-step sum for y at v equals 1.

    lines 28–31

    uses add_sub_assoc

      have he7 : ∀ v : ℤ, (range q).sum (fun a =>
          (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+7*q)).toNat) = 1 := by
        intro v
        simpa only [y, add_sub_assoc] using h7 (p+v)
  4. There exists an index a < q + (s - t) such that y(s - a, a) = true and y(s - a, a + 7*q + t - s) = true.

    We instantiate the general coverage hypothesis hcover with distance d = 7*q + t - s and base diagonal p + s. Linear arithmetic (omega) verifies that 1 ≤ d < 8*q (from 0 < q and t < s < q) and that the bound a < 8*q - d simplifies to a < q + (s - t). Rewriting x(p + s - a, ·) as y(s - a, ·) via add_sub_assoc yields the coverage witness required for y.

    lines 32–38

    uses add_sub_assoc

      have hc : ∃ a : ℕ, a < q+(s-t) ∧ y ((s : ℤ)-(a : ℤ)) a = true ∧
          y ((s : ℤ)-(a : ℤ)) (a+7*q+t-s) = true := by
        obtain ⟨a, ha, ha₀, ha₁⟩ := hcover (7*q+t-s) (by omega) (by omega) (p+(s : ℤ))
        refine ⟨a, by omega, ?_, ?_⟩
        · simpa only [y, add_sub_assoc] using ha₀
        · have hi : a+(7*q+t-s)=a+7*q+t-s := by omega
          simpa only [y, add_sub_assoc, hi] using ha₁
  5. There exists an offset u < s - t satisfying the gap-owner conditions for y.

    We apply cycle_power_eight_block_gap_owner_transfer to y. The prefix and parent conditions on y follow immediately from those on x; the diagonal sums are given by he6 and he7; the root hypotheses at 0 simplify via add_zero to hroot, hchild, and hmiss; and hc provides the required coverage pair. This yields an offset u < s - t with y(s - q - u, q + u) = true, y(s - q - u, 7*q + u) = true, and y(s - q - u, q + u - (s - t)) = false.

    lines 39–44

    uses cycle_power_eight_block_gap_owner_transfer, add_zero

      obtain ⟨u,hu,hC,hB,hA⟩ := cycle_power_eight_block_gap_owner_transfer q t s hq hts hsq y
        (fun r a b hab hb hx => hprefix (p+r) a b hab hb hx)
        (fun r a ha => hparent (p+r) a ha) he6 he7
        (by simpa only [y,add_zero] using hroot)
        (by simpa only [y,add_zero] using hchild)
        (by simpa only [y,add_zero] using hmiss) hc
  6. The witness u satisfies the theorem's conclusion for x.

    Providing u as the witness, unfolding the definition of y, and reassociating the integer terms with add_sub_assoc shows that each of the three boolean equalities for y translates directly into the corresponding condition for x at p + s - q - u.

    lines 45–48

    uses add_sub_assoc

      refine ⟨u,hu,?_,?_,?_⟩
      · simpa only [y,add_sub_assoc] using hC
      · simpa only [y,add_sub_assoc] using hB
      · simpa only [y,add_sub_assoc] using hA
add_sub_assoc
In any group or additive structure with subtraction, addition and subtraction associate as a + b - c = a + (b - c).
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
cycle_power_eight_block_gap_owner_transfer
The gap-owner transfer theorem at base point 0: given prefix, parent, and diagonal-sum conditions on x, if t is an active root (x 0 t = true) with an active child (x 0 (q + t) = true) and a gap at s (x 0 s = false), and if a coverage pair exists on diagonal s at distance 7*q + t - s, then there exists an offset u < s - t certifying the gap-owner conditions.

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_at    (q t s : ℕ) (hq : 0 < q) (hts : t < s) (hsq : s < q)    (x : ℤ → ℕ → Bool) (p : ℤ)    (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)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 8*q → ∀ v : ℤ,      ∃ a : ℕ, a < 8*q-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)    (hroot : x p t = true) (hchild : x p (q+t) = true) (hmiss : x p s = false) :    ∃ u : ℕ, u < s-t ∧      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u) = true ∧      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (7*q+u) = true ∧      x (p+(s : ℤ)-(q : ℤ)-(u : ℤ)) (q+u-(s-t)) = false := by  let y : ℤ → ℕ → Bool := fun r a => x (p+r) a  have he6 : ∀ v : ℤ, (range (2*q)).sum (fun a =>      (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+6*q)).toNat) = 1 := by    intro v    simpa only [y, add_sub_assoc] using h6 (p+v)  have he7 : ∀ v : ℤ, (range q).sum (fun a =>      (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+7*q)).toNat) = 1 := by    intro v    simpa only [y, add_sub_assoc] using h7 (p+v)  have hc : ∃ a : ℕ, a < q+(s-t) ∧ y ((s : ℤ)-(a : ℤ)) a = true ∧      y ((s : ℤ)-(a : ℤ)) (a+7*q+t-s) = true := by    obtain ⟨a, ha, ha₀, ha₁⟩ := hcover (7*q+t-s) (by omega) (by omega) (p+(s : ℤ))    refine ⟨a, by omega, ?_, ?_⟩    · simpa only [y, add_sub_assoc] using ha₀    · have hi : a+(7*q+t-s)=a+7*q+t-s := by omega      simpa only [y, add_sub_assoc, hi] using ha₁  obtain ⟨u,hu,hC,hB,hA⟩ := cycle_power_eight_block_gap_owner_transfer q t s hq hts hsq y    (fun r a b hab hb hx => hprefix (p+r) a b hab hb hx)    (fun r a ha => hparent (p+r) a ha) he6 he7    (by simpa only [y,add_zero] using hroot)    (by simpa only [y,add_zero] using hchild)    (by simpa only [y,add_zero] using hmiss) hc  refine ⟨u,hu,?_,?_,?_⟩  · simpa only [y,add_sub_assoc] using hC  · simpa only [y,add_sub_assoc] using hB  · simpa only [y,add_sub_assoc] using hA
See it in the graphDiscuss this resultChallenge it