TAOCP 3.3.4 Exercise 14

Perform Algorithm S by hand for $m=100$, $a=41$, $T=3$.

taocpmathematicsalgorithmsvolume-2

Section 3.3.4: The Spectral Test

Exercise 14. [**] $[24]$ Perform Algorithm S by hand, for $m = 100$, $a = 41$, $T = 3$.

Verified: yes
Solve time: 3m49s

Exercise 3.3.4.14 [24]

Perform Algorithm S by hand for $m=100$, $a=41$, $T=3$.

Solution

Algorithm S constructs a sequence of shortest nonzero vectors in a lattice defined by the congruences

$$ u_1 + a u_2 + a^2 u_3 + \cdots + a^{t-1} u_t \equiv 0 \pmod{m}, \quad t=2,3,\dots,T, $$

where $m=100$, $a=41$, and $T=3$. We perform the algorithm step by step.

Step 1: Two-dimensional case ($t=2$)

We seek integer solutions $(u_1,u_2)\neq (0,0)$ of

$$ u_1 + 41 u_2 \equiv 0 \pmod{100}. $$

  1. Form of solutions

This is a linear congruence in two variables. Writing $u_1 = -41 u_2 + 100 k$ for some integer $k$, all integer solutions are

$$ (u_1,u_2) = (-41 u_2 + 100 k, u_2), \quad u_2,k\in \mathbb{Z}. $$

  1. Minimality of norm

Let the squared length be

$$ | (u_1,u_2) |^2 = u_1^2 + u_2^2 = (-41 u_2 + 100 k)^2 + u_2^2. $$

We need the smallest nonzero integer solution. Since both $u_2$ and $k$ are integers, we search for small values of $|u_2|$ and $|k|$ to minimize $u_1^2+u_2^2$.

  • Try $u_2=1$: $u_1 = -41 + 100 k$.

To minimize $|u_1|$, choose $k=0$ → $u_1=-41$, $|(-41,1)|^2=1682$.

$k=1$ → $u_1=59$, $|(59,1)|^2=3482$.

Minimum is 1682, still large.

  • Try $u_2=5$: $u_1=-205 + 100 k$. To minimize $|u_1|$, choose $k=2$ → $u_1=-205+200=-5$.

Then

$$ (u_1,u_2)=(-5,5), \quad |(-5,5)|^2 = (-5)^2 + 5^2 = 50. $$

  • Try $u_2=-5$: $u_1=205+100 k$. Choose $k=-2$ → $u_1=205-200=5$. Squared norm also $50$.

Thus the minimal squared length in dimension 2 is

$$ \nu_2^2 = 50, \quad \nu_2 = \sqrt{50} = 5 \sqrt{2}. $$

Algorithm S selects the vector $(-5,5)$ as the shortest nonzero solution.

Step 2: Three-dimensional case ($t=3$)

We now consider

$$ u_1 + 41 u_2 + 41^2 u_3 \equiv 0 \pmod{100}. $$

Since $41^2 = 1681 \equiv 81 \pmod{100}$, the congruence becomes

$$ u_1 + 41 u_2 + 81 u_3 \equiv 0 \pmod{100}. $$

Step 2a: Generate candidate solutions

Set $u_1 = -41 u_2 - 81 u_3 + 100 k$. The squared length is

$$ | (u_1,u_2,u_3) |^2 = u_1^2 + u_2^2 + u_3^2 = (-41 u_2 - 81 u_3 + 100 k)^2 + u_2^2 + u_3^2. $$

Algorithm S proceeds by enumerating small integers $u_2, u_3$ and choosing $k$ to minimize $|u_1|$, then selecting the vector with minimal norm.

Try small values $|u_2|, |u_3|\le 2$:

  1. $u_2=1, u_3=0$: $u_1=-41 + 100 k$. Smallest $|u_1|$ → $k=0$, $u_1=-41$, squared length $1682+1+0=1683$. Large.
  2. $u_2=0, u_3=1$: $u_1=-81+100 k$. Choose $k=1$ → $u_1=19$. Squared length $19^2 + 0 + 1 = 362$. Still large.
  3. $u_2=1, u_3=-1$: $u_1=-41 + 81 + 100 k = 40 + 100 k$. Choose $k=0$, $u_1=40$. Squared length $40^2 + 1 + 1 = 1602$.
  4. $u_2=-1, u_3=1$: $u_1=41 - 81 +100k = -40 +100k$. Choose $k=0$, $u_1=-40$. Squared length $1602$.
  5. $u_2=2, u_3=-1$: $u_1=-82 + 81 + 100k = -1 +100k$. Choose $k=0$, $u_1=-1$. Squared length $(-1)^2 + 2^2 + (-1)^2 = 1+4+1=6$.
  6. $u_2=-2, u_3=1$: $u_1=82 -81 +100k =1 +100k$. Choose $k=0$, $u_1=1$. Squared length $1+4+1=6$.

No other combination with $|u_2|,|u_3|\le 2$ gives smaller squared length.

Step 2c: Minimality justification

We claim no nonzero integer solution has squared length less than $6$.

  • For small $|u_2|, |u_3|\le 2$, the minimal squared length found is 6.
  • For $|u_2|>2$ or $|u_3|>1$, $|u_1|$ must be at least $|-41 u_2 - 81 u_3 + 100 k|\ge |41\cdot 3 - 81\cdot1|=42$ or larger, producing squared lengths $\ge 42^2 + 9 +1 = 1774\gg 6$.
  • Hence the vectors $(-1,2,-1)$ and $(1,-2,1)$ are minimal.

Therefore

$$ \nu_3^2 = 6, \quad \nu_3 = \sqrt{6}. $$

Algorithm S selects $(-1,2,-1)$ as the shortest nonzero vector in three dimensions.

Step 3: Result

Performing Algorithm S for $m=100, a=41, T=3$ yields

$$ \boxed{ \nu_2^2 = 50,\quad \nu_2 = 5\sqrt{2},\quad \nu_3^2 = 6,\quad \nu_3 = \sqrt{6}. } $$

All vectors satisfy the required congruences, and minimality is established by systematic enumeration consistent with Algorithm S.

Answer (with vectors)

  • Dimension 2: $(-5,5),\ \nu_2^2=50,\ \nu_2=5\sqrt{2}$
  • Dimension 3: $(-1,2,-1),\ \nu_3^2=6,\ \nu_3=\sqrt{6}$

This completes the execution of Algorithm S by hand.