Dirichlet's Approximation Theorem

Theorem

Let $\alpha, x \in \R$.

Then there exist integers $a,q$ such that $\gcd(a,q) = 1$, $1 \leq q \leq x$, and

$\displaystyle \left| \alpha - \frac aq \right| \leq \frac1{qx}$

Proof

Clearly it is sufficient to find $a$, $q$ not necessarily coprime (simply cancel the greatest common divisor of $a$ and $q$).

Let $X = \lfloor x \rfloor$ be the integer part of $x$.

Let $\alpha_q = \alpha q - \lfloor \alpha q \rfloor \in [0,1)$, $q = 1,\ldots, X$.

Consider the disjoint intervals

$I_k = \left[\frac{k-1}{X + 1}, \frac k{X+1} \right),\quad k=1,\ldots, X + 1$

If there exists $q$ such that $\alpha_q \in \left[0, \frac 1{X+1} \right)$ then

$\displaystyle 0 \leq \alpha q - \lfloor \alpha q \rfloor < \frac 1{X+1}$

hence

$\displaystyle \left|\alpha - \frac{\lfloor \alpha q \rfloor}q \right| < \frac 1{q(X+1)} < \frac 1{qx}$

so we are done, taking $a = \lfloor \alpha q \rfloor$.

Similarly if there exists $q$ such that $\alpha_q \in \left[\frac{X}{X + 1}, 1 \right)$ then

$\displaystyle \frac X{X+1} < \alpha q - \lfloor \alpha q \rfloor < 1$

so

$\displaystyle -\frac 1{X+1} < \alpha q - \lfloor \alpha q \rfloor - 1 < 0$

and

$\displaystyle \left|\alpha - \frac{\lfloor \alpha q \rfloor + 1}q \right| <\frac 1{q(X+1)} < \frac 1{qx}$

so we take $a = \lfloor \alpha q \rfloor + 1$.

If neither of the above cases holds, then the $X-1$ remaining intervals $I_k$ contain the $X$ values of $\alpha_q$.

Therefore, by the Pigeonhole Principle, there are $k_0 \in \{2,\ldots, X\}$ and $q_1 < q_2$ such that $\alpha_{q_1},\alpha_{q_2} \in I_{k_0}$.

Then for $i = 1,2$,

$\displaystyle \frac{k_0 -1}{X+1} \leq \alpha q_i - \lfloor \alpha q_i \rfloor < \frac{k_0}{X+1}$

Therefore,

$\displaystyle \left| \alpha q_2 - \alpha q_1 - \lfloor \alpha q_2 \rfloor + \lfloor \alpha q_1 \rfloor \right| < \frac 1{X+1}$

and therefore

$\displaystyle \left| \alpha - \frac{\lfloor \alpha q_2 \rfloor - \lfloor \alpha q_1 \rfloor}{q_2 - q_1} \right| < \frac 1{(X+1)(q_2 - q_1)} < \frac 1{x(q_2 - q_1)}$

So we are done, taking $a = \lfloor \alpha q_2 \rfloor - \lfloor \alpha q_1 \rfloor$, $q = q_2 - q_1$ .

$\blacksquare$

Source of Name

This entry was named for Johann Lejeune Dirichlet.