Editing Graham's number

{{Short description|Large number coined by Ronald Graham}}
{{About|the very large number named after Ronald Graham|the investing term named after Benjamin Graham|Graham number}}
'''Graham's number''' is an [[Large numbers|immense 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 such as [[Skewes's number]] and [[Moser's number]], both of which are in turn much larger than a [[googolplex]]. As with these, it is so large that the [[observable universe]] is far too small to contain an ordinary [[Numerical digit|digital representation]] of Graham's number, assuming that each digit occupies one [[Planck volume]], possibly the smallest measurable space. 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 [[Tetration|power towers]] of the form <math>a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}}</math>, even though Graham's number is indeed a [[power of three|power of 3]].

However, Graham's number can be explicitly given by [[computable function|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 13 digits are ...7262464195387. Using [[Knuth's up-arrow notation]], Graham's number is <math>g_{64}</math>,<ref>{{cite web | url=https://mathworld.wolfram.com/GrahamsNumber.html | title=Graham's Number }}</ref> where
<math display="block">
  g_n =
   \begin{cases}
    3\uparrow\uparrow\uparrow\uparrow3, & \text{if } n=1 \text{ and} \\
    3\uparrow^{g_{n-1}}3, & \text{if } n \ge 2.
   \end{cases}
 </math>

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 (mathematician)|Harvey Friedman]]'s various finite forms of [[Kruskal's theorem#Friedman's finite form|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==
[[Image:GrahamCube.svg|right|thumb|Example of a 2-colored 3-dimensional cube containing one single-coloured 4-vertex coplanar complete subgraph. The subgraph is shown below the cube. This cube would contain no such subgraph if, for example, the bottom edge in the present subgraph were replaced by a blue edge – thus proving by counterexample that ''N''* > 3.]]

Graham's number is connected to the following problem in [[Ramsey theory]]:
{{quote|Connect each pair of [[vertex (geometry)|geometric vertices]] of an ''n''-dimensional [[hypercube]] to obtain a [[complete graph]] on 2<sup>''n''</sup> [[vertex (graph theory)|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 word]]s, a special case of which shows that this problem has a solution ''N*''. They bounded the value of ''N*'' by {{nowrap|6 ≤ ''N*'' ≤ ''N''}}, with ''N'' being a large but explicitly defined number

:<math>N=F^7(12) = F(F(F(F(F(F(F(12))))))),</math>

where <math>F(n) = 2\uparrow^n 3</math> in [[Knuth's up-arrow notation]]; the number is between {{nowrap|4 → 2 → 8 → 2}} and {{nowrap|2 → 3 → 9 → 2}} in [[Conway chained arrow notation]].<ref>{{cite web |url=http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |title=Graham's number records |publisher=Iteror.org |access-date=2014-04-09 |archive-url=https://web.archive.org/web/20131019135451/http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |archive-date=2013-10-19 |url-status=dead }}</ref> This was reduced in 2014 via upper bounds on the [[Hales–Jewett theorem|Hales–Jewett number]] to

:<math>N' = 2 \uparrow\uparrow 2 \uparrow\uparrow (3 + 2 \uparrow\uparrow 8),</math>

which contains three [[tetration]]s.<ref>{{cite journal |last1=Lavrov|first1=Mikhail |last2=Lee|first2=Mitchell |last3=Mackey|first3=John |date=2014 |title=Improved upper and lower bounds on a geometric Ramsey problem |journal=[[European Journal of Combinatorics]] |volume=42 |pages=135–144 |doi=10.1016/j.ejc.2014.06.003|doi-access=free }}</ref> In 2019 this was further improved to:<ref>{{cite arXiv |eprint=1905.05617 |last1=Lipka |first1=Eryk |title=Further improving of upper bound on a geometric Ramsey problem |class=math.CO |year=2019 }}</ref>

:<math>N'' = (2 \uparrow\uparrow 5138) \cdot ((2 \uparrow\uparrow 5140) \uparrow\uparrow (2 \cdot 2 \uparrow\uparrow 5137)) \ll 2 \uparrow\uparrow (2 \uparrow\uparrow 5138)</math> 

The lower bound of 6 was later improved to 11 by Geoffrey Exoo in 2003,<ref>{{cite journal |last=Exoo |first=Geoffrey |date=2003 |title=A Euclidean Ramsey Problem |journal=[[Discrete & Computational Geometry]] |volume=29 |issue=2 |pages=223–227 |doi=10.1007/s00454-002-0780-5|doi-access=free }} Exoo refers to the Graham & Rothschild upper bound ''N'' by the term "Graham's number". This is not the "Graham's number" ''G'' published by Martin Gardner.</ref> and to 13 by Jerome Barkley in 2008.<ref>{{cite arXiv |eprint=0811.1055 |last1=Barkley |first1=Jerome |title=Improved lower bound on an Euclidean Ramsey problem |class=math.CO |year=2008 }}</ref> Thus, the best known bounds for ''N*'' are {{nowrap|13 ≤ ''N*'' ≤ ''N<nowiki>''</nowiki>''}}.

Graham's number, ''G'', is much larger than ''N'': it is <math>f^{64}(4)</math>, where <math>f(n) = 3 \uparrow^n 3</math>. 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.<ref>{{cite journal|author=Martin Gardner|author-link=Martin Gardner|date= 1977 |title= In which joining sets of points leads into diverse (and diverting) paths|journal=Scientific American|issue = November| url=http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html|archive-url=https://web.archive.org/web/20131019135451/http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html |archive-date=2013-10-19|url-status=dead }}</ref>

==Publication==
The number gained a degree of popular attention when [[Martin Gardner]] described it in the [[List_of_Martin_Gardner_Mathematical_Games_columns|"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. According to physicist [[John C. Baez|John Baez]], Graham invented the quantity now known as Graham's number in conversation with Gardner. 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.<ref>{{cite web | url = https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ | author = John Baez | author-link = John C. Baez | year = 2013 | title = A while back I told you about Graham's number... | archive-url = https://web.archive.org/web/20131113102114/https://plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ | archive-date = 2013-11-13 | access-date = 2013-01-11 | url-status = dead }}</ref>

==Definition==
Using [[Knuth's up-arrow notation]], Graham's number ''G'' (as defined in Gardner's ''Scientific American'' article) is
<math display="block">
\left.
 \begin{matrix}
  G &=&3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\
    & & \underbrace{\qquad \quad \vdots \qquad \quad} \\
    & &3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} \text{64 layers}
</math>

where the number of ''arrows'' in each layer is specified by the value of the next layer below it; that is,

<math display="block">G = g_{64},</math> where <math>g_1=3\uparrow\uparrow\uparrow\uparrow 3,</math>  <math>g_n = 3\uparrow^{g_{n-1}}3,</math>

and where a superscript on an up-arrow indicates how many arrows there are. In other words, ''G'' is calculated in 64 steps: the first step is to calculate ''g''<sub>1</sub> with four up-arrows between 3s; the second step is to calculate ''g''<sub>2</sub> with ''g''<sub>1</sub> up-arrows between 3s; the third step is to calculate ''g''<sub>3</sub> with ''g''<sub>2</sub> up-arrows between 3s; and so on, until finally calculating ''G'' = ''g''<sub>64</sub> with ''g''<sub>63</sub> up-arrows between 3s.

Equivalently,
<math display="block">G = f^{64}(4),\text{ where }f(n) = 3 \uparrow^n 3,</math>

and the superscript on ''f'' indicates an [[Iterated function|iteration of the function]], e.g., <math> f^4(n) = f(f(f(f(n))))</math>.  Expressed in terms of the family of [[hyperoperation]]s <math> \text{H}_0, \text{H}_1, \text{H}_2, \cdots</math>, the function ''f'' is the particular sequence <math>f(n) = \text{H}_{n+2}(3,3)</math>, which is a version of the rapidly growing [[Ackermann function]] ''A''(''n'', ''n''). (In fact, <math>f(n) > A(n, n)</math> for all ''n''.)  The function ''f'' can also be expressed in [[Conway chained arrow notation#Graham's number|Conway chained arrow notation]] as <math>f(n) = 3 \rightarrow 3 \rightarrow n</math>, and this notation also provides the following bounds on ''G'':

<math display="block"> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.</math>

===Magnitude===
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''<sub>1</sub>) of the rapidly growing 64-term sequence.  First, in terms of [[tetration]] (<math> \uparrow\uparrow</math>) alone:
<math display="block">
 g_1
  = 3 \uparrow \uparrow \uparrow \uparrow 3
  = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)
  = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots ))
</math>

where the number of 3s in the expression on the right is
<math display="block">3 \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow (3 \uparrow \uparrow 3).</math>

Now each tetration (<math>\uparrow\uparrow</math>) operation reduces to a power tower (<math>\uparrow</math>) according to the definition
<math display="block">3 \uparrow\uparrow X = 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots)) = 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}</math> where there are ''X'' 3s.

Thus,
<math display="block">
 g_1
  = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots ))
  \quad \text{where the number of 3s is}
  \quad 3 \uparrow \uparrow (3 \uparrow \uparrow 3)
</math>

becomes, solely in terms of repeated "exponentiation towers",
<math display="block">
 g_1 =
\underbrace{
  \left.
    \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}\end{matrix}
  \right \}
  \left.
    \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
  \right \}
    \dots
  \left.
    \begin{matrix}3^{3^3}\end{matrix}
  \right \}
    3}_{
  \left.
    \begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}
  \right \}
  \left.
    \begin{matrix}3^{3^3}\end{matrix}
  \right \}
    3}
</math>

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.

In other words, ''g''<sub>1</sub> is computed by first calculating the number of towers, <math> n = 3\uparrow (3\uparrow (3\ \dots\ \uparrow 3))</math> (where the number of 3s is <math> 3\uparrow (3\uparrow 3) = 7625597484987</math>), and then computing the ''n''<sup>th</sup> tower in the following sequence:

       1st tower:  <u>3</u>
      
       2nd tower:  3↑3↑3 (number of 3s is <u>3</u>) = <u>7625597484987</u>
      
       3rd tower:  3↑3↑3↑3↑...↑3 (number of 3s is <u>7625597484987</u>) = …
      
       ⋮
      
  ''g''<sub>1</sub> = ''n''<sup>th</sup> tower:  3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the <u>{{nowrap|''n &minus; 1''<sup>th</sup>}} tower</u>)
where the number of 3s in each successive tower is given by the tower just before it.  The result of calculating the third tower is the value of ''n'', the number of towers for ''g''<sub>1</sub>.

The magnitude of this first term, ''g''<sub>1</sub>, 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 ''g''<sub>1</sub>, is far greater than the number of Planck volumes (roughly 10<sup>185</sup> of them) into which one can imagine subdividing the [[observable universe]]. And after this first term, still another 63 terms remain in the rapidly growing ''g'' sequence before Graham's number ''G'' = ''g''<sub>64</sub> is reached. To illustrate just how fast this sequence grows, while ''g''<sub>1</sub> is equal to <math>3 \uparrow \uparrow \uparrow \uparrow 3</math> with only four up arrows, the number of up arrows in ''g''<sub>2</sub> is this incomprehensibly large number ''g''<sub>1</sub>.

==Mod ''n''==

The [[Modular arithmetic#Residue systems|residue]] of Graham's number mod ''n'', starting with ''n'' = 1, is

:0, 1, 0, 3, 2, 3, 6, 3, 0, 7, 9, 3, 1, 13, 12, 11, 7, 9, 18, 7, 6, 9, 18, 3, 12, 1, 0, 27, 10, 27, 23, 27, 9, 7, 27, 27, 36, 37, 27, 27, 27, 27, 2, 31, 27, 41, 6, 27, 6, 37, … {{OEIS|A240162}}

==References==
{{Reflist}}

===Bibliography===
* {{cite journal|author=Gardner, Martin|title=Mathematical Games|journal= Scientific American|volume=237|issue=5|pages=18–28|date=November 1977|url-access=subscription|url=http://www.nature.com/scientificamerican/journal/v237/n5/pdf/scientificamerican1177-18.pdf|doi=10.1038/scientificamerican1177-18|bibcode=1977SciAm.237e..18G}}; reprinted (revised) in Gardner (2001), cited below.
* {{cite book|year=1989|title=Penrose Tiles to Trapdoor Ciphers|isbn=978-0-88385-521-8|first=Martin|last=Gardner |author-link= Martin Gardner|publisher=Mathematical Association of America|location=Washington, D.C.}}
* {{cite book|year=2001|title=The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems|isbn=978-0-393-02023-6|first=Martin|last=Gardner |author-link= Martin Gardner|publisher=Norton|location=New York, NY}}
* {{cite journal|author=Graham, R. L. |author2=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 |url=https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf|jstor=1996010}} The explicit formula for ''N'' appears on p.&nbsp;290. This is not the "Graham's number" ''G'' published by Martin Gardner.
*{{cite book |last1=Graham |first1=R. L. |last2=Rothschild |first2=B. L. |editor-first=G-C |editor-last=Rota |title=Studies in Combinatorics (MAA Studies in Mathematics) |publisher=Mathematical Association of America |volume=17 |date=1978 |pages=80–99 |chapter=Ramsey Theory |isbn=978-0-88385-117-3}} On p.&nbsp;90, in stating "the best available estimate" for the solution, the explicit formula for ''N'' is repeated from the 1971 paper.

==External links==
* {{OEIS el|A133613|Graham's number}}
* [https://sites.google.com/site/largenumbers/home/3-2/3-2-9-graham Sbiis Saibian's article on Graham's number]
* "[http://isu.indstate.edu/ge/GEOMETRY/cubes.html A Ramsey Problem on Hypercubes]" by Geoff Exoo
* {{mathworld|urlname=GrahamsNumber|title=Graham's Number}}
* [http://www-users.cs.york.ac.uk/susan/cyc/g/graham.htm How to calculate Graham's number]
* [http://waitbutwhy.com/2014/11/1000000-grahams-number.html Conceptualizing Graham's number] 
* [http://www.math.ucsd.edu/~fan/ron/papers/pre_cube.pdf Some Ramsey results for the n-cube] prepublication mentions Graham's number
* {{cite web|last=Padilla|first=Tony|title=Graham's Number|url=http://www.numberphile.com/videos/grahamsnumber.html|work=Numberphile|publisher=[[Brady Haran]]|author2=Parker, Matt|access-date=2013-04-08|archive-url=https://web.archive.org/web/20140527212509/http://www.numberphile.com/videos/grahamsnumber.html|archive-date=2014-05-27|url-status=dead}}
* Archived at [https://ghostarchive.org/varchive/youtube/20211211/HX8bihEe3nA Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20140828084008/https://www.youtube.com/watch?v=HX8bihEe3nA&feature=autoshare Wayback Machine]{{cbignore}}: {{cite web|author1=Ron Graham|author-link1=Ronald Graham|title=What is Graham's Number? (feat Ron Graham)|url=https://www.youtube.com/watch?v=HX8bihEe3nA|work=Numberphile|date=21 July 2014 |publisher=[[Brady Haran]]|format=video}}{{cbignore}}
* Archived at [https://ghostarchive.org/varchive/youtube/20211211/GuigptwlVHo Ghostarchive]{{cbignore}} and the [https://web.archive.org/web/20140722171301/http://www.youtube.com/watch?v=GuigptwlVHo Wayback Machine]{{cbignore}}: {{cite web|author1=Ron Graham|author-link1=Ronald Graham|title=How Big is Graham's Number? (feat Ron Graham)|url=https://www.youtube.com/watch?v=GuigptwlVHo|work=Numberphile|date=22 July 2014 |publisher=[[Brady Haran]]|format=video}}{{cbignore}}
* [http://ankokudan.org/d/dl/others/Graham-16M.pdf The last 16 million digits of Graham's number] by the [[Darkside communication group]]

{{Large numbers}}

{{DEFAULTSORT:Graham's Number}}
[[Category:Ramsey theory]]
[[Category:Integers]]
[[Category:Large integers]]