Grahams Zahl

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

Laut Guinness-Buch der Rekorde ist sie die größte jemals in einem mathematischen Beweis verwendete Zahl. In der Zwischenzeit kamen aber in einigen ernsthaften mathematischen Beweisen noch wesentlich größere Zahlen vor, zum Beispiel im Zusammenhang mit Kruskals Baum-Theorem.

Grahams Problemstellung

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

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.

In niedrigen Dimensionen gibt es Kantenfärbungen, wo dies nicht gilt. Bei n = 2 besteht der Gesamtgraph nur aus einer Ebene mit vier Knoten. Färbt man diesen mit unterschiedlichen Farben, so besteht der einzige Teilgraph, nämlich der Gesamtgraph selbst, nicht aus sechs Kanten gleicher Farbe. Existiert andererseits eine Dimension n₀, in der für jede mögliche Kantenfärbung des Hyperwürfels ein Teilgraph mit diesen Eigenschaften existiert, so gilt dies auch für jede höhere Dimension n > n₀, da der Hyperwürfel einer höheren Dimension einen Hyperwürfel der Dimension n₀ als Teilgraphen enthält, in dem der Teilgraph mit sechs gleichfarbigen Kanten zu finden ist.

Daraus ergibt sich die eigentliche Problemstellung: wie groß ist das n₀, mit dem für alle $n \ge n_0$ für jede mögliche Kantenfärbung ein solcher Teilgraph existiert, während es für alle n < n₀ eine Kantenfärbung gibt, die dies verhindert?

Das Problem wurde noch nicht gelöst. Graham und Rothschild haben 1971 gezeigt, dass es einen solchen Wert n₀ gibt, und dass $6 \le n_0 \le g_7$ ist. Die Zahl g₇ wird im nächsten Kapitel definiert. Der Mathematiker Geoffrey Exoo von der Indiana State University zeigte 2003, dass es noch in der Dimension n = 10 eine Kantenfärbung gibt, die keinen ebenen Teilgraph mit sechs gleichfarbigen Kanten zulässt. Die beste bekannte Abschätzung ist damit $11 \le n_0 \le g_7$.

Basierend auf unveröffentlichtem Material von Graham, aus dem sich ein Beweis der schwächeren (größeren) oberen Schranke $n_0 \le G_{64}$ ergibt, bezeichnete Martin Gardner in [Scientific American, "Mathematical Games", November 1977] die Zahl G₆₄ als „Grahams Zahl“.

Definition

Grahams Zahl G₆₄, und auch die viel kleinere g₇, sind so extrem groß, dass nicht einmal Hilfsmittel wie der Hyperpotenz-Operator ausreichen, um diese Zahlen direkt anzugeben. Die Definition der Zahlen ist aber über eine Folge möglich, die zum Beispiel mit Knuths Pfeilschreibweise dargestellt werden kann. Für natürliche Zahlen $a,b\in\Bbb N$ definiert man:

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

In der ersten Zeile wird hierbei die übliche Potenz erklärt. Beachte, dass der Pfeiloperator $\uparrow^n$ nicht assoziativ ist. Der klammerfrei notierte Ausdruck $a \uparrow^n a \uparrow^n \ldots a \uparrow^n a$ ist – so die Konvention – von rechts nach links abzuarbeiten. Somit ist $a \uparrow^n a \uparrow^n a = a \uparrow^n (a \uparrow^n a)$. Diese Reihenfolge ist auch die, bei der die größten Endergebnisse hervorgebracht werden.

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

Mit dieser Notation kann man die Folgen (G_k) und (g_k) durch folgende Regeln rekursiv definieren:

$G_0 \!\, = 4$

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

$g_0 \!\, = 12$

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

G₆₄ aus der ersten Folge ist Grahams Zahl, und g₇ aus der zweiten ist die beste bekannte obere Schranke für n₀.

Anders ausgedrückt:

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

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

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

$3\uparrow \uparrow 3 = 3\uparrow (3\uparrow 3) = 3^{3^3} = 3^{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$) oder als Potenzturm ausdrücken. Dazu wäre bereits ein Potenzturm mit 7.625.597.484.986 Exponenten erforderlich. Dennoch kann man die letzten Stellen von Grahams Zahl G₆₄ mit elementarer Zahlentheorie bestimmen. Die letzten 10 Stellen sind 2464195387.

Siehe auch

• Liste besonderer Zahlen

Weblinks

• Beitrag bei MathWorld
• Ronald Grahams Homepage
• Grahams Zahl auf Susan Stepneys Homepage
• A Ramsey Problem on Hypercubes von Geoff Exoo