AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_count_of_lower_bound

theoremverified

In a finite periodic tight dyadic class model with original count t+1, a pointwise lower bound t on the pruned active counts implies exact preservation of count t.

Statement

theorem cycle_power_dyadic_prune_count_of_lower_bound
    (k n t : ℕ) (hn : 0 < n) (x : ℤ → ℕ → Bool)
    (hperiod : ∀ p j, x (p + (n : ℤ)) j = x p j)
    (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)
    (hlower : ∀ v, t ≤ (range (2 ^ (k + 1))).sum (fun a =>
      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat)) :
    ∀ v, (range (2 ^ (k + 1))).sum (fun a =>
      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) = t
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

The proof, explained

The proof shows that the pruned active count C(v) equals t everywhere by reducing to a general shifting balance lemma for periodic functions. It defines C(v) and the upper-half remainder sum R(v), and checks that R inherits n-periodicity from x. Then, using the balance relation C(v) + R(v) = t + R(v + 2^(k+1)) provided by cycle_power_dyadic_prune_count_balance together with the pointwise lower bound C(v) ≥ t, periodic_count_eq_of_shift_balance_of_lower_bound concludes that C(v) = t for all v.

  1. Define the pruned count C(v) and the upper-half remainder sum R(v).

    We introduce C(v) as the pruned active count at vertex v, summing over a ∈ [0, 2^(k+1) - 1], and R(v) as the sum over the same range of the remaining variables shifted into the upper half of the range, at indices 2^(k+1) + a.

    lines 17–20

      let C : ℤ → ℕ := fun v => (range (2 ^ (k + 1))).sum (fun a =>
        (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat)
      let R : ℤ → ℕ := fun v => (range (2 ^ (k + 1))).sum (fun a =>
        (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat)
  2. The remainder function R is periodic with period n.

    For any v ∈ ℤ, evaluating R(v + n) shifts the first argument of x by n: (v + n) - (2^(k+1) + a) = (v - (2^(k+1) + a)) + n by ring arithmetic. Because x is periodic with period n in its first argument (hperiod), each summand in R(v + n) is identical to the corresponding summand in R(v). Applying sum_congr therefore proves R(v + n) = R(v).

    lines 21–27

    uses sum_congr

      have hpR : Function.Periodic R (n : ℤ) := by
        intro v
        apply sum_congr rfl
        intro a ha
        have heq : (v + (n : ℤ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ) =
            (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) + (n : ℤ) := by ring
        rw [heq, hperiod]
  3. For every vertex v, the pruned active count C(v) equals t.

    By cycle_power_dyadic_prune_count_balance, the tightness, full count, and half-sum hypotheses imply the shift balance relation C(v) + R(v) = t + R(v + 2^(k+1)). Since n > 0 (hn), R has period n (hpR), and C(v) ≥ t for all v (hlower), periodic_count_eq_of_shift_balance_of_lower_bound applies with shift h = 2^(k+1), forcing the lower bound C(v) ≥ t to hold with equality everywhere.

    lines 28–30

    uses periodic_count_eq_of_shift_balance_of_lower_bound, cycle_power_dyadic_prune_count_balance

      exact periodic_count_eq_of_shift_balance_of_lower_bound n t hn
        ((2 ^ (k + 1) : ℕ) : ℤ) C R hpR
        (cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf) hlower
sum_congr
Two finite sums over equal index sets are equal if their summands are equal at every element of the index set.
periodic_count_eq_of_shift_balance_of_lower_bound
If functions C and R satisfy the balance equation C(v) + R(v) = t + R(v + h) for all v, R is periodic with positive period n, and C(v) ≥ t for all v, then C(v) = t for all v.
cycle_power_dyadic_prune_count_balance
In a tight dyadic class model with full count t+1 and half-sum condition 1, the pruned count C(v) and remainder sum R(v) satisfy C(v) + R(v) = t + R(v + 2^(k+1)) for all v.

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_of_lower_bound    (k n t : ℕ) (hn : 0 < n) (x : ℤ → ℕ → Bool)    (hperiod : ∀ p j, x (p + (n : ℤ)) j = x p j)    (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)    (hlower : ∀ v, t ≤ (range (2 ^ (k + 1))).sum (fun a =>      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat)) :    ∀ v, (range (2 ^ (k + 1))).sum (fun a =>      (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat) = t := by  let C : ℤ → ℕ := fun v => (range (2 ^ (k + 1))).sum (fun a =>    (cycle_power_dyadic_b_lift k (x (v - (a : ℤ))) a).toNat)  let R : ℤ → ℕ := fun v => (range (2 ^ (k + 1))).sum (fun a =>    (x (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat)  have hpR : Function.Periodic R (n : ℤ) := by    intro v    apply sum_congr rfl    intro a ha    have heq : (v + (n : ℤ)) - ((2 ^ (k + 1) + a : ℕ) : ℤ) =        (v - ((2 ^ (k + 1) + a : ℕ) : ℤ)) + (n : ℤ) := by ring    rw [heq, hperiod]  exact periodic_count_eq_of_shift_balance_of_lower_bound n t hn    ((2 ^ (k + 1) : ℕ) : ℤ) C R hpR    (cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf) hlower
See it in the graphDiscuss this resultChallenge it