There is a prime between $n$ and $n^2$, without Bertrand

Question

Consider the following statement:

For any integer $n>1$ there is a prime number strictly between $n$ and $n^2$.

This problem was given as an (extra) qualification problem for certain workshops (which I unfortunately couldn't attend). There was a requirement to not use Bertrand's postulate (with which the problem is nearly trivial), and I was told that there does exist a moderately short proof of this statement not using Bertrand. This is my question:

How can one prove the above statement without Bertrand postulate or any strong theorems?

Although I can only accept one answer, I would love to see any argument you can come up with.

I would also want to exclude arguments using a proof of Bertrand's postulate, unless it can be significantly simplified to prove weaker statement.

Thank you in advance.

Answer 1

I have stumbled upon this paper due to Erdős, which in the course of proving something far more general proves this result (see a remark at the end of this page). I am replicating that proof here, with minor modifications by myself.

Suppose $n>8$ and that there are no primes between $n,n^2$. Since clearly (obvious induction works) $\pi(n)\leq\frac{1}{2}n$, by assumption we have $\pi(n^2)=\pi(n)\leq\frac{1}{2}n$. Now consider number $\binom{n^2}{n}$. All of its prime factors are less than $n^2$, and so less than $n$. We have the following inequality:

$$\binom{n^2}{n}=\frac{n^2}{n}\frac{n^2-1}{n-1}\dots\frac{n^2-n+2}{2}\frac{n^2-n+1}{1}>\frac{n^2}{n}\frac{n^2}{n}\dots\frac{n^2}{n}\frac{n^2}{n}=\left(\frac{n^2}{n}\right)^n=n^n$$

At the same time, consider $p$ prime and let $p^a$ be the greatest power of $p$ less than or equal to $n^2$. Since $\binom{n^2}{n}=\frac{(n^2)!}{(n^2-n)!n!}$, By Legendre's formula, exponent of the greatest power of $p$ dividing this binomial coefficient is equal to

$$\left(\left\lfloor\frac{n^2}{p}\right\rfloor-\left\lfloor\frac{n^2-n}{p}\right\rfloor-\left\lfloor\frac{n}{p}\right\rfloor\right)+\left(\left\lfloor\frac{n^2}{p^2}\right\rfloor-\left\lfloor\frac{n^2-n}{p^2}\right\rfloor-\left\lfloor\frac{n}{p^2}\right\rfloor\right)+\dots+\left(\left\lfloor\frac{n^2}{p^a}\right\rfloor-\left\lfloor\frac{n^2-n}{p^a}\right\rfloor-\left\lfloor\frac{n}{p^a}\right\rfloor\right)\leq 1+1+\dots+1=a$$

(first equality is true, because all further terms in the sum are zero. First inequality is true because for any $a,b\in\Bbb R$ $\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\in\{0,1\}$)

Since $\binom{n^2}{n}$ is a product of at most $\pi(n)$ prime powers, all at most $p^a\leq n^2$ (by above), we must have

$$\binom{n^2}{n}\leq (n^2)^{\pi(n)}\leq (n^2)^{\frac{1}{2}n}=n^n$$

We have proved two contradictory inequalities, so this ends the proof by contradiction.

Answer 2

After a little bit of searching on the net, it seems that this result isn't as easy to prove (without Bertrand that is) as one would hope. However, here: https://mathoverflow.net/a/52085, you can find the proof of the result you're looking for. Basically, the author shortens Bertrand's Postulate's proof so that it only proves your desired result.

Answer 3

I've come up with a simple proof based on the prime-counting function $\pi(x)$, which I'm pretty sure doesn't depend on Bertrand's Postulate.

First, I will prove a lemma that for every prime $n$, there is another prime $p$ with $n < p < n^2$. I will use this result later to show the general result (i.e. for composite $p$ as well).

Based on some inequalities of $\pi(x)$ and the value of a related constant we have $$\frac{n}{\log n} < \pi(n) < C\frac{n}{\log n}\text{, where }C=\pi(30)\frac{\log 113}{113} \approx 1.255$$ for all $n \geq 17$. We want to prove that for all prime $n$ we have $$\pi(n^2) > \pi(n)$$ or $$\pi(n^2) - \pi(n) > 0,$$ so we look at the upper bound of $\pi(n)$ and the lower bound of $\pi(n^2)$ to find a minimum difference.

We have $$\begin{align} \pi(n^2) - \pi(n) &> \frac{n^2}{\log n^2} - C\frac{n}{\log n} \\ &= \left(\frac{n}{2} - C\right)\frac{n}{\log n} \end{align} $$ so the conclusion is satisfied whenever $$\left(\frac{n}{2} - C\right)\frac{n}{\log n} > 0.$$ Since for all prime $n$ we have $$\frac{n}{\log n} > 0,$$ we find that $\pi(n^2) - \pi(n) > 0$ whenever $\frac{n}{2} - C > 0$, which gives us $$n > 2C \approx 2.51$$ so $$n \geq 3$$ which is true for every prime $n \geq 17$.

For lesser primes we can prove things manually: $$2 < 3 < 2^2$$ $$3 < 5 < 3^2$$ $$5 < 7 < 5^2$$ $$7 < 11 < 7^2$$ $$11 < 13 < 11^2$$ $$13 < 17 < 13^2$$ This concludes the lemma.

Then, we must prove that for every composite $n$ there is a prime $p$ with $n < p < n^2$. Take the largest prime less than $n$ and call that $p_m$. Then by applying the lemma we find that there is some prime $p$ such that $$p_m < p < p_m^2.$$ Because $p > p_m$, $p_m$ is the largest prime less than $n$, and $n$ is composite, we find that $$p < n.$$ Also, we have $$p < p_m^2 < n^2,$$ so we reach the second conclusion: if $n$ is composite then there's a prime $p$ such that $$n < p < n^2.$$

Now we've proved the original statement for both prime and composite $n$, and the proof is complete.