0
$\begingroup$

I am trying to understand the proof for $c_1*n*\log{n} \leq p_n \leq c_2*n*\log{n}$ where $c_1, c_2$ are constants and $p_n$ is the $n$-th prime. I understand the proof for the lower bound, however I am struggling with a step in the proof for the upper bound.
You first use Chebyshev's Theorem: $\exists a,b$, constants, s.t. $a\frac{x}{\log{x}}\leq \pi(x) \leq b\frac{x}{\log{x}}$, where $\pi(x)$ is the prime counting function.
Setting $x = p_n$ and taking logs gives: $\log{n}+\log{\log{p_n}} \geq \log{a}+\log{p_n}$ (1). So far I understand everything. The step I don't understand is that from the above equation it is inferred that $\log{p_n} = O(\log{n})$ (2). I understand the definition of the Big O notation, but just can't see how (1) can be manipulated to show (2). Any help would be greatly appreciated.

Thank you!

$\endgroup$
0
$\begingroup$

Because of conintuity of the exponential function $\frac{\operatorname{log}(\operatorname{log}(p_n))}{\operatorname{log}(p_n)} \rightarrow 0$ if and only if $\operatorname{exp}(\frac{\operatorname{log}(\operatorname{log}(p_n)}{\operatorname{log}(p_n)})) = \operatorname{log(p_n)}^{\frac{1}{\operatorname{log}(p_n)}} \rightarrow 1$, which is true since $\sqrt[x]{x} \rightarrow 1$ for $x \rightarrow \infty$ and $\sqrt[x]{x}$ is continuous on the relevant domain.

Manipulating $(2)$ gives $\frac{\operatorname{log}(n)}{\operatorname{log}(p_n)} + \frac{\operatorname{log}(\operatorname{log}(p_n))}{\operatorname{log}(p_n)} - \frac{\operatorname{log}(a)}{\operatorname{log}(p_n)} \geq 1$. Since $\frac{\operatorname{log}(\operatorname{log}(p_n))}{\operatorname{log}(p_n)} - \frac{\operatorname{log}(a)}{\operatorname{log}(p_n)} \rightarrow 0$ and $\frac{\operatorname{log}(n)}{\operatorname{log}(p_n)} \leq 1,$ we must have $\frac{\operatorname{log}(n)}{\operatorname{log}(p_n)} \rightarrow 1$. Therefore $\frac{\operatorname{log}(n)}{\operatorname{log}(p_n)} = O(1)$ which means $\operatorname{log}(p_n) = O(\operatorname{log}(n))$.

$\endgroup$
  • $\begingroup$ Thank you so much. This really helped me. $\endgroup$ – John Stevenson Dec 6 '17 at 12:22
  • $\begingroup$ @JohnStevenson Assuming $\pi(x) \in [a \frac{x}{\log x},b \frac{x}{\log x}]$, then $p_n > c n \log n \implies \pi(p_n) > \pi(c n \log n) > a \frac{c n \log n}{\log(c n \log n)}=a \frac{c n \log n}{\log n+\log c+\log \log n} > ac n-1$. Thus we have a contradiction if $c \ge \frac{1}{a}+\frac{1}{n}$. The lower bound is obtained the same way. $\endgroup$ – reuns Dec 6 '17 at 13:10

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.