| Version 3 |
Version 2 |
| \PMlinkescapeword{unit} |
\PMlinkescapeword{unit} |
| Theorem (Dirichlet, c. 1840): For any real number $\theta$ and any integer |
Theorem (Dirichlet, c. 1840): For any real number $\theta$ and any integer |
| $n\ge 1$, there exist integers |
$n\ge 1$, there exist integers |
| $a$ and $b$ such that $1 \le a \le n$ and |
$a$ and $b$ such that $1 \le a \le n$ and |
| $ \arrowvert a\theta-b \arrowvert \le \frac{1}{n+1}$. |
$ \arrowvert a\theta-b \arrowvert \le \frac{1}{n+1}$. |
|
|
|
Proof: We may assume $n\ge 2$.
|
Proof: We can suppose $n\ge 2$.
|
| For each integer $a$ in the interval $[1,n]$, write |
For each integer $a$ in the interval $[1,n]$, write |
| $r_a = a\theta - [a\theta] \in [0,1)$, where $[x]$ denotes |
$r_a = a\theta - [a\theta] \in [0,1)$. Since the $n+2$ |
| the greatest integer less than $x$. Since the $n+2$ |
|
| numbers $0, r_a, 1$ all lie in the same unit interval, some two |
numbers $0, r_a, 1$ all lie in the same unit interval, some two |
| of them differ (in absolute value) by at most $\frac{1}{n+1}$. |
of them differ (in absolute value) by at most $\frac{1}{n+1}$. |
| If $0$ or $1$ is in any such pair, then the other element of the |
If $0$ or $1$ is in any such pair, then the other element of the |
| pair is one of the $r_a$, and we are done. |
pair is one of the $r_a$, and we are done. |
| If not, then $0 \le r_k - r_l \le \frac{1}{n+1}$ for some distinct $k$ |
If not, then $0 \le r_k - r_l \le \frac{1}{n+1}$ for some distinct $k$ |
| and $l$. If $k>l$ we have $r_k - r_l = r_{k-l}$, since each side is in |
and $l$. If $k>l$ we have $r_k - r_l = r_{k-l}$, since each side is in |
| $[0,1)$ and the difference between them is an integer. Similarly, |
$[0,1)$ and the difference between them is an integer. Similarly, |
| if $k<l$, we have $1-(r_k - r_l) = r_{l-k}$. So, with $a=k-l$ or |
if $k<l$, we have $1-(r_k - r_l) = r_{l-k}$. So, with $a=k-l$ or |
| $a=l-k$ respectively, we get |
$a=l-k$ respectively, we get |
| \[ \arrowvert r_a - c \arrowvert \le \frac{1}{n+1} \] |
\[ \arrowvert r_a - c \arrowvert \le \frac{1}{n+1} \] |
| where $c$ is $0$ or $1$, and the result follows. |
where $c$ is $0$ or $1$, and the result follows. |
|
|
| It is clear that we can add the condition $\gcd(a,b)=1$ to the conclusion. |
It is clear that we can add the condition $\gcd(a,b)=1$ to the conclusion. |
|
|
| The same statement, but with the weaker conclusion |
The same statement, but with the weaker conclusion |
| $ \arrowvert a\theta-b \arrowvert < \frac{1}{n}$, |
$ \arrowvert a\theta-b \arrowvert < \frac{1}{n}$, |
| admits a slightly shorter proof, and is sometimes also referred to |
admits a slightly shorter proof, and is sometimes also referred to |
| as the Dirichlet approximation theorem. (It was that shorter proof |
as the Dirichlet approximation theorem. (It was that shorter proof |
| which made the ``pigeonhole principle'' famous.) Also, the theorem |
which made the ``pigeonhole principle'' famous.) Also, the theorem |
| is sometimes restricted to irrational values of $\theta$, with the |
is sometimes restricted to irrational values of $\theta$, with the |
| (nominally stronger) conclusion |
(nominally stronger) conclusion |
| $\arrowvert a\theta-b \arrowvert < \frac{1}{n+1}$. |
$\arrowvert a\theta-b \arrowvert < \frac{1}{n+1}$. |
