Linnik's theorem

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

${\displaystyle a+nd,\ }$

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

${\displaystyle \operatorname {p} (a,d)<cd^{L}.\;}$

The theorem is named after Yuri Vladimirovich Linnik, who proved it in 1944.^[1][2] 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.^[3]

On the generalized Riemann hypothesis it can be shown that

${\displaystyle \operatorname {p} (a,d)\leq (1+o(1))\varphi (d)^{2}(\log d)^{2}\;,}$

where ${\displaystyle \varphi }$ is the totient function,^[4] and the stronger bound

${\displaystyle \operatorname {p} (a,d)\leq \varphi (d)^{2}(\log d)^{2}\;,}$

has been also proved.^[5]

It is also conjectured that:

${\displaystyle \operatorname {p} (a,d)<d^{2}.\;}$ ^[4]

Bounds for L

The constant L is called Linnik's constant^[6] and the following table shows the progress that has been made on determining its size.

L ≤	Year of publication	Author
10000	1957	Pan[7]
5448	1958	Pan
777	1965	Chen[8]
630	1971	Jutila
550	1970	Jutila[9]
168	1977	Chen[10]
80	1977	Jutila[11]
36	1977	Graham[12]
20	1981	Graham[13] (submitted before Chen's 1979 paper)
17	1979	Chen[14]
16	1986	Wang
13.5	1989	Chen and Liu[15][16]
8	1990	Wang[17]
5.5	1992	Heath-Brown[4]
5.18	2009	Xylouris[18]
5	2011	Xylouris[19]
5 − ε	2018	Xylouris[20]

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