Graham-Zahl

Graham-Zahl

Grahams Zahl (nach Ronald L. Graham) ist eine spezielle, 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“.

Inhaltsverzeichnis

Grahams Problemstellung

In einem n-dimensionalen Hyperwürfel (Einheitswürfel im n-dimensionalen Euklidischen Raum) seien alle 2^n\!\, Ecken (Knoten) 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.

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_0\!\,, 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 \ge n_0, da der Hyperwürfel einer höheren Dimension einen Hyperwürfel der Dimension n_0\!\, als Teilgraph enthält, in dem der Teilgraph aus vier Knoten zu finden ist.

Daraus ergibt sich die eigentliche Problemstellung: wie groß ist das n_0\!\,, mit dem für alle n \ge n_0 für jede mögliche Kantenfärbung ein Teilgraph mit diesen Eigenschaften existiert, während es für alle n < n_0\!\, 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_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.

Definition

Grahams Zahl ist so extrem 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 (Gk) durch folgende Regeln rekursiv definieren:

G0 = 4

\begin{matrix}
G_k & = & 3 \ \underbrace{\uparrow \uparrow \uparrow \cdots\uparrow } \ 3\\
& & {G_{k-1} \; \mathrm{mal}} 
\end{matrix}

Grahams Zahl ist definiert als G64.

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


3\uparrow 3 = 3^3 = 27

3\uparrow \uparrow 3 = 3\uparrow (3\uparrow 3) = 3\uparrow 27 = 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.987 Exponenten erforderlich. Dennoch kann man die letzten Stellen von Grahams Zahl G64 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 G65 > G64“ formulieren und einen einfachen Beweis dafür liefern.

Siehe auch

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Graham Obree — Graeme Obree Graeme Obree (* 11. September 1965 in Nuneaton; auch Graham OBree) ist ein ehemaliger schottischer Radrennfahrer. Inhaltsverzeichnis 1 Rekordleistung …   Deutsch Wikipedia

  • Skewes' Zahl — Die Skewes Zahl (nach Stanley Skewes) ist eine obere Grenze für das Problem der überschätzten Primzahldichte. Ihr genauer Wert beträgt . Auch die Approximation ist gebräuchlich. Geschichte Das Problem der überschätzten Primzahldichte basiert auf… …   Deutsch Wikipedia

  • Ronald Graham — Ronald L. Graham (* 31. Oktober 1935 in Taft, Kalifornien) ist ein amerikanischer Mathematiker. Er leistete bahnbrechende Arbeiten auf dem Gebiet der diskreten Mathematik, insbesondere der Ramsey Theorie. Graham erlangte 1962 seinen Doctor of… …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

  • Sylvester Graham — Lithografie um 1865 Sylvester Graham (* 5. Juli 1794 in Suffield, Connecticut, USA; † 11. September 1851 in Northampton, Massachusetts) war ein amerikanischer Prediger und früher Verfechter einer vegetarischen Reformdiät in den …   Deutsch Wikipedia

  • Stirling-Zahl — Die Stirling Zahlen erster und zweiter Art, benannt nach James Stirling, werden in der Kombinatorik und der theoretischen Informatik verwendet. Inhaltsverzeichnis 1 Bezeichnung und Notation 2 Stirling Zahlen erster Art 2.1 Beispiel …   Deutsch Wikipedia

  • Robert Graham Wade — Robert Wade bei der Schachweltmeisterschaft der Senioren 1995 in Bad Liebenzell Robert Bob Graham Wade OBE (* 10. April 1921 in Dunedin, Neuseeland; † 29. November 2008 in London, Vereinigtes Königreich …   Deutsch Wikipedia

  • Kevin Graham Ogilvie — Skinny Puppy ist eine Post Industrial /Electronica Band, die 1982 in Vancouver, Kanada gegründet wurde. Inhaltsverzeichnis 1 Musikalische Einordnung 2 Geschichte 3 Diskographie 3.1 Studio Alben …   Deutsch Wikipedia

  • Gogoplex — Googol [ˈguːgɔl] ist eine Bezeichnung für die Zahl 10100. Das entspricht einer 1 mit 100 Nullen, ausgeschrieben: 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000… …   Deutsch Wikipedia

  • Googolplex — Googol [ˈguːgɔl] ist eine Bezeichnung für die Zahl 10100. Das entspricht einer 1 mit 100 Nullen, ausgeschrieben: 10.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000.000… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”