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<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\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
Canonical name	DirichletsApproximationTheorem
Date of creation	2013-03-22 13:15:37
Last modified on	2013-03-22 13:15:37
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	7
Author	Koro (127)
Entry type	Theorem
Classification	msc 11J04
Synonym	Dirichlet approximation theorem
Related topic	IrrationalityMeasure