5
$\begingroup$

I know that $\zeta(n) = \displaystyle\sum_{k=1}^\infty \frac{1}{k^n}$ (Where $\zeta(n)$ is the Riemann zeta function)

But the reciprocal of $\zeta(n)$ for $n$ a positive integer is equal to the probability that $n$ numbers chossen at random are relatively prime. But why? Can you give a proof?

$\endgroup$
9
  • $\begingroup$ What does it mean, the ''probability that $n$ numbers are relatively prime''? Under what probability distribution? i.e., in what sense? $\endgroup$ Commented Jun 3, 2013 at 23:53
  • $\begingroup$ @PatrickDaSilva I added the chosen at random part! $\endgroup$ Commented Jun 3, 2013 at 23:59
  • 5
    $\begingroup$ ....I insist ; what does it mean to choose at random? Does it mean you choose uniformly in $[1,N]$ with $N$ large? Because then $\frac 1{\zeta(n)}$ can only be an asymptotic for the actual probability, since it will depend on that large $N$. If you really do choose something over $\mathbb N$ at random, then you need to define the probability distribution because otherwise no one can tell. $\endgroup$ Commented Jun 4, 2013 at 0:01
  • $\begingroup$ @PatrickDaSilva I mean, if you get n numbers at random between 1 and x where x tends to infinity, the probability they will be relatively prime is equal to 1/ζ(n) $\endgroup$ Commented Jun 4, 2013 at 0:10
  • $\begingroup$ Okay so you do choose them uniformly in the interval $[1,x]$, but the probability that those $n$ integers will be relatively prime, call it $p_n(x)$, will be like this : $p_n(x) = \frac 1{\zeta(n)} + O(f(x))$ for some function of $x$ going to zero as $x \to \infty$. $\endgroup$ Commented Jun 4, 2013 at 0:31

2 Answers 2

5
$\begingroup$

Here is a very rough sketch of the idea :

We have the following : $$ \zeta(n) = \sum_{k \ge 1} \frac 1{k^n} = \sum_{k \ge 1} \prod_{p^{k_p} || k} \frac 1{(p^n)^{k_p} } = \prod_{p} \sum_{k \ge 0} \left( \frac 1{p^n} \right)^k = \prod_{p} \frac 1{1-\frac 1{p^n}}. $$ (You need to work out the details for all the convergence issues and these are treated in pretty much all good elementary number theory books.)

Now if we choose $k_1, \dots, k_n$ integers independently and uniformly over the interval $[1,x]$, one roughly expects that $p | k_i$ with probability $1/p$. The fact that $(k_1,\dots,k_n) = 1$ means that there is no prime which divides all those integers at once. $p$ divides $k_1, \dots, k_n$ with probability $1/p^n$ assuming independence, hence the probability we are looking for is roughly $$ \prod_{p \le x} \left( 1 - \frac 1{p^n} \right) \underset{x \to \infty}{\longrightarrow} \prod_p \left( 1 - \frac 1{p^n} \right) = \frac 1{\zeta(n)}. $$ You probably need to understand better what happens when $p$ is relatively large compared to $x$ to work out the error terms, but the basic ideas are all here.

Hope that helps,

$\endgroup$
4
$\begingroup$

Here's a very simple heuristic that gives some motivation for why $\zeta(k)$ appears. Fix a $k$ and let $P$ be the limiting probability that a tuple in $[1,x]^k$ is relatively prime. Then, when $x$ is large, about $P x^k$ of the tuples in $[1,x]^k$ have gcd equal to $1$. How many have gcd equal to $2$? Well, after dividing through by 2 we get a relatively prime tuple, but it lives in $[1,\frac{x}2]^k$. Well, $\frac{x}2$ is still pretty large so we should have about $P (\frac{x}2)^k$ of those. Likewise, about $P(\frac{x}3)^k$ tuples should have a gcd of $3$, and in general we'd predict $P(\frac{x}{d})^k$ tuples having gcd $d$.

Now, there are $x^k$ tuples in $[1,x]^k$ and each has a unique gcd $d$, and so by sorting tuples according to the value of $d$ we get the approximate equality:

$$x^k \approx Px^k + P(\frac{x}2)^k + P(\frac{x}3)^k + \cdots = Px^k \big( 1 + \frac1{2^k} + \frac1{3^k} + \frac1{4^k} + \cdots \big),$$

and there's your $\zeta(k)$: we get $P\zeta(k) \approx 1$, so that $P \approx 1/\zeta(k)$.

[Caveat: the reason this is only a heuristic is that as we start to take $d$ larger the box $[1,x/d]^k$ is getting smaller, making this approximation less accurate. But at the same time its contribution to the sum is getting smaller than smaller, which mitigates the loss of accuracy. These are not insurmountable problems but they are created to some extent by the fact that this is only a limiting probability and not a true probability as pointed out in the comments.]

$\endgroup$
1
  • $\begingroup$ I think this approach is more accurate if we try to work out the error terms to be honest... but I haven't tried, so this is just my guts speaking! $\endgroup$ Commented Jun 4, 2013 at 19:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .