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.

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":
,
missä
 
Knuthin nuolinotaatiolla.

Yläraja saatiin alennettua 2013 Hales–Jewettin luvulla  .

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 ) on epäkäytännöllistä. Sen sijaan käytetään Knuthin nuolinotaatiota.

Määritellään

missä  vastaa  nuolta, joten Grahamin luku  on:

 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 Planckin tilavuus veisi yhden numeron, se ei mahtuisi tunnettuun universumiin. Luvun suuruutta kuvaa se, että pelkästään nuolten'' määrä tasolla g1 (= 3↑↑↑↑3), on suurempi kuin Planckin tilavuuksien lukumäärä tunnetussa universumissa (noin 10185).

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

Lähteet

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

Kombinatoriikka
Numerot
pl:Notacja strzałkowa#Liczba Grahama