Monday, October 27, 2014
Am I the only one around here?
by Carl Pierer
It is necessary that two men have the same number of hair, gold, and others.[i]
This meme is taken from a scene in the Cohen brother's 1998 comedy "The Big Lebowski". During a game of bowling, Walter, in the picture, gets annoyed at the other characters constantly overstepping the line. Drawing a gun, he asks: "Am I the only around here who gives a shit about rules?"[ii]
Considering that there are roughly 7 billion people on earth, a positive answer seems highly unlikely. But it is possible to do better. We can know with certainty, i.e. prove, that the creator of the meme is not the only one. This is a simple and straightforward application of a fascinating, intuitive and yet powerful mathematical principle. It is usually called "pigeonhole principle" (for reasons to be explained below) or "Dirichlet's principle".
The German mathematician Gustav Lejeune Dirichlet was born in 1805 in Düren, a small town near Aachen. Although Dirichlet was no child prodigy, his love for mathematics and studies in general became apparent early in his life. His parents had him destined for the career of a merchant, but upon his insisting to attend the Gymnasium (secondary school), they sent him to Bonn, at the age of 12. After only two years, he transferred to a Gymnasium in Cologne, where he studied mathematics with Georg Simon Ohm (1789-1854), who is famous for his discovery of Ohm's Law. Dirichlet left this school after only one year, with a leaving certificate in his pocket but without an Abitur, which would cause him some troubles later in his life. At that time, students were required to be able to carry a conversation in Latin to pass the Abitur examination. With only three years of secondary education, Dirichlet could not comply with this crucial requirement. However, Dirichlet was fortunate that no Abitur was required to study mathematics.
In May 1822, Dirichlet moved to Paris, where he studied at the Collège de France and at the Faculté des Sciences. Paris, at that time, was a mathematical hotbed: "Eminent scientists such as P.-S. Laplace (1749–1827), A.-M. Legendre (1752–1833), J. Fourier (1768–1830), S.-D. Poisson (1781–1840), A.-L. Cauchy (1789–1857) were active in Paris, making the capital of France the world capital of mathematics."[iii] At the same time, Dirichlet devoted himself to a close study of Gauß's famous Disquisitiones arithmeticae, which made a big impression on him.
His first publication, which is closely related to Fermat's Last Theorem, gained him instant recognition of the French Academy of Sciences. Further, he was given the chance to lecture to the members of the Academy on his current work, which fostered ties with Fourrier and Poisson. The two French scientists introduced the young German genius to Alexander von Humboldt (1769-1859), by then already world-famous and probably the most influential scientist in Prussia. With von Humboldt's help, Dirichlet secured a position at the University of Breslau (Silesia, now Wroclaw, Poland) and a chance for a Habilitation. This smooth ascension in the academic hierarchy was met with resentment, because Dirichlet fulfilled hardly any of the formal criteria: he had not studied at a Prussian university, his thesis was not written in Latin, and he was unable to defend it in public in Latin. After some back and forth, however, Dirichlet was awarded the degree of honorary doctor by the University of Bonn, which allowed him to take up the teaching position in Wroclaw.
This time in Wroclaw proved to be most productive for Dirichlet's research and he started a fruitful exchange with Gauß. After several further influential publications, both von Humboldt (Berlin) and Fourier (Paris) tried to woe Dirichlet for their respective cities. In 1831, he was formally transferred to Berlin. At the great salons held in Berlin, von Humboldt introduced Dirichlet to the extraordinarily creative Mendelssohn Bartholdy family. In 1832 Dirichlet was married to Rebecka Mendelssohn Bartholdy, sister to the renowned composers Fanny and Felix. One biographer reports a rather amusing anecdote about this first year of marriage:
Dirichlet was notoriously lazy about letter writing. He obviously preferred to settle matters by directly contacting people. On July 2, 1833, the first child, the son Walter, was born to the Dirichlet family. Grandfather Abraham Mendelssohn Bartholdy got the happy news on a buisiness [sic] trip in London. In a letter he congratulated Rebecka and continued resentfully: "I don't congratulate Dirichlet, at least not in writing, since he had the heart not to write me a single word, even on this occasion; at least he could have written: 2 + 1 = 3"[iv]
At first, Dirichlet taught exclusively at the newly founded Military School in Berlin, a commitment that would severely limit his time for research. Further, he applied for a teaching position at the University of Berlin, for which he was accepted in the year of his move to Berlin, despite lacking a Habilitation.
Since 1829, Dirichlet and Jacobi had been in close personal and professional contact. When Jacobi transferred from Königsberg (now Kaliningrad, Russia) to Berlin in 1844, these ties became even closer, so much so that they met on an almost daily basis.
This life was disrupted when the March revolution of 1848 came. As both Jacobi and Dirichlet fostered liberal political beliefs, they were highly suspicious to an increasingly conservative post-revolutionary government. The general opinion at the Military School had become reactionary, which put Dirichlet ill at ease. Furthermore, Jacobi's unexpected death of smallpox in 1851 was a tough personal blow.
After Gauß's death in 1855, Dirichlet received a call to the University of Göttingen, where he moved during the same year. There he came into contact with the next generation of mathematical brilliance, most notably R. Dedekind (1831-1916) and B. Riemann (1826-1866).
During a journey to Montreux, Switzerland, in the summer of 1858 Dirichlet suffered a heart-attack. At first he seemed to recover well. On 1 December of that year, however, his wife Rebecka died unexpectedly. It was clear to Dirichlet's friends that he would not survive this "turn of fate". Only a couple of months later, on 5th of May, Gustav Lejeune Dirichlet died.
There exist many formulations of the Dirichlet's principle, but a very simple one is the following: Suppose you have n holes (where n is a positive integer) and n+1 pigeons. Now, no matter how hard you try, it is impossible to fit all the pigeons into individual holes. There is at least one hole that contains two (or more). Similarly for hairs. The numbers vary of course, but an average blonde person is thought to have about 150'000 hairs on their head[v]. To be on the safe side, let us assume that the hairiest person on earth has 300'000 hairs. For ease of calculation, let us further assume that there are 7 billion people on earth. Then, at least two people will have the same number of hairs. Indeed, at least 23'333 people will do.
To demonstrate the truth of this rather obscure claim, suppose it is false; this means it is not the case that at least two people will have the same number of hairs. Say, we put the 7 billion people into a row, starting with the person of 0 hairs to our left and running up to the Guinness World Record Hairiest person of 300'000 hairs. So, person 1 has 0 hairs, person 2 has exactly one hair, etc., up to person 300'001, who holds the Guinness World Record. Now what about person 300'002? Remember she has to have 0,1,…,300'000 hairs (otherwise the World Record would be broken yet again!). But all those numbers of hairs are already taken by person 1 up to 300'001, so she necessarily has the same number of hairs as someone of them.
Of course, this is a rather silly application, but the principle can be generalised (in semi-mathematical terms): If you have two sets S and T, where S contains more elements than T, there is no way of assigning a single element in T to each element in S.
So far, we have only considered finite sets, but what happens if either S or T (or both) are infinite? The pigeonhole principle still applies, and has implicitly been put to use in some of G. Cantor's (1845-1918) most beautiful proofs, notably in his diagonal argument.
Although the principle is commonly attributed to Dirichlet, the principle crops up in the literature already in the 17th century. The sentence quoted at the beginning of this article comes from a book written by the French Jesuit Jean Leurechon in 1622, where it is mentioned without any further explanations. Leurechon was a teacher of mathematics at the university of Pont-à-Mousson and renowned for his book Selectae Propositiones, in which the sentence under discussion can be found.
We have seen that "it is necessary that two men have the same number of hair (…) as each other". Now, we started the inquiry with wishing to show the meme-creator of "Am I the only one around here who x" that she is definitely not the only one. To do so, we require two sets: (1) the set A, consisting of all people to whom "around here" applies and (2) the set B, consisting of all people "who x". Further, we need to know how many elements each set contains: for (1), since the meme is distributed on the internet and is thus accessible by an incredibly large number of people, we can assume that the set of "people around here" contains approximately 2.4 billion people[vi]. For (2), this is a bit more tricky, often impossible (especially in cases where the meme expresses a supposedly unpopular opinion – how could you possibly determine the number of people who do not share this opinion?). However, there are some cases in which this is possible, for example in the case of "Am I the only around here who doesn't listen to Skrillex?" Despite the fact that Skrillex is a very successful producer of sounds, his Facebook page has "only" (roughly) 20.000.000 likes [vii]. Giving him the benefit of the doubt, let us suppose that there are another 20 million people listening to Skrillex, who either don't like his page or don't know that they are listening to him. Even so, this set B clearly contains fewer elements than the set A (the potential audience of the meme), so, by the pigeonhole principle, we can deduce that there are at least two people who do not listen to Skrillex. Therefore, the confident answer is mathematically justified: "No, you are not."
[i] Cf: Rittaud, B. & Heefer, A.: "The Pigeonhole Principle, Two Centuries before Dirichlet" in The Mathematical Intelligencer 36 n°2 (June 2014), 27-29
[iii] Elstrodt, J.: "The Life and Work of Gustav Lejeune Dirichlet (1805-1859)" in Clay Mathematics Proceedings, Vol. 7, 2007.
Posted by Carl Pierer at 12:15 AM | Permalink