15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so mersenne numbers and fermat numbers aren't in the picture. $\endgroup$ – Roddy MacPhee Nov 23 at 2:07
  • 3
    $\begingroup$ The fact that the limit approaches $1$ implies that the difference between a large prime and a large power can be a negligibly small fraction of that large power, but NOT that the difference can be made arbitrarily small, such as $<50$. Also, I don't see what is specially interesting about powers. Refinements to Bertrand's postulate suggest that $\lim_{n\to\infty}\frac{r(n)}{n} = 1$ $\endgroup$ – Keith Backman Nov 23 at 3:08
  • $\begingroup$ @RoddyMacPhee - why are Mersenne-numbers/-primes out of the picture? $\endgroup$ – Gottfried Helms Nov 23 at 22:17
  • $\begingroup$ @Gottfried , because them being infinite in the primes, would show there are infinitely many 1 away. $\endgroup$ – Roddy MacPhee Nov 24 at 0:19
  • $\begingroup$ @RoddyMacPhee - yes, but why then out of the picture instead of in the picture. Mersenne-primes are perfect exemplars for what the OP is asking for, or not? $\endgroup$ – Gottfried Helms Nov 24 at 0:26
15
$\begingroup$

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{}mlog(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$.

$\endgroup$
  • 1
    $\begingroup$ Why isn't this a rigorous argument already? It seems pretty plausible to me! (I'm not immediately sure how to make the convergence effective from this, though.) $\endgroup$ – rwbogl Nov 22 at 22:36
  • 1
    $\begingroup$ The limit being equal to 1 is immediate from the $\approx$ notation which implies that the two sides belong in the same asymptotic class as $n\to\infty$. The only issue with the proof is that it doesn’t use the form $n^p$ at all! It simply holds for $n$ and $r(n^p)/n^p$ obviously converges too as a subsequence. $\endgroup$ – Μάρκος Καραμέρης Nov 22 at 22:43
  • 3
    $\begingroup$ Technically, $r(m)=p_{\pi(m-1)}$. $\endgroup$ – J.G. Nov 22 at 22:46
  • $\begingroup$ @J.G. Indeed, hopefully the asymptotic notation and the limits at the end save the day... $\endgroup$ – Μάρκος Καραμέρης Nov 22 at 22:49
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Brutal. Correct, but brutal. $\endgroup$ – URL Nov 23 at 2:56
  • 1
    $\begingroup$ It's worth noting that your sufficient condition can be proved from the prime number theorem rather than Pierre Dusart's result - I added an update to my answer to cover this. $\endgroup$ – Ivan Nov 23 at 16:30
3
$\begingroup$

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$.

$\endgroup$

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.