1. Background

Bertrand's Postulate says that there is at least one prime between an integer $n$ and its double $2n$.

$$n < p < 2n$$

Although not a proof, the Prime Number Theorem (PNT), that the number of primes up to $x$ denoted $\pi(x)$ is asymptotically equivalent to $x/\ln(x)$, gives us a clue that this is true.

\begin{align} \frac{\pi(2n)}{\pi(n)} &\sim \frac{2n}{\ln(2n)} \cdot \frac{\ln(n)}{n} \\ & = \frac{2 \ln(n)}{\ln(2)+\ln(n)} \\ & \to 2 \text{ as } n \to \infty \end{align}

Which says that for large enough $n$, on average we expect there to be $n/\ln(n)$ primes between $n$ and $2n$.

This logic is also presented by the Wikipedia article on Bertrand's postulate, read on 28th Nov 2020.

2. Question

That same wikipedia article also suggests we can't apply similar logic to Legendre's Conjecture, which states there is at least one prime between two consecutive squares:

$$n^2 < p < (n+1)^2$$

Here is the analogous argument, an elaboration of the more concise description in that wikipedia article.

\begin{align} \frac{\pi((n+1)^2)}{\pi(n^2)} &\sim \frac{(n+1)^2}{\ln(n+1)^2} \cdot \frac{\ln(n^2)}{n^2} \\ & = \frac{(n^2 + 2n + 1) \cdot 2\ln(n)}{2\ln(n+1) \cdot n^2} \\ & = \frac{(1+\frac{2}{n} + \frac{1}{n^2}) \cdot \ln(n)}{\ln(n+1)} \\ & \to 1 \text{ as } n \to \infty \end{align}

How should I interpret this result?

Is the correct interpretation that this application of the PNT doesn't reveal any information about the number of primes between $n^2$ and $(n+1)^2$ because $\pi(n^2)$ grows too similarly to $\pi((n+1)^2)$, where "grows too similarly" means asymptotic equivalence?

3. Alternative Conjecture?

We can state a related conjecture:

$$n < p < n^2$$

A similar application of the PNT:

\begin{align} \frac{\pi(n^2)}{\pi(n)} &\sim \frac{n^2}{\ln(n^2)} \cdot \frac{\ln(n)}{n} \\ & = \frac{n \cdot ln(n)}{2\ln(n)} \\ & = \frac{n}{2} \\ & \to \infty \text{ as } n \to \infty \end{align}

I'm not an expert, but this suggests that for large $n$, we expect on average more than one prime between $n$ and $n^2$.

What makes the the $n^2$ and $(n+1)^2$ case less amenable to this kind of analysis?

  • $\begingroup$ The issue is the following: Given two sequences $a_n< b_n$ ,to apply the PNT to show that there is a prime between $a_n$ and $b_n$ for $n$ large enough you need $$\liminf_n \frac{b_n}{ \ln(b_n)} /\frac{a_n}{ \ln(a_n)} > 1$$ This holds for the last problem, but not the first. $\endgroup$ – N. S. Nov 29 '20 at 18:22
  • $\begingroup$ It's not a related conjecture, the part 3 I mean. $\endgroup$ – rtybase Nov 29 '20 at 20:58
  • $\begingroup$ @N.S., Can you explain why it is $\liminf$ and not just $lim$, please? $\endgroup$ – Ninja May 24 at 13:27
  • 1
    $\begingroup$ @Ninja to cover the case when the limit does not exist. If the lim exists, then it is the same as the liminf, but even when the lim does not exist, the condition on liminf works. $\endgroup$ – N. S. May 24 at 22:33

$2n-n=n$ and $(n+1)^2-n^2=2n+1$ thus there is approximately the same number of primes between $n$ and $2n$, as in $n^2$ and $(n+1)^2$. When talking about equivalents, $\pi(2n)\sim 2\pi(n)$ means that $\pi(2n)-2\pi(n)=o(\pi(n))$ and $\pi((n+1)^2)\sim\pi(n^2)$ means that $\pi((n+1)^2)-\pi(n^2)=o(\pi(n^2))$. But $\pi(n^2)$ grows larger than $\pi(n)$ thus the remainder between $\pi((n+1)^2)$ and $\pi(n^2)$, and $\pi(2n)$ and $\pi(n)$ can be negligeable compared to $\pi(n^2)$, but not compared to $\pi(n)$, this is why it is not detected in your approach of Legendre's conjecture.

  • 1
    $\begingroup$ +1. The PNT doesn't tell us much about $\pi((n+1)^2)-\pi(n^2)$ because $(n+1)^2\sim n^2$. $\endgroup$ – DanielWainfleet Nov 29 '20 at 21:29

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.