Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a really natural question for which I know a stunning solution. So I admit I have a solution, however I would like to see if anybody will come up with something different. The question is

What is the probability that two numbers randomly chosen are coprime?

More formally, calculate the limit as $n\to\infty$ of the probability that two randomly chosen numbers, both less than $n$ are coprime.

share|improve this question
5  
I think you will find this disappointing, but this problem is no secret: see here, here, and here. And I clicked only the first 3-4 links. ;) Actually, to be fair, some work has to be done to make the arguments in the wikipedia page rigorous, but that isn't the stunning part anyway. That said, let's see how many different proofs exist. –  Srivatsan Sep 14 '11 at 14:46
    
ah.. ok :( i thought it was something less known. Well, seems i was wrong... it is not stunning anymore now :).. btw thanks for the references –  uforoboa Sep 14 '11 at 14:48
2  
@user15453 I didn't mean that this is not a stunning problem. It is very much so, and it's good to see that you find it so fascinating. The point that I wanted to convey was simply: it's more well-known that you seem to imagine. (That will be especially true in this site than (say) among your friends, since many people here do a lot more mathematics.) And I didn't mean to discourage you from learning such interesting things. On the contrary, I hope this will turn up lot of good answers (like, Eric's answer below). –  Srivatsan Sep 14 '11 at 15:52
add comment

1 Answer

up vote 18 down vote accepted

Lets look at the function $$S(x)=\sum_{\begin{array}{c} m,n\leq x\\ \gcd(m,n)=1\end{array}}1.$$

Then notice that $$S(x)=\sum_{m,n\leq x}\sum_{d|\gcd(m,n)}\mu(d)=\sum_{d\leq x}\sum_{r,s\leq\frac{x}{d}}\mu(d)= \sum_{d\leq x}\mu(d)\left[\frac{x}{d}\right]^{2}$$

From here it is straight forward to see that in the limit, $$\frac{S(x)}{x^2}\rightarrow\sum_{n=1}^\infty \frac{\mu(n)}{n^2}=\frac{1}{\zeta(2)}=\frac{6}{\pi^2}.$$

However, there are still some interesting questions here. How fast does in converge, and what are the secondary terms? It turns out we can easily relate this to the summatory totient function, which has a rich history. See these two math stack exchange posts: Totient function, Asymptotic formula. What follows below is a modification of my answer on the second post.

The History Of The Error Term

In 1874, Mertens proved that $$S(x)=\frac{6}{\pi^{2}}x^{2}+O\left(x\log x\right).$$ Throughout we use $E(x)=S(x)-\frac{6}{\pi^2}x^2$ for the error function.

The best unconditional result is given by Walfisz 1963: $$E(x)\ll x\left(\log x\right)^{\frac{2}{3}}\left(\log\log x\right)^{\frac{4}{3}}.$$

In 1930, Chowla and Pillai showed this cannot be improved much more, and that $E(x)$ is not $$o\left(x\log\log\log x\right).$$

In particular, they showed that $\sum_{n\leq x}E(n)\sim\frac{3}{\pi^{2}}x^{2}$ so that $E(n)\asymp n$ on average. In 1950, Erdos and Shapiro proved that there exists $c$ such that for infinitely many positive integers $N,M$ we have $$E(N)>cN\log\log\log\log N\ \ \text{and}\ \ E(M)<-cM\log\log\log\log M, $$

or more concisely

$$E(x)=\Omega_{\pm}\left(x\log\log\log\log x\right).$$

In 1987 Montgomery improved this to

$$E(x)=\Omega_{\pm}\left(x\sqrt{\log\log x}\right).$$

Hope you enjoyed that,

Added: At some point, I wrote a long blog post about this, complete with a proof of Montgomery's lower bound.

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.