Nombro de Graham

En matematiko, nombro de Graham, nomita pro Ronald Graham, estas granda nombro kiu estas supera baro por solvaĵo de certa problemo en teorio de Ramsey.

Ĉi tiu nombro ekhavis iun popularan atenton kiam Martin Gardner priskribis ĝin en sekcio "Matematikaj ludoj" de Scientific American en novembro de 1977, skribante ke "En nepublikigita pruvo, Graham ĵus fondis ... baron tiel vastan ke ĝi tenas la rikordon por la plej granda nombro iam uzata en serioza matematika pruvo." La libro de mondaj rikordoj de Guiness de 1980 ripetis la pretendon de Gardner, aldoninte la popularan intereson al ĉi tiu nombro.

Nombro de Graham estas multe pli granda ol aliaj konataj grandaj nombroj tiaj kiel guglo kaj gugloplekso, kaj eĉ pli granda ol nombro de Skewes kaj nombro de Moser, aliaj konataj pli grandaj nombregoj. Ne ebla, en la limigoj de nia universo, signifi la nombron de Graham, aŭ iun moderan proksimumadon de ĝi, en kutima cifereca sistemo Eĉ potencaj turoj de formo  netaŭgas por ĉi tiu celo, kvankam ĝi povas esti facile priskribita per rikura formulo uzanta notacion de Knuth aŭ iun ekvivalentan, kiel estis farite de Graham.

Specifaj entjeroj malproksime pli grandaj ol nombro de Graham poste aperis en multaj seriozaj matematikaj pruvoj, ekzemple, kun diversaj finiaj formoj de Friedman de teoremo de Kruskal.

 Problemo de Graham 

La nombro de Graham aperis el la sekva problemo en branĉo de matematiko sciata kiel teorio de Ramsey:

 Konsideru n-dimensian hiperkubon, kaj trakonektu ĉiun paron de ĝiaj verticoj por ricevi plenan grafeon sur 2n verticoj. Tiam kolorigu ĉiun lateron de ĉi tiu grafeo ruĝe aŭ nigre. Kio estas la plej malgranda valoro de n por kiu ĉiu ebla ĉi tia kolorigo nepre enhavas samkoloran plenan subgrafeon de 4 verticoj kiu kuŝas en unu 2-dimensia ebeno en la fonta hiperkubo?

Graham kaj Rothschild en 1971 pruvis ke ĉi tiu problemo havas solvaĵon N* kaj donis kiel la baroj pritakson 6 ≤ N* ≤ N, kie N estas certa eksplicite difinita tre granda nombro. Tamen, Graham en nepublikigita laboro reviziis ĉi tiun superan baron al esti multe pli granda nombro. La reviziita supera baro de Graham estis poste publikigita kaj ĝuste ĝi estas la nombro de Graham.

La suba baro de la problemo estis poste plibonigita de Exoo en 2003, kiu montris ke la solvaĵo al estas minimume 11, kaj provizis eksperimentan indikaĵon sugestantan ke ĝi estas minimume 12. Tial, la plej bonaj sciataj baroj por la solvaĵo N* estas 11 ≤ N* ≤ G, kie G estas nombro de Graham.

 Difino de nombro de Graham 

Per notacio de Knuth, nombro de Graham G (kiel estas difinita en artikolo de Gardner en Scienca Ameriko) estas

kie kvanto de la sagoj en ĉiu tavolo krom la plej suba estas valoro de la sekva pli suba tavolo.

Aŭ ekvivalente

 G = g64

kie  kaj
  por n>1

aŭ

 G = f64(4)

kie 

kie supra indico sur supren-sago indikas la kvanton de sagoj kaj supra indico sur f indikas ripeton de apliko de funkcio. La funkcio f estas speciala okazo de la hiperoperatora familio de funkcioj, f(n) = hyper(3, n+2, 3), kaj povas ankaŭ esti esprimita per ĉena indikila skribmaniero de Conway kiel . La lasta skribmaniero ankaŭ provizas jenajn barojn por G:

 Dekumaj ciferoj de nombro de Graham 

La nombro de Graham estas potenca turo de formo  kun tre granda valoro de n, tiel ĝiaj la lastaj (dekstraj aŭ la plej malgrande signifaj) dekumaj ciferoj devas kontentigi certajn propraĵojn komunajn al ĉiuj ĉi tiaj turoj. Unu el ĉi tiuj propraĵoj estas ke ĉiuj ĉi tiaj turoj de alto pli granda ol donita valoro d havas la saman vicon de d plej dekstraj dekumaj ciferoj. Ĉi tio estas speciala okazo de pli ĝenerala propraĵo: La d plej dekstraj dekumaj ciferoj de ĉiuj ĉi tiaj turoj de alto pli granda ol d+2, estas sendependa de la plej supra 3 en la turo; kio estas, la plej supra 3 povas esti ŝanĝita al ĉiu la alia nenegativa entjero sen afekto de la d plej dekstraj ciferoj.

Jena tabelo ilustras, por kelkaj valoroj de d, kiel ĉi tio okazas. Por donita alto de turo kaj nombro de ciferoj d, la plena limigo de d-ciferaj nombroj (10d de ilin) faras ne okazi; anstataŭe, certa pli malgranda subaro de valoroj ripetas sin en ciklo. La longo de la ciklo kaj iu el la valoroj (en krampoj) estas montritaj por ĉiu okazo:

 Kvanto de ciferoj d      1 4  (1, 3, 9, 7)  2  (3, 7)  1  (7) 2 20  (01, 03, ..., 87, ..., 67)  4  (03, 27, 83, 87)  2  (27, 87)  1  (87) 3 100  (001, 003, ..., 387, ..., 667)  20  (003, 027, ...387, ..., 587)  4  (027, 987, 227, 387) 2  (987, 387)  1  (387)

Ekzemple, por d=1 konsiderante ke , estas:

 30=1
 31=3
 32=9
 33=27
 34=81
 35=243
 36=729
 37=2187
 ...

kaj la lasta unu cifero estas 1, 3, 9, 7, kaj denove 1, 3, 9, 7, kaj tiel plu kiel estas skribite en la tabelo.

Por  estas:





 ...

kaj la lasta unu cifero estas 3, 7, kaj denove 3, 7, kaj tiel plu kiel estas skribite en la tabelo.

La apartaj plej dekstraj d ciferoj kiuj estas definitive komunigitaj per ĉiuj sufiĉe altaj turoj de 3 estas montritaj per grasa tiparo pli supre, kaj videblas kiel ili ellaboriĝas kiam la turo plialtiĝas. Por ĉiu fiksita kvanto de ciferoj d (linio en la tabelo), la kvanto de valoroj eblaj por , kie x estas nenegativa entjero, estas malgrandiĝanta kiam la alto pligrandiĝas, ĝis la sola nombro kiam la alto superas d+2.

Simpla algoritmo La matematika forumo @ Drexel ("Lastaj 8 ciferoj de Z") Universitato Drexel por komputado de ĉi tiuj ciferoj povas esti sekva: estu komence x = 3, tiam ripetu d fojojn, la asignon x := 3x mod 10d. La fina valoro asignita al x estas tiam la d plej dekstraj dekumaj ciferoj de  por ĉiu n>d. Se la fina valoro de x havas malpli ol d'' dekumajn ciferojn necesas aldoni la kondukajn 0.

Ĉi tiu algoritmo produktas jenajn 100 plej dekstraj dekumaj ciferoj de nombro de Graham (aŭ ĉiu turo de pli ol 100 nombroj 3):

 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387

Referencoj

 Vidu ankaŭ 
 Teorio de Ramsey
 Notacio de Knuth
 Hiperoperatoro
 Ĉena indikila skribmaniero de Conway
 Granda nombro
 Guglo
 Gugloplekso
 Nombro de Skewes
 Nombro de Moser
 Teoremo de Kruskal
 Finia formo de Friedman

 Eksteraj ligiloj 
 Kiel kalkuli nombron de Graham
 Problemo de Ramsey sur hiperkuboj de Geoff Exoo
 Nombro de Graham je Mathworld
 Speciala enciklopedio de nombroj

Kategorio:Naturaj nombroj kun propraj nomoj
Kategorio:Grandaj nombroj