# Link/summary proof of Chebyshev statement: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n$ as $n\to\infty$?

I saw reference to this result of Chebyshev's: $$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty$$ and its relation to the Prime Number Theorem. I'm looking into an information-theory proof by Kontoyiannis (pdf). I was wondering if anyone could give me a sense for how difficult or involved the usual proof is.

I don't really need to see the whole thing in detail, more wondering about the general difficulty/complexity of the result. Thanks!

-
@b01024: Use \to to get $\to$. – Arturo Magidin Apr 20 '11 at 2:50
Not an answer, but a reference to the "usual" proof: it's Theorem 4.10 in Apostol, Introduction to Analytic Number Theory. Also 3rd part of Lemma 4.8 in Bateman and Diamond, Analytic Number Theory, where it's attributed to Mertens. And it's Theorem 425 in Hardy and Wright, An Introduction to the Theory of Numbers, 6th edition. – Gerry Myerson Apr 20 '11 at 3:21
The proof in the paper you linked is quite simple. The upper bound is almost trivial, and the lower bound is only a little involved, using the same trick as Lemma 1 in Eric's answer. – Yuval Filmus Apr 20 '11 at 6:36

The result is fairly elementary. Lets prove it now:

Recall some common definitions: Let $\theta(x)=\sum_{p\leq x} \log p$, let $\Lambda(n)$ be the Von Mangoldt lambda function and let $\psi(x)=\sum_{n\leq x} \Lambda(n)$

Then as $\log n =\sum_{d|n} \Lambda(n)$ we see that $$\sum_{n\leq x} \log n=\sum_{n\leq x}\sum_{d|n} \Lambda(d)=\sum_{d\leq x} \Lambda(d)\lfloor x/d\rfloor =x\sum_{d\leq x} \frac{\Lambda(d)}{d}+O\left(\psi(x) \right)$$

Lemma 1: $\theta(x)\leq 3x$

The proof of this is postponed until the end.

Now, since $\theta(x)=\psi (x)+O(\sqrt{x})$, we have $\psi(x)=O(x)$. Combining this with the fact that $\sum_{n\leq x} \log n= x\log x + O(x)$ we see that $$\sum_{d\leq x} \frac{\Lambda(d)}{d}=\log x+O(1).$$ Since the sum over all the prime powers of $\frac{\Lambda(d)}{d}$ is bounded by a constant, we conclude $$\sum_{p\leq x}\frac{\log p}{p}=\log x+O(1).$$

Hope that helps,

Proof of Lemma 1:

Consider the binomial coefficient $$\binom{2N}{N}.$$ Notice that every prime in the interval $(N,2N]$ appears in the numerator. Then $$\prod_{N<p\leq2N}p\leq\binom{2N}{N}$$ Since $$\binom{2N}{N}\leq(1+1)^{2N}=4^{N},$$ we see that $$\prod_{N<p\leq2N}p\leq4^{N},$$ and hence $\theta(2N)-\theta(N)\leq N\log4.$ Consider $N$ of the form $N=2^{r}.$ Then we get the list of inequalities: $$\theta\left(2\right)-\theta\left(1\right)\leq\log4$$ $$\theta\left(4\right)-\theta\left(2\right)\leq2\log4$$

$$\theta\left(8\right)-\theta\left(4\right)\leq4\log4$$

$$\theta(2^{r})-\theta\left(2^{r-1}\right)\leq2^{r-1}\log4$$ $$\theta\left(2^{r+1}\right)-\theta\left(2^{r}\right)\leq2^{r}\log4.$$

Summing all of these yields $$\theta\left(2^{r+1}\right)-\theta\left(1\right)\leq\left(2^{r}+\cdots+1\right)\log4\leq2^{r+1}\log4$$ for each $r$. For every $x$ in the interval $(2^{r},2^{r+1}]$ we have $\theta(x)\leq\theta(2^{r+1})$ so that $$\theta(x)\leq2^{r+1}\log4\leq x\cdot2\log4<3x$$ since $x>2^{r}$. Thus the result is proven.

-
 I understand, though it took a little re-reading. Thanks very much! – bo1024 Apr 20 '11 at 13:38

This is an application of the Shapiro -Tauberian theorem. Please see Tom Apostol's "Introduction to Analytic Number theory'' text.

Theorem: Let $\{a(n)\}$ be a non negative sequence such that

• $\displaystyle\sum\limits_{n \leq x }a(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$ for all $x \geq 1$.

Then

• For $x \geq 1$ we have $$\sum\limits_{ n \leq x} \frac{a(n)}{n} = \log{x} + \mathcal{O}(1)$$

• There is a constant $A >0$ and an $x_{0} > 0$ such that $$\sum\limits_{ n \leq x} a(n) \leq Bx$$ for all $x \geq 1$.

• There is a constant $A>0$ and an $x_{0}>0$ such that $$\sum\limits_{ n \leq x} a(n) \geq Ax$$ for all $x \geq x_{0}$.

Lemma 1. We have $$\sum\limits_{n \leq x} \Lambda(n) \biggl[\frac{x}{n}\biggr] = \log[x]!$$ where $\Lambda(n)$ denotes the Von-Mangoldt function which is defined as $$\Lambda(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n=p^{m} \ \text{for some prime} \ p \\\ 0 & \text{otherwise}\end{array}$$

Proof. \begin{align*} \sum\limits_{n \leq x}\Lambda(n) \biggl[\frac{x}{n}\biggr] =\sum\limits_{n \leq x}\sum\limits_{d \mid n} \Lambda(d)=\sum\limits_{n \leq x } \log{n} = \log[x]! \quad \biggl[ \because \sum\limits_{d \mid n} \Lambda(d) = \log{n} \ \biggr] \end{align*}

Lemma 2. $\displaystyle \sum\limits_{n \leq x} \Lambda(n)\biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(\log{x})$.

Proof. Taking $f(t) = \log{t}$ in the Euler's Summation formula, we have \begin{align*} \sum\limits_{n \leq x} \log{n} &= \int\limits_{1}^{x} \log{t} \ dt + \int\limits_{1}^{x} \frac{t-[t]}{t}\ dt - ( x -[x])\cdot \log{x} \\\ &= x\log{x} - x + 1 + \int\limits_{1}^{x} \frac{t-[t]}{t} \ dt + \mathcal{O}(\log{x}) \\\ &= x \log{x} + \mathcal{O}(\log{x}) \qquad \Biggl[ \because \int\limits_{1}^{t} \frac{t-[t]}{t} \ dt = \mathcal{O}\biggl(\int\limits_{1}^{t} \frac{1}{t} \ dt\biggr)=\mathcal{O}(\log{x})\Biggr] \end{align*}

Corollary. Take $a(n)= \Lambda(n)$. By Shapiro-Tauberian theorem, we then have $$\sum\limits_{n \leq x} \frac{\Lambda(n)}{n} = \log{x} + \mathcal{O}(1)$$

Lemma 3. For $x \geq 2$ we have $$\sum\limits_{p \leq x}\biggl[\frac{x}{p}\biggr]\log{p} = x\log{x} + \mathcal{O}(x)$$

Proof. Since $\Lambda(n)=0$ unless $n$ is a prime power, we have $$\sum\limits_{n \leq x} \biggl[\frac{x}{n}\biggr]\Lambda(n)= \mathop{\sum\limits_{p} \sum\limits_{m=1}^{\infty}}_{p^{m} \leq x}\biggl[\frac{x}{p^{m}}\biggr] \Lambda(p^{m})$$

For $p^{m} \leq x$ we have $p \leq x$. Also $\displaystyle \Bigl[\frac{x}{p^{m}}\Bigr]=0$ if $p >x$, so we can write the last sum as $$\sum\limits_{p \leq x}\ \sum\limits_{m=1}^{\infty}\biggl[\frac{x}{p^{m}}\biggr]\log{p}=\sum\limits_{p \leq x} \biggl[\frac{x}{p}\biggr]\log{p} + \sum\limits_{p \leq x} \ \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr]\log{p}$$

Now we prove that the last sum above is $\mathcal{O}(x)$. We have \begin{align*} \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl[\frac{x}{p^{m}}\biggr] &\leq \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \frac{x}{p^{m}} = x \sum\limits_{p \leq x} \log{p} \sum\limits_{m=2}^{\infty} \biggl(\frac{1}{p}\biggr)^{m} \\\ &= x \sum\limits_{p \leq x} \log{p} \cdot \frac{1}{p^{2}} \cdot \frac{1}{1-\frac{1}{p}} = x \sum\limits_{p \leq x} \frac{\log{p}}{p(p-1)}\\\ & \leq \sum\limits_{n=2}^{\infty}\frac{\log{n}}{n(n-1)} = \mathcal{O}(x) \end{align*}

Suppose you set $$\Lambda_{1}(n) = \biggl\{ \begin{array}{cc} \log{p} & \text{if} \ n \ \text{is a prime} \\\ 0 & \text{otherwise}\end{array}$$ then you have from the above Lemma $$\sum\limits_{n \leq x} \Lambda_{1}(n) \biggl[\frac{x}{n}\biggr] = x\log{x} + \mathcal{O}(x)$$ Now applying the Shapiro - Tauberian theorem with $a(n)= \Lambda_{1}(n)$ gives $$\sum\limits_{p \leq x} \frac{\log{p}}{p} = \log{x} + \mathcal{O}(1)$$

• Everything Can be found in Apostol's book. I just thought TeXing it here would be nice.
-