Wikia

Googology Wiki

Graham's number

Talk30
3,703pages on
this wiki
For other uses, see Graham's number (disambiguation).
Graham's number in arrow notation

A concise definition of Graham's number.

Graham's number is a famous large number, defined by Ronald Graham.[1]

Using up-arrow notation, it is defined as:

\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 celebrated as the largest number ever used in a 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.

History Edit

Wells

Martin Gardner's famous article introducing the number.

220px-GrahamCube.svg

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.

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*.

Graham published a paper 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". Graham's number appeared in an earlier unpublished paper, made famous when Martin Gardner wrote about it in Scientific American. In 2013, the upper bound was further reduced to N' = 2↑↑2↑↑2↑↑9 using the Hales–Jewett theorem.[3] As of 2014, the best known lower bound for N* is 13.

Gardner's article contained an error, where he claimed that 3↑↑7625597484987 = 3↑(7625597484987↑7625597484987); it is actually 3↑(3↑↑7625597484986).

Comparison Edit

Since g0 is 4 and not 3, Graham's number cannot be expressed efficiently with most major googological functions. It can be approximated with \(3 → 3 → 64 → 2\) in Conway's Chained Arrow Notation or \(\{ 3,65,1,2\}\) in BEAF, with upper bound \(\{3, 66, 1, 2\}\). A rare example of an exact representation is Jonathan Bowers' G functions, where it is.G644 in base 3.

Tim Chow proved that Graham's number is much larger than the Moser.[4] 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.[5] 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)\),[6] and later a better upper bound \(\Sigma(22)\) was proven.

Calculating last digits Edit

The final digits of Graham's number can be computed by taking advantage of the convergence of last digits, because Graham's number is a power tower of threes. Here is a simple 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\)

For example:

  • \(N(1) = 3^{N(0)} \equiv 3^3 \equiv 27 \equiv 7 \pmod{10}\), so the last digit is 7.
  • \(N(2) = 3^{N(1)} \equiv 3^7 \equiv 2187 \equiv 87 \pmod{100}\), so the last two digits are 87.
  • \(N(3) = 3^{N(2)} \equiv 3^{87} \equiv 323257909929174534292273980721360271853387 \equiv 387 \pmod{1000}\), so the last three digits are 387.
  • etc.

This naive method is not very efficient, since number of digits in the leftmost expression grows exponentially. We can use right-to left binary method instead:

  • Convert the exponent into binary form. E.g. \(87_{10} = 1010111_2\)
  • If last digit of exponent is 1, then multiply base to result and square base.
  • Otherwise, just square base.

Using this, it can be shown that last 20 digits of Graham's number are: \(...04575627262464195387\).[7]

Video Edit

Source: Graham's Number - Numberphile

Graham's Number - Numberphile09:16

Graham's Number - Numberphile


Sources Edit

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

See also Edit

Around Wikia's network

Random Wiki