Grahamin luku on erittäin suuri luonnollinen luku, jonka määritteli Ronald Graham -niminen mies. Graham työskenteli ongelman parissa matematiikan osa‑alueella, jota kutsutaan Ramsey‑teoriaksi, ja hän osoitti että eräälle Ramsey‑tyyppiselle kysymykselle löytyi vastaus, jonka voi sijoittaa pienemmäksi kuin tietty äärettömän suuri luku — tämä luku tunnetaan nimellä Grahamin luku.
Määritelmä ja notaatio
Grahamin luvun määrittelyssä käytetään Knuthin nuolimerkintää (up‑arrow notation), jonka avulla voidaan helposti kuvata hyvin suuria eksponenttirakenteita. Lukujono G1, G2, … määritellään rekurssiivisesti siten, että
- G1 = 3 ↑↑↑↑ 3 (eli 3, jonka ympärille on neljä up‑arrow'ta ja toinen 3),
- G_{n+1} = 3 ↑^{G_n} 3, eli G_{n+1} saadaan kirjoittamalla 3:n väliin G_n kappaletta nuolia.
Grahamin luvuksi otetaan G64 — eli määritellyn ketjun 64. jäsen. Tämä rakentamistapa johtaa niin nopeaan kasvunopeuteen, että G2 on jo käsittämättömän suuri ja G64 on sitä monta kertaluokkaa suurempi.
Esimerkkinä pienempää up‑arrow‑notaatioita: 3 ↑↑ 3 tarkoittaa 3^(3^3) = 3^27 ≈ 7,6×10^12, eli vielä laskettavissa oleva mutta suuri luku. Neljän up‑arrow'n tasolla (G1) ja sen jälkeisillä rekursioilla luvut kasvavat kuitenkin paljon nopeammin kuin mihin tavanomaiset potenssi‑ tai kertomerkintätavat riittävät.
Koko ja vertailu
Grahamin luku on yksi suurimmista luvuista, joita on koskaan käytetty järkevässä matemaattisessa todistuksessa. Sen kokoa on vaikea käsittää: vaikka Grahamin luvun jokainen numero kirjoitettaisiinkin pienimmällä mahdollisella kirjoitusasulla, se olisi silti liian suuri mahtuakseen havaittavaan maailmankaikkeuteen — eli luvun desimaaliesityksen merkkien määrä ylittää kaikissa tunnetuissa mittakaavoissa olevien hiukkasten määrän.
Kuitenkin on tärkeää huomata, että Grahamin luku on vain yläraja eräälle Ramsey‑tyyppiselle ongelmalle. Todellinen pienin luku, joka ongelman vaatimukset täyttää, on huomattavasti pienempi; myöhemmät tutkimukset ovat pudottaneet alkuperäistä ylärajaa merkittävästi. Lisäksi Grahamin luvusta on laskettavissa joitakin ominaisuuksia — esimerkiksi tietyt loppuosat (modulaariset jäännökset) voidaan laskea tehokkailla algoritmeilla — vaikka koko lukua ei voi käytännössä esittää desimaalimuodossa.
Historia ja merkitys
Ronald Graham esitteli luvun osana työtään Ramsey‑teorian problemluokan ylärajojen asettamiseksi. Grahamin luku tuli laajemman yleisön tietoon osittain populaarikirjallisuuden ja matematiikkalehdistön vuoksi, ja se on usein käytetty esimerkkinä äärimmäisen suurista luvuista ja siitä, kuinka erilaiset notaatiojärjestelmät (nuolimerkintä, Conwayn nuolat yhdistävät nuolat jne.) auttavat kuvaamaan tällaisia määriä.
Muut huomiot
- Grahamin luvun jälkeen on määritelty ja tutkittu vieläkin nopeammin kasvavia lukusarjoja (esimerkiksi Busy Beaver -funktioon ja tiettyihin Ramsey‑ongelmiin liittyviä lukuja), joten ”suurin tunnettu luku” ei ole yksiselitteinen käsite.
- Matemaatikot käyttävät Grahamin lukua usein havainnollistamaan sitä, miten ongelmien ylärajoiksi voidaan saada äärimmäisen suuria mutta silti hyvin määriteltyjä lukuja.
Yhteenvetona: Grahamin luku on konkreettisesti määritelty, äärettömän suuri luonnollinen luku, joka syntyi Ramsey‑teoreettisesta yläraja‑arviosta. Se ei kuvaa kaikkein nopeimmin kasvavien matemaattisten säikeiden huippua, mutta on silti yksi tunnetuimmista ja vaikuttavimmista esimerkeistä ihmismielen kyvystä käsitellä ja formalisoida äärimmäistä kasvua.
