Graham-szám

A Wikipédiából, a szabad lexikonból.

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 valalaha 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.

[szerkesztés] 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 (pl. 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 0883855216) 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. Újabban (2003-ban) azonban az Indianai Állami Egyetem munkatársa, Geoff Exoo kimutatta, hogy ennek a számnak legalább 11-nek kell lennie, és bizonyította is, hogy nagyobb annál.

Úgy tartják, hogy a Graham-szám a legnagyobb olyan szám, amit a gyakorlatban valaha is alkalmaztak. Nagyobb a Moser-számnál is (ez szintén egy óriási szám).

[szerkesztés] 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\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \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.