What is a lattice?

Chapter 4 ended with a set of linearly independent vectors and every point you could reach from them. If the coefficients are allowed to be any real numbers, those vectors reach every point in the space they span. Nothing is left out, and there are no gaps.

A lattice comes from making one change to that setup: the coefficients have to be integers. You can take three copies of a vector, or minus one copy, but not half a copy. That single restriction turns a continuous space into a set of separated points.

By the end of this chapter, you should understand what a lattice is, how a basis generates one, how to read $L(B) = \{Bz : z \in \mathbb{Z}^n\}$, and why the basis vectors have to be linearly independent.

The integer grid#

The simplest lattice is the one you have already drawn on graph paper: the points whose coordinates are whole numbers.

$$\mathbb{Z}^2 = \{(x, y) : x, y \in \mathbb{Z}\}$$

Read $\mathbb{Z}$ as "the integers", so $\ldots, -2, -1, 0, 1, 2, \ldots$ including the negatives and zero. Read the superscript as the number of coordinates, so $\mathbb{Z}^2$ is pairs of integers and $\mathbb{Z}^3$ is triples. Read the whole line as "the set of all pairs $(x, y)$ where both $x$ and $y$ are integers".

Points like $(0,0)$, $(3,2)$ and $(-4,7)$ are in $\mathbb{Z}^2$. Points like $(0.5, 1)$ are not.

That picture is a lattice, but the dots are not what defines it. What defines a lattice is how the points are generated.

Integer combinations of basis vectors#

Take the two vectors drawn in the diagram:

$$b_1 = (1, 0), \quad b_2 = (0, 1)$$

A linear combination of these is $z_1 b_1 + z_2 b_2$, exactly as in chapter 4. The new rule is that $z_1$ and $z_2$ must be integers. We call this an integer combination.

Two examples:

$$3 b_1 + 2 b_2 = 3(1,0) + 2(0,1) = (3,0) + (0,2) = (3,2)$$ $$-1 b_1 + 4 b_2 = -1(1,0) + 4(0,1) = (-1,0) + (0,4) = (-1,4)$$

The coefficients say how many copies of each basis vector to use, and a negative coefficient means the vector is used in the opposite direction. Every pair of integers $z_1, z_2$ gives a point of $\mathbb{Z}^2$, and every point of $\mathbb{Z}^2$ comes from exactly one such pair. So the two vectors $b_1$ and $b_2$ generate the whole infinite grid.

The point set is infinite, but the description is two vectors.

Integers are the whole difference#

Drop the word "integer" and the object changes completely. With real coefficients you can pick $0.5$ and $0.25$:

$$0.5 b_1 + 0.25 b_2 = (0.5, 0.25)$$

That point sits inside one of the squares of the grid rather than on a corner of it. Keep going with other fractions and you fill in every square, which gives the whole plane rather than a set of dots.

$$\text{integer coefficients} \rightarrow \text{separated points}$$ $$\text{real coefficients} \rightarrow \text{the whole plane}$$

The gaps are the useful part. Because the points are separated, questions like "which lattice point is nearest to this target?" have a definite answer, and answering them can be hard. In a continuous space the answer is always the target itself, and there is no problem to solve.

A lattice that is not the integer grid#

Lattices do not have to be square, and their points do not have to be all the whole-number coordinates. Take a different pair of basis vectors:

$$b_1 = (2, 0), \quad b_2 = (1, 1)$$

Then work out a few integer combinations:

$$0 b_1 + 0 b_2 = (0,0)$$ $$1 b_1 + 0 b_2 = (2,0)$$ $$1 b_1 + 1 b_2 = (2,0) + (1,1) = (3,1)$$ $$2 b_1 + 3 b_2 = (4,0) + (3,3) = (7,3)$$

The general point here is $z_1(2,0) + z_2(1,1) = (2z_1 + z_2,\; z_2)$. The first coordinate minus the second is $2z_1$, which is always even, so this lattice contains exactly the whole-number points whose two coordinates are both even or both odd. The point $(3,1)$ is in it and $(3,2)$ is not.

So this is a different lattice from $\mathbb{Z}^2$, sitting inside it, generated by a different basis. Both are lattices for the same reason: each is the full set of integer combinations of two independent vectors.

Lattice points can be added and subtracted#

One property follows straight from the definition and gets used constantly later. If $u$ and $v$ are both lattice points, then $u + v$ and $u - v$ are lattice points too.

The reason is that adding two integer combinations just adds their coefficients, and integers are closed under addition and subtraction. In the slanted lattice above, $(2,0)$ and $(3,1)$ are lattice points, and so are $(5,1)$ and $(-1,-1)$. The origin is always a lattice point, obtained by taking every coefficient to be zero.

This is what makes a lattice a repeating pattern rather than an arbitrary scatter of dots. The view from any lattice point looks the same as the view from the origin, because you can shift the whole lattice by any lattice point and land back on itself.

The definition in $n$ dimensions#

Nothing above depended on there being two dimensions. In $n$ dimensions we start from $n$ basis vectors $b_1, b_2, \ldots, b_n$, and a lattice point is any integer combination of them:

$$z_1 b_1 + z_2 b_2 + \cdots + z_n b_n$$

Written as a set, the lattice $L$ generated by those vectors is:

$$L = \left\{ \sum_{i=1}^{n} z_i b_i \;:\; z_i \in \mathbb{Z} \right\}$$

Read $\sum_{i=1}^{n} z_i b_i$ as "add up $z_1 b_1$ through to $z_n b_n$", and read $z_i \in \mathbb{Z}$ as "each coefficient $z_i$ is an integer". The braces and the colon are the same set notation used for $\mathbb{Z}^2$ above. The part before the colon says what is in the set, and the part after it gives the condition on the coefficients.

The same definition as a matrix#

Chapter 3 showed that $Bz$ is a linear combination of the columns of $B$ with coefficients from $z$. That is exactly the sum above, so the whole definition collapses into one matrix product.

Put the basis vectors in as columns:

$$B = [\, b_1 \mid b_2 \mid \cdots \mid b_n \,]$$

The vertical bars are only there to show the vectors sit side by side as columns. Stack the coefficients into a vector $z = (z_1, z_2, \ldots, z_n)$, and then:

$$Bz = z_1 b_1 + z_2 b_2 + \cdots + z_n b_n$$

So the lattice generated by $B$ is written:

$$L(B) = \{ Bz : z \in \mathbb{Z}^n \}$$

Read this as "$L(B)$ is the set of every point $Bz$, as $z$ runs over all integer vectors with $n$ entries". In code it is an ordinary matrix-vector product, with the single restriction that the vector being multiplied has integer entries.

Take care with the two decorations on $\mathbb{Z}$. A superscript counts coordinates, so $\mathbb{Z}^n$ is integer vectors of length $n$. A subscript is the modulus from chapter 6, so $\mathbb{Z}_q$ is the integers modulo $q$. They are unrelated, and both appear once we reach q-ary lattices.

The basis vectors must be independent#

The basis has to be linearly independent, for the reason chapter 4 gave. Take a pair that is not:

$$b_1 = (1, 0), \quad b_2 = (2, 0)$$

Every integer combination of these is:

$$z_1(1,0) + z_2(2,0) = (z_1 + 2 z_2,\; 0)$$

The second coordinate is always zero, so every point lands on the x-axis. The result is still a set of separated points, but it is a one-dimensional lattice sitting inside two-dimensional space, not a grid filling the plane. From chapter 5, the matrix with these columns has determinant $1 \cdot 0 - 0 \cdot 2 = 0$, which is the algebraic version of the same failure.

When this course says an $n$-dimensional lattice, it means one generated by $n$ independent vectors in $n$-dimensional space, so $\det B \neq 0$. That is called a full-rank lattice, and it is the only case we will need.

Notation#

Symbol	Meaning	Example
$\mathbb{Z}$	The integers	$\ldots, -2, -1, 0, 1, 2, \ldots$
$\mathbb{Z}^n$	Integer vectors with $n$ entries	$(3, 2) \in \mathbb{Z}^2$
$b_i$	A basis vector	$b_1 = (1, 0)$
$z$	A vector of integer coefficients	$z = (3, 2)$
$B$	The matrix whose columns are the basis vectors	$B = [\, b_1 \mid b_2 \,]$
$L(B)$	The lattice generated by $B$	every $Bz$ with $z \in \mathbb{Z}^n$

What to remember#

• A lattice is the set of all integer combinations of a set of linearly independent vectors.
• In $n$ dimensions, $L(B) = \{Bz : z \in \mathbb{Z}^n\}$, where the columns of $B$ are the basis vectors.
• Integer coefficients are what make the points separated. Real coefficients would fill the space the vectors span.
• Sums and differences of lattice points are lattice points, and the origin is always a lattice point.
• A basis is a finite description of an infinite set of points.
• A basis must be linearly independent, equivalently $\det B \neq 0$. Otherwise the lattice collapses into fewer dimensions.

Checkpoint questions#

1. What does $\mathbb{Z}^2$ mean, and which of $(2,5)$ and $(2, 0.5)$ is in it?
2. What is $3b_1 + 2b_2$ when $b_1 = (2,0)$ and $b_2 = (1,1)$?
3. Why do integer coefficients give separated points while real coefficients do not?
4. How would you read $L(B) = \{Bz : z \in \mathbb{Z}^n\}$ out loud?
5. If $u$ and $v$ are lattice points, why is $u - v$ also a lattice point?
6. What goes wrong if the basis vectors are linearly dependent?
7. What is the difference between $\mathbb{Z}^n$ and $\mathbb{Z}_q$?