icon

Writing the unwritable: up-arrow notation

Rachel Thomas Share this page
Submitted by Marianne on 3 December, 2014
Knuth

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} \]    
  \[ \]    
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} \]    
  \[ \]    
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} \]    
  \[ \]    
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.

Knuth

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.

Read more about...
arithmetic

Comments

Permalink Submitted by Anonymous (not verified) on 27 June, 2015

Hey,

I was thinking of the similarity of this concept with the Indus and Harappan scripts.
If you look at their seals of which thousands have been found you'll see this up arrow being a vertical fish shape. So it's a multiplier.There are seals with 2 vertical fish between two other shapes which could be numbers. This is the same as the power tower concept! Has to be.

On some seals there is a vertical fish with an inverted v above it. This could be just be a replacement of the 2 up arrows.

So a horizontal line of the Harappan scripts on seals is just that. So many units of a product. Followed by its total price. Like an invoice.

The odd shaped further would be its destination. And person to hand over.

The other seals could be the money received as payment. This would-be indicated by the animal type beneath it.

Permalink Submitted by Anonymous (not verified) on 21 January, 2016

Hi Rachel.

The last two times you refer to the value of 2^16 above, you show it as 65,356 (which is clearly just a typo that slipped through). The correct value is of course 65,536, which you provided earlier.

Excellent article! Had never heard of Knuth's up-arrow notation until I came upon it during a video titled "What is the largest number?" (www.youtube.com/watch?v=e0xJwdcpATM)