I want to know if there exists a measure $\mu$ on the positive integers (equipped with the $\sigma-$algebra of all subsets) satisfying:

1) For all $n > 1$, $\mu(A_n) = 1/n$, where $A_n = \{n, 2n, \ldots \}$ is the multiples of $n$, and

2) The events $A_m, A_n$ are independent when $m$ and $n$ are relatively prime.

If such a measure existed, it would mimic the notion of drawing a "random integer" from all of $\mathbb{N}$, at least with respect to these divisibility properties.

1) and 2) hold approximately for the uniform distribution on $\mathbb{N} \cap [1,X]$ for large $X$; a similar weakening of the question is to use asymptotic density, i.e. define $\mu(A) = \lim_{n \to \infty} \frac{|A \cap \{1, 2, 3, \ldots, n\}|}{n}$, which satisfies 1) and 2) but is not countably additive.

The zeta distribution, given by (for any $s > 1$) the density $\nu_s(n) = \frac{1}{\zeta(s)} n^{-s}$, comes very close: it is an easy check that 2) holds, but $\nu_s(A_n) = n^{-s}$ for all $n$. (Interestingly, as $s \to 1^+$, for a fixed subset $A \subset \mathbb{N}, \nu_s(A)$ converges to the asymptotic density of $A$, if it exists.)

I suspect the answer is that no such measure exists: the fact that the zeta distribution fails makes me think 1 and 2 are somehow at odds.

I believe any $\mu$ satisfying 1) and 2) should have $\mu(\mathbb{N}) = \infty$, but I don't have a proof.


Edit: As people have pointed out, 1) clearly implies 2). (Whoops!) And @Zhoraster has given a nice proof that no measure can exist in this case. Here's what (I think) will be a harder question:

Can we find a measure $\mu$ satisfying

1a) $\mu(A_p) = 1/p$ for primes $p$, and

2a) The events $A_p$ and $A_q$ are independent when $p$ and $q$ are prime.

Now it's not obvious that $1$ and $2$ hold for products of many primes: we do get $\mu(A_{pq}) = 1/pq$ for distinct primes $p$ and $q$, but that's it. I don't think the inclusion-exclusion proof will work as stated, but perhaps a similar idea can be used...

  • $\begingroup$ View $\mu$ as a bounded linear map $l^\infty \to \mathbb{R}$ where $A_n$ is the sequence indicating the multiples of $n$. Then $\mu$ is the natural density. It exists by the Hahn-Banach theorem applied to $l^\infty$, but it may be very strange for weird subsets of $\mathbb{N}$. Also, you can restrict to the closed subspace $E = \{ (a_k) \in l^\infty, \lim_{N \to \infty} \frac{1}{N} \sum_{k=1}^N a_k \text{ exists } \}$ of $l^\infty$, in that case $\mu$ is well-defined. $\endgroup$
    – reuns
    Feb 14 '17 at 10:54
  • 2
    $\begingroup$ As I said in the post, the 'natural density' or 'asymptotic density' is not a measure, since it isn't countably additive. $\endgroup$
    – J Richey
    Feb 14 '17 at 22:00
  • $\begingroup$ As a linear operator, it can be extended to any bounded sequence by Hahn-Banach. Not sure there is much more to say. And try to be more clear next time $\endgroup$
    – reuns
    Feb 14 '17 at 22:44
  • $\begingroup$ The linear operator you're describing is perfectly valid, but it doesn't answer the question, since it doesn't represent a measure. For instance, the natural density of any finite subset of $\mathbb{N}$ (your operator $\mu$ applied to an element of $l^\infty$ with only finitely many non-zero terms) is zero, but the natural density of the infinite union of all even integers is 1/2. As you say, the 'measure' is finitely additive, (or 'linear' as an operator on $l^\infty$), but it isn't countably additive. What is exactly is unclear? I'm happy to clarify further. $\endgroup$
    – J Richey
    Feb 15 '17 at 0:54
  • 1
    $\begingroup$ @Richey By the way, isn't $(2)$ a consequence of $(1)$ ? $\endgroup$
    – charmd
    Feb 18 '17 at 11:09

Such measure doesn't exist. The idea is to show that the only measure satisfying 1 (which, by the way, obviously implies 2) is $$ \mu(\{n\}) = \frac{1}{n\zeta(1)} = 0, n\ge 1, $$ which is a contradiction.

So let $\mu$ satisfy 1. Denote by $\mathbb{P}$ the set of primes. Then, for any $n\in \mathbb N$, we have by the inclusion-exclusion formula (all series below are divergent, but one can proceed by finite approximations) $$ \mu(\{n\}) = \mu(A_n) - \mu\Big(\bigcup_{p\in \mathbb{P}} A_{np}\Big) \\ = \frac{1}{n} - \sum_{p\in \mathbb P}\mu(A_{np}) + \sum_{\substack{p_1,p_2\in \mathbb P\\p_1\neq p_2 }}\mu(A_{np_1}\cap A_{np_2}) - \sum_{\text{distinct } p_1,p_2,p_3\in \mathbb P}\mu(A_{np_1}\cap A_{np_2}\cap A_{np_3}) + \dots \\ = \frac1n + \sum_{k=1}^\infty (-1)^k \sum_{\text{distinct } p_1,p_2,\dots,p_k\in \mathbb P}\mu\Big(\bigcap_{j=1}^k A_{np_j}\Big)\\ = \frac1n + \sum_{k=1}^\infty (-1)^k \sum_{\text{distinct } p_1,p_2,\dots,p_k\in \mathbb P}\mu\Big( A_{np_1p_2\cdots p_k}\Big) \\ = \frac1n + \sum_{k=1}^\infty (-1)^k \sum_{\text{distinct } p_1,p_2,\dots,p_k\in \mathbb P}\frac1{np_1p_2\cdots p_k} = \frac1n\prod_{p\in \mathbb P}\Big(1-\frac{1}{p}\Big) = 0, $$ as claimed.

Similarly, it can be shown that the unique measure satisfying $\mu_s(A_n) = n^{-s}$ with $s>1$ is $$ \mu_s(\{n\})=\frac1n\prod_{p\in \mathbb P}\Big(1-\frac{1}{p^s}\Big) = \frac{1}{n^s \zeta(s)}, n\ge 1. $$

  • $\begingroup$ Great answer which is obviously more appropriate than mine ; minor detail : on your seventh line you wrote twice $\mu (A_n)-\mu \Big( \bigcup \limits_{p \in \mathbb{P}} A_{np} \Big)$ $\endgroup$
    – charmd
    Feb 18 '17 at 14:25
  • $\begingroup$ @charMD, thanks, fixed. $\endgroup$
    – zhoraster
    Feb 18 '17 at 14:42
  • $\begingroup$ Nice solution! I had thought to use this inclusion-exclusion formula, but didn't realize it's (very simple) connection with the zeta function. I added an edit weakening the assumptions a little bit... do you think a similar proof will work in the case where we only assume 1) and 2) hold for distinct primes $p$ and $q$? $\endgroup$
    – J Richey
    Feb 18 '17 at 21:39
  • $\begingroup$ @JRichey If you only assume 1 and 2 for primes then, I think, such measure may be easily constructed. $\endgroup$
    – zhoraster
    Feb 19 '17 at 15:16
  • $\begingroup$ @Zhoraster What do you have in mind? I don't have any ideas on how to construct one. $\endgroup$
    – J Richey
    Feb 19 '17 at 18:33

Such a measure can not be a probability (i.e. we can't have $\mu(\mathbb{N})=1$).

Ad absurdum, suppose we have a probability $P$ satisfying $(1)$, $(2)$.

Let $(p_n)_{n \ge 1}$ be an ordered enumeration of prime numbers. There is no positive integer which has an infinity of prime divisors, and thus $$\bigcap \limits_{n \in \mathbb{N}} \bigcup \limits_{k \ge n} A_{p_k} = \varnothing.$$

Hence $P \Big(\bigcap \limits_{n \in \mathbb{N}} \bigcup \limits_{k \ge n} A_{p_k} \Big) = 0$, so $$P \Big( \bigcup \limits_{n \in \mathbb{N}} \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) > 0.$$

However, $P$ is continuous below so \begin{align*} P \Big( \bigcup \limits_{n \in \mathbb{N}} \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) & = \lim \limits_{n \to \infty} P \Big( \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) \\ & = \lim \limits_{n \to \infty} \prod \limits_{k \ge n} P (\overline{A_{p_k}}) \end{align*}

because $P$ is a probability, the $A_{p_k}$ are mutually independant, and thus so are the $\overline{A_{p_k}}$. Hence \begin{align*} P \Big( \bigcup \limits_{n \in \mathbb{N}} \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) & = \lim \limits_{n \to \infty} \prod \limits_{k \ge n} \Big( 1 - P (A_{p_k}) \Big) \\ & \le \lim \limits_{n \to \infty} \prod \limits_{k \ge n} e^{-P(A_{p_k})} \end{align*}

because $1-x \le e^{-x}$ (convexity inequality). We deduce finally :

$$P \Big( \bigcup \limits_{n \in \mathbb{N}} \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) \le \lim \limits_{n \to \infty} e^{-\sum \limits_{k=1}^n P(A_{p_k})}$$

But $$\sum \limits_{k=1}^n P(A_k) = \sum \limits_{k=1}^n \frac{1}{p_k} \underset{n \to \infty}{\longrightarrow} +\infty$$

(see Divergence sum of reciprocal of primes), so we conclude

$$P \Big( \bigcup \limits_{n \in \mathbb{N}} \bigcap \limits_{k \ge n} \overline{A_{p_k}} \Big) = 0$$

which is absurd. Hence, there is no probability satisfying your conditions.

See Zhoraster's post which provides a better and clearer answer to your question.

  • 1
    $\begingroup$ There are some typos, but essentially it is correct. In fact, you show that for each $n$ the measure of numbers not dividing $p_n,p_{n+1}\dots$ must be zero; as a result, by letting $n\to\infty$, the measure of whole $\mathbb N$ must be zero. The assumption that $\mu$ is a probability measure is not significant, as one can modify the argument for the set of even numbers, not the whole $n$ (my proof is essentially in the very same spirit). $\endgroup$
    – zhoraster
    Feb 18 '17 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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