Knuth's up-arrow notation

From Wikipedia, the free encyclopedia

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.

1 Introduction
2 Notation
3 Generalizations
4 Definition
5 Tables of values
6 References

[edit] Introduction

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

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

and exponentiation for a natural power $b$ can be defined as iterated multiplication:

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

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

$\begin{matrix} a\uparrow\uparrow b & = & \underbrace{a_{}^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & = & \underbrace{a_{}\uparrow a\uparrow\dots\uparrow a} \\ & & b\mbox{ copies of }a & & b\mbox{ copies of }a \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,

$3\uparrow\uparrow2=3^3=27\,\!$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\!$ (when expanded, this would fill a dozen moderately large hard drives)

$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):

$\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 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\uparrow2=3\uparrow\uparrow3=3^{3^3}=3^{27}=7,625,597,484,987\,\!$

$\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}$

[edit] 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 for generalization, which explains why Knuth chose to work from the inline notation $a \uparrow b$ instead.

In the context of the C programming language, the ^ character is the XOR operator. ** is a common alternative to $\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 $\uparrow\uparrow$ , but this usage is uncommon.

[edit] 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 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 relatively smaller magnitude numbers, and the chained arrow or hyper operators for larger ones.

[edit] Definition

The up-arrow notation is formally defined by

$a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{if }n=1; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{otherwise} \end{matrix} \right.$

for all integers $a, b, n$ with $b \ge 0, n \ge 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^na$ that appears in the expansion of $a \uparrow^{n + 1}b$ as $a\uparrow^n\cdots\uparrow^na\uparrow^n1$ , so that all the $a$ s appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.

[edit] 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	7	formula
0	2	4	6	8	10	12	14	$2 n$
1	2	4	8	16	32	64	128	$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^{2^{2^{65536}}}\approx 10^{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}\approx (10\uparrow)^{65531}(6.0 \times 10^{19,728})$				$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$

Note: $(10\uparrow)^k$ denotes a functional power of the function $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 $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
0	3	6	9	12	15	$3 n$
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
0	10	20	30	40	50	$10 n$
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\uparrow\uparrow n$
3	10	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10\mbox{ copies of }10 \end{matrix}$				$10\uparrow\uparrow\uparrow n$
4	10					$10\uparrow\uparrow\uparrow\uparrow n$