# 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.

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

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