El número de Graham

Gran número acuñado por Ronald Graham

El número de Graham es un número inmenso que surgió como límite superior de 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, como el número de Skewes y el número de Moser , que a su vez son mucho mayores que un googolplex . Al igual que estos, es tan grande que el universo observable es demasiado pequeño para contener una representación digital ordinaria del número de Graham, suponiendo que cada dígito ocupa un volumen de Planck , posiblemente el espacio medible más pequeño. 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 puede representarse el número de dígitos de ese número, y así sucesivamente, durante 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 energía a escala del universo físico de la forma , aunque el número de Graham es de hecho una potencia de 3 . ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$

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 , el homónimo del número. Como hay una fórmula recursiva para definirlo, es mucho más pequeño que los números de castor atareado típicos , los últimos de los cuales crecen más rápido que cualquier secuencia computable. Aunque demasiado grande para ser calculada en su totalidad, la secuencia de dígitos del número de Graham se puede calcular explícitamente mediante algoritmos simples; los últimos 13 dígitos son ...7262464195387. Usando la notación de flecha hacia arriba de Knuth , el número de Graham es , ^[1] donde ${\displaystyle g_{64}}$ $${\displaystyle g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}}$$

El número de Graham fue utilizado por Graham en conversaciones con el escritor de divulgación científica Martin Gardner como una explicación simplificada de los límites superiores del problema en el que estaba trabajando. En 1977, Gardner describió el número en Scientific American , presentándolo al público en general. En el momento de su introducción, era el entero positivo específico más grande que se haya utilizado jamás en una prueba matemática publicada. El número fue descrito en el Libro Guinness de los récords mundiales de 1980 , lo que aumentó su interés popular. Otros enteros específicos (como TREE(3) ) que se sabe que son mucho más grandes que el número de Graham han aparecido desde entonces en muchas pruebas matemáticas serias, por ejemplo en relación con las diversas formas finitas del teorema de Kruskal de Harvey Friedman . Además, desde entonces se ha demostrado que los 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 son válidos.

Contexto

Ejemplo de un cubo tridimensional de dos colores que contiene un subgrafo completo coplanar de cuatro vértices de un solo color. El subgrafo se muestra debajo del cubo. Este cubo no contendría dicho subgrafo si, por ejemplo, el borde inferior del subgrafo actual se reemplazara por un borde azul, lo que demuestra mediante un contraejemplo que N * > 3.

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

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

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

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

donde 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 . ^[2] Esto se redujo en 2014 a través de límites superiores en el número de Hales-Jewett a ${\displaystyle F(n)=2\uparrow ^{n}3}$

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

que contiene tres tetraciones . ^[3] En 2019, esto se mejoró aún más a: ^[4]

${\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, ^[5] y a 13 por Jerome Barkley en 2008. ^[6] Por lo tanto, los límites más conocidos para N* son 13 ≤ N* ≤ N'' .

El número de Graham, G , es mucho mayor que N : es , donde . 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. ^[7] ${\displaystyle f^{64}(4)}$ ${\displaystyle f(n)=3\uparrow ^{n}3}$

Publicación

El número ganó un grado de atención popular 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 prueba inédita, "un límite tan amplio que ostenta el récord del número más grande jamás utilizado en una prueba matemática seria". El Libro Guinness de los récords mundiales 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 en la teoría de Ramsey que había derivado con su colaborador Bruce Lee Rothschild , Graham descubrió que dicha cantidad era más fácil de explicar que el número real que aparecía en la prueba. Debido a que el número que Graham describió a Gardner es mayor que el número en el artículo en sí, ambos son límites superiores válidos para la solución del problema estudiado por Graham y Rothschild. ^[8]

Definición

Usando la notación de flecha hacia arriba de Knuth , el número de Graham G (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 por 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 sobre 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 s; el segundo paso es calcular g ₂ con g ₁ flechas hacia arriba entre 3 s; el tercer paso es calcular g ₃ con g ₂ flechas hacia arriba entre 3 s; y así sucesivamente, hasta calcular finalmente G = g ₆₄ con g ₆₃ flechas hacia arriba entre 3 s.

De manera 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 , p. ej. , . Expresada en términos de la familia de hiperoperaciones , la función f es la secuencia particular , que es una versión de la función de Ackermann de rápido crecimiento A ( n , n ). (De hecho, para todo n ). La función f también se puede expresar en notación de flecha encadenada de Conway como , y esta notación también proporciona los siguientes límites en G : ${\displaystyle f^{4}(n)=f(f(f(f(n))))}$ ${\displaystyle {\text{H}}_{0},{\text{H}}_{1},{\text{H}}_{2},\cdots }$ ${\displaystyle f(n)={\text{H}}_{n+2}(3,3)}$ ${\displaystyle f(n)>A(n,n)}$ ${\displaystyle f(n)=3\rightarrow 3\rightarrow n}$

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

Magnitud

Para transmitir la dificultad de apreciar el enorme tamaño del número de Graham, puede ser útil expresar, en términos de exponenciación únicamente, sólo el primer término ( g ₁ ) de la secuencia de 64 términos que crece rápidamente. Primero, en términos de tetración ( ) únicamente: ${\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 3 en la expresión de la derecha es $${\displaystyle 3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3).}$$

Ahora cada operación de tetración ( ) se reduce a una torre de potencia ( ) según la definición donde hay X 3. ${\displaystyle \uparrow \uparrow }$ ${\displaystyle \uparrow }$ $${\displaystyle 3\uparrow \uparrow X=3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))=3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}$$

De este modo, $${\displaystyle g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{where the number of 3s is}}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)}$$

se convierte, únicamente en términos de repetidas "torres de exponenciación", $${\displaystyle g_{1}=\underbrace {\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} _{\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 3 en cada torre, comenzando desde la torre más a la izquierda, está especificado por el valor de la siguiente torre a la derecha.

En otras palabras, g ₁ se calcula calculando primero el número de torres (donde el número de 3 es ), y luego calculando la n- ^ésima torre en la siguiente secuencia: ${\displaystyle n=3\uparrow (3\uparrow (3\ \dots \ \uparrow 3))}$ ${\displaystyle 3\uparrow (3\uparrow 3)=7625597484987}$

 1ª torre: 3  2da torre: 3↑3↑3 (el número de 3 es 3 ) = 7625597484987  3.ª torre: 3↑3↑3↑3↑...↑3 (el número de 3 es 7625597484987 ) = …  ⋮  g 1 = n ésima torre: 3↑3↑3↑3↑3↑3↑3↑...↑3 (el número de 3 viene dado por la n − 1 ésima torre )

donde el número de 3 en cada torre sucesiva viene dado por la torre inmediatamente anterior. El resultado de calcular la tercera torre es el valor de n , el número de torres para g ₁ .

La magnitud de este primer término, g ₁ , es tan grande que es prácticamente incomprensible, aunque la representación anterior es relativamente fácil de comprender. Incluso n , el mero número de torres en esta fórmula para g ₁ , es mucho mayor que el número de volúmenes de Planck (aproximadamente 10 ¹⁸⁵ de ellos) en los que uno puede imaginar subdividir el universo observable . Y después de este primer término, todavía quedan otros 63 términos en la secuencia g de rápido crecimiento antes de que se alcance el número de Graham G = g _64. Para ilustrar cuán rápido crece esta secuencia, mientras que g ₁ es igual a con solo cuatro flechas hacia arriba, el número de flechas hacia arriba en g ₂ es este número incomprensiblemente grande g ₁ . ${\displaystyle 3\uparrow \uparrow \uparrow \uparrow 3}$

Referencias

1. "El número de Graham".
2. "Registros numéricos de Graham". Iteror.org. Archivado desde el original el 19 de octubre de 2013. Consultado el 9 de abril de 2014 .
3. Lavrov, Mikhail; Lee, Mitchell; Mackey, John (2014). "Límites superiores e inferiores mejorados en un problema geométrico de Ramsey". Revista Europea de Combinatoria . 42 : 135–144. doi : 10.1016/j.ejc.2014.06.003 .
4. Lipka, Eryk (2019). "Mejora adicional del límite superior en un problema geométrico de Ramsey". arXiv : 1905.05617 [math.CO].
5. Exoo, Geoffrey (2003). "Un problema euclidiano de Ramsey". Geometría discreta y computacional . 29 (2): 223–227. doi : 10.1007/s00454-002-0780-5 .Exoo hace referencia al límite superior N de Graham & Rothschild mediante el término "número de Graham". Este no es el "número de Graham" G publicado por Martin Gardner.
6. Barkley, Jerome (2008). "Límite inferior mejorado en un problema euclidiano de Ramsey". arXiv : 0811.1055 [math.CO].
7. Martin Gardner (1977). «En el que la unión de conjuntos de puntos conduce a caminos diversos (y divergentes)». Scientific American (noviembre). Archivado desde el original el 19 de octubre de 2013.
8. John Baez (2013). "Hace un tiempo les hablé del número de Graham..." Archivado desde el original el 13 de noviembre de 2013. Consultado el 11 de enero de 2013 .

Bibliografía

• Gardner, Martin (noviembre de 1977). "Juegos matemáticos" (PDF) . Scientific American . 237 (5): 18–28. Bibcode :1977SciAm.237e..18G. doi :10.1038/scientificamerican1177-18.; reimpreso (revisado) en Gardner (2001), citado a continuación.
• Gardner, Martin (1989). De los mosaicos de Penrose a los cifrados de trampilla . Washington, DC: Asociación Matemática de Estados Unidos. ISBN 978-0-88385-521-8.
• Gardner, Martin (2001). El libro colosal de las matemáticas: acertijos, paradojas y problemas clásicos . Nueva York, NY: Norton. ISBN 978-0-393-02023-6.
• Graham, RL; Rothschild, BL (1971). "Teorema de Ramsey para conjuntos de n parámetros" (PDF) . Transactions of the American Mathematical Society . 159 : 257–292. doi :10.2307/1996010. JSTOR  1996010.La fórmula explícita para N aparece en la página 290. Éste no es el "número de Graham" G publicado por Martin Gardner.
• Graham, RL; Rothschild, BL (1978). "Teoría de Ramsey". En Rota, GC (ed.). Estudios en combinatoria (MAA Studies in Mathematics) . Vol. 17. Asociación Matemática de Estados Unidos. págs. 80–99. ISBN. 978-0-88385-117-3.En la página 90, al afirmar "la mejor estimación disponible" para la solución, se repite la fórmula explícita para N del artículo de 1971.

Enlaces externos

• Secuencia OEIS A133613 (número de Graham)
• Artículo de Sbiis Saibian sobre el número de Graham
• "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
• Conceptualizando el número de Graham
• 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 desde el original el 2014-05-27 . Consultado el 2013-04-08 .
• Archivado en Ghostarchive y Wayback Machine: Ron Graham (21 de julio de 2014). "What is Graham's Number? (feat Ron Graham)" (video) . Numberphile . Brady Haran .
• Archivado en Ghostarchive y Wayback Machine: Ron Graham (22 de julio de 2014). "How Big is Graham's Number? (feat 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