cycle_power_dyadic_prune_count_iff_right_half_period
Under the dyadic pruning balance hypotheses, preservation of active count t is equivalent to half-radius periodicity of right-half memberships.
Statement
theorem cycle_power_dyadic_prune_count_iff_right_half_period (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) = t) ↔ (∀ v, (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 - ((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 3
- 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
Under the dyadic pruning balance hypotheses, the pruning balance identity establishes that for every shift v, the lifted active count sum L(v) plus the right-half membership sum S(v) equals t + S(v + 2^(k+1)). The equivalence between active count preservation (L(v) = t for all v) and half-radius periodicity (S(v + 2^(k+1)) = S(v) for all v) follows immediately: substituting either equality into the balance identity reduces it to the other by additive cancellation in ℕ.
For every coordinate v ∈ ℤ, the balance equation L(v) + S(v) = t + S(v + 2^(k+1)) holds between the lifted active count sum L(v) and the right-half membership sums S(v) and S(v + 2^(k+1)); proving the equivalence reduces to verifying both implications.
We invoke cycle_power_dyadic_prune_count_balance with the tightness (htight), diagonal count (hcount), and overlap (hhalf) hypotheses to obtain the balance relation hb for all shifts v. We then split the if-and-only-if goal into forward and reverse implications.
uses
cycle_power_dyadic_prune_count_balancehave hb := cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf constructor
If the lifted active count is t for all shifts, then the right-half membership sum is periodic with period 2^(k+1).
Assuming L(v) = t for all v (hypothesis hc), fix an arbitrary shift v ∈ ℤ. Specializing the balance equation hb to v gives L(v) + S(v) = t + S(v + 2^(k+1)). Rewriting with hc v replaces L(v) with t, yielding t + S(v) = t + S(v + 2^(k+1)). Linear integer arithmetic (omega) cancels t from both sides, concluding S(v + 2^(k+1)) = S(v).
· intro hc v have hh := hb v rw [hc v] at hh omega
Conversely, if the right-half membership sum is periodic with period 2^(k+1), then the lifted active count is t for all shifts.
Assuming S(v + 2^(k+1)) = S(v) for all v (hypothesis hr), fix an arbitrary shift v ∈ ℤ. Specializing the balance equation hb to v gives L(v) + S(v) = t + S(v + 2^(k+1)). Rewriting with hr v replaces S(v + 2^(k+1)) with S(v), yielding L(v) + S(v) = t + S(v). Linear integer arithmetic (omega) cancels S(v) from both sides, concluding L(v) = t.
· intro hr v have hh := hb v rw [hr v] at hh omega
cycle_power_dyadic_prune_count_balance- Under the dyadic pruning tightness, active count, and overlap hypotheses, for every shift v, the sum of the lifted active indicators plus the right-half membership sum at v equals t plus the shifted right-half membership sum at v + 2^(k+1).
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_iff_right_half_period (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) = t) ↔ (∀ v, (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 - ((2 ^ (k + 1) + a : ℕ) : ℤ)) (2 ^ (k + 1) + a)).toNat)) := by have hb := cycle_power_dyadic_prune_count_balance k t x htight hcount hhalf constructor · intro hc v have hh := hb v rw [hc v] at hh omega · intro hr v have hh := hb v rw [hr v] at hh omega