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.