# Dirichlet’s approximation theorem

Theorem (Dirichlet, c. 1840): For any real number $\theta$ and any integer $n\geq 1$, there exist integers $a$ and $b$ such that $1\leq a\leq n$ and $\arrowvert a\theta-b\arrowvert\leq\frac{1}{n+1}$.

Proof: We may assume $n\geq 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\leq r_{k}-r_{l}\leq\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, 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\leq\frac{1}{n+1}$

where $c$ is $0$ or $1$, and the result follows.

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}$.

Title Dirichlet’s approximation theorem DirichletsApproximationTheorem 2013-03-22 13:15:37 2013-03-22 13:15:37 Koro (127) Koro (127) 7 Koro (127) Theorem msc 11J04 Dirichlet approximation theorem IrrationalityMeasure