Número de Graham

Número de Graham
Arrows-orphan.svg
 Este artículo está huérfano, pues pocos o ningún artículo enlazan aquí.
Por favor, introduce enlaces hacia esta página desde otros artículos relacionados.

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:

En una demostración no publicada, Graham ha establecido recientemente ... una cota tan vasta que tiene el registro de ser el mayor número jamás usado en una demostración matemática seria.[1]

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 gugolplex 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 las «torres de exponentes» de la forma a ^{ b ^{ c ^{ \cdot ^{ \cdot ^{ \cdot}}}}} se revelan inú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.

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.

Contenido

Problema de Graham

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 2n 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ó evidente 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.

Definición del 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:

\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\;\; \vdots \qquad\;\;} \\ & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\ & &3\uparrow \uparrow \uparrow \uparrow3 \end{matrix} \right \} \text{64 filas}

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,

G = g_{64},\text{ donde }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\ g_n = 3\uparrow^{g_{n-1}}3,

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 g1 con cuatro flechas entre los treses; el segundo paso consiste en calcular g2 con g1 flechas entre los treses, el tercer paso consiste en calcular g3 con g2 flechas entre los treses, y así sucesivamente hasta calcular finalmente G = g64, que tiene g63 flechas entre los treses.

Equivalentemente,

G = f^{64}(4),\text{ donde }f(n) = 3 \uparrow^n 3,

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(), f(n) = hiper(3,n + 2,3), y también se puede expresar mediante la notación de flechas encadenadas de Conway como f(n) = 3 \rightarrow 3 \rightarrow n. Esta última notación establece las siguientes cotas para G:

3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.\,

Magnitud del número de Graham

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 (g1) de la sucesión rápidamente creciente de 64 términos. Primero, expresemos el número mediante la tetración (\uparrow\uparrow):

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 treses en la expresión de la derecha es

3 \uparrow \uparrow \uparrow 3 \ = \ 3 \uparrow \uparrow (3 \uparrow \uparrow 3).

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

3 \uparrow\uparrow X \ = \ 3 \uparrow (3 \uparrow (3 \uparrow \dots (3 \uparrow 3) \dots )) \ = \ 3^{3^{\cdot^{\cdot^{\cdot^{3}}}}} \quad \text{donde hay X treses}.

Por tanto,

g_1 = 3 \uparrow\uparrow (3 \uparrow\uparrow (3 \uparrow\uparrow \ \dots \ (3 \uparrow\uparrow 3) \dots )) \quad \mathrm{donde~el~n\acute umero~de~treses~es}\, \quad 3 \uparrow \uparrow (3 \uparrow \uparrow 3)

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

g_1 = \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 \quad \mathrm{donde~el~n\acute umero~de~torres~es} \quad \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 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

g_1 = 3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) = 3 \uparrow \uparrow \uparrow \left( \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copias de 3}} \right) = \left. \begin{matrix} \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\text{copias de 3}}\text{copias de 3}} \\ \vdots \\ \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copias de 3}}\text{copies of 3}}\text{copias de 3} \end{matrix} \right \} \left. \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}}_{3^{3^3}\text{copias de 3}} \right. \text{filas}

La magnitud de este primer término, g1, es tan grande que prácticamente escapa a la comprensión humana. Incluso el número de torres presentes en esta fórmula para g1 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 = g64.

Últimas cifras del número de Graham

El número de Graham es una «torre de exponentes» de la forma 3\uparrow\uparrown (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 10d, 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:

Número de valores posibles de 3\uparrow3\uparrow...3\uparrowx cuando se ignoran todas las cifras menos las d últimas
Número de cifras (d) 3\uparrowx 3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrow3\uparrowx 3\uparrow3\uparrow3\uparrow3\uparrow3\uparrowx
1 4
(1,3,9,7)		 2
(3,7)		 1
(7)		 1
(7)		 1
(7)
2 20
(01,03,...,87,...,67)		 4
(03,27,83,87)		 2
(27,87)		 1
(87)		 1
(87)
3 100
(001,003,...,387,...,667)		 20
(003,027,...387,...,587)		 4
(027,987,227,387)		 2
(987,387)		 1
(387)

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\uparrow3\uparrow...3\uparrowx mod 10d, 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 = 3x mod 10d. El último valor asignado a x (como número en base 10) está compuesto por las d últimas cifras decimales de 3\uparrow\uparrown, para todo n > d. (Si el último valor de x sólo 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 treses) son:

...9404248265018193851562535
   7963996189939679054966380
   0322234872396701848518643
   9059104575627262464195387.

Temas relacionados

Referencias

  1. ↑ En inglés en el original: In an unpublished proof, Graham has recently established ... a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof.
  2. ↑ The Math Forum @ Drexel ("Last Eight Digits of Z")

Bibliografía

  • Graham, R. L.; Rothschild, B. L. (1971). «Ramsey's Theorem for n-Parameter Sets». Transactions of the American Mathematical Society 159:  pp. 257–292. doi:10.2307/1996010. 
  • Gardner, Martin (November 1977). «Mathematical Games». Scientific American 237:  pp. 18–28. ; reprinted (revised 2001) in the following book:
  • Gardner, Martin (2001). The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 0393020231. 
  • Gardner, Martin (1989). Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6. 
  • Exoo, Geoffrey (2003). «A Euclidean Ramsey Problem». Discrete Computational Geometry 29:  pp. 223–227. doi:10.1007/s00454-002-0780-5. 

Enlaces externos

En inglés:


Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Graham v. John Deere Co. — Graham v. John Deere Co. TRIBUNAL SUPREMO DE LOS ESTADOS UNIDOS Fecha 21 de febrero de 1966 Nombre completo del caso William T. Graham, et al. v. John Deere Co. of Kansas City, et al., together with No. 37, Calmar, Inc. v. Cook Chemical Co., and… …   Wikipedia Español

  • Graham Ingels — est un dessinateur de comics né le 7 juin 1915 à Cincinnati et mort le 4 avril 1991 à Lantana en Floride. Il fut un des piliers des EC Comics de 1948 à 1953 où il se spécialisa dans les comics d horreur. Lorsque EC s effondra, il arrêta de… …   Wikipédia en Français

  • Graham Harrell — Données générales Nationalité …   Wikipédia en Français

  • Graham Alexander — Pas d image ? Cliquez ici. Situation actuelle Club actuel …   Wikipédia en Français

  • Graham Dorrans — Graham Dorrans …   Wikipédia en Français

  • Graham Bonnet — Este artículo o sección sobre música y biografías necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de junio de 2010. También… …   Wikipedia Español

  • Graham Pritchard — Liste des personnages de l’univers de Harry Potter Cet article est une liste référençant les personnages de l univers de Harry Potter. Les personnages principaux peuvent être identifiés dans les articles suivants : Harry Potter Ron Weasley… …   Wikipédia en Français

  • Alexander Graham Bell — Alexander Graham Bell …   Wikipedia Español

  • Otto Graham — Données générales Nom complet Otto Everett Graham Jr …   Wikipédia en Français

  • Alexandre Graham Bell — Pour les articles homonymes, voir Bell. Alexander Graham Bell Portrait d Alexander Graham Bell vers 1914 – 1919 Naissance …   Wikipédia en Français

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”