Lattices and Lattice Partitions

A lattice $\Lambda \subset \mathbb{R}^n$ is a discrete additive subgroup of $\mathbb{R}^n$ of rank $n$. Equivalently, there exist $n$ linearly independent vectors $\mathbf{g}_1, \ldots, \mathbf{g}_n \in \mathbb{R}^n$ such that

$$\Lambda \;=\; \Bigl\{ \textstyle\sum_{i=1}^n z_i \, \mathbf{g}_i \;:\; z_i \in \mathbb{Z} \Bigr\}.$$

Stacking the basis vectors as columns of a matrix $\mathbf{G} \in \mathbb{R}^{n \times n}$, we write $\Lambda = \{\mathbf{G}\mathbf{z} : \mathbf{z} \in \mathbb{Z}^n\}$ and call $\mathbf{G}$ a generator matrix of $\Lambda$. Different bases give different $\mathbf{G}$'s, all related by unimodular transformations (integer matrices with $|\det| = 1$).

A fundamental region of $\Lambda$ is any measurable set $\mathcal{F} \subset \mathbb{R}^n$ such that the translates $\{\mathcal{F} + \lambda : \lambda \in \Lambda\}$ tile $\mathbb{R}^n$ exactly (they cover it and overlap only on measure-zero sets). The fundamental parallelepiped $\mathcal{P}(\mathbf{G}) = \{\mathbf{G}\mathbf{u} : \mathbf{u} \in [0,1)^n\}$ is one canonical choice; the Voronoi region (below) is another. All fundamental regions have the same volume, which we call the fundamental volume of the lattice:

$$V(\Lambda) \;=\; |\det \mathbf{G}|.$$

The volume is independent of the basis because unimodular $\mathbf{G} \to \mathbf{G}\mathbf{U}$ preserves $|\det|$.

The Voronoi region $\mathcal{V}(\Lambda)$ of $\Lambda$ around the origin is the set of points of $\mathbb{R}^n$ closer to $\mathbf{0}$ than to any other lattice point:

$$\mathcal{V}(\Lambda) \;=\; \bigl\{\mathbf{x} \in \mathbb{R}^n : \|\mathbf{x}\| \le \|\mathbf{x} - \lambda\| \text{ for all } \lambda \in \Lambda \bigr\}.$$

The packing radius $r_{\rm pack}(\Lambda)$ is the largest $r$ such that the balls $B(\lambda, r)$ around distinct lattice points are disjoint; equivalently, $r_{\rm pack} = \tfrac12 \min_{\lambda \ne 0} \|\lambda\|$. The covering radius $r_{\rm cov}(\Lambda)$ is the smallest $r$ such that the balls $B(\lambda, r)$ cover all of $\mathbb{R}^n$; equivalently, $r_{\rm cov} = \max_{\mathbf{x}} \min_{\lambda} \|\mathbf{x} - \lambda\|$.

The kissing number $K(\Lambda)$ of a lattice is the number of minimum-norm vectors in $\Lambda \setminus \{\mathbf{0}\}$ — the number of "nearest neighbours" of the origin:

$$K(\Lambda) \;=\; \bigl| \{\lambda \in \Lambda : \|\lambda\| = d_{\min}\} \bigr|, \qquad d_{\min} = \min_{\lambda \ne 0} \|\lambda\|.$$

At high SNR, the pairwise union bound for ML decoding gives $P_e \approx K(\Lambda) Q\!\left(\tfrac{d_{\min}}{2 \sigma^2} \right)$, so $K(\Lambda)$ is the multiplicative pre-factor controlling the error floor once coding gain has set $d_{\min}$.

A lattice partition chain is a nested sequence

$$\Lambda_0 \;\supset\; \Lambda_1 \;\supset\; \Lambda_2 \;\supset\; \cdots \;\supset\; \Lambda_L,$$

where each $\Lambda_i$ is a sublattice of $\Lambda_{i-1}$. The chain has $L$ levels; the $i$-th level contributes the partition $\Lambda_{i-1} / \Lambda_i$ of index $|\Lambda_{i-1} / \Lambda_i|$. In the binary case each level is a two-way partition (index 2), and the total number of cosets of $\Lambda_L$ in $\Lambda_0$ is $2^L$ — exactly the number of bits we need to label a coset.