Knuth's up-arrow notation

In mathematics, Knuth's up-arrow notation is a method of notation of very large integers introduced by Donald Knuth in 1976. It is closely related to the Ackermann function. The idea is based on iterated exponentiation in much the same way that exponentiation is iterated multiplication, and multiplication is iterated addition.

Introduction

Multiplication by a natural number can be defined as iterated addition:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ copies of }a \end{matrix} .

For example,

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} 3\times 2 & = & \underbrace{3+3} & = & 6\\ & & 2\mbox{ copies of }3 \end{matrix} .

Exponentiation for a natural power Failed to parse (Missing texvc executable; please see math/README to configure.): b

can be defined as iterated multiplication:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b\mbox{ copies of }a \end{matrix} .

For example,

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} 3\uparrow 2= 3^2 = & \underbrace{3\times 3} & = & 9\\ & 2\mbox{ copies of }3 \end{matrix} .

This inspired Knuth to define a “double arrow” operator for iterated exponentiation or tetration:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\uparrow\uparrow b & = {\ ^{b}a} = & \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & = & \underbrace{a\uparrow a\uparrow\dots\uparrow a} \\ & & b\mbox{ copies of }a & & b\mbox{ copies of }a \end{matrix}

For example,

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} 3\uparrow\uparrow 2 & = {\ ^{2}3} = & \underbrace{3^3} & = & \underbrace{3\uparrow 3} & = & 27 \\ & & 2\mbox{ copies of }3 & & 2\mbox{ copies of }3 \end{matrix} .

Here and below evaluation is to take place from right to left (as such the operation is right-associative):

According to this definition,

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow2=3^3=27

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}

(just writing out this number in expanded form would require about 1.37 terabytes of storage space, i. e. Failed to parse (Missing texvc executable; please see math/README to configure.): 7,625,597,484,987 \times \frac{\log 3}{\log 2}
bits)

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7625597484987}}

etc.

This already leads to some fairly large numbers, but Knuth extended the notation. He went on to define a “triple arrow” operator for iterated application of the “double arrow” operator (also known as pentation):

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow a\uparrow\uparrow\dots\uparrow\uparrow a}\\ & b\mbox{ copies of }a \end{matrix}

followed by a 'quad arrow' operator:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\uparrow\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow\dots\uparrow\uparrow\uparrow a}\\ & b\mbox{ copies of }a \end{matrix}

and so on. The general rule is that an Failed to parse (Missing texvc executable; please see math/README to configure.): n -arrow operator expands into a series of (Failed to parse (Missing texvc executable; please see math/README to configure.): n - 1 )-arrow operators. Symbolically,

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b= a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow} \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a\ \dots \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow} \ a \\ \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ } \\ \qquad\qquad\quad\ \ b\mbox{ copies of }a \end{matrix}

Examples:

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7,625,597,484,987

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 3\uparrow3\uparrow3\mbox{ copies of }3 \end{matrix} \begin{matrix} = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & \mbox{7,625,597,484,987 copies of 3} \end{matrix}

Notation

In expressions such as Failed to parse (Missing texvc executable; please see math/README to configure.): a^b , the notation for exponentiation is usually to write the exponent Failed to parse (Missing texvc executable; please see math/README to configure.): b

as a superscript to the base number Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow 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 Failed to parse (Missing texvc executable; please see math/README to configure.): a^b

doesn't lend itself well for generalization, which explains why Knuth chose to work from the inline notation Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow b
instead.

In the context of the C programming language, the ^ character is the XOR operator. ** is a common alternative to Failed to parse (Missing texvc executable; please see math/README to configure.): \uparrow

for discussion in this context, using the same principle of two symbols meaning repetition of that operator. It is possible that *** could be equivalent to Failed to parse (Missing texvc executable; please see math/README to configure.): \uparrow\uparrow

, but this usage is uncommon.

Writing out up-arrow notation in terms of powers

Attempting to write Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow \uparrow b

using the familiar superscript notation gives a power tower. With b too large to write b numbers a, this requires using dots and a brace with the number b next to it, indicating the height of the power tower. Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow \uparrow \uparrow b
requires a row of such power towers, separated by braces: there are b power towers, including the last with height 1, hence simply the number a. If b is too large  to write all these power towers, we use dots to indicate a row of them, and for the number of power towers a "cross-brace" (the number of braces is one less). Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow \uparrow \uparrow \uparrow b
requires a row of such rows of power towers; there are b rows of power towers, including the last, which consists of only one "power tower" of height 1, so is simply the number a. If b is too large to write all these rows, we use a "cross-cross-brace" with this number b next to it (the number of cross-braces is one less). And so on.

Since the power notation is in direction "/", the braces are too. A row of them could be written in perpendicular direction "\", and the cross-brace too. A row of cross-braces could then extend in the direction "/", with a cross-cross-brace too, etc.

Example:

• For 4Failed to parse (Missing texvc executable; please see math/README to configure.): \uparrow\uparrow\uparrow

6 there are six power towers, including the last with height 1, hence simply the number 4; writing out the fifth power tower we have only five:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} \underbrace{\begin{matrix} \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ \underbrace{4^{4^{4^{.^{.^{.{4}}}}}}} \\ {4^{4^{4^{.^{.^{.{4}}}}}}} \end{matrix}} \\ {4^{4^{4^{4}}}} \end{matrix}

Using the left-superscript notation for tetration we have one "level of braces" less: Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow \uparrow \uparrow b

requires a "tetration tower" in the direction "\", and a brace with the number b next to it, indicating the height of the tetration tower. Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow \uparrow \uparrow \uparrow b
requires a row of such tetration towers, separated by braces: there are b tetration towers, including the last with height 1, hence simply the number a.  If b is too large to write all these tetration towers, we use a "cross-brace" with this number b next to it. And so on.

Examples:

• The previous example becomes

Failed to parse (Missing texvc executable; please see math/README to configure.): ^{^{^{^{^{4}4}4}4}4}4

• For the fourth Ackermann number Failed to parse (Missing texvc executable; please see math/README to configure.): 4 \uparrow \uparrow \uparrow \uparrow 4

there are four tetration towers, including the last with height 1, hence simply the number 4; writing out the third tetration tower we have only three:

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} \underbrace{\begin{matrix} \underbrace{^{^{^{^{^{^{^{4}.}.}.}4}4}4}4} \\ ^{^{^{^{^{^{^{4}.}.}.}4}4}4}4 \end{matrix}} \\ ^{^{^{^4}4}4}4 \end{matrix}

Generalizations

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator Failed to parse (Missing texvc executable; please see math/README to configure.): \uparrow^n

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 notation 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.

Failed to parse (Missing texvc executable; please see math/README to configure.): \begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix}

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.

Definition

The up-arrow notation is formally defined by

Failed to parse (Missing texvc executable; please see math/README to configure.): a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{if }n=1; \\ 1, & \mbox{if }b=0; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{otherwise} \end{matrix} \right.

for all integers Failed to parse (Missing texvc executable; please see math/README to configure.): a, b, n

with Failed to parse (Missing texvc executable; please see math/README to configure.): b \ge 0, n \ge 1

.

All up-arrow operators (including normal exponentiation, Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow 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, Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow b \uparrow c = a \uparrow (b \uparrow c) , not Failed to parse (Missing texvc executable; please see math/README to configure.): (a \uparrow b) \uparrow c

for example

Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow\uparrow 3=3^{3^3}

is Failed to parse (Missing texvc executable; please see math/README to configure.): 3^{(3^3)}=3^{27}=7625597484987
not Failed to parse (Missing texvc executable; please see math/README to configure.): \left(3^3\right)^3=27^3=19683.

There is good reason for the choice of this right-to-left order of evaluation. If we used left-to-right evaluation, then Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow\uparrow b

would equal

Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow (a \uparrow (b - 1)) , so that Failed to parse (Missing texvc executable; please see math/README to configure.): \uparrow\uparrow

would not be an essentially new operation.  

Right associativity is also natural because we can rewrite the iterated arrow expression Failed to parse (Missing texvc executable; please see math/README to configure.): a\uparrow^n\cdots\uparrow^na

that appears

in the expansion of Failed to parse (Missing texvc executable; please see math/README to configure.): a \uparrow^{n + 1}b

as

Failed to parse (Missing texvc executable; please see math/README to configure.): a\uparrow^n\cdots\uparrow^na\uparrow^n1 , so that all the Failed to parse (Missing texvc executable; please see math/README to configure.): a s appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.

Writing Failed to parse (Missing texvc executable; please see math/README to configure.): (a\uparrow ^m)^b

for the bth functional power of the function Failed to parse (Missing texvc executable; please see math/README to configure.): f(n)=a\uparrow ^m n
we have Failed to parse (Missing texvc executable; please see math/README to configure.): a\uparrow ^n b = (a\uparrow ^{n-1})^b 1

.

The definition could be extrapolated one step, starting with Failed to parse (Missing texvc executable; please see math/README to configure.): a\uparrow^n b= ab

if n = 0, because exponentiation is repeated multiplication starting with 1. Extrapolating one step more, writing multiplication as repeated addition, is not as straightforward because multiplication is repeated addition starting with 0 instead of 1. "Extrapolating" again one step more, writing addition of n as repeated addition of 1, requires starting with the number a. Compare the definition of the hyper operatorhttp://en.wikilib.com/wiki/Hyper_operator#Derivation_of_the_notation, where the starting values for addition and multiplication are also separately specified.

Tables of values

Computing Failed to parse (Missing texvc executable; please see math/README to configure.): 2\uparrow^m n

can be restated in terms of an infinite table. We place the numbers 2 Failed to parse (Missing texvc executable; please see math/README to configure.): n
in the top row, and fill the left column with values 2. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

Note: Failed to parse (Missing texvc executable; please see math/README to configure.): (10\uparrow)^k

denotes a functional power of the function Failed to parse (Missing texvc executable; please see math/README to configure.): f(n)=10^n
(the function also expressed by the suffix -plex as in googolplex).

The table is the same as that of the Ackermann function, except for a shift in Failed to parse (Missing texvc executable; please see math/README to configure.): m

and Failed to parse (Missing texvc executable; please see math/README to configure.): n

, and an addition of 3 to all values.

Computing Failed to parse (Missing texvc executable; please see math/README to configure.): 3\uparrow^m n

We place the numbers 3 Failed to parse (Missing texvc executable; please see math/README to configure.): n

in the top row, and fill the left column with values 3. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

Computing Failed to parse (Missing texvc executable; please see math/README to configure.): 10\uparrow^m n

We place the numbers 10 Failed to parse (Missing texvc executable; please see math/README to configure.): n

in the top row, and fill the left column with values 10. To determine a number in the table, take the number immediately to the left, then look up the required number in the previous row, at the position given by the number just taken.

Note that for 2 ≤ n ≤ 9 the numerical order of the numbers Failed to parse (Missing texvc executable; please see math/README to configure.): 10\uparrow^m n

is the lexicographical order with m as the most significant number, so for the numbers of these 8 columns the numerical order is simply line-by-line. The same applies for the numbers in the 97 columns with 3 ≤ n ≤ 99, and if we start from m = 1 even for 3 ≤ n ≤ 9,999,999,999.

See also

• Hyper operator
• Busy Beaver
• Cutler's bar notation
• Ultra exponential function
• Tetration

Notes

References

• Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235-1236.
• Eric W. Weisstein, Arrow Notation at MathWorld.
• Robert Munafo, Large Numbersfr:Notation des puissances itérées de Knuth

ko:크누스 윗화살표 표기법 nl:Knuths pijlomhoognotatie ja:クヌースの矢印表記 pl:Notacja strzałkowa sr:Кнутова нотација