# 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.
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\$
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$_1$, com quatro setas para cima entre 3's, o segundo passo é calcular g$_2$ com g$_1$ setas para cima entre 3's; o terceiro passo é calcular g$_3$ com g$_2$ setas para cima entre 3's; e assim por diante, até que finalmente se calcule G = g$_{64}$ com g$_{63}$ 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$^4$(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$_1$) 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\$
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$_1$ é 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:
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$_1$, é 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$_1$, é 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$_{64}$ 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):