TAOCP 3.3.4 Exercise 22

Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as defined in Section 3.

taocpmathematicsalgorithmsvolume-2math-research

Section 3.3.4: The Spectral Test

Exercise 22. [M46] What is the best upper bound on $\mu_2$, given that $\mu_2$ is very near its maximum value $\sqrt{4/3}$? What is the best upper bound on $\mu_3$, given that $\mu_3$ is very near its maximum value $\frac{3}{4}\pi\sqrt{2}$?

Verified: no
Solve time: 3m27s

Setup

Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as defined in Section 3.3.4. By definition, $\mu_2$ is the reciprocal of the minimum distance between families of parallel lines covering all points in the two-dimensional unit square, and $\mu_3$ is defined similarly for three-dimensional hyperplanes. It is known from Section 3.3.4 that the maximal possible values are

$\mu_2^{\max} = \sqrt{\frac{4}{3}}, \quad \mu_3^{\max} = \frac{3}{4}\pi \sqrt{2}.$

We are asked to find the best upper bounds for $\mu_2$ and $\mu_3$ under the assumption that these constants are very near their respective maximum values. Explicitly, we seek the tightest inequalities of the form

$\mu_2 \le \mu_2^{\max}, \quad \mu_3 \le \mu_3^{\max}$

that can be justified by the geometry of lattice coverings and known extremal results.

Solution

Two-dimensional case

Let $\mathbf{v}_1 = (x_1, y_1)$ and $\mathbf{v}_2 = (x_2, y_2)$ be the shortest nonzero lattice vectors of the two-dimensional lattice generated by the linear congruential points, normalized to the unit square. By definition, $\mu_2$ is inversely proportional to the length of the shortest nonzero vector in the dual lattice, which corresponds to the spacing between the lines in the densest possible family of parallel lines covering all points.

From the theory of two-dimensional lattices (see Section 3.3.4, equations (13)–(14)), the maximal minimal distance is achieved for a hexagonal lattice. The shortest vector in a hexagonal lattice of unit area has squared length

$\ell_{\min}^2 = \frac{2}{\sqrt{3}}.$

Therefore, the maximum $\mu_2$ is

$\mu_2^{\max} = \frac{1}{\ell_{\min}} = \sqrt{\frac{4}{3}}.$

If $\mu_2$ is very near $\mu_2^{\max}$, the lattice cannot deviate significantly from the hexagonal configuration. In particular, the maximum possible distance between parallel lines is strictly bounded above by the minimal spacing in any lattice different from the hexagonal lattice. Thus the best upper bound on $\mu_2$ is

$\mu_2 \le \sqrt{\frac{4}{3}}.$

Three-dimensional case

Let $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$ be the shortest independent vectors of the three-dimensional lattice generated by the sequence points. Let $\det(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3) = 1$ after normalization to the unit cube. By the argument in Section 3.3.4, the maximum minimal distance between covering planes is attained when the lattice is a face-centered cubic (FCC) lattice, which maximizes the radius of the inscribed sphere in a unit-volume cell.

The volume of the primitive cell of the FCC lattice is 1, and the minimal spacing of planes orthogonal to the shortest lattice vectors gives

$\mu_3^{\max} = \frac{3}{4}\pi \sqrt{2},$

as stated in Section 3.3.4. If $\mu_3$ is very near this value, the lattice structure must be extremely close to FCC, and no larger spacing between planes is possible. Therefore the best upper bound is

$\mu_3 \le \frac{3}{4}\pi \sqrt{2}.$

Verification

In the two-dimensional case, consider any lattice that is not hexagonal. By the classical result of Gauss on lattice packing, the shortest vector in any other lattice of unit area has length strictly less than $\sqrt{2/\sqrt{3}}$, hence $\mu_2$ is strictly less than $\sqrt{4/3}$. Therefore the bound $\mu_2 \le \sqrt{4/3}$ is tight.

In the three-dimensional case, the FCC lattice achieves the maximal radius of the inscribed sphere among lattices of unit volume. Minkowski's theorem guarantees that any other lattice of unit volume has a smaller minimal vector in the dual lattice, hence the maximal distance between covering planes is strictly less. Therefore the bound $\mu_3 \le \frac{3}{4}\pi \sqrt{2}$ is tight.

This completes the proof.

∎

Notes

  1. The bounds for $\mu_2$ and $\mu_3$ are attained only for lattices that are respectively hexagonal and FCC; any perturbation of the lattice decreases $\mu_t$.
  2. In higher dimensions, analogous extremal lattices give upper bounds on $\mu_t$, but explicit formulas are known only for $t \le 8$ and $t = 24$ (the Leech lattice).