Dirichlet's Approximation Theorem by Farey Sequences

The same Theorem is given on the Dirichlet's Approximation Theorem page. This page provides an alternate proof using Farey sequences.

Theorem 1 (Dirichlet's Approximation): If $\alpha \in \mathbb{R}$ and $Q \in \mathbb{N}$ then there exists $\displaystyle{\frac{a}{b} \in \mathbb{Q}}$ with $1 \leq b \leq Q$ such that $\displaystyle{\left | \alpha - \frac{a}{b} \right | \leq \frac{1}{b(Q+1)}}$.

• Proof: Let $x \in [0, 1)$. If $\alpha = \frac{a}{b} \in \mathbb{Q}$ then the proof is trivially true. So assume that $\alpha \in \mathbb{R} \setminus \mathbb{Q}$.

• Then for every $n \in \mathbb{N}$ the number $\alpha$ is between two consecutive Farey fractions. Let $\frac{a}{b}, \frac{c}{d}$ in $\mathcal F_Q$, $b, d \leq Q$ be such that:

(1)

\begin{align} \quad \frac{a}{b} < \alpha < \frac{c}{d} \end{align}

• Consider the interval $\left [ \frac{a}{b}, \frac{c}{d} \right ]$ at the point $\frac{a+c}{b+d}$. Then either:

• 1. $\frac{a}{b} < \alpha < \frac{a + c}{b + d}$.

• 2. $\frac{a + c}{b + d} < \alpha < \frac{c}{d}$.

• In the first case, observing that since $\frac{a + c}{b + d}$ are consecutive in $F_{\max {b, d}}$ we have that $|a(b + d) - b(a + c)| = 1$. Hence:

(2)

\begin{align} \quad \left | \alpha - \frac{a}{b} \right | \leq \left | \frac{a + c}{b + d} - \frac{a}{b} \right | = \frac{|(a + c)b - a(b + d)|}{(b + d)b} \leq \frac{1}{b(b + d)} \end{align}

• Also, observe that $b + d \geq Q + 1$ since otherwise $\frac{a}{b}, \frac{c}{d}$ are not consecutive in $\mathcal F_Q$. Hence:

(3)

\begin{align} \quad \left | \alpha - \frac{a}{b} \right | \leq \frac{1}{b(Q + 1)} \end{align}

• Similarly in the second case, $\frac{c}{d}$ takes the role of our approximation and we have that

(4)

\begin{align} \quad \left | \alpha - \frac{c}{d} \right | \leq \left | \frac{c}{d} - \frac{a + c}{b + d} \right | = \frac{|c(b + d) - d(a + c)|}{d(b + d)} \leq \frac{1}{d(b + d)} \leq \frac{1}{d(Q + 1)} \quad \blacksquare \end{align}

• And the result follows by the change of variables. $\blacksquare$