11

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?

Community
  • 1
Will Jagy
  • 25,349
  • 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. – Stanley Yao Xiao Sep 10 '15 at 17:22
  • The $70$ appears in this paper in "private communication": http://www.hri.res.in/~thanga/papers/final-amm.pdf – joro Sep 11 '15 at 08:13
  • 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 https://mathoverflow.net/questions/80865/least-prime-in-a-arithmetic-progression#comment1082136_80867. – Bruno Apr 27 '22 at 16:28

2 Answers2

17

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.

Lucia
  • 43,311
  • That's a good point, and not something I would have figured out, that the $q \log^2 q$ I found numerically is related to Cramer's rather than GRH. – Will Jagy Sep 10 '15 at 17:33
  • Lucia, do you think there is anything in print that, say, sketches how Cramer's general viewpoint suggests $q \log^2 q?$ – Will Jagy Sep 10 '15 at 18:03
  • It's just the usual reasoning: the "probability" of $kq+1$ being prime is about $q/(\phi(q)\log q)$ (let's just say about $1/\log q$ for simplicity), and then you use a "Borel-Cantelli" heuristic (and arrive at the conjecture of $\ll \phi(q) (\log q)^2$). I don't know if anyone stated exactly this -- Granville and Pomerance did conjecture in a paper that sometimes the least prime should be $\gg \phi(q) (\log q)^2$ (more precisely, for each large $q$ they conjectured that there is some progression for which the least prime is that large). – Lucia Sep 10 '15 at 18:15
  • 1
    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? – Vesselin Dimitrov Sep 10 '15 at 20:48
  • 1
    @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.) – Lucia Sep 10 '15 at 21:04
  • We would need the degree to go to infinity in this kind of application. Actually what I had in mind is simpler than Dobrowolski's argument, and consists of combining two observations. First, if $\alpha$ is an algebraic unit not a root of unity and $p$ a split prime in $\mathbb{Q}(\alpha)$, then $\xi := \alpha^{p-1} - 1$ is a non-zero algebraic integer having positive valuation at all places dividing $p$; applying the product formula to $\xi$ gives $h(\alpha) \geq (\log{(p/2)})/(p-1)$. (If $p = 2$, do the same with $\alpha^3-1$ instead.) – Vesselin Dimitrov Sep 10 '15 at 21:49
  • And second, Mahler's inequality (interpreting a discriminant as the square of a Vandermonde determinant) bounds the absolute logarithmic discriminant of that field (indeed the discriminant of the minimum polynomial of $\alpha$) by $d \log{d} + 2d(d-1)h(\alpha)$. But we can assume $h(\alpha) < 1/d$ in this problem, and the optimistic hypothesis would give us a small prime $p$ to use in the first observation. – Vesselin Dimitrov Sep 10 '15 at 21:51
  • 1
    @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. – Lucia Sep 10 '15 at 22:29
  • "Discriminants of number fields are small precisely when there are no primes of small norm" - I am not sure I see this outside of the setting of Lehmer's problem (which, indeed, concerns WLOG only/precisely the number fields of log discriminant $\ll d\log{d}$ and no unramified primes of norm $< d\log{d}$. Perhaps the qualifier "unramified" here could be also dispensed with.). For polynomials this is clear, just because a prime of small norm would have to divide the discriminant highly, but the fields say of bounded root discriminant will most likely never be monogenic. – Vesselin Dimitrov Sep 11 '15 at 03:04
  • Is this something easy to explain in a few lines, or is there a handy reference? For instance, will a sequence of fields with bounded root discriminant and degrees going to infinity (such as an infinite unramified tower), never contain primes of small norm? Will the Euler-Kronecker constants (the constant terms of $-\zeta_K'(s)/\zeta_K(s)$ at $s = 1$) eventually all be negative? (Or perhaps I should make this into a different question?) The negativity of these quantities is related to the lack of primes of small norm; would they nearly achieve $-\log{\sqrt{D}}$ when $D$ is unusually small? – Vesselin Dimitrov Sep 11 '15 at 03:14
  • 1
    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. – Lucia Sep 11 '15 at 03:17
  • 1
    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.) – Vesselin Dimitrov Sep 11 '15 at 04:17
2

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

Community
  • 1
Igor Rivin
  • 95,560
  • 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. – Will Jagy Sep 10 '15 at 19:55
  • @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.$ – Igor Rivin Sep 10 '15 at 20:06
  • hmmm... not exactly hearsay, printsay perhaps – Will Jagy Sep 10 '15 at 20:06
  • Yeah, I looked briefly at both joro's recent questions after his message to me. – Will Jagy Sep 10 '15 at 20:07
  • Oh, and directly after his message, I put a reply calling his attention to this question. – Will Jagy Sep 10 '15 at 20:09
  • @WillJagy Why not try to debug the printsay? Hypothetically (flawed) proof may really exist. Maybe someone of sufficient math reputation spam Oesterlé? – joro Sep 11 '15 at 08:07
  • I have no math reputation, still I asked J. Oesterlé. The claimed result is a typo, cf my comment https://mathoverflow.net/questions/80865/least-prime-in-a-arithmetic-progression#comment1082136_80867. – Bruno Apr 27 '22 at 16:27