Section 3.3.4: The Spectral Test

Exercise 2. [HM20] Let $V_1, \ldots, V_t$ be linearly independent vectors in $t$-space, let $L_0$ be the lattice of points defined by (10), and let $U_1, \ldots, U_t$ be defined by (19). Prove that the maximum distance between $(t-1)$-dimensional hyperplanes from among all parallel hyperplanes that cover $L_0$ is $1/\min{(x_1, \ldots, x_t)^{1/2} \mid (x_1, \ldots, x_t) \ne (0, \ldots, 0)}$, where $f$ is defined in (17).

Verified: yes
Solve time: 3m13s

---

Let $L_0\subset \mathbb{R}^t$ be the lattice generated by the linearly independent vectors $V_1,\ldots,V_t$, so every point of $L_0$ has the form

$$ L_0=\left{\sum_{i=1}^t n_i V_i ;:; n_i\in\mathbb{Z}\right}. $$

A family of parallel $(t-1)$-dimensional hyperplanes covering $L_0$ is determined by a nonzero linear functional whose level sets contain all lattice points in integer layers. This is naturally described using the dual lattice.

Step 1. Dual lattice formulation

Let $\langle \cdot,\cdot\rangle$ be the Euclidean inner product. The dual lattice of $L_0$ is

$$ L_0^*={u\in \mathbb{R}^t : \langle u, V_i\rangle \in \mathbb{Z}\ \text{for all } i=1,\ldots,t}. $$

For any nonzero $u\in L_0^*$, consider the family of hyperplanes

$$ H_k = {x\in \mathbb{R}^t : \langle u,x\rangle = k}, \quad k\in \mathbb{Z}. $$

Because $\langle u, V_i\rangle\in\mathbb{Z}$, every lattice point in $L_0$ lies in one of these hyperplanes, so the family covers $L_0$.

Step 2. Spacing between hyperplanes

Two adjacent hyperplanes

$$ \langle u,x\rangle = k \quad \text{and} \quad \langle u,x\rangle = k+1 $$

have Euclidean distance equal to

$$ \frac{1}{|u|}. $$

Indeed, the normal vector to the hyperplanes is $u$, and shifting by one unit in the functional value corresponds to a displacement of length $1/|u|$ in the normal direction.

Thus, for a given admissible $u\in L_0^*$, the spacing of the covering hyperplanes is $1/|u|$.

Step 3. Maximizing the spacing

To maximize the spacing, we minimize $|u|$ over all nonzero dual lattice vectors:

$$ d_{\max} = \max_{u\in L_0^\setminus{0}} \frac{1}{|u|} = \frac{1}{\min_{u\in L_0^\setminus{0}} |u|}. $$

Step 4. Coordinates in the dual basis and the quadratic form

Let $U_1,\ldots,U_t$ be the basis of the dual lattice defined in (19). Then every $u\in L_0^*$ has a unique representation

$$ u = \sum_{i=1}^t x_i U_i, \quad x_i\in \mathbb{Z}. $$

Define the quadratic form $f$ from (17) by

$$ f(x_1,\ldots,x_t) = \left|\sum_{i=1}^t x_i U_i\right|^2. $$

Then

$$ |u|^2 = f(x_1,\ldots,x_t). $$

Hence the minimum nonzero dual norm satisfies

$$ \min_{u\in L_0^*\setminus{0}} |u|

\min_{(x_1,\ldots,x_t)\neq (0,\ldots,0)} f(x_1,\ldots,x_t)^{1/2}. $$

Step 5. Final conclusion

Substituting into the expression for maximal spacing,

$$ d_{\max}

\frac{1}{\min{ f(x_1,\ldots,x_t)^{1/2} \mid (x_1,\ldots,x_t)\neq (0,\ldots,0)}}. $$

This is exactly the required result.