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 has. Recall that if
, we say that
divides
, and write
, if there exists some
such that
. Of course, there are integers
such that
and
, for example
. In these cases, we have probably the next best thing that we can hope for: for any
with
there are
such that
and
or
.
The second condition tells us that either or otherwise we can divide by
and get a remainder that is strictly “smaller” than
(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)
is an Euclidean domain with a Euclidean norm
if for any
with
there are
such that
and
or
.
Of course, the ring is Euclidean with the norm
. Another example is the ring of polynomials
over a field
which is Euclidean where the norm is just the degree function, namely
where
(note that
is not defined, and for these cases we need the
in the definition of Euclidean domain. Sometimes, to avoid this, we write
).
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. ) 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 which is a subring of the complex numbers. The invertible elements here are exactly
and these are exactly the elements with distance 1 from zero in
in the standard Euclidean distance. This leads to the question of whether
is an Euclidean norm as we defined above. Clearly, the image of
is in
so we just need to check the division conditions. Given
with
, we have that
. If
was actually in
, then we would be done because
. Otherwise, if we write
for some
, then what we can say about the norm of
is that
where we use the fact that the norm is multiplicative. We conclude that if and only if we chose
which is very close to
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 in the plane
, then we will see something like the following:
In this case we will choose
to be one of the corners of the
square that contains
(in the example above, we take the point
). The middle of the square has distance
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
such that
, and this is exactly what we needed in order to prove that
is Euclidean.
To summarize, we saw that the fact that is Euclidean follows from the fact that any point in
has a point in
with distance at most
between them. In other words, if you put a circle of radius
around each point of
you will cover the whole plane:
This phenomenon calls for a new definition.
Definition: Let be a lattice.
- For
we write
where
is the standard Euclidean distance.
- The covering radius of
is defined to be
.
In other words, the covering radius is the smallest radius such that the balls of radius
around the lattice points cover the whole space.
Remark: One can show that the minimum in is well defined, namely the infimum is achieved at some point in
(because lattices are discrete subgroups). Furthermore, the function
is continuous and bounded (you can’t be “too far” from the lattice), and therefore has a finite maximum.
Going back to , we reinterpret our proof using the definitions above:
- We realized
as a lattice in
(it is spanned by the vectors
).
- We showed that this lattice has covering radius
.
- We proved that
is Euclidean with the usual Euclidean distance squared norm if and only if as a lattice it has covering radius
.
Now that we have this process, let’s see which other nice rings are Euclidean with this norm by finding their lattices in .
- The rings
has covering radius
(distance to the middle of the rectangle).
- The lattice for the ring
has covering radius
. 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
by
, because it falls exactly in the middle of the square. Similar proof show that
is not Euclidean with the standard Euclidean distance squared for any
.
- Let
where
is a primitive root of unity of order 3, namely
and
. Note that this is exactly the ring
after we add the bad point from the previous example. This ring has covering radius
(middle of the triangle). Also, note that it is no longer trivial that the norm of an element in
is an integer, but doing the computation we see that
, so everything is OK.
- Similar to the
case, we get that
is Euclidean with the standard Euclidean distance squared for
(we need
, in order for the norm to have integer value). For
the lattice will have covering radius
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 . For example, the ring
is contained inside
and is dense there, so in particular it is not a lattice in
. 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
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 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
the number of antenna will be more or less
(this is Gauss circle counting method I discussed in the end of the post about lattices). Denoting by
the covering radius of
, in order to get good coverage everywhere we need that
. Moreover, if the covering radius is much smaller than
, then we can stretch the entire picture in order to build less antennas and still have good coverage.
More formally, we multiply the lattice by
so that it has covering radius exactly
, and we get that the number of antenna that we need to build is more or less
, hence we are left with the problem of finding a 2-dimensional lattice
that minimizes
. At this point you should notice that if we started with a lattice
or
for some
we should get the same result, because we did some normalization (multiplied by
). So to reduce the number of parameters in our problem, we write
where
is unimodular, and we are left with minimizing the expression
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 !
A dual problem to the one above concerns the packing radius of a lattice. The packing radius is the largest such that the spheres in radius
around the lattice points do not overlap. For example in the lattices coming from
the packing radius is
.
:
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 what is the percentage of
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 are two distinct lattice points, then the packing radius is at most
. Since
is again a lattice point (because a lattice is closed under subtraction) we get that the packing radius of a lattice
is at most
, 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
. 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 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.
Pingback: Guess what, I’m turning 26. – Kai.