20
$\begingroup$

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!

  • 0
    The proo$f$ in the paper you linked is quite simple. $T$he upper bound i$s$ almo$s$t trivial, and the lower bound is only a little involved, using the same trick as Lemma 1 in Eric's answer.2011-04-20

3 Answers 3

25

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 Since $\binom{2N}{N}\leq(1+1)^{2N}=4^{N},$ we see that $\prod_{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.

  • 0
    I understand, though it took a little re-reading. Thanks very much!2011-04-20
10

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.
4

This proof differs from the others in that it uses the prime number theorem with remainder term, which is perhaps overpowered for this, but gives a somewhat shorter proof.

Using Riemann-Stieltjes integration, the sum can be written as $ \sum_{p \leq x} {\log p \over p} = \sum_{n \leq x} {\log n \over n} \Big\{{\pi(n) - \pi(n-1)}\Big\} = \int_2^x {\log t \over t} d\pi(t), $ and using integration by parts gives $ \sum_{p \leq x} {\log p \over p} = {{\log t \over t} \pi(t)}\Bigg|_2^x - \int_2^x {1 - \log t \over t^2} \pi(t) dt. \tag{1} $ Using the simplest form of the prime number theorem, $\pi(x) \sim x/\log x$, we see that the evaluated terms before the integral are $O(1)$ as $x \to \infty$. To handle the integral itself, we will use the prime number theorem in the form $ \pi(x) = \operatorname{li}(x) + O\Big({x e^{-c\sqrt{\log x}}}\Big), \tag{2} $ together with an expansion of $\operatorname{li}(x)$. Integrating by parts twice, we have \begin{align*} \operatorname{li}(x) &= \operatorname{li}(2) + \int_2^x {dt \over \log t} = \operatorname{li}(2) + \bigg\{{{t \over \log t}}\bigg|_2^x + \int_2^x {dt \over \log^2 t}\bigg\} \\ &= {x \over \log x} + \bigg\{{{t \over \log^2 t}}\bigg|_2^x + 2\int_2^x {dt \over \log^3 t}\bigg\} + O(1) \\ &= {x \over \log x} + {x \over \log^2 x} + O\bigg({{x \over \log^3 x}}\bigg). \end{align*} The error term in (2) can be subsumed by this error term, and so the integral in (1) is \begin{align*} \int_2^x {1 - \log t \over t^2} \pi(t) dt &= \int_2^x {1-\log t \over t^2} \bigg\{{t \over \log t} + {t \over \log^2 t} + O\bigg({t \over \log^3 t}\bigg) \bigg\} dt \\ &= \int_2^x \bigg\{{1 \over t \log t} + {1 \over t \log^2 t} + O\bigg({1 \over t \log^3 t}\bigg) \bigg\} dt \\ &\qquad- \int_2^x \bigg\{{{1 \over t} + {1 \over t \log t} + O\bigg({1 \over t \log^2 t}}\bigg)\bigg\} dt, \end{align*} which can be directly evaluated by the fundamental theorem of calculus as \begin{align*} &= \log \log x - {1 \over \log x} - O\bigg({{1 \over 2 \log^2 x}}\bigg) - \log x - \log \log x + O\bigg({1 \over \log x} \bigg) \\ &= -\log x + O(1). \end{align*} Plugging this back into (1) gives the desired result.

  • 0
    @LeastSquaresWonderer could the $\Big\{{\pi(n) - \pi(n-1)}\Big\}$ simply gives the integral limits starting at 2 not 0 as would be the case with simply $\sum_{n \leq x} {\log n \over n} \Big\{{\pi(n)}\Big\} = \int_0^x {\log t \over t} d\pi(t)$?2018-07-25