Are there primes arbitrarily close to powers?

Question

For $n \geq 3$ let $r(n)$ be the previous prime to $n$; i.e., the largest prime strictly less than $n$. For example, $r(3) = 2$, $r(10) = 7$, and so on.

I have noticed that $r(n^p)$ is very close to $n^p$. In fact, I suspect that $$\lim_{n\to\infty}\frac{r(n^p)}{n^p} = 1$$ for any positive integer power $p$, where the convergence is faster if $p$ is big. Is this true? Are there effective bounds on the rate of convergence? Is there a simple proof of this fact?

Here's an argument that doesn't work: By Bertrand's postulate, there exists a prime between $n^p / 2$ and $n^p$ (roughly). Therefore $$\frac{r(n^p)}{n^p} \geq \frac{1}{2}.$$ But this is pretty far from $1$.

I think that I can prove this using some fancy number theory results, but they seem like sledgehammers. I'd like something simpler.

Answer 1

Notice that $r(m)=p_{\pi(m-1)}$ where $p_m$ is the $m$th prime number. (Since $m=n^p$ won’t be prime in our case we will always have: $\pi(m)=\pi(m-1)$ and we can write everything more conveniently as $r(m)=p_{\pi(m)}$.)

Look at the number of primes less than $n^p$: that would be $\pi(n^p)\approx\frac{n^p}{\log(n^p)}$. Now you are looking for approximately the $\pi(n^p)$th prime number and $p_m\approx\,m\log(m)$, thus $p_{\pi(n^p)}\approx\,n^p-n^p\frac{\log(\log(n^p))}{\log(n^p)}$. Now your function is essentially $p_{\pi(n^p)}/n^p\approx{}1-\frac{\log(\log(n^p))}{\log(n^p)}$ which converges to $1$.

Answer 2

Though Μάρκος posted a great answer, for completeness I'll post the complicated proof that I know.

It suffices to show that there exists a prime between $x$ and $(1 + b(x))x$ for sufficiently large $x$, where $b(x) \to 0$ as $x \to \infty$. (Then $r(n^p) / n^p \geq \frac{1}{1 + b(n^p)}$, and letting $n \to \infty$ yields the result.) By some complicated number theory, we can take $b(x) = 1 + 1 / (2 \log^2 x)$ for $x \geq 3275$. This gives $$\frac{r(n^p)}{n^p} \geq \frac{1}{1 + \frac{1}{2 \log^2 n^p}}$$ for $n$ sufficiently large. This says that the limit is $1$, and that it approaches $1$ quicker if $p$ is large.

Answer 3

To get the limit you only need the prime number theorem

$$\lim_{n\rightarrow \infty}\pi(n)/(n/\ln n)=1 \tag 1$$

but the deduction is a bit messy.

From (1) you can deduce that for any $\epsilon^{'}>0$ $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))/(n(1+\epsilon^{'})/\ln n(1+\epsilon^{'}))=1$$ Now $\lim_{n\rightarrow \infty}\ln n(1+\epsilon^{'})/\ln n=1$ so $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))/(n(1+\epsilon^{'})/\ln n)=1$$

This means that for any $\epsilon>0$ $\exists N \in \mathbb{N}$ s.t. $\forall n>N$ the following two inequalities hold:

\begin{align} (1-\epsilon)(n/\ln(n))&<\pi(n)& &<(1+\epsilon)(n/\ln(n)) \\ (1-\epsilon)(1+\epsilon^{'})(n/\ln(n))&<\pi(n(1+\epsilon^{'}))& &<(1+\epsilon)(1+\epsilon^{'})(n/\ln(n)) \end{align}

Subtracting the two inequalities we obtain after some simplification:

$$\{\epsilon^{'}-\epsilon(\epsilon^{'}+2)\}<\frac{\pi(n(1+\epsilon^{'}))-\pi(n)}{(n/\ln(n))}<\{\epsilon^{'}+\epsilon(\epsilon^{'}+2)\}$$

This clearly implies that $$\lim_{n\rightarrow \infty}\frac{\pi(n(1+\epsilon^{'}))-\pi(n)}{(n/\ln(n))}=\epsilon^{'}$$ and in particular that $$\lim_{n\rightarrow \infty}\pi(n(1+\epsilon^{'}))-\pi(n)=\infty$$

This implies that for any $\epsilon^{'}>0$ $\pi(n(1+\epsilon^{'}))-\pi(n)>1$ for large enough $n$ and hence that there exists a prime $p$ with $n<p<n(1+\epsilon^{'}).$

Clearly then we have for $\epsilon^{'}>0$ and all large enough n $$n<r(n)<n(1+\epsilon^{'})$$ and thus also for any fixed $p\in \mathbb{N}$ $$1-\epsilon^{'}<\frac{1}{1+\epsilon^{'}}<n^p/r(n^p)<1$$.

which implies that $$\lim_{n\rightarrow \infty}n^p/r(n^p)=1$$

Update to show that the rwbogl's sufficient condition can be proved from the prime number theorem rather than Pierre Dusart's result.

From the PNT I showed that for any $\epsilon>0$ there exists a prime $p$ with $n<p<n(1+\epsilon)$ for some $n=N(\epsilon)$ where $N$ is strictly increasing as $\epsilon$ decreases to $0$. If we set $g(n)=N(1/n)$ where $n\in\mathbb{N}$ then $g\in\mathbb{N}$ increases monotonically and hence possesses a monotonically increasing pseudo-inverse $g^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ s.t. $g(g^{-1}(x))=x$ for all $x\in\mathbb{N}.$

Substituting we have for any $n\in\mathbb{N}$ there exists a prime $p$ with $g(n)<p<g(n)(1+1/n)$. Setting $n=g^{-1}(x)$, $x\in\mathbb{Z}$ we have for any $x\in\mathbb{N}$ there exists a prime $p$ with $$x<p<x(1+1/g^{-1}(x))=x(1+f(x))$$ where $f(x)=1/g^{-1}(x)$ which decreases monotonically to 0 as $x\rightarrow \infty$.