AFTD Auto-Formalizing Theoretical Domains

zmod_sum_sub_eq_sum

theoremverified

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

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.

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

    line 5

    uses Equiv.subRight, sum_comp

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

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