# What are the best known bounds for the smallest primes larger than $n$?

Let $$n>1$$ be some integer. Define $$p, q$$ to be the smallest primes larger than $$n$$, where $$p. What are the best known effective lower and upper bounds for $$p$$ and $$q$$ ?

I will write here an approach which gives some interesting upper bounds on $$p$$ and $$q$$. The trivial lower bounds are $$p \geq n$$ and $$q \geq p (\geq n)$$. The idea shown here does not give an effective method for evaluating some lower bounds, so this is only a partial answer to your question. This approach is based on the following result and on some of its extensions:

Bertrand's postulate: For all integers $$n >1$$, there exists a prime $$m$$ such that $$n < m < 2n$$

By applying this result, we get a first upper bound on $$p$$: $$p < 2n$$. The bounds on $$q$$ will all follow from this result and the bounds on $$p$$, so we will firstly focus only on $$p$$.

Many improvements of Bertrand's postulate are known. Here you can find all the extensions which I will use below, and even more.

The first improvement holds for $$n \geq 25$$: there exists a prime $$m$$ such that $$n < m < \frac{6}{5} n$$ (J. Nagura, 1952). So for such $$n$$'s we have the bound $$p < \frac{6}{5} n$$.

For $$n \geq 3275$$, there exists a prime $$m$$ such that $$n < m \leq (1+ \frac{1}{2 \ln^2 n}) n$$ (P. Dusart, 2010).

For $$n \geq 89693$$, there exists a prime $$m$$ such that $$n < m \leq (1+ \frac{1}{\ln^3 n}) n$$ (P. Dusart, 2016).

For $$n \geq 396738$$, there exists a prime $$m$$ such that $$n < m \leq (1+ \frac{1}{25 \ln^2 n}) n$$ (P. Dusart, 2010).

For $$n \geq 2010760$$, there exists a prime $$m$$ such that $$n < m \leq \frac{16598}{16597} n$$ (L. Schoenfeld, 1976).

For $$n \geq 468991632$$, there exists a prime $$m$$ such that $$n < m \leq (1+ \frac{1}{5000 \ln^2 n}) n$$ (P. Dusart, 2016).

All these results give bounds on $$p$$. Now such results can be applied to $$p$$ instead of $$n$$: for instance, for $$n >1$$ we have $$p < q < 2p < 4n$$, for $$n \geq 25$$ we have $$p < q < \frac{6}{5}p < \frac{36}{25}n$$ and so on. In the general case $$n>1$$, we can actually find a better bound using a result of M. El Bachraoui (2006), which tells us that there exists a prime $$m$$ between $$2n$$ and $$3n$$. Thus, $$q < 3n$$. Summing up, we have the following result:

Theorem: $$1 < n < 25 \Rightarrow p < 2n, \, q < 3n$$ $$25 \leq n < 3275 \Rightarrow p < \frac{6}{5} n, \, q < \frac{36}{25} n$$ $$3275 \leq n < 89693 \Rightarrow p \leq (1+ \frac{1}{2 \ln^2 n}) n, \, q \leq (1+ \frac{1}{2 \ln^2 n})^2 n$$ $$89693 \leq n < 396738 \Rightarrow p \leq (1+ \frac{1}{\ln^3 n}) n, \, q \leq (1+ \frac{1}{\ln^3 n})^2 n$$ $$396738 \leq n < 2010760 \Rightarrow p \leq (1+ \frac{1}{25 \ln^2 n}) n, \, q \leq (1+ \frac{1}{25 \ln^2 n})^2 n$$ $$2010760 \leq n < 468991632 \Rightarrow p \leq \frac{16598}{16597} n, \, q \leq \frac{275493604}{275460409} n$$ $$n \geq 2010760 \Rightarrow p \leq (1+ \frac{1}{5000 \ln^2 n}) n, \, q < (1+ \frac{1}{5000 \ln^2 n})^2 n$$

EDIT: as @Mark suggested, the lower bounds $$p \geq n$$, $$q \geq n+k$$ are tight. Here, $$k$$ is the smallest integer such that there exist infinitely many primes which differ by $$k$$. By the work of the Polymath8 project, it is known that $$k \leq 246$$ unconditionally. Assuming the twin prime conjecture, $$k=2$$.

• Thanks (+1), this is so insightful. But since it is a partial answer, maybe I shouldn't accept it as an answer as yet, to give room for someone who might post a complete answer.
– user160539
Oct 15, 2020 at 18:20