Dirichlet's approximation theorem DirichletsApproximationTheorem 2002-12-13 03:12:23 2006-10-10 09:04:21 Theorem Dirichlet diophantine approximation \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \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}$.