[Math] Update for 2015: least prime of form nq+1, with q prime

analytic-number-theorynt.number-theoryprime numbers

I have received a complaint about my 2011 answer

least prime in a arithmetic progression

which, indeed, gives conflicting reports about this:

given a prime $q,$ what can we say about an upper bound for the smallest prime $p$ in the arithmetic progression $n q + 1$?

Note that I do not see anything using the number $70$ in THIS.

I guess there are about three parts:

(A) What is the most optimistic upper bound, i.e. numerical computations? I had a short computer run in my answer.

(B) What is the strongest result one gets assuming a generalized/extended Riemann Hypothesis?

(C) What is the strongest unconditional result?

Best Answer

The most optimistic conjecture is that the least prime in this (or indeed any progression $a\pmod q$) is $\ll q (\log q)^2$. This is an analog of Cramer's conjecture on primes in short intervals, so way beyond reasonable conjectures like GRH!

On GRH Lamzouri, Li, and Soundararajan (see Corollary 1.2) have shown that the least prime that is $a\pmod q$ (with $q>3$ and $(a,q)=1$) is bounded by $$ \le (\phi(q) \log q)^2. $$ Note this is an explicit inequality. Moreover they note that asymptotically one could get an estimate $\le (1-\delta +o(1)) (\phi(q)\log q)^2$ for some $\delta >0$.

Unconditionally, Linnik was the first to show that the least prime is $\ll q^{L}$ for some fixed $L$, and over the years this has been improved and the current record is that $L=5$ is permissible due to Xylouris.

Related Question