Linnik's theorem

Linnik's theorem in analytic number theory answers a natural question after Dirichlet's theorem on arithmetic progressions. It asserts 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", then there exist positive "c" and "L" such that:

:

The theorem is named after Yuri Vladimirovich Linnik, who proved it in 1944. [Linnik, Yu. V. "On the least prime in an arithmetic progression I. The basic theorem" Rec. Math. (Mat. Sbornik) N.S. 15 (57) (1944), pages 139-178] [Linnik, Yu. V. "On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon" Rec. Math. (Mat. Sbornik) N.S. 15 (57) (1944), pages 347-368] Although Linnik's proof showed "c" and "L" to be effectively computable, he provided no numerical values for them.

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.

It is known that "L" ≤ 2 for almost all integers "d". [E. Bombieri, J. B. Friedlander, H. Iwaniec. "Primes in Arithmetic Progressions to Large Moduli. III", "Journal of the American Mathematical Society" 2(2) (1989), pp. 215–224.]

On the Generalized Riemann Hypothesis it can be shown that

: $p(a,d)\; leq\; varphi(d)^2\; ln^2\; d\; ;\; ,$

where $varphi$ is the totient function.

It is also conjectured that:

:

References