Difference between revisions of "Graham's number"

Revision as of 16:51, 18 September 2008

Graham's number, named after Ronald Graham, is a very large number which is often described as the largest number that has ever been seriously used in a mathematical proof. It is much too large to be written in scientific notation, and 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 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 <math>2^n</math> 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?

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 is the 65th in the following sequence, where each member is the number of Knuth arrows needed for the next member:

<math>4,\ 3\uparrow\uparrow\uparrow\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \ldots</math>

Equivalently, define f(n) = hyper(3,n+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 <math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2 </math>, see bounds on Graham's number in terms of Conway chained arrow notation.

External links

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