AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_eighth_corner

theoremverified

In a tight exact fully ordinarily covered dyadic model of radius2^(k+3), suppose all outer eighths are monotone. For every root p and cut1<=h<2^k, if offset h-1 is selected, then either offset h is selected too or root p+h selects offset2^(k+3)-h-1. Counts and periodicity are not assumed.

Statement

theorem cycle_power_dyadic_outer_eighth_corner
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) =
      (range (2^(k+3))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true)
    (houter : ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧
      (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) →
        x p a = true → x p b = true)) :
    ∀ (p : ℤ) (h : ℕ), 1 ≤ h → h < 2^k →
      x p (h-1) = true → x p h = true ∨
      x (p+(h : ℤ)) (2^(k+3)-h-1) = true
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 6
  • cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
  • cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
  • cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
  • cycle_power_dyadic_prune_exactDeleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class…
  • cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
  • cycle_power_dyadic_no_island_cornerConditional uniform strong corner law for every cut of every dyadic radius in a tight two-interval full-cover model with exact dyadic…

The proof, explained

The proof reduces the dyadic model of scale $2^{k+3} = 8 \cdot 2^k$ to a model of scale $2^{k+1} = 2 \cdot 2^k$ by pruning it twice. This double pruning discards the middle six eighths, splicing the bottom eighth $[0, 2^k)$ and top eighth $[7 \cdot 2^k, 8 \cdot 2^k)$ together into a smaller model $z$. The model $z$ inherits tightness, exactness, and covering from $x$, while the assumed outer-eighth monotonicity of $x$ ensures that $z$ satisfies the no-island shape condition. Applying `cycle_power_dyadic_no_island_corner` to $z$ yields the corner alternative, which directly translates back to the outer eighths of $x$.

  1. Letting $q = 2^k$, express the dyadic scales $2^{k+1}$, $2^{k+2}$, and $2^{k+3}$ as $2q$, $4q$, and $8q$ respectively, with $q > 0$.

    We define $q = 2^k$ and note that $q > 0$ by `Nat.two_pow_pos`. Using the inductive step for powers $2^{n+1} = 2^n \cdot 2$ (`pow_succ`) and linear arithmetic (`omega`), we establish that $2^{k+1} = 2q$, $2^{k+2} = 4q$, and $2^{k+3} = 8q$.

    lines 21–25

    uses Nat.two_pow_pos, pow_succ

      let q := 2^k
      have hq : 0 < q := Nat.two_pow_pos _
      have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega
      have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega
      have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega
  2. Construct the twice-pruned model $z$ of scale $2^{k+1}$ from $x$ and verify that $z$ is tight, exact, and covered.

    We apply the dyadic pruning operator `cycle_power_dyadic_b_lift (k+1)` to $x$, producing an intermediate model $y$ at scale $k+2$ that inherits tightness (`hyT`), exactness (`hyE`), and covering (`hyC`). A second application of pruning at parameter $k$ reduces $y$ to $z$ at scale $k+1$, which similarly inherits tightness (`hzT`), exactness (`hzE`), and covering (`hzC`) via `cycle_power_dyadic_tight_class_prune`, `cycle_power_dyadic_prune_exact`, and `cycle_power_dyadic_prune_cover`.

    lines 26–33

    uses cycle_power_dyadic_b_lift, cycle_power_dyadic_tight_class_prune, cycle_power_dyadic_prune_exact, cycle_power_dyadic_prune_cover

      let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p)
      let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p)
      have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p)
      have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact
      have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover
      have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p)
      have hzE := cycle_power_dyadic_prune_exact k y hyE
      have hzC := cycle_power_dyadic_prune_cover k y hyT hyC
  3. The reduced model $z$ equals $x$ on the lower interval $[0, q)$ and equals $x$ shifted by $6q$ on $[q, 2q)$ (the top eighth $[7q, 8q)$ of $x$).

    Unfolding `z`, `y`, and `cycle_power_dyadic_b_lift`, an offset $i < q$ satisfies the condition $i < 2^k$ and $i < 2^{k+1}$, selecting the identity branch at both pruning stages via `if_pos` (`hzLow`). An offset $q \le i < 2q$ takes the shifted branch at both stages via `if_neg`, shifting the offset by $2^{k+1} + 2^{k+2} = 2q + 4q = 6q$, so $z(p, i) = x(p, i + 6q)$ (`hzHigh`).

    lines 34–42

    uses cycle_power_dyadic_b_lift, if_pos, if_neg

      have hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by
        dsimp [z,y,cycle_power_dyadic_b_lift]
        rw [if_pos hi,if_pos (by omega)]
      have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) :
          z p i = x p (i+6*q) := by
        dsimp [z,y,cycle_power_dyadic_b_lift]
        rw [if_neg (by omega),if_neg (by omega)]
        congr 1
        omega
  4. The model $z$ satisfies the shape (no-island) condition: if $a < b < c < 2^{k+1}$ with $z(p, a) = \text{false}$ and $z(p, b) = \text{true}$, then $z(p, c) = \text{true}$.

    We split into cases on whether $b < q$. If $b < q$, then $a < b < q$, so both $a$ and $b$ lie in the first eighth $[0, q)$; by downward monotonicity of $x$ on $[0, q)$ (`houter`), $z(p, b) = \text{true}$ implies $z(p, a) = x(p, a) = \text{true}$, contradicting $z(p, a) = \text{false}$. If $b \ge q$, then $q \le b < c < 2q$, so $b$ and $c$ correspond to offsets $b+6q$ and $c+6q$ in the top eighth $[7q, 8q)$; by upward monotonicity of $x$ on $[7q, 8q)$ (`houter`), $z(p, b) = \text{true}$ implies $z(p, c) = x(p, c+6q) = \text{true}$.

    lines 43–57

      have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) →
          z p a = false → z p b = true → z p c = true := by
        intro p a b c hab hbc hc ha hb
        by_cases hbq : b < q
        · have haq : a < q := by omega
          rw [hzLow p a haq] at ha
          rw [hzLow p b hbq] at hb
          have hh := (houter p).1 a b (by omega) hbq hb
          rw [ha] at hh
          contradiction
        · have hcb : q ≤ c := by omega
          rw [hzHigh p b (by omega) (by omega)] at hb
          rw [hzHigh p c hcb (by omega)]
          exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega)
            (by omega) (by omega) hb
  5. For $1 \le h < q$, if $x(p, h-1) = \text{true}$, then either $z(p, h) = \text{true}$ or $z(p+h, 2^{k+1}-h-1) = \text{true}$.

    Since $h - 1 < q$, $x(p, h-1) = \text{true}$ translates to $z(p, h-1) = \text{true}$ via `hzLow`. Because $z$ is tight, exact, covered, and satisfies the shape condition at scale $2^{k+1}$, applying `cycle_power_dyadic_no_island_corner` with cut $h < q < 2^{k+1}$ gives that either $z(p, h) = \text{true}$ or root $p+h$ selects the corner offset $2^{k+1}-h-1$ in $z$.

    lines 58–62

    uses cycle_power_dyadic_no_island_corner

      intro p h hh₀ hh₁ hp
      have hpz : z p (h-1) = true := by
        simpa only [hzLow p (h-1) (by dsimp [q]; omega)] using hp
      have hc := cycle_power_dyadic_no_island_corner (k+1) z hzT hzE hzShape hzC
        p h hh₀ (by omega) hpz
  6. Either $x(p, h) = \text{true}$ or $x(p+h, 2^{k+3}-h-1) = \text{true}$.

    We case-split on the conclusion of `cycle_power_dyadic_no_island_corner`. If $z(p, h) = \text{true}$, then since $h < q$, `hzLow` gives $x(p, h) = \text{true}$, yielding the left disjunct via `Or.inl`. If $z(p+h, 2^{k+1}-h-1) = \text{true}$, then because $q \le 2^{k+1}-h-1 < 2q$, `hzHigh` rewrites this to $x(p+h, (2^{k+1}-h-1) + 6q)$; arithmetic simplifies this offset to $2^{k+3}-h-1$, yielding the right disjunct.

    lines 63–69

    uses Or.inl

      rcases hc with hc | hc
      · exact Or.inl (by simpa only [hzLow p h hh₁] using hc)
      · right
        rw [hzHigh (p+(h : ℤ)) (2^(k+1)-h-1) (by dsimp [q] at *; omega)
          (by omega)] at hc
        have he : 2^(k+1)-h-1+6*q=2^(k+3)-h-1 := by omega
        simpa only [he] using hc
Nat.two_pow_pos
For any natural number $w$, $2^w > 0$.
pow_succ
In any monoid, $a^{n+1} = a^n \cdot a$.
cycle_power_dyadic_b_lift
The dyadic pruning operation that keeps the bottom interval $[0, 2^k)$ unchanged and shifts the top interval $[2^k, 2^{k+1})$ by $2^{k+1}$, excising the middle.
cycle_power_dyadic_tight_class_prune
Pruning a tight configuration at scale $k+2$ yields a tight configuration at scale $k+1$.
cycle_power_dyadic_prune_exact
Pruning an exact model of scale $2^{k+2}$ preserves exactness at scale $2^{k+1}$.
cycle_power_dyadic_prune_cover
Pruning a tight, covered model of scale $2^{k+2}$ produces a covered model of scale $2^{k+1}$.
if_pos
If the branching condition is true, an `if-then-else` expression reduces to its 'then' branch.
if_neg
If the branching condition is false, an `if-then-else` expression reduces to its 'else' branch.
cycle_power_dyadic_no_island_corner
In a tight, exact, covered dyadic model of scale $2^m$ satisfying the no-island shape condition, if offset $h-1$ is selected at root $p$, then either offset $h$ is selected at $p$ or the complementary corner offset $2^m - h - 1$ is selected at root $p+h$.
Or.inl
From a proof of $A$, deduce the disjunction $A \lor B$.

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_dyadic_outer_eighth_corner    (k : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) =      (range (2^(k+3))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true)    (houter : ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧      (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) →        x p a = true → x p b = true)) :    ∀ (p : ℤ) (h : ℕ), 1 ≤ h → h < 2^k →      x p (h-1) = true → x p h = true ∨      x (p+(h : ℤ)) (2^(k+3)-h-1) = true := by  let q := 2^k  have hq : 0 < q := Nat.two_pow_pos _  have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega  have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega  have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega  let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p)  let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p)  have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p)  have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact  have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover  have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p)  have hzE := cycle_power_dyadic_prune_exact k y hyE  have hzC := cycle_power_dyadic_prune_cover k y hyT hyC  have hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by    dsimp [z,y,cycle_power_dyadic_b_lift]    rw [if_pos hi,if_pos (by omega)]  have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) :      z p i = x p (i+6*q) := by    dsimp [z,y,cycle_power_dyadic_b_lift]    rw [if_neg (by omega),if_neg (by omega)]    congr 1    omega  have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) →      z p a = false → z p b = true → z p c = true := by    intro p a b c hab hbc hc ha hb    by_cases hbq : b < q    · have haq : a < q := by omega      rw [hzLow p a haq] at ha      rw [hzLow p b hbq] at hb      have hh := (houter p).1 a b (by omega) hbq hb      rw [ha] at hh      contradiction    · have hcb : q ≤ c := by omega      rw [hzHigh p b (by omega) (by omega)] at hb      rw [hzHigh p c hcb (by omega)]      exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega)        (by omega) (by omega) hb  intro p h hh₀ hh₁ hp  have hpz : z p (h-1) = true := by    simpa only [hzLow p (h-1) (by dsimp [q]; omega)] using hp  have hc := cycle_power_dyadic_no_island_corner (k+1) z hzT hzE hzShape hzC    p h hh₀ (by omega) hpz  rcases hc with hc | hc  · exact Or.inl (by simpa only [hzLow p h hh₁] using hc)  · right    rw [hzHigh (p+(h : ℤ)) (2^(k+1)-h-1) (by dsimp [q] at *; omega)      (by omega)] at hc    have he : 2^(k+1)-h-1+6*q=2^(k+3)-h-1 := by omega    simpa only [he] using hc
See it in the graphDiscuss this resultChallenge it