Ferkans — Interactive Telecom Tutor

From QAM to Lattices: Why the Abstraction Pays Off

Every coded-modulation scheme we have built so far lives on a lattice, whether we acknowledged it or not. A 16-QAM constellation is a $4 \times 4$ patch of $\mathbb{Z}^2$ . A cross-32 constellation is a slightly cleverer patch of $\mathbb{Z}^2$ . The 8-PSK constellation is a single orbit of a rotated lattice. Even continuous-phase modulation, viewed through the Laurent representation, walks around a lattice. The point is this: lattices are the natural abstraction of modulation. Every QAM constellation is a finite piece of $\mathbb{Z}^2$ ; every turbo-coded bit stream carried over integer symbols lives on a lattice; the modulo-lattice reductions at the heart of dirty-paper coding and LAST codes are defined against lattices.

Understanding the general theory — what lattices exist, how dense they can be, how we count lattice points of a given norm — tells us what is and isn't achievable for modulation and coding together. In particular, the lattice gives us the raw coding-gain budget; whether we can reach it with a practical decoder is a separate question, and is where later chapters will focus.

This chapter sets up the theory as cleanly as Conway and Sloane's Sphere Packings, Lattices and Groups does. Ch. 16 will then use it to build lattice codes that achieve the AWGN capacity $\tfrac12 \log_2(1 + \text{SNR})$ , and Ch. 17 will nest two lattices to get the DMT-optimal LAST construction for MIMO fading. The single abstraction pays off three chapters in a row.

,

Definition:
Lattice

A lattice $\Lambda \subset \mathbb{R}^n$ is a discrete additive subgroup of $\mathbb{R}^n$ of rank $n$ . Explicitly, $\Lambda$ is closed under addition and under negation, contains the origin $\mathbf{0}$ , has no accumulation points, and spans $\mathbb{R}^n$ as a real vector space.

Equivalently (the constructive definition), there exist $n$ linearly independent vectors $\mathbf{b}_1, \ldots, \mathbf{b}_n \in \mathbb{R}^n$ — a basis of $\Lambda$ — such that $\Lambda \;=\; \Bigl\{\, {\textstyle \sum_{i=1}^n} u_i \mathbf{b}_i \;:\; u_1, \ldots, u_n \in \mathbb{Z} \,\Bigr\}.$ Stacking the basis vectors as columns of $\mathbf{G} \in \mathbb{R}^{n \times n}$ , we write $\Lambda = \{\mathbf{G} \mathbf{u} : \mathbf{u} \in \mathbb{Z}^n\}$ and call $\mathbf{G}$ a generator matrix of $\Lambda$ .

"Discrete additive subgroup of full rank" is the definition; the constructive form (integer combinations of $n$ linearly independent vectors) is a theorem one proves from it. Both definitions are widely used in the literature, and the equivalence is exactly what makes lattices such clean algebraic objects.

,

Definition:
Generator Matrix and Gram Matrix

The generator matrix $\mathbf{G} \in \mathbb{R}^{n \times n}$ of $\Lambda$ has the basis vectors as columns. Different bases give different $\mathbf{G}$ 's; any two generator matrices $\mathbf{G}_1, \mathbf{G}_2$ of the same lattice are related by a unimodular transformation $\mathbf{G}_2 = \mathbf{G}_1 \mathbf{U}$ with $\mathbf{U} \in \mathrm{GL}_n(\mathbb{Z})$ (i.e., $\mathbf{U}$ integer and $|\det \mathbf{U}| = 1$ ).

The Gram matrix of the basis is $\mathbf{A} \;=\; \mathbf{G}^T \mathbf{G}, \qquad A_{ij} = \langle \mathbf{b}_i, \mathbf{b}_j \rangle.$ Unlike $\mathbf{G}$ (which depends on the embedding of $\Lambda$ in $\mathbb{R}^n$ including rotation), the Gram matrix is unique up to unimodular congruence $\mathbf{A} \to \mathbf{U}^T \mathbf{A} \mathbf{U}$ and determines $\Lambda$ up to an isometry.

In practice, lattices are often specified by a Gram matrix only, because the precise embedding in $\mathbb{R}^n$ does not affect packing, covering, or any other isometry invariant. The Conway–Sloane catalog lists Gram matrices rather than generator matrices for this reason.

Theorem: Basis Invariance of the Fundamental Volume

For any lattice $\Lambda \subset \mathbb{R}^n$ with generator matrix $\mathbf{G}$ , the quantities $|\det \mathbf{G}|$ and $\det(\mathbf{G}^T \mathbf{G})$ are independent of the choice of basis. We may therefore define the fundamental volume $V(\Lambda) = |\det \mathbf{G}|$ unambiguously, and the identity $V(\Lambda)^2 \;=\; \det(\mathbf{G}^T \mathbf{G}) \;=\; \det \mathbf{A}$ holds for the Gram matrix $\mathbf{A}$ .

Changing basis is just a relabeling of lattice points. The total "real estate" each point occupies — the volume of a fundamental region — is a property of the lattice itself, not of which basis we happen to draw on a chalkboard.

Show Hint

Write the change of basis as $\mathbf{G}_2 = \mathbf{G}_1 \mathbf{U}$ with $\mathbf{U}$ unimodular and use multiplicativity of the determinant.

For the Gram-matrix identity, expand $\mathbf{G}_2^T \mathbf{G}_2 = \mathbf{U}^T \mathbf{G}_1^T \mathbf{G}_1 \mathbf{U}$ and use $|\det \mathbf{U}|^2 = 1$ .

Proof

Change of basis is unimodular

Let $\mathbf{G}_1, \mathbf{G}_2$ be two generator matrices of the same lattice $\Lambda$ . Each column of $\mathbf{G}_2$ is a lattice point of $\Lambda$ , so is an integer combination of columns of $\mathbf{G}_1$ : there is an integer matrix $\mathbf{U}$ with $\mathbf{G}_2 = \mathbf{G}_1 \mathbf{U}$ . By symmetry there is also $\mathbf{V}$ with $\mathbf{G}_1 = \mathbf{G}_2 \mathbf{V}$ . Substituting, $\mathbf{G}_1 = \mathbf{G}_1 \mathbf{U} \mathbf{V}$ , and because $\mathbf{G}_1$ has full rank, $\mathbf{U} \mathbf{V} = \mathbf{I}$ . Hence $\mathbf{U}, \mathbf{V}$ are integer matrices with integer inverses — i.e., unimodular, $|\det \mathbf{U}| = 1$ .

Determinant invariance

$|\det \mathbf{G}_2| = |\det \mathbf{G}_1| \cdot |\det \mathbf{U}| = |\det \mathbf{G}_1|$ . So the absolute determinant is a basis invariant of $\Lambda$ , and we may define $V(\Lambda) = |\det \mathbf{G}|$ unambiguously for any basis.

Gram-matrix identity

Consider the Gram matrix $\mathbf{A} = \mathbf{G}^T \mathbf{G}$ . Then $\det \mathbf{A} = \det(\mathbf{G}^T) \det(\mathbf{G}) = (\det \mathbf{G})^2 = V(\Lambda)^2$ . Under a change of basis, $\mathbf{A} \to \mathbf{U}^T \mathbf{A} \mathbf{U}$ and $\det \mathbf{A}$ picks up a factor $(\det \mathbf{U})^2 = 1$ , so it is also a basis invariant. $\blacksquare$

,

Definition:
Dual Lattice

The dual lattice of $\Lambda \subset \mathbb{R}^n$ is $\Lambda^* \;=\; \{\,\mathbf{y} \in \mathbb{R}^n : \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z} \text{ for all } \mathbf{x} \in \Lambda \,\}.$ If $\Lambda$ has generator matrix $\mathbf{G}$ , then $\Lambda^*$ has generator matrix $\mathbf{G}^{-T} = (\mathbf{G}^T)^{-1}$ . Consequently $V(\Lambda^*) = 1 / V(\Lambda)$ and $(\Lambda^*)^* = \Lambda$ .

A lattice is self-dual (or unimodular) if $\Lambda^* = \Lambda$ . Self-dual lattices have $V(\Lambda) = 1$ . The exceptional lattices $\mathbb{Z}^n$ , $E_8$ , and $\Lambda_{24}$ are all self-dual; $D_n$ and $A_n$ are generally not.

Duality is the lattice analogue of Pontryagin duality for abelian groups: $\Lambda$ labels "frequencies" that pair integrally with the "positions" in $\Lambda^*$ . For self-dual lattices, the Poisson summation formula reduces to a functional equation of the theta series — the starting point of Viazovska's $E_8$ proof.

,

2D Lattice Visualization with Voronoi Region

Three classical 2D lattices: the integer lattice $\mathbb{Z}^2$ , the hexagonal $A_2$ (densest 2D packing, proven by Thue in 1890), and the checkerboard $D_2$ (which turns out to equal $\mathbb{Z}^2$ up to rotation by 45°). The plot shows lattice points, one Voronoi cell outlined, and circles of radius $\rho$ (packing radius, inscribed in the Voronoi cell) around each point. Changing the lattice lets you see how the same region of the plane holds more or fewer points depending on the geometry.

Parameters

Lattice

Example: Generator Matrices for $\mathbb{Z}^2$ and $A_2$

Write down generator matrices $\mathbf{G}$ and Gram matrices $\mathbf{A} = \mathbf{G}^T \mathbf{G}$ for (a) the integer lattice $\mathbb{Z}^2$ and (b) the hexagonal lattice $A_2$ , whose minimum vectors are $(1, 0)$ and $(1/2, \sqrt{3}/2)$ . Verify that $V(\mathbb{Z}^2) = 1$ and $V(A_2) = \sqrt{3}/2 \approx 0.866$ .

Solution

Part (a): $\mathbb{Z}^2$

The standard basis is $\mathbf{b}_1 = (1, 0)$ , $\mathbf{b}_2 = (0, 1)$ . Thus $\mathbf{G} = \mathbf{I}_2$ and $\mathbf{A} = \mathbf{I}_2$ . We have $V(\mathbb{Z}^2) = |\det \mathbf{I}| = 1$ .

Part (b): $A_2$ generator matrix

The hexagonal lattice has basis $\mathbf{b}_1 = (1, 0)$ , $\mathbf{b}_2 = (1/2, \sqrt{3}/2)$ . Stacking as columns, $\mathbf{G}_{A_2} = \begin{pmatrix} 1 & 1/2 \\ 0 & \sqrt{3}/2 \end{pmatrix}, \qquad V(A_2) = |\det \mathbf{G}_{A_2}| = \frac{\sqrt{3}}{2}.$

Part (b): Gram matrix

$\mathbf{A}_{A_2} = \mathbf{G}^T \mathbf{G} = \begin{pmatrix} 1 & 1/2 \\ 1/2 & 1 \end{pmatrix}$ , with $\det \mathbf{A} = 3/4 = V(A_2)^2$ , confirming the identity of the theorem. The off-diagonal $1/2 = \cos 60°$ encodes the $60°$ angle between basis vectors — the hallmark of the hexagonal geometry.

Density comparison

$A_2$ has the same minimum distance $d_{\min} = 1$ as $\mathbb{Z}^2$ but fills a smaller fundamental volume ( $\sqrt{3}/2$ vs $1$ ). In the packing-density language of s02, $\Delta(A_2) = (\pi/4) / (\sqrt{3}/2) \approx 0.9069$ vs $\Delta(\mathbb{Z}^2) = \pi/4 \approx 0.7854$ , a $\sqrt{4/3} \approx 0.625$ dB gain. This is the asymptotic coding gain of hexagonal over square QAM, familiar from the TCM discussion of Ch. 2. $\blacksquare$

Common Mistake: The Generator Matrix Is Not Unique

Mistake:

Treating "the generator matrix" of a lattice as a unique object. In fact, any lattice has infinitely many generator matrices, all related by unimodular transformations $\mathbf{G} \to \mathbf{G} \mathbf{U}$ with $\mathbf{U}$ integer and $|\det \mathbf{U}| = 1$ . Two matrices that look different can describe the same lattice.

Correction:

Always work with invariants: fundamental volume $V(\Lambda)$ , minimum distance $d_{\min}$ , kissing number $K(\Lambda)$ , or the whole theta series $\Theta_\Lambda(q)$ . When you need to compare lattices in a numerical computation, first reduce $\mathbf{G}$ to a canonical form using the LLL algorithm, which returns a nearly-orthogonal basis (and is cheap in low dimension).

Historical Note: Gauss (1831): Binary Quadratic Forms and the Birth of Lattice Theory

1831

Lattice theory in the modern sense begins with Gauss's 1831 review of Ludwig Seeber's book on ternary quadratic forms. Gauss pointed out that a positive-definite binary quadratic form $f(x, y) = a x^2 + 2 b x y + c y^2$ with $a c - b^2 > 0$ is nothing other than the squared norm $\|\mathbf{G} \mathbf{u}\|^2$ of integer combinations $\mathbf{u} = (x, y)^T$ of a basis of $\mathbb{R}^2$ . The quadratic form and the lattice are two descriptions of the same object; the determinant $a c - b^2$ of the form is the squared fundamental volume $V(\Lambda)^2$ of the lattice.

Gauss then showed — in three paragraphs that are the first proof in lattice theory — that the hexagonal form $f(x, y) = x^2 + x y + y^2$ achieves the largest minimum among all forms of a given determinant. In modern terms, he proved that the hexagonal lattice $A_2$ is the densest 2D lattice packing, $80$ years before Thue's proof for general (non-lattice) packings. This single observation anticipated, in two dimensions, the entire lattice-density program that Viazovska would close in dimensions $8$ and $24$ in $2017$ .

Lattice

A discrete additive subgroup of $\mathbb{R}^n$ of full rank $n$ ; equivalently, the set of integer combinations of $n$ linearly independent vectors (the basis, or columns of the generator matrix $\mathbf{G}$ ).

Generator matrix

An $n \times n$ matrix $\mathbf{G}$ whose columns form a basis of a lattice $\Lambda$ : $\Lambda = \{\mathbf{G} \mathbf{u} : \mathbf{u} \in \mathbb{Z}^n\}$ . Two generator matrices of the same lattice differ by a unimodular multiplier.

Gram matrix

The symmetric positive-definite matrix $\mathbf{A} = \mathbf{G}^T \mathbf{G}$ of inner products between basis vectors. Invariant up to unimodular congruence; determines the lattice up to isometry.

Dual lattice

The lattice $\Lambda^* = \{\mathbf{y} \in \mathbb{R}^n : \langle \mathbf{x}, \mathbf{y} \rangle \in \mathbb{Z} \; \forall \mathbf{x} \in \Lambda\}$ . Has generator matrix $\mathbf{G}^{-T}$ and volume $V(\Lambda^*) = 1 / V(\Lambda)$ .

Related: Lattice, Self Dual, Theta Series

Quick Check

Let $\mathbf{G}$ be a generator matrix of a lattice $\Lambda$ , and let $\mathbf{U}$ be an integer matrix with $\det \mathbf{U} = 3$ . Which statements about $\mathbf{G} \mathbf{U}$ are true?

$\mathbf{G}\mathbf{U}$ is also a generator matrix of $\Lambda$ .

$\mathbf{G}\mathbf{U}$ generates a sublattice of $\Lambda$ of index $3$ .

$\mathbf{G}\mathbf{U}$ generates a sublattice only if $\mathbf{U}$ is also symmetric.

$\mathbf{G}\mathbf{U}$ generates a superlattice of $\Lambda$ .

Correction:

\mathbf{G}\mathbf{U}

generates a sublattice of

\Lambda

of index

3

.

Correct. Any integer matrix $\mathbf{U}$ with $|\det \mathbf{U}| = k$ sends a basis of $\Lambda$ to a basis of a sublattice $\Lambda' \subset \Lambda$ of index $|\Lambda / \Lambda'| = k$ . Only $|\det \mathbf{U}| = 1$ preserves the lattice — that's the definition of unimodular.

Key Takeaway

A lattice is the integer span of $n$ linearly independent vectors — no more, no less. All of its structure is encoded in the generator matrix $\mathbf{G}$ (up to unimodular change of basis) or equivalently the Gram matrix $\mathbf{A} = \mathbf{G}^T \mathbf{G}$ (which adds a further isometry equivalence). The fundamental volume $V(\Lambda) = |\det \mathbf{G}|$ and the dual lattice $\Lambda^* = (\mathbf{G}^{-T}) \mathbb{Z}^n$ are the two scalar quantities that the rest of the chapter will use to compare lattices at a glance.

Lattice Definitions and Generator Matrices

From QAM to Lattices: Why the Abstraction Pays Off

Definition: Lattice

Definition: Generator Matrix and Gram Matrix

Theorem: Basis Invariance of the Fundamental Volume

Change of basis is unimodular

Determinant invariance

Gram-matrix identity

Definition: Dual Lattice

2D Lattice Visualization with Voronoi Region

Parameters

Example: Generator Matrices for Z2\mathbb{Z}^2Z2 and A2A_2A2​

Part (a): $\mathbb{Z}^2$

Part (b): $A_2$ generator matrix

Part (b): Gram matrix

Density comparison

Common Mistake: The Generator Matrix Is Not Unique

Historical Note: Gauss (1831): Binary Quadratic Forms and the Birth of Lattice Theory

Lattice

Generator matrix

Gram matrix

Dual lattice

Quick Check

Key Takeaway

Definition:
Lattice

Definition:
Generator Matrix and Gram Matrix

Definition:
Dual Lattice

Example: Generator Matrices for $\mathbb{Z}^2$ and $A_2$