AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_eighth_owner_order

theoremverified

In a tight exact fully ordinarily covered dyadic model of radius2^(k+3), monotone outer eighths imply that roots owning consecutive edges of distance7*2^k are nondecreasing. Counts and periodicity are not assumed.

Statement

theorem cycle_power_dyadic_outer_eighth_owner_order
    (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)) :
    ∀ (v : ℤ) (a b : ℕ), a < 2^k → b < 2^k →
      x (v-(a : ℤ)) a = true →
      x (v-(a : ℤ)) (a+7*2^k) = true →
      x (v+1-(b : ℤ)) b = true →
      x (v+1-(b : ℤ)) (b+7*2^k) = true → b ≤ a+1
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

The proof, explained

The original dyadic model x has radius 2^(k+3) = 8 * 2^k and is monotone on its two outer eighths [0, 2^k) and [7 * 2^k, 8 * 2^k). Applying dyadic pruning twice cuts out the middle six eighths, compressing the two outer eighths into a smaller model z of radius 2^(k+1) = 2 * 2^k that inherits tightness, exactness, and covering. Monotonicity of the outer eighths ensures that z satisfies the "no island" shape condition, while edges of distance 7 * 2^k in x correspond to edges of distance 2^k at level k in z. The result b ≤ a + 1 then follows by applying the known owner-ordering theorem cycle_power_dyadic_no_island_rank_owner_order to z.

  1. The dyadic scales k+1, k+2, and k+3 correspond to lengths 2q, 4q, and 8q, where q = 2^k > 0.

    We set q = 2^k, which is strictly positive by `Nat.two_pow_pos`. Applying the successor rule for powers `pow_succ` and linear arithmetic shows that 2^(k+1) = 2q, 2^(k+2) = 4q, and 2^(k+3) = 8q.

    lines 23–27

    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. Two successive dyadic pruning steps reduce the model from radius 8q to radius 2q, preserving tightness, exactness, and covering.

    We define y by pruning x at scale k+1 (reducing size from 8q to 4q), and z by pruning y at scale k (reducing size from 4q to 2q). Applying the preservation lemmas `cycle_power_dyadic_tight_class_prune`, `cycle_power_dyadic_prune_exact`, and `cycle_power_dyadic_prune_cover` at each stage ensures that y and z inherit tightness, exactness, and the full covering property from x.

    lines 28–35

    uses 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 pruned model z on [0, 2q) satisfies z(p, i) = x(p, i) for i < q and z(p, i) = x(p, i + 6q) for q ≤ i < 2q.

    Unfolding the two pruning lifts, an index i < q takes the first branch of both conditionals via `if_pos`, giving z(p, i) = x(p, i) (`hzLow`). For q ≤ i < 2q, both conditionals take the second branch via `if_neg`, adding an accumulated offset of 2q + 4q = 6q, which yields z(p, i) = x(p, i + 6q) (`hzHigh`). The pruned model z thus glues together the first eighth [0, q) and the last eighth [7q, 8q) of x.

    lines 36–44

    uses 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 pruned model z satisfies the "no island" shape condition: no true value is flanked by false values.

    Suppose a < b < c < 2^(k+1) with z(p, a) = false and z(p, b) = true. If b < q, then a < q, so both a and b fall in the first eighth where z coincides with x; the downward monotonicity of x on [0, q) forces x(p, a) = true, a contradiction. If b ≥ q, then c > b ≥ q, so both b and c fall in the second half where z maps to the eighth eighth [7q, 8q); the upward monotonicity of x on [7q, 8q) implies x(p, c + 6q) = true, so z(p, c) = true.

    lines 45–59

      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. At level k in z, the upper pairing partner of a < q corresponds to an edge of length 7q in x.

    For a < q, the edge endpoint at level k in z is a + 2^(k+1) - 2^k = a + q. Because q ≤ a + q < 2q, `hzHigh` rewrites z(p, a + q) to x(p, a + q + 6q) = x(p, a + 7q) (`hzPair`).

    lines 60–65

      have hzPair (p : ℤ) (a : ℕ) (ha : a < q) :
          z p (a+2^(k+1)-2^k) = x p (a+7*q) := by
        have hi : a+2^(k+1)-2^k=a+q := by dsimp [q]; omega
        rw [hi,hzHigh p (a+q) (by omega) (by omega)]
        congr 1
        omega
  6. Consecutive edge owners satisfy b ≤ a + 1.

    We introduce the vertices v, v+1 and edge owners a, b < 2^k. The edge ownership hypotheses for x at distance 7 * 2^k translate directly via `hzLow` and `hzPair` into edge ownership hypotheses in z at scale k+1 and level k. Applying the existing owner-ordering theorem `cycle_power_dyadic_no_island_rank_owner_order` to z closes the goal.

    lines 66–72

    uses cycle_power_dyadic_no_island_rank_owner_order

      intro v a b ha hb ha₀ ha₁ hb₀ hb₁
      apply cycle_power_dyadic_no_island_rank_owner_order (k+1) z hzT hzE hzShape hzC
        k (by omega) v a b ha hb
      · simpa only [hzLow _ a ha] using ha₀
      · simpa only [hzPair _ a ha] using ha₁
      · simpa only [hzLow _ b hb] using hb₀
      · simpa only [hzPair _ b hb] using hb₁
Nat.two_pow_pos
Powers of 2 with natural exponents are strictly positive (0 < 2^w).
pow_succ
Successor power rule in a monoid: a^(n+1) = a^n * a.
cycle_power_dyadic_tight_class_prune
Pruning a tight configuration at scale k+2 preserves the tight class weight condition at scale k+1.
cycle_power_dyadic_prune_exact
Pruning an exact dyadic model at scale k+2 preserves exactness at scale k+1 for all levels j < k+1.
cycle_power_dyadic_prune_cover
In a tight model, if every distance d < 2^(k+2) is covered by a true-true pair, then pruning to scale k+1 preserves covering for all distances d < 2^(k+1).
if_pos
An if-then-else evaluates to its then-branch when the condition is true.
if_neg
An if-then-else evaluates to its else-branch when the condition is false.
cycle_power_dyadic_no_island_rank_owner_order
In a tight, exact, covered dyadic model of radius 2^m satisfying the "no island" shape condition, consecutive edge owners at level j < m satisfy b ≤ a + 1.

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_owner_order    (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)) :    ∀ (v : ℤ) (a b : ℕ), a < 2^k → b < 2^k →      x (v-(a : ℤ)) a = true →      x (v-(a : ℤ)) (a+7*2^k) = true →      x (v+1-(b : ℤ)) b = true →      x (v+1-(b : ℤ)) (b+7*2^k) = true → b ≤ a+1 := 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  have hzPair (p : ℤ) (a : ℕ) (ha : a < q) :      z p (a+2^(k+1)-2^k) = x p (a+7*q) := by    have hi : a+2^(k+1)-2^k=a+q := by dsimp [q]; omega    rw [hi,hzHigh p (a+q) (by omega) (by omega)]    congr 1    omega  intro v a b ha hb ha₀ ha₁ hb₀ hb₁  apply cycle_power_dyadic_no_island_rank_owner_order (k+1) z hzT hzE hzShape hzC    k (by omega) v a b ha hb  · simpa only [hzLow _ a ha] using ha₀  · simpa only [hzPair _ a ha] using ha₁  · simpa only [hzLow _ b hb] using hb₀  · simpa only [hzPair _ b hb] using hb₁
See it in the graphDiscuss this resultChallenge it