Teorema do número primo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Gráfico comparativo de π(x) (vermelho), x / ln x (verde) e Li(x) (azul).

Em matemática, sobretudo na teoria dos números, o teorema do número primo é um importante resultado sobre a distribuição dos números primos, que afirma que o número de primos menores ou iguais a n é aproximadamente n / ln n. Este resultado foi primeiramente demonstrado independentemente por dois matemáticos franceses, Jacques Hadamard e Charles-Jean de La Vallée Poussin, através do estudo da função zeta de Riemann. Uma demonstração elementar, sem apelo à teoria analítica dos números, foi dada posteriormente por Atle Selberg e Paul Erdös.

Enunciado[editar | editar código-fonte]

Seja \Pi(n)\, a função de contagem de números primos, que retorna o número de números primos entre 1 e n. Então vale o limite:

\lim_{n\to\infty}\frac{\Pi(n)}{n/ \ln n}=1\,

Não é difícil mostrar que este limite é equivalente a este outro:

\lim_{n\to\infty}\frac{p_n}{n \ln n}=1\,

onde p_n\, é o enésimo número primo.

Usando-se notação assimptótica, pode-se expressar o teorema como:

\Pi(n)\sim\frac{n}{\ln n}.\!

História[editar | editar código-fonte]

Distribuição dos primos até 19# (9699690).

Com base nas tabelas de Anton Felkel e Jurij Vega, Adrien-Marie Legendre conjecturou em 1797 ou 1798 que π(a) é aproximado pela função a/(A ln(a) + B), onde A e B são constantes não especificadas. Na segunda edição de seu livro sobre a teoria dos números (1808) ele então fez uma conjectura mais precisa, com A = 1 e B = −1,08366. Carl Friedrich Gauss considerou essa mesma questão quando tinha 15 ou 16 anos "ins Jahr 1792 oder 1793", segundo a sua própria recordação em 1849.[1] Em 1838 Peter Gustav Lejeune Dirichlet desenvolveu sua própria função aproximadora, a integral logarítmica li(x) (sob a forma ligeiramente diferente de uma série, que ele comunicou a Gauss). Ambas as fórmulas, de Legendre e Dirichlet, implicam a mesma equivalência assimptótica conjecturada de π(x) e x / ln(x) enunciada acima, embora tenha sido descoberto que a aproximação de Dirichlet é consideravelmente melhor se considerarmos as diferenças em vez dos quocientes.

Em dois artigos de 1848 e 1850, o matemático russo Pafnuty L'vovich Chebyshev tentou provar a lei assintótica de distribuição dos números primos. Seu trabalho é notável por usar a função zeta ζ(s) (para valores reais do argumento "s", como nas obras de Leonhard Euler, de 1737) precedendo o celebrado ensaio de Riemann de 1859, e ele obteve sucesso em provar uma forma ligeiramente mais fraca da lei assintótica, a saber, que se o limite de π(x)/(x/ln(x)) quando x vai ao infinito existe definitivamente,então ele é necessariamente igual a um.[2] Ele foi capaz de provar de forma incondicional que esta razão é limitada acima e abaixo por duas explicitamente dadas constantes próximas de 1 para todo x.[3] Embora em seu artigo Chebyshev não tenha provado o teorema dos números primos, suas estimativas para π(x) eram fortes o suficiente para ele provar o postulado de Bertrand que afirma que existe um número primo entre n e 2n para todo inteiro n ≥ 2.

Um importante artigo a respeito da distribuição dos números primos foi o ensaio de Riemann de 1859 Sobre o Número de Primos Menores Que uma Dada Magnitude, o único artigo que ele escreveu sobre o assunto. Riemann introduziu novas ideias ao tópico, a maior delas sendo a de que a distribuição dos números primos é intimamente conectada aos zeros da analiticamente estendida função zeta de Riemann de uma variável complexa. Em particular, foi nesse artigo de Riemann que a ideia de aplicar métodos de análise complexa ao estudo da função real π(x) teve origem. Estendendo as ideias de Riemann, duas provas da lei assintótica da distribuição de números primos foram obtidas de forma independente por Jacques Hadamard e Charles Jean de la Vallée-Poussin e apareceram no mesmo ano (1896). Ambas as provas utilizaram métodos de análise complexa, estabelecendo como um passo importante da prova que a função zeta de Riemann ζ(s) é não negativa para todos os valores complexos da variável s que tem a forma s = 1 + it com t > 0.[4]

Durante o século XX, o teorema de Hadamard e de la Vallée-Poussin tornou-se conhecido como o teorema dos números primos. Várias provas diferentes dele foram encontradas, incluindo as provas "elementares" de Atle Selberg e Paul Erdős (1949). Enquanto as provas originais de Hadamard e de la Vallée-Poussin são longas e complicadas, provas posteriores introduziram várias simplificações através do uso dos teoremas de Tauberian mas mantiveram-se difíceis de assimilar. Uma prova curta foi descoberta em 1980 pelo matemático estadunidense Donald J. Newman.[5] [6] A prova de Newman é talvez a prova mais simples conhecida do teorema, embora seja não elementar, uma vez que usa o teorema integral de Cauchy de análise complexa.

Demonstrações elementares[editar | editar código-fonte]

Na primeira metade do século XX, alguns matemáticos (notavelmente, G. H. Hardy) acreditavam que existe uma hierarquia de métodos de demonstração em matemática, dependendo do tipo de números (inteiros, reais, complexos) que uma demonstração requer, e que o teorema dos números primos (TNP) é um teorema "profundo" em virtude de requerer análise complexa.[7] Essa crença foi um pouco abalada por uma demonstração do TNP com base no teorema tauberiano de Wiener, embora isso pudesse ser posto de lado se o teorema de Wiener fosse considerado como tendo uma "profundidade" equivalente a dos métodos de variáveis complexas. Não existe uma definição rigorosa e amplamente aceita da noção de demonstração elementar em teoria dos números. Uma definição é "uma prova de que pode ser realizada com aritmética de Peano de primeira ordem." Há enunciados de teoria dos números (por exemplo, o teorema de Paris–Harrington) que são demonstráveis usando-se aritmética de segunda ordem mas não com métodos de aritmética de primeira ordem, mas até o presente momento conhece-se poucos teoremas assim.

Em março de 1948, Atle Selberg estabeleceu, por métodos elementares, a fórmula assintótica

\vartheta \left( x \right)\log \left( x \right) + \sum\limits_{p \le x} {\log \left( p \right)}\ \vartheta \left( {\frac{x}{p}} \right) = 2x\log \left( x \right) + O\left( x \right)

em que

\vartheta \left( x \right) = \sum\limits_{p \le x} {\log \left( p \right)}

para primos p.[8] Em julho daquele ano, Selberg e Paul Erdös tinham cada um obtido demonstrações elementares do TNP, ambos usando a fórmula assintótica de Selberg como ponto de partida.[7] [9] Essas provas efetivamente colocaram para descansar a noção de que o TNP era "profundo", e mostraram que, tecnicamente, métodos "elementares" (em outras palavras, aritméticas de Peano) eram mais poderosos do que se acreditava ser o caso. Em 1994, Charalambos Cornaros e Costas Dimitracopoulos demonstraram o TNP usando apenas I\Delta_0+\exp,[10] um sistema formal muito mais fraco do que a aritmética de Peano.[7]

Tabela de π(x), x / ln x e Li(x)[editar | editar código-fonte]

A tabela seguinte compara os valores de π(x) com as aproximações x / ln x e Li(x). A última coluna, x / π(x), é a distância média entre os primos abaixo de x.

x π(x)[11] π(x) − x / ln x[12] π(x) / (x / ln x) Li(x) − π(x)[13] x / π(x)
10 4 −0,3 0,921 2,2 2,500
10² 25 3,3 1,151 5,1 4,000
10³ 168 23 1,161 10 5,952
104 1.229 143 1,132 17 8,137
105 9.592 906 1,104 38 10,425
106 78.498 6.116 1,084 130 12,740
107 664.579 44.158 1,071 339 15,047
108 5.761.455 332.774 1,061 754 17,357
109 50.847.534 2.592.592 1,054 1.701 19,667
1010 455.052.511 20.758.029 1,048 3.104 21,975
1011 4.118.054.813 169.923.159 1,043 11.588 24,283
1012 37.607.912.018 1.416.705.193 1,039 38.263 26,590
1013 346.065.536.839 11.992.858.452 1,034 108.971 28,896
1014 3.204.941.750.802 102.838.308.636 1,033 314.890 31,202
1015 29.844.570.422.669 891.604.962.452 1,031 1.052.619 33,507
1016 279.238.341.033.925 7.804.289.844.393 1,029 3.214.632 35,812
1017 2.623.557.157.654.233 68.883.734.693.281 1,027 7.956.589 38,116
1018 24.739.954.287.740.860 612.483.070.893.536 1,025 21.949.555 40,420
1019 234.057.667.276.344.607 5.481.624.169.369.960 1,024 99.877.775 42,725
1020 2.220.819.602.560.918.840 49.347.193.044.659.701 1,023 222.744.644 45,028
1021 21.127.269.486.018.731.928 446.579.871.578.168.707 1,022 597.394.254 47,332
1022 201.467.286.689.315.906.290 4.060.704.006.019.620.994 1,021 1.932.355.208 49,636
1023 1.925.320.391.606.818.006.727 37.083.513.766.592.669.113 1,020 7.236.148.412 51,939

Referências

  1. C.F. Gauss. Werke, Bd 2, 1st ed, 444-447. Göttingen 1863.
  2. N. Costa Pereira. (August–September 1985). "A Short Proof of Chebyshev's Theorem". American Mathematical Monthly 92 (7): 494–495. DOI:10.2307/2322510.
  3. M. Nair. (February 1982). "On Chebyshev-Type Inequalities for Primes". American Mathematical Monthly 89 (2): 126–129. DOI:10.2307/2320934.
  4. Ingham, A.E.. The Distribution of Prime Numbers. [S.l.]: Cambridge University Press, 1990. 2–5 pp. ISBN 0-521-39789-8.
  5. D. J. Newman. (1980). "Simple analytic proof of the prime number theorem". American Mathematical Monthly 87 (9): 693–696. DOI:10.2307/2321853.
  6. D. Zagier. (1997). "Newman's short proof of the prime number theorem". American Mathematical Monthly 104 (8): 705–708. DOI:10.2307/2975232.
  7. a b c D. Goldfeld The elementary proof of the prime number theorem: an historical perspective.
  8. Selberg, Atle. (Apr 1949). "An Elementary Proof of the Prime-Number Theorem". Annals of Mathematics 50 (2): 305–313. DOI:10.2307/1969455.
  9. Baas, Nils A.. (2008). "The lord of the numbers, Atle Selberg. On his life and mathematics". Bull. Amer. Math. Soc. 45 (4): 617–649. DOI:10.1090/S0273-0979-08-01223-8.
  10. (1994) "The prime number theorem and fragments of PA". Archive for Mathematical Logic 33 (4): 265–281. DOI:10.1007/BF01270626.
  11. Number of primes < 10^n (A006880) On-Line Encyclopedia of Integer Sequences.
  12. Difference between pi(10^n) and the integer nearest to 10^n / log(10^n) (A057835) On-Line Encyclopedia of Integer Sequences.
  13. Difference between Li(10^n) and Pi(10^n). where Li(x) = integral of log(x) and Pi(x) = number of primes <= x (A057752) On-Line Encyclopedia of Integer Sequences.