using distribution of primes to generate random bits?

Question

In his popular science book The Music of the Primes, Marcus du Sautoy tries to link the truth of the Riemann Hypothesis to the "randomness" of the primes. To do this, he invokes the idea of a "fair coin". This, he claims that probability theory tells us, must satisfy an asymptotic relation whereby the cumulative difference between the number of heads and the number of tails should be $o(x^{1/2})$. He then proposes the difficult-to-visualise idea of a "prime number die" with $\ln n$ sides, so that the probability of each $n$ being prime is $1/\ln n$. And he states that this die will be "fair" if and only if the RH is true. His attempted explanation is necessarily vague and impressionistic, relying on the fact the RH is equivalent to $li(x) - \pi(x)$ being $o(x^{1/2+\epsilon})$ for any positive epsilon (similarly for $\psi(x) - x$, or the Mertens function), and then trying to explain $o(x^{1/2})$ in terms people are familiar with (an unbiased coin toss).

I was wondering if something like this could be made more precise. Suppose we define the increasing sequence $x_k$ for $k =0,1,2,3,...$ where $x_0 = 2$ and $Li(x_{k}) - Li(x_{k-1}) = 0.5$ (that is, $\int_{x_{k-1}}^{x_k} dx/ln x = 0.5$). The idea is that each interval $(x_{k-1},x_k]$ has a 0.5 probability of containing a prime number (taking the density of primes to be $1/ln x$ as usual).

So we then have a "random bit generator": $b_n = 0$ if there's no prime in $(x_{n-1},x_n]$ and $b_n = 1$ if there's at least one prime in the interval.

So would this sequence of bits pass the test for "unbiasedness" which du Sautoy refers to?

We could consider $2H(\pi(x_n)-\pi(x_{n-1})) - 1$ where $H(x)$ is the variation of the Heaviside function which is 1 for positive $x$ and 0 for nonpositive $x$. This will produce the value +1 if there are primes in the interval, and -1 if there are none. So we sum these values and ask: is this $o(x^{1/2})$?

My guess would be that the RH will be equivalent to this function being $o(x^{1/2+\epsilon})$ for any positive $\epsilon$. Any thoughts on this?

Answer 1

Gerhard Paseman in the end convinced me there is something to answer here, so blame him or thank him (depending on you opinion on the answer).

The question seems to be whether the $b_i$ 'behave like a random sequence' In the sense that the difference between the commultative frequency of values $0$ and $1$ for $i \le x$ is 'small', with the rough meaning something square-root-ish (the details in the question are not quite consistent). The second questions seems to be a rescaled version (to $\pm 1$ instead of $0,1$) to be able to express this via summing.

The answer to this is (in all likelihood) a clear 'no', indeed I tend to think the question is based on a false premise. The 'in all likelihood' is due to the fact that I only give a rough reasoning to make the point, and do not really work this out for the primes (this is not a claim I could do this, but if ever the claim in the question were true the distribution of the primes would be so different than what is expected, and not at all random-like with is the punch-line of the question).

The problem is that the $x_k$ are defined in some way with the motivation that some interval should have the property of 'ha[ving] a 0.5 probability of containing a prime number'; and thus it is assumed that the $b_i$ takes values $0$ and $1$ about equally often.

Yet this is not at all like this in case things were 'random.' The expected number of the primes is such an interval should be $1/2$ but this is something else.

To illustrated this with a simple example: if one were to say role a four-sided die and consider the outcome as 'prime' if one gets a $1$ so in a quater of all cases and then the anaolg to the definition in the question choice for the length of an interval would be $2$. However, if one then partitions this sequence into intervalls of length $2$ then one will expect that $9/16$ of the intervalls contain no such 'prime' (corresponding to $b_i=0$).

Also, this not (only) an effect for the small interval size. For an $n$-sided die one one would get an intervall length of $n/2$ and the intervall would not contain any prime with propabilty $(1-1/n)^{n/2}$, so converging to $1/ \sqrt{e}$, which is not $1/2$. The logarithm should be sufficiently 'constant' that I do not expect much difference in the outcome, in any case there is no reason the analog will be $1/2$.

So the $b_i$ should not have the same propabilty of having value $0$ and $1$ and the difference of the frequency-count should be about linear in $x$.

Answer 2

Here is a relevant reference:

http://arxiv.org/pdf/math/0603450