TAOCP 3.3.4 Exercise 1

When $t = 1$, the spectral test considers the set of points $\left\{\frac{1}{m} x \;\Big|\; 0 \le x < m\right\}$ in one-dimensional space, which is simply the set of equally spaced multiples of $1/m$...

Section 3.3.4: The Spectral Test

Exercise 1. [M10] What does the spectral test reduce in one dimension? (In other words, what happens when $t = 1$?)

Verified: yes
Solve time: 1m13s


When $t = 1$, the spectral test considers the set of points

$\left{\frac{1}{m} x ;\Big|; 0 \le x < m\right}$

in one-dimensional space, which is simply the set of equally spaced multiples of $1/m$ between 0 and 1. The problem of covering these points by $(t-1)$-dimensional hyperplanes reduces to covering them by points, since a $(1-1)$-dimensional hyperplane is a point in one dimension.

The maximum distance between such points is the spacing $1/m$ itself. Therefore, the one-dimensional accuracy $\nu_1$ is the reciprocal of this spacing, giving $\nu_1 = m$. This is the best possible value, since no larger spacing can cover all $m$ points.

This completes the proof.

$\boxed{\nu_1 = m}$_