Linnik's theorem explained

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:

\operatorname{p}(a,d) < c d ^{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.

It follows from Zsigmondy's theorem that p(1,d) ≤ 2^d − 1, for all d ≥ 3. It is known that p(1,p) ≤ L_p, for all primes p ≥ 5, as L_p is congruent to 1 modulo p for all prime numbers p, where L_p 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.^[3]

On the generalized Riemann hypothesis it can be shown that

\operatorname{p}(a,d) \leq ( 1+ o( 1 ))\varphi(d) ^{2} ( log d) ^{2} ,

where

\varphi is the totient function,and the stronger bound\operatorname{p}(a,d) \leq \varphi(d) ^{2} ( log d) ^{2} , has been also proved.^[4]

It is also conjectured that:

\operatorname{p}(a,d) < d ^{2.}

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^[17]
5.18	2009	Xylouris^[18]
5	2011	Xylouris^[19]

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

Notes and References

1. Linnik . Yu. V. . On the least prime in an arithmetic progression I. The basic theorem . Rec. Math. (Mat. Sbornik) . Nouvelle Série . 15 . 57 . 1944 . 139–178 . 0012111.
2. Linnik . Yu. V. . On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon . Rec. Math. (Mat. Sbornik) . Nouvelle Série . 15 . 57 . 1944 . 347–368 . 0012112.
3. Enrico Bombieri . Bombieri . Enrico . John Friedlander . John B. . Friedlander . Henryk Iwaniec . Henryk . Iwaniec . Primes in Arithmetic Progressions to Large Moduli. III . . 2 . 2 . 1989 . 215–224 . 0976723 . 10.2307/1990976. 1990976 . free .
4. Lamzouri. Y.. Li. X.. Soundararajan. K.. Conditional bounds for the least quadratic non-residue and related problems. Math. Comp.. 2015. 84. 295. 2391–2412. 10.1090/S0025-5718-2015-02925-1. 1309.3595. 15306240.
5. Book: Guy, Richard K. . Unsolved problems in number theory . 1 . Springer-Verlag . Third . 2004 . 978-0-387-20860-2. 22 . 2076335 . Problem Books in Mathematics . 10.1007/978-0-387-26677-0 . New York.
6. Pan . Cheng Dong . On the least prime in an arithmetical progression . Sci. Record . New Series . 1 . 1957 . 311–313 . 0105398.
7. Chen . Jingrun . On the least prime in an arithmetical progression . Sci. Sinica . 14 . 1965 . 1868–1871.
8. Jutila . Matti . A new estimate for Linnik's constant . Ann. Acad. Sci. Fenn. Ser. A . 471 . 1970 . 0271056.
9. Chen . Jingrun . On the least prime in an arithmetical progression and two theorems concerning the zeros of Dirichlet's $L$-functions . Sci. Sinica . 20 . 1977 . 5 . 529–562 . 0476668.
10. Jutila . Matti . On Linnik's constant . Math. Scand. . 41 . 1977 . 1 . 45–62 . 0476671. 10.7146/math.scand.a-11701 . free .
11. Applications of sieve methods . Graham . Sidney West . Ph.D. . Univ. Michigan . Ann Arbor, Mich . 1977 . 2627480 .
12. Graham . S. W. . On Linnik's constant . . 39 . 1981 . 2 . 163–179 . 0639625. 10.4064/aa-39-2-163-179 . free .
13. Chen . Jingrun . On the least prime in an arithmetical progression and theorems concerning the zeros of Dirichlet's $L$-functions. II . Sci. Sinica . 22 . 1979 . 8 . 859–889 . 0549597.
14. Chen . Jingrun . Liu . Jian Min . On the least prime in an arithmetical progression. III . Science in China Series A: Mathematics . 32 . 1989 . 6 . 654–673 . 1056044.
15. Chen . Jingrun . Liu . Jian Min . On the least prime in an arithmetical progression. IV . Science in China Series A: Mathematics . 32 . 1989 . 7 . 792–807 . 1058000.
16. Wang . Wei . On the least prime in an arithmetical progression . Acta Mathematica Sinica . New Series . 1991 . 7 . 3 . 279–288 . 1141242. 10.1007/BF02583005 . 121701036 .
17. Heath-Brown . Roger . Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression . . 64 . 3 . 1992 . 265–338 . 1143227 . 10.1112/plms/s3-64.2.265.
18. Triantafyllos . Xylouris . On Linnik's constant . 2011 . . 150 . 1 . 65–91 . 2825574 . 10.4064/aa150-1-4. free .
19. Triantafyllos . Xylouris . Ü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 . 2011 . 3086819 . de . Bonn . Universität Bonn, Mathematisches Institut . Dissertation for the degree of Doctor of Mathematics and Natural Sciences.