Knuth's up-arrow notation



         


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.

[Top]

Introduction

Multiplication can be defined as iterated addition:

<math>
\begin{matrix} a\times b=\underbrace{a_{}+a+\dots+a}\\ \qquad\quad\ \ b\mbox{ copies of }a \end{matrix} <math>

and exponentiation can be defined as iterated multiplication:

<math>
\begin{matrix} a^b=\underbrace{a_{}\times a\times\dots\times a}\\ \qquad\ b\mbox{ copies of }a \end{matrix} <math>

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

<math>
\begin{matrix} a\uparrow\uparrow b=\underbrace{a_{}^{a^{{}^{.\,^{.\,^{.\,^a}}}}}}\\ \qquad\quad\ \ \ b\mbox{ copies of }a \end{matrix} <math>

According to this definition,

<math>3\uparrow\uparrow2=3^3=27\,\!<math>
<math>3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!<math>
<math>3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\!<math>
<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}}\,\!<math>
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:

<math>
\begin{matrix} a\uparrow\uparrow\uparrow b= \underbrace{a_{}\uparrow\uparrow a\uparrow\uparrow\dots\uparrow\uparrow a}\\ \qquad\qquad\ \,b\mbox{ copies of }a \end{matrix} <math>

followed by a 'quad arrow' operator:

<math>
\begin{matrix} a\uparrow\uparrow\uparrow\uparrow b= \underbrace{a_{}\uparrow\uparrow\uparrow a\uparrow\uparrow\uparrow\dots\uparrow\uparrow\uparrow a}\\ \qquad\qquad\quad b\mbox{ copies of }a \end{matrix} <math>

and so on. The general rule is that an n-arrow operator expands into a series of (n − 1)-arrow operators. Symbolically,

<math>
\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} <math>
[Top]

Notation

In expressions such as ab, 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 ab 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 ↑n to indicate an n-arrow operator.

[Top]

Definition

The up-arrow notation is formally defined by

<math>
a\uparrow^n b= \left\{ \begin{matrix} 1,\qquad\qquad\qquad\qquad\ &&\mbox{if }b=0;\quad\,\\ a^b,\qquad\qquad\qquad\qquad&&\mbox{if }n=1;\quad\\ a\uparrow^{n-1}(a\uparrow^n(b-1)),&&\mbox{otherwise}\ \, \end{matrix} \right. <math>

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; for example
<math>3\uparrow\uparrow 3=3^{3^3} \mbox{ is }3^{\left(3^3\right)}=3^{27}=7625597484987 \mbox{ not } \left(3^3\right)^3=27^3=19683.<math>

There is good reason for the choice of this right-to-left order of evaluation. If we used left-to-right evaluation, then a↑↑b would equal a↑(a↑(b-1)), so that ↑↑ would not be an essentially new operation at all. Right associativity is also natural because we can rewrite the iterated arrow expression <math>a\uparrow^n\cdots\uparrow^na<math> that appears in the expansion of a↑n+1b as <math>a\uparrow^n\cdots\uparrow^na\uparrow^n1<math>, so that all the as appear as left operands of arrow operators. This is significant since the arrow operators are not commutative.

[Top]

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.

<math>
\begin{matrix} a\uparrow^n b&&=&&\mbox{hyper}(a,n+2,b)&&=&&a\to b\to n\\ \mbox{(Knuth)}&&&&&&&&\mbox{(Conway)} \end{matrix} <math>

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.

[Top]

See also

[Top]




  View Live Article   This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License