More trouble in randomness

[Orgasmic Troll]

No claims, just questions! :D

quoted from MathWorld:

"The probability that two integers picked at random are relatively prime is [6/pi²]"

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?

[jinydu]

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?

[mfgoode]

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/pi²]"

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

[R.D. Silverman]

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

[akruppa]

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

[R.D. Silverman]

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.

[akruppa]

Thank you!

Alex

PS: the <sqrt(N) should be <N, but my edit timed out :(

[jinydu]

So this means that the occurence of 6/pi^2 can be traced back to Euler's product form of the Zeta function?

[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

[mfgoode]

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 .

[ewmayer]

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