11
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ To my knowledge the best known bound due to GRH is something like $p \leq q^{2 + \epsilon}$. If there is a Siegel zero, then an exponent strictly smaller than $2$ is possible. I believe the latter is due to Friedlander and Iwaniece. $\endgroup$
    – Stanley Yao Xiao
    Commented Sep 10, 2015 at 17:22
  • $\begingroup$ The $70$ appears in this paper in "private communication": hri.res.in/~thanga/papers/final-amm.pdf $\endgroup$
    – joro
    Commented Sep 11, 2015 at 8:13
  • $\begingroup$ As mentioned below, there is a typo in reporting the "private communication" according to J. Oesterlé himself. He proved $p\le 70 (q\log q)^2$, not $p\le 70 q(\log q)^2$. Cf my comment mathoverflow.net/questions/80865/…. $\endgroup$
    – Bruno
    Commented Apr 27, 2022 at 16:28

2 Answers 2

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 1
    $\begingroup$ In terms of the discriminant $\Delta$ of the cyclotomic field $C_q$ the optimistic conjecture is expressed (in slightly less precise form to fix ideas) as a bound $\ll \log{\Delta} \cdot (\log{\log{\Delta}})^{1+o(1)}$. I wonder if anything has been said about the literal extension of this to a hypothetical bound on the first split prime for a general number field $K$, where now $\Delta = |D_{K/\mathbb{Q}}|$? If true, this would break Dobrowolski's bound on the Lehmer problem and yield $h(\alpha) \gg d^{-1} \cdot (\log{d})^{-1-o(1)}$. Is there a known obstruction in this generality? $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 10, 2015 at 20:48
  • 1
    $\begingroup$ @VesselinDimitrov: That's an interesting observation, also consistent for example with what we believe about the least quadratic non-residue. Do you have in mind that the degree of the number field is fixed and discriminant goes to infinity, where I would believe a heuristic of this type; or do you have in mind that the degree can go to infinity as well (which is the cyclotomic case, but at least the discriminant is pretty big), where I would be more cautious (e.g. with minimal discriminants)? (Dobrowolski's argument is not so fresh in my mind that I can see what you're thinking.) $\endgroup$
    – Lucia
    Commented Sep 10, 2015 at 21:04
  • 1
    $\begingroup$ @VesselinDimitrov: Thanks for those remarks. It seems to me that the lower bounds for Mahler measures precisely corresponds to the case of large degree and small discriminant. I don't really have a good intuition for that case -- and one also knows that discriminants of number fields are small precisely when there are no primes of small norm. It would be interesting to figure out a uniform such conjecture, but I don't know offhand what to expect. $\endgroup$
    – Lucia
    Commented Sep 10, 2015 at 22:29
  • 1
    $\begingroup$ It wasn't so precise a remark, but if you look at the Odlyzko bounds for discriminants, then if there is a small prime that splits completely then one gets an improvement of those bounds. Thus for minimal discriminants not too far from the Odlyzko bounds, one usually has that most of the small primes are not split. $\endgroup$
    – Lucia
    Commented Sep 11, 2015 at 3:17
  • 1
    $\begingroup$ I see - as in Tsfasman and Vladut's paper Infinite global fields and generalized Brauer-Siegel theorem, if I understand this correctly, which improves the Odlyzko bounds under additional splitting conditions at finite primes. Thank you! (By the way, above I made a pair of cancelling sign errors. The Kronecker invariant should be the constant term of $\zeta_K'(s)/\zeta_K(s)$ at $s = 1$, and its positivity would be one way to quantify the deficiency of small split primes.) $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 11, 2015 at 4:17
2
$\begingroup$

The $70$ comes from the claimed result of Oesterle mentioned here (which is supposed to use GRH only).

Improve this answer
$\endgroup$
7
  • $\begingroup$ Right, I guess I did not make that clear. Either way, I was entirely reporting hearsay, I figured a new question might get traction with people who have some idea how to do this stuff themselves, and that has happened. $\endgroup$
    – Will Jagy
    Commented Sep 10, 2015 at 19:55
  • $\begingroup$ @WillJagy there was a related question by joro (where $q$ is not prime but a primorial number (the product of the first $k$ primes). There, it seems that the observed result is even better than $q \log^2 q,$ more like $q \log q.$ $\endgroup$
    – Igor Rivin
    Commented Sep 10, 2015 at 20:06
  • $\begingroup$ hmmm... not exactly hearsay, printsay perhaps $\endgroup$
    – Will Jagy
    Commented Sep 10, 2015 at 20:06
  • $\begingroup$ Yeah, I looked briefly at both joro's recent questions after his message to me. $\endgroup$
    – Will Jagy
    Commented Sep 10, 2015 at 20:07
  • $\begingroup$ Oh, and directly after his message, I put a reply calling his attention to this question. $\endgroup$
    – Will Jagy
    Commented Sep 10, 2015 at 20:09

You must log in to answer this question.

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