Editing Linnik's theorem

{{Short description|Mathematical 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 [[primes in arithmetic progression|prime in the arithmetic progression]]

:<math>a + nd,\ </math>

where ''n'' runs through the positive [[integer]]s and ''a'' and ''d'' are any given positive [[coprime integers]] with 1 ≤ ''a'' ≤ ''d'' − 1, then:

: <math>\operatorname{p}(a,d) < c d^{L}. \; </math>

The theorem is named after [[Yuri Vladimirovich Linnik]], who [[mathematical proof|proved]] it in 1944.<ref>{{cite journal | last=Linnik | first=Yu. V. | title=On the least prime in an arithmetic progression I. The basic theorem | journal=Rec. Math. (Mat. Sbornik) |series=Nouvelle Série | volume=15 | issue=57 | year=1944 | pages=139–178 | mr=0012111}}</ref><ref>{{ cite journal | last=Linnik | first=Yu. V. | title=On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon | journal=Rec. Math. (Mat. Sbornik) |series=Nouvelle Série | volume=15 | issue=57 | year=1944 | pages=347–368 | mr=0012112}}</ref> Although Linnik's proof showed ''c'' and ''L'' to be [[effective results in number theory|effectively computable]], he provided no numerical values for them.

It follows from [[Zsigmondy's theorem]] that p(1,''d'') ≤ 2<sup>''d''</sup> − 1, for all ''d'' ≥ 3. It is known that p(1,''p'') ≤ L<sub>''p''</sub>, for all [[prime number|primes]] ''p'' ≥ 5, as L<sub>''p''</sub> is [[modular arithmetic|congruent]] to 1 modulo ''p'' for all prime numbers ''p'', where L<sub>''p''</sub> denotes the ''p''-th [[Lucas number]]. Just like [[Mersenne numbers]], Lucas numbers with prime indices have [[divisor]]s of the form 2''kp''+1.

== Properties ==

It is known that ''L'' ≤ 2 for [[almost all]] integers ''d''.<ref>{{cite journal | author1-link=Enrico Bombieri | last1=Bombieri | first1=Enrico | author2-link=John Friedlander | first2=John B. | last2=Friedlander | author3-link=Henryk Iwaniec | first3=Henryk | last3=Iwaniec | title=Primes in Arithmetic Progressions to Large Moduli. III | journal=[[Journal of the American Mathematical Society]] | volume=2 | issue=2 | year=1989 | pages=215–224 | mr=0976723 | doi=10.2307/1990976| jstor=1990976 | doi-access=free }}</ref>

On the [[generalized Riemann hypothesis]] it can be shown that

: <math>\operatorname{p}(a,d) \leq (1+o(1))\varphi(d)^2 (\log d)^2 \; ,</math>

where <math>\varphi</math> is the [[totient function]],<ref name="heath-brown"/>
and the stronger bound

: <math>\operatorname{p}(a,d) \leq \varphi(d)^2 (\log d)^2 \; ,</math>
has been also proved.<ref name="LamzouriLiSoundararajan">{{cite journal|last1=Lamzouri|first1=Y.|last2=Li|first2=X.|last3=Soundararajan|first3=K.|title=Conditional bounds for the least quadratic non-residue and related problems|journal=Math. Comp.|date=2015|volume=84|issue=295|pages=2391–2412|doi=10.1090/S0025-5718-2015-02925-1|arxiv=1309.3595|s2cid=15306240}}</ref>

It is also [[conjecture]]d that:

: <math>\operatorname{p}(a,d) < d^2. \; </math> <ref name="heath-brown"/>

== Bounds for ''L'' ==
The constant ''L'' is called '''Linnik's constant'''<ref>{{cite book |last=Guy | first=Richard K.  |title=Unsolved problems in number theory | volume=1  |publisher=Springer-Verlag |edition=Third |year=2004 |isbn=978-0-387-20860-2|page=22 | mr=2076335 | series=Problem Books in Mathematics | doi=10.1007/978-0-387-26677-0 | location=New York}}</ref> and the following table shows the progress that has been made on determining its size.

{| cellpadding="3"
| ''L'' ≤ || Year of publication || Author
|-
| align="right" | 10000 || align="center" | 1957 || [[Pan Chengdong|Pan]]<ref>{{cite journal | last=Pan | first=Cheng Dong | title=On the least prime in an arithmetical progression | journal=Sci. Record |series=New Series | volume=1 | year=1957 | pages=311–313 | mr=0105398}}</ref>
|-
| align="right" | 5448 || align="center" | 1958 || Pan
|-
| align="right" | 777 || align="center" | 1965 || [[Chen Jingrun|Chen]]<ref>{{cite journal | last=Chen | first=Jingrun | title=On the least prime in an arithmetical progression | journal=Sci. Sinica | volume=14 | year=1965 | pages=1868–1871}}</ref>
|-
| align="right" | 630 || align="center" | 1971 || [[Matti Jutila|Jutila]]
|-
| align="right" | 550 || align="center" | 1970  || Jutila<ref>{{cite journal | last=Jutila | first=Matti | title=A new estimate for Linnik's constant | journal=Ann. Acad. Sci. Fenn. Ser. A | volume=471 | year=1970 | mr=0271056}}</ref>
|-
| align="right" | 168 || align="center" | 1977 || Chen<ref>{{cite journal | last=Chen | first=Jingrun | title=On the least prime in an arithmetical progression and two theorems concerning the zeros of Dirichlet's $L$-functions | journal=Sci. Sinica | volume=20 | year=1977 | issue=5 | pages=529–562 | mr=0476668}}</ref>
|-
| align="right" | 80 || align="center" | 1977 || Jutila<ref>{{cite journal | last=Jutila | first=Matti | title=On Linnik's constant | journal=Math. Scand. | volume=41 | year=1977 | issue=1 | pages=45–62 | mr=0476671| doi=10.7146/math.scand.a-11701 | doi-access=free }}</ref>
|-
| align="right" | 36 || align="center" | 1977 || [[Sidney Graham|Graham]]<ref>{{cite thesis | title=Applications of sieve methods | last=Graham | first=Sidney West | type=Ph.D. | publisher=Univ. Michigan | location=Ann Arbor, Mich | year=1977 | mr=2627480 }}</ref>
|-
| align="right" | 20 || align="center" | 1981 || Graham<ref>{{cite journal | last=Graham | first=S. W. | title=On Linnik's constant | journal=[[Acta Arith.]] | volume=39 | year=1981 | issue=2 | pages=163–179 | mr=0639625| doi=10.4064/aa-39-2-163-179 | doi-access=free }}</ref> (submitted before Chen's 1979 paper)
|-
| align="right" | 17 || align="center" | 1979 || Chen<ref>{{cite journal | last=Chen | first=Jingrun | title=On the least prime in an arithmetical progression and theorems concerning the zeros of Dirichlet's $L$-functions. II | journal=Sci. Sinica | volume=22 | year=1979 | issue=8 | pages=859–889 | mr=0549597}}</ref>
|-
| align="right" | 16 || align="center" | 1986 || Wang
|-
| align="right" | 13.5 || align="center" | 1989 || Chen and [[Liu Jian Min|Liu]]<ref>{{cite journal | last1=Chen | first1=Jingrun | last2=Liu | first2=Jian Min | title=On the least prime in an arithmetical progression. III | journal=Science in China Series A: Mathematics | volume=32 | year=1989 | issue=6 | pages=654–673 | mr=1056044}}</ref><ref>{{cite journal | last1=Chen |first1=Jingrun | last2=Liu | first2=Jian Min | title=On the least prime in an arithmetical progression. IV | journal=Science in China Series A: Mathematics | volume=32 | year=1989 | issue=7 | pages=792–807 | mr=1058000}}</ref>
|-
| align="right" | 8 || align="center" | 1990 || Wang<ref>{{cite journal | last=Wang | first=Wei | title=On the least prime in an arithmetical progression | journal=Acta Mathematica Sinica |series=New Series | year=1991 | volume=7 | issue=3 | pages=279–288 | mr=1141242| doi=10.1007/BF02583005 | s2cid=121701036 }}</ref>
|-
| align="right" |  5.5 || align="center" | 1992 || [[Roger Heath-Brown|Heath-Brown]]<ref name="heath-brown">{{cite journal | last=Heath-Brown | first=Roger | title=Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression | journal=[[Proc. London Math. Soc.]] | volume=64 | issue=3 | year=1992 | pages=265–338 | mr=1143227 | doi=10.1112/plms/s3-64.2.265| url=https://ora.ox.ac.uk/objects/uuid:b63b8b4f-ad21-4de4-a86b-c82fdfc87997 }}</ref>
|-
| align="right" | 5.18 || align="center" | 2009 || Xylouris<ref>{{cite journal | first=Triantafyllos | last=Xylouris | title=On Linnik's constant | year=2011 | journal=[[Acta Arith.]] | volume=150 | issue=1 | pages=65–91 | mr=2825574 | doi=10.4064/aa150-1-4| doi-access=free }}</ref>
|-
| align="right" | 5 || align="center" | 2011 || Xylouris<ref>{{cite thesis | first=Triantafyllos | last=Xylouris | title=Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression | trans-title=The zeros of Dirichlet L-functions and the least prime in an arithmetic progression | year=2011 | mr=3086819 | language=de | location=Bonn | publisher=Universität Bonn, Mathematisches Institut | type=Dissertation for the degree of Doctor of Mathematics and Natural Sciences}}</ref>
|-
| align="right" | 5 &minus; ε || align="center" | 2018 || Xylouris<ref>[https://www.chebsbornik.ru/jour/article/view/507 Linniks Konstante ist kleiner als 5]</ref>
|}

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

==Notes==
{{reflist}}

[[Category:Theorems in analytic number theory]]
[[Category:Theorems about prime numbers]]