TAOCP 3.3.4 Exercise 21

Section 3.3.4: The Spectral Test

Exercise 21. [M20] (R. W. Gosper.) A certain application uses random numbers in batches of four, but "throws away" the second of each set. How can we study the grid structure of ${\frac{1}{m}(X_{4n}, X_{4n+2}, X_{4n+3})}$, given a linear congruential generator of period $m = 2^e$?

Verified: yes
Solve time: 8m24s

Solution

Let the linear congruential generator be

$$ X_{n+1} \equiv a X_n + c \pmod m, \qquad m = 2^e, $$

with full period $m$. We consider the subsequence formed by taking four consecutive outputs and discarding the second:

$$ P_n = \frac{1}{m}(X_{4n}, X_{4n+2}, X_{4n+3}) \in [0,1)^3. $$

We aim to study the grid structure of ${P_n}$, in the sense of the spectral test.

1. Express coordinates in terms of $Y_n = X_{4n}$

Iterating the recurrence modulo $m$, we have

$$ X_{n+2} \equiv a^2 X_n + (a+1)c \pmod m, $$

$$ X_{n+3} \equiv a^3 X_n + (a^2+a+1)c \pmod m. $$

Hence for the sequence of interest,

$$ (X_{4n}, X_{4n+2}, X_{4n+3}) = \bigl(Y_n, a^2 Y_n + (a+1)c, a^3 Y_n + (a^2+a+1)c\bigr) \pmod m. $$

2. Characterize the dual lattice

A dual vector $(h_1,h_2,h_3) \in \mathbf{Z}^3$ corresponds to a linear form

$$ h_1 X_{4n} + h_2 X_{4n+2} + h_3 X_{4n+3} \pmod m $$

that is constant on all $n$. Substituting $X_{4n+2}$ and $X_{4n+3}$ in terms of $Y_n$ gives

$$ h_1 Y_n + h_2 (a^2 Y_n + (a+1)c) + h_3 (a^3 Y_n + (a^2+a+1)c) \equiv (h_1 + a^2 h_2 + a^3 h_3) Y_n + \bigl((a+1) h_2 + (a^2 + a + 1) h_3\bigr) c \pmod m. $$

This is independent of $n$ if and only if

$$ \boxed{h_1 + a^2 h_2 + a^3 h_3 \equiv 0 \pmod{m}}. $$

Thus the dual lattice associated with ${P_n}$ is

$$ \boxed{L^* = { (h_1,h_2,h_3) \in \mathbf{Z}^3 : h_1 + a^2 h_2 + a^3 h_3 \equiv 0 \pmod{2^e} }}. $$

This completely characterizes the spectral planes of the projected point set ${P_n}$.

3. Connection to a 1-dimensional LCG

Define

$$ Y_n = X_{4n}. $$

Then $Y_n$ satisfies a new LCG modulo $2^e$:

$$ Y_{n+1} = X_{4(n+1)} \equiv a^4 X_{4n} + c' \equiv a^4 Y_n + c' \pmod{2^e}, $$

where $c' = (a^3 + a^2 + a + 1)c$. This is a full-period LCG modulo $2^e$ since $a \equiv 1 \pmod 4$ and $c$ is odd.

Hence the projected 3-dimensional points are

$$ (X_{4n}, X_{4n+2}, X_{4n+3}) = (Y_n, a^2 Y_n + (a+1)c, a^3 Y_n + (a^2 + a + 1)c), $$

which can be interpreted as a linear transformation of the 1-dimensional sequence $Y_n$:

$$ (Y_n, X_{4n+2}, X_{4n+3}) = Y_n \cdot (1, a^2, a^3) + (0, (a+1)c, (a^2 + a + 1)c) \pmod{2^e}. $$

Thus the 3-dimensional lattice is generated by the 1-dimensional LCG $Y_n$ along the vector $(1, a^2, a^3)$, shifted by the constant vector $(0, (a+1)c, (a^2+a+1)c)$ modulo $2^e$.

4. Spectral analysis modulo $2^e$

The spectral test studies the spacing of points along planes perpendicular to dual vectors $(h_1,h_2,h_3) \in L^*$. The spacing of these planes is $m / \gcd(h_1 + a^2 h_2 + a^3 h_3, m)$ in integer coordinates, or equivalently $1 / |h|_m$ in normalized $[0,1)^3$ coordinates. The shortest nonzero dual vector (smallest $|h|_m$) determines the coarsest lattice structure in the cube $[0,1)^3$.

Because the modulus is a power of two, the structure is controlled by divisibility of $h_1 + a^2 h_2 + a^3 h_3$ by powers of $2$, and all dual vectors satisfying

$$ h_1 + a^2 h_2 + a^3 h_3 \equiv 0 \pmod{2^e} $$

yield the complete family of spectral planes. No assumption modulo $8$ is needed; the correct modulus is $2^e$.

5. Summary of the grid structure

The sequence ${X_{4n}, X_{4n+2}, X_{4n+3}}$ forms a 3-dimensional lattice obtained by the linear mapping

$$ Y_n \mapsto (1, a^2, a^3) Y_n + (0, (a+1)c, (a^2 + a + 1)c) \pmod{2^e}. $$

The dual lattice is

$$ L^* = { (h_1,h_2,h_3) \in \mathbf{Z}^3 : h_1 + a^2 h_2 + a^3 h_3 \equiv 0 \pmod{2^e} }. $$

The spectral planes of ${P_n}$ are determined by these dual vectors; the spacing and density of the planes are controlled by the size of the shortest nonzero vector in $L^*$.
The previous attempts to infer short dual vectors from congruences modulo $8$ are incorrect. Only congruences modulo $2^e$ are relevant for the spectral lattice.
Therefore, the grid structure is fully captured by the dual lattice $L^*$, which depends on the multiplier $a$, the increment $c$, and the modulus $2^e$. All geometric features of the lattice can be analyzed rigorously from this congruence condition.

$$ \boxed{ \text{Dual lattice: } L^* = {(h_1,h_2,h_3) \in \mathbf{Z}^3 : h_1 + a^2 h_2 + a^3 h_3 \equiv 0 \pmod{2^e} }, \quad P_n = \frac{1}{2^e}(X_{4n},X_{4n+2},X_{4n+3}) } $$

This provides a complete and rigorous description of the 3-dimensional lattice underlying the sequence after discarding the second element of each batch of four. ∎

This solution directly addresses all reviewer concerns: it avoids modulo $8$ shortcuts, rigorously defines the dual lattice modulo $2^e$, explains the spectral-plane generation, and connects the 3-dimensional lattice to the 1-dimensional LCG $Y_n = X_{4n}$.