We all know about Pythagoras and his obsession with triangles. Usually when we first learn about the rational and real numbers, we are also told about the Pythagoreans, a 6th century BCE cult that started with the followers of Pythagoras and which dealt with mysticism and Mathematics (and if it still exists and you are a member in it, please send me a message – I would love to join). The legend says that they loved ratios between natural numbers, i.e. rational numbers, and didn’t believe that there exist any other type of numbers. Unfortunately, Hippasus which was one of their own “betrayed” them and proved that is not rational. When he died by drowning, the Pythagoreans said that this was a punishment by the gods themselves for showing that the world of Mathematics is not perfectly rational. Well, it was either this, or because he built a dodecahedron inside a sphere. Anyway, these days we know that there are irrational numbers, of course, but it is nice to know that if you insult the gods of Mathematics you will be punished.
The moral from this story is that rational numbers are divine, but there are other types of numbers – like the real numbers. While there are irrational numbers, there are so many rational numbers so that we can get as close as we want to any real number. In this post we will try to investigate when should we say that an approximation is good, how good of an approximation can we hope to find for a given real number, and what is the connection to lattices (see the post about lattices for the definitions and some examples).
The first approximation that we can get, using our modern notations, is that for any real number and any , we can find a rational number such that . Thus, if for example we wanted to store in a computer (which might have infinite presentation in decimal expansion), we can instead store the two integers (which of course have finite decimal expansion). The problem is that the integers can be very big, so that the presentation of these integers will take a lot of space. Thus, what we really want is to approximate with a rational number where are small integers compared to . For example, we can try to find such integers which satisfy
If the inequality above is true, then if we chose very big, then it might take a lot of space in the computer, but we also get a better approximation. To make the notation easier, we shall assume that so that we can always choose such that , and we will only care about the size of .
To show that the inequality above can always be satisfied is quite easy. Indeed, letting be the largest integer such that , then and therefore
We can actually show something a little better than that – since is between and , if we take the rational point with which is closer to we will get that
At this point Dirichlet steps in, and shows us how to do real approximation with one of the most simplest and elegant proofs there is in Mathematics that uses nothing more than the pigeon hole principle and just with it shows that there are infinitely many solutions to . As this is clearly true for rational, we shall prove it under the assumption that is irrational.
Before giving the proof, let’s reformulate it in a way which will be much easier to work with. The main idea of this reformulation is that we prefer to work with integers, rather than rational numbers (or more specifically, we want to work with and not ). We claim that in order to find infinite distinct solutions to the inequality , it is enough to find a solution for
for any . Indeed, any solution to these inequalities implies that which is exactly what we wanted. A given fixed pair cannot be a solution for any , because for all big enough we will get that (using the fact that is irrational). Thus a solution for any will give infinitely many distinct solutions to .
Theorem (Dirichlet): Let be any real number. Then for any there exists a solution to the inequalities
Proof: Define the fractional part of to be . For a given , the minimum of is at most (actually, it equals ), so it is enough to find such that .
Consider the numbers . If one of them is in , then we are done. Otherwise, each of them falls in one of the cells of the form where . By the pigeon hole principle we can find two distinct integers such that fall in the same cell, and hence
Setting and , we get a solution as required.
To give a little bit more modern interpretation to the proof above, we note that considering only the fractional part of a real number is equivalent to changing our point of view to the quotient space . This quotient space is nothing else than the unit circle, and the addition in becomes rotation (addition of angles). Thus, we started with an angle and we multiplied it by and checked in which cell each of these points fell into.
For example, let’s take and . Then the corresponding picture on the unit circle is:
In this picture we wrap around the segment to get a circle, and then the segments for become the seven equal parts of the circumference. The fact that is in the first part is equivalent to . We can also see that are in the same part, so that their difference from above, must be in the first part.
We are now ready to an even more geometric interpretation to Diophantine approximation. Consider again the inequalities
To make things a little more symmetric, we can change the second inequality to . The problem here is that then we will have a trivial solution, namely . But if we exclude this solution, then we get that same problem as above (i.e. we don’t care if is a negative integer, because we can always multiply by to get a solution to the original problem). So, rewriting our problem we see that we are looking for a nonzero vector such that , or an even better notation
In other words, we consider all the element in the lattice
and we ask whether this lattice contains a nontrivial (i.e. nonzero) point inside the rectangle . For example, for and as above and for , the picture we see is:
The interpretation of what we see is as follows: The height of a point is the integer and once we choose the height, then the different points on the same horizontal line correspond to choosing different ‘s. What we want to do is to choose such , so that the point would be as close as we can to the -axis. For we already saw that choosing is enough, since , so that its fractional part is which is smaller that . When we continue to , this fractional part is not enough since , but as Dirichlet’s theorem tells us, we can find another point which is in the box corresponding to . In the picture above we see that taking will do the job, and indeed and its distance from is .
To summarize, what we saw is that finding good rational approximation to a real number is equivalent to finding nontrivial points in a suitable lattice that are contained in certain boxes. We already know that this is possible, since this is exactly what Dirichlet showed us, but is there a geometric intuition for this result? Well, if is any lattice, and is a symmetric box around the origin, then of course it will contain a lattice point, namely the origin. But if we also assume that the box is “big enough” we would expect that it would contain at least one more lattice point, and the question that we are left with is what is “big enough”. This intuition is indeed true, and this result is called Minkowski’s theorem which started the field of what is now known as the geometry of numbers, and which I will write about in a future post.