Graham-szám

A Graham-szám, amely Ronald Graham amerikai matematikusról kapta nevét, arról nevezetes, hogy valószínűleg a legnagyobb olyan szám, ami matematikai bizonyításban valaha is előfordult. Jóval nagyobb annál, hogy a szokásosan használt tízes számrendszerben – akár még normálalak használatával is – le lehessen írni, így lejegyzéséhez, definiálásához külön jelölésrendszerre van szükség. Ennek ellenére elemi számelméleti módszerekkel tetszőlegesen sok számjegye kiszámítható (igaz, „hátulról”, a kisebbektől a nagyobb helyiértékek felé haladva). Graham számának utolsó 10 számjegye …2464195387.

A Graham-probléma

A Graham-szám a következő probléma megoldásakor merült fel, mely probléma egyébként a kombinatorikai, pontosabban diszkrét matematikai jellegű, Ramsey-elméletnek nevezett terület körébe tartozik:

Képzeljünk el egy n dimenziós hiperkockát, és kössük össze minden csúcspárját, hogy egy $2^{n}$ csúcsú teljes gráfot kapjunk. Ezt követően színezzük ki e gráfnak minden élét csupán két színnel (például pirossal és kékkel). Mi n legkisebb olyan értéke (azaz legalább hány dimenziós kell legyen a hiperkocka), amelyiknél minden ilyen színezés szükségképpen tartalmaz egy olyan teljes részgráfot, mely egyszínű (tehát minden éle piros, vagy minden éle kék), és még 4, egy síkban fekvő csúcsa is van?

Habár a probléma megoldása még várat magára, de az bizonyított, hogy a Graham-szám olyan szám, melynél a fenti n érték biztosan kisebb kell hogy legyen, és ennél jobb felső becslést n-re még nem találtak.

Az 1989-es, Penrose Tiles to Trapdoor Ciphers című könyvében (ISBN 0-88385-521-6) Martin Gardner azt írta, hogy „A Ramsey-elmélet szakértőinek véleménye szerint a tényleges Ramsey-szám erre a problémára valószínűleg 6”, s ebből az következik, hogy a Graham-szám feltehetően a legrosszabb felső becslés, amit valaha is egy ismeretlen mennyiség értékének nagyságára tettek. 2003-ban az Indianai Állami Egyetem munkatársa, Geoff Exoo bizonyította, hogy a 6 rossz alsó becslés, ugyanis a keresett szám nagyobb, mint 11.^[forrás?]

Úgy tartják, hogy a Graham-szám a legnagyobb olyan szám, amit a gyakorlatban valaha is alkalmaztak. Nagyobb, mint a Moser-szám, vagy a Googolplex (ezek is irdatlanul óriási számok).

A Graham-szám definíciója

Graham száma a 65. az alábbi sorozatban, ahol minden tag a következőhöz szükséges Knuth-nyilak száma:

$4,\ 3\uparrow \uparrow \uparrow \uparrow 3,\ 3\uparrow \cdots \uparrow 3,\ 3\uparrow \cdots \uparrow 3,\ \ldots$

Ennek megfelelően határozzuk meg az f(n) = hyper(3,n+2,3) = 3→3→n függvényt, majd a függvényhatványok segítségével adódik G=f⁶⁴(4).

Magát G-t, a Graham-számot nem lehet a Conway-féle láncoltnyíl-jelöléssel tömören kifejezni, de $3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2$, lásd a Graham-számra vonatkozó részeket a Conway-féle láncoltnyíl-művelet c. szócikkben.

Források

• A Ramsey-probléma hiperkockákon, Geoff Exoo cikke
• A Mathworld cikke a Graham-számról