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.
- Dirichlet’s theorem on arithmetic progressions that says any arithmetic progression , where and are integers sharing no common factor greater than , must contain infinitely many prime numbers.
- Dirichlet’s unit theorem, a result about the units in the ring of integers of an algebraic number field.
- Dirichlet L-function, a generalisation of the Riemann Zeta function.
- The Dirichlet conditions for a Fourier series.
- 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 be a real number. A way of measuring how good a rational number approximates is to check how small is. We say that is a best approximation to if for any integers and we have .
Dirichlet proved the following theorem using his principle:
Theorem. (Dirichlet) Let be a real number. Then for any integer there exist integers with such that
Proof. By and we respectively denote the fractional part and integer part of the real number . E.g.
Note that .
Consider the numbers . These are numbers all lying between and (inclusive). Divide the interval into the intervals . Since we have intervals and 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 , the length of the interval.
If one of the two numbers is , then for some , so take and . Otherwise, let the two numbers be with . Then
where and , with , as required.