Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

As observed on Mathworld, "Amazingly, the probabilities for random pairs of integers and Gaussian integers being relatively prime are the same as the asymptotic densities of squarefree integers of these types" (respectively, 6/π2 and 6/π2K where K is Catalan's constant).

This seems to me unlikely to be a coincidence. Is there a deeper reason - or at least, a proof of this fact which is not equivalent to evaluating both probabilities and observing that they are equal?

share|improve this question
    
Fix a finite set S of primes. I would guess that the density of numbers whose prime factors come only from S gets pretty small, so that (in a handwaving sense) picking numbers which "avoid S" is the same as picking squarefree numbers which are coprime to the product of elements of S. So I can see (or hallucinate, if not communicate) a strong connection between chance of coprimality and chance of finite sets of primes intersecting. Perhaps someone will come along to say clearly what I mean for both of us. Gerhard "Ask Me About System Design" Paseman, 2010.08.08 –  Gerhard Paseman Aug 9 '10 at 6:21
add comment

3 Answers

To spell out what Robin said at a more basic level (blame me if this is inapt): Consider a given prime p. The chance that a "random integer" does not divide by $p^2$ is $1-1/p^2$. So heuristically the probability that the random integer is square free is the product of $1-1/p^2$ over all primes. Making that precise is not too hard. That this comes out to be $6/\pi^2$ is kind of amazing. But it is not so amazing that the probability to be relatively prime is the same: given a "random pair" of integers, the chance that they do not both divide by p is the same $1-1/p^2$.

It would be cute to match up pairs (a,b) with integers n so that the set P of prime divisors of gcd(a,b) is the same as the set of primes whose square divides n. But it is not immediate to me how to do that.

share|improve this answer
add comment

These probabilities equal $\zeta(2)^{-1}$ and $\zeta_{\mathbb{Q}(i)}(2)^{-1}$ where $\zeta$ is the Riemann zeta-function and $\zeta_K$ is the Dedekind zeta function for the number field $K$. The proof for each of the integers and the Gaussian integers shows that each probability equals the value above, via the Euler product for the appropriate zeta function.

share|improve this answer
add comment

Another heuristic explanation. Denote $m_1,m_2,\dots$ all mutually non-equivalent non-zero not-invertible elements of $\mathbb{Z}$ or $\mathbb{Z}[i]$ (equivalent elements are those whose ratio is invertible). So, for $\mathbb{Z}$ these are (for example) $1,2,3,\dots$, for $\mathbb{Z}[i]$: $1+i$, $2$, $2+i$, $1+2i$, $\dots$

Denote by $p$ the probability that two random numbers are coprime. Then what is probability that two numbers have gcd equal to $m_k$? Of course, $p/|m_k|^2$. Sum up by $k$, we get a probability that two numbers have some gcd, i.e. we get 1. So, $1=p\sum 1/|m_k|^2$.

Denote by $q$ the probability that $n$ is squarefree. What is probability that $n$ is of form $m_k^2 n'$ for squarefree $n'$? Of course, $q/|m_k^2|$. Then sum up and get $1=q\sum 1/|m_k|^2$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.