Primes and Probability

Let $p \mathbb{N}$ denote the set of natural numbers divisible by $p$. It is a simple property of divisibility that we have the relation $p\mathbb{N} \cap q\mathbb{N} = pq\mathbb{N}$ if and only if $p,q$ are coprime; this is simply stating that a number with two coprime divisors is divisible by their product. This simple observation leads to some interesting results in elementary number theory.

It has been established for quite some time that the notion of asymptotic density is a very useful way to quantify the “size” of subsets of the natural numbers – in a much more subtle way than the coarse notion of cardinality. Formally, the asymptotic density $\mu$ is the finitely additive measure $\mu: 2^\mathbb{N} \to \mathbb{R}$ given by

Informally, we are just observing the relative frequency of elements of $A$ in $\mathbb{N}$ as we extend our horizon to infinity. That we have only finite additivity is something of a burden – in general measure theory the countably addivity requirement yields certain continuity results that make measures easy to work with, but in this case it is evident that we cannot hope for countable additivity (consider $\mathbb{N} = \cup_n \{n\}$). Nonetheless, $D(\mathbb{N}) = 1$, so we may consider the density to be a finitely additive probability measure.  and a trivial computation yields what morally should be true: $D(p\mathbb{N}) = 1/p$. In particular, if $p, q$ are distinct prime numbers, then</p>

Thus we are led quickly to see that with respect to the arithmetic density, the “events” of being divisible by distinct primes $p,q$ are independent. It is also straightforward to extend this to show that the independence hnews for the family $\{p\mathbb{N}\}_{p \in P}$, where $P$ denotes the set of prime numbers (recall that independence for more than two events demands not only pairwise independence but in fact that the multiplicative property hnew for all finite subfamilies of events).

As was previously mentioned, the arithmetic density lacks the countable additivity that is typically demanded in probability theory. Rather than work with the density, we will begin to consider which countably additive probability measures on the natural numbers also have $\{p\mathbb{N}\}_{p \in P}$ independent. A significant convenience of working with the natural numbers is that they are countable, and thus we may specify such a probability measure completely by merely defining it on the singletons $\{n\}_{n \in \mathbb{N}}$ (which extends uniquely to $2^\mathbb{N}$ by countably additivity).

If $\mu : 2^\mathbb{N} \to \mathbb{R}$ is a probability measure, then to have $\mu(pq\mathbb{N}) = \mu(p\mathbb{N})\mu(q\mathbb{N})$ we must have

Note that if $\mu(\{ab\}) = \mu(\{a\})\mu(\{b\})$ for all $a,b \in \mathbb{N}$ then the desired independence result hnews. Thus we are led naturally to consider completely multiplicative functions. For suppose $f : \mathbb{N} \to \mathbb{R}$ is positive, $f(ab) = f(a)f(b)$ for all $a,b \in \mathbb{N}$, and $% $. In this case, $\mu$ given by $\mu(\{n\}) = f(n)/c$ is a probability measure with the desired property.

There are many completely multiplicative functions and their study is at the core of number theory. However, our demands rule out many classical functions. In particular, we must have our function $f$ decay sufficiently rapidly so that $% $. As one begins to ponder the natural candidates, it becomes evident that for any fixed $s > 1$, the function $f(x) = x^{-s}$ suffices. Clearly $f$ is multiplicative, and we have the interesting property that

where $\zeta : \mathbb{C} \to \mathbb{C}$ is the Riemann zeta function, defined as $\zeta(s) = \sum_n n^{-s}$.

With this revelation, it is natural to wonder whether independence can shed any light on the nature of the Riemann zeta function. We shall soon confirm that this is indeed the case. We define the probability measure

and, by the above argument, the events $\{p\mathbb{N}\}_{p \in P}$ are independent. Note that $\mu(p\mathbb{N}) = \sum_{n} \mu(\{pn\}) = p^{-s}$.

An important property of independence is that if a family of events is independent, then the complements of those events are independent. This is a straightforward result in Boring Measure Theory, but to hint at its legitimacy (if it isn’t intuitively obvious), consider that for independent events $A,B$ we have

Thus not only is the family $\{ p\mathbb{N}\}_{p \in P}$ independent, but we also have $\{ (p\mathbb{N})^c \}_{p \in P}$ independent (one should note that the event $(p\mathbb{N})^c$ is the event of not being divisible by $p$, so the intersection of these events as $p$ ranges over all primes is simply $\{ 1 \}$).  We use this independence to compute:

Finally, since $\mu(\{1\}) = \zeta(s)^{-1}$, we see that independence establishes the Euler product formula

(One minor remark is that I have implicitly used the continuity of our probability measure to convert the probability of a countable intersection to the countable product of probabilities; independence alone would only allow this for the case where our intersection & product were finite. This is just one example of the convenience of working with countably additive measures – something like this would not have been possible by direct means had we been working with asymptotic density, for example.)

If this is at all interesting to you, I recommend the paper “Combinatorial Snapshots” by Gian-Carlo Rota. He begins with the same considerations, but heads down a different road. Also, check out the amusing book Statistical Independence** in Probability, Analysis and Number Theory by Mark Kac. He covers much more actual number theory, as well as developing some probability in the style of Borel (pre-Kolmogorov).