Big $O$ notation and Chebyshev's theorem

Question

By Chebyshev we have that, $$n\geq\frac{ap_{n}}{\log(p_{n})}$$

Where $p_{n}$ is the $n^{th}$ smallest prime and $a$ is constant. I have seen that from this, the implication that $\log(p_{n})=O(\log(n))$ and substituting back in that $p_{n}=O(n\log(n))$ however I am unsure of the steps that allow us to arrive at this.

Answer 1

The logarithm is monotonically increasing, therefore inequalities between positive expressions are preserved when taking logarithms. Thus from Chebyshev's bound we obtain $$\log n \geqslant \log p_n - \log \log p_n + \log a\,. \tag{$\ast$}$$ Differentiation shows that $\frac{\log x}{x}$ attains its maximum $\frac{1}{e}$ at $x = e$, hence $$\log n \geqslant \biggl(1 - \frac{\log \log p_n}{\log p_n}\biggr)\log p_n + \log a \geqslant \biggl(1 - \frac{1}{e}\biggr)\log p_n + \log a$$ and by rearranging $$\log p_n \leqslant \frac{e}{e-1}\biggl(\log n + \log \frac{1}{a}\biggr)$$ which yields $$\log p_n \leqslant \frac{2e}{e-1}\log n$$ for $n \geqslant e^{1/a}$. Thus $\log p_n \in O(\log n)$. In fact, we can easily obtain the sharper $\log p_n \sim \log n$. On the one hand, $p_n \geqslant n$ and consequently $\log p_n \geqslant \log n$ is clear, and if we divide $(\ast)$ by $\log n$ (for $n \geqslant 2$) we obtain $$1 \geqslant \biggl(1 - \frac{\log \log p_n}{\log p_n}\biggr)\frac{\log p_n}{\log n} + \frac{\log a}{\log n}\,.$$ Since $\frac{\log a}{\log n} \to 0$ and $\frac{\log \log p_n}{\log p_n} \to 0$ it follows that $$\limsup_{n \to \infty} \frac{\log p_n}{\log n} \leqslant 1\,.$$ Since all terms of that sequence are $\geqslant 1$ this means $$\lim_{n \to \infty} \frac{\log p_n}{\log n} = 1\,,$$ i.e. $\log p_n \sim \log n$.

Then Chebyshev's inequality yields $$p_n \leqslant \frac{1}{a}n\log p_n \leqslant \frac{C}{a}n\log n$$ for $n \geqslant 2$ where $$C = \max\: \biggl\{\frac{\log p_n}{\log n} : n \geqslant 2\biggr\}\,.$$

Answer 2

Since $\log(p_n) = O(\log(n))$, there exists a constant $C$ such that $\log(p_n) \leq C\cdot\log(n)$ for all $n$. So $$ n\geq \frac{ap_n}{\log(p_n)} \geq \frac{ap_n}{C\log(n)} $$ and $$p_n\leq \frac{C\cdot n \log(n)}{a}.$$ Thus there exists a constant $K = C/a$ such that for all $n$, $p_n \leq K\cdot n\log(n)$. So $p_n = O(n\log(n))$.