MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\Lambda(n)$ be the von Mangoldt function. The prime number theorem is equivalent to the statement that $\sum_{n \leq N} \Lambda(n) \approx N$. Defining $\lambda_{*}(n)= \Lambda(n)-1$ we may rewrite this as $S(N) = \sum_{n \leq N} \Lambda_{*}(n) =o(N)$. Now it is known that $|S(N)| \gg |N|^{1/2}$ infinitely often. Moreover, on the RH we have that $|S(N)| \ll N^{1/2}ln^2(N)$. Not that these estimates differ by a factor of $ln^2(N)$.

My question is the following: What do probabilistic considerations suggest the correct error term to be?

Let me suggest a model: Let $X_n$ be a sequence of independent random variables such that $X_n = \ln(n)-1$ with probability 1/ln(n) and $-1$ with probability $1-1/ln(n)$, and form the sum $T(N)= \sum_{n=1}^{N} X_n$. Is there an elementary function $E(N)$ such that $ \lim sup_N |T(N)|/E(n) = 1 $ holds almost surely?

Notice that if the primes had positive density in the integers and we adjusted our model accordingly the law of the iterated logarithm would allow us to take $E(N)$ to be a multiple of $|N|^{1/2}\ln\ln(N)$.

(More generally, I'm interested in understanding sums of the above form (that is independent random variables with slowly increases variance) if you know of an appropriate reference.)

share|cite|improve this question
up vote 6 down vote accepted

Let $P_n$ be independent variables which are 1 with probability $1/\log n$ and $0$ with probability $1-1/\log n$ and let $$ \Pi(x) = \sum_{n\leq x} P_n.$$

Then Cram\'{e}r showed that, almost surely,

$$ \limsup_{x\rightarrow \infty} \frac{|\Pi(x)-\ell i(x)|}{\sqrt{2x}\sqrt{\frac{\log\log x}{\log x}}} = 1 $$


$$\ell i (x) = \int_2^x \frac{dt}{\log t}.$$

See page 20 here:

Edit: H. L. Montgomery has given an unpublished probabilistic argument that suggests

$$ \limsup_{x\rightarrow \infty} \frac{|\psi(x)-x|}{\sqrt{x} (\log\log\log x)^2} = \frac{1}{2\pi}.$$

This is announced in: H.L. Montgomery, "The zeta function and prime numbers," Proceedings of the Queen's Number Theory Conference, 1979, Queen's Univ., Kingston, Ont., 1980, 1-31.

share|cite|improve this answer

Cramer's model is well-known to be (provably) a little bit off from the truth (See Maier's work on short gaps between primes). There is a different probabilistic model that you can use. It is motivated by the following equivalent form of the Riemann Hypothesis: $$ \text{RH true} \iff \sum_{n \leq X} \mu(n) \ll_{\varepsilon} X^{1/2 + \varepsilon} $$ for every fixed $\varepsilon > 0$, where $\mu$ is the the Moebius function. Motivated by this equivalence, we consider the following problem: Let $X_p$ be a sequence of independent random variable with $\mathbb{P}(X_p = 1) = \mathbb{P}(X_p = -1) = 1/2$ and for squarefree $n = p_1 \ldots p_k$ define $$ X_n = X_{p_1} \ldots X_{p_k} $$ What almost-sure bounds for $$ \sum_{n \leq X} X_n $$ can we obtain? It turns out that this is a difficult problem in it's own right. But a few results are known. It was known for a long time (since Wintner) that $$ \sum_{n \leq X} X_n \ll_{\varepsilon} X^{1/2 + \varepsilon} $$ almost surely and Halasz improved this to bound to an $\ll X^{1/2} \exp(C \sqrt{\log\log X})$ (Halasz proved a slightly weaker bound but his method can be used to obtain the bound stated here). So you could say that this model suggests a bound of $X^{1/2} \exp(C \sqrt{\log\log X})$ for partial sums of the Moebius function, but the difference between $X_n$ and $\mu(n)$ turns out surprisingly to be too stricking to believe that this is the truth. However, the model itself certainly deserves more study!

As a post-scriptum, let me mention that the best known bound (assuming RH) for the Partial sums of $\mu(n)$ is $C \cdot X^{1/2} \exp(\sqrt{\log X} (\log\log X)^{14})$ (see

share|cite|improve this answer
Thank you for the comments. I don't think Maier's work should have much impact on the question. Maier located (a very sparse collection) of small intervals with more/less primes than expected. However, since these intervals are small and sparse the contribution from all of these primes is minor to the (best possible) error term. – Mark Lewko Sep 11 '10 at 22:34
So, I thought that Maier's work "contradicted" Cramer's model, because (if I recall correctly) Cramer's model predict that all small intervals (by small, I mean some power of log x) should have just the right number of primes, that is ~ h / log x, where h is the size of the interval. Also, I think that the error term for the difference between pi(x) and li(x), as predicted by Cramer's model, can be proven to be false (i.e pi(x) - li(x) = Omega(sqrt(x)). Finally, I wonder, what prompted you in the direction of this question? – anon Sep 14 '10 at 3:51
Maier's work was also surprising, because, probably as you know, Selberg has proven earlier that (assuming RH) "almost all" intervals of size (log x)^{2} contain just the right amount of primes. – anon Sep 14 '10 at 3:52
Oups ... I would like to point out that anon = kukuriku :-) – anon Sep 14 '10 at 3:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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