## You are here

HomeDirichlet's approximation theorem

## Primary tabs

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

## Mathematics Subject Classification

11J04*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove that for any sets A, B, and C, An(BUC)=(AnB)U(AnC) by St_Louis

Apr 20

new image: information-theoretic-distributed-measurement-dds.png by rspuzio

new image: information-theoretic-distributed-measurement-4.2 by rspuzio

new image: information-theoretic-distributed-measurement-4.1 by rspuzio

new image: information-theoretic-distributed-measurement-3.2 by rspuzio

new image: information-theoretic-distributed-measurement-3.1 by rspuzio

new image: information-theoretic-distributed-measurement-2.1 by rspuzio

Apr 19

new collection: On the Information-Theoretic Structure of Distributed Measurements by rspuzio

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

## Comments

## related problem

Hi, I'm a new member and i am interested in the following closely related problem. Suppose you are given a real number r and a bound c>0. What does the set of all natural (or integral) numbers a satisfying |a*r-b| <= c for some integer b look like? Has this set any structure makes it easy to deal with it? Does anybody know if there are any good upper or lower bounds for the cardinality of the intersection of this set with a fixed interval [i1,i2]?

Would be great if anybody could help! Thanks in advance!

## Re: related problem

If r is distinct from zero, you can divide the inequality by |r|, getting

|A-b/r| <= c/|r|.

Thus A may be any integer between b/r-c/|r| and b/r+c/|r|.

Regards,

Jussi

## Re: related problem

Thank You for your fast reply!

>>Thus A may be any integer between b/r-c/|r| and b/r+c/|r|

In the problem i meant the integer b is not fixed but depends on the choice of A (resp. a in my first post). That is, given real r and c>0, we are looking for all positive integers A for which A*r is not too far away from the nearest integer.

I did some experiments yesterday using Mupad. The result: the A's seem to have a regular behavior relative to their succesive differences. For example if we look at the first 500000 multiples of r=0.2703567032 (1*r,...,500000*r), so we get 10016 possible values for A with A*r at most 1/100 away from the nearest integer. I've numbered these A's and considered the succesive differences A_(i+1)-A_(i) and discovered that each of them takes one of the tree

possible values 122, 85 and 37 (notice that 122=85+37; this was true in all my considered examples except of them where fewer than 3 values were taken; there were never more than 3 possible values for the succesive differences, but it may be when we consider more then 500000 multiples). With the above r and c I get the first 100 succesive differences as below:

[37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37,

37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

122, 37, 37, 37, 37, 37, 37, 85, 37, 37, 37, 37, 37, 37, 122, 37,

37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37,

37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122,

37, 37, 37, 37]

while the 101 in the middle are

[37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

122, 37, 37, 37, 37, 37, 37, 85, 37, 37, 37, 37, 37, 37, 122, 37,

37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 37, 85, 37, 37,

37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37,

37, 37, 122, 37, 37]

and number 915-1015:

[37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 37,

85, 37, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37,

37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122,

37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 37, 122, 37, 37, 37,

37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37,

37, 37, 37, 37, 122, 37, 37, 37, 37, 37, 122, 37, 37, 37, 37, 37,

37, 85, 37, 37, 37].

The same setting with r:=0.8142678572 yields 1000 desirable A's among the first 500000 integers with the successive differences as follows:

Number 1-100:

[70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70,

70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70,

70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 70,

43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 70, 43,

27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 43, 27, 43,

27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 43]

Number 450-550:

[43, 27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 70, 43, 27, 43,

27, 43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27,

43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27,

43, 27, 43, 27, 43, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27,

43, 27, 43, 70, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43,

27, 43, 70, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43]

and number 899-999:

[27, 43, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43,

27, 43, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43,

70, 70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70,

70, 70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70,

70, 70, 70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70, 70,

70, 70, 70, 43, 27, 43, 27, 43, 27, 43, 27, 43, 27, 43, 70, 70].

Is there anything known about these A's in the literature? Is there a formula describing it? Any ideas?

Greetings,

eddik