Login
Login

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 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.{{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}}{{ 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}} 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.{{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 }}

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.{{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}}

It is also conjectured that:

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

Bounds for ''L''

The constant L is called Linnik's constant{{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}} and the following table shows the progress that has been made on determining its size.

cellpadding="3"

| L ≤

Year of publicationAuthor
align="right" | 10000align="center" | 1957Pan{{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}}
align="right" | 5448align="center" | 1958Pan
align="right" | 777align="center" | 1965Chen{{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}}
align="right" | 630align="center" | 1971Jutila
align="right" | 550align="center" | 1970Jutila{{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}}
align="right" | 168align="center" | 1977Chen{{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}}
align="right" | 80align="center" | 1977Jutila{{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 }}
align="right" | 36align="center" | 1977Graham{{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 }}
align="right" | 20align="center" | 1981Graham{{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 }} (submitted before Chen's 1979 paper)
align="right" | 17align="center" | 1979Chen{{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}}
align="right" | 16align="center" | 1986Wang
align="right" | 13.5align="center" | 1989Chen and Liu{{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}}{{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}}
align="right" | 8align="center" | 1990Wang{{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 }}
align="right" | 5.5align="center" | 1992Heath-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 }}
align="right" | 5.18align="center" | 2009Xylouris{{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 }}
align="right" | 5align="center" | 2011Xylouris{{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}}
align="right" | 5 − εalign="center" | 2018Xylouris[https://www.chebsbornik.ru/jour/article/view/507 Linniks Konstante ist kleiner als 5]

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