Dirichlet's Approximation Theorem

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: We prove the case when $\alpha > 0$. Let $\mathrm{frac}(\alpha)$ be the fractional part of $\alpha$. Then:

(1)

\begin{align} \quad \mathrm{frac}(\alpha) = \alpha - \left \lfloor \alpha \right \rfloor \end{align}

• Consider the numbers $Q$-many numbers $\mathrm{frac}(\alpha)$, $\mathrm{frac}(2\alpha)$, …, $\mathrm{frac}(Q\alpha)$. All of these numbers are contained in $[0, 1)$. Also, consider the following partition of $[0, 1)$ into $Q + 1$ subsets:

(2)

\begin{align} \quad [0, 1) = \left [0, \frac{1}{Q + 1} \right ) \cup \left [ \frac{1}{Q + 1}, \frac{2}{Q + 1} \right ) \cup ... \cup \left [ \frac{Q}{Q+1}, 1 \right ) \end{align}

• The numbers $\mathrm{frac}(\alpha)$, $\mathrm{frac}(2\alpha)$, …, $\mathrm{frac}(Q\alpha)$ must satisfy at least one of the following cases.

• Case 1: Suppose there exists an $i$ with $i \in \{ 1, 2, ..., Q \}$ such that:

(3)

\begin{align} \quad \mathrm{frac}(i\alpha) \in \left [0, \frac{1}{Q+1} \right ) \end{align}

• Then $|\mathrm{frac}(i\alpha)| \leq \frac{1}{Q+1}$ and so by letting $a = \left \lfloor i \alpha \right \rfloor$ and $b = i$ we have that:

(4)

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

• Case 2: Suppose there is an $i$ with $i \in \{ 1, 2, ..., Q \}$ such that:

(5)

\begin{align} \quad \mathrm{frac}(i\alpha) \in \left [ \frac{Q}{Q+1}, 1 \right ) \end{align}

• Then $|\mathrm{frac}(i\alpha) - 1| \leq \frac{1}{Q+1}$ and so by letting $a = \left \lfloor i \alpha \right \rfloor + 1$ and $b = i$ we have that:

(6)

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

• Case 3: Suppose there exists $i, j$ not equal with $i, j \in \{ 1, 2, ..., Q \}$ such that for some $k \in \{ 1, 2, ..., Q - 1 \}$:

(7)

\begin{align} \quad \mathrm{frac}(i\alpha), \mathrm{frac}(j\alpha) \in \left [ \frac{k}{Q+ 1}, \frac{k+1}{Q+1} \right ) \end{align}

• Assume that $i < j$. Then $|\mathrm{frac}(j \alpha) - \mathrm{frac}(i \alpha)| < \frac{1}{Q+1}$ and so by letting $a = \left \lfloor j \alpha \right \rfloor - \left \lfloor i \alpha \right \rfloor$ and $b = j - i$ then:

(8)

\begin{align} \quad \left | \alpha - \frac{a}{b} \right | = \frac{1}{b} |b \alpha -a| = \frac{1}{b} |(j - i)\alpha - \left \lfloor j \alpha \right \rfloor - \left \lfloor i \alpha \right \rfloor | = \frac{1}{b}| \mathrm{frac}(j \alpha) - \mathrm{frac}(i\alpha)| \leq \frac{1}{b(Q+1)} \end{align}

• Note that at least one of case 1-3 must hold for if cases 1-2 do not hold, the pigeonhole principle guarantees 3 holds. So the theorem is proven. $\blacksquare$