How to prove Chebyshev's result: $\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 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!

Solution 1:

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.

Solution 2:

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.