# Monthly Archives: February 2016

## Dirichlet’s approximation theorem

The definition of rational numbers is usually expressed as follows.

Definition 1 For every real number ${x}$, ${x}$ is rational if and only if there are integers ${p}$ and ${q}$ such that ${q \ne 0}$ and ${x = p/q}$.

Remark 1 For every pair of integers ${p}$ and ${q}$ such that ${q \ne 0}$, ${p/q = (p'/\gcd(p, q))/(|q|/\gcd(p, q))}$, where ${p' = p}$ if ${q > 0}$ and ${p' = -p}$ if ${q < 0}$. Therefore, the definition which is the same as Definition 1 except that ${q}$ is required to be positive and ${p}$ is required to be coprime to ${q}$ is equivalent to Definition 1.

However, there’s a slightly different way one can express the definition, which uses the fact that the equations ${x = p/q}$ and ${q x = p}$ are equivalent.

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

Remark 2 The definition which is the same as Definition 3 except that ${q}$ is required to be positive and ${q x}$ is required to be coprime to ${q}$ 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 ${x}$ is rational: iterate through the positive integers in ascending order, and for each positive integer ${q}$ check whether ${q x}$ 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 ${x}$ 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 ${x}$ is irrational, then none of the terms in the sequence ${\langle x, 2 x, 3 x, \dotsc \rangle}$ are integers. But how close to integers are the terms? The closer they are to integers, the closer to rational ${x}$ 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 ${\{|q x - p|: p \in \mathbf Z, q \in \mathbf N\}}$. Of course, this minimum may not even exist—it may be possible to make ${|q x - p|}$ arbitrarily small by choosing appropriate integers ${p}$ and ${q}$ such that ${q > 0}$. So the first question to answer is this: for which values of ${x}$ 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 ${x}$ and every positive integer ${n}$, there are integers ${p}$ and ${q}$ such that ${q > 0}$ and

$\displaystyle |q x - p| < \frac 1 n. \ \ \ \ \ (1)$

Proof: First, let us define some notation. For every real number ${x}$, let ${[x]}$ denote the greatest integer less than or equal to ${x}$ and let ${\{x\}}$ denote ${x - [x]}$. Note that the inequality ${0 \le \{x\} < 1}$ always holds.

Now, suppose ${x}$ is a real number and ${n}$ is a positive integer. The ${n + 1}$ real numbers 0, ${\{x\}}$, ${\{2 x\}}$, … and ${\{n x\}}$ are all in the half-open interval ${I = [0, 1)}$. This interval can be partitioned into the ${n}$ sub-intervals ${I_1 = [0, 1/n}$, ${I_2 = [1/n, 2/n)}$, \dots and ${I_n = [1 - 1/n, 1)}$, each of length ${1/n}$. These ${n + 1}$ real numbers are distributed among these ${n}$ 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 ${r}$ and ${s}$ such that ${\{r x\}}$ and ${\{s x\}}$ are in the same sub-interval and hence ${|\{r x\} - \{s x\}| < 1/n}$. Or, equivalently:

$\begin{array}{rcl} 1/n &>& \|\{r x\} - \{s x\}| \\ &=& |(r x - [r x]) - (s x - [s x])| \\ &=& |(r - s) x - ([r x] - [s x])|, \end{array}$

so if we let ${q = r - s}$ and ${p = [r x] - [s x]}$ we have ${|q x - p| < 1/n}$. And ${r}$ and ${s}$ can be chosen so that ${r < s}$ and hence ${q}$ is positive. $\Box$

Dirichlet’s approximation theorem says that for every real number ${x}$, ${q x - p}$ can be made arbitrarily small by choosing appropriate integers ${p}$ and ${q}$ such that ${q > 0}$, and hence the minimum of the set ${\{|q x - p|: p \in \mathbf Z, q \in \mathbf N\}}$ 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 ${|q x - p| < 1/n}$ is divided through by ${q}$ (which produces an equivalent inequality, given that ${q}$ is positive), the result is

$\displaystyle \left| x - \frac p q \right| < \frac 1 {n q}. \ \ \ \ \ (2)$

So Dirichlet’s approximation theorem can also be interpreted as saying that for every real number ${x}$ and every positive integer ${n}$, it is possible to find a rational approximation ${p/q}$ to ${x}$ (where ${p}$ and ${q}$ are integers and ${q > 0}$) whose error is less than ${1/(nq)}$. 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 ${n}$, it is possible to find a rational approximation ${p/q}$ to ${x}$ whose error is less than ${1/n}$—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, ${\mathbf Q}$, is dense in the set of all real numbers, ${\mathbf R}$.) 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 ${1/q}$ 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 ${1/q}$. A real number ${x}$ is said to be well approximable if and only if for every positive integer ${n}$, there are integers ${p}$ and ${q}$ such that ${q > 0}$ and

$\displaystyle |q x - p| < \frac 1 {n q}, \ \ \ \ \ (3)$

or, equivalently,

$\displaystyle \left| x - \frac p q \right| < \frac 1 {n q^2}. \ \ \ \ \ (4)$

Otherwise, ${x}$ 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, ${e}$ is well-approximable because its continued fraction expansion is

$\displaystyle [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, \dotsc]$

(Note that the pattern only appears from the third term onwards, so it’s really ${(e - 2)/(3 - e)}$ 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

$\displaystyle [1, 2, 1, 1, 2, 1, 1, 1, 2, \dotsc]$

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 ${x}$ is rational if and only if there is an integer ${q}$ such that ${q^2 x}$ is an integer divisible by ${q}$, and then go on to say that the closeness of rationality of an irrational number ${x}$ can be judged by how close the terms of the sequence ${\langle x, 4 x, 9 x, \dotsc \rangle}$ are to integers that are multiples of ${q}$. 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.