- Graham's number
Graham's number, named after
Ronald Graham , is a large number that is an upper bound on the solution to a certain problem inRamsey theory . This number gained a degree of popular attention whenMartin Gardner described it in the "Mathematical Games" section of "Scientific American" in November 1977, writing that "In an unpublished proof, Graham has recently established ... a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof." The 1980Guiness Book of World Records repeated Gardner's claim, adding to the popular interest in this number. Graham's number is much larger than other well-knownlarge number s such as agoogol and agoogolplex , and even larger thanSkewes' number andMoser's number , other well-known large numbers. Indeed, it is not possible, given the limitations of ouruniverse , to denote Graham's number, or any reasonable approximation of it, in a conventional system of numeration. Even "power towers" of the form a ^{ b ^{ c ^{ cdot ^{ cdot ^{ cdot} are useless for this purpose, although it can be easily described by recursive formulas usingKnuth's up-arrow notation or the equivalent, as was done by Graham. The last ten digits of Graham's number are ...2464195387.Specific integers known to be far larger than Graham's number have since appeared in many serious mathematical proofs (e.g., in connection with Friedman's various finite forms of Kruskal's theorem).
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 acomplete 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 which lie in a plane?"Graham & Rothschild [1971] proved that this problem has a solution, "N*", and gave as a bounding estimate 6 ≤ "N*" ≤ "N", with "N" a particular, explicitly defined, very large number; however, Graham (in unpublished work) revised this upper bound to be a much larger number. Graham's revised upper bound was later published — and dubbed "Graham's number" — by Martin Gardner in ["Scientific American", "Mathematical Games", November 1977] . The "lower" bound was later improved by Exoo [2003] , who showed the solution to be at least 11, and provided experimental evidence suggesting that it is at least 12. Thus, the best known bounding estimate for the solution "N*" is 11 ≤ "N*" ≤ "G", where "G" is Graham's number.
Definition of Graham's number
Using
Knuth's up-arrow notation , Graham's number "G" (as defined in Gardner's "Scientific American" article) is: :left. egin{matrix} &3underbrace{uparrow dotsdotsdotsdots uparrow}3 \ &3underbrace{uparrow dotsdotsdots uparrow}3 \ G equiv &underbrace{qquad vdots qquad} \ &3underbrace{uparrow dots uparrow}3 \ &3uparrow uparrow uparrow uparrow3 end{matrix} ight } ext{64 layers}: where the number of arrows in each layer, starting at the top layer, is specified by the value of the next layer below it.Equivalently,
:G = g_{64}, ext{ where }g_1=3uparrowuparrowuparrowuparrow 3, g_n = 3uparrow^{g_{n-13,
or
:G = f^{64}(4), ext{ where }f(n) = 3 uparrow^n 3,
where a superscript on an up-arrow indicates how many arrows there are, and a superscript on "f" indicates function iteration. The function "f" is a special case of the hyper() family of functions, f(n) = ext{hyper}(3,n+2,3), and can also be expressed in Conway chained arrow notation as f(n) = 3 ightarrow 3 ightarrow n. The latter notation also provides the following bounds on "G": 3 ightarrow 3 ightarrow 64 ightarrow 2 < G < 3 ightarrow 3 ightarrow 65 ightarrow 2.,
Magnitude of Graham's number
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" ("g"1) of the rapidly growing 64-term sequence. First, in terms of
tetration (uparrowuparrow) alone::g_1 = 3 uparrow uparrow uparrow uparrow 3 = 3 uparrow uparrow uparrow (3 uparrow uparrow uparrow 3) = 3 uparrowuparrow (3 uparrowuparrow (3 uparrowuparrow dots (3 uparrowuparrow 3) dots ))
where the number of 3s in the expression on the right is
:3 uparrow uparrow uparrow 3 = 3 uparrow uparrow (3 uparrow uparrow 3).
Now each tetration (uparrowuparrow) operation reduces to a "tower" of exponentiations (uparrow) according to the definition
:3 uparrowuparrow X = 3 uparrow (3 uparrow (3 uparrow dots (3 uparrow 3) dots )) = 3^{3^{cdot^{cdot^{cdot^{3} quad ext{where there are X 3s}.
Thus,
:g_1 = 3 uparrowuparrow (3 uparrowuparrow (3 uparrowuparrow dots (3 uparrowuparrow 3) dots )) quad ext{where the number of 3s is} quad 3 uparrow uparrow (3 uparrow uparrow 3)
becomes, solely in terms of repeated "exponentiation towers",
:g_1 = left. egin{matrix}3^{3^{cdot^{cdot^{cdot^{cdot^{3end{matrix} ight } left. egin{matrix}3^{3^{cdot^{cdot^{cdot^{3}end{matrix} ight } dots left. egin{matrix}3^{3^3}end{matrix} ight } 3 quad ext{where the number of towers is} quad left. egin{matrix}3^{3^{cdot^{cdot^{cdot^{3}end{matrix} ight } left. egin{matrix}3^{3^3}end{matrix} ight } 3
and where the number of 3s in each tower, starting from the leftmost tower, is specified by the value of the next tower to the right.
The magnitude of this first term, "g"1, is so large that it is practically incomprehensible, even though the above display is relatively easy to comprehend. (Even the mere "number of towers" in this formula for "g"1 is far greater than the number of
Planck volume s into which one can imagine subdividing theobservable universe .) And after this first term, there still remain another 63 terms in the rapidly growing "g" sequence before Graham's number "G" = "g"64 is reached.Decimal digits of Graham's number
Graham's number is a "power tower" of the form 3uparrowuparrow"n" (with a very large value of "n"), so its least-significant decimal digits must satisfy certain properties common to all such towers. One of these properties is that "all such towers of height greater than d (say), have the same sequence of d rightmost decimal digits". This is a special case of a more general property: The "d" rightmost decimal digits of all such towers of height greater than "d"+2, are "independent" of the topmost "3" in the tower; i.e., the topmost "3" can be changed to any other nonnegative integer without affecting the "d" rightmost digits.
The following table illustrates, for a few values of "d", how this happens. For a given height of tower and number of digits "d", the full range of "d"-digit numbers (10"d" of them) does "not" occur; instead, a certain smaller subset of values repeats itself in a cycle. The length of the cycle and some of the values (in parentheses) are shown in each cell of this table:
The particular rightmost "d" digits that are ultimately shared by all sufficiently tall towers of 3s are in bold text, and can be seen developing as the tower height increases. For any fixed number of digits "d" (row in the table), the number of values possible for 3uparrow3uparrow...3uparrow"x" mod 10"d", as "x" ranges over all nonnegative integers, is seen to decrease steadily as the height increases, until eventually reducing the "possibility set" to a single number (colored cells) when the height exceeds "d"+2.
A simple algorithm [ [http://mathforum.org/library/drmath/view/51625.html The Math Forum @ Drexel ("Last Eight Digits of Z")] ] for computing these digits may be described as follows: let x = 3, then iterate, "d" times, the assignment "x" = 3"x" mod 10"d". The final value assigned to "x" (as a base-ten numeral) is then composed of the "d" least-significant decimal digits of 3uparrowuparrow"n", for all "n" > "d". (If the final value of "x" has only "d"-1 decimal digits, add a leading 0.)
This algorithm produces the following 100 rightmost decimal digits of Graham's number (or any tower of more than 100 3s):
...9404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387.
ee also
* TREE(3)
Notes
References
*cite journal|author=Graham, R. L. |coauthors= Rothschild, B. L.|title=Ramsey's Theorem for n-Parameter Sets |journal= Transactions of the American Mathematical Society|volume=159|pages=257–292|year=1971|doi=10.2307/1996010
*cite journal|author=Gardner, Martin|title=Mathematical Games|journal= Scientific American|volume=237|pages=18–28|year=1977|month=November; reprinted (revised 2001) in the following book:
*cite book|year=2001|title=The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems|id=ISBN 0393020231|first=Martin|last=Gardner |authorlink= Martin Gardner
*cite book|year=1989|title=Penrose Tiles to Trapdoor Ciphers|id=ISBN 0-88385-521-6|first=Martin|last=Gardner |authorlink= Martin Gardner
*cite journal|author=Exoo, Geoffrey|title=A Euclidean Ramsey Problem|journal= Discrete Computational Geometry|volume=29|pages=223–227|year=2003|doi=10.1007/s00454-002-0780-5External links
* " [http://isu.indstate.edu/ge/GEOMETRY/cubes.html A Ramsey Problem on Hypercubes] " by Geoff Exoo
* [http://mathworld.wolfram.com/GrahamsNumber.html Mathworld article on Graham's number]
* [http://www-users.cs.york.ac.uk/susan/cyc/g/graham.htm How to calculate Graham's number]
* [http://numeropedia2.googlepages.com/SpeciallyLargeNumbers Numeropedia - the Special Encyclopedia of Numbers]
Wikimedia Foundation. 2010.