Editing TheNumber

Graham's number G_63 is the best upper bound proven for this Ramsey theory problem:

''The smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar complete graph of one color will  be forced. Stated colloquially, this is equivalent to considering every possible committee from some number of people n and enumerating every pair of committees. Now assign each pair of committees to one of two groups, and find the smallest n that will guarantee that there are four committees in which all pairs fall in the same group and all the people belong to an even number of committees.''

(Hoffman 1998 p. 54, quoted by http://mathworld.wolfram.com/GrahamsNumber.html)

In other words, each person is a dimension of the cube, each committee is a vertex, a pair of committees is a line joining vertices, the two groups are the colorings of the lines, and the people on an even number of committees ensures that the four chosen vertices (committees) lie on a hyperplane. (But I don't think that last clause is correct. In the 3-cube, (000),(110),(101), and (011) don't lie on a hyperplane, but all three people are on two committees.)

The paper introducing Graham's number can be found at http://www.jstor.org/view/00029947/di970177/97p00383/0
(page 290 is where he mentions the number).

------

To define Graham's number, we use arrow notation. A single up-arrow is the exponentiation operator, or iterated multiplication (multiplication of course being iterated addition). A double arrow is iterated exponentiation. The triple arrow is iterated double-arrow, and so on:

m*n = m+m+m+m+...+m, n times.
 m^n = m*m*m*m*...*m, n times.
 m^^n = m^m^m^m^...^m, n times.  This is sometimes referred to as a power tower.
 m^^^n = m^^m^^m^^m^^...^^m, n times
       = m^^m^^m^^m^^..^^x, with (n-2) m's,
         where x = m^m^m^m^..^m, m times.

And so on: Clearly this gets big quickly (although not as fast as other functions out there).  An important property is that the order of operations starts at the right side and works to the left, as in the last example.  Now for some examples:

2^2 = 2*2 = 4
 2^^2 = 2^2 = 4
 2^^^2 = 2^^2 = 4

2^3 = 2*2*2 = 8
 2^^3 = 2^2^2 = 2^(4) = 16
 2^^^3 = 2^^2^^2 = 2^^4 = 2^2^2^2 = 2^2^4 = 2^16 = 65536

3^3 = 3*3*3 = 27
 3^^3 = 3^3^3 = 3^27 = 7,625,597,484,987
 3^^^3 = 3^^3^^3 = 3^^(7,625,597,484,987) = 3^3^3^...^3 (7,625,597,484,987 times)

4^4 = 4*4*4*4 = 256
 4^^4 = 4^4^4^4 = 4^4^256 = kinda big (but not very compared to later examples)

------

Okay, now we have an idea of up arrow notation, let's go to G_63. We start with G_0 (these are capital Gs with numerical subscripts).

G_0 = 3^^^^3
     = 3^^^3^^^3
     = 3^^^(3^^(7,625,597,484,987))
     = REALLY HUGE

This blows the number of particles in the universe out of the water.  (Last I hear, the estimated number of elementary particles was something like 2^100, but even if it were 2^(100^100) it isn't even comparable to this number.)

Now, to get the next item in the series:

G_1 = 3^^^^..^3 where there are G_0 up arrows

wow

To continue:

G_2 = 3^^^^..^3 where there are G_1 up arrows

Continue this until you reach G_63 and you've found the upper limit to the problem stated before.

super wow

-----

Interesting facts:
# G_{-1} = 4 (this is obvious if you look at it).
# G_63 in decimal notation ends in 7.
# This is only an upper bound on the answer... a lower bound is 11.
# G_63 is the largest finite number used in a "serious" mathematical proof.

-----

About notation: The Mathworld article on Graham's Number uses an alternative "little g" notation.  It defines g_1 = G_0, g_2 = G_1, and so on.  Therefore it gives the upper bound as g_64 instead of G_63.

Summary:
This change is a minor edit.
(Visit Preferences to set your user name.)

View other revisions
FunWiki | RecentChanges | Preferences