Home > Knuth's up-arrow notation

1 Introduction

and exponentiation can be defined as iterated multiplication:

which inspired Knuth to define a 'double arrow' operator for iterated exponentiation:

Here and below evaluation is to take place from right to left.

According to this definition,

etc.

This already leads to some pretty big numbers, but Knuth didn't stop here. He went on to define a 'triple arrow' operator for iterated application of the 'double arrow' operator:

followed by a 'quad arrow' operator:

and so on. The general rule is that an n-arrow operator expands into a series of (n − 1)-arrow operators. Symbolically,

Examples:

2 Notation

In expressions such as a^b, the notation for exponentiation is usually to write the exponent b as a superscript to the base number a. But many environments—such as programming languages and plain-text e-mail— do not support such two-dimensional layout. People have adopted the linear notation a↑b for such environments; the up-arrow suggests 'raising to the power of'. If the character set doesn't contain an up arrow, the caret ^ is used instead.

The superscript notation a^b doesn't lend itself well for generalization, which explains why Knuth chose to work from the inline notation a↑b instead.

3 Generalizations

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator ↑ⁿ is useful (and also for descriptions with a variable number of arrows), or equivalently, hyper operators.

Some numbers are so large that even that notation is not sufficient. Graham's number is an example. The Conway chained arrow can then be used: a chain of three elements is equivalent with the other notations, but a chain of four or more is even more powerful.

It is generally suggested that Knuth's arrow should be used for relatively smaller magnitude numbers, and the chained arrow or hyper operators for larger ones.

4 Definition

The up-arrow notation is formally defined by

for all integers a, b and n with b ≥ 0 and n ≥ 1.

All up-arrow operators (including normal exponentiation, a↑b) are right associative, i.e. evaluation is to take place from right to left in an expression that contains two or more such operators. For example, a↑b↑c = a↑(b↑c), not (a↑b)↑c; for example

There is good reason for the choice of this right-to-left order of evaluation. If we used left-to-right evaluation, then a↑↑b would equal a↑(a↑(b-1)), so that ↑↑ would not be an essentially new operation. Right associativity is also natural because we can rewrite the iterated arrow expression that appears in the expansion of a↑ⁿ⁺¹b as , so that all the as appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.