Knuth's Up Arrow Notation and Graham's Number

Sometimes we have to deal with really big numbers in mathematics. You've probably heard of a googol (after which Google the company named itself) which is 10^100, ie. 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, but while this mind-blowingly massive it is a small fry compared with most of numbers that we are going to deal with in this article. Other famous points of comparison are the number of atoms in the observable universe which is 10^80 give or take an order of magnitude and 10^123 which is a pretty good estimate for the total number of distinct chess games that could exist.

The next named number that people usually come across is that of a googolplex, which is 10^googol, so 1 followed by a googol of 0s. Again, really big compared with any comparison you could relate to physical things in the universe, but still basically nothing compared with Graham's Number. To give you an impression of how big a number Graham's really is we are going to have to learn a new notation.

Enter Donald Knuth and his up arrow notation. While there are various different ways to define notation capable of what we are about to do (John Conway of Game of Life had another popular one) Knuth's up arrows have become the international standard. It starts by recognising that repeated addition is just multiplication and that repeated multiplication is just exponentiation (taking things to powers). At its simplest level the Up Arrow notation works just like normal powers like this:

However, when we extend the notation with multiple arrows we get something like this:

The number before the arrows is the base that we are doing the powers to while the number afterwards says how tall the stack of powers is. I've given an example just to show you how big the numbers get with these stacks. In fact 3||4 gives math error on the calculators even for these tiny integers. This operation is called tetra traction and you can think of it as repeated exponentiation ion

However we can extend the notation. By putting more than two Up Arrows in a row we can chain the concept. The general formula linking each further arrow to the number of arrows below it is given as:

An iterative formula for the general form

They quickly reach sizes that we can only really write in terms of other arrow notations, but let's look at one of the smallest examples:

Even with both a and b picked to be really small, we get a stack of powers which is really tall

I do all of this to give you some context to just how large the number we are about to deal with is.

Let's think about shapes in different dimensions for a moment. 0D doesn't have any dimensions so would just be a single point in space. When we move up to 1D we can define a line and then by moving that at 90 degrees to itself in a second dimension we can get to a square. Moving that perpendicular to itself once again we can define a cube; but there is no mathematical reason to stop there. The jump to 4D no longer fits with the 3D world we happen to be embedded in, but we can still define it mathematically by tracing out the path of a cube moving perpendicular to all 3 of its dimensions:

In practice we can talk about the equivalent of cubes in any dimension. If we look at the number of vertices on each then we have 1, 2, 4, 8, 16... 2^n. Imagine that for each graph we connected every vertex to every other vertex (we call this a complete graph), so this includes all of the weird diagonals.

There is a classic problem in graph theory that starts by colouring in every edge of some dimension of complete cube (so with 2^n vertices as above) either red or blue. For every size n do we always get at least one plane somewhere on the n-cube which has all lines the same colour? This plane will be made out of 4 vertices all connected to each other, but it could be at some weird angle (especially for the higher graphs).

The cube above has been coloured, but there is one plane (which is shown below it) which is all the same colour. However if we switched the very bottom edge of that plane to blue instead then no plan would be of the same colour. For the smaller dimensions it is fairly easy to find a colouring that avoids having a plane of the same colour, but as the dimension gets bigger it gets harder and harder to visualise.

In 1971 Ronald Graham (who incidentally was a close friend of Erdős, popularising the concept of Erdős numbers and was a terrific juggler so he will pop up again on this website) and Bruce Lee Rothschild managed to prove that there was a dimension n at which there was a plane of one colour no matter how you coloured it. In their first proof they found bounds on which dimension was the first counterexample, so 6<n<Graham's number. I.E. the first case where the pattern breaks is anywhere between 6 and a quite large* constant.

Graham's number is written as:

The number of arrows in each layer is the value of the layer below. The very bottom layer is already bigger than any number you can imagine.

For a long time this number held the record for the largest number used in a serious mathematical proof. We have since upped the lower limit for n to be 13, but to say that the answer to a problem is somewhere between 13 and Graham's Number is pretty much the same as saying that the answer is above 13.

We've managed to work out the last digits of Graham's Number and Wikipedia has the last 500 or so. It ends in a 7, which part of me just finds funny; the futility of working out a few digits in an unimaginably big sea of them.

*This is just about the biggest understatement I have ever made.