Número de Graham

El número de Graham, que recibe su nombre por el matemático Ronald Graham, es un número grande que es una cota superior de la solución de un determinado problema en la teoría de Ramsey. Este número consiguió cierta fama popular cuando Martin Gardner lo describió en la sección «Mathematical Games» (Juegos Matemáticos) de la revista Scientific American en noviembre de 1977:

En una demostración no publicada, Graham ha establecido recientemente … una cota tan vasta que tiene el registro de ser el mayor número jamás usado en una demostración matemática seria.^[1]​

El Libro Guinness de los récords, en su edición de 1980, repitió la afirmación de Gardner, lo que contribuyó al interés popular de este número. El número de Graham es mucho mayor que otros conocidos números grandes tales como el gúgol, el gúgolplex, el gúgolduplex e incluso el número de Skewes y el número de Moser. De hecho, es imposible, dadas las limitaciones de espacio y materia de nuestro universo, denotar el número de Graham o una aproximación razonable del mismo en un sistema de numeración convencional. Incluso si cada dígito ocupara una unidad de Planck (la menor unidad de medida posible), no alcanzaría todo el universo para representarlo. Ni siquiera las «torres de exponentes» de la forma ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$ se revelan útiles para este propósito, aunque el número puede ser descrito mediante fórmulas recursivas por medio de la notación flecha de Knuth o fórmulas equivalentes, como hizo Graham. Los diez últimos dígitos del número de Graham son …2464195387. Actualmente, se le considera como el número representado matemáticamente más grande de todos.

Desde el descubrimiento y uso del número de Graham, se han empleado números aún mayores en otras demostraciones matemáticas, por ejemplo, relacionadas con las variadas formas finitas de Friedman del teorema de Kruskal.

Problema de Graham

El número de Graham está relacionado con el siguiente problema perteneciente a la rama de las matemáticas conocida como la teoría de Ramsey:

Considérese un hipercubo n-dimensional, y conéctese cada par de vértices para obtener un grafo completo con ${\displaystyle 2^{n}}$  vértices. Posteriormente, coloréese cada una de las aristas de negro o de rojo. ¿Cuál es el menor valor de n para el cual toda manera de colorear las aristas necesariamente da lugar a un subgrafo completo de un solo color con 4 vértices que forman un plano?

Graham y Rothschild [1971] demostraron que este problema tiene una solución, N*, y dieron como acotación de la misma 6 ≤ N* ≤ N, siendo N un número determinado, definido explícitamente y muy grande; sin embargo, Graham (en un trabajo no publicado) revisó esta cota superior al alza. Esta cota superior revisada por Graham fue posteriormente publicada (y apodada número de Graham) por Martin Gardner en [Scientific American, "Mathematical Games", noviembre de 1977].

La cota inferior fue posteriormente mejorada por Exoo [2003], quien mostró que la solución es al menos 11 y proporcionó evidencia experimental que sugería que era al menos 12. Con esto, la estimación más conocida para la solución N* es 11 ≤ N* ≤ G, donde G es el número de Graham.

Definición del número de Graham

Mediante la notación flecha de Knuth, el número de Graham, G, tal como se define en el artículo de Gardner en Scientific American, equivale a:

${\displaystyle \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 filas}}}$ 

donde el número de flechas en cada fila, empezando por la fila superior, viene especificado por el valor de la fila inmediatamente inferior, es decir,

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

donde un superíndice en una flecha superior indica cuántas flechas hay. En otras palabras, G se calcula a través de 64 pasos: el primer paso consiste en calcular g₁ con cuatro flechas entre los treses; el segundo paso consiste en calcular g₂ con g₁ flechas entre los treses, el tercer paso consiste en calcular g₃ con g₂ flechas entre los treses, y así sucesivamente hasta calcular finalmente G = g₆₄, que tiene g₆₃ flechas entre los treses.

Equivalentemente,

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

donde un superíndice en la f indica la iteración de la función. La función f es un caso especial de la familia de funciones hiper(), ${\displaystyle f(n)={\text{hiper}}(3,n+2,3)}$ , y también se puede expresar mediante la notación de flechas encadenadas de Conway como ${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$ . Esta última notación establece las siguientes cotas para G:

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.\,}$ 

Magnitud del número de Graham

Con el fin de hacer notar la dificultad de comprender la enorme magnitud del número de Graham, puede ser útil expresar (mediante la mera exponenciación) únicamente el primer término (g₁) de la sucesión rápidamente creciente de 64 términos. Primero, expresemos el número mediante la tetración (${\displaystyle \uparrow \uparrow }$ ):

${\displaystyle 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 ))}$ 

donde el número de treses en la expresión de la derecha es

${\displaystyle 3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3).}$ 

Ahora cada tetración (${\displaystyle \uparrow \uparrow }$ ) se reduce a una «torre» de exponenciaciones (${\displaystyle \uparrow }$ ) según la definición

${\displaystyle 3\uparrow \uparrow X\ =\ 3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\quad {\text{donde hay X treses}}.}$ 

Por tanto,

${\displaystyle g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad \mathrm {donde~el~n{\acute {u}}mero~de~treses~es} \,\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)}$ 

, únicamente empleando «torres de exponentes», se convierte en

${\displaystyle 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 {donde~el~n{\acute {u}}mero~de~torres~es} \quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3}$ 

y donde el número de treses en cada torre, empezando por la torre situada más a la izquierda, viene especificado por el valor de la torre situada inmediatamente a su derecha. Expandiendo verticalmente, esto se convierte en

${\displaystyle 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{copias 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{copias de 3}}}{\text{copias de 3}}}\\\vdots \\\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{3}}{\text{copias de 3}}}{\text{copias de 3}}}{\text{copias de 3}}\end{matrix}}\right\}\left.\underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{3^{3^{3}}{\text{copias de 3}}}\right.{\text{filas}}}$ 

La magnitud de este primer término, g₁, es tan grande que prácticamente escapa a la comprensión humana. Incluso el número de torres presentes en esta fórmula para g₁ es mucho mayor que el número de volúmenes de Planck en los que se podría dividir el universo observable. Y cabe subrayar que, después de este término, quedan otros 63 más en esta sucesión rápidamente creciente antes de llegar al número de Graham, G = g₆₄.

Últimas cifras del número de Graham

El número de Graham es una «torre de exponentes» de la forma 3${\displaystyle \uparrow \uparrow }$ n (con un valor muy grande de n), por lo que sus últimas cifras en base decimal deben satisfacer ciertas propiedades comunes a cualquier torre de este tipo. Una de estas propiedades es que todas las torres de este tipo de altura mayor que 'd' presentan la misma sucesión de 'd' cifras decimales situadas en los últimos lugares. Este es un caso especial de una propiedad más general: las d últimas cifras decimales de todas las torres de este tipo de altura mayor que d+2 son independientes del "3" situado en la parte superior de la torre, es decir, el 3 situado arriba del todo se puede cambiar por cualquier otro entero no negativo sin afectar las d últimas cifras decimales.

La siguiente tabla ilustra, para unos pocos valores de d, cómo ocurre esto. Para una altura dada de la torre y un número de cifras d, no se presenta el conjunto entero de números naturales de d cifras (de los que hay 10^d, contando los que tienen ceros iniciales), sino que se presenta un subconjunto reducido de valores que se repite cíclicamente. La longitud del ciclo y algunos de sus valores (entre paréntesis) se muestran en cada una de las celdas de la tabla:

Número de valores posibles de 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ ...3${\displaystyle \uparrow }$ x cuando se ignoran todas las cifras menos las d últimas

Número de cifras (d)	3${\displaystyle \uparrow }$ x	3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ x	3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ x	3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ x	3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ 3${\displaystyle \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)

Las d cifras situadas en los últimos lugares que son comunes a todas las torres suficientemente altas' de treses están en negritas, y se pueden verificar desarrollando la torre a medida que aumenta su altura. Para todo número fijo de cifras d (representado en las filas de la tabla), el número de valores posibles para 3${\displaystyle \uparrow }$ 3${\displaystyle \uparrow }$ ...3${\displaystyle \uparrow }$ x mod 10^d, cuando x cubre los enteros no negativos, decrece progresivamente a medida que aumenta la altura, hasta reducirse a un solo valor (en las celdas con fondo azul) cuando la altura es mayor que d+2.

Se puede describir un algoritmo simple^[2]​ para calcular estas últimas cifras de esta manera: sea x = 3, luego itérese d veces la asignación x = 3^x mod 10^d. El último valor asignado a x (como número en base 10) está compuesto por las d últimas cifras decimales de 3${\displaystyle \uparrow \uparrow }$ n, para todo n > d. (Si el último valor de x solo tiene d-1 cifras, basta con añadir un 0 a la izquierda.)

Siguiendo este algoritmo, las cien últimas cifras del número de Graham (o de cualquier torre con más de cien veces tres) son:

...9404248265018193851562535 7963996189939679054966380 0322234872396701848518643 9059104575627262464195387. 

Temas relacionados

• función de Ackermann
• gúgol
• tetración

Referencias

1. En inglés en el original: In an unpublished proof, Graham has recently established … a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.
2. The Math Forum @ Drexel ("Last Eight Digits of Z")

Bibliografía

• Graham, R. L.; Rothschild, B. L. (1971). «Ramsey's Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159: 257-292. doi:10.2307/1996010. 
• Gardner, Martin (noviembre de 1977). «Mathematical Games». Scientific American 237: 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: 223-227. doi:10.1007/s00454-002-0780-5. 

Enlaces externos

En inglés:

• "A Ramsey Problem on Hypercubes", por Geoff Exoo
• Weisstein, Eric W. «El número de Graham». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Cómo calcular el número de Graham

•   Datos: Q733169