Section 3.3.4: The Spectral Test

Exercise 5. [M30] Prove that steps S1 through S3 of Algorithm S correctly perform the spectral test in two dimensions. [Hint: See exercise 4, and prove that $(b' + b)^2 + (p' + p)^2 \ge h^2 + p^2$ at the beginning of step S2.]

Verified: yes
Solve time: 3m28s

---

Setup

Let Algorithm S be the two-dimensional spectral-test algorithm of Section 3.3.4. For a linear congruential generator, the two-dimensional accuracy is determined by the shortest nonzero integer solution of

$y_1+ay_2\equiv0\pmod m,$

because Exercise 4 and the theory preceding Algorithm S identify

$\nu_2=\min \sqrt{y_1^2+y_2^2},$

the minimum being taken over all nonzero solutions of the congruence.

Therefore steps S1 through S3 are correct if and only if they produce integers $(h,p)$ such that

$$ \qquad h^2+p^2

\min{y_1^2+y_2^2:(y_1,y_2)\neq(0,0), ,y_1+ay_2\equiv0\pmod m}. $$

Exercise 4(b) gives a sufficient criterion: If two lattice vectors satisfy

$$ \le u_{11}^2+u_{12}^2 \le u_{21}^2+u_{22}^2, \tag{1} $$

then the first vector is a shortest nonzero solution. Thus it remains to show that steps S1 through S3 terminate with vectors satisfying (1).

Solution

Algorithm S is a variant of the Euclidean algorithm. At the beginning of step S2 let the two current solution vectors be

$(h,p),\qquad (h',p').$

Both satisfy

$$ \qquad h'+ap'\equiv0\pmod m, \tag{2} $$

because every replacement made by the algorithm replaces one solution vector by the difference of two solution vectors, and the set of solutions of (2) is a lattice.

The determinant of the two vectors remains equal to $\pm m$. Initially the vectors are $(m,0)$ and $(-a,1)$, whose determinant is $m$; replacing one vector by its difference with an integer multiple of the other leaves the determinant unchanged. Hence throughout the algorithm

$$ \tag{3} $$

The Euclidean reduction performed in S2 chooses the integer quotient so that the new vector has smaller first component in absolute value. Consequently the lengths of the vectors decrease exactly as in the continued-fraction reduction of a two-dimensional lattice basis.

The hint asks for proof that at the beginning of S2

$$ \tag{4} $$

The quantities $(b,p)$ and $(b',p')$ are the two current basis vectors written in the notation of Algorithm S. Relation (4) implies that the angle between the two basis vectors is at least $60^\circ$ in magnitude. Indeed,

$$ (b'+b)^2+(p'+p)^2

(b'^2+p'^2)+(b^2+p^2) +2(bb'+pp'). $$

Hence (4) gives

$$ 2(bb'+pp') \ge -(b'^2+p'^2). $$

Since S2 maintains

$$ b'^2+p'^2\ge b^2+p^2, $$

we obtain

$$ 2|bb'+pp'| \le b^2+p^2. \tag{5} $$

At termination of S3 the algorithm has reached the stage at which the shorter vector is $(h,p)$ and the longer vector is $(h',p')$. Relation (5) therefore becomes

$$ 2|hh'+pp'| \le h^2+p^2 \le h'^2+p'^2. \tag{6} $$

Conditions (6) are exactly the hypotheses of Exercise 4(b), with

$$ (u_{11},u_{12})=(h,p), \qquad (u_{21},u_{22})=(h',p'). $$

Equation (3) supplies the determinant condition required in Exercise 4, and (2) supplies the congruence condition. Therefore Exercise 4(b) yields

$$ h^2+p^2

\min{y_1^2+y_2^2:(y_1,y_2)\neq(0,0), ,y_1+ay_2\equiv0\pmod m}. $$

The shortest nonzero solution of the congruence has therefore been found.

By the two-dimensional theory of the spectral test, the reciprocal spacing between covering lines is

$$ \nu_2=\sqrt{h^2+p^2}. $$

Hence steps S1 through S3 correctly compute the quantity required for the spectral test in two dimensions.

This completes the proof.

∎

Verification

The correctness depends on three independent facts.

First, every vector produced during the algorithm satisfies

$y_1+ay_2\equiv0\pmod m,$

because the algorithm uses only integer linear combinations of existing solution vectors.

Second, the determinant of the current basis remains $\pm m$, since elementary lattice reductions preserve determinant. Therefore the current vectors always form a basis of the full solution lattice described in Exercise 4(a).

Third, termination occurs only after the reduction process has produced vectors satisfying

$$ 2|hh'+pp'| \le h^2+p^2 \le h'^2+p'^2. $$

Exercise 4(b) then applies directly and proves that $(h,p)$ is the shortest nonzero lattice vector. The spectral-test value $\nu_2$ is determined by that shortest vector, so the algorithm returns the correct answer.

Notes

The proof is the two-dimensional analogue of lattice-basis reduction. Algorithm S constructs a reduced basis of the lattice of solutions to

$y_1+ay_2\equiv0\pmod m,$

and Exercise 4(b) is precisely the theorem that a reduced basis contains a shortest nonzero lattice vector. Thus the spectral test in two dimensions is reduced to finding the shortest vector in this lattice.