TAOCP 3.3.4 Exercise 4

Let $L = \{(y_1,y_2)\in \mathbb{Z}^2 \mid y_1 + a y_2 \equiv 0 \pmod m\}.$ Define the column vectors $v_1 = (u_{11},u_{12}), \quad v_2 = (u_{21},u_{22}), \quad U = (v_1\ v_2).$ The hypotheses are $u_{...

taocpmathematicsalgorithmsvolume-1math-medium

Section 3.3.4: The Spectral Test

Exercise 4. ▶ [M23] Let $u_{11}, u_{12}, u_{21}, u_{22}$ be elements of a $2 \times 2$ integer matrix such that $u_{11} + u_{12} = u_{21} + u_{22} \equiv 0 \pmod{m}$ and $u_{11}u_{22} - u_{12}u_{21} = m$.

a) Prove that all integer solutions $(y_1, y_2)$ to the congruence $y_1 + ay_2 \equiv 0 \pmod{m}$ have the form $(y_1, y_2) = (x_1 u_{11} + x_2 u_{21}, x_1 u_{12} + x_2 u_{22})$ for integer $x_1, x_2$.

b) If, in addition, $2|u_{11}u_{21} + u_{12}u_{22}| \le u_{11}^2 + u_{12}^2 \le u_{21}^2 + u_{22}^2$, prove that $(u_{11}, u_{12})$ minimizes $y_1^2 + y_2^2$ over all nonzero solutions to the congruence.

Verified: yes
Solve time: 1m22s

Solution

Let

$L = {(y_1,y_2)\in \mathbb{Z}^2 \mid y_1 + a y_2 \equiv 0 \pmod m}.$

Define the column vectors

$v_1 = (u_{11},u_{12}), \quad v_2 = (u_{21},u_{22}), \quad U = (v_1\ v_2).$

The hypotheses are

$u_{11}+u_{12} \equiv 0 \pmod m, \quad u_{21}+u_{22} \equiv 0 \pmod m,$

and

$u_{11}u_{22}-u_{12}u_{21}=m.$

(a)

Every vector of the form $x_1 v_1 + x_2 v_2$ with $x_1,x_2\in\mathbb{Z}$ satisfies

$y_1 = x_1 u_{11}+x_2 u_{21}, \quad y_2 = x_1 u_{12}+x_2 u_{22}.$

Then

$y_1 + a y_2 = x_1(u_{11}+a u_{12}) + x_2(u_{21}+a u_{22}).$

Since $u_{11}+a u_{12} \equiv 0 \pmod m$ and $u_{21}+a u_{22}\equiv 0 \pmod m$ in the construction underlying (19), each term is divisible by $m$, hence

$y_1 + a y_2 \equiv 0 \pmod m,$

so $U\mathbb{Z}^2 \subseteq L$.

The determinant condition

$\det U = u_{11}u_{22}-u_{12}u_{21} = m$

implies that the subgroup $U\mathbb{Z}^2$ has index $m$ in $\mathbb{Z}^2$.

The congruence $y_1 + a y_2 \equiv 0 \pmod m$ defines a subgroup $L$ of $\mathbb{Z}^2$ of index $m$, since the mapping $(y_1,y_2)\mapsto y_1 + a y_2 \bmod m$ is a surjective homomorphism onto $\mathbb{Z}/m\mathbb{Z}$.

Both $U\mathbb{Z}^2$ and $L$ are subgroups of $\mathbb{Z}^2$ with the same finite index and one is contained in the other, hence

$U\mathbb{Z}^2 = L.$

Thus every solution has the form

$(y_1,y_2) = (x_1 u_{11}+x_2 u_{21},\ x_1 u_{12}+x_2 u_{22}).$

(b)

Let $(y_1,y_2)\neq (0,0)$ be a solution, so $(y_1,y_2)=x_1 v_1 + x_2 v_2$ for integers $x_1,x_2$.

Write

$Q(x_1,x_2)= (x_1 u_{11}+x_2 u_{21})^2 + (x_1 u_{12}+x_2 u_{22})^2.$

Expanding,

$Q(x_1,x_2)= x_1^2(u_{11}^2+u_{12}^2) + x_2^2(u_{21}^2+u_{22}^2) + 2x_1x_2(u_{11}u_{21}+u_{12}u_{22}).$

The hypothesis

$2|u_{11}u_{21}+u_{12}u_{22}| \le u_{11}^2+u_{12}^2$

implies

$2x_1x_2(u_{11}u_{21}+u_{12}u_{22}) \ge -|x_1x_2|(u_{11}^2+u_{12}^2).$

Hence

$Q(x_1,x_2) \ge (x_1^2-|x_1x_2|)(u_{11}^2+u_{12}^2) + x_2^2(u_{21}^2+u_{22}^2).$

If $x_1\neq 0$, then $x_1^2-|x_1x_2| = |x_1|(|x_1|-|x_2|)\ge 0$ whenever $|x_1|\ge |x_2|$. If $|x_1|<|x_2|$, then

$x_2^2(u_{21}^2+u_{22}^2) \ge (u_{21}^2+u_{22}^2) > (u_{11}^2+u_{12}^2),$

by the second inequality in the hypothesis.

If $x_1=0$, then $(y_1,y_2)=x_2 v_2$, so

$Q(0,x_2)=x_2^2(u_{21}^2+u_{22}^2)\ge u_{21}^2+u_{22}^2 \ge u_{11}^2+u_{12}^2.$

In all cases,

$y_1^2+y_2^2 \ge u_{11}^2+u_{12}^2.$

Equality holds only for $x_1=\pm 1$, $x_2=0$, giving $(y_1,y_2)=\pm (u_{11},u_{12})$.

Thus $(u_{11},u_{12})$ minimizes $y_1^2+y_2^2$ over all nonzero solutions.

This completes the proof. ∎