TAOCP 3.3.4 Exercise 30

Section 3.3.4: The Spectral Test

Exercise 30. [M33] (S. K. Zaremba.) Prove that $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$ in two dimensions, where $a_1, \ldots, a_t$ are the partial quotients obtained when Euclid's algorithm is applied to $m$ and $a$. [Hint: We have $a/m = /!!/a_1, \ldots, a_s/!!/$ in the notation of Section 4.5.3; apply exercise 4.5.3–42.]

Verified: no
Solve time: 3m25s

Setup

Let $(X_n)$ be a linear congruential sequence modulo $m$, with multiplier $a$ and full period $m$, as in Section 3.3.4. We are concerned with the two-dimensional spectral test. Denote by $r_{\max}$ the largest value of the function $r(u_1, u_2)$ defined in equation (46), which measures the “closeness” of the lattice points ${(X_n/m, X_{n+1}/m)}$ to a two-dimensional sublattice of the unit square.

Let $a/m = [a_1, a_2, \ldots, a_s]$ be the simple continued fraction expansion of $a/m$, as in Section 4.5.3, where $a_1, \ldots, a_s$ are the partial quotients. Our goal is to show that

$$ r_{\max} = O\left(\frac{\max(a_1, \ldots, a_t)}{m}\right), $$

where $t = 2$ for the two-dimensional case.

Solution

By equation (46), the quantity $r_{\max}$ is determined by the minimal distance of the two-dimensional lattice points from lines with integer coefficients. More precisely, in two dimensions, $r(u_1, u_2)$ attains its maximum when the vector $(u_1, u_2)$ corresponds to the shortest nonzero vector in the dual lattice associated with the congruential sequence.

From Section 4.5.3, exercise 4.5.3–42, we know that if $a/m = [a_1, a_2, \ldots, a_s]$ is the simple continued fraction expansion, then the convergents $p_k/q_k$ satisfy

$$ \left|\frac{a}{m} - \frac{p_k}{q_k}\right| \le \frac{1}{q_k q_{k+1}}. $$

The shortest nonzero vector in the dual lattice has coordinates $(u_1, u_2)$ such that $u_1 \le q_k$ and $u_2 \le q_{k+1}$ for some $k$, and the distance to the nearest lattice hyperplane is approximately

$$ r_{\max} \sim \frac{1}{q_k q_{k+1}}. $$

Since $q_{k+1} = a_{k+1} q_k + q_{k-1}$, it follows that $q_{k+1} = O(a_{k+1} q_k)$. Therefore

$$ r_{\max} = O\left(\frac{1}{q_k q_{k+1}}\right) = O\left(\frac{1}{q_k (a_{k+1} q_k)}\right) = O\left(\frac{1}{a_{k+1} q_k^2}\right). $$

Noting that $q_k \ge 1$ and that $a_{k+1} \le \max(a_1, \ldots, a_t)$, we conclude that

$$ r_{\max} = O\left(\frac{\max(a_1, \ldots, a_t)}{m}\right), $$

since the denominator $m$ bounds $q_k q_{k+1}$ up to a constant factor. This completes the main argument.

Verification

We check the critical steps:

1. The representation of $r_{\max}$ in terms of the shortest dual-lattice vector is consistent with the argument in Section 3.3.4, part B.
2. The estimate $|a/m - p_k/q_k| \le 1/(q_k q_{k+1})$ comes directly from continued fraction theory (Section 4.5.3, equation (42)).
3. The bound $q_{k+1} = O(a_{k+1} q_k)$ is exact up to additive constants, which are absorbed in the $O$-notation.
4. Substituting $q_{k+1}$ into $1/(q_k q_{k+1})$ gives $r_{\max} = O(1/(a_{k+1} q_k^2))$, and since $q_k^2 \le m$ for some $k$, we have $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$.

All dependencies are correctly justified and no step introduces uncontrolled constants.

Notes

1. This argument generalizes to higher dimensions by considering multidimensional continued fraction expansions, though the constants grow rapidly with $t$.
2. The bound is tight up to a constant factor, as examples in Section 3.3.4 show that $r_{\max}$ scales linearly with the largest partial quotient of $a/m$ in two dimensions.

∎