Linnik's theorem

Last updated

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

Contents

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

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

where is the totient function, [4] and the stronger bound

has been also proved. [5]

It is also conjectured that:

[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 publicationAuthor
100001957 Pan [7]
54481958Pan
7771965 Chen [8]
6301971 Jutila
5501970Jutila [9]
1681977Chen [10]
801977Jutila [11]
361977 Graham [12]
201981Graham [13] (submitted before Chen's 1979 paper)
171979Chen [14]
161986Wang
13.51989Chen and Liu [15] [16]
81990Wang [17]
5.51992 Heath-Brown [4]
5.182009Xylouris [18]
52011Xylouris [19]

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). Nouvelle Série. 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). Nouvelle Série. 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 . JSTOR   1990976. MR   0976723.
  4. 1 2 3 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. MR   1143227.
  5. ↑ Lamzouri, Y.; Li, X.; Soundararajan, K. (2015). "Conditional bounds for the least quadratic non-residue and related problems". Math. Comp. 84 (295): 2391–2412. arXiv: 1309.3595 . doi:10.1090/S0025-5718-2015-02925-1. S2CID   15306240.
  6. ↑ Guy, Richard K. (2004). Unsolved problems in number theory. Problem Books in Mathematics. Vol. 1 (Third ed.). New York: Springer-Verlag. p. 22. doi:10.1007/978-0-387-26677-0. ISBN   978-0-387-20860-2. MR   2076335.
  7. ↑ Pan, Cheng Dong (1957). "On the least prime in an arithmetical progression". Sci. Record. New Series. 1: 311–313. MR   0105398.
  8. ↑ Chen, Jingrun (1965). "On the least prime in an arithmetical progression". Sci. Sinica. 14: 1868–1871.
  9. ↑ Jutila, Matti (1970). "A new estimate for Linnik's constant". Ann. Acad. Sci. Fenn. Ser. A. 471. MR   0271056.
  10. ↑ 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.
  11. ↑ Jutila, Matti (1977). "On Linnik's constant". Math. Scand. 41 (1): 45–62. doi: 10.7146/math.scand.a-11701 . MR   0476671.
  12. ↑ Graham, Sidney West (1977). Applications of sieve methods (Ph.D.). Ann Arbor, Mich: Univ. Michigan. MR   2627480.
  13. ↑ Graham, S. W. (1981). "On Linnik's constant". Acta Arith. 39 (2): 163–179. doi: 10.4064/aa-39-2-163-179 . MR   0639625.
  14. ↑ 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.
  15. ↑ 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. MR   1056044.
  16. ↑ 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. MR   1058000.
  17. ↑ Wang, Wei (1991). "On the least prime in an arithmetical progression". Acta Mathematica Sinica. New Series. 7 (3): 279–288. doi:10.1007/BF02583005. MR   1141242. S2CID   121701036.
  18. ↑ Xylouris, Triantafyllos (2011). "On Linnik's constant". Acta Arith. 150 (1): 65–91. doi: 10.4064/aa150-1-4 . MR   2825574.
  19. ↑ 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.

Related Research Articles

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1) = 1 and

In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann.

In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model, i.e., there exists an interpretation under which all formulas in the theory are true. This is the sense used in traditional Aristotelian logic, although in contemporary mathematical logic the term satisfiable is used instead. The syntactic definition states a theory is consistent if there is no formula such that both and its negation are elements of the set of consequences of . Let be a set of closed sentences and the set of closed sentences provable from under some formal deductive system. The set of axioms is consistent when for no formula .

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is also a positive integer. In other words, there are infinitely many primes that are congruent to a modulo d. The numbers of the form a + nd form an arithmetic progression

The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global L-functions, which are formally similar to the Riemann zeta-function. One can then ask the same question about the zeros of these L-functions, yielding various generalizations of the Riemann hypothesis. Many mathematicians believe these generalizations of the Riemann hypothesis to be true. The only cases of these conjectures which have been proven occur in the algebraic function field case.

<span class="mw-page-title-main">Analytic number theory</span> Exploring properties of the integers with complex analysis

In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.

<span class="mw-page-title-main">Chen Jingrun</span> Chinese number theorist

Chen Jingrun, also known as Jing-Run Chen, was a Chinese mathematician who made significant contributions to number theory, including Chen's theorem and the Chen prime.

In mathematics, the Bell series is a formal power series used to study properties of arithmetical functions. Bell series were introduced and developed by Eric Temple Bell.

<span class="mw-page-title-main">Chen's theorem</span>

In number theory, Chen's theorem states that every sufficiently large even number can be written as the sum of either two primes, or a prime and a semiprime.

In number theory, the Elliott–Halberstam conjecture is a conjecture about the distribution of prime numbers in arithmetic progressions. It has many applications in sieve theory. It is named for Peter D. T. A. Elliott and Heini Halberstam, who stated the conjecture in 1968.

In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if is small, then can be contained in a small generalized arithmetic progression.

In mathematics, the Bombieri–Vinogradov theorem is a major result of analytic number theory, obtained in the mid-1960s, concerning the distribution of primes in arithmetic progressions, averaged over a range of moduli. The first result of this kind was obtained by Mark Barban in 1961 and the Bombieri–Vinogradov theorem is a refinement of Barban's result. The Bombieri–Vinogradov theorem is named after Enrico Bombieri and A. I. Vinogradov, who published on a related topic, the density hypothesis, in 1965.

In analytic number theory, the Siegel–Walfisz theorem was obtained by Arnold Walfisz as an application of a theorem by Carl Ludwig Siegel to primes in arithmetic progressions. It is a refinement both of the prime number theorem and of Dirichlet's theorem on primes in arithmetic progressions.

<span class="mw-page-title-main">Landau's problems</span> Four basic unsolved problems about prime numbers

At the 1912 International Congress of Mathematicians, Edmund Landau listed four basic problems about prime numbers. These problems were characterised in his speech as "unattackable at the present state of mathematics" and are now known as Landau's problems. They are as follows:

  1. Goldbach's conjecture: Can every even integer greater than 2 be written as the sum of two primes?
  2. Twin prime conjecture: Are there infinitely many primes p such that p + 2 is prime?
  3. Legendre's conjecture: Does there always exist at least one prime between consecutive perfect squares?
  4. Are there infinitely many primes p such that p − 1 is a perfect square? In other words: Are there infinitely many primes of the form n2 + 1?

In number theory, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, states that the sequence of prime numbers contains arbitrarily long arithmetic progressions. In other words, for every natural number k, there exist arithmetic progressions of primes with k terms. The proof is an extension of Szemerédi's theorem. The problem can be traced back to investigations of Lagrange and Waring from around 1770.

<span class="mw-page-title-main">Kepler triangle</span> Right triangle related to the golden ratio

A Kepler triangle is a special right triangle with edge lengths in geometric progression. The ratio of the progression is where is the golden ratio, and the progression can be written: , or approximately . Squares on the edges of this triangle have areas in another geometric progression, . Alternative definitions of the same triangle characterize it in terms of the three Pythagorean means of two numbers, or via the inradius of isosceles triangles.

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

In analytic number theory, the Brun–Titchmarsh theorem, named after Viggo Brun and Edward Charles Titchmarsh, is an upper bound on the distribution of prime numbers in arithmetic progression.

<span class="mw-page-title-main">Riemann hypothesis</span> Conjecture on zeros of the zeta function

In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. Many consider it to be the most important unsolved problem in pure mathematics. It is of great interest in number theory because it implies results about the distribution of prime numbers. It was proposed by Bernhard Riemann (1859), after whom it is named.

In general topology and number theory, branches of mathematics, one can define various topologies on the set of integers or the set of positive integers by taking as a base a suitable collection of arithmetic progressions, sequences of the form or The open sets will then be unions of arithmetic progressions in the collection. Three examples are the Furstenberg topology on , and the Golomb topology and the Kirch topology on . Precise definitions are given below.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.