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.

  • $\begingroup$ 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). $\endgroup$ – 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.

  • $\begingroup$ 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. :) $\endgroup$ – Hachino Apr 3 '15 at 7:48
  • $\begingroup$ 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... $\endgroup$ – Benoît Kloeckner Apr 3 '15 at 8:09
  • $\begingroup$ @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)... $\endgroup$ – Qiaochu Yuan Apr 3 '15 at 8:19

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.