by Jonathan Kujawa
On the occasion of Richard Guy's 100th birthday.
Human beings have a talent for spotting patterns. No doubt this was handy in our early days. If both Ug and Oka were violently ill after eating purple berries from a particular bush, our clan was well served to notice and avoid those berries in the future. If anything, evolution encourages us to be overly quick to infer patterns. Better safe than sorry. No need for a double blind, randomized trial with a large sample size when life and death are on the line.
Our keen sense for what is random and what is not works both for and against us. After all, as we saw last month, it was Pick's keen eye for patterns which lead him to discover his beautiful formula. For an easier example, let's write down the first few numbers of the Fibonacci sequence:
1,1,2,3,5,8,13,21,34,….
It only takes a minute to spot the rule used to generate these numbers. With a little more time we can even guess exactly which ones are even and which ones are odd [2].
Now imagine I tell you that I flipped two coins twenty-one times and got:
Coin A: TTTTHTTHHTTHTTTTHHHTT,
Coin B: HTTHTTHTTHTTHTTHTTHTT.
You would have to be an awfully trusting person to believe that both are fair coins and that I faithfully flipped and recorded the results. Our pattern seeking brain notices the regularity of Coin B. It violates our sense of what a “random” sequence of coin flips should look like. Mathematically we know each string of coins flips is equally likely. But even the most steely mathematician would be hard pressed to bet against Coin B next coming up heads.
A great icebreaker on the first day of teaching is to ask the students generate two lists of 100 coin flips: one by flipping a real coin and one by hand. Even though they do this while the instructor is out of the room, the instructor invariably can identify which is list is which. The secret is to look for long runs of heads, tails, or other patterns (like Coin B). Since all outcomes are equally likely to the coin it will happily generate strings of heads in a row. Human brains, however, notice such patterns and veto them in their effort to fake a random sequence of heads and tails. There is a running joke on this theme in Rosencrantz and Guildenstern Are Dead.
Our brain isn't entirely wrong. There is something strange going on, but it's not what we've been talking about. The Strong Law of Large numbers tells us that as a sequence of truly random independent events (like coin flips) occurs, the running average should tend towards the average value. In the case of coin flips, if we're counting a heads as a -1 and a tails as a +1, then the long run average of a fair coin should tend towards zero. On this measure both Coin A and Coin B are equally sketchy. Both have 7 heads and 14 tails, so have an average of 7/21=1/3. While I'm not going to flip the table and draw pistols quite yet, I'm definitely suspicious of the fairness of these coins.
The problem is that our brains are too good at detecting patterns. We love nothing better than a good conspiracy theory. The truly faithful readers of this column [3] will remember F. P. Ramsey's Marvelous Theorem. Ramsey showed that patterns and structure are impossible to avoid if you have a sufficiently complicated data set. But surely it can't be a coincidence that the latitude of the Great Pyramid of Giza is 29.9792458° N and the speed of light in a vacuum is 299,792,458 meters/sec? [4].
As a warning against such bold leaps in pattern spotting the mathematician Richard Guy formulated his Strong Law of Small Numbers (LSN):
There aren't enough small numbers to meet the many demands placed upon them. — Richard Guy
While Ramsey's theorem is about patterns occurring by virtue of the massiveness of a data set, the LSN is about coincidences from there being too few numbers to go around. There are two people in New York City with exactly the same number of hairs on their head. Not because of some deep mystical connection, but simply because the number of people in NYC greatly exceeds the number of possible hair counts.
Guy introduced his Law in a tongue-in-cheek paper and its sequel. Between the two he gave no less than eighty examples of patterns which appear to follow some rule, but eventually fail. Just to keep the reader honest, Guy also threw in a few true results :-). As Guy warned us,
[The LSN] is the constant enemy of mathematical discovery: at once the Scylla, shattering sensible statement with spurious exceptions, and the Charybdis of capricious coincidences, causing careless conjectures…
Some fooled the best of us. For example, it is known that if 2k-1 is a prime number, then k itself must be a power of two. So k must be 2,4,8,16,… Fermat looked at the numbers of this form:
3, 5, 17, 257, 65537, 4294967297, 18446744073709551617,…
He noticed that the first five were prime numbers. Seduced by the siren song of the LSN, Fermat conjectured that all numbers of this form are prime. Unfortunately for him, soon after Fermat made his conjecture the more industrious Euler rolled up his sleeves and confirmed that 4294967297 factors into the product of 641 and 6700417. Now that we have computers we can test Fermat's “primes”. It turns other than Fermat's original five, every other one we've tested is not prime! At the moment, the primeness of Fermat's numbers is a wide open question. We don't know if they all factor, if infinitely many are prime, or somewhere in between.
Guy has lots of great examples. Here's another one. Other than 2, every prime number is odd. This means it can either be written as 4k-1 or 4k+1. In the mid 1800s Chebyshev noticed something strange. If you keep a running total of how many primes are of the form 4k-1 versus 4k+1, the former were always in the lead. In fact the two kinds of primes are equally likely. Fifty or so years after Chebyshev first noticed this phenomenon, Littlewood proved that the running totals change lead infinitely often as you go further and further out in the primes.
A striking example is Euler's famous polynomial n2+n+41. It gives you a prime number for every n between 0 and 39 before finally failing when n hits 40. Another polynomial of this kind, n2+79n+1601, gives primes for every n between 0 and 79!
Guy's examples come from across mathematics. Here are two from geometry:
In both cases, the first few are 1, 1, 2, 5, and 14. These are the first five Catalan numbers. The mountain range problem is in fact given by the Catalan numbers (fitting as Richard Guy is an avid mountaineer), while the paper folding problem breaks the pattern at the next step.
The Catalan numbers are famous for counting all sorts of things in mathematics. Famously, Richard Stanley wrote a textbook on enumerative combinatorics (the counting of gadgets) in which there were 66 problems whose answer was the Catalan numbers. If you go to his webpage for the book you'll find that he's now up to 207 problems!
Richard Guy is a fantastic mathematician, wonderful human being, and an all around interesting person. There is an enjoyable interview with him in the book Fascinating Mathematical People (you can find an electronic copy here). He recently celebrated his 100th birthday. Despite the fact that he “retired” in 1982 he still goes in to the office nearly every day. As Guy put it, “I didn’t retire. They just stopped paying me.” Here's hoping we are all lucky enough to still love what we do when we're 100!
[1] Image from here.
[2] I'll leave it to you to spot the pattern. Once you notice the rule, it's not too hard to verify that it is always true using the fact that even+odd = odd, and odd+odd = even.
[3] Hi Mom!
[4] Spoiler: It is.