Section 3.3.3: Theoretical Tests

Exercise 18. ▶ [M23] (U. Dieter.) Given positive integers $h$, $k$, $z$, let

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

Show that this sum can be evaluated in closed form, in terms of generalized Dedekind sums and the sawtooth function. [Hint: When $z \le k$, the quantity $\lfloor (y-z)/k \rfloor$ equals 1 for $0 \le j < z$, and it equals 0 for $z \le j < k$, so we can introduce this factor and sum over $0 \le j < k$.]

Verified: no
Solve time: 6m23s

---

Let

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

where

$$ \left(!\left(x\right)!\right)= \begin{cases} {x}-\frac12,&x\notin\mathbb Z,\[1mm] 0,&x\in\mathbb Z. \end{cases} $$

Define the generalized Dedekind sum

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

We first treat the case $0\le z\le k$, exactly as suggested by the hint.

1. Introducing the indicator

For $0\le j<k$,

$$ 1+\Bigl\lfloor \frac{j-z}{k}\Bigr\rfloor

\begin{cases} 0,&0\le j<z,\ 1,&z\le j<k. \end{cases} $$

Hence

$$ [,j<z,]

-\Bigl\lfloor \frac{j-z}{k}\Bigr\rfloor , $$

and therefore

$$ S(h,k,c,z)

-\sum_{j=0}^{k-1} \left(!\left(\frac{hj+c}{k}\right)!\right) \Bigl\lfloor \frac{j-z}{k}\Bigr\rfloor . $$

Write

$$ T:=\sum_{j=0}^{k-1} \left(!\left(\frac{hj+c}{k}\right)!\right) \Bigl\lfloor \frac{j-z}{k}\Bigr\rfloor , $$

so that $S=-T$.

Using

$$ \lfloor x\rfloor

x-\left(!\left(x\right)!\right) -\frac12+\frac12\delta(x), $$

where $\delta(x)=1$ if $x\in\mathbb Z$ and $0$ otherwise, we obtain

$$ T=T_1-T_2-\frac12A+\frac12T_3, $$

with

$$ A:=\sum_{j=0}^{k-1} \left(!\left(\frac{hj+c}{k}\right)!\right), $$

$$ T_1=\frac1k\sum_{j=0}^{k-1}(j-z) \left(!\left(\frac{hj+c}{k}\right)!\right), $$

$$ T_2= \sum_{j=0}^{k-1} \left(!\left(\frac{hj+c}{k}\right)!\right) \left(!\left(\frac{j-z}{k}\right)!\right), $$

and

$$ T_3= \sum_{j=0}^{k-1} \left(!\left(\frac{hj+c}{k}\right)!\right) \delta!\left(\frac{j-z}{k}\right). $$

Thus

$$ S=-T=-T_1+T_2+\frac12A-\frac12T_3. $$

We now evaluate each term.

2. Evaluation of $A$

Let

$$ d=\gcd(h,k),\qquad h=d h_0,\qquad k=d k_0. $$

Since $h_0$ is invertible modulo $k_0$, the values

$$ h_0r \pmod{k_0} $$

run through a complete residue system when $0\le r<k_0$.

Write $j=r+t k_0$ with

$$ 0\le r<k_0,\qquad 0\le t<d. $$

Then

$$ \frac{hj+c}{k}

\frac{h_0r+c/d}{k_0}+h_0t. $$

The sawtooth function is $1$-periodic, hence

$$ \left(!\left(\frac{hj+c}{k}\right)!\right)

\left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right). $$

Therefore

$$ A

d\sum_{r=0}^{k_0-1} \left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right). $$

Because multiplication by $h_0$ permutes the residues modulo $k_0$,

$$ \sum_{r=0}^{k_0-1} \left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right)

\sum_{r=0}^{k_0-1} \left(!\left( \frac{r+c/d}{k_0} \right)!\right)

\left(!\left(\frac{c}{d}\right)!\right). $$

Hence

$$ A=\left(!\left(\frac{c}{d}\right)!\right). $$

This is the identity used in the incomplete solution.

3. Evaluation of $T_2$

Replace $j$ by $j+z\pmod k$. Since the summation is over a complete residue system,

$$ T_2

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

Thus

$$ T_2=s(h,k;c-hz). $$

4. Evaluation of $T_3$

For $0\le z<k$, the only index satisfying $(j-z)/k\in\mathbb Z$ is $j=z$. Therefore

$$ T_3= \left(!\left(\frac{hz+c}{k}\right)!\right). $$

If $z=k$, then no such $j$ occurs in $0\le j<k$, so $T_3=0$.

5. Evaluation of $T_1$

Let

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

Then

$$ T_1=\frac{B(c)}{k}-\frac{z}{k}A. $$

We compute $B(c)$ by the same decomposition $j=r+t k_0$:

$$ B(c)

\sum_{r=0}^{k_0-1} \sum_{t=0}^{d-1} (r+t k_0) \left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right). $$

Hence

$$ B(c)

d\sum_{r=0}^{k_0-1} r\left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right) + k_0\frac{d(d-1)}2 \sum_{r=0}^{k_0-1} \left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right). $$

Using the previous evaluation of the second sum,

$$ B(c)

d\sum_{r=0}^{k_0-1} r\left(!\left( \frac{h_0r+c/d}{k_0} \right)!\right) + \frac{k(d-1)}2 \left(!\left(\frac{c}{d}\right)!\right). $$

Introduce

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

Then

$$ T_1

\frac1kL(h,k;c) -\frac{z}{k} \left(!\left(\frac{c}{d}\right)!\right). $$

Substituting into $S=-T_1+T_2+\frac12A-\frac12T_3$ gives

$$ S(h,k,c,z)

s(h,k;c-hz) -\frac1kL(h,k;c) +\left(\frac{z}{k}+\frac12\right) \left(!\left(\frac{c}{d}\right)!\right) -\frac12T_3. $$

Finally,

$$ T_3= \begin{cases} \left(!\left(\dfrac{hz+c}{k}\right)!\right), & 0\le z<k,\[2mm] 0,& z=k. \end{cases} $$

Therefore, for $0\le z\le k$,

$$ \boxed{ S(h,k,c,z)

s(h,k;c-hz) -\frac1kL(h,k;c) +\left(\frac{z}{k}+\frac12\right) \left(!\left(\frac{c}{d}\right)!\right) -\frac12 \left(!\left(\frac{hz+c}{k}\right)!\right) } $$

(with the last term omitted when $z=k$).

This expresses the partial sawtooth sum in closed form in terms of a generalized Dedekind sum and sawtooth-function quantities. For arbitrary $z$, write $z=qk+r$ with $0\le r<k$; then periodicity gives

$$ S(h,k,c,z)

q,\left(!\left(\frac{c}{d}\right)!\right) + S(h,k,c,r), $$

so the preceding formula yields the general case.