Grahamin luku

Grahamin luku on Ronald Grahamin päättelemä erittäin suuri luku, johon usein viitataan suurimpana matemaattisen todistuksen lukuna. Tämä tarkoittaa sitä, että Grahamin luku oli suurin luku, joka esiintyy matemaattisessa todistuksessa tietyn ongelman eksplisiittisenä rajana. Graham päätyi lukuun etsiessään todistusta Ramseyn lauseen erääseen ongelmaan.

Esimerkki:Kahdella värillä väritetty 3-ulotteinen kuutio, joka sisältää yksivärisen 4-kulmaisen osakuvion, joka on kuvattu kuution alapuolelle. Huomaa, ettei kuutio voisi sisältää tätä osakuviota, jos yksikin osakuvion viivoista korvattaisiin toisella värillä – täten todistaen että N* > 3.

Sittemmin on löydetty sitäkin isompia lukuja, mutta Grahamin luku on silti suurin omalla nimellä tunnettu luku.

Ongelma

Ramseyn lauseessa kysytään muun muassa:

Oletetaan että piirrämme joitain pisteitä ja yhdistämme jokaisen pisteen toiseen viivalla, jonka väritämme punaiseksi tai siniseksi. Voimmeko löytää 3 pistettä, joiden 3 viivaa ovat kaikki samanvärisiä?

Tämän ongelman vastaus on "kyllä", jos pisteitä on 6 tai enemmän.

Grahamin luku tulee vastauksena kysymyksen variaatioon:

Meillä on n-ulottuvuuden hyperkuutio, jonka kaikki pisteet yhdistetään samoin punaisella tai sinisellä viivalla. Onko olemassa 4 samalla tasolla olevaa pistettä, joiden kaikki 6 linjaa ovat samanvärisiä?

(Once again, say we have some points, but now they are the corners of an n-dimensional hypercube. They are still all connected by blue and red lines. For any 4 points, there are 6 lines connecting them. Can we find 4 points that all lie on one plane, and the 6 lines connecting them are all the same color?)

Ongelma voidaan esittää myös seuraavasti:

Laske kaikki tavat, joilla n-ulottuvuuden hyperkuution kaikki linjat voidaan värittää kahdella eri värillä. Tuloksena on Grahamin luku.

(Take an N-dimensional cube, and count the number of ways you can color all of it's lines using red and blue. Obviously there must be more ways to color the lines than there are lines, right?! Not so: Take a Graham's Dimensional hyper-cube and there are just as many lines as there are ways to color them! Graham's Number is the smallest number with this property.)

Vuonna 1971 Ronald Graham ja B. L. Rothschild löysivät osittaisen vastauksen tähän ongelmaan: N*, jonka rajat ovat 6 ≤ N* ≤ N, missä yläraja N on suuri, mutta äärellinen luku, Grahamin luku "G":

$G=\scriptstyle F^{7}(12)\;=\;F(F(F(F(F(F(F(12)))))))$,

missä

$\scriptstyle F(n)\;=\;2\uparrow ^{n}3$

Knuthin nuolinotaatiolla.

Yläraja saatiin alennettua 2013 Hales–Jewettin luvulla $\scriptstyle N'\;=\;2\;\uparrow \uparrow \;2\;\uparrow \uparrow \;2\;\uparrow \uparrow \;9$.

Alarajan sai Geoff Exoo vuonna 2003 parannettua 6:sta 11:een, ja Jerome Barkley vuonna 2008 13:een. Niinpä N*:n raja-arvot ovat tällä hetkellä (2013) 13 ≤ N* ≤ N'.

Määritelmä

Grahamin lukua ei voi esittää tavanomaisilla matemaattisilla operaattoreilla. Jopa sen esittäminen potenssikorotuksella (muodossa $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$) on epäkäytännöllistä. Sen sijaan käytetään Knuthin nuolinotaatiota.

Määritellään

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3$

$g_{n}=3\uparrow ^{g_{n-1}}3$

missä $\uparrow ^{g_{n-1}}$ vastaa $g_{n-1}$ nuolta, joten Grahamin luku $G=g_{64}$ on:

$\left.{\begin{matrix}&3\underbrace {\uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&3\underbrace {\uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\g_{64}=&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&3\underbrace {\uparrow \cdots \cdot \cdot \uparrow } 3\\&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 tasoa}}$

Viimeinen numero

Luvun 500 viimeistä numeroa ovat:

  …02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387

Graham itse laski viimeisen numeron vuonna 1977 olevan juuri "7". Kukaan ei ole pystynyt laskemaan mikä on luvun ensimmäinen numero.

Jos Grahamin luku kirjoitettaisiin siten, että yksi numero veisi yhden Planckin tilavuuden eli 4,22 x 10^-105 m³ (kvanttifysiikan mukaan pienin mahdollinen tilavuus), se ei mahtuisi havaittavaan maailmankaikkeuteen. Luvun suuruutta kuvaa se, että pelkästään nuolten määrä tasolla g₁ (= 3↑↑↑↑3) on suurempi kuin Planckin tilavuuksien lukumäärä havaittavassa maailmankaikkeudessa (noin 10¹⁸⁵).

Grahamin luku mainitaan Guinnessin ennätysten kirjassa suurimpana matemaattisessa todistuksessa käytettynä lukuna.

Aiheesta muualla

• Catalyst: Graham's number
• These are the biggest numbers in the universe