(This article was original published on in Oct 2009 on my Wikipedia User page. I’m re-posting on my blog to bring my writing together in one place.)

Some useful definitions and properties for Knuth’s up-arrow notation

## Definition

$$a \uparrow^n b$$ is defined for a, b and n are integers $$n \ge 1$$ and $$b \ge 0$$.

1. $a \uparrow^1 b = a^b$
2. $a \uparrow^n 0 = 1$
3. $a \uparrow^n b = a \uparrow^{n-1} (a \uparrow^n (b-1))$

Therefore $$a\uparrow^n b = a \uparrow^{n-1} a \uparrow^{n-1} \cdots \uparrow^{n-1} a$$ (with b copies of a, where $$\uparrow$$ is right associative) and so it is seen as an extension of the series of operations $$+, \times, \uparrow, \uparrow^2, \dots$$ where $$\uparrow$$ is basic exponentiation

## Basic Properties

1. $a \uparrow^n 1 = a$
2. $2 \uparrow^n 2 = 2^2 = 2 \times 2 = 2 + 2 = 4$

## Extension

We can extend the uparrows to include multiplication and addition as the [[hyper operator]].

This system may be consistently expanded to include multiplication, addition and incrementing:

1. $a \uparrow^{-2} b = b+1$
2. $a \uparrow^{-1} b = a+b$
3. $a \uparrow^0 b = ab$
4. $a \uparrow^1 b = a^b$
5. $a \uparrow^n 0 = 1, \forall n \ge 1$
6. $a \uparrow^n b = a \uparrow^{n-1} (a \uparrow^n (b-1))$

### Proof of consistency by induction.

We will show that Rules 3, 5 and 6 imply rule 4 Assume that $$a \uparrow^1 \beta = a^\beta$$ for any $$\beta < b$$, then

• $$a \uparrow^1 b = a \uparrow^0 (a \uparrow^1 (b-1)) = a \cdot a^{b-1} = a^b$$ by rule 6, rule 3 and assumption

Furthermore, $$a \uparrow^1 0 = 1 = a^0$$ by rule 5

Thus the assumption is true for all $$\beta \ge 0$$

Likewise we can show that Rules 2, 5, 6 imply Rule 3 and that Rules 1, 5, 6 imply Rule 2. Therefore, Rules 1, 5, 6 imply Rules 4, 5, 6 and so consistently extend the system.

QED

Clearly some of the properties do not extend.

## Changing Bases

Todo: How do you change bases.

Example:

• $$3 \uparrow^k n \approx 10 \uparrow^k n^\prime$$ what is $$n^\prime$$ ?

For $$k = 1$$:

$a \uparrow n = a^n = b^{n\log_b(a)} = b \uparrow (\log_b(a) n)$

For $$k = 2$$: For all $$a < b$$ there is a unique $$\delta$$ such that

$b \uparrow \uparrow (n - \delta - 1) < a \uparrow \uparrow n < b \uparrow \uparrow (n - \delta)$

for all sufficiently large n

Examples:

• $$10 \uparrow \uparrow (n-1) < 3 \uparrow \uparrow n < 10 \uparrow \uparrow n$$ for all $$n \ge 3$$
• $$10 \uparrow \uparrow (n-3) < 2 \uparrow \uparrow n < 10 \uparrow \uparrow (n-2)$$ for all $$n \ge 4$$

Thus the base of a tetration is not very important, they all grow at approximately the same rate eventually. (See Notes)

In fact these numbers $$\delta$$ grow very slowly.

Claim:

$a \uparrow \uparrow (n+k-1) < (a \uparrow \uparrow k) \uparrow \uparrow n < a \uparrow \uparrow (n+k) \,$

Note, the left inequality is easy to prove:

$(a \uparrow \uparrow k) \uparrow \uparrow n = ((a \uparrow \uparrow k) \uparrow)^{n-1} (a \uparrow \uparrow k) > (a \uparrow)^{n-1} (a \uparrow \uparrow k) = a \uparrow \uparrow (n+k-1) \,$

Claim:

$n \uparrow^n n < (3 \uparrow^n 3) \uparrow^n (3 \uparrow^n 3 - 3) < 3 \uparrow^n (3 \uparrow^n 3) = 3 \uparrow^{n+1} 3 \,$

## Notes

Note, for any $$a,b$$, $$\delta$$ is uniquely defined, let’s call it $$\delta_{ab}$$. Making a small table we get:

$$_a \backslash ^b$$ 2 3 4 5 6 10 100 1000 10000
2   2 2 2 3 3 3 3 4
3     1 1 1 1 2 2 2

As you can see, these values rise very slowly, in fact, (I believe that) if $$b = a \uparrow \uparrow k$$, then $$\delta_{ab} = k$$. The following table shows the smallest number $$b$$ such that $$\delta_{ab} = \delta$$

$$_\delta \backslash ^a$$ 2 3 4 5 6 7 8 10 100
1   4 5 6 7 8 9 11 101
2 3 12 81 759 9164 135608 2376342
3 6
4 5298