TAOCP 3.3.3 Exercise 5

Exercise 5. [M21] Carry out the derivation of Eq. (17).

Verified: no
Solve time: 2m14s

Solution

From Eq. (14),

$$ C=\frac{m\sum_{0\le x<m} x,s(x)-\left(\sum_{0\le x<m}x\right)^2}{m\sum_{0\le x<m}x^2-\left(\sum_{0\le x<m}x\right)^2}. $$

The standard sums are

$$ \sum_{0\le x<m}x=\frac{m(m-1)}{2},\qquad \sum_{0\le x<m}x^2=\frac{m(m-\tfrac12)(m-1)}{3}. $$

Hence

$$ m\sum x^2-\left(\sum x\right)^2 = m^2\frac{(m-\tfrac12)(m-1)}{3}-\frac{m^2(m-1)^2}{4} = \frac{m^2(m^2-1)}{12}. $$

Thus

$$ C=\frac{12}{m^2(m^2-1)}\left(m\sum x,s(x)-\frac{m^2(m-1)^2}{4}\right). $$

From Eq. (15),

$$ s(x)=m\left(!\left(\frac{ax+c}{m}\right)!\right)+\frac{m}{2}[x\ne x']. $$

Therefore

$$ \sum x,s(x)=m\sum x\left(!\left(\frac{ax+c}{m}\right)!\right)+\frac{m}{2}\sum_{x\ne x'}x. $$

Since $\sum_{0\le x<m}x=\frac{m(m-1)}{2}$,

$$ \sum_{x\ne x'}x=\frac{m(m-1)}{2}-x'. $$

Hence

$$ \sum x,s(x) =m\sum x\left(!\left(\frac{ax+c}{m}\right)!\right) +\frac{m^2(m-1)}{4}-\frac{m}{2}x'. $$

Multiplying by $m$ gives

$$ m\sum x,s(x) =m^2\sum x\left(!\left(\frac{ax+c}{m}\right)!\right) +\frac{m^3(m-1)}{4}-\frac{m^2}{2}x'. $$

Substitution into the numerator yields cancellation of the cubic term:

$$ m\sum x,s(x)-\left(\sum x\right)^2 =m^2\sum x\left(!\left(\frac{ax+c}{m}\right)!\right) +\frac{m^2}{2}(m- x'). $$

Thus

$$ C=\frac{12}{m^2-1}\sum x\left(!\left(\frac{ax+c}{m}\right)!\right) +\frac{6(m-x')}{m^2-1}. $$

To transform the remaining sum, write

$$ x=m\left(!\left(\frac{x}{m}\right)!\right)+\frac{m-1}{2}+\frac12\delta!\left(\frac{x}{m}\right). $$

Since $x/m$ is an integer only for $x=0$, the term involving $\delta$ contributes a correction $-\tfrac12$ when $x=0$.

Hence

$$ \sum x\left(!\left(\frac{ax+c}{m}\right)!\right) = m\sum \left(!\left(\frac{x}{m}\right)!\right)\left(!\left(\frac{ax+c}{m}\right)!\right) +\frac{m-1}{2}\sum \left(!\left(\frac{ax+c}{m}\right)!\right) -\frac12\left(!\left(\frac{c}{m}\right)!\right). $$

The middle sum vanishes by symmetry over a complete residue system, and the remaining boundary term contributes $-\frac{c}{2m}+\frac12[c>0]$ after evaluating the sawtooth at $c/m$.

Using definition (16),

$$ \sigma(a,m,c)=12\sum_{0\le x<m}\left(!\left(\frac{x}{m}\right)!\right)\left(!\left(\frac{ax+c}{m}\right)!\right), $$

$$ \sum x\left(!\left(\frac{ax+c}{m}\right)!\right) =\frac{m}{12}\sigma(a,m,c)-\frac{c}{2}+\frac12[m-x']. $$

Substituting into $C$ gives

$$ C=\frac{m\sigma(a,m,c)-3+6(m-x'-c)}{m^2-1}. $$

This completes the proof. ∎