El número de Graham.

Inmenso número propuesto por Ronald Graham

El número de Graham es un número grande que surgió como límite superior en la respuesta de un problema en el campo matemático de la teoría de Ramsey . Es mucho más grande que muchos otros números grandes, como el número de Skewes y el número de Moser , los cuales a su vez son mucho más grandes 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 ocupe un volumen de Planck , posiblemente el espacio mensurable 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 hacerlo el número de dígitos de ese número, y así sucesivamente, 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 físicas a escala universal de la forma . ${\displaystyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}$

Sin embargo, el número de Graham puede darse explícitamente mediante fórmulas recursivas computables utilizando la notación de flecha hacia arriba de Knuth o su equivalente, como lo hizo Ronald Graham , el homónimo del número. Como existe una fórmula recursiva para definirlo, es mucho más pequeño que los números típicos de los castores ocupados . Aunque es demasiado grande para poder calcularse 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}=\left\{{\begin{matrix}3\uparrow \uparrow \uparrow \uparrow 3,&n=1\\3\uparrow ^{g_{n-1}}3,&n\geq 2,n\in \mathbb {N} \end{matrix}}\right.}$$

Graham utilizó el número de 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 y lo presentó al público en general. En el momento de su introducción, era el entero positivo específico más grande jamás utilizado 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 números enteros específicos (como TREE(3) ) que se sabe que son mucho mayores que el número de Graham han aparecido desde entonces en muchas demostraciones 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 son válidos los límites superiores más pequeños del problema de la teoría de Ramsey del que se derivó el número de Graham.

Contexto

Ejemplo de un cubo tridimensional de 2 colores que contiene un subgrafo completo coplanar de 4 vértices de un solo color. El subgrafo se muestra debajo del cubo. Tenga en cuenta que este cubo no contendría tal subgrafo si, por ejemplo, el borde inferior del presente subgrafo fuera reemplazado por un borde azul, demostrando así con un contraejemplo que N * > 3.

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

Conecte cada par de vértices geométricos de un hipercubo de n dimensiones para obtener un gráfico completo en 2 ⁿ vértices . Colorea cada uno de los bordes de este gráfico de 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 , cuyo caso especial 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 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 notación de flecha encadenada de Conway . ^[2] Esto se redujo en 2014 mediante 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 :, donde . Este límite superior más débil del 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ó cierto 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 vasto que ostenta el récord de el 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, aumentando el interés popular en este número. Según el físico John Baez , Graham inventó la cantidad ahora conocida como 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 obtenido con su colaborador Bruce Lee Rothschild , Graham descubrió que dicha cantidad era más fácil de explicar que el número real que aparece en la prueba. Debido a que el número que Graham describió a Gardner es mayor que el número en el artículo mismo, 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 G de Graham (como se define en el artículo de Scientific American de Gardner ) 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; eso es,

$${\displaystyle G=g_{64},}$$

${\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 3s.

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 , por ejemplo ,. 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 flechas encadenadas 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 resultar útil expresar (solo en términos de exponenciación) sólo el primer término ( g ₁ ) de la secuencia de 64 términos en rápido crecimiento. 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 energía ( ) según la definición ${\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}}}}}}$$

X

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 enésima ^torre en la siguiente secuencia: ${\displaystyle n=3\uparrow (3\uparrow (3\ \dots \ \uparrow 3))}$ ${\displaystyle 3\uparrow (3\uparrow 3)=7625597484987}$

 1ra 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 (el número de 3 viene dado por la n − 1 ª torre )

donde el número de 3 en cada torre sucesiva lo da la torre justo antes. Tenga en cuenta que 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.185 ^de ellos) en los que uno puede imaginarse subdividiendo el universo observable . Y después de este primer término, aún quedan otros 63 términos en la secuencia g que crece rápidamente antes de que se alcance el número de Graham G = g ₆₄ . Para ilustrar qué tan 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}$

Dígitos decimales más a la derecha

El número de Graham, , es una "torre de energía" de la forma (con un valor extremadamente grande de ), por lo que sus dígitos decimales más a la derecha son dígitos estables (para una prueba, consulte el Lema 1 de la referencia ^[9] ), y por lo tanto son los lo mismo de los dígitos más a la derecha del punto fijo -adic de . Esto se deriva de una propiedad peculiar de la tetración que se llama "la constancia de la velocidad de congruencia" ^[10] de modo que todas esas torres de altura mayor que (digamos) se caracterizan por la misma secuencia de dígitos decimales situados más a la derecha (es decir, tienen una altura exactamente estable) . dígitos desde , pero no es módulo congruente con ). ${\displaystyle G}$ ${\displaystyle 3\uparrow \uparrow n}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n-1}$ ${\displaystyle 10}$ ${\displaystyle x\mapsto 3^{x}}$ ${\displaystyle d:d>1}$ ${\displaystyle d-2}$ ${\displaystyle 2\uparrow \uparrow 5}$ ${\displaystyle 3}$ ${\displaystyle 2\uparrow \uparrow 5\equiv 2\uparrow \uparrow 6{\pmod {10^{3}}}}$ ${\displaystyle 2\uparrow \uparrow 5}$ ${\displaystyle 10^{4}}$ ${\displaystyle 2\uparrow \uparrow 6}$

Este es un caso especial de la propiedad general antes mencionada. ^[11]

La siguiente tabla ilustra, para algunos valores de , cómo sucede esto. Para una altura de torre y un número de dígitos determinados , no se produce el rango completo de números de dígitos ( de ellos) ; en cambio, un cierto subconjunto más pequeño de valores se repite en un ciclo. La duración del ciclo y algunos de los valores (entre paréntesis) se muestran en cada celda de esta tabla: ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle 10^{d}}$

Los dígitos particulares situados más a la derecha que, en última instancia, comparten todas las torres de s suficientemente altas están en negrita y se pueden ver desarrollándose a medida que aumenta la altura de la torre. Para cualquier número fijo de dígitos (fila de la tabla), se ve que el número de valores posibles para , que abarca todos los números enteros no negativos, disminuye constantemente a medida que aumenta la altura, hasta reducir finalmente el "conjunto de posibilidades" a un solo número ( celdas coloreadas) cuando la altura excede . ${\displaystyle d}$ ${\displaystyle 3}$ ${\displaystyle d}$ ${\displaystyle 3\uparrow 3\uparrow \cdots \uparrow x{\pmod {10}}^{d}}$ ${\displaystyle x}$ ${\displaystyle d+2}$

Un algoritmo simple ^[12] para calcular estos dígitos se puede describir de la siguiente manera: hagamos , luego itemos, multiplicamos, la asignación . Excepto por omitir cualquier s inicial, el valor final asignado a (como un número de base diez) se compone de los dígitos decimales más a la derecha de , para todos . (Si el valor final de tiene menos de dígitos, entonces se debe agregar el número requerido de s iniciales). ${\displaystyle x=3}$ ${\displaystyle d}$ ${\displaystyle x=3^{x}{\pmod {10}}^{d}}$ ${\displaystyle 0}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle 3\uparrow \uparrow n}$ ${\displaystyle n>d}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle 0}$

La numerosidad de estos dígitos estables es desde , que satisfacen la relación de congruencia ${\displaystyle b-1}$ ${\displaystyle G:=3\uparrow \uparrow b}$

$${\displaystyle G{\pmod {10}}^{b-1}\equiv G^{G}{\pmod {10}}^{b-1}}$$

^[13] ${\displaystyle G{\pmod {10}}^{b}}$ ${\displaystyle 10^{b}}$ ${\displaystyle G^{G}}$ ${\displaystyle g_{63}<<k<<g_{64}}$

El algoritmo anterior produce los siguientes dígitos decimales situados más a la derecha del número de Graham ( OEIS : A133613 ): ${\displaystyle 500}$

...02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780 38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387

$${\displaystyle \left.{\begin{matrix}g_{n}&=&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\}n\ \mathrm {layers} =...02425950695064738395657479136519351798334535362521430035401260267716226721604198106522631693551887803881448314065252616878509555264605107117200099709291249544378887496062882911725063001303622934916080254594614945788714278323508292421020918258967535604308699380168924988926809951016905591995119502788717830837018340236474548882222161573228010132974509273445945043433009010969280253527518332898844615089404248265018193851562535796399618993967905496638003222348723967018485186439059104575627262464195387}$$

Referencias

1. https://mathworld.wolfram.com/GrahamsNumber.html
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, Mijaíl; Lee, Mitchell; Mackey, John (2014). "Límites superior e inferior 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 de un problema geométrico de Ramsey". arXiv : 1905.05617 [matemáticas.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 se refiere al límite superior N de Graham & Rothschild con 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 [matemáticas.CO].
7. Martín Gardner (1977). "En el que unir conjuntos de puntos conduce a caminos diversos (y desviados)". Científico americano (noviembre). Archivado desde el original el 19 de octubre de 2013.
8. John Báez (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 .
9. Ripà, M. (agosto de 2020). "Sobre la velocidad de congruencia constante de la tetración". Apuntes sobre teoría de números y matemáticas discretas . 26 (3): 245–260. doi : 10.7546/nntdm.2020.26.3.245-260 .
10. Ripà, M. (noviembre de 2021). "La fórmula de la velocidad de congruencia". Apuntes sobre teoría de números y matemáticas discretas . 27 (4): 43–61. arXiv : 2208.02622 . doi :10.7546/nntdm.2021.27.4.43-61.
11. Ripá, M.; Onnis, L. (julio de 2022). "Número de dígitos estables de cualquier tetración de números enteros". Apuntes sobre teoría de números y matemáticas discretas . 28 (3): 441–457. arXiv : 2210.07956 . doi :10.7546/nntdm.2022.28.3.441-457.
12. "The Math Forum @ Drexel ("Últimos ocho dígitos de Z")". Mathforum.org . Consultado el 9 de abril de 2014 .
13. Ripá, Marco (2011). La strana coda della serie n^n^...^n (en italiano). Servicio UNI. ISBN 978-88-6178-789-6.

Bibliografía

• Gardner, Martín (noviembre de 1977). «Juegos Matemáticos» (PDF) . Científico americano . 237 (5): 18–28. Código bibliográfico : 1977SciAm.237e..18G. doi : 10.1038/scientificamerican1177-18.; reimpreso (revisado) en Gardner (2001), citado a continuación.
• Gardner, Martín (1989). "Penrose Tiles hasta cifrados de trampilla" . Washington, DC: Asociación Matemática de América. ISBN 978-0-88385-521-8.
• Gardner, Martín (2001). El colosal libro de las matemáticas: acertijos, paradojas y problemas clásicos . Nueva York, Nueva York: Norton. ISBN 978-0-393-02023-6.
• Graham, RL; Rothschild, BL (1971). "Teorema de Ramsey para conjuntos de n parámetros" (PDF) . Transacciones de la Sociedad Matemática Estadounidense . 159 : 257–292. doi :10.2307/1996010. JSTOR  1996010.La fórmula explícita para N aparece en la p. 290. Este 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 (Estudios MAA en Matemáticas) . vol. 17. Asociación Matemática de América. págs. 80–99. ISBN 978-0-88385-117-3.En P. 90, al indicar "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 los hipercubos" por Geoff Exoo
• Weisstein, Eric W. "El número de Graham". MundoMatemático .
• Cómo calcular el número de Graham
• Conceptualizando el número de Graham
• Algunos resultados de Ramsey para la prepublicación de n-cube mencionan el número de Graham
• Padilla, Tony; Parker, Matt. "El número de Graham". Numéfilo . Brady Harán . Archivado desde el original el 27 de mayo de 2014 . Consultado el 8 de abril de 2013 .
• Archivado en Ghostarchive y Wayback Machine: Ron Graham . "¿Cuál es el número de Graham? (con Ron Graham)" (vídeo) . Numéfilo . Brady Harán .
• Archivado en Ghostarchive y Wayback Machine: Ron Graham . "¿Qué tan grande es el número de Graham? (con Ron Graham)" (vídeo) . Numéfilo . Brady Harán .
• Los últimos 16 millones de dígitos del número de Graham según el grupo de comunicación Darkside