AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune

theoremverified

A compatible hierarchy of tight exact full-coverage dyadic models has monotone endpoint halves at every level, provided every selected middle bit at EVERY level forces a full prune. This is a conditional all-scale classification, not a derivation of those fullness hypotheses from optimal counts.

Statement

theorem cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_prune
    (M : ℕ) (B : ℕ → ℤ → ℕ → Bool)
    (htight : ∀ r ≤ M, ∀ p, cycle_power_dyadic_class_weight (r+1) (B r p) =
      (range (2^(r+1))).sum (fun a => (B r p a).toNat))
    (hexact : ∀ r ≤ M, ∀ j < r+1, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (B r (v-(a : ℤ)) a && B r (v-(a : ℤ)) (a+2^(r+1)-2^j)).toNat) = 1)
    (hcover : ∀ r ≤ M, ∀ d : ℕ, 1 ≤ d → d < 2^(r+1) → ∀ v : ℤ,
      ∃ c : ℕ, c < 2^(r+1)-d ∧ B r (v-(c : ℤ)) c = true ∧
        B r (v-(c : ℤ)) (c+d) = true)
    (hprune : ∀ r < M, ∀ p a, B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a)
    (hmid : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →
      B (r+1) p a = true → ∀ i < 2^(r+1), B r p i = true) :
    ∀ r ≤ M, ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < 2^r → B r p b = true → B r p a = true) ∧
      (∀ a b : ℕ, 2^r ≤ a → a ≤ b → b < 2^(r+1) →
        B r p a = true → B r 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 3
Used by 1

The proof, explained

The theorem is proved by mathematical induction on the scale r ≤ M. At the base scale r = 0, the left and right intervals are singletons, so downward and upward monotonicity hold vacuously. In the inductive step from r to r+1, the induction hypothesis ensures that the outer quarters of B (r+1) p are monotone, while the hypothesis hmid guarantees that any selected middle bit forces a full prune on the lifted model. The inductive step is completed by invoking the single-scale propagation theorem cycle_power_dyadic_half_monotone_of_middle_full_prune, which promotes the quarter-monotonicity of B (r+1) p to half-monotonicity at scale r+1.

  1. We induct on the scale r.

    We introduce the dyadic scale r and set up mathematical induction on r to prove the half-monotonicity property for all r ≤ M and all phases p ∈ ℤ.

    lines 19–20

      intro r
      induction r with
  2. The monotonicity conditions hold at the base scale r = 0.

    At scale r = 0, the left interval is [0, 2^0) = {0}, so a ≤ b < 1 forces a = b = 0, making downward monotonicity B 0 p b = true → B 0 p a = true trivial. Similarly, the right interval is [2^0, 2^1) = {1}, so 1 ≤ a ≤ b < 2 forces a = b = 1, making upward monotonicity B 0 p a = true → B 0 p b = true trivial. Both branches are closed by norm_num and omega.

    lines 21–31

      | zero =>
        intro hr p
        constructor
        · intro a b hab hb hx
          norm_num at hb
          have he : a=b := by omega
          simpa only [he] using hx
        · intro a b ha hab hb hx
          norm_num at ha hb
          have he : a=b := by omega
          simpa only [he] using hx
  3. Assume r+1 ≤ M, establish the dyadic power identities, and identify B r p as the dyadic lift of B (r+1) p.

    In the inductive step, we assume the induction hypothesis for r and assume r + 1 ≤ M, which gives r < M. We express 2^(r+1) = 2 * 2^r and 2^(r+2) = 4 * 2^r using pow_succ. Applying hypothesis hprune and function extensionality, B r p equals the dyadic lift cycle_power_dyadic_b_lift r (B (r+1) p), which retains the left quarter [0, 2^r) and right quarter [3*2^r, 4*2^r) while removing the middle half [2^r, 3*2^r).

    lines 32–39

    uses pow_succ

      | succ r ih =>
        intro hr
        have hrM : r < M := by omega
        have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega
        have hD : 2^(r+2)=4*2^r := by
          rw [show r+2=(r+1)+1 by omega,pow_succ,hH]; omega
        have hB (p : ℤ) : B r p = cycle_power_dyadic_b_lift r (B (r+1) p) :=
          funext (hprune r hrM p)
  4. B (r+1) p is monotone downward on the initial quarter [0, 2^r).

    For a ≤ b < 2^r, the definition of the dyadic lift gives B r p a = B (r+1) p a and B r p b = B (r+1) p b. The induction hypothesis at scale r ensures that B r p is downward monotone on [0, 2^r); transferring this to B (r+1) p yields B (r+1) p b = true → B (r+1) p a = true.

    lines 40–47

        have hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^r →
            B (r+1) p b = true → B (r+1) p a = true := by
          intro p a b hab hb hx
          have ha : a < 2^r := by omega
          have hla : B r p a = B (r+1) p a := by rw [hB]; simp [cycle_power_dyadic_b_lift,ha]
          have hlb : B r p b = B (r+1) p b := by rw [hB]; simp [cycle_power_dyadic_b_lift,hb]
          rw [← hla]
          exact (ih (by omega) p).1 a b hab hb (by simpa only [hlb] using hx)
  5. B (r+1) p is monotone upward on the final quarter [3*2^r, 2^(r+2)).

    For 3*2^r ≤ a ≤ b < 2^(r+2) = 4*2^r, subtracting 2^(r+1) yields indices u = a - 2^(r+1) and v = b - 2^(r+1) with 2^r ≤ u ≤ v < 2^(r+1). Since u, v ≥ 2^r, the else branch of the lift definition applies (evaluated via if_neg), giving B r p u = B (r+1) p a and B r p v = B (r+1) p b. By the induction hypothesis at scale r, B r p is upward monotone on [2^r, 2^(r+1)), which implies B (r+1) p a = true → B (r+1) p b = true.

    lines 48–63

    uses if_neg

        have hright : ∀ (p : ℤ) (a b : ℕ), 3*2^r ≤ a → a ≤ b → b < 2^(r+2) →
            B (r+1) p a = true → B (r+1) p b = true := by
          intro p a b ha hab hb hx
          let u := a-2^(r+1)
          let v := b-2^(r+1)
          have hu0 : 2^r ≤ u := by dsimp [u]; omega
          have huv : u ≤ v := by dsimp [u,v]; omega
          have hv : v < 2^(r+1) := by dsimp [v]; omega
          have hua : u+2^(r+1)=a := by dsimp [u]; omega
          have hvb : v+2^(r+1)=b := by dsimp [v]; omega
          have hla : B r p u = B (r+1) p a := by
            rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬u<2^r),hua]
          have hlb : B r p v = B (r+1) p b := by
            rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬v<2^r),hvb]
          rw [← hlb]
          exact (ih (by omega) p).2 u v hu0 huv hv (by simpa only [hla] using hx)
  6. Any active middle bit of B (r+1) p forces its dyadic lift to be identically true on [0, 2^(r+1)).

    If B (r+1) p a = true for some middle index a ∈ [2^r, 3*2^r), hypothesis hmid implies B r p i = true for every i < 2^(r+1). Rewriting B r p via hprune shows that the lifted bitmask cycle_power_dyadic_b_lift r (B (r+1) p) is identically true for all i < 2^(r+1).

    lines 64–69

        have hmf : ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →
            B (r+1) p a = true → ∀ i < 2^(r+1),
              cycle_power_dyadic_b_lift r (B (r+1) p) i = true := by
          intro p a ha hb hx i hi
          rw [← hprune r hrM p i]
          exact hmid r hrM p a ha hb hx i hi
  7. B (r+1) p is monotone downward on [0, 2^(r+1)) and upward on [2^(r+1), 2^(r+2)).

    We apply the single-scale propagation theorem cycle_power_dyadic_half_monotone_of_middle_full_prune at scale k = r to B (r+1). Hypotheses htight, hexact, and hcover at level r+1 ≤ M supply the scale r+2 tightness, exactness, and coverage requirements. Together with middle pruning hmf, left-quarter monotonicity hleft, and right-quarter monotonicity hright, the lemma concludes that B (r+1) p is downward monotone on [0, 2^(r+1)) and upward monotone on [2^(r+1), 2^(r+2)), completing the inductive step.

    lines 70–72

    uses cycle_power_dyadic_half_monotone_of_middle_full_prune

        exact cycle_power_dyadic_half_monotone_of_middle_full_prune r (B (r+1))
          (htight (r+1) (by omega)) (hexact (r+1) (by omega)) hmf hleft hright
          (hcover (r+1) (by omega))
pow_succ
For any element a of a monoid and natural number n, a^(n+1) = a^n * a; in particular, 2^(n+1) = 2^n * 2.
if_neg
If a proposition c is false, the conditional expression (if c then t else e) evaluates to the else branch e.
cycle_power_dyadic_half_monotone_of_middle_full_prune
For a dyadic bitmask at scale k+2 satisfying tightness, exactness, and coverage, if any active middle bit in [2^k, 3*2^k) forces the lifted model at scale k+1 to be identically true, and the outer quarters [0, 2^k) and [3*2^k, 2^(k+2)) are monotone downward and upward respectively, then the bitmask is monotone downward on [0, 2^(k+1)) and monotone upward on [2^(k+1), 2^(k+2)).

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_hierarchy_half_monotone_of_middle_full_prune    (M : ℕ) (B : ℕ → ℤ → ℕ → Bool)    (htight : ∀ r ≤ M, ∀ p, cycle_power_dyadic_class_weight (r+1) (B r p) =      (range (2^(r+1))).sum (fun a => (B r p a).toNat))    (hexact : ∀ r ≤ M, ∀ j < r+1, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (B r (v-(a : ℤ)) a && B r (v-(a : ℤ)) (a+2^(r+1)-2^j)).toNat) = 1)    (hcover : ∀ r ≤ M, ∀ d : ℕ, 1 ≤ d → d < 2^(r+1) → ∀ v : ℤ,      ∃ c : ℕ, c < 2^(r+1)-d ∧ B r (v-(c : ℤ)) c = true ∧        B r (v-(c : ℤ)) (c+d) = true)    (hprune : ∀ r < M, ∀ p a, B r p a = cycle_power_dyadic_b_lift r (B (r+1) p) a)    (hmid : ∀ r < M, ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →      B (r+1) p a = true → ∀ i < 2^(r+1), B r p i = true) :    ∀ r ≤ M, ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^r → B r p b = true → B r p a = true) ∧      (∀ a b : ℕ, 2^r ≤ a → a ≤ b → b < 2^(r+1) →        B r p a = true → B r p b = true) := by  intro r  induction r with  | zero =>    intro hr p    constructor    · intro a b hab hb hx      norm_num at hb      have he : a=b := by omega      simpa only [he] using hx    · intro a b ha hab hb hx      norm_num at ha hb      have he : a=b := by omega      simpa only [he] using hx  | succ r ih =>    intro hr    have hrM : r < M := by omega    have hH : 2^(r+1)=2*2^r := by rw [pow_succ]; omega    have hD : 2^(r+2)=4*2^r := by      rw [show r+2=(r+1)+1 by omega,pow_succ,hH]; omega    have hB (p : ℤ) : B r p = cycle_power_dyadic_b_lift r (B (r+1) p) :=      funext (hprune r hrM p)    have hleft : ∀ (p : ℤ) (a b : ℕ), a ≤ b → b < 2^r →        B (r+1) p b = true → B (r+1) p a = true := by      intro p a b hab hb hx      have ha : a < 2^r := by omega      have hla : B r p a = B (r+1) p a := by rw [hB]; simp [cycle_power_dyadic_b_lift,ha]      have hlb : B r p b = B (r+1) p b := by rw [hB]; simp [cycle_power_dyadic_b_lift,hb]      rw [← hla]      exact (ih (by omega) p).1 a b hab hb (by simpa only [hlb] using hx)    have hright : ∀ (p : ℤ) (a b : ℕ), 3*2^r ≤ a → a ≤ b → b < 2^(r+2) →        B (r+1) p a = true → B (r+1) p b = true := by      intro p a b ha hab hb hx      let u := a-2^(r+1)      let v := b-2^(r+1)      have hu0 : 2^r ≤ u := by dsimp [u]; omega      have huv : u ≤ v := by dsimp [u,v]; omega      have hv : v < 2^(r+1) := by dsimp [v]; omega      have hua : u+2^(r+1)=a := by dsimp [u]; omega      have hvb : v+2^(r+1)=b := by dsimp [v]; omega      have hla : B r p u = B (r+1) p a := by        rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬u<2^r),hua]      have hlb : B r p v = B (r+1) p b := by        rw [hB]; simp only [cycle_power_dyadic_b_lift,if_neg (by omega : ¬v<2^r),hvb]      rw [← hlb]      exact (ih (by omega) p).2 u v hu0 huv hv (by simpa only [hla] using hx)    have hmf : ∀ (p : ℤ) (a : ℕ), 2^r ≤ a → a < 3*2^r →        B (r+1) p a = true → ∀ i < 2^(r+1),          cycle_power_dyadic_b_lift r (B (r+1) p) i = true := by      intro p a ha hb hx i hi      rw [← hprune r hrM p i]      exact hmid r hrM p a ha hb hx i hi    exact cycle_power_dyadic_half_monotone_of_middle_full_prune r (B (r+1))      (htight (r+1) (by omega)) (hexact (r+1) (by omega)) hmf hleft hright      (hcover (r+1) (by omega))
See it in the graphDiscuss this resultChallenge it