cycle_power_dyadic_prune_count_balance
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
- cycle_power_middle_quarter_prune_count_balanceFor a four-quarter class model with parent implications, constant original active count t+1, and exact half-distance coverage, pruning…
- 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_tight_class_middle_parentEquality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent…
- 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.
- Used by 2
- cycle_power_dyadic_prune_count_of_lower_boundIn a finite periodic tight dyadic class model with original count t+1, a pointwise lower bound t on the pruned active counts implies exact…
- cycle_power_dyadic_prune_count_iff_right_half_periodUnder the dyadic pruning balance hypotheses, preservation of active count t is equivalent to half-radius periodicity of right-half…
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.
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.
uses
pow_succ,pow_addhave 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
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).
uses
cycle_power_dyadic_tight_class_middle_parenthave 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
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.
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
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.
uses
cycle_power_middle_quarter_prune_count_balancehave hb := cycle_power_middle_quarter_prune_count_balance (2 ^ k) t x hleft hright hc heFor 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.
uses
sum_congrintro 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]
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.
uses
cycle_power_dyadic_b_liftrw [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.
- The step proving `hshift` (lines 41–52) carries out an explicit cancellation of integer casts (`push_cast; ring`) to establish that $(v + 2^{k+1}) - (2^{k+1} + a) = v - a$, an algebra detail that would be taken for granted on paper.
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_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