What a Lattice Is

Here is the whole definition, and it is one word different from the previous note.

A lattice is the set of all linear combinations of a fixed set of vectors, where the coefficients are required to be integers.

That is it. Not real numbers. Integers.

01.What the restriction does

In Vectors and the Plane, letting $x_1$ and $x_2$ range over all real numbers with $b_1 = (3,1)$ and $b_2 = (1,2)$ produced the entire plane, every point of it, with no gaps.

Now require $x_1$ and $x_2$ to be whole numbers. You can take $b_1$ once, or twice, or minus three times. You cannot take it half a time.

The result is a set of isolated points. They go on forever in every direction, they are spread evenly, and between any two of them there is empty space. A grid rather than a surface.

That emptiness is where every hard problem in this chapter comes from. It is worth saying plainly, because it is easy to read past: a lattice is hard to work with precisely because you cannot take fractional steps. If you could, everything below would be schoolbook algebra.

The relationship is the same as the one between $\mathbb{R}$ and $\mathbb{Z}$ from Sets and Notation. The real line is continuous. The integers sitting inside it are a lattice in one dimension.

02.The simplest lattice

Take the standard basis $e_1 = (1,0)$ and $e_2 = (0,1)$, and allow only integer coefficients. The combinations $x_1 e_1 + x_2 e_2 = (x_1, x_2)$ give exactly the points with whole-number coordinates:

$$\mathbb{Z}^2 \;=\; \{\ldots, (-1,-1),\; (0,-1),\; (1,-1),\; (-1,0),\; (0,0),\; (1,0), \ldots\}.$$

This is graph paper. Every corner where two ruled lines cross is a point of $\mathbb{Z}^2$, and nothing in between is.

$\mathbb{Z}^n$ is the same idea in $n$ dimensions and is the standard against which other lattices are compared.

03.A skewed lattice, worked by hand

Now use the basis from the previous note, $b_1 = (3, 1)$ and $b_2 = (1, 2)$, with integer coefficients only. Every lattice point has the form

$$x_1 (3,1) + x_2 (1,2) \;=\; (3x_1 + x_2,\; x_1 + 2x_2), \qquad x_1, x_2 \in \mathbb{Z}.$$

Compute a few. Each line is one substitution and two small sums.

Check the fifth row by hand: $-1 \cdot (3,1) + 1 \cdot (1,2) = (-3,-1) + (1,2) = (-2, 1)$.

Plotted, these fill out an infinite grid that has been sheared. The cells are rhombuses rather than squares, but the pattern is perfectly regular and repeats forever.

The dashed parallelogram is the cell spanned by the two basis vectors. Copies of it, placed at every lattice point, tile the plane with no gaps and no overlaps. That observation becomes a measurement in Measuring a Lattice: Determinant and Minkowski's Theorem.

04.The general definition

Two dimensions was for drawing. The definition works in any number.

Let $b_1, b_2, \ldots, b_n$ be $n$ linearly independent vectors in $\mathbb{R}^m$. The lattice they generate is

$$\mathcal{L}(b_1, \ldots, b_n) \;=\; \{\, x_1 b_1 + x_2 b_2 + \cdots + x_n b_n \;:\; x_1, \ldots, x_n \in \mathbb{Z} \,\}.$$

It is usually more convenient to pack the basis vectors as the columns of a matrix. Writing

$$B \;=\; \begin{pmatrix} 3 & 1 \\ 1 & 2 \end{pmatrix}$$

for the running example, the lattice is

$$\mathcal{L}(B) \;=\; B\,\mathbb{Z}^n \;=\; \{\, B\mathbf{x} \;:\; \mathbf{x} \in \mathbb{Z}^n \,\},$$

which reads as "take every integer vector $\mathbf{x}$ and multiply it by $B$". The matrix form is what an implementation actually uses.

Two words of vocabulary. The number of basis vectors $n$ is the rank. The dimension $m$ of the space they live in is the embedding dimension. When $n = m$ the lattice is full-rank, meaning it is spread through the whole space rather than confined to a lower-dimensional slice inside it. Essentially every lattice in cryptography is full-rank, including the running example, where $n = m = 2$.

For scale: the lattices inside ML-KEM have rank $256$ per polynomial, with two, three or four polynomials stacked depending on the parameter set. So the real object is a full-rank lattice in $512$, $768$ or $1024$ dimensions. Everything on this page is still true of it. You just cannot draw it.

The next note takes this one lattice and describes it two different ways, and the difference between those two descriptions is where the cryptography comes from.