# Up-arrow Properties

(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\).

- \[a \uparrow^1 b = a^b\]
- \[a \uparrow^n 0 = 1\]
- \[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

- \[a \uparrow^n 1 = a\]
- \[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:

- \[a \uparrow^{-2} b = b+1\]
- \[a \uparrow^{-1} b = a+b\]
- \[a \uparrow^0 b = ab\]
- \[a \uparrow^1 b = a^b\]
- \[a \uparrow^n 0 = 1, \forall n \ge 1\]
- \[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 | … |