Graham's number

Graham's number (after Ronald L. Graham ) is a special natural number . It is an upper bound for a problem in Ramsey theory .

According to the Guinness World Records , it is the largest ever used in a mathematical proof number . In the meantime, however, some serious mathematical proofs used even larger numbers, for example in connection with Kruskal's tree theorem .

Graham's problem statement

In an n -dimensional hypercube (unit cube in n -dimensional Euclidean space ) all corners (nodes) are connected in pairs by a line (edge), so that a complete graph on nodes with edges is created. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle {\tbinom {2^{n}}{2}}=(2^{n-1})(2^{n}-1)}$

These edges are now colored with one of two colors, these are different edge colors . The question then is whether for every possible edge color there is a complete subgraph consisting of four nodes lying in a plane of Euclidean space, the six edges of which are all the same color. ${\displaystyle 2^{(2^{n-1})(2^{n}-1)}}$

This is not the case in low dimensions. With , the overall graph consists of only one level with four nodes. If you color its edges with different colors, the only subgraph, namely the overall graph itself, does not consist of six edges of the same color. On the other hand , if there is a dimension in which a single-colored, flat 4-node subgraph exists for every possible edge coloring of the hypercube, this also applies to every higher dimension , since the hypercube of a higher dimension contains a hypercube of the dimension as a subgraph in which it is always gives a subgraph with six edges of the same color. ${\displaystyle n=2}$ ${\displaystyle n_{0}}$ ${\displaystyle n>n_{0}}$ ${\displaystyle n_{0}}$

From this the real problem arises: How big is it , with which such a subgraph exists for every possible edge coloring, while there is an edge coloring for all , with which every plane subgraph with four nodes has different colored edges? ${\displaystyle n_{0}}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle n<n_{0}}$

The problem has not yet been resolved. Graham and Rothschild showed in 1971 that there is such a value , and that is. The number is defined in the next chapter. The mathematician Geoffrey Exoo from Indiana State University showed in 2003 that there is still an edge coloring in the dimension that does not allow a plane subgraph with six edges of the same color. In 2008 the lower limit could be improved to, and in 2014 the upper limit to a number less than ${\displaystyle n_{0}}$ ${\displaystyle 6\leq n_{0}\leq g_{7}}$ ${\displaystyle g_{7}}$ ${\displaystyle n=10}$ ${\displaystyle n_{0}\geq 13}$ ${\displaystyle 2\uparrow \uparrow \uparrow 6=2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 65536.}$

Based on unpublished material by Graham, which provides evidence of the weaker (larger) upper bound , Martin Gardner called the number "Graham's Number". ${\displaystyle n_{0}\leq G_{64}}$ ${\displaystyle G_{64}}$

definition

Graham's number , and the much smaller one , are so extremely large that even tools like the hyperpotency operator are not sufficient to express these numbers directly. The definition of the numbers is possible via a sequence, which can be represented, for example, with Knuth's arrow notation . For natural numbers one defines: ${\displaystyle G_{64}}$ ${\displaystyle g_{7}}$ ${\displaystyle a,b\in \mathbb {N} }$

${\displaystyle {\begin{matrix}a\uparrow b&:=&a^{b}&=&\underbrace {a\cdot a\cdot a\cdot \ldots \cdot a\cdot a} \\&&&&{b\;\mathrm {mal} }\\a\uparrow \uparrow b&:=&a\uparrow ^{2}b&:=&\underbrace {a\uparrow a\uparrow a\uparrow \ldots \uparrow a\uparrow a} \\&&&&{b\;\mathrm {mal} }\\a\uparrow \uparrow \uparrow b&:=&a\uparrow ^{3}b&:=&\underbrace {a\uparrow \uparrow a\uparrow \uparrow a\uparrow \uparrow \ldots \uparrow \uparrow a\uparrow \uparrow a} \\&&&&{b\;\mathrm {mal} }\\\vdots &&\vdots &&\vdots \\a\underbrace {\uparrow \uparrow \ldots \uparrow } b&:=&a\uparrow ^{n}b&:=&\underbrace {a\uparrow ^{n-1}a\uparrow ^{n-1}a\uparrow ^{n-1}\ldots \uparrow ^{n-1}a} \\{n\;\mathrm {mal} }&&&&{b\;\mathrm {mal} }\\\end{matrix}}}$

The usual power is explained in the first line . Note that the arrow operator is not associative . The expression notation in parentheses is - according to the convention - to be processed from right to left. So is . This order is also where the greatest end results are produced. ${\displaystyle \uparrow ^{n}}$ ${\displaystyle a\uparrow ^{n}a\uparrow ^{n}\ldots a\uparrow ^{n}a}$ ${\displaystyle a\uparrow ^{n}a\uparrow ^{n}a=a\uparrow ^{n}(a\uparrow ^{n}a)}$

You also define . Instead is also the ^ symbol used. ${\displaystyle a\uparrow ^{n}0:=1}$ ${\displaystyle \uparrow }$

With this notation can see the consequences and by the following rules recursively define: ${\displaystyle (G_{k})}$ ${\displaystyle (g_{k})}$

${\displaystyle G_{0}\!\,=4}$

${\displaystyle {\begin{matrix}G_{k}&=&3\ \underbrace {\uparrow \uparrow \uparrow \cdots \uparrow } \ 3&\;=\;3\uparrow ^{G_{k-1}}3\\&&{G_{k-1}\;\mathrm {mal} }&\end{matrix}}}$

${\displaystyle g_{0}\!\,=12}$

${\displaystyle {\begin{matrix}g_{k}&=&2\ \underbrace {\uparrow \uparrow \uparrow \cdots \uparrow } \ 3&\;=\;2\uparrow ^{g_{k-1}}3\\&&{g_{k-1}\;\mathrm {mal} }&\end{matrix}}}$

${\displaystyle G_{64}}$from the first episode is Graham's number, and from the second is the best upper bound known to 2014 for . ${\displaystyle g_{7}}$ ${\displaystyle n_{0}}$

Expressed differently:

${\displaystyle {\begin{matrix}G_{64}&=F^{64}(4)&\mathrm {mit} &F(n)=3\uparrow ^{n}3\\g_{7}&=f^{7}(12)&\mathrm {mit} &f(n)=2\uparrow ^{n}3\\\end{matrix}}}$

To better illustrate just how extremely large Graham's number is, the first steps in calculating : ${\displaystyle G_{1}}$

${\displaystyle 3\uparrow 3=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3\uparrow (3\uparrow 3)=3^{3^{3}}=3^{27}=7.625.597.484.987}$

${\displaystyle {\begin{matrix}3\uparrow \uparrow \uparrow 3&=&3\uparrow \uparrow (3\uparrow \uparrow 3)&=&3\uparrow \uparrow 7.625.597.484.987&=&\underbrace {3\uparrow (3\uparrow \ldots \uparrow (3\uparrow 3))} \\&&&&&&{7.625.597.484.987\;\mathrm {mal} }\end{matrix}}}$

${\displaystyle {\begin{matrix}G_{1}=3\uparrow \uparrow \uparrow \uparrow 3&=&3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)&=&\underbrace {3\uparrow \uparrow 3\uparrow \uparrow \ldots \uparrow \uparrow 3} \\&&&&{3\uparrow \uparrow \uparrow 3\;\mathrm {mal} }\end{matrix}}}$

Already it can no longer be reasonably expressed in the usual exponential representation ( ) or as a power tower . A power tower with 7,625,597,484,986 exponents would be required for this. ${\displaystyle 3\uparrow \uparrow \uparrow 3}$ ${\displaystyle r\cdot 10^{z}}$

properties

Despite its unimaginable size, the last digits of Graham's number can be determined using elementary number theory. The last 500 digits of Graham's number are: ${\displaystyle G_{64}}$

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

One can show that in the concatenated arrow notation, Graham's number lies between and . ${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2}$ ${\displaystyle 3\rightarrow 3\rightarrow 65\rightarrow 2}$

See also

• List of special numbers
• Arrow spelling

Web links

• Contribution to MathWorld
• Ronald Graham's homepage
• Graham's number on Susan Stepney's homepage
• A Ramsey Problem on Hypercubes by Geoff Exoo
• Article on waitbutwhy.com that tries to illustrate the unimaginable number of Graham's

Individual evidence

1. ↑ http://arxiv.org/abs/0811.1055
2. ↑ http://www.sciencedirect.com/science/article/pii/S0195669814000936
3. ^ Martin Gardner: Mathematical Games in Scientific American, November 1977, pp. 18-28. online ( Memento of the original from October 19, 2013 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice.