Dirichlet's Approximation Theorem

In this explanation, we enter a pursuit of finding a good approximation for some irrational number $\alpha$. A good approximation means getting very close to $\alpha$, using a fraction with a relatively small denominator.

A very simple first idea to do this is to notice that if we mark all the fractions with denominator $q$ on the real line, $\alpha$ will fall into one of the resulting small intervals of length $1/q$. If we take the endpoint $\alpha$ is closer to as $p/q$, then $\alpha$ will be at most $1/(2q)$ distance from it. That is because the marked fractions are $\frac{1}{q}$ apart, and all other numbers are in between two of these fractions.

For each value of $q$, there exists a $p$ such that

$$\left|\alpha-\frac{p}{q}\right|\le \frac1{2q}.$$

In this case we can choose $p$ depending on $q$.

We feel this is quite loose because it allows us the luxury of being able to take $q$ to be any number we want. With this estimate, if we want to find a rational number at most $0.0001$ distant from $\alpha$, we need to look at fractions with denominators at least $5000$. Dirichlet's approximation theorem approaches us with a tradeoff: it guarantees very good approximations, but there might be only very few of them.

Dirichlet's approximation theorem. For any irrational $\alpha$, there exist infinitely many pairs of integers $p,q$ for which

$$\left|\alpha-\frac pq\right| < \frac1{q^2}.$$

For example, if we want a fraction at most $0.0001$ far from $\alpha$, we may even do this with a denominator not larger than $100$.

For convenience, we will state a Lemma before the proof, which is obvious when visualized on the number line.

Lemma. Let $\{\cdot\}$ denote the fractional part. Then there is an integer with distance $d=|\{x\}-\{y\}|$ from $|x-y|$.

Proof. Write $x=x_1+x_2$ and $y=y_1+y_2$ where $x_2,y_2$ are the fractional parts of $x,y$. (Like dividing with remainder by $1$.) Without loss of generality, assume $x_2\ge y_2$, then $d=x_2-y_2$. Also, $x-y=(x_1-y_1)+d$, so if $|x-y|=x-y$, then it is $d$ far from $x_1-y_1$, and if $|x-y|=y-x$, then it is $d$ far from $-(x_1-y_1)$. $\blacksquare$

We will now prove the theorem using nothing more advanced than the pigeonhole principle. To do this, we rather consider multiples of $\alpha$ - we should multiply our inequality by $q$ to get $|q\alpha-p|\le 1/q$. This in fact removes $p$ from the picture, as the minimum of $|q\alpha-p|$ only depends on the fractional part of $q\alpha$. (It helps a lot here to imagine the number line.)

Now, we will fix some positive integer $N$ and consider the fractional parts of the numbers $0,\alpha,2\alpha,...,N\alpha$. Stick them into this collection of $N$ intervals

$$\left[0;\frac 1N\right),\left[\frac1N,\frac2N\right),...,\left[\frac{N-1}N,1\right).$$

There are $N+1$ numbers and $N$ intervals, thus some two fractional parts fall into the same interval, say $\{x\alpha\}$ and $\{y\alpha\}$. From the Lemma, $|x-y|\cdot \alpha$ is less than $\frac1N$ distant from some integer $p$.

Here, $|x-y|$ is a positive integer not larger than $N$. Choose it to be $q$, then what we found is

$$|q\alpha-p|<\frac1N\le \frac1q,$$

which proves the theorem.

Or does it?

We have found one such $q$, but why would there be infinitely many? This follows quickly from an seemingly obvious observation: the proof of Dirichlet's theorem in fact guaranteed a $q\in[1;N]$ such that $|q\alpha-p|<1/N$. Now if we choose $N$ large enough for $1/N$ to be smaller than $|q\alpha-p|$, the reasoning of the proof must generate a different $p,q$. And so on, we may generate arbitrarily many good pairs $p,q$ in this manner.

In the rest of the explanation, we generalize this proof to approximating many irrational numbers at once.

Dirichlet's approximation theorem for simultaneous approximation. Consider irrational numbers $\alpha_1,\alpha_2,...,\alpha_k$. There then exist infinitely many $q$ with integers $p_1,p_2,...,p_k$ satisfying

$$\left|\alpha_i-\frac{p_i}q\right|<\frac1{q^{1+1/k}},$$

i.e. $|q\alpha_i-p_i|<1/(q^{1/k})$ for $i=1,2,...,k$.

Proof. The procedure is exactly the same, except now, we consider integers in $[0;N^k]$. Look at the $N$ intervals

$$I_1=\left[0;\frac 1N\right),I_2=\left[\frac1N,\frac2N\right),...,I_N=\left[\frac{N-1}N,1\right).$$

To each integer $x\in[0;N^k]$, let's assign a $k$-tuple of intervals, whose $i$-th interval is the $I_j$ which $x\alpha_i$ belongs to ($i=1,2,...,k$).

We are looking at $N^k+1$ different integers, but only $N^k$ possible $k$-tuples, thus some $x$ and $y$ are assigned the same $k$-tuple, and $\{x\alpha_i\}$ and $\{y\alpha_i\}$ are within $1/N$ of each other. The Lemma implies that $|x-y|\cdot \alpha_i$ is less than $1/N$ distant from some integer $p_i$ for each $i=1,...,k$.

Hence, we may take $q=|x-y|$. This gives $q\le N^k$, so now for each $i$, $q\alpha_i$ is at most $1/N\le 1/(q^{1/k})$ distant from some integer $p_i$.

Infinitely more $q$ can be generated the same way as in the $k=1$ case.

Read through the proofs again. Where did we use irrationality?

Motivation

The motivation of Dirichlet's approximation theorem is relatively well known: say that we want to calculate $\sqrt{2}$, perhaps to impress our friends with our ability to memorize large runs of numbers. Now, how would we go about expanding this to say, the tenth decimal place? One way would be to use the square root algorithm, but if we think deeper, we can use something called rational approximation For the given problem, say that we wanted to approximate $\sqrt{2}$ to the 2nd decimal place. To add to the challenge, let's say that we have a machine which can only multiply integers by integers, but it does those at a great speed. Moreover, say that it takes integer square roots (it rounds square roots down). This is pretty easy to do: Take the square root of $2*10^6$, and we've got a number like $1414$. Then, just divide by $1000$, and we get a number like $1.41$. Now this was pretty easy, and we managed to approximate a number to within two decimal places. The thing is, we usually want reasonably small numerators and denominators (else we can't store the numbers effectively, right?)

Easy approximation

The main claim of this section is that, given an irrational $\alpha$, we can find a fraction $\dfrac{p}{q}$ such that $0 \le \alpha - \dfrac{p}{q} \le \dfrac{1}{q}$. The proof is not too bad: fix $p$ starting at zero. If the inequality is false, keep incrementing $p$ until it satisfies the required. The proof that this eventually terminates is left to the reader. The key idea here is that we have approximated $\alpha$ with a fraction $\dfrac{p}{q}$ such that

$$\left| \dfrac{p}{q} - \alpha \right| \le \frac{1}{q}.$$

Why the above is insufficient

The above approximation is usually not enough, given how easily it was derived. Luckily for us, we can use some bigger weaponry. This is how Dirichlet approximation came about. Dirichlet states that given an irrational $\alpha$, it is true that there exists a rational number $\dfrac{p}{q}$ such that

$$\left |\alpha - \dfrac{p}{q} \right| \le \dfrac{1}{q^2}.$$

This is a significant improvement, and the proof is fairly interesting:

Proof of Dirichlet's approximation theorem.

(This proof is taken from Po-Shen Loh, who occasionally browses expii and may see this some day.)

We slightly recast the problem we were given in a more convenient form:

Given any integer $n$, show that there exists an integral $q$ with $1 \le q \le n$ such that there exists an integer where $\mid \alpha - \frac{p}{q} \mid \le \frac{1}{nq}$. This is obviously a significant improvement from the above! Now, this proof requires the pigeonhole principle, so I will try and explain it using this as an example.

Consider the set of $\{ j\alpha \}$ where $j$ runs from $0$ to $n$. There are $n+1$ of these numbers. We now create $n$ buckets for where these numbers may lie: call them $[ 0, \frac{1}{n} )$, $[\frac{1}{n}, \frac{2}{n})$, and so on. Observe that there are $n+1$ numbers and only $n$ buckets, so two of them lie in the same bucket. Say that ${a'x}$ and ${ax}$ lie in the same bucket, and WLOG ${ax} < {a'x}$. So the idea is here that there must be some integer $p$ where $0 \le a'x - ax - p \le \frac{1}{n}$, by the definition of the intervals. Let the denominator $q = a'-a$, and now we have $$p \le qx \le \dfrac{pn+1}{n}$$. Subtract $p$ and divide by $q$ to get $0 \le x - \dfrac{p}{q} \le \dfrac{1}{qn} \le \dfrac{1}{q^2}$, which was desired.

The future of this field?

One may think that maybe in the future, we will be able to get results like

$$\left| \alpha - \dfrac{p}{q} \right| \le \dfrac{1}{q^3}$$

perhaps with more sophisticated methods. However, this isn't possible for well behaved $\alpha$, for any exponent greater than $2$. This statement is the Thue-Siegel-Roth theorem, which states that for $\alpha$ which are algebraic integers, the well behaved irrationals like $\sqrt{2}$,

$$\left|\alpha - \frac{p}{q}\right| < \frac{1}{q^{2 + \epsilon}}$$

has only finitely many solutions for any $\epsilon > 0$. This proof won Roth a Fields Medal in 1958.