Module 12 — The Spectral Test

Source: The Art of Computer Programming, Vol. 2, 3rd ed., §3.3.4 (with the lattice preliminaries of §3.3.4A–B and Table 1). Lab: labs/module-12-spectral · Grade it: ./grade 12

Self-contained: you can complete the module without the book. If you own Vol. 2, read §3.3.4 up to Algorithm S first; we build the same theory but stop our exact computations at $t = 3$ (Knuth's algorithm reaches $t = 8$).

In 1968 George Marsaglia published a paper with the unimprovable title "Random numbers fall mainly in the planes." Every linear congruential generator — no matter how carefully tuned — produces points in $t$ dimensions that lie on a family of parallel hyperplanes. The only question is how many planes, and the spectral test answers it exactly. It is, in Knuth's words, by far the most powerful test known for linear congruential generators: the bad ones it condemns include IBM's infamous RANDU, which silently corrupted a decade of published simulations. By the end of this module you will compute the test exactly — integer arithmetic, no approximations — and issue the same verdicts Knuth's Table 1 does.

Companion exhibit — The Illusion of Chaos. Before you compute the test, see it: the Museum's Loom of Chaos plots an LCG's pairs $(X_n, X_{n+1})$ so the lattice of parallel lines is visible to the eye — few coarse stripes for a bad multiplier, dense white noise for a good one. Load its RANDU preset to meet the generator this module condemns.

---

1. Random numbers fall mainly in the planes

A linear congruential generator (LCG) produces

$x_{n+1} = (a\cdot x_n + c) \bmod m.$

To study how random the sequence looks in $t$ dimensions, form the overlapping $t$-tuples

$P_n = (x_n, x_{n+1}, \ldots, x_{n+t-1}) \in [0, m)^t.$

Overlapping, because that is what consumers experience: a simulation that draws three coordinates in a row gets exactly these triples, and the serial tests of §3.3.2 measure exactly this point set. A truly random source would scatter the $P_n$ uniformly through the cube. An LCG cannot: the whole point set has a rigid crystalline structure, and we are about to compute its worst defect.

The increment is irrelevant

We will work with $c = 0$ throughout, and here is why nothing is lost. Run the same multiplier with increment $c$ from the same $x_0$ and compare with the $c = 0$ sequence: by induction, the term with increment is

$x_n(c) = a^n\cdot x_0 + (a^{n-1} + \cdots + a + 1)\cdot c \pmod{m},$

so the tuple starting at position $n$ is the $c = 0$ tuple plus the fixed vector $(0, c, (a+1)c, (a^2+a+1)c, \ldots) \bmod m$ — the same shift for every $n$. The entire point set is translated; translations change neither spacings nor plane counts, so every quantity in this module is independent of $c$. (This is Knuth's observation at the start of §3.3.4: the spectral test depends only on $a$ and $m$.)

---

2. The lattice theorem

A lattice in $\mathbb{Z}^t$ is the set of all integer combinations of some basis vectors. The structure theorem for LCG tuples is almost embarrassingly short:

Theorem (lattice structure). Every overlapping $t$-tuple of the sequence $x_{n+1} = a\cdot x_n \bmod m$ lies in the lattice $L$ generated by

$v = (1, a, a^2, \ldots, a^{t-1}) \quad\text{and}\quad m\cdot e_2,\ m\cdot e_3,\ \ldots,\ m\cdot e_t.$

Proof (two lines). Coordinate $i$ of the tuple starting at $x_n$ is $x_n\cdot a^{i-1} \bmod m$. So the tuple equals $x_n\cdot v$ minus a suitable multiple of $m$ in each coordinate after the first (the first needs none: $x_n$ is already in $[0, m)$) — and those corrections are exactly what $m\cdot e_2, \ldots, m\cdot e_t$ supply. ∎

Note that $m\cdot e_1$ is also in $L$: $m\cdot v - a\cdot(m\cdot e_2) - a^2\cdot(m\cdot e_3) - \cdots = (m, 0, \ldots, 0)$. So $L$ contains all of $m\cdot\mathbb{Z}^t$ plus the $m$ distinct multiples of $v \bmod m$; its determinant (volume of a fundamental cell) is $m^t / m = m^{t-1}$. The cube $[0, m)^t$ has volume $m^t$ and the sequence visits at most $m$ points of it — one point per cell, a perfect crystal.

Honest caveat: the theorem says the tuples lie in $L \cap [0, m)^t$; over a full period they typically fill it (that is Knuth's setting), while a short run or a restricted cycle (e.g. odd seeds for $m = 2^{31}$) fills a subset. The defects we compute are properties of $L$, hence upper bounds on the quality of any run.

---

3. Dual vectors, families of planes, and $\nu_t$

Call $u = (u_1, \ldots, u_t) \in \mathbb{Z}^t$ a dual vector ($u \ne 0$) if

$u_1 + a\cdot u_2 + a^2\cdot u_3 + \cdots + a^{t-1}\cdot u_t \equiv 0 \pmod{m}.$

Why "dual": $u\cdot v \equiv 0 \pmod{m}$ by definition, and $u\cdot(m\cdot e_i) \equiv 0$ trivially, so $u\cdot w \equiv 0 \pmod{m}$ for every $w \in L$. In particular, again in two lines: every tuple $P_n$ satisfies

$u\cdot P_n \equiv x_n\cdot(u_1 + a\cdot u_2 + \cdots + a^{t-1}\cdot u_t) \equiv 0 \pmod{m},$

because coordinate $i$ of $P_n$ is congruent to $x_n\cdot a^{i-1}$. So the entire point set lies on the family of parallel hyperplanes

$u\cdot x = k\cdot m, \qquad k \in \mathbb{Z}.$

How many planes meet the cube? For $x \in [0, m)^t$, split the dual vector into its positive and negative parts: $P = \sum_{u_i>0} u_i$ and $N = \sum_{u_i<0} |u_i|$. Then

$-(m-1)\cdot N \ \le\ u\cdot x \ \le\ (m-1)\cdot P,$

so $k = (u\cdot x)/m$ ranges over the integers of $[-(m-1)N/m, (m-1)P/m]$; counting them gives exactly $N + P - 1$ planes when $u$ has entries of both signs (and $P$ when it has one sign, where the $k = 0$ plane touches only the origin). Either way, the family has at most

$|u_1| + |u_2| + \cdots + |u_t| \quad\text{planes.}$

Small dual vector $\Rightarrow$ few planes $\Rightarrow$ bad generator.

How far apart are the planes? Adjacent hyperplanes $u\cdot x = km$ and $u\cdot x = (k+1)m$ are at distance $m/\|u\|$ (the standard point–plane distance). Short dual vector $\Rightarrow$ wide empty slabs.

Both defects are governed by the same quantity, and that is the test:

Definition (spectral test). For $t \ge 2$,

$\nu_t^2 = \min\left\{\, u_1^2 + \cdots + u_t^2 \ :\ u_1 + a\cdot u_2 + \cdots + a^{t-1}\cdot u_t \equiv 0 \pmod{m},\ u \ne 0 \,\right\}.$

$\nu_t$ is the length of the shortest nonzero dual vector. The maximum gap between adjacent covering planes, over all families, is $m/\nu_t$; and the family cut out by that shortest $u$ has at most $\sum |u_i| \le \sqrt{t}\cdot\nu_t$ planes (Cauchy–Schwarz). Large $\nu_t$ is good: every direction's dual vectors are then long, so no direction sees wide empty slabs or few planes.

The RANDU catastrophe, exactly

RANDU is $a = 65539 = 2^{16} + 3$, $m = 2^{31}$, $c = 0$ (odd seeds). The multiplier was chosen so that $a\cdot x$ could be computed with two shifts and two adds. But

$(a - 3)^2 = 2^{32} \equiv 0 \pmod{2^{31}} \quad\Longrightarrow\quad a^2 \equiv 6a - 9 \pmod{2^{31}},$

so $u = (9, -6, 1)$ is a dual vector: $9 - 6a + a^2 \equiv 0 \pmod{2^{31}}$. Every triple the generator will ever produce satisfies

$9\cdot x_n - 6\cdot x_{n+1} + x_{n+2} \equiv 0 \pmod{2^{31}}.$

Plane count: $N = 6$, $P = 10$, so $N + P - 1 =$ 15 planes (at most $9 + 6 + 1 = 16$) carry all $2^{29}$ triples in a cube with $2^{31}$ cells per side. In stage 3 you will prove nothing shorter exists: $\nu_3^2 = 9^2 + 6^2 + 1^2 = 118$. A good multiplier for $m = 2^{31}$ could have achieved $\nu_3 \approx 1448$ (the Hermite bound of §6), i.e. thousands of tightly packed plane families instead of 15 gaping slabs. Marsaglia's title was not hyperbole.

---

4. Two dimensions, exactly: Gauss–Lagrange reduction

For $t = 2$ the dual lattice is $L^* = \{(u_1, u_2) : u_1 + a\cdot u_2 \equiv 0 \pmod{m}\}$. It has an obvious basis:

Lemma. $L^*$ is generated by $v_1 = (m, 0)$ and $v_2 = (-a, 1)$.

Proof. Both satisfy the congruence. Conversely if $(u_1, u_2) \in L^*$, then $u_1 = -a\cdot u_2 + km$ for some integer $k$, so $(u_1, u_2) = u_2\cdot v_2 + k\cdot v_1$. ∎

$\nu_2^2$ is the squared length of the shortest nonzero vector of $L^*$, and in rank 2 there is an exact, fast, ancient algorithm for that — Lagrange's reduction, usually credited to Gauss. It is Euclid's algorithm acting on vectors: repeatedly subtract the best integer multiple of the shorter vector from the longer one.

Algorithm G (Gauss–Lagrange reduction)

Given a basis v_1, v_2 of a rank-2 lattice, find a shortest nonzero vector.

G1. [Initialize.] v1 <- (m, 0), v2 <- (-a, 1).
G2. [Order.]      If |v1| < |v2|, interchange v1 and v2.
G3. [Reduce.]     Let q be the nearest integer to (v1·v2)/(v2·v2);
                  set v1 <- v1 - q·v2.
G4. [Done?]       If |v1| >= |v2|, terminate; v2 is a shortest nonzero
                  vector and ν_2² = v2·v2. Otherwise return to G2.

Hand-trace it on the module's toy generator $a = 137$, $m = 256$ (do this on paper — it is the module's Fibonacci-trace moment):

pass	$v_1$	$v_2$	$\|v_1\|^2$	$\|v_2\|^2$	$v_1\cdot v_2$	$q$	new $v_1$	new $\|v_1\|^2$
1	$(256, 0)$	$(-137, 1)$	65536	18770	$-35072$	$-2$	$(-18, 2)$	328
2	$(-137, 1)$	$(-18, 2)$	18770	328	2468	8	$(7, -15)$	274
3	$(-18, 2)$	$(7, -15)$	328	274	$-156$	$-1$	$(-11, -13)$	$290 \ge 274$: stop

Answer: shortest vector $(7, -15)$, so $\nu_2^2 = 274$. Sanity: is $(7, -15)$ dual? The congruence for $(-7, 15)$: $-7 + 137\cdot 15 = 2048 = 8\cdot 256$ ✓ (a lattice contains $v$ iff it contains $-v$). The pair point set of this generator lies on $|-7| + |15| - 1 = 21$ lines, spaced $256/\sqrt{274} \approx 15.5$ apart.

Termination. Steps G2–G3 leave the lattice unchanged (swaps and shears are unimodular). If G4 does not stop, the new $v_1$ is strictly shorter than $v_2$, which was the shorter of the previous pair — so $\min(\|v_1\|^2, \|v_2\|^2)$, a positive integer, strictly decreases on every continuing pass. A decreasing sequence of positive integers is finite. (And if $q = 0$ the vector is unchanged, but then $\|v_1\| \ge \|v_2\|$ from G2, so G4 stops: no infinite idling.) This is module 01's proof pattern — invariant plus a decreasing quantity — operating on norms instead of remainders.

Optimality. At termination, two facts hold: $\|v_1\| \ge \|v_2\|$, and — the property of rounding to the nearest integer — $|v_1\cdot v_2| \le \|v_2\|^2/2$. Now take any nonzero lattice vector $w = \alpha\cdot v_1 + \beta\cdot v_2$ ($\alpha, \beta \in \mathbb{Z}$).

• If $\beta = 0$: $\|w\| = |\alpha|\cdot\|v_1\| \ge \|v_2\|$.

• If $\alpha = 0$: $\|w\| = |\beta|\cdot\|v_2\| \ge \|v_2\|$.

• Otherwise,

  $$\begin{aligned} \|w\|^2 &= \alpha^2\|v_1\|^2 + 2\alpha\beta(v_1\cdot v_2) + \beta^2\|v_2\|^2 \\ &\ge \alpha^2\|v_2\|^2 - 2|\alpha||\beta|\cdot(\|v_2\|^2/2) + \beta^2\|v_2\|^2 \\ &= (\alpha^2 - |\alpha||\beta| + \beta^2)\cdot\|v_2\|^2 \ge \|v_2\|^2, \end{aligned}$$

because $\alpha^2 - |\alpha||\beta| + \beta^2 = ((|\alpha| - |\beta|)^2 + \alpha^2 + \beta^2)/2 \ge 1$ for nonzero integers. So $v_2$ is genuinely shortest. ∎ Note where integrality did the work: for real $\alpha = \beta = \tfrac12$ the quadratic form dips to $\tfrac14$. The final basis is called reduced; this is the 2-dimensional case of what LLL approximates in higher rank.

---

5. Three dimensions: a certified search

For $t = 3$ the dual condition is $u_1 + a\cdot u_2 + a^2\cdot u_3 \equiv 0 \pmod{m}$. Choose $(u_2, u_3)$ freely; then $u_1$ is pinned down modulo $m$, and the best representative is obvious:

Lemma (centered residue). Fix $(u_2, u_3) \ne (0, 0)$ and let $r \in [0, m)$ be the residue of $a\cdot u_2 + a^2\cdot u_3$. Among all valid $u_1 \equiv -r \pmod{m}$, the one of smallest absolute value is the centered residue — $u_1 = -r$ if $2r \le m$, else $u_1 = m - r$ — and it satisfies $|u_1| \le m/2$. Any other member of the class differs by a nonzero multiple of $m$ and is at least as far from 0. ∎

So the 3-D minimum is a search over the $(u_2, u_3)$ plane. The trouble: the plane is infinite. The fix: a bound that certifies itself.

Algorithm C (certified bounded search)

C1. [Initialize.] best <- m²  (the class (u2,u3) = (0,0) contributes
                  (m, 0, 0); u = 0 itself is excluded).  B <- 1.
C2. [Scan.]       For all (u2, u3) in [-B, B]² except (0,0): set u1 to the
                  centered residue of -(a·u2 + a²·u3) mod m, and
                  best <- min(best, u1² + u2² + u3²).
C3. [Certified?]  If B² >= best, terminate: ν_3² = best.
C4. [Grow.]       B <- 2B; return to C2.

Why termination at C3 is a proof, not a hope. Suppose $B^2 \ge$ best and some dual vector $u$ is shorter than best. Where is it? If $|u_2| > B$ or $|u_3| > B$, then $\|u\|^2 \ge u_2^2 + u_3^2 > B^2 \ge$ best — contradiction. So $(u_2, u_3)$ lies in the scanned square; but there we already took the best possible $u_1$ for its class (the centered-residue lemma), so $u$ cannot beat best either. Hence best $= \nu_3^2$ exactly. The search bound is justified by the answer it found — the same trick as branch-and-bound, in its simplest possible clothing.

Why C4 terminates. Hermite's theorem (next section) gives $\nu_3^2 \le 2^{1/3}\cdot m^{2/3} < 2.2\times 10^6$ for $m \le 2^{31}$, so once $B = 4096$ we have $B^2 > \nu_3^2 \ge$ best-after-scan and C3 fires. Total work: the doubling scans sum to at most $(4/3)\cdot(2\cdot 4096+1)^2 \approx 9\times 10^7$ cheap iterations — the geometric series is dominated by its last term, a bound you proved for table doubling in earlier modules. (In practice RANDU certifies at $B = 16$ and the minimal standard at $B = 1024$.)

Why not extend Gauss reduction instead? Rank-3 reduction (or LLL) gives a nearly shortest vector with more delicate proofs; Knuth's Algorithm S does exact enumeration with Cholesky-style pruning. Algorithm C is the honest kernel of the latter: exact, certified, and slow only in ways we can afford at $t = 3$.

---

6. Figures of merit: how good could $\nu_t$ possibly be?

Raw $\nu_t$ values are incomparable across moduli — $\nu_3 = 639$ is meaningless until you know how large $\nu_3$ could be for that $m$. Two normalizations:

Hermite's constants. For any rank-$t$ lattice of determinant $d$, the shortest nonzero vector satisfies $\lambda_1^2 \le \gamma_t\cdot d^{2/t}$, where

$$\begin{aligned} \gamma_2 &= 2/\sqrt{3} \approx 1.1547 \quad\text{(hexagonal lattice, Lagrange/Gauss),} \\ \gamma_3 &= 2^{1/3} \approx 1.2599 \quad\text{(face-centered cubic packing, Gauss).} \end{aligned}$$

Our dual lattice $L^* = \{u : \sum u_i a^{i-1} \equiv 0 \pmod{m}\}$ has index $m$ in $\mathbb{Z}^t$ (one congruence mod $m$), hence determinant $m$. Therefore

$\nu_2^2 \le (2/\sqrt{3})\cdot m \qquad\text{and}\qquad \nu_3^2 \le 2^{1/3}\cdot m^{2/3}.$

These bounds are load-bearing twice in the lab: they justify the brute-force cutoff in stage 2 ($|u_2| \le \sqrt{\gamma_2\cdot m}$ suffices) and the termination of Algorithm C in stage 3.

Knuth's $\mu_t$ (§3.3.4, Eq. (37)) compares $\nu_t$ to the ideal by volume:

$\mu_t = \frac{\text{volume of the } t\text{-ball of radius } \nu_t}{m} = \frac{\pi^{t/2}\cdot \nu_t^t}{(t/2)!\cdot m},$

so

$\mu_2 = \pi\cdot\nu_2^2/m \qquad\text{and}\qquad \mu_3 = (4/3)\cdot\pi\cdot\nu_3^3/m$

(the half-integer factorial: $(3/2)! = (3/4)\sqrt{\pi}$). Interpretation: the dual lattice has one point per volume $m$, so $\mu_t$ is the expected number of lattice points in a ball whose radius is the actual shortest vector — if $\mu_t$ is tiny, that vector is anomalously short and the generator is bad in $t$ dimensions. Hermite caps the scale: $\mu_2 \le 2\pi/\sqrt{3} \approx 3.63$ and $\mu_3 \le (4/3)\pi\sqrt{2} \approx 5.92$. Knuth's rule of thumb: $\mu_t \ge 0.1$ passes, $\mu_t \ge 1$ is excellent.

The verdicts you will compute in the lab (compare Knuth's Table 1):

generator	$m$	$\nu_2^2$	$\nu_3^2$	$\mu_2$	$\mu_3$	verdict
toy, $a = 137$	256	274	30	3.36	2.69	great for its size
RANDU, $a = 65539$	$2^{31}$	2 147 221 514	118	3.14	$2.5\times10^{-6}$	catastrophic in 3-D
minimal standard, $a = 16807$	$2^{31}-1$	$16807^2+1$	408 197	0.41	0.51	passes; unspectacular
$a = 48271$ (std::minstd_rand)	$2^{31}-1$	1 990 735 345	1 433 881	2.91	3.35	excellent for this $m$

Two morals. First, the test is per dimension: RANDU's pairs are nearly perfect ($\mu_2 \approx \pi$, close to the Hermite ceiling!) while its triples are ruinous — you must test every $t$ your application consumes. Second, multipliers are not commodities: 16807 and 48271 cost the same to evaluate, and one is an order of magnitude better. That is why the revision happened.

Scope note (honesty about $t \le 3$)

Knuth's Algorithm S carries this program to $t = 4, 5, \ldots, 8$: it maintains dual and primal bases simultaneously, transforms them as t grows, and enumerates candidates inside an ellipsoid with Cholesky-factorization bounds instead of our square. Every idea you implement here — dual lattice, exact integer arithmetic, a search bound certified by the best value found — reappears there, industrial-strength. We stop at $t = 3$ because rank-2 reduction and one certified 2-parameter search teach the entire method without the bookkeeping; if you want the rest, exercise W6 and §3.3.4 are waiting.

---

7. Why it's done this way

• Exact integer arithmetic, i128. $\nu_t^2$ is a minimum over a lattice; a single rounding error can report a vector that does not exist or miss one that does, and a "certification" computed in floating point certifies nothing. Norms reach $m^2 \approx 2^{62}$; i128 holds them with room to spare. Floating point enters exactly once, in $\mu_t$, after the integer minimum is frozen.
• The dual lattice, not the primal. The failure mode users care about is planes-and-slabs, and plane families correspond one-to-one to dual vectors, with gap $m/\|u\|$. Minimizing over the dual is maximizing the worst slab — and the dual basis is available by inspection, no inversion needed.
• Reduction in 2-D, enumeration in 3-D. Rank 2 is the one case where a greedy reduction provably finds the optimum (§4's proof), so use it. At rank 3 greedy is no longer provably optimal, but enumeration with a self-certifying bound is still cheap — so we buy the proof with cycles. This mirrors real practice: LLL/BKZ reduce, then an exact enumeration finishes.
• c = 0 without loss. The increment translates the point set (§1); carrying it through every formula would buy nothing and obscure the lattice. Knuth drops it in the first paragraph of §3.3.4 for the same reason.
• Overlapping tuples. Non-overlapping tuples of a full-period LCG form essentially the same lattice (a sub-sequence of an LCG is an LCG with multiplier $a^t$), but overlapping tuples are what serial correlation actually sees, and they make the lattice theorem a one-liner.

8. Stage-by-stage lab guide

Open labs/module-12-spectral/src/lab.rs. Run ./grade 12; stages run in order and stop at the first failure.

Stage 1 — tuples and is_dual_vector

Mechanics first. tuples(a, m, t, x0, count) generates $\text{count} + t - 1$ terms of $x_{n+1} = a\cdot x_n \bmod m$ and windows them; multiply in i128 before reducing. is_dual_vector(u, a, m) checks $\sum u_i\cdot a^{i-1} \equiv 0 \pmod{m}$ with incrementally computed powers (never form $a^{t-1}$ unreduced!) and rejects $u = 0$. Coordinates may be negative: rem_euclid gives the non-negative residue Rust's % does not. The tests make you verify RANDU's $(9, -6, 1)$ — and that every generated triple obeys the planes equation, which is the lattice theorem made executable.

Stage 2 — nu2_squared

Algorithm G on the basis $(m, 0)$, $(-a, 1)$, all in i128. The one subtlety is $q =$ nearest integer to $d/n$ with $n > 0$: (2*d + n).div_euclid(2*n) does it (check it against the hand trace: $d = -35072$, $n = 18770$ must give $q = -2$). The tests cross-check against a brute force whose cutoff is the Hermite bound — read that helper; its comment is the argument you should be able to reproduce cold — and pin the hand-traced $\nu_2^2(137, 256) = 274$.

Stage 3 — nu3_squared_certified

Algorithm C verbatim. Keep the running residue $r = (a\cdot u_2 + a^2\cdot u_3) \bmod m$ incremental if you like speed, but correctness only needs the centered residue chosen right: $r$ vs $m - r$, smaller absolute value wins. Do not forget to skip $(u_2, u_3) = (0, 0)$ inside the scan while still seeding best $= m^2$. The tests demand RANDU's 118 on the nose, the frozen 408 197 for the minimal standard, agreement with a full brute force on tiny moduli, and a witness dual vector achieving your minimum.

Stage 4 — mu2 and mu3

Ten lines: $\mu_2 = \pi\cdot\nu_2^2/m$, $\mu_3 = (4/3)\pi\cdot\nu_3^3/m$ with $\nu_3 = \sqrt{\nu_3^2}$ in f64. The tests hold you to the reference values to 1e-9 and — the point of the whole module — to the ordering: $48271 \succ 16807 \succ \text{RANDU}$ on $\mu_3$, with five orders of magnitude between the ends.

9. In the real world

• RANDU's corrupted simulations. RANDU shipped in IBM's System/360 Scientific Subroutine Package and was the de facto random source of the late 1960s and 1970s. Any Monte Carlo computation that consumed triples — particle transport, numerical integration in 3-D, generation of random directions — was sampling 15 planes instead of a volume. Results built on it had to be re-examined for years afterwards; Knuth's verdict in §3.3.4 is that its very name deserves contempt, and textbooks still cite it as the canonical warning that a generator can pass 1-D tests perfectly while being unusable. The deeper lesson: the flaw was provable in advance — $(a-3)^2 = 2^{32}$ is one line of algebra — but nobody ran the test before shipping.
• Why PCG and xoshiro replaced plain LCGs. The lattice structure you computed is not a bug of bad multipliers; it is a theorem about all LCGs. Even the best multiplier leaves $\nu_t \approx m^{1/t}\cdot(\gamma_t)^{1/2}$, so a 32-bit LCG is structurally weak in high dimensions, and power-of-two moduli additionally make the low $k$ bits cycle with period $2^k$. Modern designs keep a linear engine but destroy the lattice at the output: PCG (O'Neill, 2014) advances a 64/128-bit LCG state — with multipliers chosen via exactly this spectral theory, and its default multiplier 6364136223846793005 is the one Knuth ships in MMIX (and the one this course's test files use for deterministic data) — then applies a state-dependent permutation (xorshift + rotate) so that output tuples no longer lie on the state lattice. The xoshiro/xoroshiro family (Blackman & Vigna) uses linear recurrences over GF(2) plus a nonlinear scrambler (** = multiply–rotate–multiply) for the same reason. Both pass TestU01's BigCrush, where every raw LCG of comparable size fails — largely on lattice-derived tests.
• Where LCGs are still fine. As the state transition inside PCG and in java.util.Random-style engines (weak, but understood); as combined generators — L'Ecuyer's MRG32k3a, built from two multiple-recursive congruential generators chosen by spectral-type criteria, remains a workhorse of simulation libraries and GPU stream packages (MATLAB, SSJ, cuRAND); and anywhere reproducible, cheap, statistically undemanding streams are needed: test-data generation (this repo!), procedural jitter in graphics, load-balancing salts. The rule: fine when nobody consumes $k$-tuples as geometry, or when an output scrambler stands between the lattice and the user. And when someone proposes a new multiplier, the spectral test — Fishman–Moore/L'Ecuyer-style exhaustive searches, Knuth's Algorithm S — is still exactly how it is vetted.

10. Check your understanding

Answer before moving on (hints inverted at the end of each item):

1. Adding an increment $c$ changes every $x_n$ — why does it change no $\nu_t$? Hint: write the $c$-tuple as ($c = 0$ tuple) $+ w$ for a fixed $w$; what do translations do to plane families?
2. Show $9 - 6a + a^2 \equiv 0 \pmod{2^{31}}$ for $a = 2^{16} + 3$ without multiplying out $a^2$. Hint: it is $(a - 3)^2$.
3. RANDU's planes: derive the count 15 from $u = (9, -6, 1)$. Hint: bound $9x_1 - 6x_2 + x_3$ over $[0, m)^3$ and count multiples of $m$ strictly inside; $N + P - 1$ with $N = 6$, $P = 10$.
4. In Algorithm C, why may the scan fix $u_1$ to the centered residue and ignore every other member of the class — could a longer $u_1$ ever pair with the same $(u_2, u_3)$ to give a shorter vector? Hint: the other coordinates don't change, and $|u_1|$ only grows.
5. The optimality proof of Algorithm G needs $\alpha^2 - |\alpha\beta| + \beta^2 \ge 1$. Where does it fail if $\alpha, \beta$ range over reals, and what does that tell you about why lattice problems are hard while linear algebra is easy? Hint: try $\alpha = \beta = \tfrac12$; shortest-vector is discrete optimization.

11. Exercises

Ratings use Knuth's scale: 00 immediate · 10 a minute · 20 fifteen minutes to an hour · 30 hours · 40 term project. M = mathematically oriented. Log attempts in course/module-12-spectral/exercises.md. (These are curated for our $t \le 3$ build; if you own Vol. 2, the exercises of §3.3.4 continue the story — several assume the full Algorithm S.)

Ex.	Rating	Statement
▶W1	M10	Prove $\nu_{t+1} \le \nu_t$ for every $a, m$. (Pad a dual vector with a zero.) So generators only get worse as $t$ grows.
W2	M18	Write out the translation proof of §1 in full: exhibit the fixed vector $w_t$ for general $t$ and verify $P_n(c) = P_n(0) + w_t$ (mod $m$ per coordinate).
W3	M22	Prove the plane-count formula: a dual $u$ with both signs present yields exactly $N + P - 1$ planes meeting $[0, m)^t$, assuming each candidate plane contains at least one integer point of the cube. Where is that assumption used?
▶W4	M24	Fill in every inequality of the Gauss–Lagrange optimality proof, and show the reduced basis also achieves the second minimum: $v_1$ is a shortest vector independent of $v_2$.
W5	22	Instrument Algorithm C: report the final $B$ and total iterations for RANDU, 16807, 48271. Verify the doubling schedule's cost is $\le 4/3$ of the final scan.
▶W6	30	Extend the certified search to $t = 4$ (scan $(u_2,u_3,u_4)$, centered $u_1$; same certification). Estimate the cost from the Hermite bound $\gamma_4 = \sqrt{2}$, then measure. Reproduce $\nu_4$ for RANDU.
W7	M28	For $m = 2^{31} - 1$, the multiplier 48271 was found by exhaustive spectral search (Fishman–Moore style). Search all $a$ in a range of your choice maximizing $\min(\mu_2, \mu_3)$ and see how close to 48271-quality you get.

12. Proof techniques you practiced

• Reduction to a canonical case — dropping $c$ by exhibiting the point sets as translates (§1); one line of algebra deleted a parameter from the whole theory.
• Proof by generators — the lattice theorem and dual-vector annihilation were verified on basis vectors only, and linearity did the rest (§2, §3).
• Counting by bounding a linear form — the plane count $N + P - 1$ came from trapping $u\cdot x$ in an interval and counting multiples of $m$ inside it (§3); the same move produced Lamé-style bounds in module 01.
• Invariant + strictly decreasing integer quantity — termination of Gauss–Lagrange reduction (§4), the course's oldest pattern, here with unimodularity as the invariant and the squared norm as the descent.
• Optimality via a quadratic-form inequality — the exchange argument $\alpha^2 - |\alpha\beta| + \beta^2 \ge 1$ turned "locally reduced" into "globally shortest" (§4), with integrality load-bearing.
• Certified enumeration — a search bound justified a posteriori by the best value found, plus an a priori Hermite bound to guarantee the loop halts (§5, §6). This is the skeleton of every branch-and-bound correctness argument you will ever write.

13. Where this leads

• Module 04 gave you the LCG and its period theory (§3.2.1); this module is the quality theory that decides which full-period generator to ship. Together they are Knuth's answer to "what multiplier?"
• The reduction/enumeration pair (Gauss–Lagrange, certified search) is the entry point to lattice algorithms at large: LLL, BKZ, and the shortest-vector problems underlying post-quantum cryptography — where §4's optimality argument reappears as the base case of LLL's analysis.
• Knuth's Algorithm S ($t \le 8$) adds simultaneous primal/dual basis updates and ellipsoid enumeration — a finished branch-and-bound built on stage 3's certification idea.
• The statistical companion is §3.3.2's serial test and the empirical batteries (TestU01); the spectral test is the theoretical member of that family — it examines the whole period at once, no sampling.