AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_owner_order_of_middle_full_prune

theoremverified

If selected middle bits force full prunes and the retained outer quarters are monotone toward the endpoints, then coverage only at the half-radius-plus-one distance forces the exact half-edge owners to be ordered by root. The structural premises remain explicit.

Statement

theorem cycle_power_dyadic_half_owner_order_of_middle_full_prune
    (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)
    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →
      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)
    (hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^k →
      x p b = true → x p a = true)
    (hright : ∀ (p : ℤ) (a b : ℕ), 3*2^k ≤ a → a ≤ b → b < 2^(k+2) →
      x p a = true → x p b = true)
    (hcover : ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-(2^(k+1)+1) ∧
      x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+(2^(k+1)+1)) = 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 6
Used by 1

The proof, explained

The theorem is proved by contradiction: assuming b > a + 1, the roots v - a and v + 1 - b of the two half-edge owners are separated by r = b - a - 1 > 0. Because both rows possess half-edges, middle-prune propagation forces both rows to have fully pruned lifts, which by root separation implies r ≥ 2^k, restricting a < 2^k - 1 and b > 2^k. A covering pair at distance 2^(k+1)+1 with index c is then analyzed: if c < 2^k - 1 or c ≥ 2^k, tight class weight and exactness force c + 1 = b or c = a (contradicting the bounds on a and b), while if c = 2^k - 1, monotonicity forces row v - c to be fully pruned as well, contradicting the root separation bound between v - c and v - a.

  1. Define q = 2^k and establish the dyadic scaling relations 2^(k+1) = 2q and 2^(k+2) = 4q, with q > 0.

    We abbreviate q = 2^k. Powers of two are strictly positive by Nat.two_pow_pos. The scaling identities 2^(k+1) = 2q and 2^(k+2) = 4q follow from pow_succ and linear arithmetic.

    lines 21–25

    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 containing a half-edge pair is fully pruned.

    Applying cycle_power_dyadic_half_owner_full_prune_of_middle with the middle-prune assumption hmid shows that any row p with true bits at a and a + 2^(k+1) (where a < 2^(k+1)) has its b-lift identically true on all inputs.

    line 26

    uses cycle_power_dyadic_half_owner_full_prune_of_middle

      have hfull := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid
  3. Assume for contradiction that the half-owner order fails, so b > a + 1.

    We introduce the vertex v and the owners a, b < 2^(k+1) of the half-edges at v and v+1. Assuming the negation of the conclusion b ≤ a + 1 yields a + 1 < b by linear arithmetic.

    lines 27–29

      intro v a b ha hb ha0 ha1 hb0 hb1
      by_contra hne
      have hab : a+1 < b := by omega
  4. The root separation r = b - a - 1 between rows v+1-b and v-a is at least 2^k.

    Setting r = b - a - 1 > 0, the root indices satisfy (v+1-b) + r = v - a. Since both row v-a and row v+1-b contain half-edges, both have fully pruned b-lifts. Applying cycle_power_dyadic_full_prune_root_separation at scale k, the separation r between two fully pruned rows must satisfy 2^k ≤ r.

    lines 30–38

    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 owners satisfy the strict bounds a < q - 1 and b > q.

    Since 2^k = q ≤ r = b - a - 1 and both a, b < 2q, linear arithmetic forces a + 1 < q (so a < q - 1) and b > q + a + 1 > q.

    lines 39–40

      have haq : a+1 < q := by omega
      have hbq : q < b := by omega
  6. Obtain a covering pair at distance 2^(k+1)+1 for vertex v with offset c < 2^(k+1).

    Hypothesis hcover provides an index c < 2^(k+2) - (2^(k+1)+1) = 2q - 1 such that row v-c has true bits at both c and c + (2^(k+1)+1). In particular, c < 2^(k+1).

    lines 41–42

      obtain ⟨c,hc,hc0,hc1⟩ := hcover v
      have hcH : c < 2^(k+1) := by omega
  7. The case c < q - 1 is impossible.

    If c < q - 1, the index c + 2^(k+1) + 1 falls in the right-middle range [2^(k+1), 3*2^k). By cycle_power_dyadic_tight_class_middle_parent, row v-c also has a true bit at (c + 2^(k+1) + 1) - 2^(k+1) = c + 1. Since v - c = (v+1) - (c+1), index c+1 is a half-edge owner at vertex v+1. By uniqueness of exact pairs at scale k+1 (cycle_power_exact_pair_unique), c + 1 = b. But c < q - 1 implies b = c + 1 < q, contradicting b > q.

    lines 43–55

    uses cycle_power_dyadic_tight_class_middle_parent, cycle_power_exact_pair_unique

      by_cases hcl : c < q-1
      · have hp := (cycle_power_dyadic_tight_class_middle_parent k
          (x (v-(c : ℤ))) (htight _)).2 (c+(2^(k+1)+1)) (by omega) (by omega) hc1
        have hi : c+(2^(k+1)+1)-2^(k+1)=c+1 := by omega
        rw [hi] at hp
        have hrt : v+1-((c+1 : ℕ) : ℤ)=v-(c : ℤ) := by omega
        have hiC : c+1+2^(k+2)-2^(k+1)=c+(2^(k+1)+1) := by omega
        have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega
        have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x
          (hexact (k+1) (by omega)) (v+1) (c+1) b (by omega) hb
          (by simpa only [hrt] using hp) (by simpa only [hrt,hiC] using hc1)
          hb0 (by simpa only [hiB] using hb1)
        omega
  8. The case q ≤ c is impossible.

    If q ≤ c < 2q, index c lies in the left-middle range [2^k, 2^(k+1)). By cycle_power_dyadic_tight_class_middle_parent, row v-c also has a true bit at c + 2^(k+1), making c a half-edge owner at vertex v. Uniqueness of exact pairs (cycle_power_exact_pair_unique) gives c = a. But q ≤ c implies q ≤ a, contradicting a < q - 1.

    lines 56–64

    uses cycle_power_dyadic_tight_class_middle_parent, cycle_power_exact_pair_unique

      · by_cases hch : q ≤ c
        · have hp := (cycle_power_dyadic_tight_class_middle_parent k
            (x (v-(c : ℤ))) (htight _)).1 c (by omega) (by omega) hc0
          have hiC : c+2^(k+2)-2^(k+1)=c+2^(k+1) := by omega
          have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega
          have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x
            (hexact (k+1) (by omega)) v c a hcH ha hc0
            (by simpa only [hiC] using hp) ha0 (by simpa only [hiA] using ha1)
          omega
  9. The remaining case c = q - 1 is impossible, completing the proof.

    If c = q - 1, then c < 2^k, so left-monotonicity (hleft) forces all bits i ≤ c in row v-c to be true. Similarly, c + 2^(k+1) + 1 = 3*2^k, so right-monotonicity (hright) forces all bits from 3*2^k onward to be true. Thus row v-c has a fully pruned b-lift. Let s = c - a > 0. The root shift is (v-c) + s = v - a. By cycle_power_dyadic_full_prune_root_separation, 2^k ≤ s. But s = c - a ≤ c = q - 1 < q = 2^k, a contradiction.

    lines 65–81

    uses cycle_power_dyadic_full_prune_root_separation

        · have hcq : c=q-1 := by omega
          have hcf : ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(c : ℤ))) i = true := by
            intro i hi
            dsimp [cycle_power_dyadic_b_lift]
            split_ifs with hil
            · exact hleft (v-(c : ℤ)) i c (by omega) (by omega) hc0
            · have he : c+(2^(k+1)+1)=3*2^k := by omega
              apply hright (v-(c : ℤ)) (3*2^k) (i+2^(k+1)) (by omega) (by omega) (by omega)
              simpa only [he] using hc1
          let s := c-a
          have hs : 0 < s := by dsimp [s]; omega
          have hrt : v-(c : ℤ)+(s : ℤ)=v-(a : ℤ) := by dsimp [s]; omega
          have hssep := cycle_power_dyadic_full_prune_root_separation k x
            (hexact k (by omega)) (v-(c : ℤ)) s hs hcf
            (by simpa only [hrt] using hfa)
          dsimp [s] at hssep
          omega
Nat.two_pow_pos
For any natural number w, the power 2^w is strictly positive.
pow_succ
In any monoid (including natural numbers), a^(n+1) = a^n * a.
cycle_power_dyadic_half_owner_full_prune_of_middle
If any middle bit forces a full prune on row p, then a row with both half-edge bits true at distance 2^(k+1) has its entire b-lift identically true.
cycle_power_dyadic_full_prune_root_separation
Under exact coverage at scale k, two rows separated by r > 0 that both have fully pruned b-lifts must satisfy 2^k ≤ r.
cycle_power_dyadic_tight_class_middle_parent
For a configuration with tight class weight at scale k+2, a true bit in [2^k, 2^(k+1)) forces the bit at offset +2^(k+1) to be true, and a true bit in [2^(k+1), 3*2^k) forces the bit at offset -2^(k+1) to be true.
cycle_power_exact_pair_unique
When exact coverage holds with pair distance D - R and range R at vertex v, at most one index a < R can satisfy both pair conditions; any two such indices must be equal.

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_half_owner_order_of_middle_full_prune    (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)    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)    (hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^k →      x p b = true → x p a = true)    (hright : ∀ (p : ℤ) (a b : ℕ), 3*2^k ≤ a → a ≤ b → b < 2^(k+2) →      x p a = true → x p b = true)    (hcover : ∀ v : ℤ, ∃ c : ℕ, c < 2^(k+2)-(2^(k+1)+1) ∧      x (v-(c : ℤ)) c = true ∧ x (v-(c : ℤ)) (c+(2^(k+1)+1)) = 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 := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid  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 hbq : q < b := by omega  obtain ⟨c,hc,hc0,hc1⟩ := hcover v  have hcH : c < 2^(k+1) := by omega  by_cases hcl : c < q-1  · have hp := (cycle_power_dyadic_tight_class_middle_parent k      (x (v-(c : ℤ))) (htight _)).2 (c+(2^(k+1)+1)) (by omega) (by omega) hc1    have hi : c+(2^(k+1)+1)-2^(k+1)=c+1 := by omega    rw [hi] at hp    have hrt : v+1-((c+1 : ℕ) : ℤ)=v-(c : ℤ) := by omega    have hiC : c+1+2^(k+2)-2^(k+1)=c+(2^(k+1)+1) := by omega    have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega    have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x      (hexact (k+1) (by omega)) (v+1) (c+1) b (by omega) hb      (by simpa only [hrt] using hp) (by simpa only [hrt,hiC] using hc1)      hb0 (by simpa only [hiB] using hb1)    omega  · by_cases hch : q ≤ c    · have hp := (cycle_power_dyadic_tight_class_middle_parent k        (x (v-(c : ℤ))) (htight _)).1 c (by omega) (by omega) hc0      have hiC : c+2^(k+2)-2^(k+1)=c+2^(k+1) := by omega      have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega      have hu := cycle_power_exact_pair_unique (2^(k+2)) (2^(k+1)) x        (hexact (k+1) (by omega)) v c a hcH ha hc0        (by simpa only [hiC] using hp) ha0 (by simpa only [hiA] using ha1)      omega    · have hcq : c=q-1 := by omega      have hcf : ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(c : ℤ))) i = true := by        intro i hi        dsimp [cycle_power_dyadic_b_lift]        split_ifs with hil        · exact hleft (v-(c : ℤ)) i c (by omega) (by omega) hc0        · have he : c+(2^(k+1)+1)=3*2^k := by omega          apply hright (v-(c : ℤ)) (3*2^k) (i+2^(k+1)) (by omega) (by omega) (by omega)          simpa only [he] using hc1      let s := c-a      have hs : 0 < s := by dsimp [s]; omega      have hrt : v-(c : ℤ)+(s : ℤ)=v-(a : ℤ) := by dsimp [s]; omega      have hssep := cycle_power_dyadic_full_prune_root_separation k x        (hexact k (by omega)) (v-(c : ℤ)) s hs hcf        (by simpa only [hrt] using hfa)      dsimp [s] at hssep      omega
See it in the graphDiscuss this resultChallenge it