Re: [obm-l] Re: [obm-l] 6/pi^2

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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)...
   
> =soma(d=1 ate' N)(mu(d).soma(j=1 ate' [N/d])(j))=
esse tipo de inversao de Mobius eu nao conhecia...

> =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

> =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...

> 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>
=========================================================================