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 α∈R\alpha \in \mathbb{R} by a rational pq\frac{p}{q} with p∈Zp \in \mathbb{Z}, q∈N+q \in \mathbb{N}_+, it is straightforward to see that there exists a p∈Zp \in \mathbb{Z} such that
pq≤α≤p+1q \frac{p}{q} \leq \alpha \leq \frac{p + 1}{q}

If both α−pq>12q\alpha - \frac{p}{q} > \frac{1}{2q} and p+1q−α>12q\frac{p + 1}{q} - \alpha > \frac{1}{2q}, we could add the inequalities to get
(α−pq)+(p+1q−α)>1q (\alpha - \frac{p}{q})+ (\frac{p + 1}{q} - \alpha) > \frac{1}{q}

The left side is obviously equal to 1q\frac{1}{q}, so this is a contradiction. So either 0≤pq−α≤12q0 \leq \frac{p}{q} - \alpha \leq \frac{1}{2q} or 0≤p+1q−α≤12q0 \leq \frac{p + 1}{q} - \alpha \leq \frac{1}{2q}. So, we have proved the following lemma:

Lemma 1: Let α∈R\alpha \in \mathbb{R}. For any q∈N+q \in \mathbb{N}_+ there exists a p∈Zp \in \mathbb{Z} such that
∣α−pq∣≤12q \left| \alpha - \frac{p}{q} \right| \leq \frac{1}{2q}

It follows from Dirichlet’s theorem that there exist infinitely many rationals pq\frac{p}{q} such that ∣α−pq∣<1q2\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 α∈R\alpha \in \mathbb{R}. Now consider the sequence 0,{α},{2α},{3α},...,{Nα}0, \{ \alpha \}, \{ 2 \alpha \}, \{ 3 \alpha \}, ..., \{ N \alpha \}, where {x}=x−⌊x⌋\{ x \} = x - \lfloor x \rfloor (so 0≤{x}<10 \leq \{ x \} < 1 for any x∈Rx \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α}−{sα}∣<ϵ|\{ r \alpha \} - \{ s \alpha \}| < \epsilon for r,s∈N0r, s \in \mathbb{N}_0. Expanding this with the definition of the fractional operator, we see
∣(rα−⌊rα⌋)−(sα−⌊sα⌋)∣=∣qα−p∣<ϵ |(r \alpha - \lfloor r \alpha \rfloor) - (s \alpha - \lfloor s \alpha \rfloor)| = |q \alpha - p| < \epsilon

Where p=⌊rα⌋−⌊sα⌋,q=r−sp = \lfloor r \alpha \rfloor - \lfloor s \alpha \rfloor, q = r - s. Finally, dividing by ∣q∣|q|, we get
∣α−pq∣<ϵq \left| \alpha - \frac{p}{q} \right| < \frac{\epsilon}{q}

Noting that q≤Nq \leq N, we have proved the following lemma:

Lemma 2: Let α∈R\alpha \in \mathbb{R}. If ∣{rα}−{sα}∣<ϵ| \{ r \alpha \} - \{ s \alpha \} | < \epsilon for natural numbers r,s∈N0r, s \in \mathbb{N}_0, then there exists a rational pq∈Q\frac{p}{q} \in \mathbb{Q} such that
∣α−pq∣<ϵq \left| \alpha - \frac{p}{q} \right| < \frac{\epsilon}{q}

for some q≤Nq \leq N

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

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

Theorem (Dirichlet): Let α∈R\alpha \in \mathbb{R}. For any positive integer N∈N+N \in \mathbb{N}_+, there exists a fraction pq∈Q\frac{p}{q} \in \mathbb{Q} such that
∣α−pq∣<1Nq \left| \alpha - \frac{p}{q} \right| < \frac{1}{Nq}

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

Corollary: For any α∈R\alpha \in \mathbb{R}, there are infinitely many rational numbers pq∈Q\frac{p}{q} \in \mathbb{Q} such that
∣α−pq∣<1q2 \left| \alpha - \frac{p}{q} \right| < \frac{1}{q^2}