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

$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)<cd^{L}.\;$

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.

Properties

It is known that L ≤ 2 for almost all integers d.^[3]

On the generalized Riemann hypothesis it can be shown that

$p(a,d)\leq (1+o(1))\varphi (d)^{2}\ln ^{2}d\;,$

where $\varphi$ is the totient function.^[4]

It is also conjectured that:

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

Bounds for L

The constant L is called Linnik's constant ^[5] and the following table shows the progress that has been made on determining its size.

L ≤	Year of publication	Author
10000	1957	Pan[6]
5448	1958	Pan
777	1965	Chen[7]
630	1971	Jutila
550	1970	Jutila[8]
168	1977	Chen[9]
80	1977	Jutila[10]
36	1977	Graham[11]
20	1981	Graham[12] (submitted before Chen's 1979 paper)
17	1979	Chen[13]
16	1986	Wang
13.5	1989	Chen and Liu[14][15]
8	1990	Wang[16]
5.5	1992	Heath-Brown[4]
5.18	2009	Xylouris[17]
5	2011	Xylouris[18]

Moreover, in Heath-Brown's result the constant c is effectively computable.

Notes

1. Linnik, Yu. V. (1944). "On the least prime in an arithmetic progression I. The basic theorem". Rec. Math. (Mat. Sbornik) N.S. 15(57): 139–178. MR 0012111.
2. Linnik, Yu. V. (1944). "On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon". Rec. Math. (Mat. Sbornik) N.S. 15(57): 347–368. MR 0012112.
3. Bombieri, Enrico; Friedlander, John B.; Iwaniec, Henryk (1989). "Primes in Arithmetic Progressions to Large Moduli. III". Journal of the American Mathematical Society 2 (2): 215–224. doi:10.2307/1990976. MR 0976723.
4. Heath-Brown, Roger (1992). "Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression". Proc. Lond. Math. Soc. 64 (3): 265–338. doi:10.1112/plms/s3-64.2.265. MR 1143227.
5. Guy, Richard K. (2004). Unsolved problems in number theory. Problem Books in Mathematics (Third ed.). New York: Springer-Verlag. p. 22. doi:10.1007/978-0-387-26677-0. ISBN 0-387-20860-7. MR 2076335.
6. Pan, Cheng Dong (1957). "On the least prime in an arithmetical progression". Sci. Record (N.S.) 1: 311–313. MR 0105398.
7. Chen, Jingrun (1965). "On the least prime in an arithmetical progression". Sci. Sinica 14: 1868–1871.
8. Jutila, Matti (1970). "A new estimate for Linnik's constant". Ann. Acad. Sci. Fenn. Ser. A I No. 471. MR 0271056.
9. Chen, Jingrun (1977). "On the least prime in an arithmetical progression and two theorems concerning the zeros of Dirichlet's $L$-functions". Sci. Sinica 20 (5): 529–562. MR 0476668.
10. Jutila, Matti (1977). "On Linnik's constant". Math. Scand. 41 (1): 45–62. MR 0476671.
11. Graham, Sidney West (1977). Applications of sieve methods (Ph.D.). Ann Arbor, Mich: Univ. Michigan. MR 2627480.
12. Graham, S. W. (1981). "On Linnik's constant". Acta Arith. 39 (2): 163–179. MR 0639625.
13. Chen, Jingrun (1979). "On the least prime in an arithmetical progression and theorems concerning the zeros of Dirichlet's $L$-functions. II". Sci. Sinica 22 (8): 859–889. MR 0549597.
14. Chen, Jingrun; Liu, Jian Min (1989). "On the least prime in an arithmetical progression. III". Sci. China Ser. A 32 (6): 654–673. MR 1056044.
15. Chen, Jingrun; Liu, Jian Min (1989). "On the least prime in an arithmetical progression. IV". Sci. China Ser. A 32 (7): 792–807. MR 1058000.
16. Wang, Wei (1991). "On the least prime in an arithmetical progression". Acta Mathematica Sinica, New Series 7 (3): 279–288. MR 1141242.
17. Xylouris, Triantafyllos (2011). "On Linnik's constant". Acta Arith. 150 (1): 65–91. doi:10.4064/aa150-1-4. MR 2825574.
18. Xylouris, Triantafyllos (2011). Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression [The zeros of Dirichlet L-functions and the least prime in an arithmetic progression] (Dissertation for the degree of Doctor of Mathematics and Natural Sciences) (in German). Bonn: Universität Bonn, Mathematisches Institut. MR 3086819.