In the Newman short proof of the prime number theorem (http://www.maths.dur.ac.uk/~dma0hg/prime_number_theorem_zagier.pdf) Zagier states that

the fact that $2^{2n} >= e^{\theta(2n) - \theta(n)}$ and the fact that $\theta(x)$ changes by $O(log(x))$ if x changes by $O(1)$

imply that $\theta(x)-\theta(x/2) <= Cx$

I don't understand this implication; can someone please explain it in detail? Thank you very much!

  • $\begingroup$ Take logarithms? Or am I missing somthing $\endgroup$ – Ethan Jun 20 '13 at 11:35
  • $\begingroup$ @Ethan Surely you have to take the logarithm. In this way $2n log2 >= \theta(2n) -\theta(n)$ and "Intuitively" i can divide by 2 and obtain $n*log2 >= \theta(n) -\theta(n/2) $ but one thing are the naturals, an other things is the real x. How can you switch between the two? And what is the use of the statement "θ(x) changes by O(log(x)) if x changes by O(1)"? $\endgroup$ – Benzio Jun 20 '13 at 11:53
  • $\begingroup$ No need to intuitively divided by $2$ make the substitution $n:\frac{x}{2}$, in general $c\ln(x)<cx$ for large enough $x$, so $c_1x+c_2\ln(x)<c_3x$ for some constants $c_1,c_2,c_3$, also $\theta(x)=\theta([x])$ $\endgroup$ – Ethan Jun 20 '13 at 11:57
  • 1
    $\begingroup$ Dear Benzio, the fact that $\theta(x)$ changes by $O(\log x)$ when $x$ changes by $O(1)$ is precisely the statement that is used to "smooth out" the statement $\theta(x) - \theta(x/2) \leq C x$ from the case when $x$ is an even integer (i.e. $2n$) to the case of general positive real $x$. Regards, $\endgroup$ – Matt E Jun 20 '13 at 12:30
  • $\begingroup$ I'm commenting now to remember to come back and answer this question - I hope you don't mind my temporary intrusion. I'll delete this comment when I answer (hopefully this evening) $\endgroup$ – davidlowryduda Jun 23 '13 at 21:52

Your Answer

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

Browse other questions tagged or ask your own question.