Numero de graham

Número de Graham es un número inmenso que surgió como un 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, ambos a su vez mucho más grande que un googolplex. Como con estos, es tan grande que el universo observable es demasiado pequeño para contener una representación digital ordinaria del número de Graham, asumiendo que cada dígito ocupa un volumen de Planck, posiblemente el espacio más pequeño posible. 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 ser representada en el universo observable. Ni siquiera puede el número de dígitos de que número, y así sucesivamente, por un número de veces superior al número total de volúmenes de Planck en el universo observable. Por lo tanto, el número de Graham no puede ser expresado incluso por torres de energía física a escala universal de la forma abc⋅ ⋅ ⋅ ⋅ ⋅ ⋅ {cdot }.

Sin embargo, el número de Graham puede ser dado explícitamente por fórmulas recursivas computables usando la notación de Knuth hacia arriba o equivalente, como lo hizo Ronald Graham, el nombre del número. Como hay una fórmula recursiva para definirla, es mucho más pequeño que los números típicos del castor ocupado. Aunque demasiado grande para ser computado en su totalidad, la secuencia de dígitos del número de Graham se puede computar explícitamente a través de algoritmos simples; los últimos 13 dígitos son...7262464195387. Con la notación de Knuth, el número de Graham es g64{displaystyle g_{64}, donde

gn={}3↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3,n=13↑ ↑ gn− − 13,n≥ ≥ 2,n▪ ▪ N{displaystyle g_{n}=left{begin{matrix}3uparrow uparrow uparrow 3, limitadan=133uparrow ^{g_{n-1}}3, limitngeq 2,nin 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 número entero positivo específico más grande jamás utilizado en una prueba matemática publicada. El número se describió 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 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 de Kruskal de Harvey Friedman.;s teorema. Además, se ha demostrado que los límites superiores más pequeños en el problema de la teoría de Ramsey del que se deriva el número de Graham son válidos.

Contexto

Ejemplo de un cubo 3-dimensional de 2 colores que contiene un subgraph completo coplanar de 4-vertex de color único. El subgrafo se muestra debajo del cubo. Tenga en cuenta que este cubo no contiene tal subgrafo si, por ejemplo, el borde inferior en el subgrafo presente fue reemplazado por un borde azul – demostrando así por contraexamplo que N* 3.

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

Conectar cada par de vértices geométricos de un n- hipercubo dimensional para obtener un gráfico completo en 2ⁿ vertices. Color cada uno de los bordes de este gráfico ya sea rojo o azul. ¿Cuál es el valor más pequeño de n para la cual cada uno tal coloración contiene al menos un subgrafo completo de un solo color en cuatro vértices coplanar?

En 1971, Graham y Rothschild demostraron el teorema de Graham-Rothschild sobre la teoría de Ramsey de palabras parámetro, 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 valor grande pero explícitamente número definido

F7()12)=F()F()F()F()F()F()F()12))))))),{displaystyle F^{7}(12)=F(F(F(F(F(F(F(F(F(F(12)))))),}

Donde F()n)=2↑ ↑ n3{displaystyle F(n)=2uparrow ^{n}3} en la notación de Knuth hacia arriba; el número es entre 4 → 2 → 8 → 2 y 2 → 3 → 9 → 2 en la notación de flecha encadenada de Conway. Esto se redujo en 2014 a través de los límites superiores del número Hales-Jewett a

N.=2↑ ↑ ↑ ↑ 2↑ ↑ ↑ ↑ ()3+2↑ ↑ ↑ ↑ 8),{displaystyle N'=2uparrow uparrow 2uparrow uparrow (3+2uparrow uparrow 8),}

que contiene tres tetraciones. En 2019 esto se mejoró aún más a:

N.=()2↑ ↑ ↑ ↑ 5138)⋅ ⋅ ()()2↑ ↑ ↑ ↑ 5140)↑ ↑ ↑ ↑ ()2⋅ ⋅ 2↑ ↑ ↑ ↑ 5137))≪ ≪ 2↑ ↑ ↑ ↑ ()2↑ ↑ ↑ ↑ 5138){displaystyle N'=(2uparrow uparrow 5138)cdot ((2uparrow uparrow 5140)uparrow uparrow (2cdot 2uparrow uparrow 5137)ll 2uparrow uparrow (2uparrow uparrow 5138)}

El límite inferior de 6 fue posteriormente mejorado a 11 por Geoffrey Exoo en 2003, y a 13 por Jerome Barkley en 2008. Por lo tanto, los límites más conocidos para N* son 13 ≤ N* ≤ N''.

El número de Graham, G, es mucho más grande que N: f64()4){displaystyle f^{64}(4)}, donde f()n)=3↑ ↑ n3{displaystyle f(n)=3uparrow ^{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.

Publicación

El número ganó cierto grado de atención popular cuando Martin Gardner lo describió en los "Juegos matemáticos" sección de Scientific American en noviembre de 1977, escribiendo que Graham había establecido recientemente, en una prueba inédita, "un límite tan grande que tiene el récord del número más grande jamás utilizado en un estudio matemático serio". prueba." 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 que ahora se conoce 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 obtenido con su colaborador Bruce Lee Rothschild, encontró 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 le 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.

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 Scientific American de Gardner) es

G=3↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 33↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 3⋮ ⋮ ⏟ ⏟ 3↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 33↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3}64 capas{displaystyleleft.{begin{matrix}cdots cdots cdots cdots cdots cdots cdots cdotsuparrow } 3cambio de texto

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

G=g64,{displaystyle G=g_{64},}

g1=3↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3,{displaystyle g_{1}=3uparrow uparrow uparrow 3,}

gn=3↑ ↑ gn− − 13,{displaystyle G_{n}=3uparrow ^{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 3s; el segundo paso es calcular g₂ con g₁ flechas hacia arriba entre 3s; el tercer paso es calcular g₃ con g₂ flechas hacia arriba entre 3s; y así sucesivamente, hasta finalmente calcular G = g₆₄ con g₆₃ arriba -flechas entre 3s.

Equivalentemente,

G=f64()4),Dondef()n)=3↑ ↑ n3,{displaystyle G=f^{64}(4),{text{ where }f(n)=3uparrow ^{n}3,}

y el superscript en f indica una iteración de la función, por ejemplo, f4()n)=f()f()f()f()n)))){displaystyle f^{4}(n)=f(f(f(f(n))}. Expresado en términos de la familia de las hiperoperaciones H0,H1,H2,⋯ ⋯ {fnMicrosoft Sans Serif}, {fnMicrosoft Sans Serif}, la función f es la secuencia particular f()n)=Hn+2()3,3){displaystyle f(n)={H}_{n+2}(3,3)}, que es una versión de la función Ackermann de crecimiento rápido A()n, n). (De hecho, A(n,n)}" xmlns="http://www.w3.org/1998/Math/MathML">f()n)■A()n,n){displaystyle f(n)A(n,n)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c61f45ab6d510d883372184279568d07c6396ebb" style="vertical-align: -0.838ex; width:14.957ex; height:2.843ex;"/> para todos n.) La función f también se puede expresar en la notación de flecha encadenada de Conway como f()n)=3→ → 3→ → n{displaystyle f(n)=3rightarrow 3rightarrow n}, y esta notación también proporciona los siguientes límites en G:

Magnitud

Para transmitir la dificultad de apreciar el enorme tamaño del número de Graham, puede ser útil expresar, solo en términos de exponentiación, el primer término (g₁) de la secuencia de 64 plazos que crece rápidamente. Primero, en términos de tetración (↑ ↑ ↑ ↑ {displaystyle uparrow uparrow }Solo:

g1=3↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3=3↑ ↑ ↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ ↑ ↑ 3)=3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ ...... ()3↑ ↑ ↑ ↑ 3)...... )){displaystyle g_{1}=3uparrow uparrow uparrow uparrow 3=3uparrow uparrow (3uparrow uparrow uparrow 3)=3uparrow uparrow (3uparrow uparrow (3uparrow uparrow dots (3uparrow uparrow 3)dots)}

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

3↑ ↑ ↑ ↑ ↑ ↑ 3=3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ 3).{displaystyle 3uparrow uparrow 3=3uparrow uparrow (3uparrow uparrow 3).}

Ahora cada tetración (↑ ↑ ↑ ↑ {displaystyle uparrow uparrow }) operación reduce a una torre de energía (↑ ↑ {displaystyle uparrow }) según la definición

3↑ ↑ ↑ ↑ X=3↑ ↑ ()3↑ ↑ ()3↑ ↑ ...... ()3↑ ↑ 3)...... ))=33⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 3{displaystyle 3uparrow uparrow X=3uparrow (3uparrow dots (3uparrow 3)dots)=3^{cdot ^{cdot ^{cdot ^{cdot ^{3}}}}}}}}}}}}}}}}}}}}}}}}}}}

Por lo tanto,

g1=3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ ...... ()3↑ ↑ ↑ ↑ 3)...... ))donde el número de 3s es3↑ ↑ ↑ ↑ ()3↑ ↑ ↑ ↑ 3){displaystyle g_{1}=3uparrow uparrow (3uparrow uparrow (3uparrow uparrow dots (3uparrow uparrow 3)dots)quad {text{where the number of 3s is}quad 3uparrow uparrow (3uparrow uparrow 3)}}

se vuelve, únicamente en términos de "torres de exponenciación" repetidas,

g1=33⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 3}33⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 3}...... 333}3⏟ ⏟ 33⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 3}333}3{displaystyle {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {cdot} {cdot} {cdot} {cdotcdot ^{3}}}}}} {cdotcdotcdot} {3}{3}{3} {cdot} {m}{3} {cdot} {cdot} {}c}c} {} {cdot}{3} {} {}c}c}c}c}} {cdot} {c}c}c}cdot} {} {} {} {} {c} {cdot} {cdot} {}c}c}cdot} {c}c}c}c}c}c}c}cdot} {}c}c}}c}c

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 por primera vez calculando el número de torres, n=3↑ ↑ ()3↑ ↑ ()3...... ↑ ↑ 3)){displaystyle n=3uparrow (3 dots uparrow 3)} (donde el número de 3s es 3↑ ↑ ()3↑ ↑ 3)=7625597484987{displaystyle 3uparrow (3uparrow 3)=7625597484987}), y luego computar el n^T torre en la siguiente secuencia:

 Primera torre: 32a torre: 3↑3↑3 (número de 3s es 3) 76255974849873a torre: 3↑3↑3↑3↑3 (número de 3s es 7625597484987) =...

⋮

 g1 = nT torre: 3↑3↑3↑3↑3↑3↑3↑3 (número de 3s es dado por el n-1T torre)

donde el número de 3 en cada torre sucesiva viene dado por la torre justo antes de ella. 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 mandato, g₁, es tan grande que es prácticamente incomprensible, aunque la pantalla 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 el que uno puede imaginar subdividir el universo observable. Y después de este primer mandato, aún quedan otros 63 términos en el rápido crecimiento g secuencia antes del número de Graham G = g₆₄ es alcanzado. Para ilustrar lo rápido que esta secuencia crece, mientras g₁ es igual a 3↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3{displaystyle 3uparrow uparrow uparrow uparrow 3} con sólo cuatro flechas arriba, el número de flechas arriba en g₂ es este número incomprensiblemente grande g₁.

Dígitos decimales más a la derecha

El número de Graham es una "torre de energía" de la forma 3↑↑n (con un valor muy grande de n), por lo que sus dígitos decimales más a la derecha deben satisfacer ciertas propiedades comunes a todas estas torres. Una de estas propiedades es que todas esas torres de altura superior a d (por ejemplo), tienen la misma secuencia de d dígitos decimales más a la derecha. Este es un caso especial de una propiedad más general: los dígitos decimales d más a la derecha de todas esas torres de altura superior a d+2, son independientes del más alto "3" en la torre; es decir, el "3" se puede cambiar a cualquier otro entero no negativo sin afectar los dígitos de la derecha d.

La siguiente tabla ilustra, para algunos valores de d, cómo sucede esto. Para una altura de torre dada y un número de dígitos d, el rango completo de números de dígitos d (10^d de ellos) no ocurre; en cambio, 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:

El derecho en particular d dígitos que en última instancia son compartidos por todas las torres suficientemente altas de 3s están en texto audaz, y se puede ver desarrollar a medida que aumenta la altura de la torre. Para cualquier número fijo de dígitos d (hacia la tabla), el número de valores posibles para 3↑ ↑ {displaystyle scriptstyle uparrow }3↑...3↑x mod. 10^d, como x rangos sobre todos los enteros no negativos, se ve disminuir constantemente a medida que la altura aumenta, hasta reducir finalmente el "posibilidad establecido" a un solo número (células coloreadas) cuando la altura excede d+2.

Un algoritmo simple para calcular estos dígitos se puede describir de la siguiente manera: sea x = 3, luego itere, d veces, la asignación x = 3^x mod 10^d. Excepto por la omisión de cualquier 0 inicial, el valor final asignado a x (como un número de base diez) se compone de los dígitos decimales d más a la derecha de 3↑↑n, para todos los n > d. (Si el valor final de x tiene menos de d dígitos, entonces se debe agregar el número requerido de ceros iniciales).

Sea k la cantidad de estos dígitos estables, que satisfacen la relación de congruencia G(mod 10^k)≡[G^G](mod 10^k).

k=t-1, donde G(t):=3↑↑t. De ello se deduce que, g₆₃ ≪ k ≪ g₆₄.

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

...02425950695064738395657479136519351798334535362521
43003540126026771622672160419810652263169355188780
388144831406526168785095552646051071172000997092
91249544378887496062882911725063001303622934916080
254594614945788714278350829242102091825896753560
43086993801689249889268099510169055919951195027887
178308370183402364745488822161573228010132974509
273445945043300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380
032223487239670184851864390591045756272464195387

gn=3↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 33↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 3⋮ ⋮ ⏟ ⏟ 3↑ ↑ ↑ ↑ ⋯ ⋯ ⋯ ⋯ ↑ ↑ ⏟ ⏟ 33↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 3}nlaSí.ers=..24894259506950647365747913651935179833453621430035401260267760676721601865226316935518878038814483140652616878952496922490{displaystyle left.{begin{matrix}g_{n} {cdots cdots cdots cdots cdots cdots uparrow } 3\\cdots cdots cdots cdots cdots uparrow } 3flearrow gorrión {qquadcdot42595069507890783