Dirichlet's Approximation Theorem

Theorem

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

Then there exist integers $a, q$ such that:

$\gcd \left\{{a, q}\right\} = 1$, $1 \le q \le x$

and:

$\left|{\alpha - \dfrac a q}\right| \le \dfrac 1 {q x}$

Proof

It is sufficient to find $a, q$ not necessarily coprime.

Once such an $a, q$ have been found, then a coprime pair can be found by dividing numerator and denominator of $\dfrac a q$ by the GCD of $a$ and $q$.

Let $X = \left\lfloor{x}\right\rfloor$ be the integer part of $x$.

Let $\alpha_q = \alpha q - \left\lfloor{\alpha q}\right\rfloor \in \left[{0 \,.\,.\, 1}\right)$ for $q = 1, \ldots, X$.

Consider the disjoint real intervals:

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

Suppose there exists $q$ such that:

$\alpha_q \in \left[{0 \,.\,.\, \dfrac 1{X+1}} \right)$

Then:

$0 \le \alpha q - \left\lfloor{\alpha q}\right\rfloor < \dfrac 1 {X+1}$

Hence:

$\left|{\alpha - \dfrac{\left\lfloor{\alpha q}\right\rfloor} q}\right| < \dfrac 1 {q \left({X + 1}\right)} < \dfrac 1 {q x}$

Taking $a = \left\lfloor{\alpha q}\right\rfloor$, the construction is complete.

$\Box$

Suppose that not to be the case, but suppose that there exists $q$ such that:

$\alpha_q \in \left[{\dfrac X {X + 1} \,.\,.\, 1}\right)$

Then similarly:

$\dfrac X {X+1} < \alpha q - \left\lfloor{\alpha q}\right\rfloor < 1$

so:

$-\dfrac 1 {X+1} < \alpha q - \left\lfloor{\alpha q}\right\rfloor - 1 < 0$

and:

$\left|{\alpha - \dfrac {\left\lfloor{\alpha q}\right\rfloor + 1} q}\right| < \dfrac 1 {q \left({X+1}\right)} < \dfrac 1 {q x}$

Taking $a = \left\lfloor{\alpha q}\right\rfloor + 1$, again the construction is complete.

$\Box$

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 \left\{{2, \ldots, X}\right\}$ and $q_1 < q_2$ such that: :$\alpha_{q_1}, \alpha_{q_2} \in I_{k_0}$

Then for $i = 1, 2$:

$\dfrac{k_0 - 1} {X + 1} \le \alpha q_i - \left\lfloor{\alpha q_i}\right\rfloor < \dfrac {k_0} {X+1}$

Therefore:

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

and therefore:

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

Taking $a = \left\lfloor{\alpha q_2}\right\rfloor - \left\lfloor{\alpha q_1}\right\rfloor$ and $q = q_2 - q_1$ the construction is complete.

$\blacksquare$

Source of Name

This entry was named for Johann Peter Gustav Lejeune Dirichlet.