I’ll be back to my planned sequence soon—but first, a short diversion.
A long time ago, I saw in the Guinness Book of Records that the “largest number ever used in a serious mathematical proof” was called Graham’s number. I don’t recall whether I looked it up immediately after, or waited a while…. but when I finally did, I was surprised to find out that (1) I could understand exactly how it was constructed, and (2) my mind had been completely blown out of my skull.
Graham’s number is no longer the largest number ever used in a serious mathematical demonstration—that honor probably goes to Friedman’s TREE(3). But it’s still my favorite, since it demonstrates what can be done with the power of
primitive recursion alone.
And now, to the construction!
Remember, addition is repeated application of succession: for example, 3+3 is the same as next(next(next(3))), or 6.
And multiplication is repeated addition: 3⋅3 is the same as 3+(3+3), or 9.
And exponentiation is repeated multiplication: 33, which I’ll write as 3↑3 for the rest of this post, is 3⋅(3⋅3), or 27.
And in the last post we defined tetration as repeated exponentiation: 3↑↑3 is 3↑(3↑3), or 7,625,597,484,987.
I’m going to keep extending this notation further. Pentation is repeated tetration: 3↑↑↑3 is 3↑↑(3↑↑3), or 3↑↑7,625,597,484,987. If you try to turn that into regular exponentiation, you end up with
where there are exactly 7,625,597,484,987 instances of 3 in the chain.
How many digits are in that number? More than 0.47⋅(3↑↑7,625,597,484,986).
How many digits are in the number of digits in that number? More than 0.47⋅(3↑↑7,624,597,484,985).
For comparison, the number of protons in the universe is probably less than 3↑170. So if you were thinking of writing this number out, digit by digit, you may have some difficulty.
But even pentation isn’t enough for our purposes. We also need hexation, or repeated pentation: 3↑↑↑↑3 is 3↑↑↑(3↑↑↑3). Remember how big 3↑↑↑3 was? That was only a chain of exponentiations, 7,625,597,484,987 terms long. 3↑↑↑(3↑↑↑3) is a chain of tetrations, 3↑↑↑3 terms long!
If you hadn’t encountered it before now, 3↑↑↑↑3 is probably the largest number you’ve ever seen. It may be the largest number you ever even care to see. I can understand how it is constructed, but I don’t think I can truly appreciate its size—somewhere past 10100 or so, my brain just throws everything into a box labeled BIG.
Are we there yet? Is 3↑↑↑↑3 Graham’s number?
3↑↑↑↑3 isn’t even in the same ballpark as Graham’s number.
Before I go on, I’ll make a slight addition to my notation: ↑n will be shorthand for ↑↑↑↑….↑↑↑↑, where there are n up-arrows in the chain. For example, 3↑↑3 is 3↑23, and 3↑↑↑↑3 is 3↑43.
Now we’re ready to define a little operation I’ll call g. It is defined recursively as follows:
- g(0) is 4.
- g(next(n)) is 3↑g(n)3.
That’s it. To get an idea of how quickly g grows, let’s look at the first few terms of this sequence.
- g(1) is 3↑43, or 3↑↑↑↑3, also known as “huge”.
- g(2) is 3↑3↑↑↑↑33. That’s a three, then 3↑↑↑↑3 up-arrows, then another three. This number is too big to write out, even using up-arrows.
- g(3) is 3↑3↑3↑↑↑↑333. There’s not a whole lot I can say about this one, other than ouch.
The g operation grows faster than tetration. It grows faster than pentation. It grows faster than 1,000,000-ation. It grows faster than any of the operations in that sequence. It’s just ridiculous.
And now I’m ready to tell you what Graham’s number is. It’s g(64).
And that’s my favorite number.
Okay, I guess I could also tell you something about what it’s for. Graham’s number is an upper bound on a solution to a problem in Ramsey theory. Here’s the problem, according to MathWorld:
Let be the smallest dimension of a hypercube such that if the lines joining all pairs of corners are two-colored for any , a complete graph of one color with coplanar vertices will be forced. Stated colloquially, this definition is equivalent to considering every possible committee from some number of people and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find the smallest that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees (Hoffman 1998, p. 54).
Yeah, you don’t have to understand that. I can understand all the words, and I think once I held the whole question in my head at once, but even then I couldn’t understand why that particular question was interesting enough to ask.
What Ronald Graham did was to prove that this problem had a solution—and, more specifically, a solution less than or equal to g(64) above. This doesn’t mean the solution is that large, just that it’s no larger (and, more importantly, that it exists). Since then, Graham and Rothschild have published a much smaller upper bound on the solution, though even that one is obscenely huge.
So what’s the lower bound on the solution? At the moment, the best known is: 11.