AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_count_balance

theoremverified

Tight dyadic classes with constant active count t+1 and exact half-distance coverage satisfy the exact pruning balance C_pruned(v)+R(v)=t+R(v+H).

Statement

theorem cycle_power_dyadic_prune_count_balance
    (k t : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) =
      (range (2 ^ (k + 2))).sum (fun a => (x p a).toNat))
    (hcount : ∀ v, (range (2 ^ (k + 2))).sum
      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)
    (hhalf : ∀ v, (range (2 ^ (k + 1))).sum
      (fun a => (x (v - (a : ℤ)) a &&
        x (v - (a : ℤ)) (a + 2 ^ (k + 1))).toNat) = 1) :
    ∀ v : ℤ,
      (range (2 ^ (k + 1))).sum (fun a =>
        (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) +
      (range (2 ^ (k + 1))).sum (fun a =>
        (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat) =
      t + (range (2 ^ (k + 1))).sum (fun a =>
        (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))
          (2 ^ (k + 1) + a)).toNat)
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 2

The proof, explained

The proof reduces the dyadic pruning balance identity to the general middle-quarter balance theorem cycle_power_middle_quarter_prune_count_balance with quarter parameter q = 2^k. Dyadic tightness of order k + 2 provides the required middle-quarter bit propagation across distance 2^(k + 1) = 2q via cycle_power_dyadic_tight_class_middle_parent, while the active count and exact half-distance coverage hypotheses match the period 4q and half-period 2q. Finally, an integer arithmetic cancellation aligns the shifted remainder term on the right-hand side with the balance formula.

  1. The power-of-two relationships 2^(k + 1) = 2 * 2^k and 2^(k + 2) = 4 * 2^k hold.

    These follow from the exponent laws pow_succ and pow_add, which decompose 2^(k + 1) as 2^k * 2 and 2^(k + 2) as 2^k * 4, verified by arithmetic.

    lines 20–21

    uses pow_succ, pow_add

      have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega
      have hD : 2 ^ (k + 2) = 4 * 2 ^ k := by rw [pow_add]; norm_num; omega
  2. For every row p, active bits in the second quarter [2^k, 2 * 2^k) propagate forward by 2 * 2^k, and active bits in the third quarter [2 * 2^k, 3 * 2^k) propagate backward by 2 * 2^k.

    Applying cycle_power_dyadic_tight_class_middle_parent to the tightness hypothesis htight p yields bit propagation across distance 2^(k + 1) between the middle quarters. Rewriting 2^(k + 1) as 2 * 2^k via hH establishes both directional implications (hleft and hright).

    lines 22–32

    uses cycle_power_dyadic_tight_class_middle_parent

      have hp := fun p => cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)
      have hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 * 2 ^ k →
          x p a = true → x p (a + 2 * 2 ^ k) = true := by
        intro p a ha hb hx
        have hh := (hp p).1 a ha (by simpa only [hH] using hb) hx
        simpa only [hH] using hh
      have hright : ∀ (p : ℤ) (a : ℕ), 2 * 2 ^ k ≤ a → a < 3 * 2 ^ k →
          x p a = true → x p (a - 2 * 2 ^ k) = true := by
        intro p a ha hb hx
        have hh := (hp p).2 a (by simpa only [hH] using ha) hb hx
        simpa only [hH] using hh
  3. The total active count over range 4 * 2^k is t + 1, and the half-distance overlap count at offset 2 * 2^k over range 2 * 2^k equals 1.

    Rewriting 2^(k + 2) as 4 * 2^k via hD converts the total count hypothesis hcount into hc. Similarly, rewriting 2^(k + 1) as 2 * 2^k via hH converts the exact half-distance overlap hypothesis hhalf into he.

    lines 33–39

      have hc : ∀ v, (range (4 * 2 ^ k)).sum
          (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 := by
        simpa only [hD] using hcount
      have he : ∀ v, (range (2 * 2 ^ k)).sum
          (fun a => (x (v - (a : ℤ)) a &&
            x (v - (a : ℤ)) (a + 2 * 2 ^ k)).toNat) = 1 := by
        simpa only [hH] using hhalf
  4. The middle-quarter prune-count balance identity holds with quarter parameter q = 2^k.

    We instantiate the general balance theorem cycle_power_middle_quarter_prune_count_balance with quarter parameter q = 2^k, active count parameter t, and the established hypotheses hleft, hright, hc, and he.

    line 40

    uses cycle_power_middle_quarter_prune_count_balance

      have hb := cycle_power_middle_quarter_prune_count_balance (2 ^ k) t x hleft hright hc he
  5. For any vertex v, the shifted remainder sum over a < 2^(k + 1) simplifies to the unshifted sum with row index v - a.

    Fix v. Using sum_congr, it suffices to check summand equality for each index a. The integer expression (v + 2^(k + 1)) - (2^(k + 1) + a) simplifies to v - a because the 2^(k + 1) terms cancel. Rewriting with this equality aligns the summands.

    lines 41–52

    uses sum_congr

      intro v
      have hshift : (range (2 ^ (k + 1))).sum (fun a =>
            (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))
              (2 ^ (k + 1) + a)).toNat) =
          (range (2 ^ (k + 1))).sum (fun a =>
            (x (v - (a : ℤ)) (2 ^ (k + 1) + a)).toNat) := by
        apply sum_congr rfl
        intro a ha
        have heq : (v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ) = v - (a : ℤ) := by
          push_cast
          ring
        rw [heq]
  6. The pruning balance identity holds for all vertices v.

    Rewriting the right-hand side using hshift replaces the shifted remainder term with the unshifted form. The resulting expression matches the specialized balance identity hb v once 2 * 2^k is identified with 2^(k + 1) and the definition of cycle_power_dyadic_b_lift is unfolded.

    lines 53–54

    uses cycle_power_dyadic_b_lift

      rw [hshift]
      simpa only [cycle_power_dyadic_b_lift, hH] using hb v
pow_succ
In any monoid, raising an element to the successor power n + 1 satisfies a^(n + 1) = a^n * a.
pow_add
In any monoid, powers add under exponent addition: a^(m + n) = a^m * a^n.
cycle_power_dyadic_tight_class_middle_parent
For a boolean configuration of length 2^(k + 2) whose dyadic weight equals its active count, active bits in the second quarter [2^k, 2^(k + 1)) propagate forward by 2^(k + 1), and active bits in the third quarter [2^(k + 1), 3 * 2^k) propagate backward by 2^(k + 1).
cycle_power_middle_quarter_prune_count_balance
For any quarter-size q, active count t + 1 over period 4q, exact half-distance (2q) overlap 1, and middle-quarter propagation across distance 2q, the quarter-pruned count plus remainder at v equals t plus the remainder at v.
sum_congr
Two finite sums over the same finite set are equal if their summands agree on every element of the index set.
cycle_power_dyadic_b_lift
The lifted boolean configuration with parameter k: keeps the bit unchanged for indices a < 2^k, and shifts by 2^(k + 1) to inspect index a + 2^(k + 1) otherwise.

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_prune_count_balance    (k t : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (k + 2) (x p) =      (range (2 ^ (k + 2))).sum (fun a => (x p a).toNat))    (hcount : ∀ v, (range (2 ^ (k + 2))).sum      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1)    (hhalf : ∀ v, (range (2 ^ (k + 1))).sum      (fun a => (x (v - (a : ℤ)) a &&        x (v - (a : ℤ)) (a + 2 ^ (k + 1))).toNat) = 1) :    ∀ v : ℤ,      (range (2 ^ (k + 1))).sum (fun a =>        (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) +      (range (2 ^ (k + 1))).sum (fun a =>        (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat) =      t + (range (2 ^ (k + 1))).sum (fun a =>        (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))          (2 ^ (k + 1) + a)).toNat) := by  have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega  have hD : 2 ^ (k + 2) = 4 * 2 ^ k := by rw [pow_add]; norm_num; omega  have hp := fun p => cycle_power_dyadic_tight_class_middle_parent k (x p) (htight p)  have hleft : ∀ (p : ℤ) (a : ℕ), 2 ^ k ≤ a → a < 2 * 2 ^ k →      x p a = true → x p (a + 2 * 2 ^ k) = true := by    intro p a ha hb hx    have hh := (hp p).1 a ha (by simpa only [hH] using hb) hx    simpa only [hH] using hh  have hright : ∀ (p : ℤ) (a : ℕ), 2 * 2 ^ k ≤ a → a < 3 * 2 ^ k →      x p a = true → x p (a - 2 * 2 ^ k) = true := by    intro p a ha hb hx    have hh := (hp p).2 a (by simpa only [hH] using ha) hb hx    simpa only [hH] using hh  have hc : ∀ v, (range (4 * 2 ^ k)).sum      (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 := by    simpa only [hD] using hcount  have he : ∀ v, (range (2 * 2 ^ k)).sum      (fun a => (x (v - (a : ℤ)) a &&        x (v - (a : ℤ)) (a + 2 * 2 ^ k)).toNat) = 1 := by    simpa only [hH] using hhalf  have hb := cycle_power_middle_quarter_prune_count_balance (2 ^ k) t x hleft hright hc he  intro v  have hshift : (range (2 ^ (k + 1))).sum (fun a =>        (x ((v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ))          (2 ^ (k + 1) + a)).toNat) =      (range (2 ^ (k + 1))).sum (fun a =>        (x (v - (a : ℤ)) (2 ^ (k + 1) + a)).toNat) := by    apply sum_congr rfl    intro a ha    have heq : (v + (2 ^ (k + 1) : ℕ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ) = v - (a : ℤ) := by      push_cast      ring    rw [heq]  rw [hshift]  simpa only [cycle_power_dyadic_b_lift, hH] using hb v
See it in the graphDiscuss this resultChallenge it