Knuth's up-arrow notation

In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated addition and exponentiation as iterated multiplication. Continuing in this manner leads to iterated exponentiation (tetration) and to the remainder of the hyperoperation sequence, which is commonly denoted using Knuth arrow notation.

Introduction

The ordinary arithmetical operations of addition, multiplication and exponentiation are naturally extended into a sequence of hyperoperations as follows.

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

${\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ copies of }}a\end{matrix}}$

For example,

${\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ copies of }}4\end{matrix}}$

Exponentiation for a natural power $b$ can be defined as iterated multiplication, which Knuth denoted by a single up-arrow:

${\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}$

For example,

${\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ copies of }}4\end{matrix}}$

To extend the sequence of operations beyond exponentiation, Knuth defined a “double arrow” operator to denote iterated exponentiation (tetration):

${\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,

${\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}\approx 1.3\times 10^{154}\\&&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}$

Here and below evaluation is to take place from right to left, as Knuth's arrow operators (just like exponentiation) are defined to be right-associative.

According to this definition,

$3\uparrow \uparrow 2=3^{3}=27$

$3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987$

$3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7625597484987}$

$3\uparrow \uparrow 5=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):

${\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:

${\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 $n$-arrow operator expands into a right-associative series of ($n-1$)-arrow operators. Symbolically,

${\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:

$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987$

${\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\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}}$

The notation $a\uparrow ^{n}b$ is commonly used to denote $a\uparrow \uparrow \dots \uparrow b$ with n arrows.

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\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 $a^{b}$ doesn't lend itself well to generalization, which explains why Knuth chose to work from the inline notation $a\uparrow b$ instead.

Writing out up-arrow notation in terms of powers

Attempting to write $a\uparrow \uparrow b$ using the familiar superscript notation gives a power tower.

For example: $a\uparrow \uparrow 4=a\uparrow a\uparrow a\uparrow a=a^{a^{a^{a}}}$

If b is a variable (or is too large), the power tower might be written using dots and a note indicating the height of the tower.

$a\uparrow \uparrow b=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}$

Continuing with this notation, $a\uparrow \uparrow \uparrow b$ could be written with a stack of such power towers, each describing the size of the one above it.

$a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow a\uparrow \uparrow a\uparrow \uparrow a=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{a}}}$

Again, if b is a variable or is too large, the stack might be written using dots and a note indicating its height.

$a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}b$

Furthermore, $a\uparrow \uparrow \uparrow \uparrow b$ might be written using several columns of such stacks of power towers, each column describing the number of power towers in the stack to its left:

$a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a=\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}a$

And more generally:

$a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\cdots \right\}a} _{b}$

This might be carried out indefinitely to represent $a\uparrow ^{n}b$ as iterated exponentiation of iterated exponentiation for any a, n and b (although it clearly becomes rather cumbersome).

Using tetration

The tetration notation $^{b}a$ allows us to make these diagrams slightly simpler while still employing a geometric representation (we could call these tetration towers).

$a\uparrow \uparrow b={}^{b}a$

$a\uparrow \uparrow \uparrow b=\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{b}$

$a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {\vdots } _{a}}}\right\}b$

Finally, as an example, the fourth Ackermann number $4\uparrow ^{4}4$ could be represented as:

$\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{4}}}=\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{^{^{^{4}4}4}4}}$

Generalizations

Some numbers are so large that multiple arrows of Knuth's up-arrow notation become too cumbersome; then an n-arrow operator $\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.

${\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 smaller magnitude numbers, and the chained arrow or hyper operators for larger ones.

Definition

The up-arrow notation is formally defined by

$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 $a,b,n$ with $b\geq 0,n\geq 1$.

All up-arrow operators (including normal exponentiation, $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, $a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$, not $(a\uparrow b)\uparrow c$; for example
$3\uparrow \uparrow 3=3^{3^{3}}$ is $3^{(3^{3})}=3^{27}=7625597484987$ not $\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 $a\uparrow \uparrow b$ would equal $a\uparrow (a\uparrow (b-1))$, so that $\uparrow \uparrow$ would not be an essentially new operation. Right associativity is also natural because we can rewrite the iterated arrow expression $a\uparrow ^{n}\cdots \uparrow ^{n}a$ that appears in the expansion of $a\uparrow ^{n+1}b$ as $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$, so that all the $a$s appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.

Writing $(a\uparrow ^{m})^{b}$ for the bth functional power of the function $f(x)=a\uparrow ^{m}x$ we have $a\uparrow ^{n}b=(a\uparrow ^{n-1})^{b}1$.

The definition could be extrapolated one step, starting with $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 {{#invoke:Hyperoperation|Definition|definition of the hyper operator}}, where the starting values for addition and multiplication are also separately specified.

Tables of values

Computing $2\uparrow ^{m}n$ can be restated in terms of an infinite table. We place the numbers 2 $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.

Values of $2\uparrow ^{m}n$ = hyper(2, m + 2, n) = 2 → n → m

m\n	1	2	3	4	5	6	formula
1	2	4	8	16	32	64	$2^{n}$
2	2	4	16	65536	$2^{65536}\approx 2.0\times 10^{19,729}$	$2^{2^{65536}}\approx 10^{6.0\times 10^{19,728}}$	$2\uparrow \uparrow n$
3	2	4	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$			$2\uparrow \uparrow \uparrow n$
4	2	4	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ copies of }}2\end{matrix}}$				$2\uparrow \uparrow \uparrow \uparrow n$

The table is the same as that of the Ackermann function, except for a shift in $m$ and $n$, and an addition of 3 to all values.

Computing $3\uparrow ^{m}n$

We place the numbers 3 $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.

Values of $3\uparrow ^{m}n$ = hyper(3, m + 2, n) = 3 → n → m

m\n	1	2	3	4	5	formula
1	3	9	27	81	243	$3^{n}$
2	3	27	7,625,597,484,987	$3^{7,625,597,484,987}$		$3\uparrow \uparrow n$
3	3	7,625,597,484,987	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7,625,597,484,987{\mbox{ copies of }}3\end{matrix}}$			$3\uparrow \uparrow \uparrow n$
4	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7,625,597,484,987{\mbox{ copies of }}3\end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Computing $10\uparrow ^{m}n$

We place the numbers 10 $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.

Values of $10\uparrow ^{m}n$ = hyper(10, m + 2, n) = 10 → n → m

m\n	1	2	3	4	5	formula
1	10	100	1,000	10,000	100,000	$10^{n}$
2	10	10,000,000,000	$10^{10,000,000,000}$	$10^{10^{10,000,000,000}}$	$10^{10^{10^{10,000,000,000}}}$	$10\uparrow \uparrow n$
3	10	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10}{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10^{10}}{\mbox{ copies of }}10\end{matrix}}$		$10\uparrow \uparrow \uparrow n$
4	10	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10{\mbox{ copies of }}10\end{matrix}}$	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}{\mbox{ copies of }}10\end{matrix}}$			$10\uparrow \uparrow \uparrow \uparrow n$

Note that for 2 ≤ n ≤ 9 the numerical order of the numbers $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.

Numeration systems based on the hyperoperation sequence

Goodstein [1947], with a system of notation different from Knuth arrows, used the sequence of hyperoperators here denoted by $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \dots )\,\!$ to create systems of numeration for the nonnegative integers. Letting superscripts $\quad (^{(1)},\ ^{(2)},\ ^{(3)},\ ^{(4)},\ \dots )\,\!$ denote the respective hyperoperators $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \dots )\,\!$, the so-called complete hereditary representation of integer n, at level k and base b, can be expressed as follows using only the first k hyperoperators and using as digits only 0, 1, ..., b-1:

• For 0 ≤ n ≤ b-1, n is represented simply by the corresponding digit.
• For n > b-1, the representation of n is found recursively, first representing n in the form

$b^{(k)}{x_{k}}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_{2}}^{(1)}x_{1}$

where x_k, ..., x₁ are the largest integers satisfying (in turn)

$b^{(k)}x_{k}\leq n$

$b^{(k)}{x_{k}}^{(k-1)}x_{k-1}\leq n$

...

$b^{(k)}{x_{k}}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_{2}}^{(1)}x_{1}\leq n$.

Any x_i exceeding b-1 is then re-expressed in the same manner, and so on, repeating this procedure until the resulting form contains only the digits 0, 1, ..., b-1.

The remainder of this section will use $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \uparrow \uparrow \uparrow ,\ \dots )$, rather than superscripts, to denote the hyperoperators.

Unnecessary parentheses can be avoided by giving higher-level operators higher precedence in the order of evaluation; thus,

level-1 representations have the form $b+X$, with X also of this form;

level-2 representations have the form $b\times X+Y$, with X,Y also of this form;

level-3 representations have the form $b\uparrow X\times Y+Z$, with X,Y,Z also of this form;

level-4 representations have the form $b\uparrow \uparrow X\uparrow Y\times Z+T$, with X,Y,Z,T also of this form;

and so on.

The representations can be abbreviated by omitting any instances of $+0,\ \times 1,\uparrow 1,\ \uparrow \uparrow 1,$ etc.; for example, the level-3 base-2 representation of the number 6 is $2\uparrow (2\uparrow 1\times 1+0)\times 1+(2\uparrow 1\times 1+0)$, which abbreviates to $2\uparrow 2+2$.

Examples: The unique base-2 representations of the number 266, at levels 1, 2, 3, 4, and 5 are as follows:

${\text{Level 1:}}\ \ 266=2+2+\dots +2\ \ {\text{(with 133 2s)}}$

${\text{Level 2:}}\ \ 266=2\times (2\times (2\times (2\times 2\times 2\times 2\times 2+1))+1)$

${\text{Level 3:}}\ \ 266=2\uparrow 2\uparrow (2+1)+2\uparrow (2+1)+2$

${\text{Level 4:}}\ \ 266=2\uparrow \uparrow (2+1)\uparrow 2+2\uparrow \uparrow 2\times 2+2$

${\text{Level 5:}}\ \ 266=2\uparrow \uparrow \uparrow 2\uparrow \uparrow 2+2\uparrow \uparrow \uparrow 2\times 2+2$.

See also

• Primitive recursion
• Hyper operator
• Busy beaver
• Cutler's bar notation
• Ultra exponential function
• Tetration

References

• Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235–1242.
• Weisstein, Eric W. "Arrow Notation". MathWorld.
• Robert Munafo, Large Numbers