# Estimate of $n$th prime

There is a result that if $p_n$ is the $n$th prime, then $p_n\sim n\log n$ as $n\rightarrow\infty$.

I wonder: Is it a direct consequence of the prime number theorem $\pi(x)\sim x/\log x$? The theorem says that there are approximately $n/\log n$ primes less than or equal to $n$. So there are approximately $n$ primes less than or equal to $n\log n$. So $p_n$ is approximately $n\log n$.

But I'm having trouble turning this into a formal argument. We have $\lim_{n\rightarrow\infty}\dfrac{\pi(n)\log n}{n}=1$. How would it show that $\lim_{n\rightarrow\infty}\dfrac{p_n}{n\log n}=1$?

The proposals are $p_n\sim n\log n$ and $\pi(x)\sim \frac{x}{\log x}$. Consider:

$$p_{\pi(x)}\sim \pi(x)\log\pi(x)\sim\frac{x}{\log x}\log\left(\frac{x}{\log x}\right)=\frac{x}{\log x}\left(\log x-\log\log x\right)\sim x$$

and

$$\pi(p_n)\sim\pi(n\log n)\sim\frac{n\log n}{\log(n\log n)}=\frac{n\log n}{\log n+\log\log n}\sim n$$

Try formailizing this (giving more meaning to $\sim$) to show that $p_{({.})}$ and $\pi({.})$ are asymptotic inverses.

To formalize more: Let $f(x)=\frac{x}{\log{x}}$ and $g(x)=x\log{x}$. Then $$\frac{f(g(x))}{x}=\frac{1}{x}\frac{x\log{x}}{\log(x\log{x})}=\frac{1}{1+\frac{\log\log x}{\log x}}\xrightarrow{x\to\infty}1$$

And $$\frac{g(f(x))}{x}=\frac{1}{x}\frac{x}{\log{x}}\log\left(\frac{x}{\log{x}}\right)=\frac{1-\frac{\log\log x}{\log x}}{1}\xrightarrow{x\to\infty}1$$

And so for large $x$, $f(g(x))\sim x$ and $g(f(x))\sim x$, where $A\sim B$ means that their ratio approaches $1$.

All this is to say that $f$ and $g$ are asymptotic inverses. So if we start with the premise that the $n$th prime number $p_n$ is approximately $g(n)$ (in the same "ratio approaches 1" sense), and then define $\pi(x)$ as the inverse concept (the number of primes less than a given $x$), then $\pi(x)$ is approximately $f(x)$ (again in that sense).

• I added formalization. – alex.jordan Dec 17 '13 at 2:30

Continuing the argument, $n =\pi(p_n) \sim \frac{p_n}{\ln(p_n)}$.

If we can show that $\frac{\ln(p_n)}{\ln{n}} \to 1$, we can conclude that $p_n \sim n \ln n$.

This is a fairly direct consequence of $n \sim \frac{p_n}{\ln(p_n)}$.

Hint: By definition, $p_n=\inf\{x\mid\pi(x)\geqslant n\}$. For every $\varepsilon$ in $(0,1)$ there exists $x_\varepsilon$ such that $(1-\varepsilon)x/\log x\leqslant\pi(x)\leqslant(1+\varepsilon)x/\log x$ for every $x\geqslant x_\varepsilon$. Let $n_\varepsilon\geqslant(1+\varepsilon)x_\varepsilon/\log x_\varepsilon$, then, for every $n\geqslant n_\varepsilon$, ...

• I'm following your argument. Could you tell me, for every $n\geq n_\varepsilon$, what you want there? I don't see what it should be. – PJ Miller Dec 14 '13 at 21:14
• Obviously, what I am suggesting is that you do a part of the job yourself. Asking me to complete the argument is rather contradictory with this aim. Or, you will want to describe precisely which step you have a problem with. – Did Dec 15 '13 at 8:08
• Sure, so for every $n\geq n_\epsilon$, we have $\pi(x_\epsilon)\leq(1+\epsilon)x_\epsilon/\log x_\epsilon\leq n_\epsilon\leq n$. Then I'm not sure how to continue. – PJ Miller Dec 15 '13 at 16:07

Note that $\pi(p_n)=n$ for all positive integers $n$ and $p_{\pi(q)}=q$ for all primes $q$. Thus

$$\lim_{n\to\infty}\left({n\log n\over p_n}\right)=\lim_{n\to\infty}\left({\pi(p_n)\log p_n\over p_n}\cdot{\log n\over\log p_n}\right)$$

Now

$$\lim_{n\to\infty}\left({\pi(p_n)\log p_n\over p_n}\right)=\lim_{p\to\infty}\left({\pi(p)\log p\over p}\right)=1$$

is just the Prime Number Theorem. So it suffices to show that

$$\lim_{n\to\infty}\left({\log n\over\log p_n}\right)=1$$

Let's replace the sequence of integers $n$ with the sequence $\pi(q)$ where $q$ runs over the increasing sequence of primes. Using the relation $p_{\pi(q)}=q$, this gives

$$\lim_{n\to\infty}\left({\log n\over\log p_n}\right)=\lim_{q\to\infty}\left({\log\pi(q)\over\log q}\right)=\lim_{q\to\infty}\left({\log\left({\pi(q)\log q\over q}\right)+\log q-\log\log q\over\log q}\right)=1$$

where the final limit evaluation again makes use of the Prime Number Theorem, this time for $\log\left({\pi(q)\log q\over q}\right)\approx0$.

• Beautiful. I think this will help the OP the most, as it's the cleanest argument and the first I understood all the way to the end. – ShreevatsaR Dec 17 '13 at 3:11
• @ShreevatsaR, thank you! – Barry Cipra Dec 17 '13 at 3:12
• BTW, in the very last "word", instead of $\log\left({\pi(q)\log q\over q}\right)\approx0$ I think you mean $\log\left({\pi(q)\log q\over q}\right)/\log q\to0$. – ShreevatsaR Dec 17 '13 at 3:13
• @ShreevatsaR, no, you don't really need the log in the denominator. The Prime Number Theorem says that $\pi(q)\log q/q\approx1$, so its log is already close to $0$. – Barry Cipra Dec 17 '13 at 3:14
• Oh yes... sure, that makes sense. – ShreevatsaR Dec 17 '13 at 3:15