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
where n runs through the positive integers and a and d are any given positive coprime integers with 1 ≤ a ≤ d − 1, then:
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) ≤ 2d − 1, for all d ≥ 3. It is known that p(1,p) ≤ Lp, for all primes p ≥ 5, as Lp is congruent to 1 modulo p for all prime numbers p, where Lp denotes the p-th Lucas number. Just like Mersenne numbers, Lucas numbers with prime indices have divisors of the form 2kp+1.
It is known that L ≤ 2 for almost all integers d.[3]
On the generalized Riemann hypothesis it can be shown that
where is the totient function,[4] and the stronger bound
has been also proved.[5]
It is also conjectured that:
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] |
Moreover, in Heath-Brown's result the constant c is effectively computable.