Linnik's theorem in
analytic number theory answers a natural question after
Dirichlet's theorem on arithmetic progressions
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 al ...
. It asserts that there exist positive ''c'' and ''L'' such that, if we denote p(''a'',''d'') the least
prime in the arithmetic progression
:
where ''n'' runs through the positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s and ''a'' and ''d'' are any given positive
coprime integers
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equival ...
with 1 ≤ ''a'' ≤ ''d'' − 1, then:
:
The theorem is named after
Yuri Vladimirovich Linnik
Yuri Vladimirovich Linnik (russian: Ю́рий Влади́мирович Ли́нник; January 8, 1915 – June 30, 1972) was a Soviet mathematician active in number theory, probability theory and mathematical statistics.
Linnik was born in B ...
, who
proved it in 1944. Although Linnik's proof showed ''c'' and ''L'' to be
effectively computable
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can d ...
, he provided no numerical values for them.
It follows from
Zsigmondy's theorem
In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a>b>0 are coprime integers, then for any integer n \ge 1, there is a prime number ''p'' (called a ''primitive prime divisor'') that divides a^n-b^n and does not divi ...
that p(1,''d'') ≤ 2
''d'' − 1, for all ''d'' ≥ 3. It is known that p(1,''p'') ≤ L
''p'', for all
primes
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p'' ≥ 5, as L
''p'' is
congruent
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
to 1 modulo ''p'' for all prime numbers ''p'', where L
''p'' denotes the ''p''-th
Lucas number
The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci nu ...
. Just like
Mersenne numbers
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 1 ...
, Lucas numbers with prime indices have
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of the form 2''kp''+1.
Properties
It is known that ''L'' ≤ 2 for
almost all
In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the mathem ...
integers ''d''.
On the
generalized Riemann hypothesis
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-function, ''L''-func ...
it can be shown that
:
where
is the
totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
,
and the stronger bound
:
has been also proved.
It is also
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...
d that:
:
Bounds for ''L''
The constant ''L'' is called Linnik's constant
and the following table shows the progress that has been made on determining its size.
Moreover, in Heath-Brown's result the constant ''c'' is effectively computable.
Notes
{{reflist
Theorems in analytic number theory
Theorems about prime numbers