Dirichlet’s approximation theorem


Theorem (Dirichlet, c. 1840): For any real number θ and any integer n1, there exist integers a and b such that 1an and |aθ-b|1n+1.

Proof: We may assume n2. For each integer a in the intervalMathworldPlanetmathPlanetmath [1,n], write ra=aθ-[aθ][0,1), where [x] denotes the greatest integer less than x. Since the n+2 numbers 0,ra,1 all lie in the same unit interval, some two of them differ (in absolute valueMathworldPlanetmathPlanetmathPlanetmath) by at most 1n+1. If 0 or 1 is in any such pair, then the other element of the pair is one of the ra, and we are done. If not, then 0rk-rl1n+1 for some distinct k and l. If k>l we have rk-rl=rk-l, since each side is in [0,1) and the differencePlanetmathPlanetmath between them is an integer. Similarly, if k<l, we have 1-(rk-rl)=rl-k. So, with a=k-l or a=l-k respectively, we get

|ra-c|1n+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 conclusionMathworldPlanetmath.

The same statement, but with the weaker conclusion |aθ-b|<1n, admits a slightly shorter proof, and is sometimes also referred to as the Dirichlet approximation theoremMathworldPlanetmath. (It was that shorter proof which made the “pigeonhole principleMathworldPlanetmath” famous.) Also, the theorem is sometimes restricted to irrational values of θ, with the (nominally stronger) conclusion |aθ-b|<1n+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