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 real numbers which are not rational. 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 finish with a bit about the connection to lattices (see the post about lattices for the definitions and some examples).

What is a rational approximation

To start off, given a real number $x \in \mathbb{R}$ , a rational approximation is simply a rational number $\frac{p}{q}\in \mathbb{Q}$ where $|x-\frac{p}{q}|$ is “small”. Whether it is a “good” rational approximation will be determined by how “small” this is.

As it is right now, this starting point can be very confusing to anyone who knows a little bit about rational numbers. Indeed, we can find such rational numbers which make this absolute value as small as we want, or more formally, for any $\varepsilon>0$ there is a rational number which solves $|x-\frac{p}{q}|<\varepsilon$ .

To get a better intuition of the “goodness” of approximation, think about the problem of storing $x$ in your computer’s memory. Usually, we store numbers in memory using their binary presentation, however in general $x$ might have an infinite such presentation. One solution is instead to store an approximation $x_0$ of $x$ instead which has a finite presentation, and keep in mind that we have a computation error which depends on the approximation. The smaller the distance $|x-x_0|$ , the smaller our computation error.

For example, if $x_0=\frac{p}{q}$ is rational, then we only need to store $p$ and $q$ which of course have finite presentation. The problem is that if we want a very small computation error, we might end up using very big $p$ and $q$ , so they would require a lot of memory to store. As we are quite greedy mathematicians – can we find rationals which have very small error, but also the numerator and denominator are small? This is a much more interesting question, and the smaller the sizes of the numerator and denominator are with respect to the error, the better we think of the approximation.

What can we say about the comparison between these sizes $p, q$ and the error? As a starting point, we can always find such integers such that $\frac{p}{q}\leq x \leq \frac{p+1}{q}$ , in which case

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

Moreover, if we approximate $x$ with the rational $\frac{p}{q}$ or $\frac{p+1}{q}$ closer to it, then the error is at most $\frac{1}{2q}$ . For example, if we want a $\frac{1}{2\cdot 100}$ error, we can always do it with a denominator at most $100$ .

As for bounding the numerator, for simplicity, lets assume that $x \in [0,1]$ , so that $0\leq p \leq q.$ This way bounding the denominator $q$ also bounds the numerator $p$ . In particular, in the example above to get the error $\varepsilon>0$ , we look for $p,q$ which are at most $\left\lceil 1/(2\cdot\varepsilon)\right\rceil$ .

What is a GOOD rational approximation (according to Dirichlet)

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$ which is the real parameter of our problem and not $\frac{1}{q}$ ).

As a first step, we simply move from trying to solve $|x-\frac{p}{q}|\leq \frac{1}{q^2}$ , to trying to solve $|qx-p|\leq \frac{1}{q}$ which doesn’t have any rationals inside the absolute value. We can multiply again by $q$ , but then we will move from the simple linear function $qx-p$ to the more complicated function $q(qx-p)$ . To avoid this, we use an interesting trick where we break our inequality to two inequalities as follows:

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

$1\leq q\leq R,$

where $R>1$ is an integer. Note that for any fixed $R$ , the inequalities are linear in both $p$ and $q$ . Also, if we find a solution to both of these inequalities, then we have a solution to our original inequality, since

$|qx-p|\leq \frac{1}{R}\leq \frac{1}{q}.$

Finally, our new setting is much more natural when looking for better and better approximations. It basically says that for an approximation $|qx-p|$ which is at most $\frac{1}{R}$ we allow ourselves to have the denominator $q$ at most $R$ . This formulation also easily implies that if we have such an approximation for every $R>1$ , then we will get infinity many solutions to $|x-\frac{p}{q}|\leq \frac{1}{q^2}$ (prove it!).

This new formulation has a very nice visualization attached to it. First, note that in a sense $q$ is the only parameter of the inequalities. Once we choose it, $p$ will always be either $\left\lceil qx\right\rceil$ or $\left\lfloor qx\right\rfloor$ in order to minimize $|qx-p|$ . In particular, we can assume that this absolute value is always in $[0,1]$ . Equivalently, we can look on the fractional part $\{qx\}=qx-\left\lfloor qx\right\rfloor$ of $qx$ , which is in $[0,1]$ , and hope to find such $q$ where $\{qx\}$ is either very small, or very close to $1$ . Or, if we glue together $0$ and $1$ (e.g. we live in $\mathbb{R}/\mathbb{Z}$ ) to get a circle, then the question is whether $\{qx\}$ is close to the gluing point on the circle.

Let’s look on the example with $R=7$ and $x=\frac{1}{e}\sim 0.367$ :

In this picture we have $R=7$ the red points of the form $q\cdot \frac{1}{e},\; q=1,...,7$ rotate around the circle. The circle is also divided to $R=7$ equal parts, and our problem was finding a point in one of the parts touching the gluing point $(1,0)$ . In this example we can see one such point which is $3\cdot\frac{1}{e}$ . The question is if we just had a very good luck by choosing $x$ and $R,$ or maybe there is something else at work.

What would happen if there are no red points in the two blue parts near the gluing point? In this case we will need to distribute 7 points in the rest of the 5 blue regions, in which case one of them will contain at least two points by the pigeon hole principle (in the example above, we have $2\cdot\frac{1}{e}, 5\cdot\frac{1}{e}$ in the same blue region). In particular, the distance between these two points will be small, and this is what Dirichlet used in his proof.

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

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

$1\leq q \leq R$

Proof: Consider the fractionsl parts $\{1\cdot x\}, \{2\cdot x\},..., \{R \cdot x\}$ and their locations in the cells of the form $C_i = [\frac{i}{R}, \frac{i+1}{R})$ for $i=0,...,R-1$ . 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 $C_i$ 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. $\square$

Exercise: Try to reprove the claim, but with $q<R$ instead of $q\leq R$ . Can you also prove it for general $R$ and not just integers?

The lattice of approximations

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 $(qx-p,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:

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 $\{3\cdot\frac{1}{e}\}\sim 0.10362$ which is smaller that $\frac{1}{7}$ . When we continue to $R=10$ , this fractional part is not enough since $\{3\cdot\frac{1}{e}\}\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 approximations 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” (in the example above, it had area equals to 4). 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.