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: 3^{3}, 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

3↑(3↑(3↑(3↑(….(3↑(3↑3))….)))),

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 10^{100} 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↑^{2}3, and 3↑↑↑↑3 is 3↑^{4}3.

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↑^{4}3, or 3↑↑↑↑3, also known as “huge”.*g*(2) is 3↑^{3↑↑↑↑3}3. 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↑↑↑↑33}3. 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).

Yes, sixty-four.

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.

“It demonstrates what can be done with the power of primitive recursion alone.”I don’t think that’s really true. To define g(64) the way you did, you have to first define g, which, while recursive (and defined recursively), actually grows too fast to be primitive recursive. (It’s like the Ackermann function in this regard.)

And now that I look it up and remind myself exactly what the primitive recursive functions are, I see that you’re completely right. And in fact I even basically said this without realizing it in the post (“The

goperation grows faster than …. any of the functions in that sequence”). I guess I’d forgotten how limited they were.So you’re right, that’s

notan example of what can be done with primitive recursion, though 3↑↑↑↑3 is.Pingback: Perfect numbers | Irrational Inquiries