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
- [math]\displaystyle{ a + nd,\ }[/math]
where n runs through the positive integers and a and d are any given positive coprime integers with 1 ≤ a ≤ d − 1, then:
- [math]\displaystyle{ \operatorname{p}(a,d) \lt c d^{L}. \; }[/math]
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) ≤ 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.[3]
On the generalized Riemann hypothesis it can be shown that
- [math]\displaystyle{ \operatorname{p}(a,d) \leq (1+o(1))\varphi(d)^2 (\log d)^2 \; , }[/math]
where [math]\displaystyle{ \varphi }[/math] is the totient function,[4] and the stronger bound
- [math]\displaystyle{ \operatorname{p}(a,d) \leq \varphi(d)^2 (\log d)^2 \; , }[/math]
has been also proved.[5]
It is also conjectured that:
- [math]\displaystyle{ \operatorname{p}(a,d) \lt d^2. \; }[/math] [4]
Bounds for L
The constant L is called Linnik's constant[6] and the following table shows the progress that has been made on determining its size.
| L ≤ | Year of publication | Author |
| 10000 | 1957 | Pan[7] |
| 5448 | 1958 | Pan |
| 777 | 1965 | Chen[8] |
| 630 | 1971 | Jutila |
| 550 | 1970 | Jutila[9] |
| 168 | 1977 | Chen[10] |
| 80 | 1977 | Jutila[11] |
| 36 | 1977 | Graham[12] |
| 20 | 1981 | Graham[13] (submitted before Chen's 1979 paper) |
| 17 | 1979 | Chen[14] |
| 16 | 1986 | Wang |
| 13.5 | 1989 | Chen and Liu[15][16] |
| 8 | 1990 | Wang[17] |
| 5.5 | 1992 | Heath-Brown[4] |
| 5.18 | 2009 | Xylouris[18] |
| 5 | 2011 | Xylouris[19] |
Moreover, in Heath-Brown's result the constant c is effectively computable.
Notes
- ↑ Linnik, Yu. V. (1944). "On the least prime in an arithmetic progression I. The basic theorem". Rec. Math. (Mat. Sbornik). Nouvelle Série 15 (57): 139–178.
- ↑ Linnik, Yu. V. (1944). "On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon". Rec. Math. (Mat. Sbornik). Nouvelle Série 15 (57): 347–368.
- ↑ 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.
- ↑ 4.0 4.1 4.2 Heath-Brown, Roger (1992). "Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression". Proc. London Math. Soc. 64 (3): 265–338. doi:10.1112/plms/s3-64.2.265. https://ora.ox.ac.uk/objects/uuid:b63b8b4f-ad21-4de4-a86b-c82fdfc87997.
- ↑ Lamzouri, Y.; Li, X.; Soundararajan, K. (2015). "Conditional bounds for the least quadratic non-residue and related problems". Math. Comp. 84 (295): 2391–2412. doi:10.1090/S0025-5718-2015-02925-1.
- ↑ Guy, Richard K. (2004). Unsolved problems in number theory. Problem Books in Mathematics. 1 (Third ed.). New York: Springer-Verlag. p. 22. doi:10.1007/978-0-387-26677-0. ISBN 978-0-387-20860-2.
- ↑ Pan, Cheng Dong (1957). "On the least prime in an arithmetical progression". Sci. Record. New Series 1: 311–313.
- ↑ Chen, Jingrun (1965). "On the least prime in an arithmetical progression". Sci. Sinica 14: 1868–1871.
- ↑ Jutila, Matti (1970). "A new estimate for Linnik's constant". Ann. Acad. Sci. Fenn. Ser. A 471.
- ↑ 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.
- ↑ Jutila, Matti (1977). "On Linnik's constant". Math. Scand. 41 (1): 45–62. doi:10.7146/math.scand.a-11701.
- ↑ Graham, Sidney West (1977). Applications of sieve methods (Ph.D.). Ann Arbor, Mich: Univ. Michigan. MR 2627480.
- ↑ Graham, S. W. (1981). "On Linnik's constant". Acta Arith. 39 (2): 163–179. doi:10.4064/aa-39-2-163-179.
- ↑ 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.
- ↑ Chen, Jingrun; Liu, Jian Min (1989). "On the least prime in an arithmetical progression. III". Science in China Series A: Mathematics 32 (6): 654–673.
- ↑ Chen, Jingrun; Liu, Jian Min (1989). "On the least prime in an arithmetical progression. IV". Science in China Series A: Mathematics 32 (7): 792–807.
- ↑ Wang, Wei (1991). "On the least prime in an arithmetical progression". Acta Mathematica Sinica. New Series 7 (3): 279–288. doi:10.1007/BF02583005.
- ↑ Xylouris, Triantafyllos (2011). "On Linnik's constant". Acta Arith. 150 (1): 65–91. doi:10.4064/aa150-1-4.
- ↑ 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 Deutsch). Bonn: Universität Bonn, Mathematisches Institut. MR 3086819.
 |  |
