cycle_power_dyadic_zmod_model_tight_of_counts
For a positive exponent m, nonzero natural period n, and Boolean profiles indexed by ZMod n, exact dyadic edge-owner sums of one and exactly m+1 active rooted profiles at each residue force each profile's dyadic class weight to equal its selected-offset count. No ordinary-edge coverage or shape hypothesis is assumed.
Statement
theorem cycle_power_dyadic_zmod_model_tight_of_counts (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool) (hcount : ∀ v : ZMod n, (range (2^m)).sum (fun a => (b (v-(a : ZMod n)) a).toNat) = m+1) (hexact : ∀ j < m, ∀ v : ZMod n, (range (2^j)).sum (fun a => (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat) = 1) : ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) = (range (2^m)).sum (fun a => (b p a).toNat)
- Source
- Uniform actual-cover extraction for OP-205 / RT-1 following arXiv:2610.15635. The anchored-arc lemma is geometric bookkeeping. The saturation helpers double-count exact dyadic owners and active classes over a period; they do not classify class shapes or settle the graph covering value. No research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- zmod_sum_sub_eq_sumSummation of any natural function over ZMod n is invariant under subtraction by a constant residue.
- cycle_power_dyadic_class_weight_eq_of_sum_eqIf the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every…
- Used by 1
- cycle_power_dyadic_periodic_model_tight_of_countsFor a positive exponent m, nonzero natural period n, and periodic Boolean profiles indexed by the integers, exact dyadic edge-owner sums…
The proof, explained
To prove that each profile's dyadic class weight equals its selected-offset count, it suffices by `cycle_power_dyadic_class_weight_eq_of_sum_eq` to show that their sums over all residues p ∈ ZMod n coincide. For each dyadic scale j < m, reindexing the sum of active pairs via p = v - a turns it into the exact edge-owner sum at v, which equals 1 by hypothesis, totaling n across all residues. Summing the decomposed class weights over all residues then yields 2n + (m - 1)n = (m + 1)n, while reindexing the total offset counts using the count hypothesis similarly yields (m + 1)n, completing the proof.
Define N(j, p) as the number of active dyadic pairs at scale j in profile b(p).
Working classically, define for scale j < m and residue p ∈ ZMod n the quantity N(j, p) = ∑_{a ∈ range (2^j)} (b(p, a) && b(p, a + 2^m - 2^j)).toNat, which counts how many dyadic pairs at scale j are simultaneously active in profile b(p).
classical let N : ℕ → ZMod n → ℕ := fun j p => (range (2^j)).sum (fun a => (b p a && b p (a+2^m-2^j)).toNat)
For each scale j < m, the sum of N(j, p) over all residues p ∈ ZMod n equals n.
Unfold the definition of N and swap the order of summation using `sum_comm`. For each fixed offset a, reindex the sum over residues p to a sum over v by setting p = v - a, justified by `zmod_sum_sub_eq_sum` inside `sum_congr`. Swapping the sums back (`sum_comm`), the inner sum over a becomes the exact dyadic edge-owner sum at residue v, which equals 1 by hypothesis `hexact`. Summing 1 over all n elements of ZMod n gives n.
uses
sum_comm,sum_congr,zmod_sum_sub_eq_sumhave hN (j : ℕ) (hj : j < m) : (∑ p : ZMod n, N j p) = n := by dsimp only [N] rw [sum_comm] calc _ = ∑ a ∈ range (2^j), ∑ v : ZMod n, (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat := by apply sum_congr rfl intro a ha exact zmod_sum_sub_eq_sum n _ (a : ZMod n) _ = ∑ v : ZMod n, ∑ a ∈ range (2^j), (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat := sum_comm _ = ∑ v : ZMod n, 1 := by simp_rw [hexact j hj] _ = n := by simp
For each residue p, the dyadic class weight of b(p) decomposes into 2 * N(0, p) plus the sum of N(j, p) for non-zero scales j < m.
Unfold `cycle_power_dyadic_class_weight` and N. For j = 0, the range is range (2^0) = range 1 (`pow_zero`), whose sum is the single term at a = 0 (`sum_range_one`, `Nat.zero_add`), matching 2 * N(0, p). For the remaining scales j < m, the indicator if j = 0 then 0 else N(j, p) directly reproduces the non-zero scale terms of the definition.
uses
pow_zero,sum_range_one,Nat.zero_addhave hw (p : ZMod n) : cycle_power_dyadic_class_weight m (b p) = 2*N 0 p+(range m).sum (fun j => if j=0 then 0 else N j p) := by simp only [cycle_power_dyadic_class_weight, N, pow_zero, sum_range_one, Nat.zero_add]
The sum of the dyadic class weights over all residues p ∈ ZMod n equals (m + 1) * n.
Rewrite each class weight using the decomposition from `hw`. Split the sum over p into two parts using `sum_add_distrib`. The first part is 2 * ∑_p N(0, p), which equals 2 * n by `hN` evaluated at j = 0 (since 1 ≤ m implies 0 < m). In the second part, swap the sums over p and j using `sum_comm`. For j = 0, the summand is identically zero (`sum_const_zero`); for each j ∈ {1, ..., m - 1}, the sum over p gives n by `hN`. Writing m = k + 1, the remaining sum evaluates to k * n (`sum_range_succ'`, `Nat.add_mul`), giving a total sum of 2 * n + (m - 1) * n = (m + 1) * n via linear arithmetic.
uses
sum_add_distrib,mul_sum,sum_comm,sum_congr,sum_const_zero,sum_range_succ',Nat.add_mulhave hW : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) = (m+1)*n := by simp_rw [hw] rw [sum_add_distrib, ← mul_sum, hN 0 (by omega), sum_comm] have he : (range m).sum (fun j => ∑ p : ZMod n, if j=0 then 0 else N j p) = (range m).sum (fun j => if j=0 then 0 else n) := by apply sum_congr rfl intro j hj by_cases hj0 : j=0 · simp only [hj0, ↓reduceIte, sum_const_zero] · simp only [hj0, ↓reduceIte] exact hN j (mem_range.mp hj) rw [he] obtain ⟨k, rfl⟩ : ∃ k, m=k+1 := ⟨m-1, by omega⟩ simp [sum_range_succ', Nat.add_mul] <;> omega
The sum of the selected-offset counts over all residues p ∈ ZMod n equals (m + 1) * n.
Swap the order of summation over p ∈ ZMod n and a ∈ range (2^m) using `sum_comm`. For each offset a, substitute p = v - a via `zmod_sum_sub_eq_sum` (congruence via `sum_congr`). Swapping the sums back (`sum_comm`), the inner sum over a is the active rooted profile count at residue v, which equals m + 1 by hypothesis `hcount`. Summing m + 1 over all n residues of ZMod n yields (m + 1) * n (`Nat.mul_comm`).
uses
sum_comm,sum_congr,zmod_sum_sub_eq_sum,Nat.mul_commhave hC : (∑ p : ZMod n, (range (2^m)).sum (fun a => (b p a).toNat)) = (m+1)*n := by rw [sum_comm] calc _ = ∑ a ∈ range (2^m), ∑ v : ZMod n, (b (v-(a : ZMod n)) a).toNat := by apply sum_congr rfl intro a ha exact zmod_sum_sub_eq_sum n _ (a : ZMod n) _ = ∑ v : ZMod n, ∑ a ∈ range (2^m), (b (v-(a : ZMod n)) a).toNat := sum_comm _ = ∑ v : ZMod n, (m+1) := by simp_rw [hcount] _ = (m+1)*n := by simp [Nat.mul_comm]
For every residue p, the dyadic class weight of b(p) equals its selected-offset count.
Because the total dyadic class weight and the total selected-offset count summed over all residues both equal (m + 1) * n, they are equal to each other. The rigidity lemma `cycle_power_dyadic_class_weight_eq_of_sum_eq` then deduces that the class weight and offset count must agree pointwise for every residue p ∈ ZMod n.
uses
cycle_power_dyadic_class_weight_eq_of_sum_eqexact cycle_power_dyadic_class_weight_eq_of_sum_eq m n hm b (hW.trans hC.symm)
sum_comm- The order of two finite summations can be exchanged: ∑_{x ∈ s} ∑_{y ∈ t} f(x, y) = ∑_{y ∈ t} ∑_{x ∈ s} f(x, y).
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every index.
zmod_sum_sub_eq_sum- Summing any function g over all residues p ∈ ZMod n is invariant under translating the index by a fixed offset a: ∑_p g(p) = ∑_v g(v - a).
pow_zero- Any element raised to power 0 equals 1: a ^ 0 = 1.
sum_range_one- The sum of a function over the singleton range {0} is simply its value at 0: ∑_{k ∈ range 1} f(k) = f(0).
Nat.zero_add- Zero added to any natural number n is n: 0 + n = n.
sum_add_distrib- A finite sum of two functions splits into the sum of the sums: ∑_{x ∈ s} (f(x) + g(x)) = ∑_{x ∈ s} f(x) + ∑_{x ∈ s} g(x).
mul_sum- A scalar factor distributes over a finite sum: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} (a * f(i)).
sum_const_zero- The sum of the constant function 0 over any finite set is 0.
sum_range_succ'- Peeling off the k = 0 term in a range sum: ∑_{k ∈ range (n + 1)} f(k) = ∑_{k ∈ range n} f(k + 1) + f(0).
Nat.add_mul- Right distributivity of multiplication over addition for natural numbers: (n + m) * k = n * k + m * k.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
cycle_power_dyadic_class_weight_eq_of_sum_eq- For profiles on ZMod n with m ≥ 1, if the sum of dyadic class weights over all residues equals the sum of selected-offset counts over all residues, then they are equal at every residue.
- The proof delegates the pointwise deduction to `cycle_power_dyadic_class_weight_eq_of_sum_eq`, a rigidity lemma proved elsewhere in the library stating that equality of the sums over all residues forces pointwise equality of the dyadic class weight and offset count.
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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_zmod_model_tight_of_counts (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool) (hcount : ∀ v : ZMod n, (range (2^m)).sum (fun a => (b (v-(a : ZMod n)) a).toNat) = m+1) (hexact : ∀ j < m, ∀ v : ZMod n, (range (2^j)).sum (fun a => (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat) = 1) : ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) = (range (2^m)).sum (fun a => (b p a).toNat) := by classical let N : ℕ → ZMod n → ℕ := fun j p => (range (2^j)).sum (fun a => (b p a && b p (a+2^m-2^j)).toNat) have hN (j : ℕ) (hj : j < m) : (∑ p : ZMod n, N j p) = n := by dsimp only [N] rw [sum_comm] calc _ = ∑ a ∈ range (2^j), ∑ v : ZMod n, (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat := by apply sum_congr rfl intro a ha exact zmod_sum_sub_eq_sum n _ (a : ZMod n) _ = ∑ v : ZMod n, ∑ a ∈ range (2^j), (b (v-(a : ZMod n)) a && b (v-(a : ZMod n)) (a+2^m-2^j)).toNat := sum_comm _ = ∑ v : ZMod n, 1 := by simp_rw [hexact j hj] _ = n := by simp have hw (p : ZMod n) : cycle_power_dyadic_class_weight m (b p) = 2*N 0 p+(range m).sum (fun j => if j=0 then 0 else N j p) := by simp only [cycle_power_dyadic_class_weight, N, pow_zero, sum_range_one, Nat.zero_add] have hW : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) = (m+1)*n := by simp_rw [hw] rw [sum_add_distrib, ← mul_sum, hN 0 (by omega), sum_comm] have he : (range m).sum (fun j => ∑ p : ZMod n, if j=0 then 0 else N j p) = (range m).sum (fun j => if j=0 then 0 else n) := by apply sum_congr rfl intro j hj by_cases hj0 : j=0 · simp only [hj0, ↓reduceIte, sum_const_zero] · simp only [hj0, ↓reduceIte] exact hN j (mem_range.mp hj) rw [he] obtain ⟨k, rfl⟩ : ∃ k, m=k+1 := ⟨m-1, by omega⟩ simp [sum_range_succ', Nat.add_mul] <;> omega have hC : (∑ p : ZMod n, (range (2^m)).sum (fun a => (b p a).toNat)) = (m+1)*n := by rw [sum_comm] calc _ = ∑ a ∈ range (2^m), ∑ v : ZMod n, (b (v-(a : ZMod n)) a).toNat := by apply sum_congr rfl intro a ha exact zmod_sum_sub_eq_sum n _ (a : ZMod n) _ = ∑ v : ZMod n, ∑ a ∈ range (2^m), (b (v-(a : ZMod n)) a).toNat := sum_comm _ = ∑ v : ZMod n, (m+1) := by simp_rw [hcount] _ = (m+1)*n := by simp [Nat.mul_comm] exact cycle_power_dyadic_class_weight_eq_of_sum_eq m n hm b (hW.trans hC.symm)