AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono

theoremverified

Current middle-bit fullness and monotonicity of both halves of the pruned model imply monotonicity of both original halves, in a tight exact full ordinary-cover model.

Statement

theorem cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono
    (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)
    (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)
    (hpruned : ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →
        cycle_power_dyadic_b_lift k (x p) a = true) ∧
      (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →
        cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = 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 full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 2

The proof, explained

The theorem reduces monotonicity of both dyadic halves of the original model to monotonicity on the outer fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)) using `cycle_power_dyadic_half_monotone_of_middle_full_prune`. By the definition of `cycle_power_dyadic_b_lift`, the lower fringe [0, 2^k) corresponds directly to the first half of the pruned model, while the upper fringe [3 * 2^k, 2^(k+2)) shifts by 2^(k+1) to the second half [2^k, 2^(k+1)) of the pruned model. The assumed monotonicity of both halves of the pruned model (`hpruned`) therefore implies monotonicity on both fringes, which combined with the cover condition proves the theorem.

  1. 2^(k+1) = 2 * 2^k and 2^(k+2) = 4 * 2^k.

    We rewrite the power operations using `pow_succ` to expand 2^(k+1) = 2^k * 2 and 2^(k+2) = 2^(k+1) * 2, and close the arithmetic goals with `omega`.

    lines 23–24

    uses pow_succ

      have hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega
      have hD : 2^(k+2)=4*2^k := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega
  2. It suffices to prove monotonicity on the lower fringe [0, 2^k) and the upper fringe [3 * 2^k, 2^(k+2)), alongside the cover condition.

    We apply `cycle_power_dyadic_half_monotone_of_middle_full_prune`, which reduces monotonicity of both full halves of the original configuration to monotonicity on the fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)), supplying the tightness, exactness, and middle-bit fullness hypotheses directly.

    line 25

    uses cycle_power_dyadic_half_monotone_of_middle_full_prune

      apply cycle_power_dyadic_half_monotone_of_middle_full_prune k x htight hexact hmid
  3. Monotonicity holds on the lower fringe: for any a ≤ b < 2^k, if x(p)(b) = true then x(p)(a) = true.

    Since b < 2^k and a ≤ b, linear arithmetic gives a < 2^k. On indices below 2^k, the lifted configuration `cycle_power_dyadic_b_lift` agrees with the original x(p) by `if_pos`. Thus x(p)(b) = true implies the pruned lift is true at b. The first half of the pruned monotonicity hypothesis `hpruned` gives that the pruned lift is true at a, which simplifies via `if_pos` to x(p)(a) = true.

    lines 26–30

    uses cycle_power_dyadic_b_lift, if_pos

      · intro p a b hab hb hx
        have ha : a < 2^k := by omega
        have hh := (hpruned p).1 a b hab hb
          (by simpa only [cycle_power_dyadic_b_lift, if_pos hb] using hx)
        simpa only [cycle_power_dyadic_b_lift, if_pos ha] using hh
  4. Monotonicity holds on the upper fringe: for any 3 * 2^k ≤ a ≤ b < 2^(k+2), if x(p)(a) = true then x(p)(b) = true.

    We shift indices by subtracting 2^(k+1), setting a' = a - 2^(k+1) and b' = b - 2^(k+1). Linear arithmetic (`omega`) shows that 2^k ≤ a' ≤ b' < 2^(k+1), that neither a' nor b' is strictly less than 2^k, and that adding 2^(k+1) recovers a and b. By `if_neg`, `cycle_power_dyadic_b_lift` at a' equals x(p)(a). The second half of `hpruned` ensures the pruned lift is true at b', which simplifies via `if_neg` to x(p)(b) = true.

    lines 31–41

    uses cycle_power_dyadic_b_lift, if_neg

      · intro p a b ha₀ hab hbD hx
        have ha' : 2^k ≤ a-2^(k+1) := by omega
        have hab' : a-2^(k+1) ≤ b-2^(k+1) := by omega
        have hb' : b-2^(k+1) < 2^(k+1) := by omega
        have hna : ¬a-2^(k+1) < 2^k := by omega
        have hnb : ¬b-2^(k+1) < 2^k := by omega
        have hea : a-2^(k+1)+2^(k+1) = a := by omega
        have heb : b-2^(k+1)+2^(k+1) = b := by omega
        have hh := (hpruned p).2 (a-2^(k+1)) (b-2^(k+1)) ha' hab' hb'
          (by simpa only [cycle_power_dyadic_b_lift, if_neg hna, hea] using hx)
        simpa only [cycle_power_dyadic_b_lift, if_neg hnb, heb] using hh
  5. The cover condition is satisfied, completing the proof.

    The remaining premise required by `cycle_power_dyadic_half_monotone_of_middle_full_prune` is the ordinary-cover property, which matches the assumption `hcover` directly.

    line 42

      · exact hcover
cycle_power_dyadic_half_monotone_of_middle_full_prune
In a tight, exact dyadic model with middle-bit fullness and the ordinary-cover property, monotonicity of the fringe intervals [0, 2^k) and [3 * 2^k, 2^(k+2)) implies monotonicity of both dyadic halves [0, 2^(k+1)) and [2^(k+1), 2^(k+2)).
cycle_power_dyadic_b_lift
The lifted Boolean configuration at scale k, which maps index i to b(i) if i < 2^k, and to b(i + 2^(k+1)) otherwise.
pow_succ
For any base a and natural number n, a^(n + 1) = a^n * a.
if_pos
If condition c is true, then (if c then t else e) simplifies to t.
if_neg
If condition c is false, then (if c then t else e) simplifies to e.

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_half_monotone_of_middle_full_and_pruned_mono    (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)    (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)    (hpruned : ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →        cycle_power_dyadic_b_lift k (x p) a = true) ∧      (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →        cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = 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  have hH : 2^(k+1)=2*2^k := by rw [pow_succ]; omega  have hD : 2^(k+2)=4*2^k := by rw [show k+2=(k+1)+1 by omega, pow_succ, hH]; omega  apply cycle_power_dyadic_half_monotone_of_middle_full_prune k x htight hexact hmid  · intro p a b hab hb hx    have ha : a < 2^k := by omega    have hh := (hpruned p).1 a b hab hb      (by simpa only [cycle_power_dyadic_b_lift, if_pos hb] using hx)    simpa only [cycle_power_dyadic_b_lift, if_pos ha] using hh  · intro p a b ha₀ hab hbD hx    have ha' : 2^k ≤ a-2^(k+1) := by omega    have hab' : a-2^(k+1) ≤ b-2^(k+1) := by omega    have hb' : b-2^(k+1) < 2^(k+1) := by omega    have hna : ¬a-2^(k+1) < 2^k := by omega    have hnb : ¬b-2^(k+1) < 2^k := by omega    have hea : a-2^(k+1)+2^(k+1) = a := by omega    have heb : b-2^(k+1)+2^(k+1) = b := by omega    have hh := (hpruned p).2 (a-2^(k+1)) (b-2^(k+1)) ha' hab' hb'      (by simpa only [cycle_power_dyadic_b_lift, if_neg hna, hea] using hx)    simpa only [cycle_power_dyadic_b_lift, if_neg hnb, heb] using hh  · exact hcover
See it in the graphDiscuss this resultChallenge it