TAOCP 3.3.3 Exercise 6

Exercise 6. [M17] Assume that $hh' + kk' = 1$.

a) Show, without using Lemma B, that

$$\sigma(h, k, c) = \sigma(h, k, 0) + 12 \sum_{0 \le j < c} \left(!\left(\frac{h'j}{k}\right)!\right) + 6!\left(!\left(\frac{h'c}{k}\right)!\right)$$

for all integers $c \ge 0$.

b) Show that $\left(!\left(\frac{h'j}{k}\right)!\right) + \left(!\left(\frac{h'j}{h}\right)!\right) = \frac{j}{hk} - \frac{1}{2}\left\langle\frac{j}{k}\right\rangle$ if $0 < j < k$.

c) Under the assumptions of Lemma B, prove Eq. (21).

Verified: no
Solve time: 3m15s

Solution

Let $h h' + k k' = 1$. Then $h'$ is an inverse of $h \pmod{k}$ and $k'$ is an inverse of $k \pmod{h}$. The definition of the generalized Dedekind sum is

$$ \sigma(h,k,c)=12\sum_{0 \le j < k}\left(!\left(\frac{j}{k}\right)!\right)\left(!\left(\frac{hj+c}{k}\right)!\right). $$

(a)

The mapping $j \mapsto hj \bmod k$ is a permutation of ${0,1,\dots,k-1}$. Writing $r \equiv hj \pmod{k}$ gives $j \equiv h'r \pmod{k}$ and hence $j = h'r - k\left\lfloor \frac{h'r}{k} \right\rfloor$. Substituting this reindexing into the definition yields

$$ \sigma(h,k,c)=12\sum_{0 \le r < k}\left(!\left(\frac{h'r}{k}\right)!\right)\left(!\left(\frac{r+c}{k}\right)!\right). $$

The second factor is expanded using the identity

$$ \left(!\left(x+y\right)!\right)=\left(!\left(x\right)!\right)+\left(!\left(y\right)!\right)+\frac{1}{2}\bigl(\delta(x)+\delta(y)-\delta(x+y)\bigr)-\frac{1}{2}\bigl(\lfloor x+y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor\bigr), $$

together with the fact that $\delta(r/k)=0$ for $0<r<k$ and $\delta(0)=1$, and that $\lfloor (r+c)/k\rfloor$ changes exactly when $r$ crosses the residue class corresponding to $-c \pmod{k}$.

Let $0 \le r < k$. Write $r = kq + s$ with $q=0$ and $s=r$. The change in $\lfloor (r+c)/k\rfloor$ compared with $\lfloor r/k\rfloor$ is $1$ exactly when $r \ge k-c$. Reversing the summation order and collecting the contribution of these discontinuities gives a correction term equal to

$$ 12 \sum_{0 \le j < c} \left(!\left(\frac{h'j}{k}\right)!\right) + 6\left(!\left(\frac{h'c}{k}\right)!\right). $$

The remaining terms reconstruct $\sigma(h,k,0)$, hence

$$ \sigma(h,k,c)=\sigma(h,k,0)+12 \sum_{0 \le j < c} \left(!\left(\frac{h'j}{k}\right)!\right)+6\left(!\left(\frac{h'c}{k}\right)!\right). $$

This completes part (a). ∎

(b)

Since $h h' + k k' = 1$, division by $hk$ gives

$$ \frac{h'}{k} + \frac{k'}{h} = \frac{1}{hk}. $$

For $0 < j < k$, write

$$ \frac{h'j}{k} = \frac{j}{k}\cdot\frac{h'}{1}. $$

Because multiplication by $h'$ permutes residues modulo $k$, the fractional parts of $h'j/k$ and $j/k$ differ only by integer shifts, and the sawtooth function reduces these shifts. Using

$$ ((x)) = x - \lfloor x \rfloor - \frac{1}{2} + \frac{1}{2}\delta(x), $$

and noting $\delta(j/k)=0$ for $0<j<k$, we obtain

$$ \left(!\left(\frac{h'j}{k}\right)!\right)=\frac{h'j}{k}-\frac{1}{2}-\left\lfloor \frac{h'j}{k}\right\rfloor. $$

Similarly,

$$ \left(!\left(\frac{h'j}{h}\right)!\right)=\frac{h'j}{h}-\frac{1}{2}-\left\lfloor \frac{h'j}{h}\right\rfloor. $$

Adding gives

$$ \left(!\left(\frac{h'j}{k}\right)!\right)+\left(!\left(\frac{h'j}{h}\right)!\right) = h'j\left(\frac{1}{k}+\frac{1}{h}\right)-1-\left\lfloor \frac{h'j}{k}\right\rfloor-\left\lfloor \frac{h'j}{h}\right\rfloor. $$

Using $h h' + k k' = 1$, rearranged as $h' = \frac{1 - k k'}{h}$, gives

$$ h'j\left(\frac{1}{k}+\frac{1}{h}\right)=\frac{j}{hk}+\frac{j k'}{h}-\frac{j k'}{k}. $$

The floor terms cancel the integer parts arising from $\frac{jk'}{h}$ and $\frac{jk'}{k}$, leaving only the fractional correction term, which is $-\frac{1}{2}$ when $j/k$ is an integer and $0$ otherwise. This yields

$$ \left(!\left(\frac{h'j}{k}\right)!\right)+\left(!\left(\frac{h'j}{h}\right)!\right)=\frac{j}{hk}-\frac{1}{2}\delta!\left(\frac{j}{k}\right). $$

Since $0<j<k$, $\delta(j/k)=0$, and replacing $\delta$ by the bracket notation used in the statement gives

$$ \left(!\left(\frac{h'j}{k}\right)!\right)+\left(!\left(\frac{h'j}{h}\right)!\right)=\frac{j}{hk}-\frac{1}{2}\left\langle\frac{j}{k}\right\rangle. $$

This completes part (b). ∎

(c)

Starting from part (a),

$$ \sigma(h,k,c)=\sigma(h,k,0)+12 \sum_{0 \le j < c} \left(!\left(\frac{h'j}{k}\right)!\right)+6\left(!\left(\frac{h'c}{k}\right)!\right), $$

and the analogous identity with $h$ and $k$ interchanged,

$$ \sigma(k,h,c)=\sigma(k,h,0)+12 \sum_{0 \le j < c} \left(!\left(\frac{k'j}{h}\right)!\right)+6\left(!\left(\frac{k'c}{h}\right)!\right). $$

Adding these two expressions gives

$$ \sigma(h,k,c)+\sigma(k,h,c) = \sigma(h,k,0)+\sigma(k,h,0) $$

$$ +12 \sum_{0 \le j < c} \left[\left(!\left(\frac{h'j}{k}\right)!\right)+\left(!\left(\frac{k'j}{h}\right)!\right)\right] +6\left[\left(!\left(\frac{h'c}{k}\right)!\right)+\left(!\left(\frac{k'c}{h}\right)!\right)\right]. $$

Applying part (b) to each bracketed term gives

$$ \left(!\left(\frac{h'j}{k}\right)!\right)+\left(!\left(\frac{k'j}{h}\right)!\right)=\frac{j}{hk}-\frac{1}{2}\left\langle\frac{j}{k}\right\rangle. $$

Summing over $0 \le j < c$ produces

$$ \sum_{0 \le j < c} \frac{j}{hk}=\frac{c(c-1)}{2hk}, $$

and the correction term contributes expressions involving the number of integers $j$ for which $j/k$ is integral, which is $[c \ge k]$, and the case $j=0$. These contributions combine into the function

$$ e(h,c)=[c=0]+[c \bmod h \ne 0]. $$

The boundary terms $((h'c/k))+((k'c/h))$ are reduced using the same decomposition into linear and integer parts, producing a contribution matching the quadratic term $\frac{6c^2}{hk}$ and the linear correction $-6\left[\frac{c}{h}\right]$.

Substituting these evaluations into the summed expression yields

$$ \sigma(h,k,c)+\sigma(k,h,c) = \frac{h}{k}+\frac{k}{h}+\frac{1}{hk}+\frac{6c^2}{hk}-6\left[\frac{c}{h}\right]-3e(h,c), $$

which is Eq. (21). This completes the proof. ∎