big numbers

Numbers go on for ever, but our notation does not. If you want to write down the value of a very big number (way bigger even than a googolplex ), the mathematical notations for factorial or exponentiation, the fastest growing 'conventional' functions, eventually becomes unweildy; you get too many factorials or exponents to manipulate easily. Something more extensible is needed.

The so-called "large primes " -- useful for cryptography -- are relatively small compared to the kind of numbers that soon arise in these notations.


Knuth's up-arrow notation

In 1976 Donald Knuth published his up-arrow notation for large numbers. The arrows 'associate to the right' (following exponentiation). So a ^ b ^ c ^ d means a ^( b ^( c ^ d )), etc. This association gives the largest value.

  1. m n = m + m + ... + m ( n terms) = m × n
  2. m ^ n = m m ... m ( n terms) = m n
    • m ^1 = m
    • m ^ n = m ( m ... m ( n -1 terms)) = m m ^( n -1)
      • 2^2 = 2×2 = 4; 2^3 = 2×2^2 = 8; 2^4 = 2×2^3 = 16; etc...
      • 3^2 = 3×3 = 9; 3^3 = 3×3^2 = 27; 3^4 = 3×3^3 = 81; etc...
      • 4^2 = 4×4 = 16; 4^3 = 4×4^2 = 64; 4^4 = 4×4^3 = 256; etc...
  3. m ^^ n = m ^ m ^...^ m ( n terms) = m m ... m
    • m ^^1 = m
    • m ^^ n = m ^( m ^...^ m ( n -1 terms)) = m ^ m ^^( n -1)
      • 2^^2 = 2^2 = 4
      • 2^^3 = 2^2^^2 = 2^4 = 16
      • 2^^4 = 2^2^^3 = 2^16 = 65536
      • 3^^2 = 3^3 = 27
      • 3^^3 = 3^3^^2 = 3^27 = 7625597484987
      • 3^^4 = 3^3^^3 = 3^7625597484987
      • 4^^2 = 4^4 = 256
      • 4^^3 = 4^4^^2 = 4^256
      • 4^^4 = 4^4^^3 = 4^4^256
  4. m ^^^ n = m ^^ m ^^...^^ m ( n terms)
    • m ^^^1 = m
    • m ^^^ n = m ^^( m ^^ ... ^^ m ( n -1 terms)) = m ^^ m ^^^( n -1)
      • 2^^^2 = 2^^2 = 4
      • 2^^^3 = 2^^2^^^2 = 2^^4 = 65536
      • 2^^^4 = 2^^2^^^3 = 2^^65536 = 2^2^...^2 (65536 terms)
      • 3^^^2 = 3^^3 = 7625597484987
      • 3^^^3 = 3^^3^^^2 = 3^^7625597484987 = 3^3^...^3 (7625597484987 terms)
      • 3^^^4 = 3^^3^^^3 = 3^^3^...^3 (7625597484987 terms)
        = 3^...^3 (3^...^3 (7625597484987 terms) terms)
      • 4^^^2 = 4^^4 = 4^4^256
      • 4^^^3 = 4^^4^^^2 = 4^^4^4^256 = 4^...^4 (4^4^256 terms)
      • 4^^^4 = 4^^4^^^3 = 4^^4^...^4 (4^4^256 terms)
  5. m ^^^^ n = m ^^^ m ^^^...^^^ m ( n terms)
    • m ^^^^1 = m
    • m ^^^^ n = m ^^^( m ^^^ ... ^^^ m ( n -1 terms)) = m ^^^ m ^^^^( n -1)
      • 2^^^^2 = 2^^^2 = 4
      • 2^^^^3 = 2^^^2^^^^2 = 2^^^4 = 2^2^...^2 (65536 terms)
      • 2^^^^4 = 2^^^2^^^^3 = 2^^^2^2^...^2 (65536 terms)
      • 3^^^^2 = 3^^^3 = 3^3^...^3 (7625597484987 terms)
      • 3^^^^3 = 3^^^3^^^^2 = 3^^^3^3^...^3 (7625597484987 terms)
        = 3^^3^3^...^3 (3^3^...^3 (7625597484987 terms) terms)
      • 4^^^^2 = 4^^^4 = 4^^4^...^4 (4^4^256 terms)
  6. etc...

Eventually, as for cases like Graham's number, you get too many up-arrows to manipulate easily. Something more extensible is needed.


Conway's chained arrow notation

John H. Conway has gone 'one' step further:

  1. a --> b --> c = a ^^...^^ b , with c up arrows
  2. The chain can be reduced in length when the last item is a 1
    a --> b --> ... x --> 1 = a --> b --> ... x
  3. The last item in the chain can be reduced in size by 1
    a ... x --> y --> ( z + 1) depends on y :
    1. a ... x --> 1 --> ( z + 1) = a ... x
    2. a ... x --> 2 --> ( z + 1) = a ... x --> ( a ... x ) --> z
    3. a ... x --> 3 --> ( z + 1) = a ... x --> ( a ... x --> ( a ... x ) --> z ) --> z
    4. etc... (where the brackets can be removed once the number inside has been evaluated)

Eventually, you get too many right arrows to manipulate easily. Something more extensible is needed...


Steinhaus's polygon notation

It is easy to write down very large numbers. Such giants can be defined very simply if we agree to write [a in triangle] instead of a a , [a in square] instead of ' a in a triangles', and [a in circle] instead of ' a in a squares'. Then the number 'Mega' = [2 in circle] is already too great to have any physical meaning,

[Mega]

the last symbol being 256 in 256 triangles, and the reason why we have abandoned the ordinary system of writing numbers is clear. (The reader may try to explain the 'Megiston' given by [10 in circle] ).

-- H. Steinhaus. Mathematical Snapshots , Ch.1, 3rd edn. 1983
[note that there is an error in the diagram as printed: it should read ... [2 in circle] = [2 in 2 squares] = ...]


Moser's polygon notation

Leo Moser extended Steinhaus' notation. Rather than going to a circle for the third level, Moser continues the sequence of polygons with a pentagon, an hexagon, and so on. So we have

In order to express general relationships, it is useful to have a rather different notation, than captures the number of sides of the polygons, and the number of repetitions of the polygons, symbolically. So, instead of drawing the polygon, I write the number of sides in square brackets: [a in triangle] = a [3]; [a in triangle in square] = a [3][4], etc. And instead of drawing repeated similar polygons, I subscript the 'polygon number' with the repetition number: [a in 2 triangles] = a [3][3] = a [3] 2 ; [a in 2 triangles in 3 squares] = a [3][3][4][4][4] = a [3] 2 [4] 3 , etc. This means we can define the notation in general:

The polygons associate to the left, and bind more strongly that conventional mathematical operators. So n [2]^ n [3] means ( n [2])^( n [3]). Expanding deeply nested terms from the inside out (expand the definition of the innermost polygon first), or from the outside in (expand the definition of the outermost polygon first) gives the same result.

  1. [a in triangle] = a [3] = a^a
    • n [3] = n^n
    • n [3] 2 = n [3][3] = n [3]^ n [3] = ( n^n )^( n^n )
    • n [3] 3 = n [3] 2 [3] = n [3] 2 ^ n [3] 2 = (( n^n )^( n^n ))^(( n^n )^( n^n ))
    • n [3] 4 = n [3] 3 [3] = n [3] 3 ^ n [3] 3 = ((( n^n )^( n^n ))^(( n^n )^( n^n )))^((( n^n )^( n^n ))^(( n^n )^( n^n )))
    • n [3] k = (...( n^n )^( n^n )...)^...^(...( n^n )^( n^n )...)[2 k terms]
    • 2[3] = 2^2 = 4
    • 2[3] 2 = 2[3]^2[3] = 4^4 = 256
    • 2[3] 3 = 2[3] 2 ^2 2 [3] = 256^256 = 10 616.509...
    • 2[3] 4 = 2[3] 3 ^2 3 [3] = 10 616.509... ^10 616.509... = 10 616.509... x 10 616.509... = 10 10 619.3...
    • 2[3] 5 = 2[3] 4 ^2[3] 4 = 10 10 619.3... ^10 10 619.3...
    • etc..
    • 3[3] = 3^3 = 27
    • 3[3] 2 = 3[3]^3[3] = 27^27 = 443426488243037769948249630619149892803 = 10 38.646...
    • 3[3] 3 = 3[3] 2 ^3[3] 2 = 10 38.646... ^10 38.646... = 10 10 40.23...
    • etc...
    • 4[3] = 4^4 = 2[3]^2[3] = 2[3][3] = 2[3] 2
    • 4[3] 2 = 4[3][3] = 2[3] 2 [3] = 2[3] 3
    • 4[3] 3 = 4[3] 2 [3] = 2[3] 3 [3] = 2[3] 4
    • 4[3] k = 2[3] k +1
  2. [a in square] = a [4] = a [3] a
    • n [4] = n [3] n = (...( n^n )^( n^n )...)^...^(...( n^n )^( n^n )...)[2 n terms]
    • 2[4] = 2[3] 2 = 256
    • 2[4] 2 = 2[4][4] = 256[4] = 256[3] 256
    • 2[4] 3 = 2[4] 2 [4] = 256[3] 256 [4] = 256[3] 256 [3] 256[3] 256
    • etc...
    • 3[4] = 3[3] 3 = 3[3] 2 ^3[3] 2 = (27^27)^(27^27)
    • 3[4] 2 = 3[3] 3 [4] = (3[3] 2 ^3[3] 2 )[4] = ((27^27)^(27^27))[4]
      = ((27^27)^(27^27))[3] (27^27)^(27^27)
    • etc...
    • 4[4] = 4[3] 4 = 2[3] 5
    • etc...
  3. [a in pentagon] = a [5] = a [4] a
    • 2[5] = Steinhaus' Mega = 2[4] 2 = 2[3] 2 [4] = (2^2)[3][4] = (4^4)[4] = 256[3] 256
    • A polygon with 2[5] sides is a Megagon . It looks pretty circular if drawn!
    • 2[5] 2 = 2[5][5] = 2[4] 2 = 256[3] 256 [5]
    • 3[5] = 3[4] 3 = ((27^27)^(27^27))[3] (27^27)^(27^27) [4]
    • 10[5] = Steinhaus' Megiston = 10[4] 10
    • etc..
  4. a [6] = a [5] a
    1. 2[6] = 2[5] 2 = 256[3] 256 [5]
    2. 3[6] = 3[5] 3 = 3[5][5] 2 = ((27^27)^(27^27))[3] (27^27)^(27^27) [4][5] 2
  5. in general, a [ k +1] = a [ k ] a

Moser's number = '2 in a Megagon' = 2[2[5]] = 2[256[3] 256 ]

Which of Moser's number and Graham's number is the larger? The Moser construction yields big numbers much faster than does the up-arrow notation, but there are a lot of up-arrows in the Graham number.