Parity problem (sieve theory)
- Parity problem (sieve theory)
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.
The problem
Terence Tao 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.
Example of the parity problem
This example is due to Selberg and is given as an exercise with hints by Cojocaru & Murty. [] Rp|133–134
The problem is to estimate separately the number of numbers ≤ "x" with no prime divisors ≤ "x"1/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 primes between "x"1/2 and x, so by the prime number theorem its size is 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 Friedlander and Henryk Iwaniec developed some new sieve techniques to "break" the parity problem. [] [] One of the triumphs of these new methods is the Bombieri–Friedlander–Iwaniec theorem, that states that there are infinitely many primes of the form "a"2 + "b"4.
Notes
Wikimedia Foundation.
2010.
Look at other dictionaries:
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 .… … Wikipedia
List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia
List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic … Wikipedia
Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… … Wikipedia
Henryk Iwaniec — Infobox Scientist box width = name = Henryk Iwaniec imagesize = 150px caption = birth date = birth date and age|1947|10|9|mf=yes birth place = Elblag, Poland death date = death place = residence = United States citizenship = United States… … Wikipedia
Henryk Iwaniec — (* 9. Oktober 1947 in Elbląg in Polen) ist ein polnisch US amerikanischer Mathematiker, der sich mit analytischer Zahlentheorie beschäftigt. Henryk Iwaniec Inhaltsverzeichnis … Deutsch Wikipedia
Iwaniec — Henryk Iwaniec (* 9. Oktober 1947 in Elbląg in Polen) ist ein polnisch US amerikanischer Mathematiker, der sich mit analytischer Zahlentheorie beschäftigt. Inhaltsverzeichnis 1 Leben 2 Schriften 3 Weblinks 4 Einzelnachweise … Deutsch Wikipedia
Conjetura de Elliott–Halberstam — El texto que sigue es una traducción defectuosa o incompleta. Si quieres colaborar con Wikipedia, busca el artículo original y mejora o finaliza esta traducción. Puedes dar aviso al autor principal del artículo pegando el siguiente código en su… … Wikipedia Español
Teoría de cribas — La teoría de cribas es un conjunto de técnicas generales en teoría de números, diseñadas para contar o estimar el tamaño de un conjunto de números enteros. El ejemplo primordial de un conjunto tamizado es conjunto de números primos menores… … Wikipedia Español
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
