At least one prime between $\sqrt{n}$ and $n$?

Solution 1:

Not a full answer, but hopefully helpful progress:

Look at $M_p := \binom{p^2}{p~p~\ldots~p} = \frac{p^2!}{p!^p}$ where $p$ is a prime number, let $v_q(x)$ the q-adic valuation of $M_p$ : $$ v_q(M_p) = \sum_{k \geq 1} \lfloor\frac{p^2}{q^k}\rfloor - p\lfloor \frac{p}{q^k}\rfloor \leq (p-1)\lfloor \log_q(p^2) \rfloor $$ Thus, $$ q^{v_q(M_p)} \leq p^{2(p-1)} $$ In particular, if the interval $\{p+1,\ldots,p^2\}$ does not include any prime number, then $$ M_p \leq p^{2(p-1)\pi(p)} $$ where $\pi(p)$ is the number of prime numbers is the interval $\{p+1,\ldots,p^2\}$.

Moreover we know that $\ln(n!) \sim n \ln(n)$.Thus, $$ \ln(M_p) \sim p^2 \ln(p) $$ Because $2(p-1)\pi(p) \ln(p)$ is very small compared to $p^2 \ln(p)$

We know that your inequality will be true from a certain rank. Finding explicit bounds for a similar result to $\ ln (n!) \sim n \ ln (n)$, we will win...

Edit:

$$n \ln(n) \geq \ln(n!) \geq \frac{2n}{3} \ln(\frac{n}{3}) $$

Then, $$ \ln(M_p) \geq \frac{9p^2}{10} \ln(\frac{p^2}{10}) - p^2 \ln(p) = \frac{p^2}{10} (8\ln(p) - 9 \ln(10)) $$ Therefore, $\ln(M_p) \geq \frac{p^2}{2} \ln(p)$ since $ln(p) \geq 10^3$.

Yet, $$\pi(n) \leq 4 + \frac{1}{2} \frac{2}{3} \frac{4}{5} \frac{6}{7} (n+1) = 4 + \frac{8(n+1)}{35}$$ for all integer n$\geq 0$.

Thus,

$$\frac{p^2}{2} \ln(p) \leq \ln(M_p) \leq \frac{2}{35}(p-1)(8p+140)\ln(p)$$

In the same way, $$ 35 p^2 \leq 4(p-1)(8p+140) $$ ie $$ 0 \geq 35p^2-4(p-1)(8p+140) =3p^2-528p+560 > 3((p-88)^2-88^2) $$

Therefore $p < 176$

Thus , it is known that the interval $ \{p+1,\ldots,p^2-1\}$ has a prime number when $p \geq 10^3$

but $3, 7, 47, 1009$ are prime numbers.

So the interval $\{p +1, \ldots , p ^ 2-1 \}$ has a prime number when $p \geq 2$ . This completes your exercise .

Solution 2:

By way of a bump, I'm answering my question to give two facts and hope someone can give a good answer from this or at least convince me it will be too hard to do.

The first is that if $n=pq$ where $p$ and $q$ are primes then the claim is true. This is because if both $p,q<\sqrt{n}$ we get $n<n$.

The second is that the statement is equivalent to proving that if $p$ is a prime, the next prime $q$ is $q<p^2$. That is, the statement holds if it holds for $n=p^2$, $p$ prime. One does an induction argument, assuming there is a prime $p$ with $\sqrt{n}<p<n$, and then consider the interval $\sqrt{n+1}$ to $n+1$. If it doesn't contain a prime, it must be because $\sqrt{n}<p \leq \sqrt{n+1}$. Squaring gives the conclusion $n+1=p^2$, reducing the problem.