3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user160539
    Oct 15 '20 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy