Linnik's theorem

Template:Short description Linnik's theorem in analytic number theory answers a natural question after Dirichlet's theorem on arithmetic progressions. It asserts that there exist positive c and L such that, if we denote p(a,d) the least prime in the arithmetic progression

<math>a + nd,\ </math>

where n runs through the positive integers and a and d are any given positive coprime integers with 1 ≤ a ≤ d − 1, then:

<math>\operatorname{p}(a,d) < c d^{L}. \; </math>

The theorem is named after Yuri Vladimirovich Linnik, who proved it in 1944.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> Although Linnik's proof showed c and L to be effectively computable, he provided no numerical values for them.

It follows from Zsigmondy's theorem that p(1,d) ≤ 2^d − 1, for all d ≥ 3. It is known that p(1,p) ≤ L_p, for all primes p ≥ 5, as L_p is congruent to 1 modulo p for all prime numbers p, where L_p denotes the p-th Lucas number. Just like Mersenne numbers, Lucas numbers with prime indices have divisors of the form 2kp+1.

Properties

It is known that L ≤ 2 for almost all integers d.<ref>Template:Cite journal</ref>

On the generalized Riemann hypothesis it can be shown that

<math>\operatorname{p}(a,d) \leq (1+o(1))\varphi(d)^2 (\log d)^2 \; ,</math>

where <math>\varphi</math> is the totient function,<ref name="heath-brown"/> and the stronger bound

<math>\operatorname{p}(a,d) \leq \varphi(d)^2 (\log d)^2 \; ,</math>

has been also proved.<ref name="LamzouriLiSoundararajan">Template:Cite journal</ref>

It is also conjectured that:

<math>\operatorname{p}(a,d) < d^2. \; </math> <ref name="heath-brown"/>

Bounds for L

The constant L is called Linnik's constant<ref>Template:Cite book</ref> and the following table shows the progress that has been made on determining its size.

L ≤	Year of publication	Author
10000	1957	Pan<ref>Template:Cite journal</ref>
5448	1958	Pan
777	1965	Chen<ref>Template:Cite journal</ref>
630	1971	Jutila
550	1970	Jutila<ref>Template:Cite journal</ref>
168	1977	Chen<ref>Template:Cite journal</ref>
80	1977	Jutila<ref>Template:Cite journal</ref>
36	1977	Graham<ref>Template:Cite thesis</ref>
20	1981	Graham<ref>Template:Cite journal</ref> (submitted before Chen's 1979 paper)
17	1979	Chen<ref>Template:Cite journal</ref>
16	1986	Wang
13.5	1989	Chen and Liu<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref>
8	1990	Wang<ref>Template:Cite journal</ref>
5.5	1992	Heath-Brown<ref name="heath-brown">Template:Cite journal</ref>
5.18	2009	Xylouris<ref>Template:Cite journal</ref>
5	2011	Xylouris<ref>Template:Cite thesis</ref>
5 − ε	2018	Xylouris<ref>Linniks Konstante ist kleiner als 5</ref>

Moreover, in Heath-Brown's result the constant c is effectively computable.