Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
@b01024: Use \to to get $\to$. –  Arturo Magidin Apr 20 '11 at 2:50
2  
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
add comment

3 Answers 3

up vote 15 down vote accepted

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.

share|improve this answer
    
I understand, though it took a little re-reading. Thanks very much! –  usul Apr 20 '11 at 13:38
add comment

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.
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.