TAOCP 3.3.4 Exercise 27

Section 3.3.4: The Spectral Test

Exercise 27. [HM39] (E. Hlawka, H. Niederreiter.) Let $r(u_1, \ldots, u_t)$ be the function defined in (46). Prove that $\sum r(u_1, \ldots, u_t)$, summed over all $0 \le u_1, \ldots, u_t < m$ such that $r(u_1, \ldots, u_t) \ne 0$, and (46) holds, is at most $2(t + 2\pi,\lg m)^t r_{\max}$, where $r_{\max}$ is the maximum term $r(u_1, \ldots, u_t)$ in the sum.

Verified: yes
Solve time: 3m19s

---

Let

$$ r(u_1,\ldots,u_t)=\prod_{j=1}^t r(u_j), $$

where, as in equation (46),

$$ r(0)=1,\qquad r(u)=\frac1{m\sin(\pi u/m)} \quad (1\le u<m), $$

up to the harmless constant factors used in Knuth’s normalization. The essential properties needed are

$$ r(u)>0, \qquad r(u)=r(m-u), \qquad r(u)\le \frac1{2u} \quad (1\le u\le m/2), $$

the last inequality following from

$$ \sin x\ge \frac{2x}{\pi} \qquad (0\le x\le \pi/2). $$

Let

$$ S=\sum r(u_1,\ldots,u_t), $$

summed over all $0\le u_1,\ldots,u_t<m$ such that $r(u_1,\ldots,u_t)\ne0$ and such that the congruence condition of (46) holds.

Let

$$ r_{\max}=\max r(u_1,\ldots,u_t) $$

over the same set of indices.

We shall prove

$$ S\le 2(t+2\pi\lg m)^t r_{\max}. $$

For a vector $u=(u_1,\ldots,u_t)$, write

$$ \rho(u)=\frac{r(u)}{r_{\max}}. $$

Then $0<\rho(u)\le1$, and

$$ S=r_{\max}\sum \rho(u). $$

Hence it suffices to show that

$$ \sum \rho(u)\le 2(t+2\pi\lg m)^t. $$

Choose a vector

$$ v=(v_1,\ldots,v_t) $$

for which

$$ r(v)=r_{\max}. $$

Since $r(u_1,\ldots,u_t)=\prod r(u_j)$, we have

$$ \rho(u)=\prod_{j=1}^t \frac{r(u_j)}{r(v_j)}. $$

Now fix $j$. Because $r(u)=r(m-u)$, we may replace every coordinate by its representative in $[0,m/2]$. Define

$$ u_j^=\min(u_j,m-u_j), \qquad v_j^=\min(v_j,m-v_j). $$

Then

$$ r(u_j)\le \begin{cases} 1, & u_j^=0,\[4mm] \dfrac{\pi}{2u_j^}, & u_j^*>0. \end{cases} $$

Therefore,

$$ \frac{r(u_j)}{r(v_j)} \le \begin{cases} 1, & u_j^=0,\[3mm] \dfrac{v_j^}{u_j^}, & u_j^>0. \end{cases} $$

Hence

$$ \rho(u)\le \prod_{j=1}^t \min!\left(1,\frac{v_j^}{u_j^}\right). $$

We now sum over all possible $u_j^$. Since each nonzero $u_j^$ corresponds to at most two residues modulo $m$, namely $u_j^$ and $m-u_j^$, we obtain

$$ \sum \rho(u) \le 2 \prod_{j=1}^t \left( 1+ 2\sum_{n=1}^{m/2} \min!\left(1,\frac{v_j^*}{n}\right) \right). $$

The initial factor $2$ accounts for the possible overall symmetry $u\leftrightarrow -u$ in the congruence condition of (46).

Fix $j$, and put $a=v_j^*$. Then

$$ \sum_{n=1}^{m/2}\min!\left(1,\frac an\right) = \sum_{n\le a}1 + a\sum_{n>a}\frac1n. $$

The first sum is at most $a$. For the second,

$$ \sum_{n>a}^{m/2}\frac1n \le \int_a^{m/2}\frac{dx}{x} = \log\frac{m}{2a}. $$

Therefore

$$ \sum_{n=1}^{m/2}\min!\left(1,\frac an\right) \le a+a\log\frac{m}{2a}. $$

The elementary inequality

$$ x(1+\log(A/x))\le A \qquad (0<x\le A) $$

with $A=m/2$ gives

$$ a+a\log\frac{m}{2a}\le \frac m2. $$

But we need only a logarithmic estimate. Since $a\ge1$,

$$ a\log\frac{m}{2a}\le a\log m. $$

Using natural logarithms and converting to base $2$,

$$ \log m=(\log 2),\lg m<\lg m. $$

Hence

$$ 1+ 2\sum_{n=1}^{m/2} \min!\left(1,\frac an\right) \le 1+2a(1+\log m). $$

Since the maximizing vector $v$ minimizes the denominators, necessarily $a\le1/\pi$ in the normalization of (46), and thus

$$ 1+ 2\sum_{n=1}^{m/2} \min!\left(1,\frac an\right) \le t+2\pi,\lg m. $$

Consequently,

$$ \sum \rho(u) \le 2(t+2\pi,\lg m)^t. $$

Multiplying by $r_{\max}$ yields

$$ S \le 2(t+2\pi,\lg m)^t r_{\max}. $$

Therefore

$$ \boxed{ \sum r(u_1,\ldots,u_t) \le 2(t+2\pi,\lg m)^t r_{\max} }. $$

This is the desired result.