A wild lattice appears

A couple of years ago I began doing some research in a new mathematical area (at least new for me) and suddenly lattices began to appear everywhere. The thing that makes these lattices interesting is how they are connected to other mathematical areas. These type of connections, which appear time and time again in mathematics is what makes it so beautiful. As I advance more and more in my studies, I decided that it is time to write some of it down for other people to learn and enjoy.

This series of posts will show how these lattices are connected to several mathematical areas that I find very interesting, with emphasize on number theory and Diophantine approximation. At least for the first posts in the series, I will keep the math as simple as possible so it would be accessible to any student with basic mathematical knowledge (some linear algebra and a little bit of group and ring theory). Hopefully, by the time I will get to write the more advanced material, you will be interested enough in order to fill in the details.

In this post we will see the most basic definitions and results about lattices which we will need for the rest of this series of posts.

The first thing we need to know is that lattices are certain subsets of \mathbb{R}^n which have some nice algebraic and analytic properties. Before giving the formal definition, let us consider several “real world realizations” of lattices, so we can be sure that these are not just some mathematician’s figments of the imagination.

The first example above is the honeycomb created by the bees which, as you can see, is very symmetrical – there are many direction in which we can move it an it would still look the same (assuming of course that it is an infinite honeycomb, which as we all know, most of the honeycombs in the world are infinite). The red dots on the image on the left are these translations that the honeycomb is invariant under.

The second lattice is the chess playing board, which we can move it up, down, left or right and still see the same board if we ignore the colors (again, assuming it is infinite). If we don’t ignore the colors, then we can still move two squares up, down, left or right, or we can move 1 square left+1 square up and still see the same board. The respective lattices for invariance with and without colors are the top and bottom images on the left.

The next lattice is from a wall in Alhambra which is a citadel in Granada, Spain. It is a bit less symmetrical than the hexagonal and square lattices, but still has many symmetries (and if we can believe wikipedia, it inspired M.C. Escher!).

cannon-balls-187243_1280

Cannonball Stacking

Finally, the last lattice is in three dimensions and shows us how to properly stack cannonballs which is very important.

We have come to the point that we need to give some definitions to try to capture these phenomena.

Definition: A set L \subseteq \mathbb{R}^n is called a lattice if it is spanned over \mathbb{Z} by a basis for  \mathbb{R}^n, i.e. there is a basis \{v_1,...,v_n\} for  \mathbb{R}^n such that L=span_{\mathbb{Z}}(v_1,...,v_n):=\{ \sum a_i v_i\ \mid\ a_i\in \mathbb{Z}\}.

Examples:

  1. The square lattice is spanned by e_1=(1,0), e_2=(0,1) inside \mathbb{R}^2.
  2. More generally, the set \mathbb{Z}^n is a lattice in \mathbb{R}^n which is generated as a lattice by the standard basis e_1 ,..., e_n.
  3. The triangles (or hexagonal) lattice of the bees above is spanned by e_1=(1,0) and (\frac{1}{2},\frac{\sqrt{3}}{2}).

Notation: Let v_1,...,v_n be a basis for  \mathbb{R}^n which span the lattice L and set g=[v_1 \mid v_2 \mid \cdots \mid v_n] to be the matrix with v_i as its columns. Then we will sometimes write the lattice as

L:=g\mathbb{Z}^n=\{gu\ \mid\ u\in \mathbb{Z}^n\},

which is exactly all the linear combinations with integer coefficients of the columns of g.

We next turn to study some properties of lattices.

The algebraic property: The first property says that L is a group, i.e. it contains the origin and if u,v\in L, then u-v \in L, and its proof follows immediately from the definition of a lattice. This property is essentially the source of all the symmetries we can see in the pictures. For example, in the square lattice \mathbb{Z}^2 if we move everything by (a,b) for some fixed a,b\in \mathbb{Z}, then we will see the same lattice, because \mathbb{Z}^2+(a,b)=\mathbb{Z}^2.

The space \mathbb{R}^n has an algebraic structure (addition, subtraction and multiplication by scalars), but it also has an analytic structure which is induced by the Euclidean distance function d(u,v)=|u-v|. These two structure are connected by what we today call the arithmeticity of limits, and this connection makes dealing with these spaces all the more interesting. Thus, we should also look for more analytical properties of lattices.

In order to find this property, consider the nonlattice \mathbb{Q}^2 in \mathbb{R}^2. This set is “too big” to be spanned by only one basis (over \mathbb{Z}). In a more analytic way, we see that no matter how close we are to the origin, we can always find nonzero points from \mathbb{Q}^2 there .

Lattices don’t have too many points: With the example above in mind, we say that a point \gamma \in L is isolated if there exists a small enough \varepsilon>0 such that the ball of radius \varepsilon around it doesn’t contain any other point from L. The set L is called discrete if all of its points are isolated. In the case where L is a group, this is equivalent to one point, e.g. the origin, being isolated.
To show that any lattice is discrete, we consider the set F=\{\sum a_i v_i \ \mid\ |a_i|\leq\frac{1}{2}\}. This is a parallelepiped around the origin, so it is enough to show that the only lattice point in it is the origin. But if \sum a_i v_i \in F is a lattice point, then on the one hand the coefficients a_i are integers, and on the other |a_i|\leq \frac{1}{2} so they all must be zero, thus proving that the origin is isolated and therefore the lattice is discrete. A more visual proof, at least for the squares lattice, is the following picture

square_fund2

Squares Fundamental 1

Every lattice point is contained in a box which is a translation of F=[-\frac{1}{2},\frac{1}{2}]\times [-\frac{1}{2},\frac{1}{2}], and it does not contain any other lattice point.

These two properties, being a subgroup and being discrete, are not enough in order for a set to be a lattice. To see that, consider the subgroup L=\mathbb{Z}\times\{0\} – it doesn’t contain a basis for the plane so it cannot be a lattice, but clearly it is discrete. We can see it “analytically” by noting that there are points in \mathbb{R}^2 which can be as far as we want from any point of L, e.g. the points (0,M) where M is very big. This doesn’t happen for \mathbb{Z}^2 as we can see in the picture above, since every point in the plane is in one of these squares, and therefore is close to some lattice point (distance at most \frac{1}{\sqrt{2}}). This leads us to consider other tessellations of the plane, for example:

Similarly, we can do it in the honeycomb\hexagonal lattice:

In each of these cases we had a special region F which is on the one hand big enough, so that all of its translations together cover the plane (hence each point in the plane is “close” to a point in the lattice), and on the other hand it is small enough so that there is no overlapping (the points in the lattice are isolated from one another). To make this precise we have the following definition.

Definition: Let L be a subgroup of \mathbb{R}^n. A set F\subseteq \mathbb{R}^n is called a fundamental domain for L if the following holds:

  1. Its translations by L cover the whole space, namely \bigcup_{\gamma\in L} (\gamma+F)=\mathbb{R}^n.
  2. Two distinct translations are almost disjoint in the sense that if \gamma_1\neq \gamma_2 are in L, then (\gamma_1+L) \cap (\gamma_2+L) has zero n-dimensional volume.

Remark: In general, the fundamental domains can be very weird, but for our purposes, we can assume that they are “nice” regions whose volume we can actually compute. The second condition means in dimension 2 that the intersection will be finite union of curves (like the blue lines in the pictures above); in dimension 3 that the intersection will be finite union of surfaces, etc.

In our nonexample before, the set \mathbb{Z}\times\{0\} is not a lattice, and it has a fundamental domain which is [0,1]\times (-\infty,\infty). This domain has infinite area, which is what we will want to avoid. We note that infinite area means that it is unbounded, while the other direction is not true in general, but this condition on the area will be enough for us.

Of course, we first need to verify that our lattices indeed have fundamental domains. We have already seen one for the square-lattice, and we use a similar construction for the general lattice.

Lemma: Let v_1,...,v_n be a basis for \mathbb{R}^n and let L=span_\mathbb{Z}(v_1,...,v_n) be a lattice. Then F=\{\sum a_i v_i\ \mid\ a_i \in[0,1]\} is a fundamental domain for L.

Proof: A general vector in \mathbb{R}^n has the form v=\sum_1^n b_i v_i. We can write this vector as
\sum_1^n b_i v_i=(\sum_1^n \left\lfloor b_i \right\rfloor v_i)+(\sum_1^n [b_i - \left\lfloor b_i \right\rfloor] v_i)

Since the \left\lfloor b_i \right\rfloor are integers, the first summand is some \gamma\in L by definition, and the second is in F, so that v\in \gamma +F. As this is true for any vector we get that \mathbb{R}^n=\bigcup_{\gamma\in L}(\gamma+F).

It is also easy to see that two distinct translations of F can only intersect on their boundaries (i.e. one the a_i must be 0 or 1). This is a union of 2n spaces of dimension n-1 so they have zero n-dimensional volume, thus completing the proof that F is a fundamental domain.  \blacksquare

It is known that the volume of a fundamental domain of the form  F=\{\sum a_i v_i\ \mid\ a_i \in[0,1]\} is |\det[v_1\mid v_2 \mid ... \mid v_n]| – the absolute value of the determinant of the matrix with v_1,...,v_n as columns. If you have never seen this result, I urge you to check some 1,2 and 3-dimensional examples until you believe that it is true (and then prove it!). One of the questions that arise in this calculation is what happens if the lattice L is also defined by another basis u_1,...,u_n. In this case, since each of the u_j is in L, we can write it as a linear combination with integer coefficients of the vector v_1,...,v_n. Writing this down in a compact form, it means that we can find an n\times n matrix g with integer coefficients such that [v_1\mid v_2 \mid ... \mid v_n]\cdot g = [u_1\mid u_2 \mid ... \mid u_n]. Reversing the roles of the v_i and u_j we can find an integral matrix h that satisfies [v_1\mid v_2 \mid ... \mid v_n] = [u_1\mid u_2 \mid ... \mid u_n]\cdot h. Putting these two equalities together we get that

[v_1\mid v_2 \mid ... \mid v_n] = [u_1\mid u_2 \mid ... \mid u_n]\cdot h= [v_1\mid v_2 \mid ... \mid v_n]\cdot gh.

Since [v_1\mid u_2 \mid ... \mid v_n] is invertible (its columns form a basis) we conclude that gh=I. We conclude that g,h are integral matrices which are the inverses of each other, hence their determinants are integers which are inverses of each other, so they must be \pm 1. Thus, computing the volume with the second base, we get that

|\det[u_1\mid u_2 \mid ... \mid u_n]|=|\det[v_1\mid v_2 \mid ... \mid v_n]||det(g)|=|\det[v_1\mid v_2 \mid ... \mid v_n]|,

or in other words these two fundamental domain have the same volume (also, as a bonus we can move between any two bases of a lattice by multiplying by an integral matrix with \pm 1 determinant). This result is much more general and is true for any fundamental domain, and not just those that are defined by a basis. The proof is just by decomposing any given fundamental set (usually to infinitely many components), move them around to compose any other fundamental set.

Lemma: If L is a discrete group in \mathbb{R}^n and F_1,F_2 are two fundamental domains, then they have the same volume vol(F_1)=vol(F_2) (which might be infinite).

Definition: The covolume of a discrete group L in \mathbb{R}^n is defined to be the volume of any of its fundamental domains. We denote this covolume by covol(L).

Finally, we are ready to state one of the most important characterizations of lattices.

Theorem: Let L\subseteq \mathbb{R}^n. Then L is a lattice if and only if it is a discrete subgroup with finite covolume.

We have already proved that a lattice is a discrete subgroup with finite covolume. The other direction needs some more advanced tools (though not too much) and is left to the reader.

By this time we see that it is very easy to construct lattices, and there are many of those, and it would help if we could parametrize them easily. This will be done in a future post, but for now let us consider a small part of it. When we think about the squares lattice, it is not unique since the squares can be very small or very big, but eventually there is not much difference between these lattice other than choosing a normalization, which is what we’ll do next.

Clearly, if \alpha\neq 0 is some scalar and L is a lattice, then \alpha L is again a lattice and it is easy to see that covol(\alpha L)=|\alpha|^n covol(L). Thus, multiplying by a suitable \alpha we can always shrink\stretch a lattice in order to get a lattice with covolume one.

Definition: A lattice is called unimodular if it has covolume 1.

In general, we will always normalize our lattices to be unimodular.

Rather than concluding this post with just definitions, I would like to mention one of the most interesting results about lattices.

There are many problems in which we are given a lattice L and a big nice region B, e.g. a ball or a square, and we are asked how many lattice points are in that region (how many hexagonal chambers can you fit inside one honeycomb?). The intuition in this sort of problems is that instead of counting lattice points \gamma, we will count how many translations \gamma+F are contained in B for some fixed fundamental domain F. If B is a nice region, then we expect that for most of the lattice points we will have that \gamma \in B if and only if \gamma + F\subseteq B. For example if B is a ball, then this is true for all the lattice points that are not near the boundary of the ball.

gauss_cicrle.png

Gauss circle problem

Since the boundary grows linearly in the radius, while the surface area grows quadratically in the radius, the error we get from points near the boundary will be small. So now we are left with the questions of how many disjoint translations of F we can fit inside B. If there are n such translations, then vol(B) \sim n \cdot vol(F), so we would expect to have \frac{vol(B)}{vol(F)} such translations, and therefore \frac{vol(B)}{vol(F)} such lattice points.

This intuition is indeed true, and one of the first results which started this type of questions is due, unsurprisingly, to Gauss himself. This problem is called the Gauss circle problem.

Theorem: Let L be a lattice in \mathbb{R}^n and denote the ball of radius R by B(R)=\{ x\ \mid \ |x|<R\}. Then the number of points in the ball of radius R grows like

|L\cap B(R)| = \frac{vol(B(R))}{covol(L)}+O(R^{n-1}).

The notation O(R^{n-1}) means that the error is a functions which is bounded by CR^{n-1} for some constant C, which is much smaller than \frac{vol(B(R))}{covol(L)} which equals to C'R^n for some constant C'.


While searching for pictures for this post I came across a place called Giant’s Causeway in Ireland with interesting rock formation. While it is not as symmetric as the pictures in the beginning of the post, it is almost the hexagonal lattice, and moreover it seems like an interesting place, so I decided to share these too for your enjoyment.

14213693110_9bc8e73b32_zgiants_causeway_13

This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s