Die Zahl von Graham, genannt nach Ronald Graham, ist eine Vielzahl, die ein oberer ist, hat zur Lösung eines bestimmten Problems in der Theorie von Ramsey gebunden.

Die Zahl hat einen Grad der populären Aufmerksamkeit gewonnen, als Martin Gardner es in den "Mathematischen Spielen" Abteilung des Wissenschaftlichen Amerikaners im November 1977 beschrieben hat, schreibend, dass, "In einem unveröffentlichten Beweis hat Graham kürzlich... einen so riesengroßen bestimmten eingesetzt, dass es die Aufzeichnung für die größte in einem ernsten mathematischen Beweis jemals verwendete Zahl hält." Das 1980-Guinness-Buch von Weltaufzeichnungen hat den Anspruch von Gardner wiederholt, zum populären Interesse an dieser Zahl beitragend.

Die Zahl von Graham ist unvorstellbar größer als andere wohl bekannte große Anzahl wie ein googol, googolplex, und noch größer als die Zahl von Skewes und die Zahl von Moser. Tatsächlich ist das erkennbare Weltall zu klein, um eine gewöhnliche Digitaldarstellung der Zahl von Graham zu enthalten, annehmend, dass jede Ziffer mindestens ein Volumen von Planck besetzt. Sogar Macht-Türme der Form sind für diesen Zweck nutzlos, obwohl sie durch rekursive Formeln mit der-Pfeil-Notation von Knuth oder der Entsprechung leicht beschrieben werden kann, wie von Graham getan wurde. Die letzten zehn Ziffern der Zahl von Graham sind... 2464195387.

Spezifische ganze Zahlen, die bekannt sind, viel größer zu sein, als die Zahl von Graham, sind in vielen ernsten mathematischen Beweisen (z.B, im Zusammenhang mit den verschiedenen begrenzten Formen von Friedman des Lehrsatzes von Kruskal) seitdem erschienen.

Zusammenhang

Die Zahl von Graham wird mit dem folgenden Problem in der Theorie von Ramsey verbunden:

:Consider ein n-dimensional Hyperwürfel, und verbinden jedes Paar von Scheitelpunkten, um einen ganzen Graphen auf 2 Scheitelpunkten zu erhalten. Dann Farbe jeder der Ränder dieses Graphen entweder rot oder blau.

:What ist der kleinste Wert von n, für welchen jedes solches Färben mindestens einen einzeln-farbigen ganzen Subgraphen auf 4 coplanar Scheitelpunkten enthält?

1971 haben Graham und Rothschild bewiesen, dass dieses Problem eine Lösung, N * hat, und als bestimmter 6  N*  N, mit N eine Einzelheit, ausführlich definiert, sehr hohe Zahl gegeben hat: wo. Tiefer bestimmt 6 wurde später zu 11 von Geoff Exoo 2003, und zu 13 von Jerome Barkley 2008 verbessert. So sind die am besten bekannten Grenzen für N* 13  N*  N.

Die Zahl von Graham, G, ist viel größer als N: wo. Das schwächer ober gebunden für das Problem, das einer unveröffentlichten Arbeit von Graham zugeschrieben ist, wurde schließlich veröffentlicht und von Martin Gardner im Wissenschaftlichen Amerikaner im November 1977 genannt.

Definition der Zahl von Graham

Mit der-Pfeil-Notation von Knuth ist die Nummer G von Graham (wie definiert, im Artikel Scientific American von Gardner)

:

\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 \; \; \vdots \qquad \; \;} \\

& &3 \underbrace {\\uparrow \uparrow \cdots\cdot\cdot \uparrow} 3 \\

& &3 \uparrow \uparrow \uparrow \uparrow3

\end {Matrix}

\right \} \text {64 Schichten }\

</Mathematik>:

wo die Zahl von Pfeilen in jeder Schicht, an der Spitzenschicht anfangend, durch den Wert der folgenden Schicht darunter angegeben wird; das, ist

:

und wo ein Exponent auf einem-Pfeil anzeigt, wie viel Pfeile dort sind. Mit anderen Worten wird G in 64 Schritten berechnet: Der erste Schritt ist, g mit vier-Pfeilen zwischen 3s zu berechnen; der zweite Schritt ist, g mit g-Pfeilen zwischen 3's zu berechnen; der dritte Schritt ist, g mit g-Pfeilen zwischen 3's zu berechnen; und so weiter, bis zum Endrechnen G = g mit g-Pfeilen zwischen 3s.

Gleichwertig,

:

und der Exponent auf f zeigt eine Wiederholung der Funktion z.B an. Ausgedrückt in Bezug auf die Familie von Hyperoperationen ist die Funktion f die besondere Folge, die eine Version des schnell wachsenden die Funktion von Ackermann (n, n) ist. (Tatsächlich, für den ganzen n.) Kann die Funktion f auch in Conways geketteter Pfeil-Notation als ausgedrückt werden, und diese Notation stellt auch die folgenden Grenzen auf G zur Verfügung:

:

Umfang der Zahl von Graham

Um die Schwierigkeit zu befördern, die enorme Größe der Zahl von Graham zu schätzen, kann es nützlich sein — in Bezug auf den exponentiation allein — gerade der erste Begriff (g) von der schnell wachsenden 64-Begriffe-Folge auszudrücken. Erstens, in Bezug auf tetration allein:

:

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))

</Mathematik>

wo die Zahl 3s im Ausdruck rechts ist

:

Jetzt nimmt jeder tetration Operation zu einem "Turm" von exponentiations gemäß der Definition ab

:

So,

:

wird allein in Bezug auf den wiederholten "exponentiation Türme",

:

g_1 =

\left.

\begin {Matrix} 3^ {3^ {\\cdot^ {\\cdot^ {\\cdot^ {\\cdot^ {3}}}}} }\\Ende {Matrix-}\

\right \}

\left.

\begin {Matrix} 3^ {3^ {\\cdot^ {\\cdot^ {\\cdot^ {3}}}} }\\Ende {Matrix-}\

\right \}\

\dots

\left.

\begin {Matrix} 3^ {3^3 }\\Ende {Matrix-}\

\right \}\

3

\quad \text {wo die Zahl von Türmen} \quad ist

\left. \begin {Matrix} 3^ {3^ {\\cdot^ {\\cdot^ {\\cdot^ {3}}}} }\\Ende {Matrix-}\ \right \}\ \left. \begin {Matrix} 3^ {3^3 }\\Ende {Matrix-}\ \right \}\ 3</Mathematik>

und wo die Zahl 3s in jedem Turm, vom leftmost Turm anfangend, durch den Wert des folgenden Turms nach rechts angegeben wird.

Mit anderen Worten wird g durch das erste Rechnen der Zahl von Türmen, n = 333  geschätzt... 3 (wo die Zahl 3s 333 = 7625597484987 ist), und dann Computerwissenschaft des n Turms in der folgenden Folge:

1. Turm:

2. Turm: 333 (ist Zahl 3s), =

3. Turm: 3333 ... 3 (ist Zahl 3s), =...

.

. .

g = n Turm: 3333333 ... 3 (wird Zahl 3s durch gegeben)

wo die Zahl 3s in jedem aufeinander folgenden Turm durch den Turm kurz davor gegeben wird. Bemerken Sie, dass das Ergebnis, den dritten Turm zu berechnen, der Wert von n, die Zahl von Türmen für g ist.

Der Umfang dieses ersten Begriffes, g, ist so groß, dass es praktisch unverständlich ist, wenn auch die obengenannte Anzeige relativ leicht ist umzufassen. Sogar n, die bloße Zahl von Türmen in dieser Formel für g, ist viel größer als die Zahl von Volumina von Planck (ungefähr 10 von ihnen), in den sich vorstellen kann, das erkennbare Weltall zu unterteilen. Und nach diesem ersten Begriff noch bleiben weitere 63 Begriffe im schnellen Wachsen g Folge, bevor die Nummer G von Graham = g erreicht wird.

Niedrigstwertige dezimale Ziffern der Zahl von Graham

Die Zahl von Graham ist ein "Macht-Turm" der Form 3n (mit einem sehr großen Wert von n), so müssen seine niedrigstwertigen dezimalen Ziffern bestimmte für alle diese Türme übliche Eigenschaften befriedigen. Einer dieser Eigenschaften ist, dass alle diese Türme der Höhe, die größer ist als d (sagen), dieselbe Folge von d niedrigstwertigen dezimalen Ziffern haben. Das ist ein spezieller Fall eines allgemeineren Eigentums: Die d niedrigstwertigen dezimalen Ziffern aller dieser Türme der Höhe, die größer ist als d+2, sind des höchsten "3" im Turm unabhängig; d. h. das höchste "3" kann zu jeder anderen natürlichen Zahl geändert werden, ohne die d niedrigstwertigen Ziffern zu betreffen.

Der folgende Tisch illustriert für einige Werte von d, wie das geschieht. Für eine gegebene Höhe des Turms und Zahl von Ziffern d kommt die volle Reihe von d-digit Zahlen (10 von ihnen) nicht vor; statt dessen wiederholt sich eine bestimmte kleinere Teilmenge von Werten in einem Zyklus. Die Länge des Zyklus und einige der Werte (in Parenthesen) wird in jeder Zelle dieses Tisches gezeigt:

Die besonderen niedrigstwertigen d Ziffern, die durch alle genug hohen Türme 3s schließlich geteilt werden, sind im kühnen Text und können gesehen werden sich entwickelnd, als die Turm-Höhe zunimmt. Für jede festgelegte Zahl von Ziffern d (Reihe im Tisch), die Zahl von Werten, die für 33 möglich sind... 3x mod 10, als x Reihen über alle natürlichen Zahlen, wird gesehen, fest abzunehmen, als die Höhe, bis zum schließlichen Reduzieren des "Möglichkeitssatzes" zu einer einzelnen Zahl zunimmt (gefärbt Zellen), wenn die Höhe d+2 überschreitet.

Ein einfacher Algorithmus, um diese Ziffern zu schätzen, kann wie folgt beschrieben werden: Lassen Sie x = 3, dann, wiederholen Sie d Zeiten, die Anweisung x = 3 mod 10. Abgesehen vom Auslassen jeder Führung 0s wird der Endwert, der x (als eine Basis zehn Ziffer) zugeteilt ist, dann aus den d niedrigstwertigen dezimalen Ziffern 3n, für den ganzen n> d zusammengesetzt. (Wenn der Endwert von x weniger hat als d Ziffern, dann muss die erforderliche Zahl, 0s zu führen, hinzugefügt werden.)

Lassen Sie k die Zahlreichkeit dieser stabilen Ziffern sein, die die Kongruenz-Beziehung G (mod 10)  [G] (mod 10) befriedigen.

k=t-1, wo G (t): =3t. Hieraus folgt dass.

Der Algorithmus erzeugt oben die folgenden 500 niedrigstwertigen dezimalen Ziffern der Zahl von Graham (oder von jedem Turm von mehr als 500 3s):

...02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387.

Siehe auch

• BAUM (3)
• Funktion von Ackermann

Referenzen

• Die ausführliche Formel für N erscheint auf p. 290. Das ist nicht die Zahl von "Graham" G veröffentlicht von Martin Gardner.
• Graham, R. L.; Rothschild, B.L. (1978). "Theorie von Ramsey", Studien in Combinatorics, Abwechselndem Dienst, G.-G. Hrsg., Mathematische Vereinigung Amerikas, 17:80-99. Auf p. 90, im Angeben "der besten verfügbaren Schätzung" für die Lösung, wird die ausführliche Formel für N vom 1971-Papier wiederholt.
• ; nachgedruckt (revidiert) in Gardner (2001), zitiert unten.
• Exoo bezieht sich auf oberen Graham & Rothschild hat N durch den Begriff "von Graham der der Zahl" gebunden. Das ist nicht die Zahl von "Graham" G veröffentlicht von Martin Gardner.

Links

• "Ein Problem von Ramsey auf Hyperwürfeln" durch Geoff Exoo
• Artikel Mathworld über die Zahl von Graham
• Wie man die Zahl von Graham berechnet
• Einige Ergebnisse von Ramsey für die N-Würfel-Vorveröffentlichung erwähnen die Zahl von Graham