cycle_power_middle_quarter_prune_count_balance
For a four-quarter class model with parent implications, constant original active count t+1, and exact half-distance coverage, pruning gives C_pruned(v)+R(v)=t+R(v+H).
Statement
theorem cycle_power_middle_quarter_prune_count_balance (q t : ℕ) (x : ℤ → ℕ → Bool) (hleft : ∀ (p : ℤ) (a : ℕ), q ≤ a → a < 2 * q → x p a = true → x p (a + 2 * q) = true) (hright : ∀ (p : ℤ) (a : ℕ), 2 * q ≤ a → a < 3 * q → x p a = true → x p (a - 2 * q) = true) (hcount : ∀ v : ℤ, (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1) (hhalf : ∀ v : ℤ, (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = 1) : ∀ v : ℤ, (range (2 * q)).sum (fun a => ((if a < q then x (v - (a : ℤ)) a else x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) + (range (2 * q)).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = t + (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) (2 * q + 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 1
- 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 1
- cycle_power_dyadic_prune_count_balanceTight dyadic classes with constant active count t+1 and exact half-distance coverage satisfy the exact pruning balance…
The proof, explained
The proof decomposes the active counts across a range of length 4*q into four quarters of size q, denoted A, B, C, D, whose sum is t + 1 by the total count hypothesis. Using the half-distance coverage hypothesis and the directional implications between quarters, the conjunctions simplify to show that the shifted count E and the second quarter B satisfy E + B = 1. The pruned sum evaluates to A + F while the remaining sums decompose as C + D and E + F, reducing the balance equation (A + F) + (C + D) = t + (E + F) to the linear arithmetic identity (A + B + C + D) - (E + B) = t.
Fix v and establish helper lemmas for splitting length-2q sums and simplifying Boolean conjunctions under implication.
We fix an arbitrary integer v. We first prove a helper lemma htwo stating that any sum over range (2 * q) splits into two sums of length q via sum_range_add and two_mul (2 * q = q + q). We then prove two Boolean lemmas (handr and handl): if b = true implies a = true, then a && b simplifies to b; symmetrically, if a = true implies b = true, then a && b simplifies to a.
uses
two_mul,sum_range_addintro v have htwo (f : ℕ → ℕ) : (range (2 * q)).sum f = (range q).sum f + (range q).sum (fun a => f (q + a)) := by simpa only [two_mul] using (sum_range_add f q q) have handr (a b : Bool) (h : b = true → a = true) : (a && b).toNat = b.toNat := by cases a <;> cases b <;> simp_all have handl (a b : Bool) (h : a = true → b = true) : (a && b).toNat = a.toNat := by cases a <;> cases b <;> simp_all
Define the six quarter-range sums A, B, C, D, E, F.
We partition the active points into blocks of length q: A, B, C, D denote the active counts in the four quarters of the original interval of length 4 * q (offsets a, q + a, 2 * q + a, and 2 * q + (q + a) for a < q), while E and F denote the active counts in the first two quarters when shifted by 2 * q.
let A := (range q).sum (fun a => (x (v - (a : ℤ)) a).toNat) let B := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) let C := (range q).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) let D := (range q).sum (fun a => (x (v - ((2 * q + (q + a) : ℕ) : ℤ)) (2 * q + (q + a))).toNat) let E := (range q).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat) let F := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat)
The sum of the four quarters equals t + 1, that is, A + B + C + D = t + 1.
By hypothesis hcount, the total active count over range (4 * q) is t + 1. Applying cycle_power_dyadic_sum_range_four_blocks splits this into four blocks of length q. The first three blocks match the definitions of A, B, C, and using sum_congr with the index equality 2 * q + (q + a) = 3 * q + a shows the fourth block matches D.
uses
cycle_power_dyadic_sum_range_four_blocks,sum_congrhave hfull : A + B + C + D = t + 1 := by have hh := hcount v have hs := cycle_power_dyadic_sum_range_four_blocks q (fun a => (x (v - (a : ℤ)) a).toNat) change (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 at hh rw [hs] at hh have hD : D = (range q).sum (fun a => (x (v - ((3 * q + a : ℕ) : ℤ)) (3 * q + a)).toNat) := by apply sum_congr rfl intro a ha rw [show 2 * q + (q + a) = 3 * q + a by omega] rw [hD] exact hh
The half-distance overlap sum gives E + B = 1.
Hypothesis hhalf asserts that the pairwise conjunction sum over range (2 * q) equals 1. Splitting this range into two blocks of length q using htwo: for the first block (a < q), index a + 2 * q is in [2 * q, 3 * q), so by hright and Nat.add_sub_cancel_right, x (v - a) (a + 2 * q) = true implies x (v - a) a = true, simplifying the conjunction to x (v - a) (2 * q + a) (via Nat.add_comm and handr), which sums to E; for the second block (q + a), by hleft, x (v - (q + a)) (q + a) = true implies x (v - (q + a)) (q + a + 2 * q) = true, simplifying the conjunction to x (v - (q + a)) (q + a) via handl, which sums to B. Both block simplifications use sum_congr. Hence E + B = 1.
uses
sum_congr,Nat.add_sub_cancel_right,Nat.add_commhave hmid : E + B = 1 := by have hh := hhalf v rw [htwo] at hh have hfirst : (range q).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = E := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp : x (v - (a : ℤ)) (a + 2 * q) = true → x (v - (a : ℤ)) a = true := by intro hx have hh := hright (v - (a : ℤ)) (a + 2 * q) (by omega) (by omega) hx simpa only [Nat.add_sub_cancel_right] using hh simpa only [Nat.add_comm a (2 * q)] using handr _ _ hp have hsecond : (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a) && x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat) = B := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha exact handl _ _ (hleft _ _ (by omega) (by omega)) rw [hfirst, hsecond] at hh exact hh
The pruned sum over range (2 * q) decomposes as A + F.
Splitting the pruned sum into two blocks of length q via htwo: for the first block (a < q), if_pos simplifies the summand to x (v - a) a, summing to A; for the second block (offset q + a), since q + a < q is false, if_neg selects the shifted component x (v - (q + a)) (q + a + 2 * q), which by index arithmetic matches the definition of F. Both steps use sum_congr.
uses
sum_congr,if_pos,if_neghave hprune : (range (2 * q)).sum (fun a => ((if a < q then x (v - (a : ℤ)) a else x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) = A + F := by rw [htwo] congr 1 · apply sum_congr rfl intro a ha rw [if_pos (mem_range.mp ha)] · apply sum_congr rfl intro a ha rw [if_neg (by omega : ¬q + a < q)] change (x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat = (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat rw [show q + a + 2 * q = 2 * q + (q + a) by omega]
The remaining two sums decompose as C + D and E + F, respectively.
Applying the splitting lemma htwo directly to the second sum on the left-hand side yields C + D, and applying it to the sum on the right-hand side yields E + F.
have hrightcount : (range (2 * q)).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = C + D := htwo _ have hshiftcount : (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat) = E + F := htwo _
The balance equation holds by linear integer arithmetic.
Rewriting with the decompositions from the previous steps reduces the theorem to (A + F) + (C + D) = t + (E + F). Linear arithmetic (omega) closes this from A + B + C + D = t + 1 and E + B = 1, as (A + F + C + D) - (t + E + F) = (A + B + C + D) - (t + 1) + 1 - (E + B) = 0.
rw [hprune, hrightcount, hshiftcount] omega
two_mul- Multiplication by 2 equals addition to self: 2 * n = n + n.
sum_range_add- A sum over range (n + m) splits into the sum over range n and the sum over range m shifted by n.
cycle_power_dyadic_sum_range_four_blocks- A sum over range (4 * L) splits into four sums over range L with offsets 0, L, 2 * L, and 3 * L.
sum_congr- Two sums over the same finite set are equal if their summands agree on every element.
Nat.add_sub_cancel_right- Subtracting m from n + m yields n: n + m - m = n.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
if_pos- An if-then-else evaluates to the then-branch when the condition is true.
if_neg- An if-then-else evaluates to the else-branch when the condition is false.
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_middle_quarter_prune_count_balance (q t : ℕ) (x : ℤ → ℕ → Bool) (hleft : ∀ (p : ℤ) (a : ℕ), q ≤ a → a < 2 * q → x p a = true → x p (a + 2 * q) = true) (hright : ∀ (p : ℤ) (a : ℕ), 2 * q ≤ a → a < 3 * q → x p a = true → x p (a - 2 * q) = true) (hcount : ∀ v : ℤ, (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1) (hhalf : ∀ v : ℤ, (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = 1) : ∀ v : ℤ, (range (2 * q)).sum (fun a => ((if a < q then x (v - (a : ℤ)) a else x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) + (range (2 * q)).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = t + (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat) := by intro v have htwo (f : ℕ → ℕ) : (range (2 * q)).sum f = (range q).sum f + (range q).sum (fun a => f (q + a)) := by simpa only [two_mul] using (sum_range_add f q q) have handr (a b : Bool) (h : b = true → a = true) : (a && b).toNat = b.toNat := by cases a <;> cases b <;> simp_all have handl (a b : Bool) (h : a = true → b = true) : (a && b).toNat = a.toNat := by cases a <;> cases b <;> simp_all let A := (range q).sum (fun a => (x (v - (a : ℤ)) a).toNat) let B := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) let C := (range q).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) let D := (range q).sum (fun a => (x (v - ((2 * q + (q + a) : ℕ) : ℤ)) (2 * q + (q + a))).toNat) let E := (range q).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat) let F := (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat) have hfull : A + B + C + D = t + 1 := by have hh := hcount v have hs := cycle_power_dyadic_sum_range_four_blocks q (fun a => (x (v - (a : ℤ)) a).toNat) change (range (4 * q)).sum (fun a => (x (v - (a : ℤ)) a).toNat) = t + 1 at hh rw [hs] at hh have hD : D = (range q).sum (fun a => (x (v - ((3 * q + a : ℕ) : ℤ)) (3 * q + a)).toNat) := by apply sum_congr rfl intro a ha rw [show 2 * q + (q + a) = 3 * q + a by omega] rw [hD] exact hh have hmid : E + B = 1 := by have hh := hhalf v rw [htwo] at hh have hfirst : (range q).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 * q)).toNat) = E := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp : x (v - (a : ℤ)) (a + 2 * q) = true → x (v - (a : ℤ)) a = true := by intro hx have hh := hright (v - (a : ℤ)) (a + 2 * q) (by omega) (by omega) hx simpa only [Nat.add_sub_cancel_right] using hh simpa only [Nat.add_comm a (2 * q)] using handr _ _ hp have hsecond : (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a) && x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat) = B := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha exact handl _ _ (hleft _ _ (by omega) (by omega)) rw [hfirst, hsecond] at hh exact hh have hprune : (range (2 * q)).sum (fun a => ((if a < q then x (v - (a : ℤ)) a else x (v - (a : ℤ)) (a + 2 * q)) : Bool).toNat) = A + F := by rw [htwo] congr 1 · apply sum_congr rfl intro a ha rw [if_pos (mem_range.mp ha)] · apply sum_congr rfl intro a ha rw [if_neg (by omega : ¬q + a < q)] change (x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 * q)).toNat = (x (v - ((q + a : ℕ) : ℤ)) (2 * q + (q + a))).toNat rw [show q + a + 2 * q = 2 * q + (q + a) by omega] have hrightcount : (range (2 * q)).sum (fun a => (x (v - ((2 * q + a : ℕ) : ℤ)) (2 * q + a)).toNat) = C + D := htwo _ have hshiftcount : (range (2 * q)).sum (fun a => (x (v - (a : ℤ)) (2 * q + a)).toNat) = E + F := htwo _ rw [hprune, hrightcount, hshiftcount] omega