Grahams Nummer – Wikipedia

Posted on by

Enorm große Zahl, die Lösung der oberen Schranke für ein Problem der Ramsey-Theorie

Dieser Artikel handelt von der großen Anzahl, die nach Ronald Graham benannt ist. Für die nach Benjamin Graham benannte Anlagedauer siehe Graham-Nummer.

Grahams Nummer ist eine immense Zahl, die als Obergrenze für die Antwort auf ein Problem im mathematischen Bereich der Ramsey-Theorie entstanden ist. Es ist nach dem Mathematiker Ronald Graham benannt, der die Zahl in Gesprächen mit dem populärwissenschaftlichen Schriftsteller Martin Gardner als vereinfachte Erklärung der Obergrenzen des Problems verwendete, an dem er arbeitete. Im Jahr 1977 beschrieb Gardner die Nummer in Wissenschaftlicher Amerikanerund stellt es der Öffentlichkeit vor. Zum Zeitpunkt seiner Einführung war es die größte spezifische positive ganze Zahl, die jemals in einem veröffentlichten mathematischen Beweis verwendet wurde. Die Nummer wurde 1980 beschrieben Guinness-Buch der Rekorde, was zu seinem populären Interesse beiträgt. Andere spezifische ganze Zahlen (wie TREE (3)), von denen bekannt ist, dass sie weit größer als Grahams Zahl sind, sind seitdem in vielen ernsthaften mathematischen Beweisen aufgetaucht, beispielsweise im Zusammenhang mit Harvey Friedmans verschiedenen endlichen Formen des Kruskal-Theorems. Darüber hinaus haben sich seitdem kleinere Obergrenzen des Ramsey-Theorie-Problems als gültig erwiesen, von dem Grahams Zahl abgeleitet wurde.

Grahams Zahl ist viel größer als viele andere große Zahlen wie Skewes ‘Zahl und Mosers Zahl, die beide viel größer sind als ein Googolplex. Wie bei diesen ist es so groß, dass das beobachtbare Universum viel zu klein ist, um eine gewöhnliche digitale Darstellung von Grahams Zahl zu enthalten, vorausgesetzt, dass jede Ziffer ein Planck-Volumen einnimmt, möglicherweise den kleinsten messbaren Raum. Aber selbst die Anzahl der Ziffern in dieser digitalen Darstellung von Grahams Zahl wäre selbst eine so große Zahl, dass ihre digitale Darstellung im beobachtbaren Universum nicht dargestellt werden kann. Auch die Anzahl der Ziffern von kann nicht einmal Das Anzahl – und so weiter, und zwar so oft, dass die Gesamtzahl der Planck-Volumina im beobachtbaren Universum weit überschritten wird. Somit kann Grahams Zahl nicht einmal durch Kraftmasten der Form ausgedrückt werden

einbc⋅⋅⋅{ displaystyle a ^ {b ^ {c ^ { cdot ^ { cdot ^ { cdot}}}}}

.

Grahams Zahl kann jedoch explizit durch berechenbare rekursive Formeln unter Verwendung von Knuths Aufwärtspfeil-Notation oder einer gleichwertigen angegeben werden, wie dies von Graham getan wurde. Da es eine rekursive Formel gibt, um sie zu definieren, ist sie viel kleiner als die typischen Zahlen für beschäftigte Biber. Obwohl zu groß, um vollständig berechnet zu werden, kann die Ziffernfolge von Grahams Zahl durch einfache Algorithmen explizit berechnet werden. Die letzten 12 Ziffern sind … 262464195387. Mit Knuths Aufwärtspfeil-Notation ist Grahams Nummer

G64{ displaystyle g_ {64}}

, wo

Gn={3↑↑↑↑3,n=13↑Gn– –13,n≥2,n∈N.{ displaystyle g_ {n} = left {{ begin {matrix} 3 uparrow uparrow uparrow uparrow 3, & n = 1 \ 3 uparrow ^ {g_ {n-1}} 3, & n geq 2, n in mathbb {N} end {matrix}} right.}

Kontext[edit]

Beispiel eines zweifarbigen dreidimensionalen Würfels, der einen einfarbigen koplanaren vollständigen Teilgraphen mit vier Scheitelpunkten enthält. Der Untergraph wird unter dem Würfel angezeigt. Beachten Sie, dass dieser Würfel keinen solchen Untergraphen enthalten würde, wenn beispielsweise die Unterkante im vorliegenden Untergraphen durch eine blaue Kante ersetzt würde – was durch ein Gegenbeispiel bewiesen wird N.*> 3.

Grahams Zahl hängt mit dem folgenden Problem in der Ramsey-Theorie zusammen:

Verbinden Sie jedes Paar geometrischer Eckpunkte eines n-dimensionaler Hyperwürfel, um ein vollständiges Diagramm auf 2 zu erhaltennEckpunkte. Färben Sie jeden Rand dieses Diagramms entweder rot oder blau. Was ist der kleinste Wert von n für welche jeder Eine solche Färbung enthält mindestens einen einfarbigen vollständigen Teilgraphen auf vier koplanaren Eckpunkten.

1971 bewiesen Graham und Rothschild das Graham-Rothschild-Theorem zur Ramsey-Theorie der Parameterwörter, von denen ein Sonderfall zeigt, dass dieses Problem eine Lösung hat N *. Sie haben den Wert von begrenzt N * um 6 ≤ N * ≤ N.mit N. eine große, aber explizit definierte Zahl

F.7((12)=F.((F.((F.((F.((F.((F.((F.((12))))))),{ displaystyle F ^ {7} (12) = F (F (F (F (F (F (F (12))))),}

wo

F.((n)=2↑n3{ displaystyle F (n) = 2 uparrow ^ {n} 3}

in Knuths Aufwärtspfeilnotation; Die Zahl liegt zwischen 4 → 2 → 8 → 2 und 2 → 3 → 9 → 2 in der Conway-Notation mit verketteten Pfeilen.[1] Dies wurde 2014 über Obergrenzen der Hales-Jewett-Zahl auf reduziert

N.‘=2↑↑2↑↑((3+2↑↑8),{ displaystyle N ‘= 2 uparrow uparrow 2 uparrow uparrow (3 + 2 uparrow uparrow 8),}

welches drei Tetrationen enthält.[2] Im Jahr 2019 wurde dies weiter verbessert auf:[3]

N.″=((2↑↑5138)⋅((((2↑↑5140)↑↑((2⋅2↑↑5137))≪2↑↑((2↑↑5138){ displaystyle 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)}

Die Untergrenze von 6 wurde später von Geoffrey Exoo im Jahr 2003 auf 11 verbessert.[4] und bis 13 von Jerome Barkley im Jahr 2008.[5] Somit sind die bekanntesten Grenzen für N * sind 13 ≤ N * ≤ N ”.

Grahams Nummer, Gist viel größer als N.::

f64((4){ displaystyle f ^ {64} (4)}

, wo

f((n)=3↑n3{ displaystyle f (n) = 3 uparrow ^ {n} 3}

. Diese schwächere Obergrenze für das Problem, die einem unveröffentlichten Werk von Graham zugeschrieben wird, wurde schließlich von Martin Gardner in veröffentlicht und benannt Wissenschaftlicher Amerikaner im November 1977.[6]

Veröffentlichung[edit]

Die Zahl erlangte eine gewisse Aufmerksamkeit in der Bevölkerung, als Martin Gardner sie in der “Mathematische Spiele” Abschnitt von Wissenschaftlicher Amerikaner im November 1977, als er schrieb, dass Graham kürzlich in einem unveröffentlichten Beweis festgestellt hatte, “Eine Grenze, die so groß ist, dass sie den Rekord für die größte Anzahl enthält, die jemals in einem ernsthaften mathematischen Beweis verwendet wurde.” Die 1980 Guinness-Buch der Rekorde wiederholte Gardners Behauptung und trug zum Interesse der Bevölkerung an dieser Zahl bei. Laut dem Physiker John Baez hat Graham im Gespräch mit Gardner die Menge erfunden, die jetzt als Grahams Nummer bekannt ist. Während Graham versuchte, ein Ergebnis in der Ramsey-Theorie zu erklären, das er mit seinem Mitarbeiter Bruce Lee Rothschild abgeleitet hatte, stellte Graham fest, dass diese Menge leichter zu erklären war als die tatsächliche Zahl, die im Beweis erscheint. Da die Zahl, die Graham Gardner beschrieben hat, größer ist als die Zahl in der Arbeit selbst, sind beide gültige Obergrenzen für die Lösung des von Graham und Rothschild untersuchten Problems.[7]

Definition[edit]

Mit Knuths Aufwärtspfeilnotation Grahams Nummer G (wie in Gardner’s definiert Wissenschaftlicher Amerikaner Artikel) ist

G=3↑↑⋯⋯⋯⋯⋯↑⏟33↑↑⋯⋯⋯⋯↑⏟3⋮⏟3↑↑⋯⋯↑⏟33↑↑↑↑3}}64 Schichten{ displaystyle 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 uparrow 3 end {matrix}} right } { text {64 Ebenen}}}

wo die Anzahl von Pfeile in jeder nachfolgenden Schicht wird durch den Wert der nächsten Schicht darunter angegeben; das ist,

G=G64,{ displaystyle G = g_ {64},}

wo

G1=3↑↑↑↑3,{ displaystyle g_ {1} = 3 uparrow uparrow uparrow uparrow 3,}

Gn=3↑Gn– –13,{ displaystyle g_ {n} = 3 uparrow ^ {g_ {n-1}} 3,}

und wo ein hochgestellter Pfeil auf einem Aufwärtspfeil angibt, wie viele Pfeile es gibt. Mit anderen Worten, G wird in 64 Schritten berechnet: Der erste Schritt ist die Berechnung G1 mit vier Aufwärtspfeilen zwischen 3s; Der zweite Schritt ist die Berechnung G2 mit G1 Aufwärtspfeile zwischen 3s; Der dritte Schritt ist die Berechnung G3 mit G2 Aufwärtspfeile zwischen 3s; und so weiter, bis schließlich berechnet G = G64 mit G63 Aufwärtspfeile zwischen 3s.

Gleichermaßen

G=f64((4), wo f((n)=3↑n3,{ displaystyle G = f ^ {64} (4), { text {where}} f (n) = 3 uparrow ^ {n} 3,}

und das hochgestellte auf f zeigt eine Iteration der Funktion an, z.

f4((n)=f((f((f((f((n)))){ displaystyle f ^ {4} (n) = f (f (f (f (n)))}

. Ausgedrückt in Bezug auf die Familie der Hyperoperationen

H.0,H.1,H.2,⋯{ displaystyle { text {H}} _ {0}, { text {H}} _ {1}, { text {H}} _ {2}, cdots}

, die Funktion f ist die bestimmte Reihenfolge

f((n)=H.n+2((3,3){ displaystyle f (n) = { text {H}} _ {n + 2} (3,3)}

Dies ist eine Version der schnell wachsenden Ackermann-Funktion EIN((n, n). (Eigentlich,

f((n)>EIN((n,n){ displaystyle f (n)> A (n, n)}

f((n)=3→3→n{ displaystyle f (n) = 3 rightarrow 3 rightarrow n}

, und diese Notation bietet auch die folgenden Grenzen G::

3→3→64→2<G<3→3→65→2.{ displaystyle 3 rightarrow 3 rightarrow 64 rightarrow 2

Größe[edit]

Um die Schwierigkeit zu vermitteln, die enorme Größe von Grahams Zahl einzuschätzen, kann es hilfreich sein, nur in Bezug auf die Potenzierung nur den ersten Ausdruck auszudrücken (G1) der schnell wachsenden 64-Term-Sequenz. Erstens in Bezug auf die Tetration (

↑↑{ displaystyle uparrow uparrow}

) allein:

G1=3↑↑↑↑3=3↑↑↑((3↑↑↑3)=3↑↑((3↑↑((3↑↑ … ((3↑↑3)…)){ displaystyle 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))}

Dabei ist die Anzahl der 3s im Ausdruck rechts

3↑↑↑3=3↑↑((3↑↑3).{ displaystyle 3 uparrow uparrow uparrow 3 = 3 uparrow uparrow (3 uparrow uparrow 3).}

Nun jede Tetration (

↑↑{ displaystyle uparrow uparrow}

) Betrieb reduziert sich auf einen Power Tower (

↑{ displaystyle uparrow}

) gemäß der Definition

3↑↑X.=3↑((3↑((3↑…((3↑3)…))=33⋅⋅⋅3{ displaystyle 3 uparrow uparrow X = 3 uparrow (3 uparrow (3 uparrow dots (3 uparrow 3) dots)) = 3 ^ {3 ^ { cdot ^ { cdot ^ { cdot ^ {3}}}}}}

wo sind sie X. 3s.

So,

G1=3↑↑((3↑↑((3↑↑ … ((3↑↑3)…))wo die Anzahl der 3s ist3↑↑((3↑↑3){ displaystyle g_ {1} = 3 uparrow uparrow (3 uparrow uparrow (3 uparrow uparrow dots (3 uparrow uparrow 3) dots)) quad { text {wobei die Zahl von 3s ist}} quad 3 uparrow uparrow (3 uparrow uparrow 3)}

wird, nur in Bezug auf wiederholt “Potenzierungstürme”,

G1=33⋅⋅⋅⋅3}}33⋅⋅⋅3}}…333}}3wo die Anzahl der Türme ist33⋅⋅⋅3}}333}}3{ displaystyle g_ {1} = 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 quad { text {wobei die Anzahl der Türme}} quad left ist. { begin {matrix} 3 ^ {3 ^ { cdot ^ { cdot ^ { cdot ^ {3}}}} end {matrix}} right } left. { begin {matrix} 3 ^ {3 ^ {3}} end {matrix}} right } 3}

und wo die Anzahl von 3s in jedem Turm, beginnend vom Turm ganz links, durch den Wert des nächsten Turms rechts angegeben wird.

Mit anderen Worten, G1 wird berechnet, indem zuerst die Anzahl der Türme berechnet wird,

n=3↑3↑3 … ↑3{ displaystyle n = 3 uparrow 3 uparrow 3 dots uparrow 3}

(wo die Anzahl der 3s ist

3↑3↑3=7625597484987{ displaystyle 3 uparrow 3 uparrow 3 = 7625597484987}

) und berechnen dann die nth Turm in der folgenden Reihenfolge: 

      1st tower:  3
     
      2nd tower:  3↑3↑3 (number of 3s is 3) = 7625597484987
     
      3rd tower:  3↑3↑3↑3↑...↑3 (number of 3s is 7625597484987) = …
     
      ⋮
     
 g1 = nth tower:  3↑3↑3↑3↑3↑3↑3↑...↑3 (number of 3s is given by the n-1th tower)

wobei die Anzahl von 3s in jedem aufeinanderfolgenden Turm durch den Turm unmittelbar davor angegeben wird. Beachten Sie, dass das Ergebnis der Berechnung des dritten Turms der Wert von ist n, die Anzahl der Türme für G1.

Die Größe dieses ersten Terms, G1ist so groß, dass es praktisch unverständlich ist, obwohl die obige Anzeige relativ leicht zu verstehen ist. Sogar n, das bloße Anzahl der Türme in dieser Formel für G1ist weitaus größer als die Anzahl der Planck-Bände (ungefähr 10)185 von ihnen), in die man sich vorstellen kann, das beobachtbare Universum zu unterteilen. Und nach dieser ersten Amtszeit bleiben noch 63 Amtszeiten in der schnell wachsenden G Sequenz vor Grahams Nummer G = G64 ist erreicht. Um zu veranschaulichen, wie schnell diese Sequenz wächst, während G1 entspricht

3↑↑↑↑3{ displaystyle 3 uparrow uparrow uparrow uparrow 3}

mit nur vier Aufwärtspfeilen die Anzahl der Aufwärtspfeile in G2 ist diese unverständlich große Zahl G1.

Dezimalstellen ganz rechts[edit]

Grahams Nummer ist a “Kraftturm” der Form 3 ↑↑n (mit einem sehr großen Wert von n), daher müssen die Dezimalstellen ganz rechts bestimmte Eigenschaften erfüllen, die allen solchen Türmen gemeinsam sind. Eine dieser Eigenschaften ist die Alle diese Türme mit einer Höhe größer als d (sagen wir) haben die gleiche Folge von d Dezimalstellen ganz rechts. Dies ist ein Sonderfall einer allgemeineren Eigenschaft: Die d Dezimalstellen ganz rechts aller dieser Türme mit einer Höhe von mehr als d+2, sind unabhängig der obersten “3” im Turm; dh das oberste “3” kann in eine andere nicht negative Ganzzahl geändert werden, ohne die d Ziffern ganz rechts.

Die folgende Tabelle zeigt einige Werte von d, wie das passiert. Für eine bestimmte Turmhöhe und Anzahl der Ziffern d, die gesamte Palette von d-stellige Zahlen (10d von ihnen) tut nicht auftreten; Stattdessen wiederholt sich eine bestimmte kleinere Teilmenge von Werten in einem Zyklus. Die Länge des Zyklus und einige der Werte (in Klammern) werden in jeder Zelle dieser Tabelle angezeigt:

Anzahl der verschiedenen möglichen Werte von 3 ↑ 3 ↑… 3 ↑x wenn alle außer ganz rechts d Dezimalstellen werden ignoriert
Anzahl an Ziffern (d) 3 ↑x 3 ↑ 3 ↑x 3 ↑ 3 ↑ 3 ↑x 3 ↑ 3 ↑ 3 ↑ 3 ↑x 3 ↑ 3 ↑ 3 ↑ 3 ↑ 3 ↑x
1 4
(1,3,9,7)		 2
(3,7)		 1
((7)		 1
((7)		 1
((7)
2 20
(01,03,…,87,…, 67)		 4
(03,27,83,87)		 2
(27,87)		 1
((87)		 1
((87)
3 100
(001.003,…,387,…, 667)		 20
(003,027,…387,…, 587)		 4
(027,987,227,387)		 2
(987,387)		 1
((387)

Das besondere ganz rechts d Ziffern, die letztendlich von allen ausreichend hohen Türmen von 3 geteilt werden, sind fett gedruckt und können mit zunehmender Turmhöhe entwickelt werden. Für eine beliebige feste Anzahl von Ziffern d (Zeile in der Tabelle), die Anzahl der möglichen Werte für 3

↑{ displaystyle scriptstyle uparrow}

3 ↑… 3 ↑x mod 10d, wie x Bereiche über alle nichtnegativen ganzen Zahlen hinweg nehmen mit zunehmender Höhe stetig ab, bis sie schließlich abnehmen “Möglichkeit eingestellt” zu einer einzelnen Zahl (farbige Zellen), wenn die Höhe überschreitet d+2.

Ein einfacher Algorithmus[8] zur Berechnung dieser Ziffern kann wie folgt beschrieben werden: sei x = 3, dann iteriere, d mal die Zuordnung x = 3x mod 10d. Mit Ausnahme des Weglassens führender Nullen wird der endgültige Wert zugewiesen x (als Basis-Zehn-Zahl) setzt sich dann aus dem d Dezimalstellen ganz rechts von 3 ↑↑n, für alle n > d. (Wenn der Endwert von x hat weniger als d Ziffern, dann muss die erforderliche Anzahl führender Nullen hinzugefügt werden.)

Lassen k sei die Zahl dieser stabil Ziffern, die die Kongruenzrelation G erfüllen (mod 10k) ≡[GG](Mod 10k).

k=t-1, wobei G (t): = 3 ↑↑t.[9] Es folgt dem, G63 ≪ k ≪ g64.

Der obige Algorithmus erzeugt die folgenden 500 Dezimalstellen ganz rechts von Grahams Zahl (OEIS: A133613): 

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

Verweise[edit]

Literaturverzeichnis[edit]

  • Gardner, Martin (November 1977). “Mathematische Spiele” (PDF). Wissenschaftlicher Amerikaner. 237 (5): 18–28. Bibcode:1977SciAm.237e..18G. doi:10.1038 / Scientificamerican1177-18.;; Nachdruck (überarbeitet) in Gardner (2001), unten zitiert.
  • Gardner, Martin (1989). Penrose Fliesen zu Falltür-Chiffren. Washington, DC: Mathematische Vereinigung von Amerika. ISBN 978-0-88385-521-8.
  • Gardner, Martin (2001). Das kolossale Buch der Mathematik: Klassische Rätsel, Paradoxien und Probleme. New York, NY: Norton. ISBN 978-0-393-02023-6.
  • Graham, RL; Rothschild, BL (1971). “Ramseys Satz für n-Parametersätze” (PDF). Transaktionen der American Mathematical Society. 159: 257–292. doi:10.2307 / 1996010. JSTOR 1996010. Die explizite Formel für N. erscheint auf p. 290. Dies ist nicht die “Grahams Nummer” G herausgegeben von Martin Gardner.
  • Graham, RL; Rothschild, BL (1978). “Ramsey-Theorie”. In Rota, GC (Hrsg.). Studium der Kombinatorik (MAA Studium der Mathematik). 17. Mathematische Vereinigung von Amerika. S. 80–99. ISBN 978-0-88385-117-3. Auf P. 90, in der Angabe “die beste verfügbare Schätzung” für die Lösung die explizite Formel für N. wird aus dem Papier von 1971 wiederholt.

Externe Links[edit]