Graham's number
Graham's number is an immense number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory.
As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space.
Thus Graham's number cannot be expressed even by physical universe-scale power towers of the form
However, Graham's number can be explicitly given by computable recursive formulas using Knuth's up-arrow notation or equivalent, as was done by Ronald Graham, the number's namesake.
As there is a recursive formula to define it, it is much smaller than typical busy beaver numbers, the latter of which grow faster than any computable sequence.
Though too large to ever be computed in full, the sequence of digits of Graham's number can be computed explicitly via simple algorithms; the last 13 digits are ...7262464195387.
Using Knuth's up-arrow notation, Graham's number is
Graham's number was used by Graham in conversations with popular science writer Martin Gardner as a simplified explanation of the upper bounds of the problem he was working on.
In 1977, Gardner described the number in Scientific American, introducing it to the general public.
At the time of its introduction, it was the largest specific positive integer ever to have been used in a published mathematical proof.
The number was described in the 1980 Guinness Book of World Records, adding to its popular interest.
Other specific integers (such as TREE(3)) known to be far larger than Graham's number have since appeared in many serious mathematical proofs, for example in connection with Harvey Friedman's various finite forms of Kruskal's theorem.
Additionally, smaller upper bounds on the Ramsey theory problem from which Graham's number was derived have since been proven to be valid.
Graham's number is connected to the following problem in Ramsey theory: Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices.
Colour each of the edges of this graph either red or blue.
What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?In 1971, Graham and Rothschild proved the Graham–Rothschild theorem on the Ramsey theory of parameter words, a special case of which shows that this problem has a solution N*.
They bounded the value of N* by 6 ≤ N* ≤ N, with N being a large but explicitly defined number where
[2] This was reduced in 2014 via upper bounds on the Hales–Jewett number to which contains three tetrations.
This weaker upper bound for the problem, attributed to an unpublished work of Graham, was eventually published and named by Martin Gardner in Scientific American in November 1977.
[7] The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977, writing that Graham had recently established, in an unpublished proof, "a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof."
The 1980 Guinness Book of World Records repeated Gardner's claim, adding to the popular interest in this number.
While Graham was trying to explain a result in Ramsey theory which he had derived with his collaborator Bruce Lee Rothschild, Graham found that the said quantity was easier to explain than the actual number appearing in the proof.
Because the number which Graham described to Gardner is larger than the number in the paper itself, both are valid upper bounds for the solution to the problem studied by Graham and Rothschild.
[8] Using Knuth's up-arrow notation, Graham's number G (as defined in Gardner's Scientific American article) is
, which is a version of the rapidly growing Ackermann function A(n, n).
for all n.) The function f can also be expressed in Conway chained arrow notation as
To convey the difficulty of appreciating the enormous size of Graham's number, it may be helpful to express—in terms of exponentiation alone—just the first term (g1) of the rapidly growing 64-term sequence.
In other words, g1 is computed by first calculating the number of towers,
The magnitude of this first term, g1, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend.
Even n, the mere number of towers in this formula for g1, is far greater than the number of Planck volumes (roughly 10185 of them) into which one can imagine subdividing the observable universe.
