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. 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<sup>d</sup> − 1, for all d ≥ 3. It is known that p(1,p) ≤ L<sub>p</sub>, for all primes p ≥ 5, as L<sub>p</sub> is congruent to 1 modulo p for all prime numbers p, where L<sub>p</sub> 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
: <math>\operatorname{p}(a,d) \leq (1+o(1))\varphi(d)^2 (\log d)^2 \; ,</math>
where <math>\varphi</math> is the totient function,
It is also conjectured that:
: <math>\operatorname{p}(a,d) < d^2. \; </math> and the following table shows the progress that has been made on determining its size.
{| cellpadding="3"
| L ≤ || Year of publication || Author
|-
| align="right" | 10000 || align="center" | 1957 || Pan
|-
| align="right" | 5448 || align="center" | 1958 || Pan
|-
| align="right" | 777 || align="center" | 1965 || Chen
|-
| align="right" | 630 || align="center" | 1971 || Jutila
|-
| align="right" | 550 || align="center" | 1970 || Jutila
|-
| align="right" | 168 || align="center" | 1977 || Chen
|-
| align="right" | 80 || align="center" | 1977 || Jutila
|-
| align="right" | 36 || align="center" | 1977 || Graham
|-
| align="right" | 20 || align="center" | 1981 || Graham (submitted before Chen's 1979 paper)
|-
| align="right" | 17 || align="center" | 1979 || Chen
|-
| align="right" | 16 || align="center" | 1986 || Wang
|-
| align="right" | 13.5 || align="center" | 1989 || Chen and Liu
|-
| align="right" | 8 || align="center" | 1990 || Wang
|-
| align="right" | 5.5 || align="center" | 1992 || Heath-Brown
|-
| align="right" | 5.18 || align="center" | 2009 || Xylouris
|-
| align="right" | 5 || align="center" | 2011 || Xylouris
|-
| align="right" | 5 − ε || align="center" | 2018 || Xylouris
|}
Moreover, in Heath-Brown's result the constant c is effectively computable.