Grahamovo číslo

Grahamovo číslo, pomenované po Ronaldovi Grahamovi, je veľké číslo, ktoré je hornou hranicou riešenia určitého problému v Ramseyovej teoréme.

Číslo získalo veľkú popularitu keď ho Martin Gardner opísal v sekcii "Mathematical Games" magazínu Scientific American v novembri 1977, opisujúc, "V nepublikovanom dôkaze, Graham nedávno ustanovil ... hranicu tak rozsiahlu, že drží rekord za najväčšie číslo, ktoré bolo kedy použité v matematickom dôkaze." V Guinnessovej knihe rekordov z roku 1980 zopakovala Gardenerovo vyhlásenie, čo pridalo na popularite tohto čísla.

Grahamovo číslo je nepredstaviteľne väčšie ako ostatné známe veľké čísla ako Googol, Googolplex, a dokonca väčšie ako Skewesovo číslo a Moserovo číslo. V skutočnosti, pozorovateľný vesmír je príliš malý aby obsahoval bežnú digitálnu reprezentáciu Grahamovho čísla, v predpoklade, že každé číslo okupuje aspoň jednu planckovu jednotku. Dokonca umocňovanie vo forme $\scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ sú nepoužiteľné pre tento zámer, aj keď Grahamovo číslo môže byť ľahko popísané pomocou rekurzívnych vzorcov, ktoré využívajú Knuthov zápis. Posledných 10 číslic Grahamovho čísla sú ...2464195387.

Špecifické celé čísla považované za ďaleko väčšie ako Grahamovo číslo sa odvtedy objavili v množstve serióznych matematických dôkazoch (napr. v spojitosti s Friedmanovými rôznymi konečnými formami Kruskalovho algoritmu).

Súvislosť s Ramseyovou teorémou

Príklad 2-farebnej 3-dimenzionálej kocky obsahujúcej jeden jednofarebný 4-vrcholový komplanárny súbor podgrafu. Tento podgraf je zobrazený pod kockou. Treba poznamenať, že táto kocka by neobsahovala žiaden podgraf, ak by napríklad spodná hrana v tomto podgrafe bola vymenená za modrú hranu - čo by bolo dokázané, že N* > 3.

Grahamovo číslo je spojené s týmto problémom v Ramseyovej teoréme: Zoberte do úvahy n-dimenzionálnu hyperkocku a spojte každý pár vrcholov, aby ste získali kompletný graf 2n vrcholov. Potom vyfarbite každú z hrán tohto grafu buď na modro, alebo červeno. Aká je najmenšia hodnota n pre ktorú každé takéto vyfarbenie obsahuje aspoň 1 jednofarebný kompletný podgraf 4 koplanárnych vrcholov?

V roku 1971, Graham a Rothschild dokázali, že tento problém má riešenie, N*, a dali mu ohraničenie 6 ≤ N* ≤ N, kde N je definované výlučne ako veľmi veľké číslo. Spodná hranica 6 bola neskôr zdokonalená na 11 Geoffom Exooom v roku 2003 a na 13 Jeromom Barkleyom v roku 2008. Teda, najznámejšie hranice pre N* sú 13 ≤ N* ≤ N.

Grahamovo číslo, G, je omnoho väčšie ako N. Táto horná hranica bola napokon publikovaná a pomenovaná po Martinovi Gardnerovi v Scientific American v novembri 1977.

Vysvetlenie veľkosti Grahamovho čísla

Grahamové číslo dostaneme umocňovaním čísla 3. Namiesto klasického umocňovania, je pri vysvetlení efektívnejšie použiť Knuthov zápis, kde sa namiesto formy $\scriptstyle {a^{b}}$ používa zápis a↑b

1. bod: 3
2. bod: 3↑3 = ($\scriptstyle {3^{3}}$) = 27
3. bod: 3↑↑3 = ($\scriptstyle {3^{3^{3}}}$) = 7 625 597 484 987
4. bod: 3↑↑↑3 = (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$); počet čísiel 3 v mocninovej veži je 7 625 597 484 987) = ...
5. bod: g₁ = 3↑↑↑↑3 = (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$)}($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$)}($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$)}...}($\scriptstyle {3^{3^{3}}}$)}3; počet mocninových veží 3 je výsledok štvrtého bodu = ...
6. bod: g₂ = 3↑↑↑...↑3 = (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$); počet operátorov (šípiek hore) je g₁)

.

.

.

68. bod: g₆₄ = 3↑↑↑...↑3 (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$); počet operátorov (šípiek hore) je g₆₃) = Grahamovo číslo

Ako teda dostaneme číslo G1 a Grahamovo číslo? Začneme mocninovými vežami sprava a postupujeme doľava:

1. veža : číslo 3.

2. veža : ($\scriptstyle {3^{3^{3}}}$) = 7 625 597 484 987

3. veža : (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$); počet čísiel 3 v mocninovej veži je 7 625 597 484 987) = ...

.

.

.

n-tá veža: počet čisel 3 v n-tej veži je daný n-1. vežou. toto opakujeme (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$)-krát, pričom počet čísiel 3 v mocninovej veži je 7 625 597 484 987) = ...

ak n = (($\scriptstyle {3^{3^{\cdot ^{\cdot }}}}$); počet čísiel 3 v mocninovej veži je 7 625 597 484 987) = ... dostali sme G1.

Následne postupujeme tak, že počet operátorov v G(k) je G(k-1).

Výpočtom G(64) dostávame Grahamove číslo.

Najkrajnešie miesta Grahamovho čísla

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387.