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 + n d , {\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:
p ( a , d ) < c d L . {\displaystyle \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) ≤ 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.
Properties It is known that L ≤ 2 for almost all integers d. On the generalized Riemann hypothesis it can be shown that
p ( a , d ) ≤ ( 1 + o ( 1 ) ) φ ( d ) 2 ( log d ) 2 , {\displaystyle \operatorname {p} (a,d)\leq (1+o(1))\varphi (d)^{2}(\log d)^{2}\;,}
where φ {\displaystyle \varphi } is the totient function, and the stronger bound
p ( a , d ) ≤ φ ( d ) 2 ( log d ) 2 , {\displaystyle \operatorname {p} (a,d)\leq \varphi (d)^{2}(\log d)^{2}\;,}
has been also proved. It is also conjectured that:
p ( a , d ) < d 2 . {\displaystyle \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.
Moreover, in Heath-Brown's result the constant c is effectively computable.
Notes