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 dem 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 <math>2^n</math> Ecken (Knoten) je paarweise durch eine Linie (Kante) verbunden, so dass ein vollständiger Graph auf <math>2^n</math> Knoten mit <math>\tbinom{2^n}{2} = (2^{n-1})(2^n-1) </math> Kanten entsteht.

Diese Kanten werden nun mit jeweils einer von zwei Farben eingefärbt, das sind <math>2^{(2^{n-1})(2^n-1)}</math> verschiedene Kantenfärbungen. Die Frage ist dann, ob es für jede mögliche Kantenfärbung 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 ist dies nicht der Fall. Bei <math>n=2</math> besteht der Gesamtgraph nur aus einer Ebene mit vier Knoten. Färbt man dessen Kanten mit unterschiedlichen Farben, so besteht der einzige Teilgraph, nämlich der Gesamtgraph selbst, nicht aus sechs Kanten gleicher Farbe. Existiert andererseits eine Dimension <math>n_0</math>, in der für jede mögliche Kantenfärbung des Hyperwürfels ein einfarbiger ebener 4-Knoten-Teilgraph existiert, so gilt dies auch für jede höhere Dimension <math>n > n_0</math>, da der Hyperwürfel einer höheren Dimension einen Hyperwürfel der Dimension <math>n_0</math> als Teilgraphen enthält, in dem es stets einen Teilgraphen mit sechs gleichfarbigen Kanten gibt.

Daraus ergibt sich die eigentliche Problemstellung: Wie groß ist das <math>n_0</math>, mit dem für alle <math>n \ge n_0</math> für jede mögliche Kantenfärbung ein solcher Teilgraph existiert, während es für alle <math>n < n_0</math> eine Kantenfärbung gibt, mit der jeder ebene Teilgraph mit vier Knoten verschiedenfarbige Kanten hat?

Das Problem wurde noch nicht gelöst. Graham und Rothschild haben 1971 gezeigt, dass es einen solchen Wert <math>n_0</math> gibt, und dass <math>6 \le n_0 \le g_7</math> ist. Die Zahl <math>g_7</math> wird im nächsten Kapitel definiert. Der Mathematiker Geoffrey Exoo von der Indiana State University zeigte 2003, dass es noch in der Dimension <math>n=10</math> eine Kantenfärbung gibt, die keinen ebenen Teilgraph mit sechs gleichfarbigen Kanten zulässt. 2008 konnte die Untergrenze auf <math>n_0 \ge 13</math> verbessert werden,<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:Jerome Barkley|Jerome Barkley: }}{{#if:|{{#if:Improved lower bound on an Euclidean Ramsey problem|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Improved lower bound on an Euclidean Ramsey problem}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://arxiv.org/pdf/0811.1055%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Improved lower bound on an Euclidean Ramsey problem}}}}|[{{#invoke:URLutil|getNormalized|1=https://arxiv.org/pdf/0811.1055}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Improved lower bound on an Euclidean Ramsey problem}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}pdf-Datei| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://arxiv.org/pdf/0811.1055%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://arxiv.org/pdf/0811.1055}}%7C%7C URL ungültig}}}}{{#if:Improved lower bound on an Euclidean Ramsey problem|{{#if:{{#invoke:WLink|isValidLinktext|1=Improved lower bound on an Euclidean Ramsey problem|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:90540||(?)}}}}}}{{#if: 2024-06-27|;}}}}{{#if: 2024-06-27| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2024-06-27 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2024-06-27|class=Zitationswartung}} }} {{#invoke:DateTime|format|2024-06-27|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:de|de||{{#if:|1}}}}pdf-Datei|{{#if:{{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: pdf-Datei|{{#ifeq:{{#if:de|de|de}}|de||, }}pdf-Datei}})}}{{#if: {{#if: 2024-06-27 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}pdf-Datei|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://arxiv.org/pdf/0811.1055
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://arxiv.org/pdf/0811.1055
      | {{#if:{{#invoke:URLutil|isWebURL|https://arxiv.org/pdf/0811.1055}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://arxiv.org/pdf/0811.1055 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://arxiv.org/pdf/0811.1055
       | {{#if:{{#invoke:URLutil|isWebURL|https://arxiv.org/pdf/0811.1055}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://arxiv.org/pdf/0811.1055 }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://arxiv.org/pdf/0811.1055
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://arxiv.org/pdf/0811.1055
      | {{#if:{{#invoke:URLutil|isWebURL|https://arxiv.org/pdf/0811.1055}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://arxiv.org/pdf/0811.1055 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://arxiv.org/pdf/0811.1055
       | {{#if:{{#invoke:URLutil|isWebURL|https://arxiv.org/pdf/0811.1055}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://arxiv.org/pdf/0811.1055 }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> und 2014 die Obergrenze auf eine Zahl kleiner als <math> 2 \uparrow \uparrow \uparrow 6 = 2 \uparrow \uparrow 2 \uparrow \uparrow 2 \uparrow \uparrow 65536.</math><ref> {{#invoke:Vorlage:Literatur|f}} </ref>

Basierend auf unveröffentlichtem Material von Graham, aus dem sich ein Beweis der schwächeren (größeren) oberen Schranke <math>n_0 \le G_{64}</math> ergibt, bezeichnete Martin Gardner die Zahl <math>G_{64}</math> als „Grahams Zahl“.<ref>Martin Gardner: Mathematical Games in Scientific American, November 1977, S. 18–28. <templatestyles src="Webarchiv/styles.css" />{{#if:20131019135451

      | {{#ifeq: 20131019135451 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20131019135451}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20131019135451}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: online | {{#invoke:WLink|getEscapedTitle|online}} | {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20131019135451|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: online
    | {{#if: {{#invoke:WLink|isBracketedLink|online}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}</ref>

Definition

Grahams Zahl <math>G_{64}</math>, und auch die viel kleinere <math>g_7</math>, 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 <math>a,b\in\mathbb N</math> definiert man:

<math>

\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} </math>

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

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

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

<math>

G_0 \!\, = 4 </math>

<math>

\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} </math>

<math>

g_0 \!\, = 12 </math>

<math>

\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} </math>

<math>G_{64}</math> aus der ersten Folge ist Grahams Zahl, und <math>g_7</math> aus der zweiten ist die beste bis 2014 bekannte obere Schranke für <math>n_0</math>.

Anders ausgedrückt:

<math>

\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} </math>

Zur besseren Veranschaulichung, wie extrem groß Grahams Zahl ist, werden die ersten Schritte zur Berechnung von <math>G_1</math> gezeigt:

<math>

3\uparrow 3 = 3^3 = 27 </math>

<math>

3\uparrow \uparrow 3 = 3\uparrow (3\uparrow 3) = 3^{3^3} = 3^{27} = 7.625.597.484.987 </math>

<math>

\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} </math>

<math>

\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} </math>

Bereits <math>3\uparrow \uparrow \uparrow 3</math> lässt sich nicht mehr vernünftig in der üblichen Exponentialdarstellung (<math>r \cdot 10^z</math>) oder als Potenzturm ausdrücken. Dazu wäre bereits ein Potenzturm mit 7.625.597.484.986 Exponenten erforderlich.

Eigenschaften

Trotz ihrer unvorstellbaren Größe kann man die letzten Stellen von Grahams Zahl <math>G_{64}</math> mit elementarer Zahlentheorie bestimmen. Die letzten 500 Stellen von Grahams Zahl lauten:

02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560
43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509
27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
03222348723967018485186439059104575627262464195387

Man kann zeigen, dass Grahams Zahl in der verketteten Pfeilschreibweise zwischen

<math>3 \rightarrow 3 \rightarrow 64 \rightarrow 2</math>

und

<math> 3 \rightarrow 3 \rightarrow 65 \rightarrow 2 </math> liegt.

Weblinks

Einzelnachweise