April 1, 2014 | 9

Evelyn Lamb is a postdoc at the University of Utah. She writes about mathematics and other cool stuff. Follow on Twitter Evelyn Lamb is a postdoc at the University of Utah. She writes about mathematics and other cool stuff. Follow on Twitter

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 10^{18}. But Graham’s number minus 10^{18} 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, a^{b}=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=4^{44}. 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 4^{444}, and then we raise 4 to the 4th power that many times. I can’t say much about that number because 4^{444} has 8×10^{153} 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 g_{1}=3↑↑↑↑3 and then creating the second row (call it g_{2}) by having two threes separated by g_{1} up-arrows. Then g_{3} is two threes separated by g_{2} up-arrows, and so on, until g_{64} is Graham’s number. The only one of these numbers that I can hope to describe a little bit is g_{1}=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)=3^{33}, which is over 7.5 trillion. So to get g_{1}, 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 g_{1}. (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!

Rights & Permissions

Add a Comment

You must sign in or register as a ScientificAmerican.com member to submit a comment.

Secrets of the Universe: Past, Present, Future

X
Here we go again SA.

Link to thisWhy are comments sometimes not showing up until logged in again?

My comment from 11:31 am 04/1/2014 did not show up until I logged in again.

I wonder if some form of “intellectual property theft” is not happening over to other sites?

Link to thisComments are moderated by me, the author of this blog. Your comment from 11:31 am 04/1/2014 was not approved because it was not related to this post.

Link to thisSo the first level is incomprehensible because it is 3 to the huge. What if we change the base to be something just a tad bit bigger than one? Like 1.1(up up up up)1.1?

Link to thisIs infinty-1 the same as infinty? Just wondered…

Link to thisaihardin,

Link to thisthere was a SciAm article in the 80′s about 1.1 being squared multiple times. (I may still have a hard copy somewhere.) Most electronic devices use binary arithmetic in floating point mode to do calculations. Turns out this was a simple test of the quality of the calculations. IIRC, the best in the article was able to compute 1.1 squared 27 times. I remember I had a Commodore 64 and while its calculator failed to reach 27 times it was much better than the IBM PC of that time.

Many devices fail to reach much beyond squaring 1.1 9 or 10 times before they begin to have round off errors.

enojy

ed

Evelyn,

Graham’s number is so mind boggling that I have reread this article a few times. Doing so today I see I don’t quite understand the Arrow notation. 3^^3=3^(3^3)=3^27. OK

now the question is how does the expansion for different numbers work. if 4^^3=4^(4^4), then is 3^^4=3^((3^3)^3)?

but isn’t that 3^(3^(3^3))= 3^^^^3 ?

Basically I thought the number of up arrows controlled the expansion, but now I think I’m wrong.

I’m posting rather than email because i thought others might have the same confusion.

Link to thisThanks for a great article.

ed

I agree, it’s pretty confusing. It’s recursively defined, with ^ meaning normal exponentiation. Two arrows means a stack of powers, so like you said, 4^^3=4^(4^4), and 3^^4=3^(3^(3^3)). In other words, the double arrow means to do the single arrow thing that many times. If we add another arrow, 3^^^4 means 3^^(3^^(3^^3)). The triple arrow means we should do the double arrow thing a certain number of times. Likewise, four arrows would mean doing the triple arrow thing a certain number of times. Unfortunately, the numbers grow so quickly using this notation that it’s really hard to get a handle on it. Maybe if you go through the examples on this wikipedia page, it will help: http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

Thanks for asking for clarification. I hope it helps other people who are confused!

Link to thisI’m a tad late, sorry. Great article.

Link to thisI too am fascinated by Graham’s number. I thought I would add that, FYI, recently it was reduced a great deal to less than 2^^^6 –

http://arxiv.org/abs/1304.6910