Número de Graham

O número de Graham, em homenagem a Ronald Graham, é um número muito grande que é um limite superior sobre a solução para um determinado problema na teoria de Ramsey.

Exemplo de um cubo tridimensional de duas cores contendo um único vértice quadrilátero subgráfico completo coplanar. O subgrafo é mostrado abaixo do cubo. Note-se que esse cubo que não contem tal subgrafo se, por exemplo, a borda inferior no presente subgrafo for substituída por uma borda azul - provando assim que via exemplo contrário, $N*>3$.

O número ganhou um grau de atenção popular quando Martin Gardner o descreveu na seção "Mathematical Games" do Scientific American em novembro de 1977, escrevendo que "Em uma prova inédita, Graham criou recentemente ... um salto tão grande que ele detém o recorde para o maior número já usado em uma prova séria matemática."

A edição de 1980 do Guiness Book of World Records repetiu a afirmação de Gardner, aumentando o interesse popular por este número. O número de Graham é inimaginavelmente maior do que os outros já conhecidos grande números como o googol, googolplex, e ainda maior do que o Número de Skewes e o Número de Moser. Na verdade, o Universo observável é demasiado pequeno para conter uma representação ordinária do número de Graham, supondo que cada dígito ocupe pelo menos um volume de Planck. Mesmo torres de potência da forma $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ são inúteis para esse fim, embora ele possa ser facilmente descrito pelas fórmulas recursivas usando a Notação de Knuth ou equivalente, como foi feito por Graham. Os dez últimos dígitos do número de Graham são ... 2464195387.

Inteiros específicos conhecidos por serem muito maiores do que o número de Graham, desde então, apareceram em muitas provas matemáticas sérias (por exemplo, em conexão com as várias formas finitas de Friedman do Teorema de Kruskal).

O Problema de Graham

O número de Graham está ligado ao seguinte problema no ramo da matemática conhecido como teoria de Ramsey:

Considere um hipercubo n-dimensional, e conecte cada par de vértices para obter um grafo completo com $2^{n}$ vértices. Em seguida, pinte cada uma das arestas do grafo usando apenas as cores vermelho e preto. Qual é o menor valor de n para o qual todas as colorações possíveis devem necessariamente incluir um sub-grafo completo de uma única cor com 4 vértices que estão em um mesmo plano?

Graham & Rothschild (1971) provaram que este problema tem uma solução N*, e deram como uma estimativa delimitadora 6 ≤ N* ≤ N, com o limite superior N um particular, explicitamente definido, número muito grande. (Em termos da notação de seta para cima de Knuth, $N=F^{7}(12)\,\!$, onde $F(n)=2\uparrow ^{n}3\,\!$.) O limite inferior de 6 foi posteriormente melhorado por Geoff Exoo (2003), que mostrou que a solução deve ser pelo menos 11, e forneceu evidências experimentais sugerindo que é pelo menos 12. Assim, a melhor estimativa explícita delimitadora conhecida para a solução N* é agora 11 ≤ N* ≤ N.

O tema do presente artigo é um limite superior G que é muito mais fraco (maior) do que N; ou seja, $G=f^{64}(4)\,\!$, onde $f(n)=3\uparrow ^{n}3\,\!$. Este fraco limite superior, atribuído a alguns trabalhos inéditos de Graham, foi finalmente publicado (e apelidado de Número de Graham) por Martin Gardner, no Scientific American, "Mathematical Games", Nov. 1977].

Definição do Número de Graham

Usando a notação de seta para cima de Knuth, o número de Graham G (como definido no artigo de Gardner da Scientific American) é

$\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 \uparrow 3\end{matrix}}\right\}{\text{64 camadas}}$

onde o número de setas em cada camada, a partir da camada superior, é especificado pelo valor da camada imediatamente abaixo dela, isto é,

$G=g_{64},{\text{ onde }}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,$

e onde um sobrescrito em uma seta para cima indica quantas setas estão lá. Em outras palavras, G é calculado em 64 etapas: o primeiro passo é calcular g₁, com quatro setas para cima entre 3's, o segundo passo é calcular g₂ com g₁ setas para cima entre 3's; o terceiro passo é calcular g₃ com g₂ setas para cima entre 3's; e assim por diante, até que finalmente se calcule G = g₆₄ com g₆₃ setas para cima entre 3's.

Equivalentemente,

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

e o sobrescrito em f indica uma iteração de uma função, por exemplo, f ⁴(n) = f(f(f(f(n)))). A função f é um caso especial de hiper() família de funções, $f(n)={\text{hyper}}(3,n+2,3)$, e também pode ser expressa na Notação de seta encadeada de Conway como $f(n)=3\rightarrow 3\rightarrow n$. A última notação também fornece os seguintes limites em G:

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

Magnitude do número de Graham

Para transmitir a dificuldade de se perceber a ideia do enorme tamanho do número de Graham, pode ser útil expressar, em termos de exponenciação, apenas o primeiro termo (g₁) da sequência de 64-termos de rápido crescimento. Em primeiro lugar, em termos de Tetração ($\uparrow \uparrow$) somente:

$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 ))$

onde o número de 3s na expressão da direita é

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

Agora, cada operação de Tetração ($\uparrow \uparrow$) reduz para uma "torre" de exponenciação ($\uparrow$), de acordo com a definição

$3\uparrow \uparrow X\ =\ 3\uparrow (3\uparrow (3\uparrow \dots (3\uparrow 3)\dots ))\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\quad {\text{onde existem X 3s}}.$

Assim,

$g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))\quad {\text{onde a quantidade de 3s equivale a}}\quad 3\uparrow \uparrow (3\uparrow \uparrow 3)$

torna-se, exclusivamente, em termos de repetidas "torres de exponenciação",

$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 {\text{onde a quantidade de torres fica com}}\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3$

e onde o número de 3s em cada torre, a partir da torre da esquerda, é especificado pelo valor da torre ao lado da direita.

Em outras palavras, g₁ é obtido calculando-se primeiramente o número de torres, n = 3^3^3^...^3 (onde o número de 3s é 3^3^3 = 7625597484987), e então, calculando-se a n^ésima torre na seguinte sequência:

      1.ª torre:  3

      2.ª torre:  3^3^3 (número de 3s é 3) = 7625597484987

      3.ª torre:  3^3^3^3...^3 (número de 3s é 7625597484987) = ...

      .
      .
      .

 g1 = nésima torre:  3^3^3^3^3^3^3^...^3 (número de 3s é dado pela n-1ésima torre)

onde o número de 3s em cada torre sucessiva é dado pela torre anterior. Note que a terceira torre acontece também ser o valor de n, o número de torres.

A magnitude desse primeiro termo,g₁, é tão grande que é praticamente incompreensível, embora a figura acima seja relativamente fácil de compreender. Mesmo n, o mero número de torres nesta fórmula para g₁, é muito maior do que o número de volumes de Planck (cerca de 10^185 deles) em que se pode imaginar subdividindo-se o universo observável. E depois deste primeiro termo, ainda restam outros 63 termos na sequência g que vem crescendo rapidamente antes do número Graham G = g₆₄ ser atingido.

Dígitos decimais mais à direita do número de Graham

O número de Graham é uma torre de potência da forma 3$\uparrow \uparrow$n (com um valor muito grande para n), pelo que a sua direita dígitos decimais devem satisfazer certas propriedades comuns a todas essas torres. Uma dessas propriedades é que todas as torres de tal altura maior do que d (por exemplo), têm a mesma sequência de d dígitos decimais à direita. Este é um caso especial de uma propriedade mais geral: os d dígitos decimais mais à direita de todas as torres de altura superior a d+2 são independentes dos mais altos na torre; ou seja, os "3" superiores no topo podem ser alterados para qualquer outro inteiro não negativo, sem afetar os d dígitos mais à direita.

A tabela a seguir ilustra, para alguns valores de d, como isso acontece. Para uma dada altura da torre e um número de dígitos d, a gama completa de números de dígitos-d (10^d deles) não ocorre; ao invés, um subconjunto menor de valores se repete em um ciclo. A duração do ciclo e alguns dos valores (entre parênteses) são mostrados em cada célula da tabela:

Número de diferentes possíveis valores de 3$\uparrow$3$\uparrow$...3$\uparrow$x quando todos exceto os d dígitos decimais mais à direita são ignorados

Número de dígitos (d)	3$\uparrow$x	3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$x	3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$3$\uparrow$x
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)

Particularmente, os d dígitos mais à direita, que são em última análise partilhados por todas as torres suficientemente altas de 3s, estão em negrito, e podem ser vistos em desenvolvimento à medida que a altura da torre aumenta. Para qualquer número fixo de dígitos d (linha na tabela), o número de possíveis valores para 3$\uparrow$3$\uparrow$...3$\uparrow$x mod 10^d, como x varia percorrendo todos os inteiros não negativos, parece diminuir progressivamente com o aumento da altura, até eventualmente reduzir o "conjunto de possibilidades" para um número único (células coloridas), quando a altura exceder d+2.

Um algoritmo simples para computar esses números pode ser descrito como segue: faça x = 3, então faça uma iteração de d vezes do comando de atribuição x = 3^x mod 10^d. Exceto pela omissão de quaisquer 0s na frente, o valor final atribuído a x (como um número de base dez) é então composto pelos d dígitos decimais mais à direita de 3$\uparrow \uparrow$n, para todo n > d.(Se o valor final de x tem menos dígitos d, então o número de 0s à frente devem ser adicionados).

Este algoritmo produz os seguintes 500 dígitos decimais mais à direita do número de Graham (ou qualquer torre de mais de 500 3s):

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

Ver também

• Função de Ackermann

Ligações externas

• Um problema de Ramsey sobre Hipercubos
• artigo na Mathworld sobre números de Graham
• Como calcular um número de Graham
• Numeropedia - the Special Encyclopedia of Numbers