AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_half_owner_order

theoremverified

In a tight dyadic full-coverage class model with explicit no-island shapes, the root owning the next half-radius edge is at least the root owning the preceding one. No scalar count or periodicity is assumed.

Statement

theorem cycle_power_dyadic_no_island_half_owner_order
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =
      (range (2^(k+2))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1)
    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) →
      x p a = false → x p b = true → x p c = true)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true) :
    ∀ (v : ℤ) (a b : ℕ), a < 2^(k+1) → b < 2^(k+1) →
      x (v-(a : ℤ)) a = true →
      x (v-(a : ℤ)) (a+2^(k+1)) = true →
      x (v+1-(b : ℤ)) b = true →
      x (v+1-(b : ℤ)) (b+2^(k+1)) = true → b ≤ a+1
Source
Uniform conditional structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. The middle-bit fullness assumptions and smaller-quarter monotonicity are explicit when used; no optimal-count classification, graph covering value or research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

The theorem shows that when moving from vertex v to v + 1, the owner index b of the half-radius chord (span 2^(k+1)) satisfies b ≤ a + 1, meaning the root (v+1) - b owning the edge at v + 1 is at least the preceding root v - a. Assuming for contradiction that a + 1 < b, both roots own chords of span 2^(k+1) and are therefore fully pruned. By the root separation theorem, the offset r = b - a - 1 between the roots must be at least 2^k, which implies a + 1 < 2^k. This upper bound allows us, via the outer pattern of fully pruned rows and the no-long-prefix property, to show that a + 1 also owns the half-radius chord at vertex v + 1. By uniqueness of the owner at v + 1, we obtain a + 1 = b, contradicting a + 1 < b.

  1. Define q = 2^k and establish the powers 2^(k+1) = 2q and 2^(k+2) = 4q with q > 0.

    We set q = 2^k. By Nat.two_pow_pos, q > 0. Using pow_succ and linear arithmetic (omega), we rewrite the half-period 2^(k+1) as 2q and the full period 2^(k+2) as 4q.

    lines 19–23

    uses Nat.two_pow_pos, pow_succ

      let q := 2^k
      have hq : 0 < q := Nat.two_pow_pos _
      have hH : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega
      have hD : 2^(k+2)=4*q := by
        rw [show k+2=(k+1)+1 by omega,pow_succ,hH]; omega
  2. Any row owning a chord of span 2^(k+1) is fully pruned.

    Suppose a row p satisfies x(p, a) = true and x(p, a + 2^(k+1)) = true for some a < 2^(k+1) = 2q. We case-split on whether a < q. If a < q, then the second endpoint a + 2^(k+1) = a + 2q falls in [2q, 3q) = [2^k, 3 · 2^k). If a ≥ q, then the first endpoint a lies in [q, 2q) ⊆ [2^k, 3 · 2^k). In either case, row p contains a true bit in [2^k, 3 · 2^k). Applying cycle_power_dyadic_no_island_middle_imp_full_prune shows that row p is fully pruned on [0, 2^(k+1)).

    lines 24–31

    uses cycle_power_dyadic_no_island_middle_imp_full_prune

      have hfull (p : ℤ) (a : ℕ) (ha : a < 2^(k+1))
          (h0 : x p a = true) (h1 : x p (a+2^(k+1)) = true) :
          ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true := by
        by_cases hl : a < q
        · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p)
            (htight p) (hshape p) (a+2^(k+1)) (by omega) (by omega) h1
        · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p)
            (htight p) (hshape p) a (by omega) (by omega) h0
  3. Assume for contradiction that the next owner index satisfies b > a + 1.

    We introduce vertices and owner indices a, b < 2^(k+1) for the chords of span 2^(k+1) at vertex v and vertex v + 1, respectively. We assume for contradiction that ¬(b ≤ a + 1), which means a + 1 < b.

    lines 32–34

      intro v a b ha hb ha0 ha1 hb0 hb1
      by_contra hne
      have hab : a+1 < b := by omega
  4. The root offset r = b - a - 1 is positive and satisfies r ≥ 2^k.

    Let r = b - a - 1. Since a + 1 < b, we have r > 0 and b = a + r + 1. The root owning the chord at v + 1 is v + 1 - b, and shifting it by r yields (v + 1 - b) + r = v - a, the root owning the chord at v. Because both rows own chords of span 2^(k+1), both are fully pruned by the helper lemma hfull. Applying cycle_power_dyadic_full_prune_root_separation to these two distinct fully pruned rows separated by r > 0 yields r ≥ 2^k.

    lines 35–43

    uses cycle_power_dyadic_full_prune_root_separation

      let r := b-a-1
      have hr : 0 < r := by dsimp [r]; omega
      have hsum : b = a+r+1 := by dsimp [r]; omega
      have hroot : v+1-(b : ℤ)+(r : ℤ)=v-(a : ℤ) := by omega
      have hfa := hfull (v-(a : ℤ)) a ha ha0 ha1
      have hfb := hfull (v+1-(b : ℤ)) b hb hb0 hb1
      have hsep := cycle_power_dyadic_full_prune_root_separation k x
        (hexact k (by omega)) (v+1-(b : ℤ)) r hr hfb
        (by simpa only [hroot] using hfa)
  5. The index a + 1 is strictly less than q, which implies x(v - a, a + 1) = true.

    From b < 2^(k+1) = 2q, b = a + r + 1, and r ≥ q, we have a + 1 = b - r < 2q - q = q. By cycle_power_dyadic_full_prune_outer, any fully pruned row is identically true on [0, 2^k) = [0, q). Thus x(v - a, a + 1) = true.

    lines 44–46

    uses cycle_power_dyadic_full_prune_outer

      have haq : a+1 < q := by omega
      have hout := cycle_power_dyadic_full_prune_outer k (x (v-(a : ℤ))) hfa
      have hanext : x (v-(a : ℤ)) (a+1) = true := hout.1 _ haq
  6. The right endpoint also holds: x(v - a, a + 1 + 2^(k+1)) = true.

    We know x(v - a, a + 2^(k+1)) = true from hypothesis ha1. Applying cycle_power_dyadic_no_island_no_long_prefix at index h = a + 1 + 2^(k+1) (which satisfies 2^(k+1) < h < 2^(k+2) because a + 1 < q), the truth of bit h - 1 = a + 2^(k+1) forces bit h to be true as well.

    lines 47–51

    uses cycle_power_dyadic_no_island_no_long_prefix

      have hanextH : x (v-(a : ℤ)) (a+1+2^(k+1)) = true := by
        have hh := cycle_power_dyadic_no_island_no_long_prefix k x htight hexact
          hshape hcover (v-(a : ℤ)) (a+1+2^(k+1)) (by omega) (by omega)
          (by convert ha1 using 1 <;> congr 1 <;> omega)
        exact hh
  7. Index a + 1 is also an owner at vertex v + 1, forcing a + 1 = b by uniqueness and contradicting a + 1 < b.

    Rewriting the root as v - a = (v + 1) - (a + 1), the verified values show that a + 1 < 2^(k+1) satisfies both x((v + 1) - (a + 1), a + 1) = true and x((v + 1) - (a + 1), a + 1 + 2^(k+2) - 2^(k+1)) = true. Thus a + 1 is an owner of the half-radius pair at vertex v + 1. By cycle_power_exact_pair_unique, the exactness condition hexact (k+1) ensures that the owner in [0, 2^(k+1)) is unique at vertex v + 1. Since b is also an owner, a + 1 = b, contradicting a + 1 < b and completing the proof.

    lines 52–60

    uses cycle_power_exact_pair_unique

      have hroot' : v+1-((a+1 : ℕ) : ℤ)=v-(a : ℤ) := by omega
      have heA : a+1+2^(k+2)-2^(k+1)=a+1+2^(k+1) := by omega
      have heB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega
      have hd := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x
        (hexact (k+1) (by omega)) (v+1) (a+1) b (by omega) hb
        (by simpa only [hroot'] using hanext)
        (by simpa only [hroot',heA] using hanextH) hb0
        (by simpa only [heB] using hb1)
      omega
Nat.two_pow_pos
Powers of two with natural exponents are strictly positive.
pow_succ
The (n+1)-th power of an element in a monoid equals its n-th power multiplied by the element.
cycle_power_dyadic_no_island_middle_imp_full_prune
In a tight dyadic class with no-island shape, any true bit at an index in [2^k, 3 · 2^k) implies that the row is fully pruned (its dyadic lift is identically true on [0, 2^(k+1))).
cycle_power_dyadic_full_prune_root_separation
Under exact dyadic coverage, two distinct fully pruned rows separated by distance r > 0 must satisfy r ≥ 2^k.
cycle_power_dyadic_full_prune_outer
A fully pruned row has all bits set to true in both the initial interval [0, 2^k) and the upper interval [3 · 2^k, 2^(k+2)).
cycle_power_dyadic_no_island_no_long_prefix
In a tight full-coverage model with no-island shapes, for any index h with 2^(k+1) < h < 2^(k+2), if bit h - 1 is true, then bit h is also true.
cycle_power_exact_pair_unique
When an exact coverage condition specifies that exactly one pair of span D - R occurs over range R, the owner index in [0, R) for that pair at any vertex is unique.

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 Finsettheorem cycle_power_dyadic_no_island_half_owner_order    (k : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (k+2) (x p) =      (range (2^(k+2))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1)    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+2) →      x p a = false → x p b = true → x p c = true)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(k+2)-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true) :    ∀ (v : ℤ) (a b : ℕ), a < 2^(k+1) → b < 2^(k+1) →      x (v-(a : ℤ)) a = true →      x (v-(a : ℤ)) (a+2^(k+1)) = true →      x (v+1-(b : ℤ)) b = true →      x (v+1-(b : ℤ)) (b+2^(k+1)) = true → b ≤ a+1 := by  let q := 2^k  have hq : 0 < q := Nat.two_pow_pos _  have hH : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega  have hD : 2^(k+2)=4*q := by    rw [show k+2=(k+1)+1 by omega,pow_succ,hH]; omega  have hfull (p : ℤ) (a : ℕ) (ha : a < 2^(k+1))      (h0 : x p a = true) (h1 : x p (a+2^(k+1)) = true) :      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true := by    by_cases hl : a < q    · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p)        (htight p) (hshape p) (a+2^(k+1)) (by omega) (by omega) h1    · exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p)        (htight p) (hshape p) a (by omega) (by omega) h0  intro v a b ha hb ha0 ha1 hb0 hb1  by_contra hne  have hab : a+1 < b := by omega  let r := b-a-1  have hr : 0 < r := by dsimp [r]; omega  have hsum : b = a+r+1 := by dsimp [r]; omega  have hroot : v+1-(b : ℤ)+(r : ℤ)=v-(a : ℤ) := by omega  have hfa := hfull (v-(a : ℤ)) a ha ha0 ha1  have hfb := hfull (v+1-(b : ℤ)) b hb hb0 hb1  have hsep := cycle_power_dyadic_full_prune_root_separation k x    (hexact k (by omega)) (v+1-(b : ℤ)) r hr hfb    (by simpa only [hroot] using hfa)  have haq : a+1 < q := by omega  have hout := cycle_power_dyadic_full_prune_outer k (x (v-(a : ℤ))) hfa  have hanext : x (v-(a : ℤ)) (a+1) = true := hout.1 _ haq  have hanextH : x (v-(a : ℤ)) (a+1+2^(k+1)) = true := by    have hh := cycle_power_dyadic_no_island_no_long_prefix k x htight hexact      hshape hcover (v-(a : ℤ)) (a+1+2^(k+1)) (by omega) (by omega)      (by convert ha1 using 1 <;> congr 1 <;> omega)    exact hh  have hroot' : v+1-((a+1 : ℕ) : ℤ)=v-(a : ℤ) := by omega  have heA : a+1+2^(k+2)-2^(k+1)=a+1+2^(k+1) := by omega  have heB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega  have hd := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x    (hexact (k+1) (by omega)) (v+1) (a+1) b (by omega) hb    (by simpa only [hroot'] using hanext)    (by simpa only [hroot',heA] using hanextH) hb0    (by simpa only [heB] using hb1)  omega
See it in the graphDiscuss this resultChallenge it