mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-03-11, 06:33   #1
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

641 Posts
Default 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?
Orgasmic Troll is offline   Reply With Quote
Old 2005-03-11, 07:22   #2
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

33368 Posts
Default

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
jinydu is offline   Reply With Quote
Old 2005-03-30, 16:43   #3
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

40048 Posts
Lightbulb

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
mfgoode is offline   Reply With Quote
Old 2005-03-30, 17:19   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

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
R.D. Silverman is offline   Reply With Quote
Old 2005-03-30, 18:08   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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}} {1-p^{-2}}

For N->oo, 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<<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
akruppa is offline   Reply With Quote
Old 2005-03-30, 18:25   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-03-30, 18:31   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Thank you!

Alex

PS: the <sqrt(N) should be <N, but my edit timed out :(
akruppa is offline   Reply With Quote
Old 2005-03-30, 22:40   #8
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

110110111102 Posts
Default

So this means that the occurence of 6/pi^2 can be traced back to Euler's product form of the Zeta function?
jinydu is offline   Reply With Quote
Old 2005-03-30, 23:07   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-04-09, 17:49   #10
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Lightbulb 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 .
mfgoode is offline   Reply With Quote
Old 2005-04-15, 05:11   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1165810 Posts
Default

...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.
ewmayer is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
asm trouble science_man_88 Programming 52 2010-10-06 21:52
Randomness ShiningArcanine Math 12 2008-05-22 21:52
Is Entropia in trouble? ekugimps PrimeNet 1 2005-09-09 16:18
What is Randomness and does relative randomness make sense? sakreha Data 1 2005-02-04 23:29
Measuring randomness? Xyzzy Math 9 2004-12-06 20:05

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


Fri Oct 22 01:08:22 UTC 2021 up 90 days, 19:37, 2 users, load averages: 1.14, 1.28, 1.34

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.