Grahams Zahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Grahams Zahl (nach Ronald L. Graham) ist eine obere Grenze für ein Problem der Ramsey-Theorie.

[Bearbeiten] Grahams Problemstellung

In einem n-dimensionalen Hyperwürfel seien alle $2 n$ Ecken je paarweise durch eine Linie verbunden, so dass ein vollständiger Graph auf $2 n$ Knoten entsteht, der ${2^n\choose 2}$ Kanten besitzt.

Diese Kanten werden nun mit jeweils einer von zwei Farben eingefärbt. Es ergibt sich die Frage, wie groß n sein muss, damit es notwendigerweise immer mindestens einen gleichfarbigen vollständigen Untergraphen gibt, der aus 4 Knoten besteht, die in einer Ebene liegen. Anders ausgedrückt: Ab welcher Dimension tritt notgedrungen die genannte Form von Ordnung auf?

Das Problem wurde noch nicht gelöst. Graham und Rothschild haben 1971 gezeigt, dass n mindestens 6 ist; 2003 wies Exoo $n \geq 11$ nach. Grahams Zahl ist andererseits eine obere Grenze für dieses Problem, d. h. $n < G 64$ .

[Bearbeiten] Definition von Grahams Zahl

Grahams Zahl ist so groß, dass man Notationshilfsmittel wie Knuths Pfeil-Schreibweise benötigt, um eine sinnvolle Definition dieser Zahl hinzuschreiben. Knuths Pfeil-Schreibweise wird am besten anhand einiger Beispiele verdeutlicht. Für natürliche Zahlen $m,n\in\Bbb N$ führt man folgende „Hyperpotenz“-Operationen ein:

$\begin{matrix} m\hat{\ }n & = & \underbrace{m\cdot m\cdot m\cdot \ldots \cdot m\cdot m} \\ & & {n-\mathrm{mal}} \\ m\hat{\ }\hat{\ }n & = & \underbrace{m\hat{\ } m\hat{\ } m\hat{\ }\ldots\hat{\ } m\hat{\ } m} \\ & & {n-\mathrm{mal}} \\ m\hat{\ }\hat{\ }\hat{\ }n & = & \underbrace{m\hat{\ }\hat{\ } m\hat{\ }\hat{\ } m\hat{\ }\hat{\ }\ldots\hat{\ }\hat{\ } m\hat{\ }\hat{\ } m} \\ & & {n-\mathrm{mal}} \\ & & \vdots \end{matrix}$

In der ersten Zeile wird hierbei die übliche Potenz erklärt; ab der zweiten Zeile ist für das Verständnis zu beachten, dass der Potenzoperator $\hat{\ }$ nicht assoziativ ist. Der klammerfrei notierte Ausdruck $m\hat{\ } m\hat{\ } \ldots m\hat{\ } m$ ist deshalb mehrdeutig; in diesem Fall ist er - wie unter Mathematikern bei Weglassen der Klammern als Konvention üblich - von rechts nach links abzuarbeiten, d. h. beispielsweise ist $m\hat{\ }m\hat{\ }m = m\hat{\ }(m\hat{\ }m)$ zu lesen. Diese Abarbeitungsreihenfolge ist auch gerade diejenige, bei der die größten Endergebnisse hervorgebracht werden.

Ausgestattet mit dieser Notation (statt ^ wird oft auch das Symbol $\uparrow$ verwendet) kann man eine Folge bilden, die durch die folgenden Regeln rekursiv definiert ist:

G 0 = 4

$\begin{matrix} G_n & = & 3\ \underbrace{\hat{\ }\hat{\ }\hat{\ }\cdots\hat{\ }} \ 3\\ & & {G_{(n-1)}\mathrm{-mal}} \end{matrix}$

Grahams Zahl ist nun definiert als $G = G 64$ .

Zur besseren Veranschaulichung, wie extrem groß Grahams Zahl ist, werden hier die ersten Schritte zur Berechnung von $G_{1}=3\hat{\ }\hat{\ }\hat{\ }\hat{\ }3$ angegeben:

$3\hat{\ }3 = 3\cdot3\cdot3 = 27$

$3\hat{\ }\hat{\ }3 = 3\hat{\ }(3\hat{\ }3) = 3\hat{\ }27 = 7.625.597.484.987$

$\begin{matrix} 3\hat{\ }\hat{\ }\hat{\ }3 & = & 3\hat{\ }\hat{\ }(3\hat{\ }\hat{\ }3) & = & 3\hat{\ }\hat{\ }7.625.597.484.987 & = & \underbrace{3\hat{\ }(3\hat{\ }(3\hat{\ }\ldots\hat{\ }(3\hat{\ }3)\ldots)} \\ & & & & & & {7.625.597.484.987-\mathrm{mal}} \end{matrix}$

Bereits $G 1$ lässt sich nicht mehr vernünftig in der üblichen Exponentialdarstellung ausdrücken. Nichtsdestoweniger kann man die letzten Stellen von Grahams Zahl $G 64$ mit elementarer Zahlentheorie bestimmen. Die letzten 10 Stellen sind 2464195387.

Laut Guinness-Buch der Rekorde ist sie die größte jemals in einem mathematischen Beweis verwendete Zahl. Genauer müsste es „in einem sinnvollen mathematischen Beweis“ lauten, denn ansonsten könnte jemand den mathematischen Satz „Es gilt $G 65 > G 64$ “ formulieren und einen einfachen Beweis dafür liefern.