[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Re: [obm-l] 6/pi^2

To: obm-l@xxxxxxxxxxxxxx
Subject: Re: [obm-l] Re: [obm-l] 6/pi^2
From: Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>
Date: Fri, 28 Mar 2003 22:32:28 -0300 (EST)
In-Reply-To: <BAA8F8FB.252Ülaudio.buffara@terra.com.br> from "Claudio Buffara" at Mar 27, 3 06:52:44 pm
Reply-To: obm-l@xxxxxxxxxxxxxx
Sender: owner-obm-l@xxxxxxxxxxxxxxxxxxxxx
   Caro Claudio,
   Vou tentar comentar as suas observacoes sobre o meu argumento abaixo,
apos as mesmas. Sobre a independencia, pode-se usar o teorema chines dos
restos: modulo p_1.p_2.....p_r (e em qualquer sequencia de k.p_1.p_2...._p_r
inteiros consecutivos), os eventos do tipo "ser multiplo de p_i" sao
independentes. Como soma(1/n^2) converge, dado eps > 0 existe N natural tal
que soma(p primo,p>N)(1/p^2) < eps. Pela observacao acima, o conjunto dos
pares de naturais (m,n) tais que mdc(m,n) nao tem nenhum fator primo p <= N
tem densidade igual ao produto sobre todos os primos p <= N de (1-1/p^2).
Como o conjunto dos (m,n) tais que mdc(m,n) tem algum fator primo maior que
N tem densidade no maximo soma(p primo,p>N)(1/p^2) < eps, segue o resultado.
   Abracos,
           Gugu

P.S.:Viu, Dirichlet ? Nao foi preciso recorrer a nenhum livro em ingles...    

>
>Caro Gugu:
>
>Obrigado pela explanacao. Apesar de nao conhecer alguns detalhes (vide
>abaixo), deu pra entender a ideia geral. Vou consultar alguns livros de
>teoria dos numeros pra tentar preencher as lacunas.
>
>Um abraco,
>Claudio.
>
>on 27.03.03 17:22, Carlos Gustavo Tamm de Araujo Moreira at gugu@impa.br
>wrote:
>
>> Caro Claudio,
>> A interpretacao mais usual e' tomar A igual a um quadrado (como
>> {m,n inteiros | 1<=m,n<=N}).
>realmente, deve simplificar as contas comparado com um disco...
>
>> O argumento do Claudio Buffara pode ser
>> formalizado. 
>Ainda bem! Um ponto do meu argumento (ou melhor, do argumento que eu
>reproduzi abaixo - nao sei quem eh o autor original) que me incomoda eh a
>hipotese implicita da independencia estatistica quando eu escrevo:
>P(p e q nao dividem m) = P(p nao divide m)*P(q nao divide m)
>Intuitivamente faz sentido, mas como se formaliza este argumento?
>
>> Ai vai outro: o problema, nesse caso e' equivalente a estimar o
>> numero de pares (m,n) com mdc(m,n)=1 e 1<=m<=n<=N (isso vai ser essencialmente
>> a metade de #(pontos visiveis pertencentes ao conjunto A).
>
>> Nosso problema
>> agora e' estimar soma(n=1 ate' N)(phi(n))=
>
>> =soma(n=1 ate' N)(soma(d divide n)(mu(d).n/d))=
>ate aqui OK. Ambas as somas dao n(1-1/p1)(1-1/p2)...

De fato, foi so' aqui que usamos inversao de Mobius, a partir do fato de
que, para todo n, soma(d divide n)(phi(d))=n.

>   
>> =soma(d=1 ate' N)(mu(d).soma(j=1 ate' [N/d])(j))=
>esse tipo de inversao de Mobius eu nao conhecia...

Isso nao e' inversao de Mobius: para cada d com 1<=d<=N, eu so' agrupei os
termos na expressao anterior em que d aparece.

>
>> =soma(d=1 ate' N)(mu(d).[N/d].([N/d]+1)/2=
>
>> =N^2.soma(d=1 ate' N)(mu(d)/d^2)/2+O(N.log(N))=
>preciso checar essa estimativa tambem

Aqui o N.log(N) vem do erro que cometemos tirando as partes inteiras (e'
O(soma(d=1 ate' N)(N/d)) ).

>
>> =N^2.soma(d=1 ate' infinito)(mu(d)/d^2)/2+O(N.log(N))=
>
>> =(3/Pi^2).N^2+O(N.log(N)), o que prova o resultado (para ver que
>
>> soma(d=1 ate' infinito)(mu(d)/d^2)=6/Pi^2, basta ver que
>
>> soma(d=1 ate' infinito)(mu(d)/d^2).soma(d=1 ate' infinito)(1/d^2)=
>
>> =soma(m=1 ate' infinito)((soma(d divide m)(mu(d))/m^2)=1).
>de novo a tal variante da inversao de Mobius, agora com uma soma infinita...

Aqui tambem nao e' inversao de Mobius: ao desenvolver o produto notamos que
todos os denominadores sao da forma 1/m^2, e agrupamos os que tem o mesmo
denominador.

>
>> Essa estimativa tambem da' o mesmo limite para outras escolhas de A, como
>> os seus quartos de disco, com um pouco mais de trabalho (por exemplo
>> aproximando A por unioes de retangulos, como no calculo de integrais de
>> Riemann)...
>
>> Abracos,
>> Gugu
>> 
>>> 
>>> Oi, JP e Helder:
>>> 
>>> Mas n?o ? verdade que o ponto (m,n) ? vis?vel a partir da origem se e
>>> somente se mdc(m,n) = 1?
>>> 
>>> Depois, como voc? define densidade do conjunto de pontos vis?veis?
>>> Eu acho que tem que ser o limite de algum quociente do tipo:
>>> #(pontos vis?veis pertencentes a um conjunto A) / #(pontos de A)
>>> onde A ? algo como um disco contendo a origem e cujo raio tende a infinito.
>>> Ou seja, bem parecido com a defini??o de probabilidade como o limite de uma
>>> frequ?ncia relativa.
>>> 
>>> Assim, eu acho que se a interpreta??o probabil?stica n?o for rigorosa, a
>>> interpreta??o como densidade tamb?m n?o ser?.
>>> 
>>> Ser? que algu?m na lista pode formalizar este problema?
>>> 
>>> Um abra?o,
>>> Claudio.
>>> 
>>> 
>>> ----- Original Message -----
>>> From: <peterdirichlet1985@zipmail.com.br>
>>> To: <obm-l@mat.puc-rio.br>
>>> Sent: Thursday, March 27, 2003 1:14 PM
>>> Subject: [obm-l] Re: [obm-l] 6/pi^2
>>> 
>>> 
>>>> Esse e o Helder Toshiro que conhe?o!!!!!!!So devo dizer uma coisa:esse
>>> resultado
>>>> nao e rigoroso,e a demonstra?ao "real" disso ai consiste em considerar os
>>>> pontos visiveis da origem do reticulado N*N e sua densidade.Basicamente
>>>> 2 pontos quaisquer desse reticulado infinito sao ditos visiveis entre si
>>>> quando o segmento reto que os liga nao contem outro ponto alem dos ditos.
>>>> A densidade desse conjunto seria o porcentual de espa?o que ele ocupa em
>>>> rela?ao aos outros.Demonstrando que a densidade e
>>>> 6/(pi)? acaba.Grosso modo a probabilidade e so uma interpreta?ao.
>>>> 
>>>> -- Mensagem original --
>>>> 
>>>>> on 26.03.03 23:16, Helder Suzuki at heldersuzuki@yahoo.com.br wrote:
>>>>> 
>>>>>> Se dois n?meros naturais e distintos s?o escolhidos
>>>>>> aleatoriamente, prove que a chance de esses n?meros
>>>>>> n?o terem nenhum fator em comum ? 6/pi^2?
>>>>>> 
>>>>> 
>>>>> Caro Helder:
>>>>> 
>>>>> Esse eh um resultado interessante, apesar de ser bem conhecido.
>>>>> 
>>>>> Dados os numeros A e B, para cada primo p chame de P(p) a probabilidade
>>>> de
>>>>> A
>>>>> e B serem ambos multiplos de p.
>>>>> 
>>>>> Assim, P(p) = 1/p^2 e
>>>>> 1 - P(p) = 1 - 1/p^2 = probabilidade de que A e B nao tenham o fator
>>> primo
>>>>> p
>>>>> em comum.
>>>>> 
>>>>> A partir disso, concluimos que:
>>>>> P(A e B primos entre si) =
>>>>> 
>>>>> (1 - P(2))*(1 - P(3))*(1 - P(5))*(1 - P(7))*... =
>>>>> 
>>>>> PRODUTORIO (1 - P(p)) =
>>>>> p primo
>>>>> 
>>>>> PRODUTORIO (1 - 1/p^2)
>>>>> p primo
>>>>> 
>>>>> Pela formula da soma de uma PG infinita (com razao de modulo < 1),
>>> teremos:
>>>>> 1 - 1/p^2 = 1/(1 + 1/p^2 + 1/p^4 + 1/p^6 + ... )
>>>>> 
>>>>> Assim,
>>>>> PRODUTORIO (1 - 1/p^2) =
>>>>> p primo
>>>>> 
>>>>> = 1 / PRODUTORIO (1 + 1/p^2 + 1/p^4 + ... )
>>>>> p primo
>>>>> 
>>>>> Mas o produtorio no denominador eh justamente igual a:
>>>>> infinito
>>>>> SOMATORIO 1/n^2
>>>>> n = 1
>>>>> 
>>>>> pois se a decomposicao de n em fatores primos eh:
>>>>> 
>>>>> n = p1^a1 * p2^a2 * ... * pk^ak, entao:
>>>>> 
>>>>> 1/n^2 = 1/p1^(2*a1) * 1/p2^(2*a2) * ... * 1/pk^(2*ak)
>>>>> 
>>>>> e o membro da direita aparece exatamente uma vez no desenvolvimento de
>>>>> PRODUTORIO (1 + 1/p^2 + 1/p^4 + ... )
>>>>> p primo
>>>>> 
>>>>> Alem disso, o valor de:
>>>>> infinito
>>>>> SOMATORIO 1/n^2
>>>>> n = 1
>>>>> eh justamente Pi^2/6 (isso pode ser provado via series de Fourier, por
>>>>> exemplo)
>>>>> 
>>>>> Logo,
>>>>> PRODUTORIO (1 + 1/p^2 + 1/p^4 + ... ) = Pi^2/6
>>>>> p primo
>>>>> 
>>>>> e, portanto,
>>>>> P(A e B primos etre si) = 1/PRODUTORIO = 6/Pi^2.
>>>>> 
>>>>> 
>>>>> Um abraco,
>>>>> Claudio.
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> =========================================================================
>>>>> Instru??es para entrar na lista, sair da lista e usar a lista em
>>>>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>>>> O administrador desta lista ? <nicolau@mat.puc-rio.br>
>>>>> =========================================================================
>>>>> 
>>>> 
>>>> TEA WITH ME THAT I BOOK YOUR FACE
>>>> 
>>>> 
>>>> ------------------------------------------
>>>> Use o melhor sistema de busca da Internet
>>>> Radar UOL - http://www.radaruol.com.br
>>>> 
>>>> 
>>>> 
>>>> =========================================================================
>>>> Instru??es para entrar na lista, sair da lista e usar a lista em
>>>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>>> O administrador desta lista ? <nicolau@mat.puc-rio.br>
>>>> =========================================================================
>>> 
>>> =========================================================================
>>> Instru??es para entrar na lista, sair da lista e usar a lista em
>>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>> O administrador desta lista ? <nicolau@mat.puc-rio.br>
>>> =========================================================================
>> 
>> =========================================================================
>> Instru??es para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>> O administrador desta lista ? <nicolau@mat.puc-rio.br>
>> =========================================================================
>> 
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================
Follow-Ups:
- Re: [obm-l] Re: [obm-l] 6/pi^2
  - From: Claudio Buffara
Prev by Date: Re: [obm-l] ajuda
Next by Date: Re: [obm-l] fracoes parciais
Prev by thread: RE: [obm-l] Re: [obm-l] 6/pi^2
Next by thread: Re: [obm-l] Re: [obm-l] 6/pi^2
Index(es):
- Date
- Thread