Graham's number is a very large number that arose as an upper bound on the answer of a problem in the mathematical field of Ramsey theory. It is much larger than many other large numbers introduced as effective bounds in mathematics, such as Skewes's bound, which in turn is much larger than a googolplex. Graham's number is so large that the observable universe is far too small to contain its ordinary digital representation, assuming that each digit occupies one Planck volume. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represented in the observable universe. Nor even can the number of digits of that number—and so forth, for a number of times far exceeding the total number of Planck volumes in the observable universe. Thus, Graham's number cannot be expressed even by physical universe-scale power towers of the form a b c ⋅ ⋅ ⋅ {\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}} , even though Graham's number is indeed a power of three. 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 sequence of which grows 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 10 digits of Graham's number are ...2464195387. Using Knuth's up-arrow notation, Graham's number is g 64 {\displaystyle g_{64}} , where
g n = { 3 ↑↑↑↑ 3 , if n = 1 and 3 ↑ g n − 1 3 , if n ≥ 2. {\displaystyle g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}}
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.
Context
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
N = F 7 ( 12 ) = F ( F ( F ( F ( F ( F ( F ( 12 ) ) ) ) ) ) ) , {\displaystyle N=F^{7}(12)=F(F(F(F(F(F(F(12))))))),}
where F ( n ) = 2 ↑ n 3 {\displaystyle F(n)=2\uparrow ^{n}3} in Knuth's up-arrow notation; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2 in Conway chained arrow notation. This was reduced in 2014 via upper bounds on the Hales–Jewett number to
N ′ = 2 ↑↑ ( 2 ↑↑ ( 3 + 2 ↑↑ 8 ) ) , {\displaystyle N'=2\uparrow \uparrow (2\uparrow \uparrow (3+2\uparrow \uparrow 8)),}
which contains three tetrations. In 2019 this was further improved to
… excerpt ends here. Continue reading the full article.
