Parity problem (sieve theory)
Encyclopedia
In number theory
, the parity problem refers to a limitation in sieve theory
that prevents sieves from giving good estimates in many kinds of prime
-counting problems. The problem was identified and named by Atle Selberg
in 1949. Beginning around 1996, John Friedlander
and Henryk Iwaniec
developed some parity-sensitive sieves that make the parity problem less of an obstacle.
gave this "rough" statement of the problem:
This problem is significant because it may explain why it is difficult for sieves to "detect primes," in other words to give a non-trivial lower bound for the number of primes with some property. For example, in a sense Chen's theorem
is very close to a solution of the twin prime conjecture, since it says that there are infinitely many primes such that prime + 2 is either prime or the product of two primes. The parity problem suggests that, because the case of interest has an odd number of prime factors (namely 1), it won't be possible to separate out the two cases using sieves.
and is given as an exercise with hints by Cojocaru & Murty.
The problem is to estimate separately the number of numbers ≤ x with no prime divisors ≤ x1/2, that have an even (or an odd) number of prime factors. It can be shown that, no matter what the choice of weights in a Brun
- or Selberg
-type sieve, the upper bound obtained will be at least (2 + o(1)) x / ln x for both problems. But in fact the set with an even number of factors is empty and so has size 0. The set with an odd number of factors is just the prime
s between x1/2 and x, so by the prime number theorem
its size is (1 + o(1)) x / ln x. Thus these sieve methods are unable to give a useful upper bound for the first set, and overestimate the upper bound on the second set by a factor of 2.
and Henryk Iwaniec
developed some new sieve techniques to "break" the parity problem.
One of the triumphs of these new methods is the Friedlander–Iwaniec theorem, which states that there are infinitely many primes of the form a2 + b4.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the parity problem refers to a limitation in sieve theory
Sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
that prevents sieves from giving good estimates in many kinds of prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
-counting problems. The problem was identified and named by Atle Selberg
Atle Selberg
Atle Selberg was a Norwegian mathematician known for his work in analytic number theory, and in the theory of automorphic forms, in particular bringing them into relation with spectral theory...
in 1949. Beginning around 1996, John Friedlander
John Friedlander
John Benjamin Friedlander is a Canadian mathematician specializing in analytic number theory. He received his B.Sc. from the University of Toronto in 1965, an M.A. from the University of Waterloo in 1966, and a Ph.D. from Pennsylvania State University in 1972. He was a lecturer at M.I.T...
and Henryk Iwaniec
Henryk Iwaniec
Henryk Iwaniec is a Polish American mathematician, and since 1987 a professor at Rutgers University. He was awarded the fourteenth Frank Nelson Cole Prize in Number Theory in 2002. He received the Leroy P. Steele Prize for Mathematical Exposition in 2011.-Background and education:Iwaniec studied...
developed some parity-sensitive sieves that make the parity problem less of an obstacle.
The problem
Terence TaoTerence Tao
Terence Chi-Shen Tao FRS is an Australian mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory...
gave this "rough" statement of the problem:
This problem is significant because it may explain why it is difficult for sieves to "detect primes," in other words to give a non-trivial lower bound for the number of primes with some property. For example, in a sense Chen's theorem
Chen's theorem
right|thumb|Chen JingrunChen'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 . The theorem was first stated by Chinese mathematician Chen Jingrun in 1966, with further details of the proof in 1973. His original...
is very close to a solution of the twin prime conjecture, since it says that there are infinitely many primes such that prime + 2 is either prime or the product of two primes. The parity problem suggests that, because the case of interest has an odd number of prime factors (namely 1), it won't be possible to separate out the two cases using sieves.
Example of the parity problem
This example is due to SelbergAtle Selberg
Atle Selberg was a Norwegian mathematician known for his work in analytic number theory, and in the theory of automorphic forms, in particular bringing them into relation with spectral theory...
and is given as an exercise with hints by Cojocaru & Murty.
The problem is to estimate separately the number of numbers ≤ x with no prime divisors ≤ x1/2, that have an even (or an odd) number of prime factors. It can be shown that, no matter what the choice of weights in a Brun
Brun sieve
In the field of number theory, the Brun sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
- or Selberg
Selberg sieve
In mathematics, in the field of number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences...
-type sieve, the upper bound obtained will be at least (2 + o(1)) x / ln x for both problems. But in fact the set with an even number of factors is empty and so has size 0. The set with an odd number of factors is just the prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s between x1/2 and x, so by the prime number theorem
Prime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
its size is (1 + o(1)) x / ln x. Thus these sieve methods are unable to give a useful upper bound for the first set, and overestimate the upper bound on the second set by a factor of 2.
Parity-sensitive sieves
Beginning around 1996 John FriedlanderJohn Friedlander
John Benjamin Friedlander is a Canadian mathematician specializing in analytic number theory. He received his B.Sc. from the University of Toronto in 1965, an M.A. from the University of Waterloo in 1966, and a Ph.D. from Pennsylvania State University in 1972. He was a lecturer at M.I.T...
and Henryk Iwaniec
Henryk Iwaniec
Henryk Iwaniec is a Polish American mathematician, and since 1987 a professor at Rutgers University. He was awarded the fourteenth Frank Nelson Cole Prize in Number Theory in 2002. He received the Leroy P. Steele Prize for Mathematical Exposition in 2011.-Background and education:Iwaniec studied...
developed some new sieve techniques to "break" the parity problem.
One of the triumphs of these new methods is the Friedlander–Iwaniec theorem, which states that there are infinitely many primes of the form a2 + b4.