AFTD Auto-Formalizing Theoretical Domains

cycle_power_eight_block_double_gap_transfer

theoremverified

Conditional on no vertical defects and h-separated active roots, two gap transfers preserve the gap, move the physical selected vertex left by2h and cannot decrease its selected offset t. Equality forces the intermediate root to lie exactly h to the left. All additional hypotheses remain explicit.

Statement

theorem cycle_power_eight_block_double_gap_transfer
    (h t s : ℕ) (hh : 0 < h) (hts : t < s) (hsq : s < 2*h)
    (x : ℤ → ℕ → Bool) (p : ℤ)
    (hprefix : ∀ p : ℤ, ∀ a b : ℕ, a ≤ b → b < 2*h → x p b = true → x p a = true)
    (hparent : ∀ p a, a < 4*h →
      (a < 2*h → x p (a+12*h) = true → x p a = true) ∧
      (2*h ≤ a → x p a = true → x p (a+12*h) = true))
    (h6 : ∀ v : ℤ, (range (4*h)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+12*h)).toNat) = 1)
    (h7 : ∀ v : ℤ, (range (2*h)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+14*h)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 16*h → ∀ v : ℤ,
      ∃ a : ℕ, a < 16*h-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)
    (hnov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true)
    (hsep : ∀ (p r : ℤ) (a b : ℕ), p < r → a < 2*h → b < 2*h →
      x p a = true → x p (14*h+a) = true →
      x r b = true → x r (14*h+b) = true → (h : ℤ) ≤ r-p)
    (hroot : x p t = true) (hchild : x p (2*h+t) = true) (hmiss : x p s = false) :
    ∃ u v : ℕ, u < s-t ∧ v < 2*h-(s-t) ∧ t ≤ v ∧
      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) u = true ∧
      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u) = true ∧
      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u-(s-t)) = false ∧
      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v = true ∧
      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) (2*h+v) = true ∧
      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) (v+s-t) = false ∧
      (v=t → u+h=s)
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 1
Used by 2

The proof, explained

The proof performs two successive gap transfers using block size $q = 2h$. The first transfer shifts the gap from the initial root at $(p, t)$ to an intermediate root at $p_1 < p$ with offset $u < s - t$, and the second shifts it further to a root at $p_2 < p_1$ with offset $v < 2h - (s - t)$. The $h$-separation hypothesis guarantees that $p - p_1 \ge h$ and $p_1 - p_2 \ge h$, which forces the net horizontal shift $p - p_2 = 2h + v - t$ to be at least $2h$, ensuring $t \le v$; when $v = t$, both separation inequalities are tight, which uniquely fixes the intermediate root offset to $u + h = s$.

  1. Specializing the single gap transfer lemma to block size $2h$.

    The auxiliary lemma `hf` specializes `cycle_power_eight_block_gap_owner_transfer_at` by setting the block size parameter $q$ to $2h$. Rewriting the arithmetic multiples $2(2h) = 4h$, $6(2h) = 12h$, $7(2h) = 14h$, and $8(2h) = 16h$ matches the global assumptions `hparent`, `h6`, `h7`, and `hcover`. Given any root at offset $a$ with child at $2h+a$ and a missing vertex at $b > a$, this produces an offset $u < b - a$ at horizontal position $r + b - 2h - u$ with active child, active $14h$-ancestor, and transferred gap defect.

    lines 31–51

    uses cycle_power_eight_block_gap_owner_transfer_at

      have hf (r : ℤ) (a b : ℕ) (hab : a < b) (hb : b < 2*h)
          (ha : x r a = true) (hc : x r (2*h+a) = true) (hm : x r b = false) :
          ∃ u : ℕ, u < b-a ∧
            x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u) = true ∧
            x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (14*h+u) = true ∧
            x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u-(b-a)) = false := by
        have hp : ∀ p a, a < 2*(2*h) →
          (a < 2*h → x p (a+6*(2*h)) = true → x p a = true) ∧
          (2*h ≤ a → x p a = true → x p (a+6*(2*h)) = true) := by
          simpa only [show 2*(2*h)=4*h by omega,show 6*(2*h)=12*h by omega] using hparent
        have he6 : ∀ v : ℤ, (range (2*(2*h))).sum (fun a =>
          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+6*(2*h))).toNat) = 1 := by
          simpa only [show 2*(2*h)=4*h by omega,show 6*(2*h)=12*h by omega] using h6
        have he7 : ∀ v : ℤ, (range (2*h)).sum (fun a =>
          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+7*(2*h))).toNat) = 1 := by
          simpa only [show 7*(2*h)=14*h by omega] using h7
        have hc' : ∀ d : ℕ, 1 ≤ d → d < 8*(2*h) → ∀ v : ℤ,
          ∃ a : ℕ, a < 8*(2*h)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true := by
          simpa only [show 8*(2*h)=16*h by omega] using hcover
        simpa only [show 7*(2*h)=14*h by omega] using
          cycle_power_eight_block_gap_owner_transfer_at (2*h) a b (by omega) hab hb x r hprefix hp he6 he7 hc' ha hc hm
  2. First gap transfer from $p$ to an intermediate root at $p_1$.

    Applying `hf` to the initial configuration $(p, t, s)$ produces an offset $u < s - t$ at position $p_1 = p + s - 2h - u$, with an active child at $2h + u$ and a transferred missing defect at $s_1 = 2h + u - (s - t)$. Since $u < 2h$, the no-vertical-defect hypothesis `hnov` promotes the active child $x(p_1, 2h+u) = \mathrm{true}$ to an active root $x(p_1, u) = \mathrm{true}$. Linear arithmetic confirms that $u < s_1 < 2h$.

    lines 52–58

      obtain ⟨u,hu,hC,hB,hM⟩ := hf p t s hts hsq hroot hchild hmiss
      let p₁ : ℤ := p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)
      let s₁ := 2*h+u-(s-t)
      have huq : u < 2*h := by omega
      have hus : u < s₁ := by dsimp [s₁]; omega
      have hs₁ : s₁ < 2*h := by dsimp [s₁]; omega
      have hAu : x p₁ u = true := hnov p₁ u huq hC
  3. Second gap transfer from $p_1$ to a second root at $p_2$.

    Since $u < s_1 < 2h$ and $x(p_1, u) = \mathrm{true}$, $x(p_1, 2h+u) = \mathrm{true}$, and $x(p_1, s_1) = \mathrm{false}$, applying `hf` a second time to $(p_1, u, s_1)$ yields an offset $v < s_1 - u = 2h - (s - t)$ at position $p_2 = p_1 + s_1 - 2h - v$. Applying `hnov` again gives $x(p_2, v) = \mathrm{true}$. Linear arithmetic confirms that the roots are strictly ordered: $p_2 < p_1 < p$.

    lines 59–64

      obtain ⟨v,hv,hC₂,hB₂,hM₂⟩ := hf p₁ u s₁ hus hs₁ hAu hC hM
      let p₂ : ℤ := p₁+(s₁ : ℤ)-(2*h : ℕ)-(v : ℤ)
      have hvq : v < 2*h := by omega
      have hAv : x p₂ v = true := hnov p₂ v hvq hC₂
      have hp₁ : p₁ < p := by dsimp [p₁]; omega
      have hp₂ : p₂ < p₁ := by dsimp [p₂]; omega
  4. Root separation inequalities and coordinate simplification.

    Applying `hparent` to the child $x(p, 2h+t) = \mathrm{true}$ yields $x(p, 14h+t) = \mathrm{true}$. The separation hypothesis `hsep` applied to $p_1 < p$ and $p_2 < p_1$ then yields $h \le p - p_1$ and $h \le p_1 - p_2$. Unfolding the definitions of $p_1$, $p_2$, and $s_1$ algebraically simplifies $p_2$ to $p + t - 2h - v$ and the second defect offset $2h + v - (s_1 - u)$ to $v + s - t$.

    lines 65–71

      have hBt : x p (14*h+t) = true := by
        have ht := (hparent p (2*h+t) (by omega)).2 (by omega) hchild
        convert ht using 1 <;> congr 1 <;> omega
      have hs1 := hsep p₁ p u t hp₁ huq (by omega) hAu hB hroot hBt
      have hs2 := hsep p₂ p₁ v u hp₂ hvq huq hAv hB₂ hAu hB
      have heP : p₂=p+(t : ℤ)-(2*h : ℕ)-(v : ℤ) := by dsimp [p₂,p₁,s₁]; omega
      have heM : 2*h+v-(s₁-u)=v+s-t := by dsimp [s₁]; omega
  5. The witnesses $u$ and $v$ satisfy all conclusions, with $t \le v$ and rigidity when $v = t$.

    Summing the two separation inequalities yields $p - p_2 = (p - p_1) + (p_1 - p_2) \ge 2h$. Since $p - p_2 = 2h + v - t$, this implies $2h + v - t \ge 2h$, which gives $t \le v$. If $v = t$, then $p - p_2 = 2h$, which forces both separation steps to be equalities; in particular $p - p_1 = h$, which rearranges to $2h + u - s = h$, or $u + h = s$. Rewriting using the simplified form of $p_2$ discharges all remaining conjuncts.

    lines 72–80

      refine ⟨u,v,hu,by dsimp [s₁] at hv; omega,?_,hAu,hC,hM,?_,?_,?_,?_⟩
      · dsimp [p₁,p₂,s₁] at hs1 hs2
        omega
      · simpa only [← heP] using hAv
      · simpa only [← heP] using hC₂
      · simpa only [← heP,heM] using hM₂
      · intro hvEq
        dsimp [p₁,p₂,s₁] at hs1 hs2
        omega
cycle_power_eight_block_gap_owner_transfer_at
In an 8-block periodic system with block size $q$, given a root at offset $t$ with active child at $q+t$ and a defect at offset $s > t$, the gap transfers to a new root at horizontal position $p + s - q - u$ with offset $u < s - t$, where the child at $q + u$ and 7-block ancestor at $7q + u$ are active, and the defect is transferred to $q + u - (s - t)$.

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_double_gap_transfer    (h t s : ℕ) (hh : 0 < h) (hts : t < s) (hsq : s < 2*h)    (x : ℤ → ℕ → Bool) (p : ℤ)    (hprefix : ∀ p : ℤ, ∀ a b : ℕ, a ≤ b → b < 2*h → x p b = true → x p a = true)    (hparent : ∀ p a, a < 4*h →      (a < 2*h → x p (a+12*h) = true → x p a = true) ∧      (2*h ≤ a → x p a = true → x p (a+12*h) = true))    (h6 : ∀ v : ℤ, (range (4*h)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+12*h)).toNat) = 1)    (h7 : ∀ v : ℤ, (range (2*h)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+14*h)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 16*h → ∀ v : ℤ,      ∃ a : ℕ, a < 16*h-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true)    (hnov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true)    (hsep : ∀ (p r : ℤ) (a b : ℕ), p < r → a < 2*h → b < 2*h →      x p a = true → x p (14*h+a) = true →      x r b = true → x r (14*h+b) = true → (h : ℤ) ≤ r-p)    (hroot : x p t = true) (hchild : x p (2*h+t) = true) (hmiss : x p s = false) :    ∃ u v : ℕ, u < s-t ∧ v < 2*h-(s-t) ∧ t ≤ v ∧      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) u = true ∧      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u) = true ∧      x (p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u-(s-t)) = false ∧      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v = true ∧      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) (2*h+v) = true ∧      x (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) (v+s-t) = false ∧      (v=t → u+h=s) := by  have hf (r : ℤ) (a b : ℕ) (hab : a < b) (hb : b < 2*h)      (ha : x r a = true) (hc : x r (2*h+a) = true) (hm : x r b = false) :      ∃ u : ℕ, u < b-a ∧        x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u) = true ∧        x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (14*h+u) = true ∧        x (r+(b : ℤ)-(2*h : ℕ)-(u : ℤ)) (2*h+u-(b-a)) = false := by    have hp : ∀ p a, a < 2*(2*h) →      (a < 2*h → x p (a+6*(2*h)) = true → x p a = true) ∧      (2*h ≤ a → x p a = true → x p (a+6*(2*h)) = true) := by      simpa only [show 2*(2*h)=4*h by omega,show 6*(2*h)=12*h by omega] using hparent    have he6 : ∀ v : ℤ, (range (2*(2*h))).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+6*(2*h))).toNat) = 1 := by      simpa only [show 2*(2*h)=4*h by omega,show 6*(2*h)=12*h by omega] using h6    have he7 : ∀ v : ℤ, (range (2*h)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+7*(2*h))).toNat) = 1 := by      simpa only [show 7*(2*h)=14*h by omega] using h7    have hc' : ∀ d : ℕ, 1 ≤ d → d < 8*(2*h) → ∀ v : ℤ,      ∃ a : ℕ, a < 8*(2*h)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true := by      simpa only [show 8*(2*h)=16*h by omega] using hcover    simpa only [show 7*(2*h)=14*h by omega] using      cycle_power_eight_block_gap_owner_transfer_at (2*h) a b (by omega) hab hb x r hprefix hp he6 he7 hc' ha hc hm  obtain ⟨u,hu,hC,hB,hM⟩ := hf p t s hts hsq hroot hchild hmiss  let p₁ : ℤ := p+(s : ℤ)-(2*h : ℕ)-(u : ℤ)  let s₁ := 2*h+u-(s-t)  have huq : u < 2*h := by omega  have hus : u < s₁ := by dsimp [s₁]; omega  have hs₁ : s₁ < 2*h := by dsimp [s₁]; omega  have hAu : x p₁ u = true := hnov p₁ u huq hC  obtain ⟨v,hv,hC₂,hB₂,hM₂⟩ := hf p₁ u s₁ hus hs₁ hAu hC hM  let p₂ : ℤ := p₁+(s₁ : ℤ)-(2*h : ℕ)-(v : ℤ)  have hvq : v < 2*h := by omega  have hAv : x p₂ v = true := hnov p₂ v hvq hC₂  have hp₁ : p₁ < p := by dsimp [p₁]; omega  have hp₂ : p₂ < p₁ := by dsimp [p₂]; omega  have hBt : x p (14*h+t) = true := by    have ht := (hparent p (2*h+t) (by omega)).2 (by omega) hchild    convert ht using 1 <;> congr 1 <;> omega  have hs1 := hsep p₁ p u t hp₁ huq (by omega) hAu hB hroot hBt  have hs2 := hsep p₂ p₁ v u hp₂ hvq huq hAv hB₂ hAu hB  have heP : p₂=p+(t : ℤ)-(2*h : ℕ)-(v : ℤ) := by dsimp [p₂,p₁,s₁]; omega  have heM : 2*h+v-(s₁-u)=v+s-t := by dsimp [s₁]; omega  refine ⟨u,v,hu,by dsimp [s₁] at hv; omega,?_,hAu,hC,hM,?_,?_,?_,?_⟩  · dsimp [p₁,p₂,s₁] at hs1 hs2    omega  · simpa only [← heP] using hAv  · simpa only [← heP] using hC₂  · simpa only [← heP,heM] using hM₂  · intro hvEq    dsimp [p₁,p₂,s₁] at hs1 hs2    omega
See it in the graphDiscuss this resultChallenge it