Grahamovo číslo

Grahamovo číslo, pojmenované po Ronaldu Grahamovi, je velké číslo, které je horní hranicí řešení určitého problému v Ramseyově větě.

Číslo získalo velkou popularitu, když ho Martin Gardner popsal v sekci „Mathematical Games“ magazínu Scientific American v listopadu 1977: „V nepublikovaném důkazu Graham nedávno ustanovil… hranici tak rozsáhlou, že drží rekord za největší číslo, které bylo kdy použito v matematickém důkazu.“ Guinnessova kniha rekordů z roku 1980 zopakovala Gardenerovo prohlášení, což přidalo na popularitě tohoto čísla.

Grahamovo číslo je nepředstavitelně větší než ostatní známá velká čísla jako Googol, googolplex, a dokonce větší než Skewesovo číslo a Moserovo číslo. Ve skutečnosti je pozorovatelný vesmír příliš malý, aby obsahoval běžnou dekadickou digitální reprezentaci Grahamova čísla za předpokladu, že každá číslice okupuje alespoň jednu Planckovu délku krychlovou. Dokonce umocňování ve formě $\scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ je nepoužitelné pro tento záměr. Pro definici Grahamova čísla je nutno použít rekurzivní Knuthův zápis.

Posledních deset číslic Grahamova čísla je …2464195387.

Specifická celá čísla považovaná za daleko větší než Grahamovo číslo se od té doby objevila v množství seriózních matematických důkazů (např. ve spojitosti s Friedmanovými různými konečnými formami Kruskalova algoritmu).

Souvislost s Ramseyovou teorií

Příklad dvoubarevné 3rozměrné kostky obsahující jeden jednobarevný 4vrcholový koplanární soubor podgrafu. Tento podgraf je zobrazen pod kostkou. Tato kostka by ale neobsahovala žádný podgraf, pokud by například spodní hrana v tomto podgrafu byla vyměněna za modrou hranu – což by prokázalo, že N* > 3.

Grahamovo číslo je spojeno s tímto problémem v Ramseyově větě: vezměte v úvahu n-dimenzionální nadkrychli a spojte každý pár vrcholů, abyste získali kompletní graf 2ⁿ vrcholů. Pak vybarvěte každou z hran tohoto grafu buď modře, nebo červeně. Jaká je nejmenší hodnota n, pro kterou každé takové vybarvení obsahuje alespoň 1 jednobarevný kompletní podgraf 4 koplanárních vrcholů?

V roce 1971 Graham a Rothschild dokázali, že tento problém má řešení, N*, a dali mu ohraničení 6 ≤ N* ≤ N, kde N je definováno výlučně jako velmi velké číslo. Spodní hranice 6 byla později zdokonalena na 11 Geoffem Exooem v roce 2003 a na 13 Jeromem Barkleym v roce 2008. Nejznámější hranice pro N* jsou tedy 13 ≤ N* ≤ N.

Grahamovo číslo je mnohem větší než N. Tato horní hranice byla nakonec publikována a pojmenována Martinem Gardnerem v Scientific American v listopadu 1977.

Vysvětlení velikosti Grahamova čísla

Pro definici Grahamova čísla je nutno použít Knuthův zápis. Nejprve definujeme g₁ jako 3 ↑↑↑↑ 3 = 3 ↑⁴ 3. Dále definujeme

g_n = 3 ↑^g_(n–1) 3

Tedy:

g₂ = 3 ↑^g₁ 3 = 3 ↑^{3↑↑↑↑3} 3

g₃ = 3 ↑^g₂ 3

…

g₆₄ = 3 ↑^g₆₃ 3 = Grahamovo číslo

Již g₁ je větší než jakékoliv číslo rozumně zapsatelné ve formě mocninové věže $\scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$. Vzhledem k tomu, že g_n se v iteraci g_n+1 používá jako počet šipek, roste funkce g_x nepředstavitelně rychle.

Teoretický výpočet Grahamova čísla v programovacím jazyce JavaScript

// non-negative integers only
function Knuth(left, arrowCount, right) {
    if (arrowCount <= 0)
        return left * right;
    if (right <= 0)
        return 1;
    arrowCount--;
    right--;
    var result = left;
    for (var i = 0; i < right; i++)
        result = Knuth(left, arrowCount, result);
    return result;
}
function G(value) {
    var result = 4;
    for (var i = 0; i < value; i++)
        result = Knuth(3, result, 3);
    return result;
}
function GetGrahamsNumber() {
    return G(64);
}

Reference

V tomto článku byl použit překlad textu z článku Grahamovo číslo na slovenské Wikipedii.