My favorite number

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

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 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).

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 N^* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any n>=N^*, a complete graph K_4 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 n and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find N^* the smallest n 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.

Advertisements

3 responses to “My favorite number

  1. skeptical scientist

    “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 g operation 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 not an example of what can be done with primitive recursion, though 3↑↑↑↑3 is.

  2. Pingback: Perfect numbers | Irrational Inquiries

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s