Grahams Zahl

aus Wikipedia, der freien Enzyklopädie

Grahams Zahl (nach Ronald L. Graham) ist eine spezielle, schier unvorstellbar große natürliche Zahl. Sie ist eine obere Grenze für ein Problem der Ramsey-Theorie und gilt als „die größte Zahl, die je in einem mathematischen Beweis verwendet wurde“.

[Bearbeiten] Grahams Problemstellung

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

Diese Kanten werden nun mit jeweils einer von zwei Farben eingefärbt. Die Frage ist dann, ob es einen vollständigen Teilgraphen aus vier in einer Ebene des Euklidischen Raums liegenden Knoten gibt, dessen sechs Kanten alle die gleiche Farbe haben.

Daraus ergibt sich die eigentliche Problemstellung: wie groß muss $n$ mindestens sein, damit für jede mögliche Kantenfärbung ein Teilgraph mit diesen Eigenschaften existiert? Anders ausgedrückt: man sucht $n 0$ , so dass für alle $n \ge n_0$ immer ein solcher Teilgraph gefunden werden kann, während es für alle $n < n 0$ eine Kantenfärbung gibt, die dies verhindert. Ab der Dimension $n 0$ tritt also zwangsläufig diese Form von Ordnung auf.

Das Problem wurde noch nicht gelöst. Graham und Rothschild haben 1971 gezeigt, dass es einen solchen Wert $n 0$ gibt, und dass $6 \le n_0 \le G_{64}$ ist. $G 64$ wird Grahams Zahl genannt, und ist nachfolgend definiert.

Der Mathematiker Geoffrey Exoo von der Indiana State University verbesserte 2003 die untere Schranke auf $n_0 \ge 11$ .

[Bearbeiten] Definition

Grahams Zahl ist so groß, dass nicht einmal Hilfsmittel wie der Hyperpotenz-Operator ausreichen, um die Definition dieser Zahl sinnvoll niederzuschreiben. Dieser Operator kann z. B. mit Knuths Pfeil-Schreibweise dargestellt werden. Für natürliche Zahlen $m,n\in\Bbb N$ definiert man:

$\begin{matrix} m\uparrow n & := & \underbrace{m\cdot m\cdot m\cdot \ldots \cdot m\cdot m} & = & m^n \\ & & {n\;\mathrm{mal}} \\ m\uparrow \uparrow n & := & \underbrace{m\uparrow m\uparrow m\uparrow \ldots\uparrow m\uparrow m} \\ & & {n\;\mathrm{mal}} \\ m\uparrow \uparrow \uparrow n & := & \underbrace{m\uparrow \uparrow m\uparrow \uparrow m\uparrow \uparrow \ldots\uparrow \uparrow m\uparrow \uparrow m} \\ & & {n\;\mathrm{mal}} \\ & & \vdots \end{matrix}$

Außerdem definiert man $m \uparrow \uparrow \ldots \uparrow 0 := 1$ . Statt $\uparrow$ wird oft auch das Symbol ^ verwendet.

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 $\uparrow$ nicht assoziativ ist. Der klammerfrei notierte Ausdruck $m\uparrow m\uparrow \ldots m\uparrow m$ ist deshalb mehrdeutig; in diesem Fall ist er - wie unter Mathematikern als Konvention üblich - von rechts nach links abzuarbeiten. Beispielsweise ist $m\uparrow m\uparrow m = m\uparrow (m\uparrow m)$ . Diese Reihenfolge ist auch gerade diejenige, bei der die größten Endergebnisse hervorgebracht werden.

Mit dieser Notation kann man die Folge $(G i)$ durch folgende Regeln rekursiv definieren:

G 0 = 4

$\begin{matrix} G_n & = & 3 \ \underbrace{\uparrow \uparrow \uparrow \cdots\uparrow } \ 3\\ & & {G_{n-1} \; \mathrm{mal}} \end{matrix}$

Grahams Zahl ist damit definiert als $G 64$ .

Zur besseren Veranschaulichung, wie extrem groß Grahams Zahl ist, werden die ersten Schritte zur Berechnung von $G 1$ gezeigt:

$3\uparrow 3 = 3^3 = 27$

$3\uparrow \uparrow 3 = 3\uparrow (3\uparrow 3) = 3\uparrow 27 = 7.625.597.484.987$

$\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}$

$\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}$

Bereits $3\uparrow \uparrow \uparrow 3$ lässt sich nicht mehr vernünftig in der üblichen Exponentialdarstellung ( $r \cdot 10^z$ ) ausdrücken, und $G 1$ noch weniger. Dennoch 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.