TAOCP 3.3.4 Exercise 11
Let m=2^e, \qquad R=\sqrt{\frac43}\,m .
Section 3.3.4: The Spectral Test
Exercise 11. ▶ [**] $[HM30]$ (Alan G. Waterman, 1974.) Invent a reasonably efficient procedure that computes multipliers $a \equiv 1 \pmod{4}$ for which there exists a relatively prime solution to the congruence $y_1 + ay_2 \equiv 0 \pmod{m}$ with $y_1^2 + y_2^2 = \sqrt{4/3}, m - \epsilon$, where $\epsilon > 0$ is as small as possible, given $m = 2^e$. (By exercise 10, this choice of $a$ will guarantee that $u_1^2 + u_2^2)(y_1^2 + y_2^2) > \sqrt{4/3}, m$, and there is a chance that $u_1^2$ will be near its optimum value $\sqrt{4/3}, m$. In practice we will compute several such multipliers having small $\epsilon$, choosing the one with best spectral values $\nu_2, \nu_3, \ldots$.)
Verified: yes
Solve time: 4m19s
Let
$$ m=2^e, \qquad R=\sqrt{\frac43},m . $$
We seek integers $y_1,y_2$ satisfying
$$ y_1+a y_2\equiv0\pmod m, \qquad \gcd(y_1,y_2)=1, $$
with
$$ y_1^2+y_2^2=R-\epsilon, \qquad \epsilon>0 $$
as small as possible, and with
$$ a\equiv1\pmod4. $$
The natural strategy is to search for primitive lattice points lying just inside the circle
$$ x^2+y^2=R, $$
then derive the multiplier $a$ from such a point.
Since $m=2^e$, an integer is invertible modulo $m$ exactly when it is odd. If $(y_1,y_2)=1$, the two coordinates cannot both be even, hence at least one coordinate is odd. Interchanging the coordinates if necessary, we may therefore assume that $y_2$ is odd.
Then $y_2^{-1}\pmod m$ exists, and the congruence
$$ y_1+a y_2\equiv0\pmod m $$
determines $a$ uniquely:
$$ a\equiv -y_1y_2^{-1}\pmod m. $$
Thus the problem reduces to finding primitive pairs $(y_1,y_2)$ with $y_2$ odd and
$$ y_1^2+y_2^2<R $$
as close as possible to $R$.
We now translate the condition $a\equiv1\pmod4$. Since $y_2$ is odd,
$$ y_2^{-1}\equiv y_2\pmod4, $$
because every odd residue is its own inverse modulo $4$. Hence
$$ a\equiv -y_1y_2^{-1} \equiv -y_1y_2 \pmod4. $$
Since $y_2^2\equiv1\pmod4$,
$$ a\equiv1\pmod4 \iff -y_1y_2\equiv1\pmod4 \iff y_1\equiv -y_2\pmod4. $$
Therefore admissible pairs are precisely the primitive pairs satisfying
$$ y_2 \text{ odd}, \qquad y_1\equiv -y_2\pmod4. $$
We now describe a complete search procedure.
For each odd integer $y_2$ with
$$ 1\le y_2\le \lfloor \sqrt R\rfloor, $$
define
$$ B(y_2)=\left\lfloor \sqrt{R-y_2^2}\right\rfloor . $$
Every admissible $y_1$ must satisfy
$$ y_1^2\le R-y_2^2, $$
hence
$$ y_1\le B(y_2). $$
Among all integers congruent to $-y_2\pmod4$, there is a unique largest one not exceeding $B(y_2)$. It is
$$ y_1 = B(y_2)-r, $$
where $r\in{0,1,2,3}$ is chosen so that
$$ B(y_2)-r\equiv -y_2\pmod4. $$
Thus decrementing by at most three units always produces the largest admissible residue representative.
For this fixed $y_2$, any other admissible integer has the form
$$ y_1-4k, \qquad k\ge1, $$
and therefore satisfies
$$ (y_1-4k)^2+y_2^2 < y_1^2+y_2^2. $$
Hence the chosen $y_1$ uniquely maximizes
$$ y_1^2+y_2^2 $$
among all admissible integers for that $y_2$. Consequently it minimizes
$$ \epsilon = R-(y_1^2+y_2^2) $$
for that $y_2$.
We then test whether
$$ \gcd(y_1,y_2)=1. $$
If not, the pair is discarded. Otherwise define
$$ S=y_1^2+y_2^2, \qquad \epsilon=R-S, $$
and retain the pairs having smallest positive $\epsilon$.
Finally compute
$$ a\equiv -y_1y_2^{-1}\pmod{2^e}. $$
This yields the desired multiplier.
We verify correctness.
First, because $y_2$ is odd, $y_2^{-1}\pmod{2^e}$ exists, and therefore
$$ y_1+a y_2 \equiv y_1-y_1y_2^{-1}y_2 \equiv0 \pmod{2^e}. $$
Second, the residue condition imposed on $y_1$ guarantees
$$ a\equiv1\pmod4. $$
Indeed,
$$ a \equiv -y_1y_2 \equiv -(-y_2)y_2 \equiv y_2^2 \equiv1 \pmod4. $$
Third, for every admissible odd $y_2$, the algorithm finds the unique admissible $y_1$ giving maximal value of $y_1^2+y_2^2$. Therefore scanning all admissible $y_2$ necessarily finds the global maximum of
$$ y_1^2+y_2^2<R $$
subject to the congruence and coprimality conditions. Equivalently, it finds the smallest possible positive $\epsilon$.
The procedure is reasonably efficient. Since
$$ R=\sqrt{\frac43},m, $$
we have
$$ \sqrt R = O(\sqrt m). $$
The algorithm examines only odd integers $y_2$ up to $\sqrt R$, hence only $O(\sqrt m)$ candidates are considered. Each iteration requires:
- one integer square root,
- a few congruence operations modulo $4$,
- one gcd computation,
- optionally one modular inverse modulo $2^e$.
All of these require polynomial time in $e$. Therefore the total search requires $O(\sqrt m)$ arithmetic iterations.
Thus the procedure computes multipliers $a\equiv1\pmod4$ arising from primitive lattice points immediately inside the circle
$$ x^2+y^2=\sqrt{\frac43},m, $$
exactly as required for the application in Exercise 10.