13
$\begingroup$

The basic question that I have is in the title, but let us make it more rigorous below.

Let $N=\{1, 2, ..., n\}$, and put the (normalized) counting measure, $\mu_n$, on $N\times N$.

Let $\mathcal{S}_n= \{ (a, b)\in N\times N: gcd(a, b)=1\}$

and $x_n=\mu_n(\mathcal{S}_n).$

Then what is the assymptotic behavior of $x_n$ as $n\rightarrow\infty$.

$\endgroup$
22
$\begingroup$

The probability tends to $\frac{1}{\zeta(2)}=\frac{6}{\pi^2}$ as was mentioned by Qiaochu. This actually generalizes to arbitrary number fields, and is a less commonly known fact.

In fact in any number field, the probability that two ideals are relatively prime is given by $1/\zeta_K(2)$, where $\zeta_K$ is the Dedekind zeta function of the number field $K$. And is proven in a similar way to the classical result. Here is a reference: "The probability of relative primality of Gaussian integers". For example the analogous probability for Gaussian integers is $6/(\pi^2G)$ where $G=1-\frac{1}{3^2}+\frac{1}{5^2}+\cdots$ is the Catalan constant.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ A reference for the general "less commonly known fact" is Schanuel, S.H.: Heights in number fields, Bull. Soc. Math. France 107 (1979), 433–449. It is true also using field elements in place of ideals. A function-field analogue was announced by Serre in Lectures on the Mordell-Weil Theorem (F. Vieweg & Sohn, Braunschweig 1989) and proved independently but in the same way by S.DiPippo (Spaces of Rational Functions on Curves Over Finite Fields, Ph.D. Thesis, Harvard, 1990) and D.Wan (Heights and Zeta Functions in Function Fields, in The Arithmetic of Function Fields (1992)... $\endgroup$ – Noam D. Elkies May 16 '12 at 1:24
  • 1
    $\begingroup$ ...... likewise $1/\zeta_K(n)$ is the probability that $n>1$ ideals or field elements have no common factor. This also lets you asymptotically count rational points up to a given height in projective space over $K$. Here's why I had to look up these references some years ago: arxiv.org/pdf/math/0104115v1.pdf $\endgroup$ – Noam D. Elkies May 16 '12 at 1:26
13
$\begingroup$

This is a very standard counting problem in analytic number theory. Here's a rigorous proof: It is enough to derive an asymptotic formula for $$\sum_{a,b\leq n, (a,b)=1} 1 $$ This is $$\sum_{a,b\leq n, d|a, d|b} \mu(d) $$ $$=\sum_{d\leq n} \mu(d)\sum_{k\leq n/d , l\leq n/d} 1$$ $$=\sum_{d\leq n} \mu(d) ((n/d)^2 + O(n/d) ) $$ $$=n^2\sum_{d\leq n} \mu(d)/d^2 + O(n\log n)$$ $$=n^2\sum_{d=1}^{\infty} \mu(d)/d^2 + O(n) + O(n\log n)$$. $$=n^2 6/\pi^2 + O(n\log n).$$

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

The probability is $\frac{6}{\pi^2} = \frac{1}{\zeta(2)}$. A sketch of a proof can be found in this blog post (actually I only show, more or less, that if the density exists it must be $\frac{6}{\pi^2}$).

| cite | improve this answer | |
$\endgroup$

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