From Diophantine approximation to geometry of numbers

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 \sqrt{2} 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 x \in \mathbb{R} and any \varepsilon>0, we can find a rational number \frac{p}{q}\in \mathbb{Q} such that |x-\frac{p}{q}|<\varepsilon. Thus, if for example we wanted to store x in a computer (which might have infinite presentation in decimal expansion), we can instead store the two integers p,q (which of course have finite decimal expansion). The problem is that the integers p,q 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 x with a rational number \frac{p}{q} where p,q are small integers compared to \varepsilon. For example, we can try to find such integers which satisfy

|x-\frac{p}{q}|\leq \frac{1}{q}.

If the inequality above is true, then if we chose q 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 x\in [0,1] so that we can always choose p such that 0\leq p\leq q, and we will only care about the size of q.

To show that the inequality above can always be satisfied is quite easy. Indeed, letting p be the largest integer such that \frac{p}{q}\leq x, then \frac{p+1}{q}> x and therefore

|x-\frac{p}{q}|=x-\frac{p}{q}<\frac{p+1}{q}-\frac{p}{q}=\frac{1}{q}

We can actually show something a little better than that – since x is between \frac{p}{q} and \frac{p+1}{q}, if we take the rational point \frac{p'}{q} with p'\in \{p,p+1\} which is closer to x we will get that

|x-\frac{p'}{q}|\leq \frac{1}{q\cdot 2}.

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 |x-\frac{p}{q}|\leq \frac{1}{q^2}. As this is clearly true for x rational, we shall prove it under the assumption that x 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 q and not \frac{1}{q}). We claim that in order to find infinite distinct solutions to the inequality |x-\frac{p}{q}|\leq \frac{1}{q^2}, it is enough to find a solution for

|qx-p|\leq  \frac{1}{R}

1\leq q\leq R

for any R>1. Indeed, any solution to these inequalities implies that |qx-p|\leq \frac{1}{R}\leq \frac{1}{q} which is exactly what we wanted.  A given fixed pair (p,q) cannot be a solution for any R, because for all big enough R we will get that |qx-p|> \frac{1}{R} (using the fact that x is irrational). Thus a solution for any R>1 will give infinitely many distinct solutions to |x-\frac{p}{q}|\leq \frac{1}{q^2}.

Theorem (Dirichlet): Let x be any real number. Then for any R>1 there exists a solution (p,q)\in \mathbb{Z}^2 to the inequalities

|qx-p|<  \frac{1}{R}

1\leq q \leq R

Proof: Define the fractional part of y to be \{y\}=y-\left\lfloor y \right\rfloor \in [0,1). For a given q, the minimum of |qx-p| is at most \{qx\} (actually, it equals \min\{ \{qx\}, 1-\{qx\} \}), so it is enough to find 1\leq q\leq R such that \{qx\}\in[0,\frac{1}{R}).

Consider the numbers \{1\cdot x\}, \{2\cdot x\},..., \{R \cdot x\}. If one of them is in [0,\frac{1}{R}), then we are done. Otherwise, each of them falls in one of the R-1 cells of the form [\frac{i}{R}, \frac{i+1}{R}) where 1\leq i \leq R-1. By the pigeon hole principle we can find two distinct integers 1\leq q_1< q_2 \leq R such that \{q_1 x\}, \{q_2 x\} fall in the same cell, and hence

\frac{1}{R}> |\{q_2x\}-\{q_1x\}|=|(q_2-q_1)x-(\left\lfloor q_2x \right\rfloor-\left\lfloor q_1x \right\rfloor)|.

Setting  p=\left\lfloor q_1x \right\rfloor-\left\lfloor q_2x \right\rfloor and q=q_2 - q_1, we get a solution as required.  \blacksquare

To give a little bit more modern interpretation to the proof above, we note that considering only the fractional part of a real number y\in \mathbb{R} is equivalent to changing our point of view to the quotient space \mathbb{R}/\mathbb{Z}. This quotient space is nothing else than the unit circle, and the addition in \mathbb{R} becomes rotation (addition of angles). Thus, we started with an angle x and we multiplied it by 1,2,...,R and checked in which cell each of these points fell into.

For example, let’s take x=\frac{1}{e}\sim 0.367 and R=7. Then the corresponding picture on the unit circle is:circle_dio_approx.png

In this picture we wrap around the segment [0,1] to get a circle, and then the segments [\frac{i}{7},\frac{i+1}{7}] for i=0,...,6 become the seven equal parts of the circumference. The fact that y=3\cdot \frac{1}{e} is in the first part is equivalent to y-\left\lfloor y \right\rfloor \in [0,\frac{1}{7}). We can also see that 2\cdot \frac{1}{e}, 5\cdot \frac{1}{e} are in the same part, so that their difference 3\cdot \frac{1}{e} 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

|qx-p|\leq  \frac{1}{R}

1\leq q \leq R.

To make things a little more symmetric, we can change the second inequality to |q|\leq R. The problem here is that then we will have a trivial solution, namely (p,q)=(0,0). But if we exclude this solution, then we get that same problem as above (i.e. we don’t care if q is a negative integer, because we can always multiply p,q by -1 to get a solution to the original problem). So, rewriting our problem we see that we are looking for a nonzero vector (p,q)\in \mathbb{Z}^2 such that (px-q,q) \in [-\frac{1}{R},\frac{1}{R}]\times [-R,R], or an even better notation

\left(\begin{array}{cc} -p & q\end{array}\right)\left(\begin{array}{cc} 1 & 0\\ x & 1 \end{array}\right)\in\left[-\frac{1}{R},\frac{1}{R}\right]\times\left[-R,R\right].

In other words, we consider all the element in the lattice

span_\mathbb{Z} \{ (1,0), (x,1) \}:=\{ p(1,0)+q(x,1)\ \mid\ p,q\in \mathbb{Z} \},

and we ask whether this lattice contains a nontrivial (i.e. nonzero) point inside the rectangle [-\frac{1}{R},\frac{1}{R}]\times [-R,R]. For example, for x=\frac{1}{e} and R=7 as above and for R=10, the picture we see is:

dio_boxes.png

The interpretation of what we see is as follows: The height of a point is the integer q and once we choose the height, then the different points on the same horizontal line correspond to choosing different p‘s. What we want to do is to choose such p, so that the point would be as close as we can to the y-axis. For R=7 we already saw that choosing q=3 is enough, since 3\cdot\frac{1}{e}\sim 1.10363 , so that its fractional part is \sim 0.10362 which is smaller that \frac{1}{7}. When we continue to R=10, this fractional part is not enough since \sim 0.10362 > \frac{1}{10}=0.1, but as Dirichlet’s theorem tells us, we can find another point which is in the box corresponding to R=10. In the picture above we see that taking q=8 will do the job, and indeed 8\cdot \frac{1}{e} \sim 2.94303 and its distance from 3=\left\lceil 8\cdot\frac{1}{e}\right\rceil is \sim 0.0569<0.1.

To summarize, what we saw is that finding good rational approximation to a real number x 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 L is any lattice, and B 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.

This entry was posted in Diophantine approximation 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