Add new comment

Writing the unwritable: up-arrow notation

Donald Knuth.

We recently published an article about one of our very favourite numbers: Graham's number. One of the reasons we love it is that this number is big. So big in fact that the observable Universe is not big enough to write the number out in full. But it isn't just big, it's also precisely defined. And in order to define such mind-bendingly huge numbers you need a new way to write them down.

Graham's number can be exactly expressed thanks to an ingenious notation developed by the mathematician and computer scientist Donald Knuth. Knuth's up-arrow notation continues the compounding nature of the better-known arithmetic operations. Multiplication is simply repeated addition:

$\begin{array}{ccc} a \times b & = & \underbrace{a+a+\dots +a} \\ & & b\mbox{ copies of }a \end{array}$

$\text{[math]}$

So, for example, $2 \times 3 = 2+2+2 = 6$ .

Similarly exponentiation (raising a number to the power of another number) is just repeated multiplication:

$\begin{array}{ccc} a^ b & = & \underbrace{a \times a \times \ldots \times a} \\ & & b\mbox{ copies of }a \end{array}$

$\text{[math]}$

So this time our example might be $2^3 = 2 \times 2 \times 2 = 8$ .

Knuth developed an ingenious system that allows this process to carry on, defining infinitely many more levels of arithmetic operations. The first step was another way of expressing the familiar exponentiation. Knuth used a single up-arrow, $\uparrow$ , to represent this repeated multiplication:

$\begin{array}{ccccc} a \uparrow b & = & \underbrace{a \times a \times \ldots \times a} & = & a^ b. \\ & & b\mbox{ copies of }a \end{array}$

So our example becomes $2 \uparrow 3 = 2^3 = 8.$

Multiplication is repeated addition, exponentiation, represented by a single up-arrow, is repeated multiplication...so the next operation is repeated exponentiation, sometimes called a power tower, and notated with a double up-arrow, $\uparrow \uparrow$ :

$\begin{array}{ccccc} a\uparrow \uparrow b & = & \underbrace{a\uparrow (a\uparrow (\ldots (a\uparrow a)))} & = & \underbrace{a^{a^{.^{.^{.^ a}}}}}. \\ & & b\mbox{ copies of }a & & b\mbox{ copies of }a \end{array}$

So $a\uparrow \uparrow b$ produces a power tower of $a$ 's that is $b$ levels high. For example $2\uparrow \uparrow 3$ produces a power tower of 2s that is 3 levels high:

$2\uparrow \uparrow 3 = 2\uparrow (2\uparrow 2) = 2^{2^2}=2^4 = 16.$

And this process can be continued indefinitely, allowing us to create more and more arithmetic operations:

$\begin{array}{ccc} a\uparrow \uparrow \uparrow b & = & \underbrace{a\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\ & & b\mbox{ copies of }a \end{array}$

$\text{[math]}$

So our example might be:

$2\uparrow \uparrow \uparrow 3 = 2\uparrow \uparrow (2\uparrow \uparrow 2) = 2 \uparrow \uparrow (2\uparrow 2) = 2\uparrow \uparrow 4$

which is a power tower of 2s that is 4 levels high. We saw above that a power tower of 2s that is 3 levels high is equal to 16. A power tower of 2s that is 4 levels high is

$2\uparrow \uparrow 4 = 2\uparrow (2\uparrow (2\uparrow 2)) = 2^{2^{2^2}}=2^{2^4}=2^{16} = 65,536.$

You can see how quickly the double up-arrow operation, $\uparrow \uparrow$ , grows: $2\uparrow \uparrow 2=4$ , $2\uparrow \uparrow 3=16$ , $2\uparrow \uparrow 4 = 65,536$ , and $2\uparrow \uparrow 5$ is $2^{65,536}$ , at which point your calculator will give up the ghost.

The triple up-arrow operation grows even faster. We saw that $2\uparrow \uparrow \uparrow 3=65,536$ . But just taking the value of $b$ to be 4 rather than 3 gives

$2\uparrow \uparrow \uparrow 4 = 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2)) = 2 \uparrow \uparrow (2\uparrow \uparrow 4) = 2\uparrow \uparrow 65,536.$

This is a power tower of 2s that is 65,536 levels high. We'll leave you to calculate its exact value as an exercise for some insomnia-blighted night.

The sky's the limit with up-arrow notation.

This has already got out of hand from the point of view of numbers that we can actually comprehend. But just as mathematicians are quite happy thinking in arbitrarily high dimensions if the rules are clearly defined, they are quite happy to continue Knuth's nice, well-defined process of iterating the arithmetic operations. And so we can precisely define numbers, such as Graham's number, that are so enormous that there is not enough room in the observable Universe to write them. Mathematics gives us the power to define the unimagineable.

About the author

Rachel Thomas is Editor of Plus.

Plus.Maths.org

Writing the unwritable: up-arrow notation

About the author

Filtered HTML