Maths in a minute: Lattices

Share this page
A lattice generated by basis vectors that aren't at right-angles to each other

Maths in a minute: Lattices

A lattice is essentially a regular grid of points generated by arrows.

Imagine a dot in the plane. Draw two arrows starting at that dot, which aren't parallel to each other. Now also draw the same two arrows, but facing in exactly the opposite direction from the first two. Draw a new dot at the tip of your four arrows.

Image
The beginning of a lattice: two arrows starting from the same point, together with the arrows in the opposite direction from that point.
 

Now draw the same four arrows for each of your new points. This gives you another generation of points at the tips of the new arrows.

Image
Building a lattice of points from copies of your original two arrows, and their opposites
 

Now do the same for all the new points, drawing four arrows each for the new generation of points. If you keep going like this, you eventually fill the whole plane with a grid, called a lattice. The pair of arrows which generated this lattice is called the basis of the lattice.

Image
A lattice of points and their basis vectors
A lattice is generated by its basis vectors, such as this one generated by the pair of purple vectors.

Mathematically, the arrows are called vectors. Every point in the lattice comes from an integer combination of the two basis vectors. For example, in the image below, the point P is given by v+w because you get to it by following one copy of v and then one copy of w, where v and w are the two basis vectors. The point Q is given by -v+2w because you get to it by following one copy of v but in the opposite direction (hence the minus) and then two copies of w.

Image
Two points in the lattice , P and Q, and how they are each generated by the basis vectors v and w
 

In our example, the lattice points define rectangles. That's because there's a right angle between the two basis vectors. But this doesn't have to be the case. Here is an example of a lattice that isn't:

Image
A lattice generated by basis vectors that aren't at right-angles to each other
 

(Technically, a lattice comes from integer combinations of vectors that together form a basis of the underlying vector space, see more here.)

Finally, note that the same lattice can have different bases. In the example below, two different pairs of arrows give you the same lattice.

Image
An example of two different bases that generate the same lattice
 

Then any point in your lattice can be generated by both basis pairs. In the example we saw above, you can get to the point P below by following one of the purple basis vectors by the other. But you can also get to the point P by starting with two copies of one of the red basis vectors, followed by three opposite copies of the other red basis vector.

Image
Generating the same point on a lattice using two different bases
 

You can also play the game of producing a lattice using vectors in three-dimensional space. And since mathematicians have a way of thinking about the 4th, 5th, 6th, or any higher dimension, they can define lattices and their bases in any dimension.

The basis reduction problem

There are many interesting problems to do with lattices. Here's one: given a lattice (in any dimension), can you find a basis whose vectors are as short as possible (see here for the precise meaning of this) and as close as possible to orthogonal to each other (that is, have right angles between the pairs of vectors)? (The purple basis in the image above is an example of this "good" or reduced basis for this example lattice.)

When we're looking at a lattice in a plane, as in our example, there's an efficient algorithm to solve this lattice reduction problem. But that's not the case when you look at higher-dimensional lattices. Such hard problems in high-dimensional lattices are the key to lattice-based cryptography,thought to be the best cryptography technique for keeping information safe in the advent of quantum computing.

You can find out more about lattice-based cryptography here and more details about research into lattices here.

This introduction is drawn from the article László Lovász: Working mathematical miracles about the work of László Lovász, the winner of the 2021 Abel Prize.


This article was produced as part of our collaborations with the Isaac Newton Institute for Mathematical Sciences (INI) and the Newton Gateway to Mathematics.

The INI is an international research centre and our neighbour here on the University of Cambridge's maths campus. The Newton Gateway is the impact initiative of the INI, which engages with users of mathematics. You can find all the content from the collaboration here.

 

Image
INI logo
 

 

Image
Gateway logo