cycle_power_defective_fold_count_balance
Folding a defective model yields an exact identity relating folded count, lower-half counts and shifted defects.
Statement
theorem cycle_power_defective_fold_count_balance (L k : ℕ) (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ) (hcount : ∀ v : ℤ, (Finset.range (L+L)).sum (fun a => (y (v-(a : ℤ)) a).toNat) + (e v).toNat = k+1) (htop : ∀ v : ℤ, (Finset.range L).sum (fun a => (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+L)).toNat) + (e (v+shift)).toNat = 1) : ∀ v : ℤ, (Finset.range L).sum (fun a => (y (v-(a : ℤ)) a || y (v-(a : ℤ)) (a+L)).toNat) + (Finset.range L).sum (fun a => (y (v+(L:ℤ)-(a:ℤ)) a).toNat) + (e (v+(L:ℤ))).toNat = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + k + (e (v+shift)).toNat
- Source
- Defective half-model reduction for research thread RT-1.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- cycle_power_dyadic_defective_fold_model_of_corrected_periodicityFor any zero-phase defective dyadic model of exponent t+1, if the lower-half active count plus the defect is 2^t-periodic, folding each…
The proof, explained
The proof establishes the balance identity by evaluating the count hypothesis at v + L and splitting the 2L terms into two ranges of length L. The upper-half range is re-indexed to match the defective coordinates, and a boolean inclusion-exclusion identity—that (p || q) + (p && q) = p + q—is summed to relate the folded OR terms to the AND terms. Finally, substituting the hypothesis on AND terms evaluated at v into these relations leaves a linear system over ℕ that is resolved by linear arithmetic.
Fix an arbitrary vertex v ∈ ℤ.
We introduce the vertex v for which the balance identity is to be shown.
intro vThe count hypothesis evaluated at v + L splits into a sum over [0, L) and a sum over [L, 2L) plus the defect at v + L, equaling k + 1.
We specialize the count hypothesis hcount at v + L and split the summation over [0, 2L) into two ranges of length L using Finset.sum_range_add.
uses
Finset.sum_range_addhave hc := hcount (v+(L:ℤ)) rw [Finset.sum_range_add] at hc
The second sum of length L re-indexes to ∑_{a < L} y(v - a, a + L), updating the count equation.
For each i < L, the index simplifies as v + L - (L + i) = v - i and L + i = i + L via Nat.add_comm. Using Finset.sum_congr, the second sum rewrites to ∑_{a < L} y(v - a, a + L), so the count hypothesis at v + L becomes ∑_{a < L} y(v + L - a, a) + ∑_{a < L} y(v - a, a + L) + e(v + L) = k + 1.
uses
Finset.sum_congr,Nat.add_commhave hB : (Finset.range L).sum (fun i => (y (v+(L:ℤ)-((L+i:ℕ):ℤ)) (L+i)).toNat) = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by refine Finset.sum_congr rfl fun i _ => ?_ have hp : v+(L:ℤ)-((L+i:ℕ):ℤ) = v-(i:ℤ) := by push_cast; ring rw [hp, Nat.add_comm L i] rw [hB] at hc
The sum of the boolean disjunctions and conjunctions equals the sum of the individual component sums.
For any Booleans p and q, the identity (p || q).toNat + (p && q).toNat = p.toNat + q.toNat holds by exhaustion over the four boolean cases. Combining this pointwise equality across the sum via Finset.sum_add_distrib and Finset.sum_congr gives the inclusion-exclusion relation between the OR sum, AND sum, and component sums.
uses
Finset.sum_add_distrib,Finset.sum_congrhave hF : (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a || y (v-(a:ℤ)) (a+L)).toNat) + (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+L)).toNat) = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun a _ => ?_ cases y (v-(a:ℤ)) a <;> cases y (v-(a:ℤ)) (a+L) <;> rfl
The overlap hypothesis at v relates the conjunction sum and shifted defect to 1.
Specializing htop at vertex v yields ∑_{a < L} (y(v - a, a) && y(v - a, a + L)).toNat + e(v + shift).toNat = 1.
have hp := htop vThe balance identity holds.
Linear arithmetic over ℕ (omega) combines the split count equation, the inclusion-exclusion identity, and the overlap equation to eliminate the conjunction sum and the upper-half component sum, completing the proof.
omega
Finset.sum_range_add- Splits a sum over the range [0, n + m) into a sum over [0, n) and a sum over [0, m) with indices shifted by n.
Finset.sum_congr- Two sums over the same finite set are equal if their summands agree at every element.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
Finset.sum_add_distrib- The sum of a pointwise sum f(x) + g(x) over a finite set equals the sum of f plus the sum of g.
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.
theorem cycle_power_defective_fold_count_balance (L k : ℕ) (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ) (hcount : ∀ v : ℤ, (Finset.range (L+L)).sum (fun a => (y (v-(a : ℤ)) a).toNat) + (e v).toNat = k+1) (htop : ∀ v : ℤ, (Finset.range L).sum (fun a => (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+L)).toNat) + (e (v+shift)).toNat = 1) : ∀ v : ℤ, (Finset.range L).sum (fun a => (y (v-(a : ℤ)) a || y (v-(a : ℤ)) (a+L)).toNat) + (Finset.range L).sum (fun a => (y (v+(L:ℤ)-(a:ℤ)) a).toNat) + (e (v+(L:ℤ))).toNat = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + k + (e (v+shift)).toNat := by intro v have hc := hcount (v+(L:ℤ)) rw [Finset.sum_range_add] at hc have hB : (Finset.range L).sum (fun i => (y (v+(L:ℤ)-((L+i:ℕ):ℤ)) (L+i)).toNat) = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by refine Finset.sum_congr rfl fun i _ => ?_ have hp : v+(L:ℤ)-((L+i:ℕ):ℤ) = v-(i:ℤ) := by push_cast; ring rw [hp, Nat.add_comm L i] rw [hB] at hc have hF : (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a || y (v-(a:ℤ)) (a+L)).toNat) + (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a && y (v-(a:ℤ)) (a+L)).toNat) = (Finset.range L).sum (fun a => (y (v-(a:ℤ)) a).toNat) + (Finset.range L).sum (fun a => (y (v-(a:ℤ)) (a+L)).toNat) := by rw [← Finset.sum_add_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun a _ => ?_ cases y (v-(a:ℤ)) a <;> cases y (v-(a:ℤ)) (a+L) <;> rfl have hp := htop v omega