zmod_sum_sub_eq_sum
Summation of any natural function over ZMod n is invariant under subtraction by a constant residue.
Statement
theorem zmod_sum_sub_eq_sum
(n : ℕ) [NeZero n] (g : ZMod n → ℕ) (a : ZMod n) :
(∑ p : ZMod n, g p) = ∑ v : ZMod n, g (v - a)- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- cycle_power_dyadic_central_position_existsIn a periodic tight dyadic class model with exact dyadic coverage and coverage at all lower neighbour distances, some class uses one of…
- cycle_power_dyadic_zmod_model_tight_of_countsFor a positive exponent m, nonzero natural period n, and Boolean profiles indexed by ZMod n, exact dyadic edge-owner sums of one and…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
The proof, explained
The theorem states that summing a function g over ZMod n is invariant under shifting the argument by a constant residue a. Right-subtraction by a is an equivalence of ZMod n with itself, so reindexing the summation by this bijection leaves the sum unchanged. Taking the symmetry of this equality produces the theorem statement.
The sum of g(p) over all p in ZMod n is equal to the sum of g(v - a) over all v in ZMod n.
The map v ↦ v - a is an equivalence of ZMod n with itself via `Equiv.subRight a`. By `sum_comp`, reindexing the sum of g over ZMod n by this equivalence does not change the total sum, giving ∑ v, g (v - a) = ∑ p, g p. Applying symmetry to this equality completes the proof.
uses
Equiv.subRight,sum_compexact (Equiv.subRight a).sum_comp g |>.symm
Equiv.subRight- Right-subtraction by a fixed element in an additive group is an equivalence (a bijection) of the group with itself.
sum_comp- Summing the composition of a function with an equivalence between finite types is equal to summing the function over the type.
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.
/-- Summation of any natural function over ZMod n is invariant under subtraction by a constant residue. -/theorem zmod_sum_sub_eq_sum (n : ℕ) [NeZero n] (g : ZMod n → ℕ) (a : ZMod n) : (∑ p : ZMod n, g p) = ∑ v : ZMod n, g (v - a) := by exact (Equiv.subRight a).sum_comp g |>.symm