# Smallest prime in an arithmetic progression

Let $\{a_n\}_{n\in\mathbb{N}}$ be defined as $a_n = a + bn$ for some $a, b >0,(a, b) = 1$. Are there good bounds on the minimal $k$ s.t. $a_k$ is prime. It is well known that there are infinitely many primes in this series,

-
Search under Linnik's constant. Linnik showed that the least such prime is bounded by $\ll b^{L}$ for a constant $L$, which has been improved over the years, most recently by Xylouris. –  Lucia Aug 14 '14 at 17:46

This is Linnik's theorem, and the best known bound is $O(b^5)$ due to Xylouris. (This is in the Wikipedia page, and as I admitted in this year's JMM I added it to the Wikipedia page. It's in his thesis but otherwise unpublished as far as I know.)

-
If one assumes GRH, then one can obtain much stronger results: see, e.g. Corollary 1.2 of arxiv.org/abs/1309.3595, which shows the strict bound $(\phi(b) \log b)^2$. –  Peter Humphries Aug 14 '14 at 18:46
And it is conjectured that much more that even what can be proved using GRH is true, namely that the first prime is O(b^{1+\epsilon}) for all $\epsilon>0$, or perhaps even $O(b \log^2b)$. –  Joël Aug 14 '14 at 21:03
Xylouris has 5.18 in Xylouris, Triantafyllos, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith. 150 (2011), no. 1, 65–91, MR2825574 (2012m:11129). –  Gerry Myerson Aug 14 '14 at 23:25
@GerryMyerson: Right, but as far as I know the 5.00 is unpublished. –  Charles Aug 14 '14 at 23:56
I found Xylouris' thesis online: bib.math.uni-bonn.de/downloads/bms/BMS-404.pdf –  GH from MO Aug 15 '14 at 0:34