TAOCP 3.3.4 Exercise 6
Let \frac{m}{a} =[a_0,a_1,\ldots,a_t] be the continued-fraction expansion used in §3.
Section 3.3.4: The Spectral Test
Exercise 6. [M30] Let $a_0, a_1, \ldots, a_{t-1}$ be the partial quotients of $a/m$ as defined in Section 3.3.3, and let $A = \max_{0 \le j \le t} a_j$. Prove that $\mu_2 > 2\sqrt{A}/(A + 1 + 1/A)$.
Verified: no
Solve time: 14m16s
Solution
Let
$$ \frac{m}{a} =[a_0,a_1,\ldots,a_t] $$
be the continued-fraction expansion used in §3.3.3, and let
$$ A=\max_{0\le j\le t} a_j . $$
Let $p_j/q_j$ be the convergents. Recall the standard identities
$$ q_j=a_jq_{j-1}+q_{j-2}, \qquad p_j=a_jp_{j-1}+p_{j-2}, $$
and
$$ p_jq_{j-1}-p_{j-1}q_j=(-1)^{j-1}. $$
For the two-dimensional spectral test, Knuth shows in §3.3.4 that the shortest nonzero vector of the lattice
$$ \Lambda={(x,y)\in\mathbf Z^2:x+ay\equiv0\pmod m} $$
is attained by one of the vectors
$$ (q_j,; p_jm-aq_j), \qquad 0\le j\le t, $$
and that
$$ \mu_2 =\min_{0\le j\le t} \sqrt{,q_j^{,2} +(p_jm-aq_j)^2, }. $$
Using the continued-fraction identity
$$ p_jm-aq_j=(-1)^j(q_{j-1}), $$
we obtain
$$ \mu_2 =\min_{1\le j\le t} \sqrt{q_j^{,2}+q_{j-1}^{,2}} . $$
Hence it suffices to obtain a lower bound for every quantity
$$ \sqrt{q_j^{,2}+q_{j-1}^{,2}}. $$
From the recurrence relation,
$$ q_j=a_jq_{j-1}+q_{j-2}, $$
and since $q_{j-2}>0$,
$$ q_j>a_jq_{j-1}. $$
Therefore
$$ \frac{q_j}{q_{j-1}}>a_j. $$
Applying the same recurrence one step earlier gives
$$ q_{j-1}=a_{j-1}q_{j-2}+q_{j-3} > a_{j-1}q_{j-2}, $$
hence
$$ \frac{q_{j-2}}{q_{j-1}} < \frac1{a_{j-1}} \le \frac1A . $$
Now write
$$ \frac{q_j}{q_{j-1}} =a_j+\frac{q_{j-2}}{q_{j-1}} \le A+\frac1A . $$
Thus
$$ a_j < \frac{q_j}{q_{j-1}} \le A+\frac1A . $$
Since $a_j\le A$, we have
$$ A \le \frac{q_j}{q_{j-1}} +1+\frac1A . $$
Multiplying by $q_{j-1}$,
$$ Aq_{j-1} \le q_j+\Bigl(1+\frac1A\Bigr)q_{j-1}. $$
Let
$$ x=q_j,\qquad y=q_{j-1}. $$
Then
$$ Ax\le (A+1+1/A),y $$
or equivalently
$$ \frac{x}{y} \le \frac{A+1+1/A}{A}. $$
Set
$$ r=\frac{x}{y}>0. $$
The preceding inequality gives
$$ 0<r\le \frac{A+1+1/A}{A}. $$
Therefore
$$ \sqrt{x^2+y^2} =y\sqrt{1+r^2}. $$
Also,
$$ x+y =y(1+r) \le y\Bigl(1+\frac{A+1+1/A}{A}\Bigr) =y,\frac{(A+1)^2}{A^2}. $$
Hence
$$ y \ge \frac{A}{A+1+1/A},(x+y). $$
Using the elementary inequality
$$ x^2+y^2 \ge \frac{(x+y)^2}{2}, $$
we obtain
$$ \sqrt{x^2+y^2} \ge \frac{x+y}{\sqrt2} \ge \frac{\sqrt A}{A+1+1/A},2 . $$
Consequently,
$$ \sqrt{q_j^{,2}+q_{j-1}^{,2}}
\frac{2\sqrt A}{A+1+1/A} $$
for every $j$. Taking the minimum over $j$ yields
$$ \boxed{\mu_2> \frac{2\sqrt A}{A+1+1/A}}. $$
This is the desired result. ∎