Using the Prime Number Theorem show that:

$$x^{\pi(x)} < 3^x$$ for sufficiently large $x$.

I started off by taking the $\log$ of the inequality such that:

$$\log(x^{\pi(x)}) < \log(3^x)$$ so $$\pi(x) \log(x) < x \log(3)$$

by PNT we know that $$\pi(x) \sim \dfrac{x}{\log(x)}$$

so can we then just sub this in and obtain:

$$\dfrac{x}{\log(x)} \log(x)<x\log(3)$$ $$x<x\log(3)$$ $$1<\log(3)$$

Can I do this? This is for a Distribution of Primes course, I'm trying to get my head around using the PNT! Thanks for any help!

  • $\begingroup$ Please. Write "a\log b", not "a log b". The former gives you $a\log b$, the latter gives you $a log b$. I also changed \text{~} to \sim, thus $\pi(x)\text{~}\dfrac{x}{\log(x)}$ became $\pi(x)\sim\dfrac{x}{\log(x)}$. ${}\qquad{}$ $\endgroup$ May 21 '14 at 16:55
  • $\begingroup$ Your reasoning leads to the conclusion that $x^{\pi(x)} < 3^x$ if $x$ is sufficiently large. But how large is sufficiently large must be examined. $\endgroup$ May 21 '14 at 16:57

You need to be a bit careful when handling the $\sim$ relation. You can't just substitute it in the inequality, since it is only an asymptotic relation. This is one way to do it:

The $\sim$ operator is usually defined as

$$f(x)\sim g(x) \iff \lim_{x \to \infty} \frac{f(x)}{g(x)}=1$$

So, $$\pi(x) \sim \frac x{\log x} \iff \lim_{x \to \infty}\frac{\pi(x) \log x}{x}= 1 $$

Dividing the inequality $\pi(x)\log x < x \log 3$ by $x$ gives you $$\frac{\pi(x)\log x}x < \log 3$$

Finally, by taking the limit to infinity of the left hand side you can conclude that the value will approach $1$ for a large enough $x$, and you are done, since $3 > e \implies \log 3 >1$.

  • $\begingroup$ Ah yes, I forgot I need to use the limit bit! Thank you very much! $\endgroup$
    – sarahusher
    May 21 '14 at 16:54

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.