Getal van Graham

Het getal van Graham, genoemd naar de wiskundige Ronald Graham, is een onvoorstelbaar groot getal. Het wordt algemeen erkend als het grootste getal dat ooit in een serieus wiskundig bewijs is gebruikt, en is als zodanig opgenomen in het Guiness Book of Records.

Het getal van Graham is zo groot, dat zelfs gigantische getallen als googol of googolplex er volkomen bij in het niet vallen. Het getal van Graham is te groot om in de wetenschappelijke notatie te worden uitgedrukt, zelfs met meervoudig opeenvolgende exponenten. Het getal dient te worden weergegeven als een element van een rij getallen gedefinieerd met behulp van Knuths pijlomhoognotatie. Met behulp van elementaire getaltheorie is echter wel uit te rekenen hoe het eind van het getal er uit ziet. De laatste tien cijfers van het getal van Graham zijn ...2464195387 .

[bewerk] Grahams probleem

Het getal van Graham is de bovenlimiet van de oplossing van een vraagstuk uit de tak van wiskunde die bekend staat als de Ramsey-theorie. De probleemstelling is als volgt:

Stel je een n-dimensionale hyperkubus voor, en verbind elk paar knooppunten met elkaar zodat een complete graaf op 2ⁿ knooppunten ontstaat. Beschilder vervolgens elk hoekpunt in 1 van 2 kleuren. Wat is de kleinste waarde van n waarvoor elk van de mogelijke beschilderingen tenminste 1 complete subgraaf bevat met 4 knooppunten van dezelfde kleur in een plat vlak?

Een oplossing voor dit vraagstuk is anno 2006 nog niet bekend. In 1971 bewezen Graham en Rotschild dat n ≥ 6 moet zijn. Er kan bewezen worden dat het getal van Graham de theoretische bovengrens is van dit vraagstuk. Jarenlang geloofden sommige deskundigen dat n = 6, hetgeen nogal een schril contrast is met de door Graham bewezen bovenlimiet. In 2001 bewees Geoff Exoo echter dat n ≥ 11, en er zijn aanwijzingen dat n > 11 moet zijn.

[bewerk] Definitie van het getal van Graham

Zoals gezegd is het getal van Graham alleen te schrijven in de pijlomhoognotatie. Om het getal van Graham aan te duiden definiëren we de volgende rij:

$\begin{matrix} G_0 & = & 4 \end{matrix}$

$\begin{matrix} G_1 & = & 3\uparrow\uparrow\uparrow\uparrow3 \end{matrix}$

$\begin{matrix} G_2 & = & 3\ \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow}\ 3 \\ & & {G_1} \end{matrix}$

$\begin{matrix} G_n & = & 3\ \underbrace{\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\cdots\uparrow}\ 3 \\ & & {G_{(n-1)}} \end{matrix}$

In deze reeks is het getal van Graham gelijk aan $G 64$ .

[bewerk] Toelichting

Om duidelijk te maken hoe absoluut onvoorstelbaar groot het Getal van Graham is, zij vermeld dat zelfs G₁ al niet meer in de wetenschappelijke notatie of meervoudig exponentiële notatie is op te schrijven. Zie onderstaande uitwerking om dit te illustreren:

$3\uparrow3=3^3=27$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987$

$\begin{matrix} 3\uparrow\uparrow\uparrow3 & = 3\uparrow\uparrow7625597484987 & = & \underbrace{\ 3^{3^{3^{3^{\cdots^3}}}} }\ \\ & & & {7625597484987} \end{matrix}$ ofwel 3³ berekenen, en vervolgens steeds weer, namelijk 7.625.597.484.985 maal, het berekende getal gebruiken als exponent voor het grondtal 3.

Dit is al een getal wat het menselijke bevattingsvermogen verre te boven gaat, ontelbare malen groter dan bijvoorbeeld 10^googolplex. En het is nog niets eens G₁.

Noem het voorgaande getal F. Dan geldt dat
$G_1 = 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 3 = 3\uparrow\uparrow\uparrow F = \begin{matrix} \underbrace{3_{}\uparrow\uparrow 3\uparrow\uparrow\dots\uparrow\uparrow 3}\\ F\mathrm{\, kopie\ddot{e}n \, van \,}3 \end{matrix}$

Vervolgens wordt na 63 recursieve stappen, waarin steeds $G i$ wordt gebruikt als het aantal omhoog-pijltjes in $G i + 1$ , het Getal van Graham verkregen.