Númberu de Graham

El númberu de Graham, que recibe'l so nome de Ronald Graham, ye un númberu grande que ye una cota cimera de la solución d'un determináu problema na teoría de Ramsey. Esti númberu consiguió cierta fama popular cuando Martin Gardner escribió na seición «Mathematical Games» (Xuegos Matemáticos) de la revista Scientific American en payares de 1977:

Nuna demostración ensin publicar, Graham estableció apocayá ... una cota tan vasta que tien el rexistru de ser el mayor númberu enxamás usáu nuna demostración matemática seria.

El Llibru Guinness de los récores, na so edición de 1980, repitió l'afirmación de Gardner, lo que contribuyó al interés popular d'esti númberu. El númberu de Graham ye enforma mayor qu'otros conocíos númberos grandes tales como'l gúgol, el gúgolplex ya inclusive'l númberu de Skewes y el de Moser. Ello ye que ye imposible, daes les llimitaciones d'espaciu y materia del nuesu universu, denota'l númberu de Graham o un aproximamientu razonable del mesmu nun sistema de numberación convencional. Inclusive les «torres d'esponentes» de la forma $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ revélense inútiles pa esti propósitu, anque'l númberu puede ser descritu con fórmules recursives per aciu de la notación flecha de Knuth o fórmules equivalentes, como fixo Graham. Los diez últimos díxitos del númberu de Graham son ...2464195387. Anguaño, considéraselu como'l númberu representáu matemáticamente más grande de toos.

Dende'l descubrimientu y usu del númberu de Graham, emplegáronse númberos tovía mayores n'otres demostraciones matemátiques, por casu, rellacionaes coles variaes formes finites de Friedman del teorema de Kruskal.

Problema de Graham

El númberu de Graham ta rellacionáu col siguiente problema perteneciente a la caña de les matemátiques conocida como la teoría de Ramsey:

Considérese un hipercubo n-dimensional, y conéctese cada par de vértices pa llograr un grafo completu con $2^{n}$ vértices. Darréu, coloréese caúna de les arestes de negru o de colloráu. ¿Cuál ye'l menor valor de n pal cual toa manera de colorear les arestes necesariamente da llugar a un subgrafo completu d'un solu color con 4 vértices que formen un planu?

Graham y Rothschild [1971] demostraron qu'esti problema tien una solución, N*, y dieron como acotación de la mesma 6 ≤ N* ≤ N, siendo N un númberu determináu, definíu explícitamente y bien grande; sicasí, Graham (nun trabayu ensin publicar) revisó esta cota cimera a l'alza. Esta cota cimera revisada por Graham foi darréu publicada (y moteyada númberu de Graham) por Martin Gardner en [Scientific American, "Mathematical Games", payares de 1977].

La cota inferior foi darréu ameyorada por Exoo [2003], quien amosó que la solución ye siquier 11 y apurrió evidencia esperimental que suxuría que yera siquier 12. Con esto, la estimación más conocida pa la solución N* ye 11 ≤ N* ≤ G, onde G ye'l númberu de Graham.

Definición del númberu de Graham =

Por aciu la notación flecha de Knuth, el númberu de Graham, G, tal como se define nel artículu de Gardner en Scientific American, equival a:

$\left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 files}}$

onde'l númberu de fleches en cada fila, empezando pola fila cimera, vien especificáu pol valor de la fila darréu inferior, esto ye,

$G=g_{64},{\text{ onde }}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,$

onde un superíndice nuna flecha cimera indica cuántes fleches hai. N'otres pallabres, G calcúlase al traviés de 64 pasos: el primer pasu consiste en calcular g₁ con cuatro fleches ente los treses; el segundu pasu consiste en calcular g₂ con g₁ fleches ente los treses, el tercer pasu consiste en calcular g₃ con g₂ fleches ente los treses, y asina socesivamente hasta calcular finalmente G = g₆₄, que tien g₆₃ fleches ente los treses.

Equivalentemente,

$G=f^{64}(4),{\text{ onde }}f(n)=3\uparrow ^{n}3,$

onde un superíndice na f indica la iteración de la función. La función f ye un casu especial de la familia de funciones hiper(), $f(n)={\text{hiper}}(3,n+2,3)$, y tamién puede espresase por aciu la notación de fleches encadenaes de Conway como $f(n)=3\rightarrow 3\rightarrow n$. Esta última notación establez les siguientes cotes pa G:

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.\,$

Magnitú del númberu de Graham

Col fin de faer notar la dificultá d'entender la enorme magnitú del númberu de Graham, pue ser útil espresar (por aciu la mera exponenciación) namái'l primer términu (g₁) de la socesión rápido creciente de 64 términos. Primero, espresemos el númberu por aciu la tetración ($\uparrow \uparrow$):

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))$

onde'l númberu de treses na espresión de la derecha ye

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

Agora cada tetración ($\uparrow \uparrow$) amenorgar a una torre» de exponenciaciones ($\uparrow$) según la definición

$3\uparrow \uparrow X\ =\ 3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\quad {\text{onde hai X treses}}.$

Por tanto,

$g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad \mathrm {onde'l~~n{\acute {u}}mero~detreses~~ye} \,\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)$

, namái emplegando «torres d'esponentes», convertir en

$g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3\quad \mathrm {onde'l~~n{\acute {u}}mero~detorres~~ye} \quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3$

y onde el númberu de treses en cada torre, empezando pola torre asitiada más a la izquierda, vien especificáu pol valor de la torre asitiada darréu a la so derecha. Espandiendo verticalmente, esto conviértese en

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \uparrow \left(\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{3}}{\text{copies de 3}}}\right)=\left.{\begin{matrix}\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}{\text{copies de 3}}}{\text{copies de 3}}}\\\vdots \\\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{3}}{\text{copies de 3}}}{\text{copies de 3}}}{\text{copies de 3}}\end{matrix}}\right\}\left.\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{3}}{\text{copies de 3}}}\right.{\text{files}}$

La magnitú d'esti primer términu, g₁, ye tan grande que práuticamente escapa a la comprensión humana. Inclusive'l númberu de torres presentes nesta fórmula pa g₁ ye enforma mayor que'l númberu de volumes de Planck nos que podría estremase l'universu observable. Y cabo sorrayar que, dempués d'esti términu, queden otros 63 más nesta socesión rápido creciente antes de llegar al númberu de Graham, G = g₆₄.

Últimes cifres del númberu de Graham

El númberu de Graham ye una torre d'esponentes» de la forma 3$\uparrow \uparrow$n (con un valor bien grande de n), polo que les sos últimes cifres en base decimal tienen de satisfaer ciertes propiedaes comunes a cualquier torre d'esti tipu. Una d'estes propiedaes ye que toles torres d'esti tipu d'altor mayor que d presenten la mesma socesión de d cifres decimales asitiaes nos últimos llugares. Este ye un casu especial d'una propiedá más xeneral: les d últimes cifres decimales de toles torres d'esti tipu d'altor mayor que d+2 son independientes del "3" asitiáu na parte cimera de la torre, esto ye, el 3 asitiáu enriba del tou puede camudase por cualesquier otru enteru non negativu ensin afectar les d últimes cifres decimales.

La siguiente tabla ilustra, pa unos pocos valores de d, cómo asocede esto. Pa un altor dau de la torre y un númberu de cifres d, nun se presenta'l conxuntu enteru de númberos naturales de d cifres (de los qu'hai 10^d, cuntando los que tienen ceros iniciales), sinón que se presenta un subconxuntu amenorgáu de valores que se repite cíclicamente. El llargor del ciclu y dalgunos de los sos valores (ente paréntesis) amosar en caúna de les celdes de la tabla:

Númberu de valores posibles de 3$\uparrow$3$\uparrow$...3$\uparrow$x cuando s'ignoren toles cifres menos les d últimes

Númberu de cifres (d)	3$\uparrow$x	3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$x
1	4 (1,3,9,7)	2 (3,7)	1 (7)	1 (7)	1 (7)
2	20 (01,03,...,87,...,67)	4 (03,27,83,87)	2 (27,87)	1 (87)	1 (87)
3	100 (001,003,...,387,...,667)	20 (003,027,...387,...,587)	4 (027,987,227,387)	2 (987,387)	1 (387)

Les d cifres asitiaes nos últimos llugares que son comunes a toles torres abondo altes' de treses tán en negrines, y pueden verificase desenvolviendo la torre a midida que aumenta'l so altor. Pa tou númberu fixu de cifres d (representáu nes files de la tabla), el númberu de valores posibles pa 3$\uparrow$3$\uparrow$...3$\uparrow$x mod 10^d, cuando x cubre los enteros non negativos, escai progresivamente a midida que aumenta l'altor, hasta amenorgase a un solu valor (nes celdes con fondu azul) cuando l'altor ye mayor que d+2.

Puede describise un algoritmu simple pa calcular estes últimes cifres d'esta manera: sía x = 3, depués itérese d vegaes l'asignación x = 3^x mod 10^d. L'últimu valor asignáu a x (como númberu en base 10) ta compuestu poles d últimes cifres decimales de 3$\uparrow \uparrow$n, pa tou n > d. (Si l'últimu valor de x namái tien d-1 cifres, basta con añader un 0 a la izquierda.)

Siguiendo esti algoritmu, los cien últimes cifres del númberu de Graham (o de cualquier torre con más de cien veces trelce) son:

...9404248265018193851562535
7963996189939679054966380
0322234872396701848518643
9059104575627262464195387.

Temes rellacionaes

• Función de Ackermann
• Tetración
• Gúgol

Bibliografía

• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey's Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159:  páxs. 257–292. doi:10.2307/1996010. 
• Gardner, Martin (payares de 1977). «Mathematical Games». Scientific American 237:  páxs. 18–28. ; reprinted (revised 2001) in the following book:
• Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 0393020231.
• Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6.
• Exoo, Geoffrey (2003). «A Euclidean Ramsey Problem». Discrete Computational Geometry 29:  páxs. 223–227. doi:10.1007/s00454-002-0780-5. 

Enllaces esternos

N'inglés:

• "A Ramsey Problem on Hypercubes" por Geoff Exoo
• Weisstein, Eric W. «El númberu de Graham» (inglés). MathWorld. Wolfram Research.
• Cómo calcular el númberu de Graham
• Numeropedia - the Special Encyclopedia of Numbers

• Datos: Q733169