AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_monotone_of_middle_full_prune

theoremverified

One uniform induction step: if all middle marks have full prunes and both retained outer quarters are monotone toward their endpoints, then the entire left and right halves are monotone toward the endpoints. Tightness, exact dyadic ownership and ordinary coverage are assumed; no counts, period or pre-existing original no-island shape are used.

Statement

theorem cycle_power_dyadic_half_monotone_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 : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,
      ∃ c : ℕ, c < 2^(k+2)-d ∧ x (v-(c : ℤ)) c = true ∧
        x (v-(c : ℤ)) (c+d) = true) :
    ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < 2^(k+1) → x p b = true → x p a = true) ∧
      (∀ a b : ℕ, 2^(k+1) ≤ a → a ≤ b → b < 2^(k+2) →
        x p a = true → x p b = true)
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 2

The proof, explained

The theorem extends endpoint-directed monotonicity from the outer quarters [0, 2^k) and [3·2^k, 2^(k+2)) across the entire left and right halves [0, 2^(k+1)) and [2^(k+1), 2^(k+2)). The proof first establishes two single-step propagation lemmas: any mark at i+1 in the left half propagates leftward to i, and any mark at i in the right half propagates rightward to i+1. When the mark falls in an inner quarter, tightness pairs it into a half-owner, and coverage supplies an adjacent half-owner that the ordering and full-prune root separation uniquely pin down to the adjacent mark. Finally, natural induction on the step lemmas propagates the marks across each half.

  1. The dyadic scale parameters q = 2^k, 2^(k+1) = 2*q, and 2^(k+2) = 4*q are established.

    Define q = 2^k, note that q > 0 by Nat.two_pow_pos, and establish 2^(k+1) = 2*q and 2^(k+2) = 4*q by rewriting with pow_succ and linear arithmetic.

    lines 22–26

    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. Half-owners inherit full prunes and satisfy the adjacent-diagonal ordering b ≤ a + 1.

    Apply cycle_power_dyadic_half_owner_full_prune_of_middle to show that any half-owner has a full prune, and apply cycle_power_dyadic_half_owner_order_of_middle_full_prune with coverage distance 2^(k+1)+1 to deduce that consecutive half-owners on diagonals v and v+1 satisfy b ≤ a + 1.

    lines 27–29

    uses cycle_power_dyadic_half_owner_full_prune_of_middle, cycle_power_dyadic_half_owner_order_of_middle_full_prune

      have hfull := cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid
      have horder := cycle_power_dyadic_half_owner_order_of_middle_full_prune k x
        htight hexact hmid hleft hright (hcover (2^(k+1)+1) (by omega) (by omega))
  3. Leftward single-step propagation holds: if x p (i+1) = true with i+1 < 2^(k+1), then x p i = true.

    If i+1 < q, the result holds by the assumed left-quarter monotonicity. Otherwise, i+1 is in the second quarter [q, 2*q), so by hmid the path p has a full prune. If i < q, the full prune directly implies x p i = true via cycle_power_dyadic_full_prune_outer. If i ≥ q, tightness (cycle_power_dyadic_tight_class_middle_parent) ensures x p (i+1 + 2^(k+1)) = true, making p a half-owner at i+1 on diagonal p+i+1. Coverage at distance 2^(k+1) on diagonal p+i yields a half-owner b < 2^(k+1). The adjacent ordering gives i ≤ b. If b ≠ i, the root separation s = b - i > 0 between the two full-prune paths must satisfy 2^k ≤ s by cycle_power_dyadic_full_prune_root_separation, which contradicts s = b - i < 2*q - q = 2^k. Thus b = i, which proves x p i = true.

    lines 30–58

    uses cycle_power_dyadic_full_prune_outer, cycle_power_dyadic_tight_class_middle_parent, cycle_power_dyadic_full_prune_root_separation

      have hstepL (p : ℤ) (i : ℕ) (hi : i+1 < 2^(k+1))
          (hx : x p (i+1) = true) : x p i = true := by
        by_cases hil : i+1 < q
        · exact hleft p i (i+1) (by omega) hil hx
        have hpf := hmid p (i+1) (by omega) (by omega) hx
        have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf
        by_cases hiq : i < q
        · exact hout.1 i hiq
        have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1
          (i+1) (by omega) hi hx
        obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(i : ℤ))
        have hbH : b < 2^(k+1) := by omega
        have hrt : p+(i : ℤ)+1-((i+1 : ℕ) : ℤ)=p := by omega
        have hle := horder (p+(i : ℤ)) b (i+1) hbH hi hb0 hb1
          (by simpa only [hrt] using hx) (by simpa only [hrt] using hp)
        have hib : i ≤ b := by omega
        have hbf := hfull (p+(i : ℤ)-(b : ℤ)) b hbH hb0 hb1
        have hbi : b=i := by
          by_contra hne
          let s := b-i
          have hs : 0 < s := by dsimp [s]; omega
          have hroot : p+(i : ℤ)-(b : ℤ)+(s : ℤ)=p := by dsimp [s]; omega
          have hsep := cycle_power_dyadic_full_prune_root_separation k x
            (hexact k (by omega)) (p+(i : ℤ)-(b : ℤ)) s hs hbf
            (by simpa only [hroot] using hpf)
          dsimp [s] at hsep
          omega
        subst b
        simpa using hb0
  4. Rightward single-step propagation holds: if x p i = true with 2^(k+1) ≤ i and i+1 < 2^(k+2), then x p (i+1) = true.

    If i ≥ 3*q, the result holds by the assumed right-quarter monotonicity. Otherwise, i is in the third quarter [2*q, 3*q), so by hmid the path p has a full prune. If i+1 ≥ 3*q, the full prune implies x p (i+1) = true via cycle_power_dyadic_full_prune_outer. If i+1 < 3*q, setting a = i - 2^(k+1) < q, tightness (cycle_power_dyadic_tight_class_middle_parent) gives x p a = true, so p is a half-owner at a on diagonal p+a. Coverage at distance 2^(k+1) on diagonal p+a+1 gives a half-owner b < 2^(k+1). The ordering implies b ≤ a+1. If b ≠ a+1, the difference s = a+1-b > 0 between the two full-prune paths requires 2^k ≤ s by cycle_power_dyadic_full_prune_root_separation, contradicting s ≤ a+1 < q = 2^k (since i+1 < 3*q means a+1 < q). Thus b = a+1, which yields x p (i+1) = true.

    lines 59–92

    uses cycle_power_dyadic_full_prune_outer, cycle_power_dyadic_tight_class_middle_parent, cycle_power_dyadic_full_prune_root_separation

      have hstepR (p : ℤ) (i : ℕ) (hi0 : 2^(k+1) ≤ i) (hi1 : i+1 < 2^(k+2))
          (hx : x p i = true) : x p (i+1) = true := by
        by_cases hir : 3*q ≤ i
        · exact hright p i (i+1) hir (by omega) hi1 hx
        have hpf := hmid p i (by omega) (by omega) hx
        have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf
        by_cases hit : 3*q ≤ i+1
        · exact hout.2 (i+1) hit hi1
        let a := i-2^(k+1)
        have ha : a < q := by dsimp [a]; omega
        have hai : a+2^(k+1)=i := by dsimp [a]; omega
        have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2
          i hi0 (by omega) hx
        have hpa : x p a = true := hp
        have hpH : x p (a+2^(k+1)) = true := by simpa only [hai] using hx
        obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(a : ℤ)+1)
        have hbH : b < 2^(k+1) := by omega
        have hrt : p+(a : ℤ)-(a : ℤ)=p := by omega
        have hle := horder (p+(a : ℤ)) a b (by omega) hbH
          (by simpa only [hrt] using hpa) (by simpa only [hrt] using hpH) hb0 hb1
        have hbf := hfull (p+(a : ℤ)+1-(b : ℤ)) b hbH hb0 hb1
        have hba : b=a+1 := by
          by_contra hne
          let s := a+1-b
          have hs : 0 < s := by dsimp [s]; omega
          have hroot : p+(s : ℤ)=p+(a : ℤ)+1-(b : ℤ) := by dsimp [s]; omega
          have hsep := cycle_power_dyadic_full_prune_root_separation k x
            (hexact k (by omega)) p s hs hpf
            (by simpa only [hroot] using hbf)
          dsimp [s] at hsep
          omega
        have hroot : p+(a : ℤ)+1-(b : ℤ)=p := by omega
        have hindex : b+2^(k+1)=i+1 := by omega
        simpa only [hroot,hindex] using hb1
  5. The left half [0, 2^(k+1)) is monotone toward 0: if a ≤ b < 2^(k+1) and x p b = true, then x p a = true.

    Fix p. By induction on b starting from a using Nat.le_induction, the base case b = a is immediate, and the induction step applies the leftward step lemma hstepL to move from b+1 to b, then finishes by the induction hypothesis.

    lines 93–102

    uses Nat.le_induction

      intro p
      constructor
      · intro a b hab hb hx
        have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+1) → x p b = true → x p a = true := by
          induction b,hab using Nat.le_induction with
          | base => intro _ hx; exact hx
          | succ b hab ih =>
            intro hb hx
            exact ih (by omega) (hstepL p b hb hx)
        exact hmove b hab hb hx
  6. The right half [2^(k+1), 2^(k+2)) is monotone toward the endpoint 2^(k+2): if 2^(k+1) ≤ a ≤ b < 2^(k+2) and x p a = true, then x p b = true.

    By induction on b starting from a using Nat.le_induction, the base case b = a is given by the assumption, and the induction step applies the rightward step lemma hstepR to advance from b to b+1 using the induction hypothesis.

    lines 103–110

    uses Nat.le_induction

      · intro a b ha hab hb hx
        have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+2) → x p b = true := by
          induction b,hab using Nat.le_induction with
          | base => intro _; exact hx
          | succ b hab ih =>
            intro hb
            exact hstepR p b (by omega) hb (ih (by omega))
        exact hmove b hab hb
Nat.two_pow_pos
Powers of two are strictly positive: 0 < 2^w for any natural number w.
pow_succ
Successor power identity in a monoid: a^(n+1) = a^n * a.
cycle_power_dyadic_half_owner_full_prune_of_middle
If every middle mark on a path induces a full prune, then any half-owner (a pair of marks separated by 2^(k+1)) also has a full prune.
cycle_power_dyadic_half_owner_order_of_middle_full_prune
Under tightness, exact dyadic ownership, middle full pruning, outer monotonicity, and coverage, half-owners on adjacent diagonals satisfy the ordering b ≤ a + 1.
cycle_power_dyadic_full_prune_outer
A configuration with a full prune has all marks true in the outer quarters: for all i < 2^k and all 3*2^k ≤ i < 2^(k+2).
cycle_power_dyadic_tight_class_middle_parent
In a tight configuration, any mark in the second quarter [2^k, 2^(k+1)) is paired with a mark at a + 2^(k+1), and any mark in the third quarter [2^(k+1), 3*2^k) is paired with a mark at a - 2^(k+1).
cycle_power_dyadic_full_prune_root_separation
Under exact dyadic ownership, two distinct paths separated by r > 0 that both have full prunes must be separated by at least 2^k ≤ r.
Nat.le_induction
Induction principle for natural numbers: to prove P(n) for all n ≥ m, it suffices to prove P(m) and that P(n) implies P(n+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 Finsettheorem cycle_power_dyadic_half_monotone_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 : ∀ d : ℕ, 1 ≤ d → d < 2^(k+2) → ∀ v : ℤ,      ∃ c : ℕ, c < 2^(k+2)-d ∧ x (v-(c : ℤ)) c = true ∧        x (v-(c : ℤ)) (c+d) = true) :    ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^(k+1) → x p b = true → x p a = true) ∧      (∀ a b : ℕ, 2^(k+1) ≤ a → a ≤ b → b < 2^(k+2) →        x p a = true → x p b = true) := 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  have horder := cycle_power_dyadic_half_owner_order_of_middle_full_prune k x    htight hexact hmid hleft hright (hcover (2^(k+1)+1) (by omega) (by omega))  have hstepL (p : ℤ) (i : ℕ) (hi : i+1 < 2^(k+1))      (hx : x p (i+1) = true) : x p i = true := by    by_cases hil : i+1 < q    · exact hleft p i (i+1) (by omega) hil hx    have hpf := hmid p (i+1) (by omega) (by omega) hx    have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf    by_cases hiq : i < q    · exact hout.1 i hiq    have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).1      (i+1) (by omega) hi hx    obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(i : ℤ))    have hbH : b < 2^(k+1) := by omega    have hrt : p+(i : ℤ)+1-((i+1 : ℕ) : ℤ)=p := by omega    have hle := horder (p+(i : ℤ)) b (i+1) hbH hi hb0 hb1      (by simpa only [hrt] using hx) (by simpa only [hrt] using hp)    have hib : i ≤ b := by omega    have hbf := hfull (p+(i : ℤ)-(b : ℤ)) b hbH hb0 hb1    have hbi : b=i := by      by_contra hne      let s := b-i      have hs : 0 < s := by dsimp [s]; omega      have hroot : p+(i : ℤ)-(b : ℤ)+(s : ℤ)=p := by dsimp [s]; omega      have hsep := cycle_power_dyadic_full_prune_root_separation k x        (hexact k (by omega)) (p+(i : ℤ)-(b : ℤ)) s hs hbf        (by simpa only [hroot] using hpf)      dsimp [s] at hsep      omega    subst b    simpa using hb0  have hstepR (p : ℤ) (i : ℕ) (hi0 : 2^(k+1) ≤ i) (hi1 : i+1 < 2^(k+2))      (hx : x p i = true) : x p (i+1) = true := by    by_cases hir : 3*q ≤ i    · exact hright p i (i+1) hir (by omega) hi1 hx    have hpf := hmid p i (by omega) (by omega) hx    have hout := cycle_power_dyadic_full_prune_outer k (x p) hpf    by_cases hit : 3*q ≤ i+1    · exact hout.2 (i+1) hit hi1    let a := i-2^(k+1)    have ha : a < q := by dsimp [a]; omega    have hai : a+2^(k+1)=i := by dsimp [a]; omega    have hp := (cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)).2      i hi0 (by omega) hx    have hpa : x p a = true := hp    have hpH : x p (a+2^(k+1)) = true := by simpa only [hai] using hx    obtain ⟨b,hb,hb0,hb1⟩ := hcover (2^(k+1)) (by omega) (by omega) (p+(a : ℤ)+1)    have hbH : b < 2^(k+1) := by omega    have hrt : p+(a : ℤ)-(a : ℤ)=p := by omega    have hle := horder (p+(a : ℤ)) a b (by omega) hbH      (by simpa only [hrt] using hpa) (by simpa only [hrt] using hpH) hb0 hb1    have hbf := hfull (p+(a : ℤ)+1-(b : ℤ)) b hbH hb0 hb1    have hba : b=a+1 := by      by_contra hne      let s := a+1-b      have hs : 0 < s := by dsimp [s]; omega      have hroot : p+(s : ℤ)=p+(a : ℤ)+1-(b : ℤ) := by dsimp [s]; omega      have hsep := cycle_power_dyadic_full_prune_root_separation k x        (hexact k (by omega)) p s hs hpf        (by simpa only [hroot] using hbf)      dsimp [s] at hsep      omega    have hroot : p+(a : ℤ)+1-(b : ℤ)=p := by omega    have hindex : b+2^(k+1)=i+1 := by omega    simpa only [hroot,hindex] using hb1  intro p  constructor  · intro a b hab hb hx    have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+1) → x p b = true → x p a = true := by      induction b,hab using Nat.le_induction with      | base => intro _ hx; exact hx      | succ b hab ih =>        intro hb hx        exact ih (by omega) (hstepL p b hb hx)    exact hmove b hab hb hx  · intro a b ha hab hb hx    have hmove (b : ℕ) (hab : a ≤ b) : b < 2^(k+2) → x p b = true := by      induction b,hab using Nat.le_induction with      | base => intro _; exact hx      | succ b hab ih =>        intro hb        exact hstepR p b (by omega) hb (ih (by omega))    exact hmove b hab hb
See it in the graphDiscuss this resultChallenge it