Tag Archives: diophantine approximation

What Dirichlet had to do with the pigeonhole principle

Suppose you have six pigeons. You want to put them into five holes. Then at least one of the holes must contain more than one pigeon.

This simple idea is a very important mathematical principle known as the pigeonhole principle, or sometimes Dirichlet principle, Dirichlet’s box principle etc. If you have come across this you have probably wondered (like me) why it is named after Dirichlet, or how exactly did he use it. Dirichlet was one of the most prominent mathematicians of all time, having many important things named after him. E.g.

  1. Dirichlet’s theorem on arithmetic progressions that says any arithmetic progression a, a+d, a+2d,\dots, where a and d are integers sharing no common factor greater than 1, must contain infinitely many prime numbers.
  2. Dirichlet’s unit theorem, a result about the units in the ring of integers of an algebraic number field.
  3. Dirichlet L-function, a generalisation of the Riemann Zeta function.
  4. The Dirichlet conditions for a Fourier series.
  5. And many, many more.

When I first came to know that the pigeonhole principle was credited to Dirichlet, I was curious as to what Dirichlet had to do with it. A number theory lecture from last term happened to shed some light on it. First we need to know some basic facts about rational approximations.

We know that any real number has arbitrarily good rational approximations: just take the decimal expansion and truncate it anywhere. The more digits, the better the approximation. However, there is a different notion of a ‘good rational approximation’ in number theory.

Let \alpha be a real number. A way of measuring how good a rational number p/q approximates \alpha is to check how small |q\alpha-p| is. We say that p/q is a best approximation to \alpha if for any integers p' and 0<q'<q we have |q'\alpha-p'|>|q\alpha-p|.

Dirichlet proved the following theorem using his principle:

Theorem. (Dirichlet) Let \alpha be a real number. Then for any integer N>1 there exist integers p,q with 0<q<N such that

\displaystyle|q\alpha-p|<\frac 1N.

Proof. By \{x\} and \lfloor x\rfloor we respectively denote the fractional part and integer part of the real number x. E.g.
\{20/3\}=2/3,
\lfloor 20/3\rfloor=6,
\{\pi\}=\pi-3=0.1415926535\dots,
\lfloor \pi\rfloor=3 etc.

Note that x=\lfloor x\rfloor+\{x\}.

Consider the numbers 0,1,\{\alpha\}, \{2\alpha\},\dots,\{(N-1)\alpha\}. These are N+1 numbers all lying between 0 and 1 (inclusive). Divide the interval [0,1] into the N intervals [0,1/N], [1/N, 2/N],\dots,[(N-1)/N, 1]. Since we have N intervals and N+1 numbers each lying in one of these, the pigeonhole principle says that there must be two numbers lying in the same interval. Then the difference of these two numbers must be less than 1/N, the length of the interval.

If one of the two numbers is 1, then 1/N>|\{m\alpha\}-1|=|m\alpha-(\lfloor m\alpha\rfloor+1)| for some m, so take p=\lfloor m\alpha\rfloor+1 and q=m. Otherwise, let the two numbers be \{m\alpha\},\{n\alpha\} with N-1\ge m>n\ge 0. Then

\displaystyle \quad |\{m\alpha\}-\{n\alpha\}|<\frac 1N
\displaystyle \Rightarrow |(m\alpha-\lfloor m\alpha\rfloor)-(n\alpha-\lfloor n\alpha\rfloor)|<\frac 1N
\displaystyle \Rightarrow |q\alpha-p|<\frac 1N

where p=\lfloor m\alpha\rfloor-\lfloor n\alpha\rfloor and q=m-n, with 0<q<N, as required. \square

Advertisements

Leave a comment

Filed under Combinatorics, Number theory