TAOCP 3.3.4 Exercise 3
Let $b=a-1$.
Section 3.3.4: The Spectral Test
Exercise 3. [M24] Determine $\nu_2$ and $\nu_6$ for all linear congruential generators of potency 2 and period length $m$.
Verified: yes
Solve time: 8m50s
Solution
Let $b=a-1$. For a linear congruential generator of period length $m$ and potency $2$,
$b^2\equiv0\pmod m,\qquad b\not\equiv0\pmod m.$
By the theory of the spectral test, $\nu_t$ is the minimum Euclidean length of a nonzero integer vector $(u_1,\ldots,u_t)$ satisfying
$u_1+a u_2+\cdots+a^{t-1}u_t\equiv0\pmod m. \eqno(15)$
Since $b^2\equiv0\pmod m$,
$$$$
Hence (15) becomes
$\sum_{j=1}^t u_j+b\sum_{j=1}^t (j-1)u_j\equiv0\pmod m. \eqno{*}$
The case $t=2$
Equation (15) is
$$$$
Because $m\mid b^2$,
$$ =-1+(1+b)(1-b) =-b^2 \equiv0\pmod m. $$
Therefore $(u_1,u_2)=(-1,,1-b)$ is an admissible dual vector, whose squared length is
$$$$
Any nonzero solution of $u_1+a u_2\equiv0\pmod m$ having smaller Euclidean length would satisfy
$$$$
hence would actually satisfy
$$$$
The primitive solution of this exact equation is $(-a,1)$, whose length is larger than that of $(-1,1-b)$ because $a=b+1>1$. Thus the shortest nonzero dual vector is $(-1,1-b)$.
Consequently
$$ \nu_2=\sqrt{,1+(b-1)^2,} =\sqrt{,1+(a-2)^2,}. $$
The case $t=6$
Using $a^k\equiv1+kb\pmod m$, equation (*) becomes
$$ \sum_{j=1}^6 u_j+b\sum_{j=1}^6 (j-1)u_j\equiv0\pmod m. $$
The vector
$$ (1,-1,-1,1,0,0) $$
satisfies
$$ \sum u_j=0, \qquad \sum (j-1)u_j =0-1-2+3=0, $$
hence it satisfies (15) exactly. Its squared length is
$$ 1+1+1+1=4. $$
No nonzero admissible vector can have squared length $1$, $2$, or $3$.
A vector of squared length $1$ has only one nonzero component and cannot satisfy (15).
A vector of squared length $2$ must be of the form $e_i-e_j$; then
$$ \sum u_j=0, \qquad \sum (j-1)u_j=i-j\ne0, $$
so (15) fails.
A vector of squared length $3$ has three nonzero coordinates $\pm1$; then $\sum u_j\ne0$, hence (15) fails.
Therefore no admissible vector has length $<2$, and the vector above has length exactly $2$. Thus
$$ \nu_6=2. $$
Hence the required accuracies are
$$ \boxed{\nu_2=\sqrt{,1+(a-2)^2,}}, \qquad \boxed{\nu_6=2}. $$
∎