cycle_power_dyadic_prune_count_of_lower_bound
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
- periodic_count_eq_of_shift_balance_of_lower_boundFor a finite-period count balance C(v)+R(v)=t+R(v+h), a pointwise lower bound C(v)>=t forces C to be identically t.
- cycle_power_dyadic_prune_count_balanceTight dyadic classes with constant active count t+1 and exact half-distance coverage satisfy the exact pruning balance…
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
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.
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.
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)
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).
uses
sum_congrhave 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]
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.
uses
periodic_count_eq_of_shift_balance_of_lower_bound,cycle_power_dyadic_prune_count_balanceexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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