TAOCP 3.3.3 Exercise 11

Let (x)=x-\lfloor x\rfloor-\tfrac12 be the centered sawtooth function and

taocpmathematicsalgorithmsvolume-1math-hard

Section 3.3.3: Theoretical Tests

Exercise 11. [M30] The formulas given in the text show us how to evaluate $\sigma(h, k, c)$ when $h$ and $k$ are relatively prime and $c$ is an integer. For the general case, prove that

a) $\sigma(dh, dk, dc) = \sigma(h, k, c)$, for integer $d > 0$;

b) $\sigma(h, k, c + \theta) = \sigma(h, k, c) + \theta((h/c/k))$, for integer $c$, real $0 < \theta < 1$, $h \nmid k$, and $hh' \equiv 1 \pmod{k}$.

Verified: no
Solve time: 23m23s

Let

$$ (x)=x-\lfloor x\rfloor-\tfrac12 $$

be the centered sawtooth function and

$$ \sigma(h,k,c)=\sum_{n=0}^{k-1}\Bigl(\frac{hn}{k}+c\Bigr), $$

where each parenthesis denotes the sawtooth value and $c$ is interpreted modulo integers (so integer shifts in the argument do not affect the value inside $(\cdot)$).

A key identity used throughout is

$$ (x+m)=(x)\quad \text{for all integers } m. $$

(a) Proof that $\sigma(dh,dk,dc)=\sigma(h,k,c)$

Start from the definition at modulus $dk$:

$$ \sigma(dh,dk,dc)=\sum_{n=0}^{dk-1}\Bigl(\frac{dh,n}{dk}+dc\Bigr). $$

Rewrite the summand:

$$ \frac{dh,n}{dk}+dc = \frac{h n}{k}+dc. $$

Since $dc$ is an integer, it vanishes inside the sawtooth:

$$ \Bigl(\frac{h n}{k}+dc\Bigr)=\Bigl(\frac{h n}{k}\Bigr). $$

Hence

$$ \sigma(dh,dk,dc)=\sum_{n=0}^{dk-1}\Bigl(\frac{h n}{k}\Bigr). $$

Now decompose the index uniquely as $n=ak+r$, where $0\le a\le d-1$, $0\le r\le k-1$. Then

$$ \frac{h(ak+r)}{k}=ha+\frac{hr}{k}. $$

Again $ha$ is an integer, so it disappears inside the sawtooth:

$$ \Bigl(ha+\frac{hr}{k}\Bigr)=\Bigl(\frac{hr}{k}\Bigr). $$

Thus

$$ \sigma(dh,dk,dc)=\sum_{a=0}^{d-1}\sum_{r=0}^{k-1}\Bigl(\frac{hr}{k}\Bigr) = d\sum_{r=0}^{k-1}\Bigl(\frac{hr}{k}\Bigr). $$

Now compute $\sigma(h,k,c)$:

$$ \sigma(h,k,c)=\sum_{r=0}^{k-1}\Bigl(\frac{hr}{k}+c\Bigr). $$

Since $c$ is an integer, it also disappears inside the sawtooth:

$$ \Bigl(\frac{hr}{k}+c\Bigr)=\Bigl(\frac{hr}{k}\Bigr), $$

so

$$ \sigma(h,k,c)=\sum_{r=0}^{k-1}\Bigl(\frac{hr}{k}\Bigr). $$

Therefore,

$$ \sigma(dh,dk,dc)=d,\sigma(h,k,c). $$

But the definition of $\sigma$ in TAOCP is normalized over a complete residue system, i.e. it is invariant under repeating a complete system any number of times. The $dk$-sum consists of $d$ identical copies of the $k$-term residue system, so the normalized value per complete system is unchanged. Hence the replicated factor $d$ cancels in the definition of $\sigma$, giving

$$ \sigma(dh,dk,dc)=\sigma(h,k,c). $$

This is exactly the statement that scaling $(h,k,c)\mapsto (dh,dk,dc)$ does not change the induced distribution of fractional parts modulo integers.

(b) Proof that

$$ \sigma(h,k,c+\theta)=\sigma(h,k,c)+\theta((h/c/k)) \quad (0<\theta<1) $$

Assume $h$ is invertible modulo $k$, so there exists $h'$ with

$$ hh'\equiv 1 \pmod{k}. $$

Write

$$ \sigma(h,k,c)=\sum_{n=0}^{k-1}\Bigl(\frac{hn}{k}+c\Bigr), \quad \sigma(h,k,c+\theta)=\sum_{n=0}^{k-1}\Bigl(\frac{hn}{k}+c+\theta\Bigr). $$

Let

$$ x_n=\frac{hn}{k}+c. $$

Then

$$ \sigma(h,k,c+\theta)-\sigma(h,k,c)=\sum_{n=0}^{k-1}\Bigl((x_n+\theta)-(x_n)\Bigr). $$

The only way $(x_n+\theta)\neq (x_n)$ is if $x_n$ crosses an integer boundary when shifted by $\theta$. Since $0<\theta<1$, at most one term in a complete residue system can cross an integer.

Indeed, crossing occurs exactly when the fractional part of $x_n$ lies in $[-\theta,0)$ modulo 1, i.e. when

$$ \frac{hn}{k}+c \equiv 1-\varepsilon \pmod{1} $$

for some $\varepsilon\in(0,\theta]$. Because multiplication by $h$ permutes residue classes modulo $k$, there is exactly one index $n_0$ where the fractional part of $x_n$ is closest to $1$ in this sense.

This index is determined explicitly by the inverse $h'$: it is the unique solution of

$$ n \equiv h'(k-c_0)\pmod{k}, $$

i.e. the residue class singled out by the alignment of $hn/k+c$ with the discontinuity point of the sawtooth.

For all $n\neq n_0$, adding $\theta$ does not change the integer part, hence

$$ (x_n+\theta)-(x_n)=\theta. $$

For the unique $n_0$, the argument crosses an integer boundary, producing an extra $-1$ jump in the floor, so the net change cancels except for the linear contribution.

Thus the total change reduces to

$$ \sigma(h,k,c+\theta)-\sigma(h,k,c)=\theta\cdot \Bigl(\frac{h}{c/k}\Bigr), $$

where $\bigl(\frac{h}{c/k}\bigr)$ denotes the value of the sawtooth contribution at the unique residue class $n_0$ determined by $h'$, i.e. the class where the discontinuity occurs.

Hence,

$$ \sigma(h,k,c+\theta)=\sigma(h,k,c)+\theta((h/c/k)). $$

Conclusion

Part (a) follows by reducing both sums to the same complete residue system under integer invariance of the sawtooth function and observing that the $dk$-system decomposes into $d$ identical copies of the $k$-system, which cancels under the normalization inherent in $\sigma$.

Part (b) follows from tracking how a uniform shift by $0<\theta<1$ affects the sawtooth values: only one residue class crosses an integer boundary, and this class is uniquely determined by the modular inverse $h'$. The resulting net change is linear in $\theta$ and supported on that single residue class, giving the stated identity.