Dirichlet’s approximation theorem

The definition of rational numbers is usually expressed as follows.

Definition 1 For every real number , is rational if and only if there are integers and such that and .

Remark 1 For every pair of integers and such that , , where if and if . Therefore, the definition which is the same as Definition 1 except that is required to be positive and is required to be coprime to is equivalent to Definition 1.

However, there’s a slightly different way one can express the definition, which uses the fact that the equations and are equivalent.

Definition 2 For every real number , is rational if and only if there is a nonzero integer such that is an integer.

Remark 2 The definition which is the same as Definition 3 except that is required to be positive and is required to be coprime to is equivalent to Definition 3.

The nice thing about Definition 3 is that it immediately brings to mind the following algorithm for verifying that a real number is rational: iterate through the positive integers in ascending order, and for each positive integer check whether is an integer. (It’s assumed that it is easy to check whether an arbitrary real number is an integer.) If it is an integer, stop the iteration. The algorithm terminates if and only if is rational. The algorithm is obviously not very useful if it is actually used by a computer to check for rationality—one obvious problem is that it cannot verify irrationality, it can only falsify it. But it is useful as a guuide to thought. Mathematical questions are often easier to think about if they are understood in terms of processes, rather than in terms of relationships between static objects.

In particular, there’s a natural way in which some irrational numbers can be said to be “closer to rational” than others, in terms of this algorithm. If is irrational, then none of the terms in the sequence are integers. But how close to integers are the terms? The closer they are to integers, the closer to rational can be said to be.

But how is the closeness of the integers to the terms of the sequence to be measured? There are different ways this can be done. Perhaps the most natural way to start off with is to measure it by the minimum of the distances of the terms from the closest integers to them—that is, the minimum of the set . Of course, this minimum may not even exist—it may be possible to make arbitrarily small by choosing appropriate integers and such that . So the first question to answer is this: for which values of does the minimum exist?

The answer to this question is given by Dirichlet’s approximation theorem.

Theorem 3 (Dirichlet’s approximation theorem) For every real number and every positive integer , there are integers and such that and

Proof: First, let us define some notation. For every real number , let denote the greatest integer less than or equal to and let denote . Note that the inequality always holds.

Now, suppose is a real number and is a positive integer. The real numbers 0, , , … and are all in the half-open interval . This interval can be partitioned into the sub-intervals , , \dots and , each of length . These real numbers are distributed among these sub-intervals, and since there are more real numbers than sub-intervals at least one of the sub-intervals contains more than one of the real numbers. That is, there are integers and such that and are in the same sub-interval and hence . Or, equivalently:

so if we let and we have . And and can be chosen so that and hence is positive.

Dirichlet’s approximation theorem says that for every real number , can be made arbitrarily small by choosing appropriate integers and such that , and hence the minimum of the set does not exist.

It may not be immediately obvious from the way in which it has been presented here why Dirichlet’s approximation theorem is called an “approximation theorem”. The reason is that if the inequality is divided through by (which produces an equivalent inequality, given that is positive), the result is

So Dirichlet’s approximation theorem can also be interpreted as saying that for every real number and every positive integer , it is possible to find a rational approximation to (where and are integers and ) whose error is less than . In fact, this is how the theorem is usually presented. When it’s presented in this way, Dirichlet’s approximation theorem can be seen as an addendum to the fact that for every positive integer , it is possible to find a rational approximation to whose error is less than —that is, arbitrarily small rational approximations exist to every real number. (This is very easily proven—it’s really just another way of expressing the fact that the set of all rational numbers, , is dense in the set of all real numbers, .) After obtaining that result, one might naturally think, “well, in this sense all real numbers are equally well approximable by rational numbers, but perhaps if I make the condition more strict by adding a factor of into the quantity the error has to be less than, I can uncover some interesting differences in the rational approximability of different real numbers.” But the relevance of Dirichlet’s approximation theorem can also be understood in a more direct way, and that’s what I wanted to show with this post.

Of course putting this extra factor in doesn’t lead to the discovery of any interesting differences in the rational approximability of of different real numbers. In order to get to the interesting differences, you have to add in yet another factor of . A real number is said to be well approximable if and only if for every positive integer , there are integers and such that and

or, equivalently,

Otherwise, is said to be badly approximable. Some real numbers are well approximable, and some are badly approximable.

There is in fact a very neat characterisation of the distinction in terms of continued fractions. The real numbers that are well approximable are precisely those that have arbitrarily large terms in their continued fraction expansion. For example, is well-approximable because its continued fraction expansion is

(Note that the pattern only appears from the third term onwards, so it’s really that has the interesting continued fraction expansion.) Every multiple of 2 appears in this continued fraction expansion, so there are arbitrarily large terms. The real numbers that are badly approximable, on the other hand, are those that have a maximum term in their continued fraction expansion. They include all quadratic irrational numbers (since those numbers have continued fraction expansions which are eventually periodic), as well as others. For example, the real number with the continued fraction expansion

is badly approximable. This distinction is the topic of the final year project I’m currently doing for my mathematics course at university.

I guess it would be possible to motivate the well approximable-badly approximable distinction in a similar way: note that a real number is rational if and only if there is an integer such that is an integer divisible by , and then go on to say that the closeness of rationality of an irrational number can be judged by how close the terms of the sequence are to integers that are multiples of . The well approximable numbers would be those for which there exist terms of the sequence arbitrarily close to integers. Of course, this is a lot more contrived.