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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – OneTwoOne Oct 15 at 18:20

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.