Número de Graham

El número de Graham, que recibe su nombre de 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:

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

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.

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:

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,

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,

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)={ ext{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 ightarrow 3 ightarrow n}$. Esta última notación establece las siguientes cotas para G:

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

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 }$):

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

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

Por tanto,

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

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

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₆₄.

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:

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:

En inglés: