|
|
|
Viewing Version
3
of
'Dirichlet's approximation theorem'
|
[ view 'Dirichlet's approximation theorem'
|
back to history
]
| Title of object: |
Dirichlet's approximation theorem |
| Canonical Name: |
DirichletsApproximationTheorem |
| Type: |
Theorem |
| Created on: |
2002-12-13 03:12:23 |
| Modified on: |
2006-04-09 13:25:47 |
| Classification: |
msc:11J04 |
| Keywords: |
Dirichlet diophantine approximation |
| Synonyms: |
Dirichlet's approximation theorem=Dirichlet approximation theorem |
Revision comment (for changes between this and next version):
| Changes for correction #10533 ('contains own proof'). |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts} |
Content:
\PMlinkescapeword{unit}
Theorem (Dirichlet, c. 1840): For any real number $\theta$ and any integer
$n\ge 1$, there exist integers
$a$ and $b$ such that $1 \le a \le n$ and
$ \arrowvert a\theta-b \arrowvert \le \frac{1}{n+1}$.
Proof: We may assume $n\ge 2$.
For each integer $a$ in the interval $[1,n]$, write
$r_a = a\theta - [a\theta] \in [0,1)$, where $[x]$ denotes
the greatest integer less than $x$. Since the $n+2$
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}$.
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.
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
$[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
$a=l-k$ respectively, we get
\[ \arrowvert r_a - c \arrowvert \le \frac{1}{n+1} \]
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.
The same statement, but with the weaker conclusion
$ \arrowvert a\theta-b \arrowvert < \frac{1}{n}$,
admits a slightly shorter proof, and is sometimes also referred to
as the Dirichlet approximation theorem. (It was that shorter proof
which made the ``pigeonhole principle'' famous.) Also, the theorem
is sometimes restricted to irrational values of $\theta$, with the
(nominally stronger) conclusion
$\arrowvert a\theta-b \arrowvert < \frac{1}{n+1}$. |
|
|
|
|
|
