11
$\begingroup$

Hello

Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression?

This question is usually asked for any $q$ instead of only prime value $q$, but I think if one restrict to only prime number $q$ Linnik bound would be easier to compute. Am I right?

Thank you.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ It's a reasonable hope ... but I do not know of any way to use the fact that the modulus is prime or that the progression starts at 1 to improve any known bounds. In fact, one could argue that both hurt your chances: $q$ being prime means that the primes are distributed among more residue classes modulo $q$, reducing the number in any one residue class; and results on "prime number races" say that primes are slightly less likely to be squares modulo $q$ (such as 1) than non-squares. $\endgroup$
    – Greg Martin
    Commented Nov 14, 2011 at 6:50
  • 3
    $\begingroup$ Dear M.B., it is funny that you ask this question right now. T. Xylouris, a colleague of mine in Bonn, has proved a result about this in 2009 - this is mentioned in the answer by Will - and he has still been working on it. I do not know the current state of his research, but his thesis defence on precisely that topic is the day after tomorrow. $\endgroup$
    – Robert Kucharczyk
    Commented Nov 14, 2011 at 11:02
  • 1
    $\begingroup$ It is believed that the least prime congruent to $a\pmod q$ is $\ll_\epsilon q^{1+\epsilon}$, and maybe even $\ll q(\log q)^{1+o(1)}$. The underlying heuristic is that the probability that all integers $n\le Q$ in the arithmetic progression $a\pmod q$ are not prime is $\prod_{n\le Q,n\equiv a\pmod q}(1-1/\log n)\approx (1-1/\log q)^{Q/q}$. This becomes $<1$ as soon as $Q\gg q\log q$. You can play with this quite a bit (e.g. consider only integers with no primes $\le(Q/q)^{1/3}$, and so on). See also mathoverflow.net/questions/834/…. $\endgroup$
    – Dimitris Koukoulopoulos
    Commented Nov 15, 2011 at 19:04
  • 3
    $\begingroup$ Maybe the right answer is $Q\ll\phi(q)\log^2q$: let $N$ be the set of $n\le Q$, all of whose prime factors are $<Q^\epsilon$, and which lie in the arithmetic progression $a\pmod q$. Then $N$ should contain a prime as soon as $Q\gg\phi(q)\log^2q$. jlms.oxfordjournals.org/cgi/reprint/s2-41/2/193.pdf $\endgroup$
    – Dimitris Koukoulopoulos
    Commented Nov 15, 2011 at 19:20

2 Answers 2

Reset to default
13
$\begingroup$

EDIT, September 2015. This material has come up again. Note that, in post and comments, i simply report things I found. I also did a computer program because I was curious about what might be the best possible behavior. It is probably time for a follow-up question.

Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. Thangadurai and A. Vatwani. They give an elementary argument to show $$ p \leq 2^{\phi(q) + 1} - 1.$$ The best unconditional result they report is T. Xylouris (2009), $$ p \leq c_1 q^{5.2}$$ which improves a 1992 result of Heath-Brown.

Apparently Oesterle showed that GRH implies $$ p \leq 70 q (\log q)^2 $$ which is much better. This was a private communication to the authors, not in the reference list.

EDIT TOOOOO: there is some doubt now, BACH and SORENSEN say, on their page 1718 (second page of the downloadable pdf) that Oesterle proved something different in 1979, also never published it. So perhaps the best GRH bound is theirs, $$ p \leq (1 + o(1)) (\phi(q) \log q)^2.$$ Perhaps Xylouris has also worked on this aspect.

Anyway, table of contents at CONTENTS

EDIT: I ran a little computer program for the GRH result, dropping the factor of 70... It certainly appears that the largest prime $q$ for which $ p > q (\log q)^2 $ is $q=5227$ with first prime congruent to $1\pmod q$ being $p=397253 = 1 + 76 \cdot 5227.$ Unprovable. Program run for $q < 10000000$ and print out only $ p > 0.8 \, q \, (\log q)^2. $ Each line is $q, \, p, \, p / \left( q \, (\log q)^2 \right)$ 

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./primes_in_progressions 
             2           3    3.12205
             3           7    1.93325
             5          11    0.849326
             7          29    1.09409
            19         191    1.15951
            31         311    0.850749
           227        5449    0.815642
           521       16673    0.817744
          3833      229981    0.881247
          5227      397253    1.03683
          6637      424769    0.82637
        138163    15750583    0.813731
        170167    24504049    0.992619
        177791    22757249    0.875941
        218531    27534907    0.833558
        325517    44921347    0.856523
        326617    42460211    0.806441
        707467   110364853    0.859855
       1940777   326050537    0.801413
       4722079  1104966487    0.99082
       8195953  1753933943    0.84445
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
Improve this answer
$\endgroup$
12
  • $\begingroup$ but $2^{\varphi(q)}$ is much bigger then $q^2$. So do you know if one can get a better bound then $2^{\varphi(q)}$ assuming $q$ is a prime? $\endgroup$
    – M.B
    Commented Nov 14, 2011 at 5:19
  • 3
    $\begingroup$ Two quick comments. It's maybe interesting to note that for prime $q$, it's easy to establish the Monthly bound: Any prime divisor $p$ of $2^q-1$ works. Also, I'm skeptical of the bound attributed to Oesterle. I'd wager that the best bounds, on ERH, are those in ams.org/journals/mcom/1996-65-216/ Note that their upper bound is bigger than $q^2$, and so doesn't settle the OP's problem. The discussion in this paper also suggests the result attributed to Oesterle is based on a misunderstanding or a typo. $\endgroup$
    – so-called friend Don
    Commented Nov 14, 2011 at 20:24
  • 1
    $\begingroup$ @Will Jagy: I believe that it should be $70q^2\log^2 q$ rather then $70q\log^2 q$. The former follows from GRH, whereas the later, an improvement to something of the form $q^{1+\delta}$ for any $\delta$, is only conjectured, and if proven would be a very strong result. $\endgroup$
    – Eric Naslund
    Commented Nov 22, 2011 at 23:03
  • 4
    $\begingroup$ In fact, the Bach-Sorenson bound has been improved. See math.uiuc.edu/~xiannan/QuaResL1ver2.pdf $\endgroup$
    – user709
    Commented Mar 15, 2012 at 7:06
  • 2
    $\begingroup$ I asked Joseph Oesterlé. There is indeed a typo in the Monthly article, he only proved $p\le 70 (q\log q)^2$, that is the same as Bach-Sorenson (with a larger constant). You can find the announcement of the Oesterlé's results in Astérisque 61 (in French) here. $\endgroup$
    – Bruno
    Commented Apr 27, 2022 at 16:22
1
$\begingroup$

One can clearly improve the L if one restricted the modulus q to prime numbers, however not anywhere near L=2 or so. E.g. in Heath-Brown's article 1992, it's mentioned how you get better results if q has bounded cube-part (i.e. if every prime number p, such that p^3 | q, is less then c1, then there is a c2=c2(1), such that p <= c2 * q^L. Here, the L will be a slightly better constant than if you don't use the assumption of the bounded cube-part, maybe something like 4.5 instead of 5.5, compare a note of "Meng").

The reason for this improvement is, that you have better bounds for character sums (to modulo q) due to Burgess, if you restrict q e.g. to primes (compare §2 of Heath-Brown's 1992 article). Improvement of these bounds then directly translate into improvements of zero-free regions for Dirichlet L-functions (modulo q).

As regards the thought if it would be easier if one restricted oneself only to one residue class, e.g. a mod q where the number a is fixed and q runs, I don't think you can gain something since everything you prove for a fixed a might likely be proven for any other a as well. That thought stems from looking at the proof of Linnik's theorem (meaning the classical proof, there are also some others out there, originating more from sieve theory; I don't know if they would give a different answer but I would be surprised): The whole reasoning is very "symmetric" for whatever a you take. It's not like your average proof in elementary prime number theory (or sieve theory), where you work with a particular sequence a+kq and have sums over different values etc.

Hope this helps.

Improve this answer
$\endgroup$

You must log in to answer this question.

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