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

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

has been also proved.[5]

It is also conjectured that:

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

The constant L is called Linnik's constant^[6] 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.