# Natural probability on integers

This is a follow-up to this classical question asked recently here: we know (e.g. using the second Borel-Cantelli Lemma) that no probability measure on $\mathbb{Z}$ has the property that $n\mathbb{Z}$ has mass $\frac1n$. The argument I know of makes use of an independence property induced by the formulation of the problem: $p_1\dots p_k \mathbb{Z} = p_1\mathbb{Z} \cap\dots\cap p_k\mathbb{Z}$ has measure $1/(p_1\dots p_k)= (1/p_1)\dots(1/p_k)$.

This question was looking to a weakened notion of "uniform" measure on $\mathbb{Z}$: one would even like better that every class $\mod n$ has mass $\frac1n$, but this is trivially impossible.

Here comes my question:

Does there exist a probability measure on $\mathbb{Z}$, such that for all $n\in\mathbb{N}$ there is at least one class $\mod n$ which has mass $\frac1n$?

this weakening should destroy the independence above, and thus prevents applying Borel-Cantelli.

• Nice question! I tinkered with it for a bit and I can't even make up my mind whether to conjecture that the answer is yes or no. While tinkering I did manage to show that for the original question it suffices that the events "a random integer is divisible by $p$" are pairwise independent rather than independent (it's a straightforward application of Chebyshev's inequality). – Qiaochu Yuan Apr 2 '15 at 21:22

Here are examples showing that unlike in the previous problem, here it does not suffice to simply use the fact that the harmonic series / the sum of the reciprocals of the primes diverges. In fact for all $s > 1$ there exists a probability measure on $\mathbb{Z}$ such that for all $n \in \mathbb{N}$ there is at least one class $\bmod n$ which has mass

$$\frac{1}{n} + O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

where the constant depends on $s$ (and the same will be true for other big-Os appearing in this argument). Note that the exponent $1 + \frac{1}{s}$ can get arbitrarily close to $2$. With some more annoying examples I can do very slightly better than this but I still can't reach an exponent of $2$. So let me propose the following companion problem, a negative answer to which would also answer your problem in the negative:

Does there exist a probability measure on $\mathbb{Z}$ such that for all $n \in \mathbb{N}$ there is at least one class $\bmod n$ which has mass $\frac{1}{n} + O \left( \frac{1}{n^2} \right)$?

Now for the examples. What we'll actually work with is a probability distribution on $\mathbb{N}$, but this can straightforwardly be converted to a probability distribution on $\mathbb{Z}$ by setting the mass of a nonpositive integer to be $0$. The distribution in question is just the zeta distribution which also appears in the other question; that is, if $X$ denotes a random positive integer then we have

$$\mathbb{P}(X = k) = \frac{1}{\zeta(s) k^s}.$$

The zeta distribution has the property that the numbers $\mathbb{P}(X \equiv a \bmod n)$ are monotonically decreasing, where $a \in \{ 0, 1, \dots, n - 1 \}$, and since they sum to $1$ it follows that they begin at a value $\ge \frac{1}{n}$ and end at a value $\le \frac{1}{n}$. We'll try to find a value of $a$ for which $\mathbb{P}(X \equiv a \bmod n)$ is close to $\frac{1}{n}$ as follows. First, we'll bound the differences between the sums

$$\zeta_{a, n}(s) = \sum_{k \equiv a \bmod n} \frac{1}{k^s} = \mathbb{P}(X \equiv a \bmod n) \zeta(s).$$

We have

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) = \sum_{k \equiv a \bmod n} \left( \frac{1}{k^s} - \frac{1}{(k+1)^s} \right).$$

Each term in the sum is bounded by

$$\begin{eqnarray*} \frac{1}{k^s} - \frac{1}{(k+1)^s} &=& \frac{1}{k^s} \left( 1 - \left( \frac{k}{k+1} \right)^s \right) \\ &=& \frac{1}{k^s} \left( 1 - e^{-s \log \frac{k+1}{k}} \right) \\ &\le& \frac{1}{k^s} \left( s \log \left( 1 + \frac{1}{k} \right) \right) \\ &\le& \frac{s}{k^{s+1}} \end{eqnarray*}$$

where we use the inequality $e^x \ge 1 + x$ twice, first in the form $1 - e^x \le -x$ and second in the form $\log (1 + x) \le x$. It follows that

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) \le \sum_{k \equiv a \bmod n} \frac{s}{k^{s+1}} \le \frac{s}{a^{s+1}} + \sum_{n \mid k} \frac{s}{k^{s+1}} \le \frac{s}{a^{s+1}} + \frac{s}{n^{s+1}} \zeta(s + 1).$$

This bound is monotonically decreasing as a function of $a$, and now our goal is to find out how large we can take $a$ and still guarantee that $\mathbb{P}(a, n) \ge \frac{1}{n}$. Using the very crude lower bound

$$\zeta_{a, n}(s) \ge \frac{1}{a^s}$$

we see that it suffices to require

$$\frac{1}{a^s} \ge \frac{1}{n} \zeta(s) \Leftrightarrow a \le \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }.$$

For $a \ge \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }$ it now follows that

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) \le \frac{s \zeta(s)^{ \frac{s + 1}{s}}}{n^{ \frac{s+1}{s} } } + \frac{s}{n^{s+1}} \zeta(s+1) = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

and hence that

$$\mathbb{P}(X \equiv a \bmod n) - \mathbb{P}(X \equiv a + 1 \bmod n) = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right).$$

Hence for $a \ge \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }$ the sequence $\mathbb{P}(X \equiv a \bmod n)$ begins at a value $\ge \frac{1}{n}$, ends at a value $\le \frac{1}{n}$, while changing by at most the RHS above. It follows that there is some $a$ in this range for which

$$\left| \mathbb{P}(X \equiv a \bmod n) - \frac{1}{n} \right| = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

as desired.

• I remember having read somewhere that the sequence of probability measures associated to $\zeta(s)$ does have some limit when $s$ goes to $1$. Don't know whether this is a trivial fact or if any intersting/explicit properties of this limit are known, but anyway, this might help you getting rid of the $\frac 1s$ you hate so much. :) – Hachino Apr 3 '15 at 7:48
• I guess that by using even more barely convergent series like $\sum n^{-1}(\log n)^{-s}$ or $\sum n^{-1}(\log n)^{-1}(\log\log n)^{-s}$, you can get smaller remainders... – Benoît Kloeckner Apr 3 '15 at 8:09
• @Benoît: yes, but I couldn't get $O \left( \frac{1}{n^2} \right)$ this way using the above argument. I can get, for example, $O \left( \frac{1}{n^2 (\log n)^{-2s}} \right)$ (or something like that)... – Qiaochu Yuan Apr 3 '15 at 8:19