The spectral test consists of comparing the length of a shortest vector in a lattice associated with a linear congruential generator with multiplier $a$ and modulus $m$ to the maximum possible length of a shortest vector in any lattice of the same dimension.
In particular the spectral test's figure of merit of degree $d$ consists of
$$
\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\,,
$$
where $\nu_d$ is the $L_2$ norm of the shortest vector of the lattice generated by the rows
$$
\begin{pmatrix}
m&0&0&\dots&0\\
a&1&0&\dots&0\\
a^2&0&1&\dots&0\\
&&\dots&\\
a^{d-1}&0&0&\dots&1
\end{pmatrix},
$$
and $\gamma_d$ is Hermite's constant for dimension $d$, or an approximation thereof. Since the determinant of this lattice is $m$, the term $\gamma_d^{1/2}m^{1/d}$ is a tight upper bound for the shortest vector for a lattice of dimension $d$. (Note: the figure of merit if degree $d$ is usually defined as the minimum of all scores from $2$ up to $d$; I'm ignoring that here for simplicity).
Computing an exact average for this score seems pretty difficult. However, we can relax the problem a bit and pretend that the lattices of the above form can be modeled as random lattices, in which case we can use the Gaussian heuristic and approximate the expected value of a shortest vector in dimension $d$ as
$$
\left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} m^{1/d}\,,
$$
from which we can obtain an average spectral test score for dimension $d$ as
$$
\frac{ \left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} }{\gamma_d^{1/2}}\,.
$$
Below are the respective approximations for dimensions $2$ to $8$, where the Hermite constant is known exactly. Do note that we are committing here at least two sins:
- Treating fairly structured lattices as randomly-sampled lattices;
- Using asymptotic approximations at pretty low dimensions, which might not be too accurate.
| $d$ |
$\mathbf{E}\left[\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\right]$ |
| 2 |
0.525 |
| 3 |
0.552 |
| 4 |
0.564 |
| 5 |
0.583 |
| 6 |
0.589 |
| 7 |
0.595 |
| 8 |
0.593 |
Curiously enough, the score defined by Knuth (Volume 2, §3.3.4),
$$
\mu_d = \frac{\pi^{d/2}\nu_d^d}{(d/2)! m}\,,
$$
is comparing the LCG's lattice structure to this expected average value, but with a different scaling. According to Knuth, $\mu_d \ge 1$ is a good score, meaning that the LCG's lattice behaves like a random lattice would.
