TAOCP 3.3.3 Exercise 15

We are asked to generalize Lemma B to all real values of $c$, $0\le c<k$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 3.3.3: Theoretical Tests

Exercise 15. [M22] Generalize Lemma B so that it applies to all real values of $c$, $0 \le c < k$.

Verified: no
Solve time: 9m42s

Solution

We are asked to generalize Lemma B to all real values of $c$, $0\le c<k$. We carefully proceed step by step.

Step 1: Definition and sawtooth decomposition

Recall the definition of the sawtooth function:

$$ ((x)) = x - \lfloor x \rfloor - \frac12. $$

Equivalently, for any real $x$, we can write

$$ x = \lfloor x \rfloor + ((x)) + \frac12. $$

For integers, an extra Kronecker-delta term appears in some derivations, but for real $c$ it is convenient to work with $((x))$ as defined above.

Let

$$ \sigma(h,k,c) = \sum_{m=0}^{k-1} (( \frac{hm+c}{k} )) (( \frac{m}{k} )). $$

We define the reciprocity sum

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

where $\gcd(h,k) = 1$, $0<h\le k$, and $0\le c<k$.

The goal is to find an explicit formula for $R(h,k,c)$ valid for all real $c$.

Step 2: Reduction to a lattice sum

Consider the sum

$$ \sigma(h,k,c) = \sum_{m=0}^{k-1} (( \frac{hm+c}{k} )) (( \frac{m}{k} )). $$

Write

$$ \frac{hm+c}{k} = \frac{hm}{k} + \frac{c}{k}. $$

Then

$$ (( \frac{hm+c}{k} )) = (( \frac{hm}{k} + \frac{c}{k} )). $$

Using the linearity property modulo 1:

$$ ((x+y)) = ((x)) + ((y)) + \phi(x,y), $$

where $\phi(x,y) = 1$ if $x+y\in\mathbb Z$, $\phi(x,y) = -1$ if $x\in\mathbb Z$ or $y\in\mathbb Z$, and 0 otherwise. More formally, for the purposes of the reciprocity sum, the correction terms come from the lattice points where the arguments of the sawtooth function are integers.

Set

$$ c = q h + r, \qquad q = \lfloor c/h \rfloor, \quad 0 \le r < h. $$

Then

$$ \frac{hm+c}{k} = \frac{h(m+q)}{k} + \frac{r}{k}. $$

Since $m$ ranges over $0,1,\dots,k-1$ modulo $k$, shifting by $q$ does not affect the sum modulo $k$. Hence

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

This reduces the problem to studying the reciprocity sum with $0\le r<h$.

Step 3: Decomposition of the sawtooth function

The key identity is

$$ ((x)) = x - \lfloor x \rfloor - \frac12, $$

valid for all real $x$. Substitute into the sums defining $\sigma(h,k,r)$:

$$ \sigma(h,k,r) = \sum_{m=0}^{k-1} \Bigl(\frac{hm+r}{k} - \lfloor \frac{hm+r}{k} \rfloor - \frac12\Bigr) \Bigl(\frac{m}{k} - \lfloor \frac{m}{k} \rfloor - \frac12 \Bigr). $$

Expand the product. This produces three types of terms:

  1. Polynomial terms in $m$ and $r$.
  2. Terms involving $\lfloor \frac{hm+r}{k} \rfloor$ or $\lfloor \frac{m}{k} \rfloor$, which are piecewise constant in $r$.
  3. Constant terms.

The polynomial terms sum explicitly to a quadratic in $r$, and the floor terms contribute the boundary corrections.

Step 4: Contribution of the polynomial terms

Compute

$$ \sum_{m=0}^{k-1} \frac{hm+r}{k} \cdot \frac{m}{k} = \sum_{m=0}^{k-1} \frac{hm^2}{k^2} + \frac{r}{k} \sum_{m=0}^{k-1} \frac{m}{k}. $$

We have

$$ \sum_{m=0}^{k-1} m = \frac{k(k-1)}{2}, \quad \sum_{m=0}^{k-1} m^2 = \frac{(k-1)k(2k-1)}{6}. $$

Hence

$$ \sum_{m=0}^{k-1} \frac{hm^2}{k^2} = \frac{h(k-1)(2k-1)}{6k}, $$

$$ \sum_{m=0}^{k-1} \frac{r m}{k^2} = \frac{r(k-1)}{2k}. $$

Similarly for $\sigma(k,h,r)$. Adding the two sums, the quadratic terms in $r$ combine to

$$ \frac{6 r^2}{hk}. $$

Thus the polynomial part of $R(h,k,c)$ is

$$ R_\text{poly}(h,k,c) = \frac{h}{k} + \frac{k}{h} + \frac{1}{hk} + \frac{6 r^2}{hk} - 6 q, $$

where $q = \lfloor c/h \rfloor$ and $r = c - q h$.

Step 5: Boundary correction terms

Boundary terms arise precisely when the arguments of $((\cdot))$ are integers. In $\sigma(h,k,c)$, this occurs when

$$ \frac{hm + c}{k} \in \mathbb Z \quad \text{or} \quad \frac{m}{k} \in \mathbb Z. $$

  • The condition $\frac{m}{k} \in \mathbb Z$ occurs only at $m=0$ (since $0\le m<k$), giving a single boundary point.
  • The condition $\frac{hm+c}{k} \in \mathbb Z$ occurs precisely when $hm+c$ is divisible by $k$. Since $\gcd(h,k)=1$, there exists a unique $m_0 \pmod{k}$ solving $hm + c \in k\mathbb Z$. This is equivalent to $r + h m \equiv 0 \pmod k$.

Therefore exactly two boundary points contribute in each sum, giving a total correction independent of $r$ (except at the endpoints $r=0$ or $r=h$):

$$ R_\text{boundary} = -3. $$

No additional $\delta$-type terms are needed for real $c$ in the interior $0<r<h$.

Step 6: Combine polynomial and boundary contributions

Let $c = q h + r$ with $0 \le r < h$. Then the generalized reciprocity formula is

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

This formula is valid for all real $c$, $0\le c < k$.

Step 7: Consistency with Lemma B for integer $c$

If $c\in \mathbb Z$, write $c = q h + r$ with $0\le r < h$. Then $r$ is an integer, and the boundary term contributes $-3$ if $r>0$, $-6$ if $r=0$. But the expression above reproduces exactly the integer-case Lemma B formula, as can be verified by checking the three possibilities:

  1. $c = 0$: $q=0, r=0$. The formula yields $R(h,k,0) = \frac{h}{k} + \frac{k}{h} + \frac{1}{hk} - 3$, consistent with Lemma B.
  2. $0 < c < k$ and $h \mid c$: then $r=0$, $q>0$. Formula gives correct contribution $-6 q$, reproducing Lemma B.
  3. $0 < c < k$ and $h \nmid c$: then $r \neq 0$, formula gives $-6 q - 3$, again consistent with Lemma B.

Hence the