A delightful pastime in mathematics is to think about really big numbers. And unlike many other mathematical mind games, this is one that has captured the imagination of a much wider community. It is fun to think about a million, a billion, or a trillion, and then picture how big they are, and how much bigger each subsequent number is than the previous one. This game is hard to continue, though, simply because we run out of names.
The next step is huge powers of ten. A thousand is
To get much bigger than that, we need to put larger numbers into the exponent. Like a thousand, or a billion, or a trillion. Or, hey, why not a googol? Yes, that number exists (of course) and it has a name: it’s called a googolplex:
It is indeed huge. It’s a 1 followed by a googol number of zeros! This game can of course be continued, but it’s a bit arid, since no new “mechanism” arises for making numbers bigger. So we need some novel mathematical notation.
The one I will introduce here is the “up-arrow notation”, invented by legendary mathematician and computer scientist Donald Knuth. It works like this: a single up-arrow, “
But we can iterate arrows! We can make sense of things such as
The best way to see how this works is to look at a few examples. For the most part, this is a repeated exercise of the last rule in this set:
In the last step we dropped the parenthesis, since people have agreed that the up-arrow notation should be right-associative, meaning, we parse things from right to left.
So what is
Repeated exponentiation is sometimes also called tetration. It creates stacked powers of powers, and is therefore sometimes called a “power tower”. Since
This is now the time where we can introduce a number which breaks everything we’ve seen so far, by a lot, and which is very famous both in mathematics and in many recreational circles of mathematicians who delight in such games. Knowing it, or at least having heard of it, has become a badge of recognition for the big number aficionados. We’re talking about Graham’s number.
Graham’s number is “made” in steps, and it uses the up-arrow notation for the steps of this construction. Let us begin with a short sequence of increasingly large numbers using increasingly more up-arrows:
Wow, that escalated quickly! We now have a ginormous number of up-arrows, and given that each single added arrow makes the number massively larger, the addition of a massive number of arrows absolutely truly and breathtakingly explodes the resulting number.
But wait, there’s more!
We can now define a new number,
In other words, we have incomprehensibly increased the number of arrows, blowing things again vastly into the beyond.
And we’re still not done. We now repeat this game 61 more times! Each time creating a new
At this point, the customary thing to do is to regale in extravagant language (and quite some hand gesticulation if done in front of a live audience) to express how mind-bogglingly big this number is. How incomprehensibly large, how utterly, blazingly, vastly gargantuan. But this is just incredibly lame rhetoric, as if human language were somehow more powerful to grasp the largeness of
But what I wanted to do here is to emphasize that basically the same I-give-up feeling occurs much earlier in the sequence of making Graham’s number. We don’t have to go all the way to the terrifying end before we must give up. Yes,
Let me show you how.
Recall the very first sequence of number we made?
Well, the first we had already calculated:
Using the rules from above, we find
Since we already know that double-up-arrows create a power tower, we realize that this is a truly huge power tower. It looks a bit like this:
So it’s a power tower that has
And there you have it. We just broke our brain. We gave up. We lied. We threw our hands in the air and said, hell, it doesn’t matter anymore.
What? What did we do?
We said, “A power tower with about 7.6 trillion 3s.” And that’s wrong. Because it’s really 7,625,597,484,987 occurrences of 3, not “just” 7.6 trillion. But you might say, “well, these numbers are close”. But these are the numbers of 3s in a power tower! How different does our result get if we quote our result approximately? What if we, as we did, neglected more than 25 billion occurrences of 3 in that tower?
To see what that means, here’s a helpful (and shocking) procedure. Recall what a logarithm does to a power:
It pulls the exponent out. That of course also works for power towers: it will pull the tower out. Let’s look at this in one example:
That means, we get a tower that is smaller by one occurrence of 3, and the result is then multiplied by
So let us recap: taking the logarithm of a power tower of 3s gives a new power tower of 3s that is one 3 shorter.
This now helps us to understand why I said we hopelessly capitulated when we described
Of course, we know that applying the logarithm makes huge numbers tiny. For instance, remember googol,
It’s really hard to conceive of numbers that are so big that a few logarithms wouldn’t cut them to size quite handily. For instance, take the smallest conceivable volume in the universe, the smallest one where we still feel that our current laws of physics apply: the Planck volume. It’s a cube with a side length of about
And now imagine a number so big that you can’t really bother to distinguish whether or not you took its logarithm 25 billion times.
See: you can’t imagine that. That’s my point.
And, I’d like to remind you that we haven’t even completed the last baby-step towards constructing Graham’s number. We haven’t even arrived at
The trouble is that most of us have no intuitive understanding of processes that would grow more rapidly than exponentiation. Of course, these exist in mathematics, where situations can be contrived where they show up. A famous subfield that is infested with such processes, and correspondingly huge numbers, is “Ramsey theory”—a branch of combinatorics that looks for certain patterns in substructures of bigger structures, and often asks questions such as: how big does a substructure have to be so that a certain property holds? Let us make one example.
Take a hypercube in
It’s not obvious, because we have no control over the original coloring. Maybe the person who colored the hypercube and its edges was particularly mean in the coloring strategy, such that simply no planar quartet exists that is of one color. But then, is that possible? Is it possible to create a coloring that has no unicolor quartets? Presumably that depends on the dimension
We know now, and that’s a famous theorem due to Ron Graham and Bruce Lee Rothschild, that for sufficiently small dimension, the person who colors he graph can always find a way to thwart our ability to ever find a unicolor quartet. But if the dimension is high enough, that mean spoilsport will not succeed in frustrating us, because no matter how they color the edges of the hypercube, we will always be able to find a unicolor quartet!
So how big is that mysterious dimension
And what’s the upper bound? At what dimension can we be sure that we will find a unicolor quartet, no matter how fiendishly the hypercube’s edges were colored? Well, one of the well know upper bounds is Graham’s number! At that number of dimensions you can be sure that the search will be successful! But that’s such a huge number! Well, that is the trouble with Ramsey theory! It has a habit of creating formidable combinatorial problems which can only be attacked with comparatively blunt instruments, which then lead to bounds that may be ludicrously large, and maybe also ludicrously far off. Graham and Rothschild later improved the bound, and made it much smaller. Recently John Mackey, a colleague of mine in the Department of Mathematical Sciences at Carnegie Mellon University, together with two other coworkers, reduced the upper bound to
That’s it for today. Now you know a bit more about Graham’s number. But I hope you also took away the idea that already the first modest baby-steps towards it basically break everyone’s brain. And isn’t that impressive all by itself?
Markus Deserno is a professor in the Department of Physics at Carnegie Mellon University. His field of study is theoretical and computational biophysics, with a focus on lipid membranes.
0 Comments