April 1, 2014 | 10
I was going to write an April Fool’s Day post with the title “Mathematicians Declare Graham’s Number Equal to Infinity.” Graham’s number is really big, but of course, it’s precisely 0% as big as infinity. On the other hand, everything we touch is finite, so in some sense, Graham’s number is probably “close enough” to infinity for doing most math. I didn’t end up writing that post because Graham’s number is too big for the post to be funny.
For example, here’s one of the paragraphs I would have written:
“The decision to round Graham’s number up to infinity promises to simplify the proof of the twin prime and Goldbach conjectures as well as other longstanding number theory problems: now they can be proved by checking the finite number of remaining cases.”
But this is where I got stuck. I wanted to tell you how many cases might be left to check for one of these number theory problems. Goldbach’s conjecture, which states that every even integer is the sum of two primes, is known to be true for numbers up to 1018. But Graham’s number minus 1018 is basically equal to Graham’s number. For all practical purposes, we’re 0% of the way to checking that the Goldbach conjecture is true for numbers up to Graham’s number.
Here is where I should tell you how big Graham’s number is. But I can’t.
Sometimes when we talk about big numbers, we talk about how many digits they have or, basically equivalently, write them in scientific notation involving some power of 10. A googol, for example, is 10^100, which has 101 digits. The largest known prime number has over 17 million digits. A googolplex is 10 raised to the googol power, so it has approximately a googol digits. It takes a while to write down a 1 followed by 100 zeroes, but we can do it.
But Graham’s number is different. I can’t tell you how many digits it has. I also can’t tell you how many digits its number of digits has, or how many digits the number of digits of its number of digits has. They’re all too big.
A couple years ago, Numberphile made a nice video on Graham’s number. The good folks in the video run into some of the same problems I did comprehending how big the number is.
The only way to describe Graham’s number involves some dense “up-arrow” notation. The Wikipedia page on the notation is a good resource if you’d like to read more.
Up-arrow notation is an extension of exponentiation. In the same way that exponentiation is iterated multiplication (and is denoted by one up-arrow), two up-arrows denotes iterated exponentiation, three up-arrows denotes iterated iterated exponentiation, and so on.
More concretely, a↑b is the usual exponential notation, ab=a×a×a.., for a total of b copies of a multiplied together. Adding a second arrow, so we have a↑↑b, means we take b copies of a in a tower of exponentials. An example is worth a thousand words: 4↑↑3=444. When we add yet another arrow, a↑↑↑b means “make b copies of a↑↑.” So 4↑↑↑3 means we do 4↑↑(4↑↑4). (There are three copies of the number 4, separated by the ↑↑ symbol.) The thing inside the parentheses is 4444, and then we raise 4 to the 4th power that many times. I can’t say much about that number because 4444 has 8×10153 digits, and we have to make a tower with that many powers of 4 in it.*
The important thing about up arrows is that they grow mind-bogglingly quickly. Exponentiation grows much more quickly than multiplication. 2×10 is just 20, but 2^10=1024. In the same way, each level of up-arrows grows much more quickly than the level before.
We can describe Graham’s number with an enormous stack of these up-arrows.
It’s easiest to think of this as an iterative process. We start at the bottom with g1=3↑↑↑↑3 and then creating the second row (call it g2) by having two threes separated by g1 up-arrows. Then g3 is two threes separated by g2 up-arrows, and so on, until g64 is Graham’s number. The only one of these numbers that I can hope to describe a little bit is g1=3↑↑↑↑3. Peeling the onion of up-arrow notation, we have 3↑↑↑↑3=3↑↑↑(3↑↑↑3). So far so good. The thing in parentheses, 3↑↑↑3, is 3↑↑(3↑↑3)=333, which is over 7.5 trillion. So to get g1, we have to do “↑↑” to 3 over 7.5 trillion times. It boggles the mind! Check out Wikipedia if you’d like to see some more details about the magnitude of g1. (Warning: your brain might explode.) I can’t even describe how large the first layer is, and each layer grows much more quickly than the last. The final number is totally beyond comprehension.
The origin of Graham’s number is one of those slightly legendary math stories. In 1977, Martin Gardner wrote, “In an unpublished proof, [mathematician Ronald] Graham has recently established … a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.” Graham had worked on a fairly complicated question about combinatorics. But Graham’s number doesn’t actually appear in the published proof of his result. The number he used was quite a bit smaller. In a Google+ post, John Baez describes both the combinatorics problem Graham was working on and where the number came from. He writes,
“I asked Graham. And the answer was interesting. He said he made up Graham’s number when talking to Martin Gardner! Why? Because it was simpler to explain than his actual upper bound – and bigger, so it’s still an upper bound!”
*This sentence was changed after publication to correct a numerical error. Thanks to Mike for pointing it out!