Grahamin luku: äärimmäisen suuri luku Ramsey-teoriassa
Grahamin luku: uskomattoman valtava Ramsey-teorian ratkaisu — tutustu maailman yhteen suurimmista matemaattisista luvuista, sen historiasta ja merkityksestä.
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.
Konteksti
Ramsey-teoria on matematiikan osa-alue, jossa kysytään seuraavanlaisia kysymyksiä:
Oletetaan, että piirretään jokin määrä pisteitä ja yhdistetään jokainen pistepari viivalla. Jotkut viivat ovat sinisiä ja jotkut punaisia. Löydämmekö aina kolme pistettä, joita yhdistävät kolme viivaa ovat kaikki samanvärisiä?
On käynyt ilmi, että tässä yksinkertaisessa ongelmassa vastaus on "kyllä", kun pisteitä on vähintään 6, riippumatta siitä, miten viivat on väritetty. Mutta kun meillä on 5 pistettä tai vähemmän, voimme värittää viivat niin, että vastaus on "ei".
Sanotaan taas, että meillä on joitakin pisteitä, mutta nyt ne ovat n-ulotteisen hyperkuution kulmia. Ne ovat edelleen kaikki yhteydessä toisiinsa sinisillä ja punaisilla viivoilla. Kaikkia 4 pistettä yhdistää 6 viivaa. Löydämmekö 4 pistettä, jotka kaikki sijaitsevat yhdessä tasossa ja joita yhdistävät 6 viivaa ovat kaikki samanvärisiä?
Vaatimalla, että 4 pistettä on tasossa, olemme tehneet ongelmasta paljon vaikeamman. Haluaisimme tietää: millä n:n arvoilla vastaus on "ei" (jollain tavalla väritettäessä viivoja) ja millä n:n arvoilla vastaus on "kyllä" (kaikilla tavoilla väritettäessä viivoja)? Mutta tätä ongelmaa ei ole vielä täysin ratkaistu.
Vuonna 1971 Ronald Graham ja B. L. Rothschild löysivät osittaisen ratkaisun tähän ongelmaan. He osoittivat, että kun n=6, vastaus on "ei". Mutta kun n on hyvin suuri, yhtä suuri kuin Grahamin luku tai suurempi, vastaus on "kyllä".
Yksi syy siihen, miksi tämä osittainen vastaus on tärkeä, on se, että se tarkoittaa, että vastaus on lopulta "kyllä" ainakin jollekin suurelle n:lle. Ennen vuotta 1971 emme tienneet edes näin paljon.
Samalle ongelmalle on olemassa paljon pienempi raja-arvo N. Se on yhtä suuri kuin 
, missä 
. Tämän Grahamin julkaisemattomaan työhön liitetyn ongelman heikomman ylärajan julkaisi ja nimesi lopulta Martin Gardner Scientific American -lehdessä marraskuussa 1977.
Määritelmä
Grahamin luku ei ole liian suuri, jotta kaikki sen numerot voitaisiin kirjoittaa ylös, vaan se on liian suuri jopa tieteellisessä merkintätavassa. Jotta voimme kirjoittaa sen ylös, meidän on käytettävä Knuthin ylösnuolimerkintää.
Kirjoitamme ylös numerosarjan, jota kutsumme nimillä g1, g2, g3 ja niin edelleen. Jokaista käytetään yhtälössä seuraavan luvun löytämiseksi. g64 on Grahamin luku.
Seuraavassa on ensin joitakin esimerkkejä ylöspäin suuntautuvista nuolinäkökulmista:
on 3x3x3, mikä on 27. Kahden luvun välissä oleva nuoli tarkoittaa vain sitä, että ensimmäinen luku on kerrottu itsellään toisen luvun verran.- Voidaan ajatella, että
on 
, koska kaksi nuolta numeroiden A ja B välillä tarkoittaa vain sitä, että A on kirjoitettu B:n kanssa ylös useita kertoja, ja jokaisen A:n välissä on nuoli. Koska tiedämme, mitä yksittäiset nuolet ovat, on 3 kerrottuna itsellään kertaa ja tiedämme, että on kaksikymmentäseitsemän. Joten on 3x3x3x3x3x....x3x3, yhteensä 27 kertaa. Se vastaa 7 625 597 484 987 kertaa. 
on 
ja tiedämme, että on 7,625,597,484,987. Joten on 
. Tämä voidaan kirjoittaa myös seuraavasti: 
yhteensä 7,625,597,484,987 3s. Tämä luku on niin valtava, että sen numerot, vaikka ne kirjoitettaisiinkin hyvin pieninä, voisivat täyttää havaittavan maailmankaikkeuden ja sen ulkopuolella.- Vaikka tämä luku voi olla jo käsittämätön, tämä on vasta alkua tälle jättimäiselle määrälle.
- Seuraava tällainen askel on
tai 
. Tämä on luku, jota kutsumme nimellä g1.
After that, g2 is equal to 
; the number of arrows in this number is g1.
g3 is equal to 
, where the number of arrows is g2.
Jatkamme tällä tavalla. Lopetamme, kun määrittelemme g64:n olevan , where the number of arrows is g63.
Tämä on Grahamin numero.
Aiheeseen liittyvät sivut
- Knuthin ylösnuolimerkintätapa
Kysymyksiä ja vastauksia
K: Kuka määritteli Grahamin numeron?
V: Ronald Graham määritteli Grahamin luvun.
K: Millä matematiikan alalla Ronald Graham työskenteli, kun hän määritteli luvun?
V: Ronald Graham työskenteli Ramsey-teoriaksi kutsutulla matematiikan alalla, kun hän määritteli luvun.
K: Mitä Ronald Graham todisti ongelmallaan?
V: Ronald Graham todisti, että vastaus hänen ongelmaansa oli pienempi kuin Grahamin luku.
K: Kuinka suuri Grahamin luku on verrattuna muihin matemaattisissa todistuksissa käytettyihin lukuihin?
V: Grahamin luku on yksi suurimmista matemaattisessa todistuksessa koskaan käytetyistä luvuista.
K: Jos luvun jokainen numero kirjoitettaisiin, mahtuisiko se havaittavaan maailmankaikkeuteen?
V: Vaikka Grahamin luvun jokainen numero kirjoitettaisiin mahdollisimman pienellä kirjoituksella, se olisi silti liian suuri mahtuakseen havaittavaan maailmankaikkeuteen.
K: Voiko mitenkään laskea tai arvioida, kuinka suuri tämä luku on?
V: Ei ole olemassa tarkkaa tapaa laskea tai arvioida, kuinka suuri tämä tietty luonnollinen luku on, koska sitä ei ole vielä täysin määritelty.
K: Miksi näin suuri luonnollinen luku on olemassa ja mitä tarkoitusta se palvelee?
V: Tämä erittäin suuri luonnollinen luku on olemassa, koska Ronald Grahm käytti sitä osana matemaattista todistusta, ja se toimii hänen ratkaisunsa ylärajana.
Etsiä