mersenneforum.org > Math More trouble in randomness
 Register FAQ Search Today's Posts Mark Forums Read

 2005-03-11, 06:33 #1 Orgasmic Troll 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/pi2]" 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?
2005-03-11, 07:22   #2
jinydu

Dec 2003
Hopefully Near M48

2×3×293 Posts

Quote:
 Originally Posted by TravisT My question, however, is how do you randomly pick two integers?
Well, I don't know the answer to your first question, but I can make a guess on this one.

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 2005-03-11 at 07:24

2005-03-30, 16:43   #3
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22×33×19 Posts

Quote:
 Originally Posted by TravisT No claims, just questions! :D quoted from MathWorld: "The probability that two integers picked at random are relatively prime is [6/pi2]" 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?

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

2005-03-30, 17:19   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by jinydu Well, I don't know the answer to your first question, but I can make a guess on this one. 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.
Yes. This is exactly correct. There does not exist a uniform distribution on
the entire real number line. 6/pi^2 is the limit as n--> oo

 2005-03-30, 18:08 #5 akruppa     "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 poo, this becomes \prod{p \in \Primes} {1-p^{-2}} which is the reciprocal of the zeta function in Euler's product form at 2: \prod{p \in \Primes} {1/(1-p^{-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<
2005-03-30, 18:25   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa 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
In a word, yes. Instead of treating the probabilities directly, instead just
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.

 2005-03-30, 18:31 #7 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Thank you! Alex PS: the
 2005-03-30, 22:40 #8 jinydu     Dec 2003 Hopefully Near M48 6DE16 Posts So this means that the occurence of 6/pi^2 can be traced back to Euler's product form of the Zeta function?
 2005-03-30, 23:07 #9 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts Euler's product form of zeta is what makes the connection between prod{p \in \Primes} {1/(1-p^{-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
2005-04-09, 17:49   #10
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts
More trouble in randomness

Quote:
 Originally Posted by akruppa Euler's product form of zeta is what makes the connection between prod{p \in \Primes} {1/(1-p^{-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

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 .

 2005-04-15, 05:11 #11 ewmayer ∂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 Multi-Conference on Systemics, Cybernetics and Informatics" deserves to be hoaxed.

 Similar Threads Thread Thread Starter Forum Replies Last Post science_man_88 Programming 52 2010-10-06 21:52 ShiningArcanine Math 12 2008-05-22 21:52 ekugimps PrimeNet 1 2005-09-09 16:18 sakreha Data 1 2005-02-04 23:29 Xyzzy Math 9 2004-12-06 20:05

All times are UTC. The time now is 08:49.

Tue Mar 2 08:49:23 UTC 2021 up 89 days, 5 hrs, 0 users, load averages: 0.64, 0.91, 1.09