TAOCP 3.3.3 Exercise 10
Let $\sigma(h,k,c)$ be the sawtooth sum used in the TAOCP context, where the key structure is a sum over a complete residue system modulo $k$ of a shifted sawtooth expression of the form \sigma(h,k,c)...
Section 3.3.3: Theoretical Tests
Exercise 10. [M20] Show that when $0 < h < k$ it is possible to express $\sigma(k-h, k, c)$ and $\sigma(h, k, -c)$ easily in terms of $\sigma(h, k, c)$.
Verified: yes
Solve time: 15m12s
Let $\sigma(h,k,c)$ be the sawtooth sum used in the TAOCP context, where the key structure is a sum over a complete residue system modulo $k$ of a shifted sawtooth expression of the form
$$ \sigma(h,k,c) = \sum_{n=0}^{k-1} \left(\frac{hn}{k} + c \right), $$
where $(x) = x - \lfloor x \rfloor - \tfrac{1}{2}$ is the centered sawtooth function (any equivalent TAOCP normalization leads to the same symmetry argument used below). The only properties needed are periodicity modulo integers and the odd symmetry $( -x ) = - (x)$.
The problem asks to relate the values obtained when replacing $h$ by $k-h$ and $c$ by $-c$ to the original quantity $\sigma(h,k,c)$ when $0 < h < k$.
Key structural observation
Because $h$ and $k-h$ are complements modulo $k$, multiplication by $k-h$ permutes the residue system in the opposite direction of multiplication by $h$. Concretely, the map
$$ n \mapsto (k-n) \pmod{k} $$
is a bijection on ${0,1,\dots,k-1}$, and it reverses the order of residues.
This reversal is the only ingredient needed. The sawtooth function converts linear expressions into periodic ones, and reversing the index flips the sign of the centered fractional part.
First identity: $\sigma(k-h,k,c)$
Start from the definition:
$$ \sigma(k-h,k,c) = \sum_{n=0}^{k-1} \left( \frac{(k-h)n}{k} + c \right). $$
Rewrite the linear term:
$$ \frac{(k-h)n}{k} = n - \frac{hn}{k}. $$
Thus
$$ \left(\frac{(k-h)n}{k} + c\right) = \left(n + c - \frac{hn}{k}\right). $$
Since the sawtooth function is periodic modulo integers, adding the integer $n$ does not change its contribution:
$$ (n + x) = (x). $$
Therefore,
$$ \left(n + c - \frac{hn}{k}\right) = \left(c - \frac{hn}{k}\right). $$
Using odd symmetry of the sawtooth function,
$$ (c - x) = -(x - c), $$
we get
$$ \left(c - \frac{hn}{k}\right) = -\left(\frac{hn}{k} - c\right). $$
Hence
$$ \sigma(k-h,k,c) = - \sum_{n=0}^{k-1} \left(\frac{hn}{k} - c\right) = -\sigma(h,k,-c). $$
So the first relation is
$$ \sigma(k-h,k,c) = -\sigma(h,k,-c). $$
Second identity: $\sigma(h,k,-c)$
Apply the same symmetry directly to the definition:
$$ \sigma(h,k,-c) = \sum_{n=0}^{k-1} \left(\frac{hn}{k} - c\right). $$
Using oddness again,
$$ \left(\frac{hn}{k} - c\right) = -\left(\frac{hn}{k} + c\right). $$
Therefore,
$$ \sigma(h,k,-c) = - \sum_{n=0}^{k-1} \left(\frac{hn}{k} + c\right) = -\sigma(h,k,c). $$
Final relationships
Combining both results:
$$ \sigma(h,k,-c) = -\sigma(h,k,c), $$
$$ \sigma(k-h,k,c) = -\sigma(h,k,-c) = \sigma(h,k,c). $$
So both expressions reduce immediately to $\sigma(h,k,c)$ up to sign changes induced by $c \mapsto -c$ and $h \mapsto k-h$.
Why this works
The entire structure rests on two invariances: periodicity of the sawtooth function under integer shifts, and odd symmetry under sign reversal. The substitution $h \mapsto k-h$ introduces an integer shift plus a sign flip in the fractional part, while $c \mapsto -c$ contributes an independent sign flip. The sum over a complete residue system ensures that index reparametrization introduces no boundary effects, so the transformations carry through term-by-term without correction terms.