Número de Graham

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde Dezembro de 2012).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

Número de Graham, em homenagem a Ronald Graham, é um grande número 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."

E edição de 1980 do Guiness Book of World Records repetiu a afirmação de Gardner, acrescentando interesse popular neste 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 Teorema de Kruskal).

O Problema de Graham[editar | editar código-fonte]

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 uma 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", November 1977].

Definição do Número de Graham[editar | editar código-fonte]

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 \uparrow3
 \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 g1, com quatro setas para cima entre 3's, o segundo passo é calcular g2 com g1 setas para cima entre 3's; o terceiro passo é calcular g3 com g2 setas para cima entre 3's; e assim por diante, até que finalmente se calcule G = g64 com g63 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[editar | editar código-fonte]

Para transmitir a dificuldade de se perceber a idéia do enorme tamanho do número de Graham, pode ser útil expressar, em termos de exponenciação, apenas o primeiro termo (g1) da seqüê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, g1 é 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,g1, é 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 g1, é 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 seqüência g que vem crescendo rapidamente antes do número Graham G = g64 ser atingido.

Dígitos decimais mais à direita do número de Graham[editar | editar código-fonte]

O número de Graham é uma torre de potência da forma 3\uparrow\uparrown (com um valor muito grande paran), 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 seqüê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 (10d 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\uparrow3\uparrow...3\uparrowx quando todos exceto os d dígitos decimais mais à direita são ignorados
Número de dígitos (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)

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\uparrow3\uparrow...3\uparrowx mod 10d, 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 [1] 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 = 3x mod 10d. 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\uparrown, 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[editar | editar código-fonte]

Referências

  1. The Math Forum @ Drexel ("Last Eight Digits of Z"). Página visitada em 2010-10-01.

Ligações externas[editar | editar código-fonte]