El número de Graham

El número de Graham es un número inmenso que surgió como una cota superior para la respuesta a un problema en el campo matemático de la teoría de Ramsey . Es mucho mayor que muchos otros números grandes introducidos como cotas efectivas en matemáticas, como la cota de Skewes , que a su vez es mucho mayor que un googolplex . El número de Graham es tan grande que el universo observable es demasiado pequeño para contener su representación digital ordinaria , suponiendo que cada dígito ocupa un volumen de Planck . Pero incluso el número de dígitos en esta representación digital del número de Graham sería en sí mismo un número tan grande que su representación digital no puede representarse en el universo observable. Ni siquiera el número de dígitos de ese número, y así sucesivamente, para un número de veces que excede con creces el número total de volúmenes de Planck en el universo observable. Por lo tanto, el número de Graham no puede expresarse ni siquiera mediante torres de potencia a escala del universo físico de la forma${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$, aunque el número de Graham es, en efecto, una potencia de tres .

Sin embargo, el número de Graham se puede dar explícitamente mediante fórmulas recursivas computables utilizando la notación de flecha hacia arriba de Knuth o equivalente, como lo hizo Ronald Graham , quien da nombre al número. Como existe una fórmula recursiva para definirlo, es mucho más pequeño que los números típicos de "busy beaver" , cuya secuencia crece más rápido que cualquier secuencia computable. Aunque demasiado grande para ser calculado por completo, la secuencia de dígitos del número de Graham se puede calcular explícitamente mediante algoritmos simples; los últimos 10 dígitos del número de Graham son ...2464195387. ^{[ 1 ]} Usando la notación de flecha hacia arriba de Knuth, el número de Graham es${\displaystyle g_{64}}$, ^{[ 2 ]} donde $${\displaystyle g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{si }}n=1{\text{ y}}\\3\uparrow ^{g_{n-1}}3,&{\text{si }}n\geq 2.\end{cases}}}$$

Graham utilizó el número de Graham en conversaciones con el divulgador científico Martin Gardner como una explicación simplificada de los límites superiores del problema en el que trabajaba. En 1977, Gardner lo describió en Scientific American , dándolo a conocer al público general. En el momento de su publicación, era el entero positivo más grande jamás utilizado en una demostración matemática publicada. El número fue descrito en el Libro Guinness de los Récords de 1980 , lo que aumentó su popularidad. Otros enteros específicos (como TREE(3) ), conocidos por ser mucho mayores que el número de Graham, han aparecido desde entonces en numerosas demostraciones matemáticas rigurosas, por ejemplo, en relación con las diversas formas finitas del teorema de Kruskal de Harvey Friedman . Además, se ha demostrado la validez de límites superiores más pequeños en el problema de la teoría de Ramsey del que se derivó el número de Graham.

El número de Graham está relacionado con el siguiente problema en la teoría de Ramsey :

Conecta cada par de vértices geométricos de un hipercubo n -dimensional para obtener un grafo completo de 2n ^vértices . Colorea cada una de las aristas de este grafo de rojo o azul. ¿Cuál es el valor mínimo de n para el cual cada coloración contiene al menos un subgrafo completo de un solo color con cuatro vértices coplanares ?

En 1971, Graham y Rothschild demostraron el teorema de Graham-Rothschild sobre la teoría de Ramsey de palabras de parámetros , un caso especial del cual muestra que este problema tiene una solución N* . Acotaron el valor de N* por 6 ≤ N* ≤ N , donde N es un número grande pero definido explícitamente.

$${\displaystyle N=F^{7}(12)=F(F(F(F(F(F(F(12))))))),}$$

dónde${\displaystyle F(n)=2\uparrow ^{n}3}$en la notación de flecha hacia arriba de Knuth ; el número está entre 4 → 2 → 8 → 2 y 2 → 3 → 9 → 2 en la notación de flecha encadenada de Conway . ^{[ 3 ]} Esto se redujo en 2014 mediante límites superiores en el número de Hales-Jewett a

$${\displaystyle N'=2\uparrow \uparrow (2\uparrow \uparrow (3+2\uparrow \uparrow 8)),}$$

que contiene tres tetraciones . ^{[ 4 ]} En 2019 esto se mejoró aún más a ^{[ 5 ]}

$${\displaystyle N''=(2\uparrow \uparrow 5138)\cdot ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\cdot 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow (2\uparrow \uparrow 5138).}$$

El límite inferior de 6 fue mejorado posteriormente a 11 por Geoffrey Exoo en 2003, ^{[ 6 ]} y a 13 por Jerome Barkley en 2008. ^{[ 7 ]} Por lo tanto, los mejores límites conocidos para N* son 13 ≤ N* ≤ N'' .

El número de Graham, G , es mucho mayor que N : es${\displaystyle f^{64}(4)}$, dónde${\displaystyle f(n)=3\uparrow ^{n}3}$. Este límite superior más débil para el problema, atribuido a un trabajo inédito de Graham, fue finalmente publicado y nombrado por Martin Gardner en Scientific American en noviembre de 1977. ^{[ 8 ]}

El número cobró cierta notoriedad cuando Martin Gardner lo describió en la sección "Juegos Matemáticos" de Scientific American en noviembre de 1977, escribiendo que Graham había establecido recientemente, en una demostración inédita, "un límite tan vasto que ostenta el récord del número más grande jamás utilizado en una demostración matemática seria". El Libro Guinness de los Récords de 1980 repitió la afirmación de Gardner, lo que aumentó el interés popular en este número. Según el físico John Baez , Graham inventó la cantidad ahora conocida como el número de Graham en una conversación con Gardner. Mientras Graham intentaba explicar un resultado de la teoría de Ramsey que había derivado con su colaborador Bruce Lee Rothschild , descubrió que dicha cantidad era más fácil de explicar que el número real que aparecía en la demostración. Dado que el número que Graham describió a Gardner es mayor que el número del propio artículo, ambos son límites superiores válidos para la solución del problema estudiado por Graham y Rothschild. ^{[ 9 ]}

Utilizando la notación de flecha hacia arriba de Knuth , el número G de Graham (tal como se define en el artículo de Gardner en Scientific American ) es $${\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 \quad \vdots \qquad \quad } \\&&3\underbrace {\uparrow \uparrow \cdots \cdots \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 layers}}}$$

donde el número de flechas en cada capa se especifica mediante el valor de la siguiente capa debajo de ella; es decir,

$${\displaystyle G=g_{64},}$$dónde${\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,}$${\displaystyle g_{n}=3\uparrow ^{g_{n-1}}3,}$

y donde un superíndice en una flecha hacia arriba indica cuántas flechas hay. En otras palabras, G se calcula en 64 pasos: el primer paso es calcular g ₁ con cuatro flechas hacia arriba entre 3; el segundo paso es calcular g ₂ con g ₁ flechas hacia arriba entre 3; el tercer paso es calcular g ₃ con g ₂ flechas hacia arriba entre 3; y así sucesivamente, hasta finalmente calcular G = g ₆₄ con g ₆₃ flechas hacia arriba entre 3.

De forma equivalente, $${\displaystyle G=f^{64}(4),{\text{ where }}f(n)=3\uparrow ^{n}3,}$$

y el superíndice en f indica una iteración de la función , por ejemplo,${\displaystyle f^{4}(n)=f(f(f(f(n))))}$Expresado en términos de la familia de hiperoperaciones${\displaystyle {\text{H}}_{0},{\text{H}}_{1},{\text{H}}_{2},\cdots }$, la función f es la secuencia particular${\displaystyle f(n)={\text{H}}_{n+2}(3,3)}$, que es una versión de la función de Ackermann de rápido crecimiento A ( n , n ). (De hecho,${\displaystyle f(n)>A(n,n)}$para todo n .) La función f también se puede expresar en notación de flechas encadenadas de Conway como${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$y esta notación también proporciona los siguientes límites para G :

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

El residuo del número de Graham módulo n , comenzando con n = 1, es

• Secuencia OEIS A133613 (número de Graham)
• Artículo de Sbiis Saibian sobre el número de Graham. Archivado el 17 de enero de 2023 en la Wayback Machine.
• " Un problema de Ramsey sobre hipercubos " por Geoff Exoo
• Weisstein, Eric W. "El número de Graham" . MathWorld .
• Cómo calcular el número de Graham
• Urban, Tim. "De 1.000.000 al número de Graham" . Wait But Why . Recuperado el 24 de abril de 2026 .
• Algunos resultados de Ramsey para la prepublicación del n-cubo mencionan el número de Graham
• Padilla, Tony ; Parker, Matt . "El número de Graham" . Numberphile . Brady Haran . Archivado del original el 27 de mayo de 2014. Recuperado el 8 de abril de 2013 .
• Archivado en Ghostarchivey la Wayback Machine: Ron Graham (21 de julio de 2014). "¿Cuál es el número de Graham? (con Ron Graham)" (vídeo) . Numberphile . Brady Haran .
• Archivado en Ghostarchivey la Wayback Machine: Ron Graham (22 de julio de 2014). "¿Qué tan grande es el número de Graham? (con Ron Graham)" (video) . Numberphile . Brady Haran .
• Los últimos 16 millones de dígitos del número de Graham por el grupo de comunicación Darkside