AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_zmod_model_tight_of_counts

theoremverified

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
Used by 1

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.

  1. 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).

    lines 13–15

      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)
  2. 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.

    lines 16–28

    uses sum_comm, sum_congr, zmod_sum_sub_eq_sum

      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
  3. 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.

    lines 29–31

    uses pow_zero, sum_range_one, Nat.zero_add

      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]
  4. 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.

    lines 32–45

    uses sum_add_distrib, mul_sum, sum_comm, sum_congr, sum_const_zero, sum_range_succ', Nat.add_mul

      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
  5. 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`).

    lines 46–55

    uses sum_comm, sum_congr, zmod_sum_sub_eq_sum, Nat.mul_comm

      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]
  6. 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.

    line 56

    uses cycle_power_dyadic_class_weight_eq_of_sum_eq

      exact 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.

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

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)
See it in the graphDiscuss this resultChallenge it