domingo, 5 de fevereiro de 2012

014-O Desafio dos Números Primos

Desde que o homem aprendeu a calcular até os tempos atuais não foi possível estabelecer uma fórmula fechada [;P_n;] que gere a  sequência [;P_1=2;],[;P_2=3;],[;P_3=5;],[;P_4=7;],[;P_5=11;], etc, ou seja,

[;P_n=;] enésimo número primo

Esta questão desafiou os melhores matemáticos de cada época provando ser um empreendimento bastante difícil, para não dizer impossível.


De forma que Legendre [;(1752-1833);] provou que não existe função algébrica racional que sempre forneça primos, mesmo que fora de ordem. Vejam uma prova desta impossibilidade para polinômios no [;3^o;] ítem de Miscelânea.

O que existem são fórmulas limitadas que fornecem primos até certo ponto como, por exemplo, para [;1 \leq n \leq 8;], a fórmula abaixo fornece os [;8;] primeiros números primos em ordem crescente:

[;P_n=2+{n-1 \choose 1}+{n-1 \choose 2}-{n-1 \choose 3}+3{n-1 \choose 4}-9{n-1 \choose 5}+23{n-1 \choose 6}-53{n-1 \choose 7};]

Os coeficientes [;2;], [;1;], [;-1;], [;3;], etc, desta fórmula combinativa se conseguem a partir dos [;8;] primeiros primos usando o triângulo das variações, conforme o artigo Progressão Aritmética de Ordem Superior


Fermat [;(1601-1665);] tinha conjecturado que [;F(n)=2^{2^n}+1;] é primo para qualquer inteiro não-negativo [;n;]. No entanto Euler, em [;1732;], descobriu que [;F(5)=2^{2^5}+1=641.6700417;] e, portanto, composto.

Legendre observou que [;n^2+n+17;] é primo para [;0 \leq n \leq 16;] e que [;2n^2+29;]  é primo para [;0 \leq n \leq 28;]. Euler mostrou que [;n^2-n+41;]  é primo para [;0 \leq n \leq 40;] . [;n^2-79n+1601;] é primo para [;0 \leq n \leq 79;].

Em face da limitação algébrica dada por Legendre, os matemáticos voltaram-se para a estratégia de pesquisar sobre a distribuição média dos primos ao longo dos números naturais. O que se queria, na verdade, era achar uma função que indicasse a quantidade de primos menores que um dado inteiro positivo [;n;] e em função de [;n;] . Esta lei ou regra ficou conhecida como teorema dos números primos. 

[;\pi (n)=;] quantidade de primos [;\leq n;]


O próprio Legendre, após um exame árduo de uma tabela contendo um grande número de primos, conjecturou que [;\pi(n);] se aproxima de [;\frac{n}{ln (n)-1,08366};] quando [;n;] cresce indefinidamente. Mas Gauss,  na sua adolescência em [;1792;]  e usando a mesma técnica, foi mais longe ao anotar em seu pequeno caderno de memórias matemáticas o seguinte limite

[;\pi(n)=\lim_{n \rightarrow \infty};] [;\frac{n}{ln (n)};]


E isto é equivalente  a afirmar que

[;\lim_{n \rightarrow \infty};] [;\frac {\pi (n)}{n/ln(n)}=1;]


No entanto, nem mesmo o grande Gauss conseguiu provar sua própria conjectura.


Esforços matemáticos foram feitos no sentido de que em [;1850;], o matemático russo Chebyshev demonstrou que

[;\frac{7}{8}< \frac{\pi(n)}{n/ln(n)}<\frac{9}{8};], válido quando [;n \rightarrow \infty;].



Riemann, em [;1859;], em um artigo de nove páginas, esboçou um caminho para uma prova mas foi inconclusivo. Mas esta luz foi importantíssima para futuros pesquisadores.



Em [;1896;], dois matemáticos, Hadamard e De La Vallée Poussin, trabalhando independentemente mas debruçados sobre os escritos de Riemann, conseguiram finalmente demonstrar que [;\lim_{n \rightarrow \infty};] [;\frac {\pi (n)}{n/ln(n)}=1;] transformando a conjectura de Gauss no tão procurado Teorema dos Números Primos.

Este teorema tem uma interessante interpretação probabilística tendo em vista que se [;n;] crescer indefinidamente,


[;\frac{\pi (n)}{n/ln(n)}=\frac{1/n}{1/n}.\frac {\pi (n)}{n/ln(n)}=\frac{\pi(n)/n}{1/ln(n)}\rightarrow 1 \Rightarrow \frac{\pi (n)}{n}\rightarrow \frac{1}{ln(n);]

A última expressão nos diz que a probabilidade de encontrarmos uma quantidade [;\pi(n);] de números primos no intervalo fechado [;[1,n];] é aproximadamente [;\frac{1}{ln(n);], quando [;n \rightarrow \infty;].

O limite de Gauss não resolve a questão da fórmula fechada do [;n;]-ésimo número primo mas induz à uma estimativa para [;P_n;]  conforme o teorema a seguir.


TEOREMA

Se [;n \rightarrow \infty;], então [;P_n \rightarrow n.ln(n);]

Demostração: nos cálculos abaixo considere sempre  [;n \rightarrow \infty;] e o limite do primeiro membro depois do sinal [;=;].

Seja [;\frac{\pi(n)}{n/ln(n)}=1;]. Como [;\pi(P_n)=n;], temos [;\frac{n}{P_n/ln(P_n)}=1\Rightarrow \frac{P_n}{n.ln(P_n)}=1;]  ( 1 )

Tirando o logaritmo natural de ambos os membros,

[;ln \left[\frac{P_n}{n.ln(P_n)}\right]=ln(1) \Rightarrow ln(P_n)-ln(n)-ln ln (P_n)=0;]

Colocando [;ln(P_n);] em evidência, [;ln(P_n) \left[1-\frac{ln(n)}{ln(P_n)}-\frac{ln ln(P_n)}{ln (P_n)}\right]=0;];

Já que [;ln(P_n) \neq 0;], a expressão entre colchetes tende a [;0;], quando [;n \rightarrow \infty;] .


Mas, recordando que [;\lim_{u \rightarrow \infty}\frac{ln(u)}{u}=0;] o que implica que [;\lim_{n \rightarrow \infty} \frac{ln ln(P_n)}{ln (P_n)}=0;],  a expressão do colchete reduz-se à [;1-\frac{ln(n)}{ln(P_n)}-0 \Rightarrow;] [;\lim_{n \to \infty}\frac{ln(n)}{ln(P_n)}=1;].

Multiplicando este último resultado pelo inverso de ( 1 )

 [;\lim_{n \to \infty};]  [;\frac{ln(n)}{ln(P_n)};]  [;\lim_{n \to \infty};] [;\frac{n.ln(P_n)}{P_n}=1.1\Rightarrow;]
[;\lim_{n \to \infty};] [;\frac{ln(n)}{ln(P_n)};]  [;\frac{n.ln(P_n)}{P_n}=1\Rightarrow;] 

[;\lim_{n \to \infty};]  [;\frac {n.ln(n)}{P_n}=1\Rightarrow;] 

[;\lim_{n \to \infty;]  [;P_n=n.ln(n);] 


 

REFERÊNCIA BIBLIOGRÁFICA 

- Cálculo com Geometria Analítica - Volume 1, de George F.Simmons, Editora McGraw-Hill,1988;
- O que é a Matemática?, de Richard Courant e Herbert Robbins, Editora Moderna, 2000;
- História da Matemática, de Carl B.Boyer, Editora Edgard Blücher LTDA, 1974.

21 comentários:

  1. Li com atenção todo o post, mostrando o desenvolvimento das ideias sobre a distribuição de números primos. Acho que já tinha visto a prova em [;\lim_{n \to \infty P_n=n.ln(n);], mas não lembrava mais. Aqui a demonstração passo a passo foi clara e instrutiva. Seria interessante colocar em uma tabela de 3 colunas: n, pi(n) e P(n) para alguns valores de n. Parabéns pelo excelente post.

    ResponderExcluir
    Respostas
    1. Prof, nesta demonstração que adaptei do livro de George Simmons parece que temos um paradoxo. Na passagem que diz que o limite de ln(n)/ln(Pn)=1 quando n tende ao infinito, isto não sugere que ln(Pn) tende a ln(n) e, portanto, Pn tende a n???

      Excluir
    2. Oi Teixeira! As razões entre logaritmos enganam muito, veja o caso seguinte: (n^n).n/(n^n) fica claro que esta razão tende a infinito quando n tende a infinito, veja agora: ln[(n^n).n]/ln(n^n)={nlnn+lnn}/nlnn=(n+1)/n cujo limite é 1 para n tendendo ao infinito. Obrigado desculpe a intromissão.

      Excluir
    3. Um interessante paradoxo, tavano: infinito=1. Já vi que tem muita habilidade com logaritmos.

      Excluir
  2. Bom dia Aloísio, tudo bem? Mas que maravilha esse artigo heim? Só li nomes de grandes matemáticos. Isso mostra o quão essa função para gerar os números primos era almejada. Bem que o Paulo me avisou para ler o livro do Simmons. No link abaixo tem um pequeno texto, também interessante:
    http://obaricentrodamente.blogspot.com/2010/12/dirichlet-e-os-numeros-primos-de-uma.html

    Um grande abraço!

    ResponderExcluir
    Respostas
    1. Oi, Kleber, o Cálculo I e II de Simmons são extremamentes interessantes. É um tipo de leitura agradável sem muito formalismo mas sem atentar para o rigor. Os apêndices e as notas históricas ao final destes volumes são excelentes. Eu deixei um comentário no post do seu link. Obrigado!

      Excluir
  3. Irei ver este assunto no livro. As vezes, encontramos alguns erros matemáticos em bons livros.

    ResponderExcluir
  4. Oi Teixeira! O que você acha disso?. Seja a^a=x, dizemos então que a é a raiz transcendente de x e escrevemos a=T(x). Seja n=p/lnp => 1/n=lnp/p => e^(1/n)=p^(1/p) =>.....e ^(-1/n)=1/(p^(1/p). Note que o segundo membro é (1/p)^(1/p) e que portanto 1/p=T(e^(-1/n)). Não acha legalzinho?

    ResponderExcluir
  5. Um bela igualdade, TAVANO! É de sua autoria?

    ResponderExcluir
    Respostas
    1. Oi Teixeira! A raiz transcendente é uma invenção minha (ou uma reinvenção).Algumas curiosidades: Os números de 0 a 1 que têm raiz transcendente, em verdade têm duas. Se admitirmos que sabemos calcular a raiz transcendente, equações como x*(e^x)=k ou do tipo x^(x^2)=K ou (e^x)+x=k passam a ser resolúveis "algebricamente". Pode-se provar que T(2) é irracional e daí provarmos que a raiz transcendente de 2 é transcendente no sentido algébrico e daí o nome que pus. Só mais uma coisa parece que a fórmula para números primos passa pela raiz transcendente não acha? Obrigado

      Excluir
    2. Se quizer, mande um e-mail para eu analizar suas idéias. Está convidado para ser um membro de ELEMENTOS.

      Excluir
  6. Oi Teixeira! Em 1997 estive pensando sobre o teorema de Legendre e cheguei ao seguinte: Inicialmente escreverei a==b (mód p) para significar que a é côngruo ou congruente a b módulo p. Seja P um polinômio de grau m com coeficientes inteiros que para todo n natural forneça um número primo. Seja r natural então P(r)=p(primo). Não é difícil provar que para todo k natural P(kp+r)==P(r) mod p basta lembrar que p==0 mod p. Como P(r)==0 mód p então P(kp+r)==0 mód p isso significa que P(kp+r)=qp para algum q, como P só fornece números primos então q=1 para todo k. Observemos agora o polinômio Q(x)=P(x)-p temos que Q(kp+r)=0 para todo k o que indica que Q tem infinitas raízes, isso é absurdo pois Q é de grau m e no máximo poderia ter m raízes, logo não existe P nas condições propostas e assim fica demonstrado o teorema.Obs.: Traballhei só com números positivos para encurtar a demonstração. O que você acha? Obrigado

    ResponderExcluir
  7. Oi, Tavano

    Depois vou colocar isto no papel e te respondo, ok?

    Valeu, obrigado pela participação!

    ResponderExcluir
    Respostas
    1. Oi, amigo, Tavano.Uma coisa não entendi na sua exposição. Se P(8)=13 e p=13, por exemplo, então Q(8)=P(8)-13=0. No entanto, podemos ter Q(9)=P(9)-13 = diferente de zero. A não ser que vc trate p como uma variável que sempre se modifica com P(x). Neste caso, p é função de x. Então eu pergunto: qual a natureza da função p?? Q(x) tem uma natureza misteriosa justamente porque a função p tem natureza misteriosa. Então não se pode dizer que p=Q(x)-P(x) é a diferença de dois polinômios.

      Excluir
    2. O quero dizer é o seguinte: se P(x)é uma função que só fornece primos, então p ( sendo função de x ) é outra função que só fornece números primos. Neste caso, de acordo com vc, em Q(x)=P(x)-p, P(x)=p ( sempre ). Logo, Q(x) é uma função identicamente nula e, se tiver natureza polinomial, tem grau zero.

      Excluir
    3. Oi Teixeira! O p é uma constante. Pelo exemplo seu: P(13k+8)=múltiplo de 13, isto é P(8), P(21), P(34)..etc são todos múltiplos de 13. Há um teorema verdadeiro que diz que se P(r)=p então P(kp+r)=múltiplo de p, daí que caímos no absurdo pois se P só gera números primos por hipótese e P(8), P(21), P(34), P(47) são todos múltiplos de 13 então P(13k+8) só pode ser igual a 13 que é o único múltiplo de 13 que é primo. Resumindo: P só gera primos, P(13k+8) é múltiplo de 13, dessas duas afirmações só podemos tirar uma conclusão P(13k+8)=13 para todo k, nesse caso Q não seria identicamente nula mas, Q(8)=0, Q(21)=0, Q(34)=0 etc. Espero ter sido claro, mas estou à disposição. Obrigado

      Excluir
  8. Oi, Tavano! Agora, entendi, obrigado pela atenção e paciência. Vc perguntou o que eu acho? Brilhante! Simples e conclusivo. E pensar que existiam matemáticos antes da prova de Legendre se matando para encontrar P(n)=só primos...

    ResponderExcluir
  9. Prof. Aloísio, fantástico o seu artigo, parabéns!
    Mas algo me chamou a atenção: No trecho: " Euler mostrou que [;n²-n+41;] é primo para [;0 \leq n \leq 40;], está um pouco confuso. No livro do Du Sautoy - A MÚSICA DOS NÚMEROS PRIMOS, pág 54, afirma ser a equação de Euler n² + n + 41. Estranho que o livro restringe a função para n de 0 a 39, mas aqui vc o restringe até a 40... curioso é que testei ambas as funções e resultaram ambas em números primos nas devidas restrições. Contudo a sua vai mais longe. AFINAL DE CONTAS, QUAL MESMO É A EQUAÇÃO QUE ELE BRINCOU?

    ResponderExcluir
  10. Oi, Edmarcos. Obrigado. Conforme o livro História da Matemática, de Carl B.Boyer, capítulo 22, seção 17, Euler estudou a expressão [;n^2-n+41;] considerando seus valores primos de 1 ao 40. Mas acredito que ele também tenha considerado [;n^2+n+41;], conforme sua fonte.

    Um forte abraço.

    ResponderExcluir
  11. Então pode mesmo ter estudado as duas expressões.
    Muito obrigado Prof. Aloisio

    ResponderExcluir