In Apostol's book Introduction to Analytic Number Theory, we have the following exercise

4.18. Prove that the following two relations are equivalent: \begin{align*} \text{(a)} \quad \quad & \pi(x)=\frac{x}{\log x}+O \left( \frac{x}{\log^2 x} \right).\\ \text{(b)} \quad \quad & \vartheta(x)=x+O \left( \frac{x}{\log x} \right). \end{align*}

where $\pi(x)$ is, of course, the prime counting function, and $\vartheta(x)$ is Chebychev's function $\sum_{p \le x} \log p$.

I don't quite understand what "equivalent" is supposed to mean in this context, and I thought of skipping this particular exercise, but I suppose it would be a bad habit to skip all questions that I don't understand (especially since I am self-studying). So my hope is that someone would like to help me clarify this.

  • 2
    $\begingroup$ They want you to show that $(a)\Rightarrow (b)$ and $(b)\Rightarrow (a)$. To put it another way, they want you to show that $$\pi(x)=\frac{\theta(x)}{\log x}+O\left(\frac{x}{\log^2 x}\right).$$ $\endgroup$ – Eric Naslund Dec 3 '11 at 8:10
  • $\begingroup$ @EricNaslund: that's very helpful, thanks! $\endgroup$ – Carolus Dec 3 '11 at 8:30

"Equivalent" here means that you can prove that (a) implies (b), and that (b) implies (a), with significantly less effort than it takes to prove either (a) or (b).

In this particular case, I imagine that you're intended to use partial summation to derive each one from the other one.


Maybe this could help. Note that I use $\ln x$ for natural logarithm.

I guess someone will come up with the solution without using Chebyshev's inequalities. Perhaps you could specify in the question, whether you're allowed to used them in this exercise (i.e., whether Chebyshev's inequalities were proved in the book before this exercise).

Lemma. $$\pi(x)\sim \frac{\vartheta(x)}{\ln x}$$

Proof. Clearly $\vartheta(x)= \sum\limits_{p\leq x} \ln p \leq \sum\limits_{p\leq x} \ln x = \pi(x) \ln x$. This implies $$\frac{\vartheta(x)}{\pi(x)\ln x} \leq 1.$$

Now let $x\geq 2$ and $0<\varepsilon<1$. Then we have $$ \vartheta(x) \geq \sum_{x^{1-\varepsilon} < p \leq x} \ln p \geq (1-\varepsilon) \ln x (\pi(x)-\pi(x^{1-\varepsilon})) \geq (1-\varepsilon) \ln x (\pi(x)-x^{1-\varepsilon}). $$ This yields (using one of Chebyshev inequalities) $$\frac{\vartheta(x)}{\pi (x) \ln x } \geq (1-\varepsilon)\left(1 - \frac{x^{1-\varepsilon}}{\pi(x)}\right) \geq (1-\varepsilon)\left(1 - \frac{x^{1-\varepsilon}\ln x}{c_2x}\right)$$ for some constant $c_2$.

If we take the limit for $x\to\infty$ we get $$\liminf_{x\to\infty} \frac{\vartheta(x)}{\pi(x) \ln x} \geq 1-\varepsilon.$$ Since $\varepsilon$ cen be chose arbitrarily small, we get $$\lim\limits_{x\to\infty} \frac{\vartheta(x)}{\pi(x) \ln x} = 1.$$

  • $\begingroup$ Very interesting answer! I haven't learned about Chebychev's inequalities yet, but I will check them out. $\endgroup$ – Carolus Dec 4 '11 at 6:08
  • $\begingroup$ Note that Chebyshev's inequalities have been proved for various positive values of $\epsilon$, but not for any sequence of $\epsilon$ that tends to 0 - that stronger result is equivalent to the prime number theorem. $\endgroup$ – Greg Martin Dec 6 '11 at 9:24
  • 1
    $\begingroup$ @Greg I am using this inequality in the form $\pi(x)\ge c_2 \frac{x}{\ln x}$, i.e. the above proof works for arbitrary positive constant $c_2$. (The $\varepsilon$ has different meaning, it is not the constant from Chebyshev's inequality.) $\endgroup$ – Martin Sleziak Dec 6 '11 at 11:31
  • $\begingroup$ Ah, you're right. Sorry not to have read closely enough. $\endgroup$ – Greg Martin Dec 6 '11 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.