Knuth's up-arrow notation

For people who check facts

In mathematics, Knuth's up-arrow notation is a notation for very large integers introduced by Donald Knuth in 1976. The idea is based on iterated exponentiation in much the same way that exponentiation is iterated multiplication, and multiplication is iterated addition.

Table of contents

1 Introduction
2 Notation
3 Definition
4 Generalizations
5 See also
6 External links

Introduction

Multiplication can be defined as iterated addition:

and exponentiation can be defined as iterated multiplication:

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

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,

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.

A further notation used in this article is ↑ⁿ to indicate an n-arrow operator.

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 of such operators. For example, a↑b↑c = a↑(b↑c), not (a↑b)↑c.

Generalizations

Some numbers are so large that Knuth's up-arrow notation becomes too cumbersome to describe them. Graham's number is an example. The hyper operators or Conway chained arrow can then be used.

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.