From number theory to geometry of lattices

Number theory can mean a lot of thing to a lot of people. This is a very big part of mathematics, and it contains many areas starting with the elementary number theory (“simple” congruence like arguments), algebraic number theory (e.g. field extensions and algebraic integers), analytic number theory (Riemann zeta function) and many more. I will mainly concentrate on the algebraic part, though this post will be very basic. I recommend reading my post about lattices before reading this post.

The main goal of this post is to describe a method that gives geometric interpretation to many algebraic questions. In this post I will only mention one such question, but in later posts I will mention several others.

We begin by considering one of the most useful properties the ring of integers $\mathbb{Z}$ has. Recall that if $a,b\in \mathbb{Z}$ , we say that $b$ divides $a$ , and write $b \mid a$ , if there exists some $r\in \mathbb{Z}$ such that $br=a$ . Of course, there are integers $a,b$ such that $a\nmid b$ and $b\nmid a$ , for example $a=2, b=3$ . In these cases, we have probably the next best thing that we can hope for: for any $a,b\in \mathbb{Z}$ with $b\neq 0$ there are $q,r \in \mathbb{Z}$ such that

$a=bq+r$ and
$r=0$ or $|r|<|b|$ .

The second condition tells us that either $b\mid a$ or otherwise we can divide by $b$ and get a remainder that is strictly “smaller” than $b$ (which, for example, is used many times for induction type proofs). This property of division with remainder is not unique to the integers and there are several other important rings which satisfy this property. We say that an integral domain (i.e. a commutative ring with unit and without zero divisors) $R$ is an Euclidean domain with a Euclidean norm $N:R-\{0\} \to \mathbb{N}$ if for any $a,b \in R$ with $b\neq 0$ there are $q,r\in R$ such that

$a=bq+r$ and
$r=0$ or $N(r)<N(b)$ .

Of course, the ring $\mathbb{Z}$ is Euclidean with the norm $N(m)=|m|$ . Another example is the ring of polynomials $\mathbb{F}[x]$ over a field $\mathbb{F}$ which is Euclidean where the norm is just the degree function, namely $deg(\sum_{n=0}^{d} a_n x^n)=d$ where $a_d \neq 0$ (note that $N(0)$ is not defined, and for these cases we need the $r=0$ in the definition of Euclidean domain. Sometimes, to avoid this, we write $N(0)=-\infty$ ).

In both of the cases above, the invertible elements have the smallest possible norm (1 for integers and 0 for polynomials), and when we take elements which are product of many other elements (e.g. $n!$ ) we expect the norm to be very big.

The next Euclidean domain is where things start to get interesting. Consider the ring of Gaussian integers $\mathbb{Z}[i]=\{a+bi\ \mid\ a,b\in \mathbb{Z}\}$ which is a subring of the complex numbers. The invertible elements here are exactly $\pm 1, \pm i$ and these are exactly the elements with distance 1 from zero in $\mathbb{Z}[i]$ in the standard Euclidean distance. This leads to the question of whether $N(a+bi)=|a+bi|^2=a^2+b^2$ is an Euclidean norm as we defined above. Clearly, the image of $N$ is in $\mathbb{N}$ so we just need to check the division conditions. Given $z,w\in \mathbb{Z}[i]$ with $w\neq 0$ , we have that $\tilde{q}=\frac{z}{w}\in \mathbb{C}$ . If $\tilde{q}$ was actually in $\mathbb{Z}[i]$ , then we would be done because $z=\tilde{q}w+0$ . Otherwise, if we write $z=wq+r$ for some $q,r\in\mathbb{Z}[i]$ , then what we can say about the norm of $r$ is that

$N(r)=N(z-wq)=N(w\tilde{q}-wq)=N(w)N(\tilde{q}-q)$

where we use the fact that the norm is multiplicative. We conclude that $N(r)<N(q)$ if and only if we chose $q$ which is very close to $\tilde{q}$ in the sense that the distance between them is less than 1.

Let’s try to understand this condition visually. If we draw the points of $\mathbb{Z}[i]$ in the plane $\mathbb{C}\cong\mathbb{R}^2$ , then we will see something like the following:
z[i].png In this case we will choose $q$ to be one of the corners of the $1\times 1$ square that contains $\tilde{q}$ (in the example above, we take the point $1+i$ ). The middle of the square has distance $\frac{\sqrt{2}}{2}=\frac{1}{\sqrt{2}}<1$ from each of the corners, and this is the farthest that you can get from the corner for any point inside the square. In other words we can always find $q\in \mathbb{Z}[i]$ such that $|q-\tilde{q}|<\frac{\sqrt{2}}{2}$ , and this is exactly what we needed in order to prove that $\mathbb{Z}[i]$ is Euclidean.

To summarize, we saw that the fact that $\mathbb{Z}[i]$ is Euclidean follows from the fact that any point in $\mathbb{C}$ has a point in $\mathbb{Z}[i]$ with distance at most $\frac{1}{\sqrt{2}}<1$ between them. In other words, if you put a circle of radius $\frac{1}{\sqrt{2}}<1$ around each point of $\mathbb{Z}[i]$ you will cover the whole plane:

z[i]_circles.png

This phenomenon calls for a new definition.

Definition: Let $L\subseteq \mathbb{R}^n$ be a lattice.

For $v\in \mathbb{R}^n$ we write $dist(v,L)=\min_{u \in L} |u-v|$ where $|(x_1,...,x_n)|=\sqrt{x_1^2+\cdots+x_n^2}$ is the standard Euclidean distance.
The covering radius of $L$ is defined to be $\max_{v\in \mathbb{R}^n} dist(v,L)$ .

In other words, the covering radius is the smallest radius $r>0$ such that the balls of radius $r$ around the lattice points cover the whole space.

Remark: One can show that the minimum in $dist(v,L)$ is well defined, namely the infimum is achieved at some point in $L$ (because lattices are discrete subgroups). Furthermore, the function $d(v,L)$ is continuous and bounded (you can’t be “too far” from the lattice), and therefore has a finite maximum.

Going back to $\mathbb{Z}[i]$ , we reinterpret our proof using the definitions above:

We realized $\mathbb{Z}[i]$ as a lattice in $\mathbb{C}\cong \mathbb{R}^2$ (it is spanned by the vectors $1,i$ ).
We showed that this lattice has covering radius $\frac{1}{\sqrt{2}} < 1$ .
We proved that $\mathbb{Z}[i]$ is Euclidean with the usual Euclidean distance squared norm if and only if as a lattice it has covering radius $<1$ .

Now that we have this process, let’s see which other nice rings are Euclidean with this norm by finding their lattices in $\mathbb{C}$ .

The rings $\mathbb{Z}[\sqrt{-2}]=\{a+b\sqrt{2}i\ \mid\ a,b\in \mathbb{Z}\}$ has covering radius $\frac{\sqrt{3}}{2}<1$ (distance to the middle of the rectangle).
The lattice for the ring $\mathbb{Z}[\sqrt{-3}]$ has covering radius $\frac{\sqrt{4}}{2}=1$ . It follows that it is not Euclidean with the standard Euclidean distance squared. We cannot use the division algorithm needed in the definition when we try to divide $1+\sqrt{3}i$ by $2$ , because it falls exactly in the middle of the square. Similar proof show that $\mathbb{Z}[\sqrt{-m}]$ is not Euclidean with the standard Euclidean distance squared for any $m\geq 3$ .
Let $\mathbb{Z}[\omega]=\{a+b\omega\ \mid\ a,b\in \mathbb{Z}\}$ where $\omega=\frac{-1+\sqrt{3}i}{2}$ is a primitive root of unity of order 3, namely $\omega^3=1$ and $\omega \neq 1$ . Note that this is exactly the ring $\mathbb{Z}[\sqrt{-3}]$ after we add the bad point from the previous example. This ring has covering radius $\frac{1}{\sqrt{3}}$ (middle of the triangle). Also, note that it is no longer trivial that the norm of an element in $\mathbb{Z}[\omega]$ is an integer, but doing the computation we see that $N(a+b\omega)=(a+b\omega)(a+b\bar{\omega})=a^2-ab+b^2 \in \mathbb{N}$ , so everything is OK.
Similar to the $\mathbb{Z}[\omega]=\mathbb{Z}[\frac{-1+\sqrt{3}i}{2}]$ case, we get that $\mathbb{Z}[\frac{-1+\sqrt{m}i}{2}]$ is Euclidean with the standard Euclidean distance squared for $m=3,7,11$ (we need $m\equiv 3 (mod 4)$ , in order for the norm to have integer value). For $m=15,19,23,...$ the lattice will have covering radius $\geq 1$ so that it will not be Euclidean with this norm.

At this point we can ask what happens with a ring which is not naturally embedded as a lattice in $\mathbb{C}$ . For example, the ring $\mathbb{Z}[\sqrt{2}]$ is contained inside $\mathbb{R}$ and is dense there, so in particular it is not a lattice in $\mathbb{C}$ . While the method above for showing that a ring is Euclidean cannot be used on such a ring, there is still a “natural” way to embed it as a lattice in $\mathbb{R}^2$ which will appear in a future post.

We have just seen how to use lattices and their covering radius, in order to understand algebraic properties of rings. On the other hand, lattices have many applications by themselves, and we can ask whether we can use number theory to construct “good” lattices.

Consider the problem of a cellular phone company who wants to build antennas. Let $r$ be the radius such that you get good signal reception only if you are at most r meters away from an antenna. The company now faces with the problem of building as few as possible antennas (because they cost a lot of money!) and on the other hand they want to cover as much as possible space. If they build these antennas according to some lattice, then in any nice region (e.g. a big circle) with surface area $V$ the number of antenna will be more or less $\frac{V}{covol(L)}$ (this is Gauss circle counting method I discussed in the end of the post about lattices). Denoting by $R(L)$ the covering radius of $L$ , in order to get good coverage everywhere we need that $R(L) \leq r$ . Moreover, if the covering radius is much smaller than $r$ , then we can stretch the entire picture in order to build less antennas and still have good coverage.

More formally, we multiply the lattice $L$ by $\frac{r}{R(L)}$ so that it has covering radius exactly $r$ , and we get that the number of antenna that we need to build is more or less $\frac{V}{covol((r/R(L))L)}=\frac{V}{r^2} \frac{R(L)^2}{covol(L)}$ , hence we are left with the problem of finding a 2-dimensional lattice $L$ that minimizes $\frac{R(L)^2}{covol(L)}$ . At this point you should notice that if we started with a lattice $L$ or $\alpha L$ for some $\alpha\neq 0$ we should get the same result, because we did some normalization (multiplied by $\frac{r}{R(L)}$ ). So to reduce the number of parameters in our problem, we write $L=\alpha \hat {L}$ where $\hat{L}$ is unimodular, and we are left with minimizing the expression

$\frac{R(\alpha \hat{L})^2}{covol(\alpha \hat{L})}=R(\hat{L})^2$

Or in other words, we’re looking for a unimodular 2-dimensional lattice with minimal covering radius. As this is just 2-dimensional, it is not that hard to solve, and I will leave it as an exercise to show that this is exactly the hexagonal lattice that corresponds to $\mathbb{Z}[\omega]$ !

A dual problem to the one above concerns the packing radius of a lattice. The packing radius is the largest $r$ such that the spheres in radius $r$ around the lattice points do not overlap. For example in the lattices coming from $\mathbb{Z}[i], \mathbb{Z}[\omega]$ the packing radius is $\frac{1}{2}$ .

$\mathbb{Z}[i]$ :
$\mathbb{Z}[\omega]:$

Of course, we need to normalize these lattices in order to be able to compare their packing radius. Another way to think about the packing radius is given a big region $V$ what is the percentage of $V$ covered by these sphere that we drew. At least for the two lattices above, we can see that the packing in the hexagonal lattice cover more of the space than the packing in the square lattice. Actually, when we consider only 2-dimensional lattices, this is again the best possible. In a sense, this should not surprize us – when bees want to create their beehive, each larva is put in a circular chamber, so in order to have the maximal number of chambers in their two dimensional hives, they also use the hexagonal lattice, so they waste as little as possible space.

(As I’m far from being a bee expert, this of course might have a totally different reason, but I like to think that for millions of years, bees have been making lattice related optimization…)

Let us note, that if $v,u$ are two distinct lattice points, then the packing radius is at most $\frac{1}{2}|u-v|$ . Since $u-v$ is again a lattice point (because a lattice is closed under subtraction) we get that the packing radius of a lattice $L$ is at most $\frac{1}{2}\min_{0\neq v\in L} |v|$ , and a bit more thought show that there is an equality. Thus, we are interested in finding the length of the shortest nonzero vector in $L$ . The problem of finding the minimal length of a nonzero vector has great importance in the study of lattices and their connection to number theory, and I will cover some of its roles in future post.

I want to finish with one more use of lattices and packing numbers (which unfortunately, I don’t know too much about). To make life even harder, given a lattice $L$ we can try to find a nonzero vector with the shortest length. This problem for general lattices is used as part of encryption protocols, and it is claimed that in a post quantum computers world, where the RSA based protocols could be broken quickly, the lattice based protocols will still be hard to break. So, what I’m trying to say is that if you want to survive the post apocalyptic world, after we develop quantum computers, and still be able to use the internet (or maybe the mindnet, if we are lucky), then you should learn about lattices.

1 Response to From number theory to geometry of lattices

Pingback: Guess what, I’m turning 26. – Kai.