20050311, 06:33  #1 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 
More trouble in randomness
No claims, just questions! :D
quoted from MathWorld: "The probability that two integers picked at random are relatively prime is [6/pi^{2}]" I think Euler proved this, I would be interested in an outline of the proof if anyone can summarize or point me to a book that has it. My question, however, is how do you randomly pick two integers? 
20050311, 07:22  #2  
Dec 2003
Hopefully Near M48
2×3×293 Posts 
Quote:
What I think is that you randomly pick two integers between 1 and n, where each integer between 1 and n has an equal chance of being picked. Compute the probability that the two integers are relatively prime. Then, take the limit of this probability as n goes to infinity. However, you may want to have someone more knowledgeable confirm this. But I have my own question on this topic: Since zeta(2) = (pi^2)/6, the probability that two integers chosen at random are relatively prime is 1/((pi^2)/6), or 6/pi^2. But can you make the proof run backwards? That is, can you prove through some independent means that the probability is 6/pi^2, and then use that result to conclude that zeta(2) = (pi^2)/6? Last fiddled with by jinydu on 20050311 at 07:24 

20050330, 16:43  #3  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Quote:
Afsaik Euler proved that zeta(2) = pi^2/6 This has been fully proved in the book "Journey through Genius" Chapter 9 by William Dunham (a Penguin book) For the probability formulae this is given in Ch.5 and Ch.8 of the book 'The Mathematical Experience' by Davis and Hersh (and very good explanations too on random integers and the Mobius function). exactly what you want. These books are a must for any math'cian worth his salt. The websites I give are not as good. http://www.fortunecity.com/emachines...6/mathex5.html http://www.mathreference.com/num,mu.html jinydu:Study the 3 chapters mentioned. I conclude that zeta (2) =(pi^2)/6 =(4*9*25*49....)/3*8*24*48....) = 1/(pi^2)/6 Further reading: I.J. Good +R.F. Churchhouse ; M.Kac. ; G. Polya. For Dunham: Weil, Andre, Number theory:An approach through History 1984. Mally 

20050330, 17:19  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:
the entire real number line. 6/pi^2 is the limit as n> oo 

20050330, 18:08  #5 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I guess the analysis should run something like this: if n1 and n2 are chosen independently and uniformly at random from the positive integers <=N, the probability that n1 is divisible by a prime p < n1 is about 1/p, same for n2. Since n1 and n2 were chosen independently, the probability that both are simultaneously divisible by p is 1/p^2, and the probability that at least one is not divisible by p is 1(1/p^2). Also, n1 and n2 are coprime iff for all p<N, at least one of n1 and n2 is not divisible by p. Assuming that the probabilites for different primes to divide n1 (or n2) are independent, we can express the probability that every prime <sqrt(N) doesn't divide both n1 and n2 by the product
\prod{p \in \Primes, p \leq N}} {1p^{2}} For N>oo, this becomes \prod{p \in \Primes} {1p^{2}} which is the reciprocal of the zeta function in Euler's product form at 2: \prod{p \in \Primes} {1/(1p^{2})} which is known to have value Pi^2/6. All good and well, but there is some vagueness in this derivation. Is a number n1 <= N divisible by any p <= n1 with probability 1/p? Does the same hold for p <= N? (Hardly, if n1<<N) And I don't think the events that different primes divide n1 are independent, either... the "Practical Analysis of ECM" paper contains something about that, but I don't have it here. So I'd like to ask: why is this product actually correct? Does the fact that almost all numbers in a given interval are large save the day again by making the error introduced by small n1,n2 vanish? Alex 
20050330, 18:25  #6  
Nov 2003
2^{2}×5×373 Posts 
Quote:
COUNT the number of integers up to n divisible by p. This is n/p, plus potentially a very small error (i.e. how many integers less than 100 are divisible by 3? (33), but this is the same answer as "how many less than 101 are divisible by 3" but 100/3 != 101/3 the *relative* error goes to 0 as n>oo. 

20050330, 18:31  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Thank you!
Alex PS: the <sqrt(N) should be <N, but my edit timed out :( 
20050330, 22:40  #8 
Dec 2003
Hopefully Near M48
6DE_{16} Posts 
So this means that the occurence of 6/pi^2 can be traced back to Euler's product form of the Zeta function?

20050330, 23:07  #9 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
Euler's product form of zeta is what makes the connection between
prod{p \in \Primes} {1/(1p^{2})} and \sum_{k \in \N} {1/k^2} and the latter is long known to have value 1/6 * Pi^2, but I don't know when or by whom that series was discovered. Alex 
20050409, 17:49  #10  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
More trouble in randomness
Quote:
The series adding up to pi^2/6 was first derived by Leonhard Euler about 1734 by a masterful stroke of genius. The Mobius function by Good and Churchhouse which churns out the probability of primes occurring is calculated thus: To calculate m(x) [mu of x] factor x into primes. If there is a repeated factor then m(x) is defined to be zero. If all factors are distinct then count them. If even no. of factors set m(x) =1. If odd then m(x) = 1 Now add up the values of m(x) for all ‘n’ less than or equal to N. This function is called M (N).It has been proved a long time ago that M(N) grows no faster than, and is similar to the Riemann conjecture. Either conjecture implies the other; both of course are still unproven. What is the chance that ‘n’ has no repeated factor i.e. that m(n) is not equal to zero?. This happens for the squares of prime no.s or multiples of 4, 9, 25 etc. Now the probability that a number chosen at random is NOT a multiple of 4 is 3/4, of 9 is 8/9, of 25 is 24/25 and so on. Moreover these conditions are all independent. Hence the probability of occurrence of 2 independent events is their product so M(N) =3/4* 8/9* 24/25 ………. Even tho’ this is an infinite product and not equal to zero this adds up to 6/pi^2. Note pi^2/6 = 1+1/4+1/9+1/25….. its reciprocal. For the Riemann conjecture we should have taken the values of n for no.s 1 to N. Instead we took no.s at random. I leave it to you to reach your own conclusions. References: 1)‘Journey through Genius’ by W. Dunham. 2) The Mathematical Experience by P.J. Davis and R.Hersh. Further Readings: H.Edwards, E Grosswald, G. Polya (1954), I.J. Good and R.F. Churchhouse Mally . 

20050415, 05:11  #11 
∂^{2}ω=0
Sep 2002
República de California
3×53×73 Posts 
...And on the humorous side of randomness:
http://www.cnn.com/2005/TECH/science...eut/index.html IMO, any organization pompous enough to host a "World MultiConference on Systemics, Cybernetics and Informatics" deserves to be hoaxed. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
asm trouble  science_man_88  Programming  52  20101006 21:52 
Randomness  ShiningArcanine  Math  12  20080522 21:52 
Is Entropia in trouble?  ekugimps  PrimeNet  1  20050909 16:18 
What is Randomness and does relative randomness make sense?  sakreha  Data  1  20050204 23:29 
Measuring randomness?  Xyzzy  Math  9  20041206 20:05 