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

$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:

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

The theorem is named after Yuri Vladimirovich Linnik, who proved it in 1944. 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.

On the generalized Riemann hypothesis it can be shown that

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

where $\varphi$ is the totient function, and the stronger bound

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

has been also proved.

It is also conjectured that:

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

Bounds for L

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

L ≤	Year of publication	Author
10000	1957	Pan
5448	1958	Pan
777	1965	Chen
630	1971	Jutila
550	1970	Jutila
168	1977	Chen
80	1977	Jutila
36	1977	Graham
20	1981	Graham (submitted before Chen's 1979 paper)
17	1979	Chen
16	1986	Wang
13.5	1989	Chen and Liu
8	1990	Wang
5.5	1992	Heath-Brown
5.18	2009	Xylouris
5	2011	Xylouris

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