Dirichlet’s approximation theorem

Dirichlet’s approximation theorem is a result about rational approximation. First, let’s derive a trivial bound on the error of the best rational approximation so that we can compare it with Dirichlet’s theorem.

If we approximate a real number $\alpha \in \mathbb{R}$ by a rational $\frac{p}{q}$ with $p\in \mathbb{Z}$, $q\in {\mathbb{N}}_{+}$, it is straightforward to see that there exists a $p\in \mathbb{Z}$ such that

If both $\alpha -\frac{p}{q}>\frac{1}{2q}$ and $\frac{p+1}{q}-\alpha >\frac{1}{2q}$, we could add the inequalities to get

The left side is obviously equal to $\frac{1}{q}$, so this is a contradiction. So either $0\le \frac{p}{q}-\alpha \le \frac{1}{2q}$ or $0\le \frac{p+1}{q}-\alpha \le \frac{1}{2q}$. So, we have proved the following lemma:

Lemma 1: Let $\alpha \in \mathbb{R}$. For any $q\in {\mathbb{N}}_{+}$ there exists a $p\in \mathbb{Z}$ such that

It follows from Dirichlet’s theorem that there exist infinitely many rationals $\frac{p}{q}$ such that $\left|\alpha -\frac{p}{q}\right|<\frac{1}{q^2}$. The quadratic order of the error turns out to be optimal; This is what Hurwitz’ theorem proves.

It seems that Dirichlet was fond of arithmetic progressions; Dirichlet’s most famous theorem is about arithmetic progressions, and they turn out to play an important role in the proof of this theorem as well.

Let $\alpha \in \mathbb{R}$. Now consider the sequence $0,\{\alpha \},\{2\alpha \},\{3\alpha \},...,\{N\alpha \}$, where $\{x\}=x-\lfloor x\rfloor$ (so $0\le \{x\}<1$ for any $x\in \mathbb{R}$). It turns out that if two fractional parts are close, we can find a good rational approximation to $\alpha$.

Say we have $|\{r\alpha \}-\{s\alpha \}|<ϵ$ for $r,s\in {\mathbb{N}}_0$. Expanding this with the definition of the fractional operator, we see

Where $p=\lfloor r\alpha \rfloor -\lfloor s\alpha \rfloor ,q=r-s$. Finally, dividing by $|q|$, we get

Noting that $q\le N$, we have proved the following lemma:

Lemma 2: Let $\alpha \in \mathbb{R}$. If $|\{r\alpha \}-\{s\alpha \}|<ϵ$ for natural numbers $r,s\in {\mathbb{N}}_0$, then there exists a rational $\frac{p}{q}\in \mathbb{Q}$ such that

for some $q\le N$

Now to prove Dirichlet’s theorem we just need to obtain a good bound $ϵ$ which we can then plug in this lemma. We can obtain such an $ϵ$ by splitting the interval $[0,1)$ up in $N$ equal parts. We then consider the $N+1$ terms of the sequence $0,\{\alpha \},\{2\alpha \},...,\{N\alpha \}$ and apply the pigeonhole principle: Since there are $N+1$ terms and only $N$ intervals, there is at least one interval with two terms in it, say $\{r\alpha \}$ and $\{s\alpha \}$, so that

Now, by lemma 2 there exists a rational approximation $\frac{p}{q}\in \mathbb{Q}$ of $\alpha$ that satisfies $|\alpha -\frac{p}{q}|<\frac{1}{Nq}$. So we have proved the following theorem:

Theorem (Dirichlet): Let $\alpha \in \mathbb{R}$. For any positive integer $N\in {\mathbb{N}}_{+}$, there exists a fraction $\frac{p}{q}\in \mathbb{Q}$ such that

Now suppose that for a given $\alpha \in \mathbb{R}$ the set $S_{\alpha }=\{\frac{p}{q}:|\alpha -\frac{p}{q}|<\frac{1}{q^2}\}$, (with each fraction $\frac{p}{q}$ irreducible) is finite. Then $N={\max }_{\frac{p}{q}\in S_{\alpha }}(q)$ exists. This implies that there is no $\frac{p}{q}\in \mathbb{Q}$ such that $|\alpha -\frac{p}{q}|<\frac{1}{Nq}$. This contradicts Dirichlet’s theorem, so we conclude that our assumption that $S_{\alpha }$ is finite was wrong.

Corollary: For any $\alpha \in \mathbb{R}$, there are infinitely many rational numbers $\frac{p}{q}\in \mathbb{Q}$ such that