Googology Wiki
Register
Googology Wiki
m (Jr Mime moved page SUCK to Graham's number over a redirect without leaving a redirect: Reverting Max Damage ~ Wiki Edition 1924)
No edit summary
Tag: Visual edit
Line 85: Line 85:
 
*\(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)
 
*\(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)
   
Assume that this method works. Then for any positive integer \(x\) such that \(G_{64} < 10^x\), \(N(x)\) coincides with \(G_{64}\). It means that \(3^{G_{64}} - G_{64}\) is divisible by \(10^x\) for any positive integer \(x\). It implies \(3^{G_{64}} - G_{64} = 0\), and it is contradition.
+
Assume that this method works forever. Then for any positive integer \(x\) such that \(G_{64} < 10^x\), \(N(x)\) coincides with \(G_{64}\). It means that \(3^{G_{64}} - G_{64}\) is divisible by \(10^x\) for any positive integer \(x\). It implies \(3^{G_{64}} - G_{64} = 0\), and it is contradition. However, if N is the number such that \(3 \uparrow\uparrow N = G_{64}\), then the number of correct digits this method produces is N-1. This is because the period of the last \(d\) digits of \(3^n\) in base 10 for \(d \ge 4\) is \(5 \times 10^{d-2}\), which evenly divides \(10^{d-1}\) but is greater than \(10^{d-2}\), meaning one convergent digit is added each time another 3 is added to the tower.
   
  +
The last d digits of Graham's number can be computed using the following algorithm:
While it is not known how to calculate the leading digit of Graham's number in base 10 in the current community, the leading digit must be 1 in base 2 (because all positive integers except 0 have this property), 1 in base 3 (because it is a power of 3) , and 3 in base 9 (because it is an odd-numbered power of 3). It is not known how to calculate the leading digit of Graham's number in any other base in the current community, unless if it is a power of 3 (such as 27), or at least comparable to Graham's number (such as Graham's number - 64).
 
  +
  +
\(N(0) = 3\)
  +
  +
\(N(x) = 3^{N(x-1) \mod \phi(10^d)} \mod 10^d\)
  +
  +
Using this, the last 20 digits of Graham's number in base 10 are ...04,575,627,262,464,195,387.
  +
 
While it is not known how to calculate the leading digit of Graham's number in base 10 in the current community (and it is highly unlikely that a method will be found), the leading digit must be 1 in base 2 (because all positive integers except 0 have this property), 1 in base 3 (because it is a power of 3) , and 3 in base 9 (because it is an odd-numbered power of 3). It is not known how to calculate the leading digit of Graham's number in any other base in the current community, unless if it is a power of 3 (such as 27), or at least comparable to Graham's number (such as Graham's number - 64).
   
 
== Video ==
 
== Video ==

Revision as of 17:29, 10 February 2020

For other uses, see Graham's number (disambiguation).
Graham's number in arrow notation

A concise definition of Graham's number.

Graham's number \(G_{64}\) is a famous large number, defined by Ronald Graham.[1]

Using up-arrow notation, it is defined as the 64th term of the following function:

\begin{eqnarray*} G_0 &=& 4 \\ G_1 &=& 3 \uparrow\uparrow\uparrow\uparrow 3 \\ G_2 &=& 3 \underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{G_1 \text{ arrows}} 3 \\ G_{k + 1} &=& 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_{G_k \text{ arrows}} 3 \\ G_{64} &=& \text{Graham's number} \end{eqnarray*}

Graham's number is commonly celebrated as the largest number ever used in a serious mathematical proof, although much larger numbers have since claimed this title (such as TREE(3) and SCG(13)). The smallest Bowersism exceeding Graham's number is corporal, and the smallest Saibianism exceeding Graham's number is graatagold.

History

Graham's number arose out of the following unsolved problem in Ramsey theory:

Let N* be the smallest dimension n of a hypercube such that if the lines joining all pairs of corners are two-colored for any nN*, a complete graph K4 of one color with coplanar vertices will be forced. Find N*.

220px-GrahamCube

An example of a cube with 12 planar K4's, with a single monochromatic K4 shown below. If you change the edge on the bottom of this K4 to blue, then the cube will contain no monochromatic planar K4's, thus showing that N* is at least 4.

To understand what this problem asks, first consider a hypercube of any number of dimensions (1 dimension would be a line, 2 would be a square, 3 would be a cube, 4 would be a tesseract (4-dimensional cube), etc.), and call that number of dimensions N. Then, imagine connecting all possible vertex pairs with lines, and coloring each of those red or blue - one such way you can color all of the vertex pairs of the 3-dimensional cube is shown to the right. What is the smallest number of dimensions N such that all possible colorings would have a monochromatic complete graph of four coplanar vertices (that is a set of four points that are connected in all possible ways, with all lines being the same color)?

Graham published a paper in 1971 proving that the answer exists, providing the upper bound \(F^{7}(12)\), where \(F(n) = 2 \uparrow^{n} 3\) in arrow notation.[2] Sbiis Saibian calls this number "Little Graham". Martin Gardner, when discovering the number's size, found it difficult to explain, and he devised a larger, easier-to-explain number which Graham proved in an unpublished 1977 paper. Martin Gardner wrote about the number in Scientific American and it even made it to Guiness World Records in 1980 as the largest number used in a mathematical proof, although a few years later the title was removed from Guinness World Records.

In 2013, the upper bound was further reduced to N' = 2↑↑2↑↑(3+2↑↑8) using the Hales–Jewett theorem [3], and to N" = (2↑↑5138) x ((2↑↑5140)↑↑(2 x (2↑↑5137))) << 2↑↑↑5 in 2019 [4]. As of 2014, the best known lower bound for N* is 13, shown by Jerome Barkley in 2008.[5]

2-2-2-2-2-2-9

Solved new upper bound (N') 2↑↑2↑↑2↑↑9.

Comparison

Since g0 is 4 and not 3, Graham's number cannot be expressed efficiently in chained arrow notation \(g_{64} \approx 3 → 3 → 64 → 2\) or BEAF \(\{3,65,1,2\} < g_{64} < \{3, 66, 1, 2\}\). Using Jonathan Bowers' G functions it is exactly G644 in base 3. It can be also exactly expressed in the Graham Array Notation as \([3,3,4,64]\).

Tim Chow proved that Graham's number is much larger than the Moser.[6] The proof hinges on the fact that, using Steinhaus-Moser Notation, n in a (k + 2)-gon is less than \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\). He sent the proof to Susan Stepney on July 7, 1998.[7] Coincidentally, Stepney was sent a similar proof by Todd Cesere several days later.

It has been proven that Graham's number is much less than \(\Sigma(64)\),[8] and later a better upper bound \(\Sigma(17)\) was proven.

In the fast-growing hierarchy, Graham's number can be shown to be less than \(f_{\omega+1}(64)\).

Approximations
Notation Approximation
Fast-growing hierarchy \(f_{\omega+1}(64)\)
Chained arrow notation \(3 \rightarrow 3\rightarrow 64\rightarrow 2\)
Hardy hierarchy \(H_{\omega^{\omega+1}}(64)\)
BEAF \(\{3,65,1,2\}\)
Extended Hyper-E Notation \(E[3]3\#\#4\#64\)
The Q-supersystem \(Q_{1,64}(3)\)
Hyperfactorial array notation \(64![2]\)
Strong array notation \(s(3,64,2,2)\)
X-Sequence Hyper-Exponential Notation \(3\{X+1\}65\)
Graham array notation \([3,3,4,64]\) (exact)
Slow-growing hierarchy \(g_{\Gamma_0}(65)\)

Calculating last digits

The final digits of Graham's number is not easily computed by a simple application of algorithms for modular exponentiation. Here is a simple but wrong algorithm to obtain the last \(x\) digits \(N(x)\) of Graham's number:

  • \(N(0) = 3\)
  • \(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)

Assume that this method works forever. Then for any positive integer \(x\) such that \(G_{64} < 10^x\), \(N(x)\) coincides with \(G_{64}\). It means that \(3^{G_{64}} - G_{64}\) is divisible by \(10^x\) for any positive integer \(x\). It implies \(3^{G_{64}} - G_{64} = 0\), and it is contradition. However, if N is the number such that \(3 \uparrow\uparrow N = G_{64}\), then the number of correct digits this method produces is N-1. This is because the period of the last \(d\) digits of \(3^n\) in base 10 for \(d \ge 4\) is \(5 \times 10^{d-2}\), which evenly divides \(10^{d-1}\) but is greater than \(10^{d-2}\), meaning one convergent digit is added each time another 3 is added to the tower.

The last d digits of Graham's number can be computed using the following algorithm:

\(N(0) = 3\)

\(N(x) = 3^{N(x-1) \mod \phi(10^d)} \mod 10^d\)

Using this, the last 20 digits of Graham's number in base 10 are ...04,575,627,262,464,195,387.

While it is not known how to calculate the leading digit of Graham's number in base 10 in the current community (and it is highly unlikely that a method will be found), the leading digit must be 1 in base 2 (because all positive integers except 0 have this property), 1 in base 3 (because it is a power of 3) , and 3 in base 9 (because it is an odd-numbered power of 3). It is not known how to calculate the leading digit of Graham's number in any other base in the current community, unless if it is a power of 3 (such as 27), or at least comparable to Graham's number (such as Graham's number - 64).

Video

Source: Graham's Number - Numberphile

See also

Sources

  1. Graham's Number
  2. Graham & Rothchild 1971 paper
  3. http://arxiv.org/abs/1304.6910
  4. http://arxiv.org/abs/1905.05617
  5. http://arxiv.org/abs/0811.1055
  6. Proof that G >> M. (This website uses n[m] = n inside an m-gon for Steinhaus-Moser Notation.)
  7. Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
  8. Proof that BB(64) >> G

External links