16
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear Engelbrekt, do you know a reference for the conjecture of H. L. Montgomery you mention ? (I mean, the which implies both GRH and Elliot-Halberstam). Thanks $\endgroup$
    – Joël
    Commented Sep 2, 2013 at 0:18
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ moonface: I'm a bit confused, here. Certainly heuristics given by the PNT would show that for most primes you have p^{1+\epsilon}, but I don't think this rules out the possibility that there are infinitely many primes for which it's not true. (Certainly it doesn't trivially rule out the possibility!) $\endgroup$
    – Harrison Brown
    Commented Oct 18, 2009 at 11:47
  • 2
    $\begingroup$ (This might show up twice by accident, sorry.) Let e > 0. Mindlessly applying the heuristic, the chance f(p) that "there is no prime less than p^{1+e} in the progression" decreases very fast with p; in fact, the sum of f(p) over all p converges, suggesting this event happens only finitely often. For an example of the limitations of such reasoning, see "Primes in short intervals" by H. Maier. $\endgroup$
    – moonface
    Commented Oct 18, 2009 at 17:51
3
$\begingroup$

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?

Improve this answer
$\endgroup$
3
  • $\begingroup$ I should get some sleep rather than posting further on this, but it's probably also worth thinking about the Elliott-Halberstam conjecture, which now that I think about it might be strong enough to answer the question in the negative. $\endgroup$
    – Harrison Brown
    Commented Oct 17, 2009 at 6:20
  • $\begingroup$ Nope, no heuristics as yet. It's just that this is the bound we need for the group theory problem, and it is exactly at the right place to meet the bounds that you expect from GRH. $\endgroup$
    – David E Speyer
    Commented Oct 17, 2009 at 6:20
  • $\begingroup$ Hmm, in that case I'm unconvinced that it'd be reasonable to conjecture the affirmative, and I'd look at some of the crazy stuff that's stronger than GRH. I now think that Elliott-Halberstam isn't actually enough for a negative answer, but it seems to provide evidence in that direction. (I'm not getting out pencil and paper because I plan to get some sleep tonight.) $\endgroup$
    – Harrison Brown
    Commented Oct 17, 2009 at 6:28
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .