Dirichlet's Approximation Theorem
Theorem
Let $\alpha, x \in \R$.
Then there exist integers $a, q$ such that:
- $\gcd \set {a, q} = 1$, $1 \le q \le x$
and:
- $\size {\alpha - \dfrac a q} \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 = \floor x$ be the integer part of $x$.
Let $\alpha_q = \alpha q - \floor {\alpha q} \in \hointr 0 1$ for $q = 1, \ldots, X$.
Consider the disjoint real intervals:
- $I_k = \hointr {\dfrac{k-1} {X + 1} } {\dfrac k {X + 1} }, \quad k = 1, \ldots, X + 1$
Suppose there exists $q$ such that:
- $\alpha_q \in \hointr 0 {\dfrac 1 {X + 1} }$
Then:
- $0 \le \alpha q - \floor {\alpha q} < \dfrac 1 {X + 1}$
Hence:
- $\size {\alpha - \dfrac {\floor {\alpha q} } q} < \dfrac 1 {q \paren {X + 1} } < \dfrac 1 {q x}$
Taking $a = \floor {\alpha q}$, the construction is complete.
$\Box$
Suppose that not to be the case, but suppose that there exists $q$ such that:
- $\alpha_q \in \hointr {\dfrac X {X + 1} } 1$
Then similarly:
- $\dfrac X {X + 1} < \alpha q - \floor {\alpha q} < 1$
so:
- $-\dfrac 1 {X + 1} < \alpha q - \floor {\alpha q} - 1 < 0$
and:
- $\size {\alpha - \dfrac {\floor {\alpha q} + 1} q} < \dfrac 1 {q \paren {X + 1} } < \dfrac 1 {q x}$
Taking $a = \floor {\alpha q} + 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 \set {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$:
- $\dfrac {k_0 - 1} {X + 1} \le \alpha q_i - \floor {\alpha q_i} < \dfrac {k_0} {X + 1}$
Therefore:
- $\size {\alpha q_2 - \alpha q_1 - \floor {\alpha q_2} + \floor {\alpha q_1} } < \dfrac 1 {X + 1}$
and therefore:
- $\size {\alpha - \dfrac{\floor {\alpha q_2} - \floor {\alpha q_1} } {q_2 - q_1} } < \dfrac 1 {\paren {X + 1} \paren {q_2 - q_1} } < \dfrac 1 {x \paren {q_2 - q_1} }$
Taking $a = \floor {\alpha q_2} - \floor {\alpha q_1}$ and $q = q_2 - q_1$ the construction is complete.
$\blacksquare$
Source of Name
This entry was named for Johann Peter Gustav Lejeune Dirichlet.