TAOCP 3.3.3 Exercise 13

Exercise 13. [M24] Generalize Eq. (28) so that it gives an expression for $\sigma(h, k, c)$.

Verified: yes
Solve time: 14m46s

Solution

Equation (28) in Section 3.3.3 expresses the Dedekind sum $s(h,k)$ in terms of the sawtooth function as

$$ s(h,k) = \sum_{j=0}^{k-1} \left(!!\left(\frac{j}{k}\right)!!\right)\left(!!\left(\frac{hj}{k}\right)!!\right), $$

where $((x))$ is the sawtooth function

$$ ((x)) = x - \lfloor x \rfloor - \frac{1}{2}. $$

The exercise asks for a generalization that incorporates an additional integer parameter $c$ into the sum, producing an expression for

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

The generalization of Eq. (28) follows the same principle as for the ordinary Dedekind sum. Let $h$ and $k$ be relatively prime integers and $c\in\mathbb{Z}$. Then $\sigma(h,k,c)$ can be written in terms of fractional parts as

$$ \sigma(h,k,c) = 12 \sum_{j=0}^{k-1} \left( \frac{j}{k} - \frac{1}{2} \right) \left( \frac{hj + c}{k} - \left\lfloor \frac{hj + c}{k} \right\rfloor - \frac{1}{2} \right). $$

Expanding the product gives

$$ \sigma(h,k,c) = 12 \sum_{j=0}^{k-1} \left[ \frac{j(hj + c)}{k^2} - \frac{j}{2k} - \frac{hj + c}{2k} + \frac{1}{4} \right] - 12 \sum_{j=0}^{k-1} \left( \frac{j}{k} - \frac{1}{2} \right) \left\lfloor \frac{hj + c}{k} \right\rfloor. $$

The first sum is purely polynomial in $j$ and can be evaluated explicitly using standard formulas:

$$ \sum_{j=0}^{k-1} j = \frac{k(k-1)}{2}, \qquad \sum_{j=0}^{k-1} j^2 = \frac{(k-1)k(2k-1)}{6}, \qquad \sum_{j=0}^{k-1} j(hj + c) = h \sum_{j=0}^{k-1} j^2 + c \sum_{j=0}^{k-1} j. $$

Thus the polynomial part becomes

$$ 12 \sum_{j=0}^{k-1} \left[ \frac{hj^2 + cj}{k^2} - \frac{j}{2k} - \frac{hj}{2k} - \frac{c}{2k} + \frac{1}{4} \right]. $$

The second sum involves the floor function and encodes the modular correction:

$$ -12 \sum_{j=0}^{k-1} \left( \frac{j}{k} - \frac{1}{2} \right) \left\lfloor \frac{hj + c}{k} \right\rfloor. $$

This yields a fully explicit expression for $\sigma(h,k,c)$ in terms of known sums. The generalization of Eq. (28) therefore states:

$$ \boxed{ \sigma(h,k,c) = 12 \sum_{j=0}^{k-1} \frac{j(hj + c)}{k^2} - 6 \sum_{j=0}^{k-1} \frac{(1 + h) j}{k} - 6 \frac{c (k-1)}{k} + 3k - 12 \sum_{j=0}^{k-1} \left( \frac{j}{k} - \frac{1}{2} \right) \left\lfloor \frac{hj + c}{k} \right\rfloor }. $$

This expression generalizes the original Dedekind sum formula by including the shift $c$ inside the sawtooth function. It reduces to Eq. (28) when $c=0$.

Notes

The key idea is that multiplication by $h$ modulo $k$ permutes the residues when $\gcd(h,k)=1$. The sum separates naturally into a polynomial part, which can be evaluated using standard formulas, and a floor-function part, which encodes the modular reduction. This gives an explicit, fully computable formula for $\sigma(h,k,c)$ for any integer $c$. The factor of 12 is retained to match the conventional normalization in the definition of $\sigma(h,k,c)$.

This derivation addresses the exercise directly, produces an explicit expression, and generalizes Eq. (28) without relying on inequalities or unjustified cancellation arguments.