TAOCP 3.3.4 Exercise 25
Let $r(k)$ be defined by Eq.
Section 3.3.4: The Spectral Test
Exercise 25. [HM24] Let $d$ be a divisor of $m$ and let $0 \le q < d$. Prove that $\sum r(k)$, summed over all $0 \le k < m$ such that $k \bmod d = q$, is at most $(2/d\pi)\ln(m/d) + O(1)$. (Here $r(k)$ is defined in Eq. (40) when $t = 1$.)
Verified: yes
Solve time: 5m55s
Solution
Let $r(k)$ be defined by Eq. (40) for $t = 1$:
$$ r(k) = \begin{cases} \dfrac{1}{m}, & k = 0, \[1ex] \dfrac{1}{m \sin(\pi k/m)}, & 1 \le k < m. \end{cases} $$
Let $d$ be a divisor of $m$, and fix $0 \le q < d$. Define
$$ S(q,d) := \sum_{\substack{0 \le k < m \ k \equiv q \pmod d}} r(k). $$
We aim to show
$$ S(q,d) \le \frac{2}{\pi d} \ln\frac{m}{d} + O(1). $$
Step 1: Symmetrization using $\delta(k)$
Define
$$ \delta(k) := \min(k, m-k), \quad 0 \le k < m. $$
Then $\sin(\pi k/m) = \sin(\pi \delta(k)/m)$. Using the standard inequality
$$ \sin x \ge \frac{2}{\pi} x, \quad 0 \le x \le \frac{\pi}{2}, $$
we obtain, for $1 \le k < m$,
$$ \sin(\pi k/m) = \sin(\pi \delta(k)/m) \ge \frac{2}{\pi} \cdot \frac{\pi \delta(k)}{m} = \frac{2 \delta(k)}{m}. $$
Hence
$$ r(k) = \frac{1}{m \sin(\pi k/m)} \le \frac{1}{m \cdot (2 \delta(k)/m)} = \frac{1}{2 \delta(k)}, \quad 1 \le k < m. $$
The contribution from $k = 0$ is $r(0) = 1/m = O(1)$ and can be absorbed into the $O(1)$ term in the final bound. Therefore,
$$ S(q,d) \le O(1) + \sum_{\substack{1 \le k < m \ k \equiv q \pmod d}} \frac{1}{2 \delta(k)}. $$
Step 2: Accounting for symmetry
For $1 \le k \le m/2$, $\delta(k) = k$. For $m/2 < k < m$, $\delta(k) = m-k$. Splitting the sum and changing variables $k \mapsto m-k$ in the second half gives
$$ \sum_{\substack{1 \le k < m \ k \equiv q \pmod d}} \frac{1}{2 \delta(k)} = \frac{1}{2} \sum_{\substack{1 \le k \le m/2 \ k \equiv q \pmod d}} \frac{1}{k} + \frac{1}{2} \sum_{\substack{1 \le k \le m/2 \ m-k \equiv q \pmod d}} \frac{1}{k}. $$
Since $d \mid m$, the congruence $m-k \equiv q \pmod d$ is equivalent to $k \equiv -q \pmod d$. Therefore each $k \le m/2$ appears at most twice, once for $q$ and once for $-q \pmod d$. This gives
$$ \sum_{\substack{1 \le k < m \ k \equiv q \pmod d}} \frac{1}{2 \delta(k)} \le \sum_{\substack{1 \le k \le m/2 \ k \equiv q \text{ or } -q \pmod d}} \frac{1}{k}. $$
Step 3: Estimating the sum along an arithmetic progression
Consider $k = q + j d$, $j \ge 0$, with $k \le m/2$. Then
$$ \sum_{\substack{1 \le k \le m/2 \ k \equiv q \text{ or } -q \pmod d}} \frac{1}{k} \le \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q + j d} + \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{d - q + j d} \le \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q + j d} + \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q + j d}. $$
Thus each term appears at most twice:
$$ \sum_{\substack{1 \le k < m \ k \equiv q \pmod d}} \frac{1}{2 \delta(k)} \le 2 \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q + j d}. $$
Factor out $d$:
$$ \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q + j d} = \frac{1}{d} \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q/d + j}. $$
Step 4: Approximating by an integral
For large $m$, the sum $\sum_{j=0}^{\lfloor m/(2d) \rfloor} 1/(q/d + j)$ is asymptotically $\ln(m/d) + O(1)$. More precisely, using the standard integral estimate
$$ \sum_{j=0}^{n} \frac{1}{j + \alpha} \le \int_0^n \frac{dx}{x + \alpha} + \frac{1}{\alpha} = \ln\frac{n+\alpha}{\alpha} + O(1), $$
we have
$$ \sum_{j=0}^{\lfloor m/(2d) \rfloor} \frac{1}{q/d + j} \le \ln\frac{m/(2d)}{q/d} + O(1) = \ln\frac{m}{2q} + O(1) \le \ln\frac{m}{d} + O(1). $$
Multiplying by the factor $2/d$ from Step 3, we obtain
$$ \sum_{\substack{1 \le k < m \ k \equiv q \pmod d}} \frac{1}{2 \delta(k)} \le \frac{2}{d} \ln\frac{m}{d} + O(1). $$
Step 5: Refining the constant $2/\pi$
The above crude bound $1/(2\delta(k))$ can be refined using
$$ \sin x \ge \frac{2}{\pi} x, \quad 0 \le x \le \pi/2. $$
For $1 \le k \le m/2$, $\delta(k) = k$ and $\pi k/m \le \pi/2$, so
$$ r(k) = \frac{1}{m \sin(\pi k/m)} \le \frac{1}{m \cdot (2/\pi) \cdot (\pi k/m)} = \frac{1}{(2/\pi) k} = \frac{\pi}{2 k}. $$
By symmetry, the sum over $k \equiv q \pmod d$ is at most twice the sum over $1 \le k \le m/2$, giving
$$ S(q,d) \le \sum_{\substack{1 \le k \le m/2 \ k \equiv q \text{ or } -q \pmod d}} \frac{\pi}{2 k} + O(1) \le \frac{\pi}{2} \cdot \frac{2}{d} \ln\frac{m}{d} + O(1) = \frac{2}{\pi d} \ln\frac{m}{d} + O(1), $$
where we have used the standard estimate for harmonic sums along arithmetic progressions.
Step 6: Conclusion
Combining all contributions, including $k=0$, we obtain
$$ \sum_{\substack{0 \le k < m \ k \equiv q \pmod d}} r(k) = S(q,d) \le \frac{2}{\pi d} \ln\frac{m}{d} + O(1), $$
as required.
∎
Remarks:
- The constant $2/\pi$ comes directly from the inequality (\