Arithmetic progressions without small primes The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? :
Is it known that there are infinitely many primes p for which the least prime q which is 1 mod p is > c p^2 (for some positive constant c, independent of p)?
Wikipedia's article on primes in arithmetic progressions says that the expected bound for the least prime is p^{2 + \epsilon}, given various strengthenings of the Riemann Hypothesis, but it doesn't say much about lower bounds.
By the way, for the applications in the linked post, it would be even better if the same lower bound applied to finding a prime power q which is 1 mod p.
 A: I don't have a reference for you, but what GRH proves has nothing to do with the truth; the proof is "lossy." The expected answer would be p^{1+\epsilon} for the smallest prime congruent to 1 mod p: an integer around N is prime with probability 1/log(N), and in most regimes (although not all) this makes accurate predictions. 
A: I don't know a definite answer either way, but here's one line of questioning: I believe it is a known result that Linnik's constant is at least 2 (although it's less for almost all integers.) Do the methods used to prove that fail to distinguish between primes and composites, or between some set in which the primes have positive density and some set in which they don't?
From the other direction, however, it's apparently possible on GRH to bound the error term in the PNT in arithmetic progressions (as in Brun-Titchmarsh, although I don't think they're that tight) when N > q^{2+\epsilon}. This would put some rather tricky constraints on the error term, which one could take as evidence against it.
By the way, do you have a heuristic argument that, for instance, there are infinitely many primes for which the least prime congruent to 1 mod p is at least c p^(2-\epsilon)? Or even at least c p^e for some e > 1?
A: For a fixed a>0 it is known that there are infinitely many moduli q such that the least prime in the arithmetic progresion a mod q is at least >> q ln (q) lnln (q) ln ln ln ln (q) / (ln ln ln(q) )^2. This can be found in:
Prachar, K. Über die kleinste Primzahl einer arithmetischen Reihe. (German) J. Reine Angew. Math. 206 1961. 
To the best of my knowledge this is the world record.
A: It is firmly expected that for every \epsilon > 0 each aritmetic progression with difference q and terms coprime with q will contain a prime <<{\epsilon} q^{1 + \epsilon}. 
This is a direct consequence of a conjecture of H. L. Montgomery (not the one on pair correlations, another one), which implies both the GRH and the Elliott-Halberstam conjecture. But the upper bound $\ll {\epsilon} q^{1 + \epsilon}$ for the least prime in an arithmetic progression was conjectured by S. Chowla (in his book "The Riemann Hypothesis and Hilbert's tenth problem"), and probably by others independently of him, years before Montgomery made his conjecture, and presumably on the basis of the same kind of heuristic argument that moonface advances. In fact, I think that even an upper bound as strong as qlog(q)^2 has been conjectured, though I won't swear to that. But it is definitely known that qlog(q) won't work. The Montgomery conjecture seems reasonable, because it rests on the assumption that there is square root cancellation in a certain sum with D-characters as coefficients in an explicit formula - this ties in with moonface's comment about the proof that GRH implies L \leq 2 being "lossy". On the other hand, one cannot expect to get q^{1 + \epsilon} out of the Elliott-Halberstam conjecture in any direct way, because that is an averaging kind of statement. You would not expect to get L \leq 2 out of the Bombieri-A. I. Vinogradov theorem either, for that is an averaged version of GRH. The point is that information is needed about every single one of the arithmetic progressions individually.
