Número de Graham

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo (desde Dezembro de 2012). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
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ú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 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 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, , onde .) 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, , onde . 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) é

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

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,

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, , e também pode ser expressa na Notação de seta encadeada de Conway como . A última notação também fornece os seguintes limites em G:

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 () somente:

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

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

Assim,

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

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 3n (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 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 33...3x quando todos exceto os d dígitos decimais mais à direita são ignorados
Número de dígitos (d) 3x 33x 333x 3333x 33333x
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 33...3x 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 3n, 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

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