Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We know that $$ \sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x) $$

where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy $$ \sum_{p \le x}\frac{1}{p} = \ln\ln x + M + O(1/\ln x). $$

Thus both these divergent series grow at the same rate. Mertens' theorem was proved without using the prime number theorem, some 25 years before PNT was proved. However from these two examples, we cannot conclude that

$$ \lim_{n \to \infty} \frac{p_n}{n\ln n} = 1 $$ otherwise Mertens' would have been the first to prove PNT. My question is - based on the above two series, what are the technical difficulties that prevent us from reaching the conclusion that $p_n/n\ln n = 1$. There may be counter examples with other series, so such conclusions may not be true in general. However I am not interested in the general case. Instead I am asking only in case of the sequence $1/n\ln n$ and $1/p_n$.

share|improve this question
The error in Merten's theorem is $O(1/\log x)$, not $O(1/x)$. I suspect that $O(1/x)$ is not true. –  David Speyer May 2 '12 at 12:59
Indeed, I suspect that standard techniques (Landau's theorem) prove that the error term in Mertens's theorem is $\Omega(x^{-1/2})$; perhaps Littlewood's technique might even give $\Omega_\pm(x^{-1/2}\log\log\log x)$. –  Greg Martin May 2 '12 at 17:47
@Greg: See my response for a precise estimate. –  GH from MO May 3 '12 at 2:38
Incidentally, Mertens did give a proof of $\zeta(1+it)=0\implies \zeta(1+2it)=\infty$ based on his 3-4-1 inequality (this was after the proofs of Hadamard and de la Vallee Poussin). So in some sense he could prove PNT. :) –  Gjergji Zaimi May 4 '12 at 7:08
Well, I'm sure that grammar correction was well worth resurrecting this question for. –  Yemon Choi 9 hours ago

3 Answers 3

up vote 52 down vote accepted

Here is a heuristic that I plan to make into a blog post some day. Suppose that there were only finitely many primes with first digit $9$. Is your estimate good enough to see that?

To be more precise, suppose that there were no primes between $9 \times 10^k$ and $10^{k+1}$ for all sufficiently large $k$. And suppose that the number of primes between $a$ and $b$, for $10^k \leq a < b \leq 9 \times 10^k$ is $\approx \frac{\log 10}{\log 9} \int_{a}^b dt/\log t$ (when $a$ is not too close to $b$). We'll see later where the fraction $\log 10/\log 9$ comes from.

The first thing to note is that this would violate the prime number theorem. In this scenario, we would have $\pi(9 \times 10^k) = \pi(10 \times 10^k)$ for $k$ large. But the prime number theorem says that $$\pi(10\times 10^k) - \pi(9 \times 10^k) \sim \frac{10 \times 10^k}{k \log 10 + \log {10}} - \frac{9 \times 10^k}{k \log 10 + \log {9}} \sim \frac{10^k}{k \log 10} \to \infty.$$ So proving the prime number theorem involves disproving this ridiculous scenario.

Now, let's see that the scenario is consistent with $\sum_{p \leq N} 1/p = \log \log N + M + O(1/\log N)$. The sum over the primes between $10^k$ and $10^{k+1}$ would be roughly $$\frac{\log 10}{\log 9} \int_{10^k}^{9 \times 10^k} \frac{dt}{t \log t} = \frac{\log 10}{\log 9} \left( \log \log (9 \times 10^k) - \log \log 10^k \right)$$ $$=\frac{\log 10}{\log 9} \left( \log( k \log 10+\log 9) - \log (k \log 10) \right) = \frac{\log 10}{\log 9} \left( \log \left( 1+\frac{\log 9}{k \log 10} \right) \right) $$ $$ = \frac{\log 10}{\log 9} \frac{\log 9}{k \log 10} + O(1/k^2)= \frac{1}{k} + O(1/k^2)$$

So $$\sum_{p \leq 10^{n+1}} \frac{1}{p} = \sum_{j=1}^n \left( \frac{1}{j} + O(1/j^2) \right)=$$ $$\log n + B + O(1/n) = \log \log 10^{n+1} + C + O(1/\log 10^{n+1}).$$ Very important exercise left for you: If you redo this computation for $\sum_{p \leq 9 \times 10^k} 1/p$, you get $\log \log (9 \times 10^k) + C + O(1/\log(9 \times 10^k))$ for the same constant $C$. The point is that $\log \log 10^{k+1} - \log \log (9 \times 10^k) = O(1/\log 10^k)$, so this estitmate is consistent with $\sum_{p \leq N} 1/p$ not growing at all between $9 \times 10^k$ and $10 \times 10^k$.

This trick is useful for refuting other simple approaches to the PNT. For example, the "primes hate to start with $9$ scenario" is also consistent with $\sum \log p/p^s = 1/(s-1) + O(1)$ as $s \to 1^{+}$, so that is also not enough to prove PNT.

share|improve this answer
See also my response. –  GH from MO May 3 '12 at 2:35
Indeed, one can view the known proofs of the prime number theorem as methodically isolating and then eliminating such "conspiracies" among the primes. In particular, by working either with the zeroes of the zeta function or with Selberg's explicit formula, one soon finds that the only conspiracy that can really cause trouble is if primes p hate having $p^{it}$ stray far from the negative axis, for some non-zero real $t$... but then $p^{2it}$ stays too close to the positive real axis, which one can show is in contradiction with the conditional convergence of $n^{2it}/n$. –  Terry Tao May 4 '12 at 6:53
Or, one can use sieve theory to stop $p^{it}$ clustering near the negative axis too often (this is how the Erdos-Selberg elementary proof goes). –  Terry Tao May 4 '12 at 6:54
To connect Terry's comment and my post, having no primes between $9 \times 10^k$ and $10 \times 10^k$ is the same as having $p^{2 \pi i/\log 10}$ avoid a certain wedge in $\mathbb{C}$. I just find it easier to think "how would such and such sum behave if no primes started with $9$" then "how would it behave if $\mathrm{arg}(p^{it})$ was never near $\pi$?" –  David Speyer May 4 '12 at 17:13

Let me supplement David Speyer's nice response by elaborating on his original comment and Greg Martin's comment. Let us write $$ \sum_{p\leq x}\frac{1}{p}=\ln\ln x+M+R(x), $$ then we have, using Riemann-Stieltjes integrals, $$ F(x):=\sum_{x < p \leq 2x} \frac{\ln p}{p}=\int_x^{2x}\ln t\ d(\ln\ln t+M) + \int_x^{2x} \ln(t) dR(t) $$ $$ = \int_x^{2x} \frac{dt}{t} + [R(t)\ln t]_x^{2x} - \int_x^{2x} \frac{R(t)}{t} dt = \ln 2 + O( \ln x \sup_{x < t \leq 2x} R(t) ). $$ If $\hat F(s)$ denotes the Mellin transform of $dF(x)$, then with the notation $$ S(x):=\sum_{p \leq x} \frac{\ln p}{p} $$ we have $$ \hat F(s) = \int_{1-}^\infty x^{-s}dS(2x) - \int_{2-}^\infty x^{-s}dS(x) = (2^s-1)\sum_p \frac{\ln p}{p^{s+1}}, \quad \Re s>0. $$ In particular, if $\zeta(s)$ has a zero on $\Re s=\sigma\geq\frac{1}{2}$, then $\hat F(s)$ has a pole on $\Re s=\sigma -1$. Note that on the real segment $s\geq-\frac{1}{2}$, the only singularity of $\hat F(s)$ is $s=-\frac{1}{2}$, coming from the difference between $\sum (\ln p)p^{-s}$ and $\sum\Lambda(n)n^{-s}$. Hence by a well-known principle (see Theorem 11.8 in Bateman-Diamond: Analytic number theory), for a certain $c\in\mathbb{R}$ we infer the two-sided estimates $$ F(x)-\ln 2-c x^{-1/2} = \Omega_\pm(x^{\sigma-1}). $$ This implies, by our initial calculation, $$ R(x) = \Omega(x^{\sigma-1}/\ln x). $$ Here we can take $\sigma=\frac{1}{2}$. In the unlikely case that RH fails, we can choose a larger $\sigma$ and replace $\Omega$ by $\Omega_\pm$. Probably, with more work, we could replace $\Omega$ by $\Omega_\pm$ for $\sigma=\frac{1}{2}$ as well.

EDIT 1. I inserted the term $c x^{-1/2}$ to account for the pole at $s=-\frac{1}{2}$.

EDIT 2. I deleted the comment regarding a possible multiple zero of $\zeta(s)$, since the corresponding zero of $-\zeta'(s)/\zeta(s)=\sum\Lambda(n)n^{-s}$ is always simple.

share|improve this answer

Thanks to David very interesting remark and GH for the calculation of R(x). I like to present my reasoning why I thought on the Merten's theorem could imply PNT. I would have put it as a comment but due to the length, I am writing as a reply. In all likely hood, I must have committed an error somewhere hence I am reaching the ridiculous conclusion that Merten's theorem implies PNT. I would appreciate if someone tell me where I went wrong.

Let $s(n)$ be a strictly increasing sequence, $s(1) \ge 2$, such that $$ S_s(x) = \sum_{s(r) \le x}\frac{1}{s(r)} = \ln\ln x + C_s + R_s(x). $$ where $C_s$ is a constant that depends only on $s$ and $R_s(x) = o(1)$ is the error term which depends on $s$ and $x$. Let $A=\{[s(1)],[s(2)], [s(3)], \ldots \}$ where [.] denotes the greatest integer function. Let $a(r) = 1$ if $r \in A$ and $a(r) = 0$ if $r \notin A$. Then $N_s(x) = \sum_{r \le x} a(r)$ is the number of elements of $A$ in the interval $(0,x)$. Using Abel's summation formula we obtain $$ \sum_{s(r) \le x}\frac{1}{s(r)} = \frac{N_s(x)}{x} + \int_{s(1)}^{x} \frac{N_s(t)}{t^2}dt = \ln\ln x + C_s + R_s(x) $$ Differentiating under the integral sign with respect to $x$, we obtain $$ \frac{N_s'(x)}{x} - \frac{N_s(x)}{x^2} + \frac{N_s(x)}{x^2} = \frac{1}{x\ln x} + R_s'(x) $$ Simplifying the above equation and integrating both sides, we obtain $$ N_s(x) = \int_{s(1)}^{x}\frac{dt}{\ln t} + \int_{s(1)}^{x} tR_s'(t)dt $$ Without loss of generality, we can define $s(1) =2$ as this will only effect the constant term $C_s$ and not $R_s(x)$. Hence we have $$ N_s(x) = \int_{2}^{x}\frac{dt}{\ln t} + E(x) = Li(x) + E(x). $$ Thus any sequence $s(n)$ satisfying $S_s(x) = \ln\ln x + C_s + R_s(x)$ must have a density function which is asymptotic to the logarithmic integral. We can verify this with the sequences $n\ln n, n\ln n + n\ln\ln n, nH_n$ etc; where $H_n$ is the harmonic number. Also we have found the explicit relationship between the error term in $S_s(x)$ and that of $N_s(x)$ which is $$ E(x) = \int_{2}^{x} tR_s'(t)dt $$

In case of prime numbers, $N_s(x) = \pi (x)$ and Merten's theorem shows that primes satisfy the condition on $S_s(x)$. This gives $$ \pi(x) = \int_{2}^{x}\frac{dt}{\ln t} + E(x). $$

This shows that the fact that $\pi(x) \sim Li(x)$ is a consequence of $S_p(x) \sim \ln\ln x$ and it is not a unique property of primes. In fact it is a common attribute of a general family of sequences which grow at the same asymptotic rate in their dominant term. Primes happen to be just one sequence in this family. What differentiates primes and other members of this family of sequences form each other is difference in their respective error terms $E(x)$ or in terms of $S_s(x)$ the difference in their respective constant terms $C_s$ and their error terms $R_s(x)$. Therefore the correct way to interpret Merten's theorem is that for prime numbers, the constant term in $S_p(x)$ is $$ C_p = M = \gamma + \sum_{k=2}^{\infty} \frac{\mu (k)\ln \zeta(k)}{k} \simeq 0.2614972128 $$ because if it were any other constant, then we know that we are dealing with some other sequence and not the sequence of primes even though the dominant term in asymptotic expansion of the sum of the reciprocal of the sequence would still be $\ln\ln x$ and its density would still be asymptotic to $Li(x)$.

share|improve this answer
First a minor note: $R$ and $N$ aren't actually differentiable functions; they have jump discontinuities at integers. But you can fix that by replacing $R'(x)$ by $(R(x+h)-R(x))/h$ where $h$ is much smaller than $x$ but much larger than $1$. I'll refer to $R'$ below, but what I really mean is "the size of $(R(x+h)-R(x))/h$" for $h$ in the right range. –  David Speyer May 4 '12 at 16:50
The problem is that $R$ small does not force $R'$ small. In the scenario of my answer, $R(x) = O(1/\log x)$. Between $9 \times 10^k$ and $10 \times 10^k$, the function $R$ changes by $\log \log (10 \times 10^k) - \log \log (9 \times 10^k) \approx c/\log 10^{k+1}$, where $c$ is a constant I don't care to work out. So $R' \approx c/(10^k \log 10^{k+1})$ or $R'(x) \approx c/(x \log x)$. For $10^k < x < 9 \times 10^k$, you get $R'(x) \approx d/(x \log x)$, for a different constant $d$. (continued) –  David Speyer May 4 '12 at 16:57
So, $|R'(x)|$ is of the same order as $d (\log \log x)/dx = 1/(x \log x)$, even though $R(x) << \log \log x$. When you compute $N(t) = \int t d(\log \log t)/dt \cdot dt + \int t R'(t) dt$, the two terms are of the same order of magnitude, and you have no control over $N(t)$. –  David Speyer May 4 '12 at 17:07
@ David, Thank you for the explanation. Now the gap is clear to me. I have accepted your answer as the answer to this question. –  Nilotpal Sinha May 6 '12 at 7:04

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.