# 23.1 Lattices

Let ${v}_{1}\text{,}\text{}\dots \text{,}\text{}{v}_{n}$ be linearly independent vectors in $n$-dimensional real space ${\mathbf{R}}^{n}$. This means that every $n$-dimensional real vector $v$ can be written in the form

with real numbers ${a}_{1}\text{,}\text{}\dots \text{,}\text{}{a}_{n}$ that are uniquely determined by $v$. The **lattice** generated by ${v}_{1}\text{,}\text{}\dots \text{,}\text{}{v}_{n}$ is the set of vectors of the form

where ${m}_{1}\text{,}\text{}\dots \text{,}\text{}{m}_{n}$ are integers. The set $\{{v}_{1}\text{,}\text{}\dots \text{,}\text{}{v}_{n}\}$ is called a **basis** of the lattice. A lattice has infinitely many possible bases. For example, suppose $\{{v}_{1}\text{,}\text{}{v}_{2}\}$ is a basis of a lattice. Let $k$ be an integer and let ${w}_{1}={v}_{1}+k{v}_{2}$ and ${w}_{2}={v}_{2}$. Then $\{{w}_{1}\text{,}\text{}{w}_{2}\}$ is also a basis of the lattice: Any vector of the form ${m}_{1}{v}_{1}+{m}_{2}{v}_{2}$ can be written as ${m}_{1}^{\prime}{w}_{1}+{m}_{2}^{\prime}{w}_{2}$ with ${{m}_{1}}^{\prime}={m}_{1}$ and ${m}_{2}^{\prime}={m}_{2}-k{m}_{1}$, and similarly any integer linear combination of ${w}_{1}$ and ${w}_{2}$ can be written as an integer linear combination of ${v}_{1}$ and ${v}_{2}$.

# Example

Let ${v}_{1}=(1\text{,}\text{}0)$ and ${v}_{2}=(0\text{,}\text{}1)$. The lattice generated by ${v}_{1}$ and ${v}_{2}$ is the set of all pairs $(x\text{,}\text{}y)$ with $x\text{,}\text{}y$ integers. Another basis for this lattice is $\{(1\text{,}\text{}5)\text{,}\text{}\phantom{\rule{thinmathspace}{0ex}}(0\text{,}\text{}1)\}$. A third basis is $\{(5\text{,}\text{}16)\text{,}\text{}\phantom{\rule{thinmathspace}{0ex}}(6\text{,}\text{}19)\}$. More generally, if $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$ is a matrix with determinant $\pm 1$, then $\{(a\text{,}\text{}b)\text{,}\text{}\phantom{\rule{thinmathspace}{0ex}}(c\text{,}\text{}d)\}$ is a basis of this lattice (Exercise 4).

The length of a vector $v=({x}_{1}\text{,}\text{}\dots \text{,}\text{}{x}_{n})$ is

Many problems can be related to finding a shortest nonzero vector in a lattice. In general, the **shortest vector problem** is hard to solve, especially when the dimension of the lattice is large. In the following section, we give some methods that work well in small dimensions.

# Example

A shortest vector in the lattice generated by

is $(3\text{,}\text{}-1)$ (another shortest vector is $(-3\text{,}\text{}1)$). How do we find this vector? This is the subject of the next section. For the moment, we verify that $(3\text{,}\text{}-1)$ is in the lattice by writing

In fact, $\{(3\text{,}\text{}-1)\text{,}\text{}\phantom{\rule{thinmathspace}{0ex}}(1\text{,}\text{}4)\}$ is a basis of the lattice. For most purposes, this latter basis is much easier to work with than the original basis since the two vectors $(3\text{,}\text{}-1)$ and $(1\text{,}\text{}4)$ are almost orthogonal (their dot product is $(3\text{,}\text{}-1)\cdot (1\text{,}\text{}4)=-1$, which is small). In contrast, the two vectors of the original basis are nearly parallel and have a very large dot product. The methods of the next section show how to replace a basis of a lattice with a new basis whose vectors are almost orthogonal.