Graham szám

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 25-én felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

Graham száma egy szuperóriás szám , amely a Ramsey-elmélet egy adott probléma megoldásának felső korlátja . Valami nagyon nagy hatványa a hármasnak, amelyet Knuth-jelöléssel írnak le . Ronald Grahamről nevezték el .

A nagyközönség számára azután vált ismertté, hogy Martin Gardner 1977. novemberi Scientific American rovatában, a "Math Games" című rovatában leírta , ahol ez állt: "Egy kiadatlan bizonyítékban Graham nemrég olyan nagy korlátot állított fel, hogy ez tartja a legnagyobb rekordot. szám, amelyet valaha is használtak egy komoly matematikai bizonyításhoz ."

1980- ban a Guinness Rekordok Könyve megismételte Gardner állításait, tovább növelve ezzel a számmal kapcsolatos közérdeklődést. Graham száma elképzelhetetlenül sokszor nagyobb, mint más jól ismert nagy számok, mint például a googol , a googolplex , és még nagyobb, mint Skuse és Moser száma . Valójában a teljes megfigyelhető univerzum túl kicsi ahhoz, hogy tartalmazza a Graham-szám szokásos decimális jelölését (feltételezzük, hogy az egyes számjegyek jelölése legalább a Planck-térfogatot elfoglalja ). Még a formájú erőtornyok is használhatatlanok erre a célra (ugyanabban az értelemben), bár ez a szám felírható rekurzív képletekkel, mint például Knuth jelölése vagy azzal egyenértékű, ahogy azt Graham tette. Graham számának utolsó 50 számjegye: 03222348723967018485186439059104575627262464195387. $a^{{b^{{c^{{\cdot ^{{\cdot ^({\cdot ))))))))))))$

A modern matematikai bizonyításokban néha előfordulnak olyan számok, amelyek még mindig jóval nagyobbak Graham számánál, például a Kruskal-tétel Friedman véges alakjával - az úgynevezett FA(3) .

Graham problémája

A Graham-szám a következő problémához kapcsolódik a Ramsey-elméletben :

Tekintsünk egy -dimenziós hiperkockát , és kössük össze az összes csúcspárt , hogy teljes gráfot kapjunk csúcsokkal . Színezd ki a grafikon minden élét pirosra vagy kékre. Mi az a minimális érték , amelyhez minden ilyen színezés szükségszerűen tartalmaz egy egyszínű teljes részgráfot négy csúcsgal, amelyek mindegyike ugyanabban a síkban van?

n

2^{n}

n

Graham és Rothschild 1971 -ben bebizonyította, hogy ennek a problémának van megoldása, és megmutatták, hogy ahol egy konkrét, jól definiált, nagyon nagy szám van. Knuth nyíl jelölésének nyelvén így írható , ahol . Ezt a számot "kis Graham-számnak" (eng. Little Graham) nevezik. $N^{*}$ $6\leqslant N^{*}\leqslant N$ $N$ $N=F^{7}(12)$ $F(n)=2\uparrow ^{n}3$

Az alsó korlátot Exoo 2003 -ban , Barclay 2008-ban javította, és kimutatta, hogy legalább 13-nak kell lennie. Ezután a felső korlátot javították -ra, majd -ra . Így, . $N^{*}$ $2\uparrow ^{3}6$ $2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$ $13\leqslant N^{*}\leqslant 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$

Ennek a cikknek a tárgya a felső korlát , amely sokkal gyengébb (azaz nagyobb), mint : , ahol . Ezt a Graham kiadatlan munkájában leírt határt írta le (és nevezte Graham számának) Martin Gardner. $G$ $N$ $G=f^{64}(4)$ $f(n)=3\uparrow ^{n}3$

Graham számának meghatározása

A Knuth-féle nyíl jelöléssel Graham G -száma így írható fel

\left.{\begin{mátrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow }3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \c cdots \uparrow }3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;}\\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow }3\\&&3\ felfelé \uparrow \uparrow \uparrow 3\end{mátrix}}\jobbra\}{\szöveg{64 réteg}}

ahol az egyes rétegekben lévő nyilak számát felülről kezdve a következő rétegben lévő szám határozza meg, azaz.

G=g_{64},

ahol

g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,

ahol a nyíl felső indexe a nyilak teljes számát jelzi. Vagyis 64 lépésben számítjuk: az első lépésben négy nyilakkal számolunk a hármasok között, a másodikban - a hármasok közötti nyilakkal, a harmadikban - a hármasok közötti nyilakkal, és így tovább; a végén a hármaspárok közötti nyilakból számolunk . $G$ $g_{1}$ $g_{2}$ $g_{1}$ $g_{3}$ $g_{2}$ $G=g_{{64}}$ $g_{{63}}$

Ezt így lehet írni

G=f^{64}(4)

, ahol

f(n)=3\uparrow ^{n}3,

ahol az y felső index a függvény iterációit jelenti. A függvény a hiperoperátorok speciális esete, és Conway láncnyilaival is írható, mint . Az utolsó bejegyzés lehetővé teszi a következő határértékek beírását is : $f$ $f$ $f(n)={\szöveg{hiper}}(3,n+2,3)$ $f(n)=3\jobbra 3\jobbra nyíl (n+2)$ $G$

3\jobbra 3\jobbra 64\jobbra 2<G<3\jobbra 3\jobbra 65\jobbra 2.

Bowers masszív jelöléssel a Graham-számhatárok a következőképpen írhatók fel:

{3,64,1,2} < G < {3,65,1,2}.

Graham számskála

A Graham-szám méretének megértéséhez hasznos, ha egy gyorsan növekvő 64 tagú sorozat (az úgynevezett „grál”, Grahal) legalább az első tagját ( g 1 ) próbáljuk hatványozással ábrázolni . A tetraciók nyelvén ez azt jelenti: $\uparrow \uparrow$

g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow {\Bigl (}3\uparrow \uparrow { \bigl (}3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots {\bigr )}{\Bigr )}

ahol a hármasok száma a jobb oldali kifejezésben

3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3).

Most minden tetració ( ) definíció szerint egy "erőtoronnyá" bontakozik ki, mint $\uparrow \uparrow$

3\uparrow \uparrow X\ =\ 3\uparrow {\Bigl (}3\uparrow {\bigl (}3\uparrow \dots (3\uparrow 3)\dots {\bigr )}{\Bigr )}\ = \ 3^{{3^{{\cdot ^{{\cdot ^({\cdot ^{{3))))))))))))

, ahol X a hármasok száma.

Ily módon

g_{1}=3\felsőparrow \felső parrow (3\felső parrow (3\felső parrow \ \pontok \ (3\felsőparrow \felső parrow)\pontok))

, ahol a hármasikrek száma .

3\uparrow\uparrow (3\uparrow\uparrow 3)

Fokokkal is felírható:

g_{1}=\left.{\begin{mátrix}3^{{3^{{\cdot ^({\cdot ^{{\cdot ^{{\cdot ^{{3))))))) } )))))\end{mátrix}}\jobbra\}\left.{\begin{mátrix}3^{{3^{{\cdot ^{{\cdot ^{{\cdot ^{{3) ) }}}}}}}}\end{mátrix}}\jobbra\}\pontok \bal.{\begin{mátrix}3^{{3^{3}}}\end{mátrix}}\jobbra\ } 3\quad

, ahol a tornyok száma ,

\quad \left.{\begin{mátrix}3^{{3^{{\cdot ^{{\cdot ^({\cdot ^{{3))))))))))\end{ mátrix} }\jobbra\}\left.{\begin{mátrix}3^{{3^{3}}}\end{mátrix}}\jobbra\}3

ahol balról indulva az egyes tornyokban lévő hármasikrek számát az előző torony jelzi.

Más szavakkal, kiszámítása a tornyok számának kiszámításával történik (ahol a hármasok száma = 7 625 597 484 987 ), majd a következő sorrendben számítja ki a tornyokat: $g_{1}$ $n=3^{{3^{{\cdot ^{{\cdot ^({\cdot ^{{3))))))))))))$ $3^{{3^{{3}}}}$ $n$

1. torony: 3

2. torony: 3↑3↑3 (hármasok száma - 3) = 7 625 597 484 987

3. torony: 3↑3↑3↑3↑…↑3 (a hármasikrek száma 7 625 597 484 987 ) = …

$g_{1}$ = -edik torony: 3↑3↑3↑3↑3↑3↑3↑…↑3 (a hármasok számát a -edik torony számításának eredménye adja) $n$ $(n-1)$

Az első tag skálája olyan nagy, hogy szinte lehetetlen megérteni, bár a fenti jelölés viszonylag könnyen érthető. Bár - ez csak a tornyok száma a képletben , ez a szám már sokkal nagyobb, mint a megfigyelhető univerzumban található Planck-kötetek száma (körülbelül ). Már nagyobb, mint egy googolplex, és a teljes rekord 7625597484987 hármasával már a harmadik toronyban (az úgynevezett "tritri", Tritri) elfoglalja a Föld és a Nap közötti távolságot. Még egy négy hármas torony is túl nagy szám ahhoz, hogy közvetlenül ábrázoljuk. Az első tag után egy gyorsan növekvő sorozat további 63 tagja vár ránk. $g_{1}$ $n$ $g_{1}$ $4\cdot 10^{185}$ $3^{3^{3^{3))}=3^{7\,625\,597\,484\,987}\körülbelül 1{,}3\szor 10^{3\,638 \,334\,640\,024}$

Lásd még

Irodalom

Graham, R. L.; Rothschild, BL Ramsey-tétel n-paraméteres halmazokhoz // Az Amerikai Matematikai Társaság tranzakciói . - 1971. - 1. évf. 159 . - P. 257-292 . - doi : 10.2307/1996010 . Az N kifejezett képletea p. 290.
Graham, R. L.; Rothschild, B. L. (1978). "Ramsey Theory", Studies in Combinatorics , Rota, G.-G., szerk., Mathematical Association of America , 17 , 80-99. o. A 90. ábrán a „legjobb elérhető becslés” kifejezésben a megoldásra az N kifejezett képlete megismétlődik az 1971-es cikkből.
Gardner, Martin. Matematikai játékok (angol) // Scientific American . - Springer Nature , 1977. - November ( 237. kötet ). - P. 18-28 . ; újranyomva (2001-ben átdolgozva) a következő könyvben:
Martin Gardner . A matematika kolosszális könyve :klasszikus rejtvények, paradoxonok és problémák . - New York, NY: Norton, 2001. - ISBN 0393020231 .
Martin Gardner . Penrose csempe a csapóajtó titkosítókhoz (neopr.) . — Washington, DC: Mathematical Association of America , 1989. — ISBN 0-88385-521-6 .
Exo, Geoffrey. Egy euklideszi Ramsey-probléma (neopr.) // Discrete Computational Geometry. - 2003. - T. 29 . - S. 223-227 . - doi : 10.1007/s00454-002-0780-5 .

Linkek

Graham szám az ujjakon
" A hiperkockák Ramsey-problémája ". Geoff Exoo
Weisstein, Eric W. Graham száma (angolul) a Wolfram MathWorld weboldalán .
Hogyan számítsuk ki Graham számát
Numeropedia – a számok speciális enciklopédiája

Számok tulajdonnévvel

Matematikai állandók

Algebrai

Transzcendentális ,
valószínűleg transzcendentális

Ezer fok

Régi orosz számok

A tíz többi hatványa

Tizenkettő hatványai

Más egész

Egyéb számok

képzeletbeli egység

Nagy számok
Számok	googol Shannon szám Googolplex Skewes szám Moser szám Graham szám FA (3) Rayo szám
Funkciók	Ackermann függvény Veblen funkció Buchholz Pszi-függvényei tetració Pentation Hiperoperátor Gyorsan növekvő hierarchia Lassan növekvő hierarchia Hardy hierarchia
Jelölések	Steinhaus-Moser jelölés Knuth nyíl jelölése Conway nyíl jelölése Massive Bowers jelölés