Graham's number

Graham's number, named after Ronald Graham, is often described as the largest number that has ever been seriously used in a mathematical proof. It is too large to be written in scientific notation because even the digits in the exponent would exceed the number of particles in the visible universe, so it needs special notation to write down. However, as many of its final digits as are desired may be calculated using elementary number theory. The last 10 digits of Graham's number are ...2,464,195,387. Graham's number is much larger than other well known large numbers such as a googol and a googolplex.

Graham's problem

Graham's number is connected to the following problem in the branch of mathematics known as Ramsey theory:

Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on $2^{n}$ vertices. Then colour each of the edges of this graph using only the colours red and black. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices that lies in a plane?

Or more colloquially:

Take a number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. Now assign every pair of committees to one of two secretaries. How many people must be in the original group so that no matter how the assignments are made there will always be a secretary with a group of four committees where all the people belong to an even number of these four committees?

Although the solution to this problem is not yet known, Graham's number is the smallest known upper bound.

In his 1989 book Penrose Tiles to Trapdoor Ciphers (ISBN 0883855216), Martin Gardner wrote "Ramsey-theory experts believe the actual Ramsey number for this problem is probably 6, making Graham's number perhaps the worst smallest-upper-bound ever discovered." More recently, however, Geoff Exoo of Indiana State University has shown (in 2003) that it must be at least 11 and provided evidence that it is larger.

Graham's number is said to be the largest number ever put to practical use. It is even bigger than Moser's number, which is another very large number.

Definition of Graham's number

Graham's number G is a member of the following recursive sequence defined with the help of Knuth's up-arrow notation $\uparrow$ as follows:

g₁=$3\uparrow \uparrow \uparrow \uparrow 3$

and

g_n=$3\uparrow \cdots \uparrow 3$, where there are g_n-1 of the $\uparrow$.

In this sequence, Graham's number is g₆₄.

Equivalently, define 4(n) = hyper(4,x+2,3) = 3→3→n, then, using functional powers, G=f⁶⁴(4).

Graham's number G itself can not succinctly be expressed in Conway chained arrow notation, but $3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$, see bounds on Graham's number in terms of Conway chained arrow notation.

See also

• Large number
• Knuth's up-arrow notation
• Hyper operator
• Ramsey theory

External links

• "A Ramsey Problem on Hypercubes" by Geoff Exoo
• Mathworld article on Graham's number
• How to calculate Graham's number