Chained arrow notation

View full site to see MathJax equation

Chained arrow notation
Growth rate	Original: \(cg(n) \approx f_{\omega^2}(n)\) (FGH) Hurford's extension: \(n\rightarrow_n n \approx f_{\omega^3}(n)\) C(n,n,n) \(\approx f_{\omega^3 + \omega}(n)\) Cookiefonster's extension: \(n\rightarrow^n n \approx f_{\omega^\omega}(n)\)
Notations	Original: \(a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_n\) Hurford's extension: \(a_1 \rightarrow_b a_2 \rightarrow_b \cdots \rightarrow_b a_n\) Cookiefonster's extension: \(a_1 \rightarrow^{b_1} a_2 \rightarrow^{b_2} \cdots \rightarrow^{b_{n-1}} a_n\)
Author(s)	J. H. Conway, R. K. Guy Extensions: Peter Hurford, Cookiefonster
Year	1995 (original) 2011 (Hurford's extension) 2015 (Cookiefonster's extension)

Chained arrow notation is a generalization of up-arrow notation devised by J. H. Conway and R. K. Guy in The Book of Numbers.

Nathan Ho and Wojowu showed that chained arrow notation terminates — that is, its output exists for all input sequences.^{[dead link]}

By Bird's Proof, chained arrow notation is roughly comparable to 4-entry arrays in Jonathan Bowers' linear array notation, but is far exceeded by arrays with 5 entries or more.

Definition

1. \(a \rightarrow b = a^{b}\)
2. \(a \rightarrow b \rightarrow c = a\uparrow^cb = a\underbrace{\uparrow\ldots\uparrow}_cb\) (in which up-arrow notation is used) = a[c+2]b (in which the bracket notation of hyper operator is used)
3. \(a \rightarrow\ldots\rightarrow b \rightarrow 1 = a \rightarrow\ldots\rightarrow b\) — When last entry is 1, it will be ignored.
4. \(a \rightarrow\ldots\rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow\ldots\rightarrow b\)
5. \(a \rightarrow\ldots\rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow\ldots\rightarrow b \rightarrow (a \rightarrow\ldots\rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d\)

Note that the arrow \(\rightarrow\) is not an operator in the conventional sense; \(a\rightarrow b\rightarrow c\) is equal to neither of \(a\rightarrow(b\rightarrow c)\) or \((a\rightarrow b)\rightarrow c\). The entire chain (which could be thought of as an array) represents a single operation.

Examples

Here are some small examples of chained arrow notation in action:

\(2 \rightarrow 2 \rightarrow 2 \rightarrow 2\) = \(2 \rightarrow 2 \rightarrow (2 \rightarrow 2 \rightarrow 1 \rightarrow 2) \rightarrow 1\) = \(2 \rightarrow 2 \rightarrow 4 \rightarrow 1\) = \(2\uparrow\uparrow\uparrow\uparrow2\) = 4

\(3 \rightarrow 3 \rightarrow 2 = 3\uparrow\uparrow3 = 7,625,597,484,987\)

\(3 \rightarrow 3 \rightarrow 2 \rightarrow 2\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2)\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3)\)

\(= 3 \rightarrow 3 \rightarrow (3^{3})\)

\(= 3 \rightarrow 3 \rightarrow 27\)

\(= 3 \uparrow^{27} 3 \)

\(3 \rightarrow 3 \rightarrow 3 \rightarrow 2\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \rightarrow 1\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1) \rightarrow 1\)

\(= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3^3 \rightarrow 1) \rightarrow 1\)

\(= 3 \rightarrow 3 \rightarrow 3\uparrow^{3^3}3 \)

\(= 3 \uparrow^{3 \uparrow^{3^3} 3} 3\)

CG function

Using chained arrow notation, Conway and Guy wrote "The first three of our rapidly increasing sequence of numbers 1, \(2\rightarrow 2\), \(3\rightarrow 3 \rightarrow 3\), \(4\rightarrow 4 \rightarrow 4 \rightarrow 4\), ...", which implies that they defined a function similar to the Ackermann numbers; \(cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n\). Although it is equal to the Ackermann numbers for n from 1 to 3, \(cg(4) = 4\rightarrow 4\rightarrow 4\rightarrow 4 > \lbrace 4,4,3,2 \rbrace\), using Bird's Proof. Therefore, cg(4) is much, much larger than the famous Graham's number (in fact, the same can be said for the much smaller Conway's Tetratri).

The growth rate of this function is about \(f_{\omega^2}(n)\) in the fast-growing hierarchy. This is comparable to 4 entry linear arrays in BEAF or Bird's array notation. In Notation Array Notation, the CG function can be written as (n{3,n}n).

Peter Hurford's extensions

Peter Hurford extends chained arrow notation by adding the following rule:

\(a \rightarrow_c b = \underbrace{a \rightarrow_{c-1} a \rightarrow_{c-1}\ldots\rightarrow_{c-1} a \rightarrow_{c-1}a}_{b \rightarrow_{c-1}'s}\)

All normal rules remains unchanged. Thus, they apply ignoring subscripts. Notice that expressions like \(3 \rightarrow_{2} 3 \rightarrow 3\) are illegal; entire expressions must have single type of right-arrows. Also, Hurford shows that \(f(n) = n \rightarrow_n n\) is about \(f_{\omega^3}(n)\) in the fast-growing hierarchy.

Furthermore, he defines C(n) function as follows:

\(C(a) = a \rightarrow_a a\)

\(C(a,1) = a \rightarrow_{C(a)} a\)

\(C(a,b) = a \rightarrow_{C(a,b-1)} a\)

\(C(a,1,1) = C(a,C(a,a))\)

\(C(a,b,1) = C(a,C(a,b-1,1))\)

\(C(a,1,c) = C(a,C(a,a,c-1),c-1)\)

\(C(a,b,c) = C(a,C(a,b-1,c),c-1)\)

The function \(f(n) = C(n,n,n)\) grows about as fast as \(f_{\omega^3 + \omega}(n)\) in the fast-growing hierarchy.

Cookiefonster's extension

The wiki user Cookiefonster created an alternate extension that allows expressions to contain multiple arrow types. He uses a superscript to denote arrow type rather than a subscript.

• \(a\rightarrow^1 b = a^b\)
• \(a\rightarrow^x b = a\rightarrow^{x-1} a\rightarrow^{x-1} a \ldots \rightarrow^{x-1} a\) where there are \(b\) copies of \(a\)
• \(\#\rightarrow^x 1 = \#\) (here, \(\#\) denotes an arbitrarily long part of the chain before the relevant terms)
• \(\#\rightarrow^x 1\rightarrow^y a = \#\) (the source accidentally uses two \(\rightarrow^x\) arrows implying they must be the same, but that is not required)
• \(\#\rightarrow^n a\rightarrow^1 b = \#\rightarrow^n (\#\rightarrow^n (a-1)\rightarrow^1 b)\rightarrow^1 (b-1)\)
• \(\#\rightarrow^n a\rightarrow^x b = \#\rightarrow^n a\rightarrow^{x-1} a\rightarrow^{x-1} a \ldots \rightarrow^{x-1} a\) where there are \(b\) copies of \(a\)

The function \(f(n) = n\rightarrow^n n\) grows about as fast as \(f_{\omega^\omega}(n)\) in the fast-growing hierarchy.

Approximation

Conway wrote that Graham's number = G is between 3→3→64→2 and 3→3→65→2, and therefore less than 3→3→3→3. It can be confirmed as follows. Let g(x) = \(3\uparrow^{x}3 = 3\rightarrow3\rightarrow x\), and G = g⁶⁴(4).

• 3→3→1→2 = 3→3→1 = g(1) = 27
• 3→3→2→2 = 3→3→(3→3→1→2)→1 = 3→3→(3→3→1) = g(g(1)) = g²(1) = 3→3→27 = g(27)
• 3→3→3→2 = 3→3→(3→3→2→2) = g³(1) = g²(27)
• 3→3→n→2 = gⁿ(1) = g^n-1(27)
• 3→3→64→2 = g⁶⁴(1) < g⁶⁴(4) = G
• 3→3→65→2 = g⁶⁴(27) > g⁶⁴(4) = G
• 3→3→3→3 = 3→3→(3→3→2→3)→2 > 3→3→65→2 > G

Using this approximation, a Moser is \(\approx g(10 \uparrow\uparrow 257) < g(g(3))\),

• 3→3→2→2 < Moser < 3→3→3→2

The chained arrow notation can be approximated with the Taro's multivariable Ackermann function as follows for x=1, y>1 ou x>1, y+z>0.

$A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)$

It can be approximated with Fast-growing hierarchy with the fundamental sequence of Wainer hierarchy as follows.

• \(3 \rightarrow 3 \rightarrow n \sim f_\omega (n) \)
• \(3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \sim f_\omega (27) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_\omega (27) \)
• \(3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_\omega (27) \)
• \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega +1} (n) \)
• \(3 \rightarrow 3 \rightarrow 2 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 2 \sim f_{\omega +1} (26) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \rightarrow 2 \sim f^2_{\omega +1} (26) \)
• \(3 \rightarrow 3 \rightarrow 4 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3) \rightarrow 2 \sim f^3_{\omega +1} (26) \)
• \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega +2} (n) \)
• \(3 \rightarrow 3 \rightarrow 2 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 3 \sim f_{\omega +2} (26) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 4) \rightarrow 3 \sim f^2_{\omega +2} (26) \)
• \(3 \rightarrow 3 \rightarrow 4 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 4) \rightarrow 3 \sim f^3_{\omega +2} (26) \)
• \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega +3} (n) \)
• \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 5 \sim f_{\omega +4} (n) \)
• \(3 \rightarrow 3 \rightarrow (n+1) \rightarrow 6 \sim f_{\omega +5} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 2} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3) \sim f_{\omega \times 2} (f_4 (3)) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \sim f^2_{\omega \times 2} (f_4 (3)) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \sim f^3_{\omega \times 2} (f_4 (3)) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 2 +1} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 2 +2} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 2 +3} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 3} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \sim f_{\omega \times 3 +1} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \sim f_{\omega \times 3 +2} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \sim f_{\omega \times 3 +3} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 4} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 5} (n) \)
• \(3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \sim f_{\omega \times 6} (n) \)
• \(\underbrace{3 \rightarrow 3 \rightarrow \ldots \rightarrow 3 \rightarrow 3}_{n+2} \sim f_{\omega^2}(n)\)

See also

• Arrow notation
• BEAF
• Conway's Tetratri
• Conway's Tetratet