Wsrtjtyk

Conway chained arrow notation, created by mathematician John Horton Conway, is a means of expressing certain extremely large numbers. It is simply a finite sequence of positive integers separated by rightward arrows, e.g. 2 → 3 → 4 → 5 → 6.

As with most combinatorial notations, the definition is recursive. In this case the notation eventually resolves to being the leftmost number raised to some (usually enormous) integer power.

Definition and overview

A "Conway chain" is defined as follows:

• Any positive integer is a chain of length 1.


• A chain of length n, followed by a right-arrow → and a positive integer, together form a chain of length n+1{displaystyle n+1}.

Any chain represents an integer, according to the four rules below. Two chains are said to be equivalent if they represent the same integer.

If p{displaystyle p} and q{displaystyle q} are positive integers, and X{displaystyle X} is a subchain, then:

1. An empty chain (or a chain of length 0) represents 1, and the chain p{displaystyle p} represents the number p{displaystyle p}.


2. 
   p→q{displaystyle pto q} represents the exponential expression pq{displaystyle p^{q}}. (Note that Conway in The Book of Numbers^[1] leaves the 2-tuple p→q{displaystyle prightarrow q} undefined, but has the 3rd parameter [r in p→q→r{displaystyle prightarrow qrightarrow r}] count Knuth's arrows, so that this rule actually follows from the axiom to drop the →1{displaystyle to 1} from the right end.)


3. 
   X→1{displaystyle Xto 1} is equivalent to X{displaystyle X}.


4. 
   X→p→(q+1){displaystyle Xto pto (q+1)} is equivalent to X→(X→(⋯(X→(X)→q)⋯)→q)→q{displaystyle Xto (Xto (cdots (Xto (X)to q)cdots )to q)to q}
   (with p copies of X, p − 1 copies of q, and p − 1 pairs of parentheses; applies for q > 0).

Note that the last rule can be restated recursively to avoid the ellipses:

4a. X→1→(q+1)=X{displaystyle Xto 1to (q+1)=X}

4b. X→(p+1)→(q+1)=X→(X→p→(q+1))→q{displaystyle Xto (p+1)to (q+1)=Xto (Xto pto (q+1))to q}

Properties

1. A chain of length 3 corresponds to hyperoperation and Knuth's up-arrow notation:
   

   p→q→r=p[r+2]q=p↑↑↑⋯↑↑↑⏟q=p↑rq.r arrows{displaystyle {begin{matrix}pto qto r=p[r+2]q=p!!!&underbrace {uparrow uparrow uparrow dots uparrow uparrow uparrow } &!!!q=puparrow ^{r}q.\&!!!r{text{ arrows}}!!!end{matrix}}}

   
   


2. a chain X → Y is of the form X → p; hence:


3. a chain starting with a is a power of a
   


4. a chain 1 → Y is equal to 1


5. a chain X → 1 → Y is equal to X
   


6. a chain 2 → 2 → Y is equal to 4


7. a chain X → 2 → 2 is equal to X → (X) (chain X with its value concatenated to it)

Interpretation

One must be careful to treat an arrow chain as a whole. Arrow chains do not describe the iterated application of a binary operator. Whereas chains of other infixed symbols (e.g. 3 + 4 + 5 + 6 + 7) can often be considered in fragments (e.g. (3 + 4) + 5 + (6 + 7)) without a change of meaning (see associativity), or at least can be evaluated step by step in a prescribed order, e.g. 3⁴⁵⁶⁷ from right to left, that is not so with Conway's arrow.

For example:

• 2→3→2=2↑↑3=222=16{displaystyle 2rightarrow 3rightarrow 2=2uparrow uparrow 3=2^{2^{2}}=16}


• 2→(3→2)=2(32)=232=512{displaystyle 2rightarrow left(3rightarrow 2right)=2^{(3^{2})}=2^{3^{2}}=512}


• (2→3)→2=(23)2=64{displaystyle left(2rightarrow 3right)rightarrow 2=left(2^{3}right)^{2}=64}

The fourth rule is the core: A chain of 3 or more elements ending with 2 or higher becomes a chain of the same length with a (usually vastly) increased penultimate element. But its ultimate element is decremented, eventually permitting the third rule to shorten the chain. After, to paraphrase Knuth, "much detail", the chain is reduced to two elements and the second rule terminates the recursion.

Examples

Examples get quite complicated quickly. Here are some small examples:

n

= n (by rule 1)

p→q

= p^q (by rule 2)

Thus 3→4 = 3⁴ = 81

1→(any arrowed expression)

= 1 since the entire expression eventually reduces to 1^number = 1. (Indeed, any chain containing a 1 can be truncated just before that 1; e.g. X→1→Y=X for any (embedded) chains X,Y.)

4→3→2

= 4→(4→(4)→1)→1 (by 4) and then, working from the inner parentheses outwards,

= 4→(4→4→1)→1 (remove redundant parentheses (rrp))

= 4→(4→4)→1 (3)

= 4→(256)→1 (2)

= 4→256→1 (rrp)

= 4→256 (3)

= 4²⁵⁶ (2)

= 13 407 807 929 942 597 099 574 024 998 205 846 127 479 365 820 592 393 377 723 561 443 721 764 030 073 546 976 801 874 298 166 903 427 690 031 858 186 486 050 853 753 882 811 946 569 946 433 649 006 084 096 exactly ≈ 1.34078079299 × 10¹⁵⁴

2→2→4

= 2→(2)→3 (by 4)

= 2→2→3 (rrp)

= 2→2→2 (4, rrp)

= 2→2→1 (4, rrp)

= 2→2 (3)

= 4 (2) (In fact, any chain beginning with two 2s stands for 4.)

2→4→3

= 2→(2→(2→(2)→2)→2)→2 (by 4) The four copies of X (which is 2 here) are in bold to distinguish them from the three copies of q (which is also 2)

= 2→(2→(2→2→2)→2)→2 (rrp)

= 2→(2→(4)→2)→2 (previous example)

= 2→(2→4→2)→2 (rrp) (expression expanded in next equation shown in bold on both lines)

= 2→(2→(2→(2→(2)→1)→1)→1)→2 (4)

= 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)

= 2→(2→(2→(2→2)))→2 (3 repeatedly)

= 2→(2→(2→(4)))→2 (2)

= 2→(2→(16))→2 (2)

= 2→65536→2 (2,rrp)

= 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (4) with 65535 sets of parentheses

= 2→(2→(2→(...2→(2→(2))...))) (3 repeatedly)

= 2→(2→(2→(...2→(4))...))) (2)

= 2→(2→(2→(...16...))) (2)

= 22…2{displaystyle 2^{2^{dots ^{2}}}} (a tower with 2¹⁶ = 65536 stories)

= ⁶⁵⁵³⁶2 (See tetration)

2→3→2→2

= 2→3→(2→3)→1 (by 4)

= 2→3→8 (2 and 3)

= 2→(2→2→7)→7 (by 4)

= 2→4→7 (two initial 2's give 4 [prop6])

= 2→(2→(2→2→6)→6)→6 (4)

= 2→(2→4→6)→6 (prop6)

= 2→(2→(2→(2→2→5)→5)→5)→6 (4)

= 2→(2→(2→4→5)→5)→6 (prop6)

= 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6 (4)

= 2→(2→(2→(2→4→4)→4)→5)→6 (prop6)

= 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4) →5)→6 (4)

= 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (prop6)

= 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (previous example)

= much larger than previous number

3→2→2→2

= 3→2→(3→2)→1 (4)

= 3→2→9 (2 and 3)

= 3→3→8 (4)

Systematic examples

The simplest cases with four terms (containing no integers less than 2) are:

• 
  a→b→2→2{displaystyle ato bto 2to 2}
  =a→b→2→(1+1){displaystyle =ato bto 2to (1+1)}
  =a→b→(a→b)→1{displaystyle =ato bto (ato b)to 1}
  =a→b→ab{displaystyle =ato bto a^{b}}
  =a[ab+2]b{displaystyle =a[a^{b}+2]b}
  

(also following from the last-mentioned property)

• 
  a→b→3→2{displaystyle ato bto 3to 2}
  =a→b→3→(1+1){displaystyle =ato bto 3to (1+1)}
  =a→b→(a→b→(a→b)→1)→1{displaystyle =ato bto (ato bto (ato b)to 1)to 1}
  =a→b→(a→b→ab){displaystyle =ato bto (ato bto a^{b})}
  =a[a→b→2→2+2]b{displaystyle =a[ato bto 2to 2+2]b}
  


• 
  a→b→4→2{displaystyle ato bto 4to 2}
  =a→b→(a→b→(a→b→ab)){displaystyle =ato bto (ato bto (ato bto a^{b}))}
  =a[a→b→3→2+2]b{displaystyle =a[ato bto 3to 2+2]b}
  

We can see a pattern here. If, for any chain X, we let f(p)=X→p{displaystyle f(p)=Xto p} then X→p→2=fp(1){displaystyle Xto pto 2=f^{p}(1)} (see
functional powers).

Applying this with X=a→b{displaystyle X=ato b}, then f(p)=a[p+2]b{displaystyle f(p)=a[p+2]b} and a→b→p→2=a[a→b→(p−1)→2+2]b=fp(1){displaystyle ato bto pto 2=a[ato bto (p-1)to 2+2]b=f^{p}(1)}

Thus, for example, 10→6→3→2=10[10[1000002]6+2]6{displaystyle 10to 6to 3to 2=10[10[1000002]6+2]6}.

Moving on:

• 
  a→b→2→3{displaystyle ato bto 2to 3}
  =a→b→2→(2+1){displaystyle =ato bto 2to (2+1)}
  =a→b→(a→b)→2{displaystyle =ato bto (ato b)to 2}
  =a→b→ab→2{displaystyle =ato bto a^{b}to 2}
  =fab(1){displaystyle =f^{a^{b}}(1)}
  

Again we can generalize. When we write gq(p)=X→p→q{displaystyle g_{q}(p)=Xto pto q} we have X→p→q+1=gqp(1){displaystyle Xto pto q+1=g_{q}^{p}(1)}, that is, gq+1(p)=gqp(1){displaystyle g_{q+1}(p)=g_{q}^{p}(1)}. In the case above, g2(p)=a→b→p→2=fp(1){displaystyle g_{2}(p)=ato bto pto 2=f^{p}(1)} and g3(p)=g2p(1){displaystyle g_{3}(p)=g_{2}^{p}(1)}, so a→b→2→3=g3(2)=g22(1)=g2(g2(1))=ff(1)(1)=fab(1){displaystyle ato bto 2to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^{a^{b}}(1)}

Ackermann function

The Ackermann function may be expressed using Conway chained arrow notation:

A(m, n) = (2 → (n + 3) → (m − 2)) − 3 for m > 2 (Since A(m, n) = 2 [m] (n + 3) - 3 in hyperoperation)

hence

2 → n → m = A(m + 2,n − 3) + 3 for n > 2

(n = 1 and n = 2 would correspond with A(m, −2) = −1 and A(m, −1) = 1, which could logically be added).

Graham's number

Graham's number G{displaystyle G} itself cannot be expressed concisely in Conway chained arrow notation, but by defining the intermediate function f(n)=3→3→n=3↑↑⋯↑⏟3n arrows{displaystyle f(n)=3rightarrow 3rightarrow n={begin{matrix}3underbrace {uparrow uparrow cdots uparrow } 3\{text{n arrows}}end{matrix}}}, we have:
G=f64(4){displaystyle G=f^{64}(4)} (see functional powers), and
3→3→64→2<G<3→3→65→2{displaystyle 3rightarrow 3rightarrow 64rightarrow 2<G<3rightarrow 3rightarrow 65rightarrow 2}

Proof: Applying in order the definition, rule 3, and rule 4, we have:

f64(1){displaystyle f^{64}(1)}

=3→3→(3→3→(⋯(3→3→(3→3→1))⋯)){displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow (cdots (3rightarrow 3rightarrow (3rightarrow 3rightarrow 1))cdots ))} (with 64 3→3{displaystyle 3rightarrow 3}'s)

=3→3→(3→3→(⋯(3→3→(3→3)→1)⋯)→1)→1{displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow (cdots (3rightarrow 3rightarrow (3rightarrow 3)rightarrow 1)cdots )rightarrow 1)rightarrow 1}

=3→3→64→2;{displaystyle =3rightarrow 3rightarrow 64rightarrow 2;}

=3↑↑⋯⋯⋯⋅↑⏟33↑↑⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋅↑⏟33↑3}64 layers{displaystyle left.{begin{matrix}=&3underbrace {uparrow uparrow cdots cdots cdots cdot uparrow } 3\&3underbrace {uparrow uparrow cdots cdots cdots uparrow } 3\&underbrace {qquad ;;vdots qquad ;;} \&3underbrace {uparrow uparrow cdots cdot uparrow } 3\&3uparrow 3end{matrix}}right}{text{64 layers}}}

f64(4)=G;{displaystyle f^{64}(4)=G;}

=3→3→(3→3→(⋯(3→3→(3→3→4))⋯)){displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow (cdots (3rightarrow 3rightarrow (3rightarrow 3rightarrow 4))cdots ))} (with 64 3→3{displaystyle 3rightarrow 3}'s)

=3↑↑⋯⋯⋯⋅↑⏟33↑↑⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋅↑⏟33↑↑↑↑3}64 layers{displaystyle left.{begin{matrix}=&3underbrace {uparrow uparrow cdots cdots cdots cdot uparrow } 3\&3underbrace {uparrow uparrow cdots cdots cdots uparrow } 3\&underbrace {qquad ;;vdots qquad ;;} \&3underbrace {uparrow uparrow cdots cdot uparrow } 3\&3uparrow uparrow uparrow uparrow 3end{matrix}}right}{text{64 layers}}}

f64(27){displaystyle f^{64}(27)}

=3→3→(3→3→(⋯(3→3→(3→3→27))⋯)){displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow (cdots (3rightarrow 3rightarrow (3rightarrow 3rightarrow 27))cdots ))} (with 64 3→3{displaystyle 3rightarrow 3}'s)

=3→3→(3→3→(⋯(3→3→(3→3→(3→3)))⋯)){displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow (cdots (3rightarrow 3rightarrow (3rightarrow 3rightarrow (3rightarrow 3)))cdots ))} (with 65 3→3{displaystyle 3rightarrow 3}'s)

=3→3→65→2{displaystyle =3rightarrow 3rightarrow 65rightarrow 2} (computing as above).

=f65(1){displaystyle =f^{65}(1)}

=3↑↑⋯⋯⋯⋅↑⏟33↑↑⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋅↑⏟33↑3}65 layers{displaystyle left.{begin{matrix}=&3underbrace {uparrow uparrow cdots cdots cdots cdot uparrow } 3\&3underbrace {uparrow uparrow cdots cdots cdots uparrow } 3\&underbrace {qquad ;;vdots qquad ;;} \&3underbrace {uparrow uparrow cdots cdot uparrow } 3\&3uparrow 3end{matrix}}right}{text{65 layers}}}

Since f is strictly increasing,

f64(1)<f64(4)<f64(27){displaystyle f^{64}(1)<f^{64}(4)<f^{64}(27)}

which is the given inequality.

With chain arrows it is very easy to specify a much larger number. For example, note that

3→3→3→3{displaystyle 3rightarrow 3rightarrow 3rightarrow 3}

=3→3→(3→3→27→2)→2{displaystyle =3rightarrow 3rightarrow (3rightarrow 3rightarrow 27rightarrow 2)rightarrow 2,}

=f3→3→27→2(1){displaystyle =f^{3rightarrow 3rightarrow 27rightarrow 2}(1)}

=ff27(1)(1){displaystyle =f^{f^{27}(1)}(1)}

=3↑↑⋯⋯⋯⋅⋅↑⏟33↑↑⋯⋯⋯⋅↑⏟33↑↑⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋅↑⏟33↑3}3↑↑⋯⋯⋯⋅↑⏟33↑↑⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋅↑⏟33↑3} 3↑3=27 layers{displaystyle left.{begin{matrix}=&3underbrace {uparrow uparrow cdots cdots cdots cdot cdot uparrow } 3\&3underbrace {uparrow uparrow cdots cdots cdots cdot uparrow } 3\&3underbrace {uparrow uparrow cdots cdots cdots uparrow } 3\&underbrace {qquad ;;vdots qquad ;;} \&3underbrace {uparrow uparrow cdots cdot uparrow } 3\&3uparrow 3end{matrix}}right}left.{begin{matrix}3underbrace {uparrow uparrow cdots cdots cdots cdot uparrow } 3\3underbrace {uparrow uparrow cdots cdots cdots uparrow } 3\underbrace {qquad ;;vdots qquad ;;} \3underbrace {uparrow uparrow cdots cdot uparrow } 3\3uparrow 3end{matrix}}right} 3uparrow 3={text{27 layers}}}

3→3→27→2{displaystyle 3rightarrow 3rightarrow 27rightarrow 2}

CG function

Conway and Guy created a simple, single-argument function that diagonalizes over the entire notation, defined as:

cg(n)=n→n→n→⋯→n→n→n⏟n{displaystyle cg(n)=underbrace {nrightarrow nrightarrow nrightarrow dots rightarrow nrightarrow nrightarrow n} _{n}}

meaning the sequence is:

cg(1) = 1

cg(2) = 2 → 2 = 2² = 4

cg(3) = 3 → 3 → 3 = 3↑↑↑3

cg(4) = 4 → 4 → 4 → 4

cg(5) = 5 → 5 → 5 → 5 → 5

...

This function, as one might expect, grows extraordinarily fast.

Extension by Peter Hurford

Peter Hurford, a web developer and statistician, has defined an extension to this notation:

a→bc=a→b−1a→b−1a→b−1⋯→b−1a→b−1a→b−1a⏟c arrows{displaystyle arightarrow _{b}c=underbrace {arightarrow _{b-1}arightarrow _{b-1}arightarrow _{b-1}dots rightarrow _{b-1}arightarrow _{b-1}arightarrow _{b-1}a} _{c{text{ arrows}}}}

All normal rules are unchanged otherwise.

a→2(a−1){displaystyle arightarrow _{2}(a-1)} is already equal to the aforementioned cg(a), and the function f(n)=n→nn{displaystyle f(n)=nrightarrow _{n}n} is much faster growing than Conway and Guy's cg(n).

Note that expressions like a→bc→de{displaystyle arightarrow _{b}crightarrow _{d}e} are illegal if b and d are different numbers; one chain must only have one type of right-arrow.

However, if we modify this slightly such that:

a→bc→de=a→bc→d−1c→d−1c→d−1⋯→d−1c→d−1c→d−1c⏟e arrows{displaystyle arightarrow _{b}crightarrow _{d}e=arightarrow _{b}underbrace {crightarrow _{d-1}crightarrow _{d-1}crightarrow _{d-1}dots rightarrow _{d-1}crightarrow _{d-1}crightarrow _{d-1}c} _{e{text{ arrows}}}}

then not only does a→bc→de{displaystyle arightarrow _{b}crightarrow _{d}e} become legal, but the notation as a whole becomes much stronger.^[2]

See also

• Steinhaus–Moser notation


• Systematically creating ever faster increasing sequences

References

External links

• Factoids > big numbers


• Robert Munafo's Large Numbers


• The Book of Numbers by J. H. Conway and R. K. Guy