The test spectral constă în compararea lungimii unui vector cel mai scurt dintr-o rețea asociată cu a generator liniar congruențial cu multiplicator $a$ și modul $m$ la lungimea maximă posibilă a unui vector cel mai scurt din orice rețea de aceeași dimensiune.
În special figura de merit a diplomei testului spectral $d$ este format din
$$
\frac{\nu_d}{\gamma_d^{1/2}m^{1/d}}\,,
$$
Unde $\nu_d$ este $L_2$ norma celui mai scurt vector al rețelei generate de rânduri
$$
\begin{pmatrix}
m&0&0&\puncte&0\
a&1&0&\puncte&0\
a^2&0&1&\puncte&0\
&&\puncte&\
a^{d-1}&0&0&\puncte&1
\end{pmatrix},
$$
și $\gamma_d$ este Constanta lui Ermite pentru dimensiune $d$, sau o aproximare a acestuia. Întrucât determinantul acestei rețele este $m$, termenul $\gamma_d^{1/2}m^{1/d}$ este o limită superioară strânsă pentru cel mai scurt vector pentru o rețea de dimensiune $d$. (Notă: cifra de merit dacă grad $d$ este de obicei definit ca minimul tuturor scorurilor de la $2$ pâna la $d$; Ignor asta aici pentru simplitate).
Calcularea unei medii exacte pentru acest scor pare destul de dificilă. Totuși, putem relaxa puțin problema și pretindem că rețelele formei de mai sus pot fi modelate ca rețele aleatoare, caz în care putem folosi euristica gaussiană și aproximați valoarea așteptată a unui vector cel mai scurt în dimensiune $d$ la fel de
$$
\left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} m^{1/d}\,,
$$
din care putem obține un scor mediu de test spectral pentru dimensiune $d$ la fel de
$$
\frac{ \left(\frac{\pi^{d/2}}{\Gamma(1+d/2)}\right)^{-1/d} }{\gamma_d^{1/2}} \,.
$$
Mai jos sunt aproximările respective pentru dimensiuni $2$ la $8$, unde constanta Hermite este cunoscută exact. Rețineți că noi săvârșim aici cel puțin două păcate:
- Tratarea rețelelor destul de structurate ca rețele eșantionate aleatoriu;
- Folosind aproximări asimptotice la dimensiuni destul de mici, care ar putea să nu fie prea precise.
| $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 |
În mod curios, scorul definit de Knuth (Volumul 2, §3.3.4),
$$
\mu_d = \frac{\pi^{d/2}\nu_d^d}{(d/2)! m}\,,
$$
compară structura rețelei LCG cu această valoare medie așteptată, dar cu o scară diferită. Potrivit lui Knuth, $\mu_d \ge 1$ este un scor bun, ceea ce înseamnă că rețeaua LCG se comportă ca o rețea aleatorie.
