Knuth's up-arrow notation: expressing extremely large integers

Definition and basic examples

Knuth wrote a sequence of arrows between two integers to indicate repeated application of the previous level of operation. One arrow denotes ordinary exponentiation: a single arrow is equivalent to raising to a power. Two arrows denote tetration, three arrows pentation, and so on. A succinct recursive description is convenient:

• For n = 1, a ↑¹ b = a^b (ordinary exponentiation).
• For n > 1 and b = 1, a ↑ⁿ 1 = a (the single entry of a tower of height one is a itself).
• For n > 1 and b > 1, a ↑ⁿ (b + 1) = a ↑ⁿ⁻¹ (a ↑ⁿ b). This defines each level in terms of the previous level applied to the result of the same-level operation on a smaller second argument.

Examples that show how quickly values grow:

• 2 ↑ 3 = 2³ = 8.
• 2 ↑↑ 3 = 2 ↑ (2 ↑ 2) = 2 ↑ 4 = 16. Here ↑↑ denotes two arrows (tetration), which builds a power tower of three 2's: 2^(2^2).
• 3 ↑↑ 3 = 3 ↑ (3 ↑ 3) = 3 ↑ 27 = 3²⁷, a number with many digits.

Relation to the hyperoperation sequence

The up-arrow notation can be seen as a notation for higher hyperoperations beyond exponentiation. The hyperoperation list starts with addition (rank 1), multiplication (rank 2), exponentiation (rank 3), tetration (rank 4), and continues. Knuth's arrow count corresponds to rank: one arrow = rank 3, two arrows = rank 4, three arrows = rank 5, etc. This correspondence makes the notation useful in theoretical discussions of growth rates and the hierarchy of operations.

History, uses and notable facts

Knuth introduced the notation to give mathematicians and computer scientists a practical way to write and reason about iterated exponentials and higher operations without resorting to awkward verbal descriptions. It has since been used informally to name and compare extremely large numbers, and it appears in combinatorics and Ramsey theory where such sizes can arise. A famous application is the construction of Graham's number, which uses iterated up-arrows to describe a value vastly larger than numbers encountered in ordinary mathematics.

Variants, limitations and related notations

While Knuth's up-arrows are convenient for large integers, they are defined for nonnegative integer arguments and are not a direct extension to the real or complex numbers. Other notations and systems for very large numbers exist, such as Conway's chained arrow notation, Steinhaus–Moser notation and fast-growing hierarchies; each has different expressive power and convenience. The double-arrow form is commonly called tetration, and higher names (pentation, hexation, etc.) are used informally for more arrows. Practical computation with up-arrow expressions is generally impossible beyond the smallest cases because the values escalate too rapidly.

Note: The notation is primarily a tool for describing combinatorial or theoretical magnitudes rather than values to be explicitly computed; its main role is to make concise statements about the relative sizes of extremely large integers.