AFTD Auto-Formalizing Theoretical Domains

cycle_power_eight_block_overlap_stabilizes

theoremverified

Under the explicit no-vertical hypothesis and active-root separation, every overlap defect yields the rigid three-root stable-overlap pattern. This is a conditional reduction, not an unconditional extension or graph-covering theorem.

Statement

theorem cycle_power_eight_block_overlap_stabilizes
    (h : ℕ) (hh : 0 < h) (x : ℤ → ℕ → Bool)
    (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)
    (p : ℤ) (t s : ℕ) (hts : t < s) (hsq : s < 2*h)
    (hroot : x p t = true) (hchild : x p (2*h+t) = true) (hmiss : x p s = false) :
    cycle_power_eight_block_stable_overlap h x
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 is proved by strong induction on the slack distance N = 2*h - t between the root t and the upper boundary 2*h. In each step, the double gap transfer lemma (`cycle_power_eight_block_double_gap_transfer`) produces a new defect configuration with root v ≥ t. If v = t, the relation u + h = s forces the configuration to directly witness the rigid three-root stable overlap pattern; if v > t, the remaining slack 2*h - v strictly decreases, allowing the induction hypothesis to finish the proof.

  1. The theorem reduces to an auxiliary statement proved by strong induction on the slack N = 2*h - t.

    We introduce an auxiliary statement `aux` asserting that any configuration with 2*h - t = N satisfying the defect hypotheses yields a stable overlap. Strong induction on N is initiated using `Nat.strong_induction_on`.

    lines 24–30

    uses Nat.strong_induction_on

      have aux : ∀ N : ℕ, ∀ (p : ℤ) (t s : ℕ), 2*h-t=N → t < s → s < 2*h →
          x p t = true → x p (2*h+t) = true → x p s = false →
          cycle_power_eight_block_stable_overlap h x := by
        intro N
        induction N using Nat.strong_induction_on with
        | h N ih =>
          intro p t s hN hts hsq hroot hchild hmiss
  2. The defect at root t transfers to two new candidate roots u and v with t ≤ v.

    Applying `cycle_power_eight_block_double_gap_transfer` to the defect at (p, t, s) produces indices u < s - t and v < 2*h - (s - t) with t ≤ v, along with verified root, child, and missing-bit conditions for the shifted positions, and the property that v = t implies u + h = s.

    lines 31–33

    uses cycle_power_eight_block_double_gap_transfer

          obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ :=
            cycle_power_eight_block_double_gap_transfer h t s hh hts hsq x p
              hprefix hparent h6 h7 hcover hnov hsep hroot hchild hmiss
  3. If v = t, the configuration directly satisfies `cycle_power_eight_block_stable_overlap h x`.

    When v = t, the transfer lemma ensures u + h = s. From this and the bounds on u and s, linear arithmetic determines that t < h and h ≤ s < 2*h. We witness `cycle_power_eight_block_stable_overlap` with (p, t, s). The six required bit evaluations at p - h and p - 2*h coincide with the transferred hypotheses hAu, hCu, hMu, hAv, hCv, hMv because p + s - 2*h - u = p - h and p + t - 2*h - v = p - 2*h; each goal is solved by rewriting with these hypotheses and simplifying coordinate arithmetic.

    lines 34–44

          by_cases hvEq : v=t
          · have hus : u+h=s := heq hvEq
            have hth : t < h := by omega
            have hhS : h ≤ s := by omega
            refine ⟨p,t,s,hth,hhS,hsq,hroot,hchild,hmiss,?_,?_,?_,?_,?_,?_⟩
            · convert hAu using 1 <;> congr 1 <;> omega
            · convert hCu using 1 <;> congr 1 <;> omega
            · convert hMu using 1 <;> congr 1 <;> omega
            · convert hAv using 1 <;> congr 1 <;> omega
            · convert hCv using 1 <;> congr 1 <;> omega
            · convert hMv using 1 <;> congr 1 <;> omega
  4. If v ≠ t, the induction hypothesis applies to the strictly smaller slack 2*h - v.

    Since t ≤ v and v ≠ t, we have t < v, so the new slack 2*h - v is strictly less than N = 2*h - t. The transferred defect at position p' = p + t - 2*h - v, root t' = v, and missing index s' = v + s - t satisfies all induction premises by hAv, hCv, and hMv, so applying the induction hypothesis `ih` completes this branch.

    lines 45–47

          · have htv' : t < v := by omega
            exact ih (2*h-v) (by omega) (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v (v+s-t)
              rfl (by omega) (by omega) hAv hCv hMv
  5. The main theorem holds by specializing the auxiliary lemma.

    Applying `aux` to N = 2*h - t and the original parameters (p, t, s) yields the final conclusion.

    line 48

      exact aux (2*h-t) p t s rfl hts hsq hroot hchild hmiss
Nat.strong_induction_on
Strong (course-of-values) induction on natural numbers: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
cycle_power_eight_block_double_gap_transfer
Given a defect at root t with child 2*h+t and missing bit s (where t < s < 2*h), produces transferred defect coordinates u < s - t and v < 2*h - (s - t) with t ≤ v and corresponding active/missing bit patterns, such that v = t implies u + h = s.

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_overlap_stabilizes    (h : ℕ) (hh : 0 < h) (x : ℤ → ℕ → Bool)    (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)    (p : ℤ) (t s : ℕ) (hts : t < s) (hsq : s < 2*h)    (hroot : x p t = true) (hchild : x p (2*h+t) = true) (hmiss : x p s = false) :    cycle_power_eight_block_stable_overlap h x := by  have aux : ∀ N : ℕ, ∀ (p : ℤ) (t s : ℕ), 2*h-t=N → t < s → s < 2*h →      x p t = true → x p (2*h+t) = true → x p s = false →      cycle_power_eight_block_stable_overlap h x := by    intro N    induction N using Nat.strong_induction_on with    | h N ih =>      intro p t s hN hts hsq hroot hchild hmiss      obtain ⟨u,v,hu,hv,htv,hAu,hCu,hMu,hAv,hCv,hMv,heq⟩ :=        cycle_power_eight_block_double_gap_transfer h t s hh hts hsq x p          hprefix hparent h6 h7 hcover hnov hsep hroot hchild hmiss      by_cases hvEq : v=t      · have hus : u+h=s := heq hvEq        have hth : t < h := by omega        have hhS : h ≤ s := by omega        refine ⟨p,t,s,hth,hhS,hsq,hroot,hchild,hmiss,?_,?_,?_,?_,?_,?_⟩        · convert hAu using 1 <;> congr 1 <;> omega        · convert hCu using 1 <;> congr 1 <;> omega        · convert hMu using 1 <;> congr 1 <;> omega        · convert hAv using 1 <;> congr 1 <;> omega        · convert hCv using 1 <;> congr 1 <;> omega        · convert hMv using 1 <;> congr 1 <;> omega      · have htv' : t < v := by omega        exact ih (2*h-v) (by omega) (p+(t : ℤ)-(2*h : ℕ)-(v : ℤ)) v (v+s-t)          rfl (by omega) (by omega) hAv hCv hMv  exact aux (2*h-t) p t s rfl hts hsq hroot hchild hmiss
See it in the graphDiscuss this resultChallenge it