Parity problem (sieve theory)

Last updated January 05, 2022

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.

Statement

Terence Tao gave this "rough" statement of the problem:^[1]

Parity problem. If A is a set whose elements are all products of an odd number of primes (or are all products of an even number of primes), then (without injecting additional ingredients), sieve theory is unable to provide non-trivial lower bounds on the size of A. Also, any upper bounds must be off from the truth by a factor of 2 or more.

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 p such that p + 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

This example is due to Selberg and is given as an exercise with hints by Cojocaru & Murty.^[2]^{: 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 (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.^[3]^[4] One of the triumphs of these new methods is the Friedlander–Iwaniec theorem, which states that there are infinitely many primes of the form a² + b⁴.

Glyn Harman relates the parity problem to the distinction between Type I and Type II information in a sieve.^[5]

Karatsuba phenomenon

In 2007 Anatolii Alexeevitch Karatsuba discovered an imbalance between the numbers in an arithmetic progression with given parities of the number of prime factors. His papers^[6]^[7] were published after his death.

Let $\mathbb {N}$ be a set of natural numbers (positive integers) that is, the numbers $1,2,3,\dots$ . The set of primes, that is, such integers $n\in \mathbb {N}$ , $n>1$ , that have just two distinct divisors (namely, $n$ and $1$ ), is denoted by $\mathbb {P}$ , $\mathbb {P} =\{2,3,5,7,11,\dots \}\subset \mathbb {N}$ . Every natural number $n\in \mathbb {N}$ , $n>1$ , can be represented as a product of primes (not necessarily distinct), that is $n=p_{1}p_{2}\dots p_{k},$ where $p_{1}\in \mathbb {P} ,\ p_{2}\in \mathbb {P} ,\ \dots ,\ p_{k}\in \mathbb {P}$ , and such representation is unique up to the order of factors.

If we form two sets, the first consisting of positive integers having even number of prime factors, the second consisting of positive integers having an odd number of prime factors, in their canonical representation, then the two sets are approximately the same size.

If, however, we limit our two sets to those positive integers whose canonical representation contains no primes in arithmetic progression, for example $6m+1$ , $m=1,2,\dots$ or the progression $km+l$ , $1\leq l<k$ , $(l,k)=1$ , $m=0,1,2,\dots$ , then of these positive integers, those with an even number of prime factors will tend to be fewer than those with odd number of prime factors. Karatsuba discovered this property. He found also a formula for this phenomenon, a formula for the difference in cardinalities of sets of natural numbers with odd and even amount of prime factors, when these factors are complied with certain restrictions. In all cases, since the sets involved are infinite, by "larger" and "smaller" we mean the limit of the ratio of the sets as an upper bound on the primes goes to infinity. In the case of primes containing an arithmetic progression, Karatsuba proved that this limit is infinite.

We restate the Karatsuba phenomenon using mathematical terminology.

Let $\mathbb {N} _{0}$ and $\mathbb {N} _{1}$ be subsets of $\mathbb {N}$ , such that $n\in \mathbb {N} _{0}$ , if $n$ contains an even number of prime factors, and $n\in \mathbb {N} _{1}$ , if $n$ contains an odd number of prime factors. Intuitively, the sizes of the two sets $\mathbb {N} _{0}$ and $\mathbb {N} _{1}$ are approximately the same. More precisely, for all $x\geq 1$ , we define $n_{0}(x)$ and $n_{1}(x)$ , where $n_{0}(x)$ is the cardinality of the set of all numbers $n$ from $\mathbb {N} _{0}$ such that $n\leq x$ , and $n_{1}(x)$ is the cardinality of the set of all numbers $n$ from $\mathbb {N} _{1}$ such that $n\leq x$ . The asymptotic behavior of $n_{0}(x)$ and $n_{1}(x)$ was derived by E. Landau:^[8]

n_{0}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right),n_{1}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right);c>0.

This shows that

n_{0}(x)\sim n_{1}(x)\sim {\frac {1}{2}}x,

that is $n_{0}(x)$ and $n_{1}(x)$ are asymptotically equal.

Further,

n_{1}(x)-n_{0}(x)=O\left(xe^{-c{\sqrt {\ln x}}}\right),

so that the difference between the cardinalities of the two sets is small.

On the other hand, if we let $k\geq 2$ be a natural number, and $l_{1},l_{2},\dots l_{r}$ be a sequence of natural numbers, $1\leq r<\varphi (k)$ , such that $1\leq l_{j}<k$ ; $(l_{j},k)=1$ ; every $l_{j}$ are different modulo $k$ ; $j=1,2,\dots r.$ Let $\mathbb {A}$ be a set of primes belonging to the progressions $kn+l_{j}$ ; $j\leq r$ . ( $\mathbb {A}$ is the set of all primes not dividing $k$ ).

We denote as $\mathbb {N} ^{*}$ a set of natural numbers, which do not contain prime factors from $\mathbb {A}$ , and as $\mathbb {N} _{0}^{*}$ a subset of numbers from $\mathbb {N} ^{*}$ with even number of prime factors, as $\mathbb {N} _{1}^{*}$ a subset of numbers from $\mathbb {N} ^{*}$ with odd number of prime factors. We define the functions

n^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} ^{*}\end{array}}1;n_{0}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{0}^{*}\end{array}}1;n_{1}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{1}^{*}\end{array}}1.

Karatsuba proved that for $x\to +\infty$ , the asymptotic formula

n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},

is valid, where $C$ is a positive constant.

He also showed that it is possible to prove the analogous theorems for other sets of natural numbers, for example, for numbers which are representable in the form of the sum of two squares, and that sets of natural numbers, all factors of which do belong to $\mathbb {A}$ , will display analogous asymptotic behavior.

The Karatsuba theorem was generalized for the case when $\mathbf {A}$ is a certain unlimited set of primes.

The Karatsuba phenomenon is illustrated by the following example. We consider the natural numbers whose canonical representation does not include primes belonging to the progression $6m+1$ , $m=1,2,\dots$ . Then this phenomenon is expressed by the formula:

n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},\qquad x\to +\infty .

Notes

↑ Tao, Terence (2007-06-05). "Open question: The parity problem in sieve theory" . Retrieved 2008-08-11.
↑ Cojocaru, Alina Carmen; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. ISBN 0-521-61275-6.
↑ Friedlander, John; Henryk Iwaniec (1997-02-18). "Using a parity-sensitive sieve to count prime values of a polynomial". Proceedings of the National Academy of Sciences. 94 (4): 1054–1058. Bibcode:1997PNAS...94.1054F. doi: 10.1073/pnas.94.4.1054 . PMC 19742 . PMID 11038598. 1054–1058.
↑ Friedlander, John; Henryk Iwaniec (1998). "Asymptotic sieve for primes". Annals of Mathematics. 148 (3): 1041–1065. arXiv: math/9811186 . Bibcode:1998math.....11186F. doi:10.2307/121035. JSTOR 121035. S2CID 11574656.
↑ Harman, Glyn (2007). Prime-detecting sieves. London Mathematical Society Monographs. 33. Princeton University Press. pp. 45, 335. ISBN 978-0-691-12437-7. Zbl 1220.11118.
↑ Karatsuba, A. A. (2011). "A property of the set of prime numbers". Russian Mathematical Surveys. 66 (2): 209–220. Bibcode:2011RuMaS..66..209K. doi:10.1070/RM2011v066n02ABEH004739.
↑ Karatsuba, A. A. (2011). "A property of the Set of Primes as a Multiplicative Basis of Natural Numbers". Doklady Mathematics (84:1): 1–4.
↑ Landau, E. (1912). "Über die Anzahl der Gitter punkte in gewissen Bereichen". Gött. Nachricht.: 687–771.

Related Research Articles

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization.

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even whole number greater than 2 is the sum of two prime numbers.

In mathematics, a divisor of an integer $, also called a factor of, is an integer that may be multiplied by some integer to produce . In this case, one also says that is a multiple of An integer is divisible or evenly divisible by another integer if is a divisor of; this implies dividing by leaves no remainder.$

In mathematics, the $p$ -adic number system for any prime number $p$ extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems. The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value. In particular, two $p$ -adic numbers are considered to be close when their difference is divisible by a high power of $p$ : the higher the power, the closer they are. This property enables $p$ -adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles.

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

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.

In mathematics, Dickson's lemma states that every set of $-tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it in order to prove a result in number theory about perfect numbers. However, the lemma was certainly known earlier, for example to Paul Gordan in his research on invariant theory.$

In mathematics, and more particularly in number theory, primorial, denoted by “#”, is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 7² and 15750 = 2 × 3² × 5³ × 7 are both 7-smooth, while 11 and 702 = 2 × 3³ × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers. The 2-smooth numbers are just the powers of 2, while 5-smooth numbers are known as regular numbers.

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 prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.

Carmichael function function of interest in number theory

In number theory, a branch of mathematics, the Carmichael function associates to every positive integer $n$ a positive integer $λ (n)$ , defined as the smallest positive integer $m$ such that

In mathematics, the Legendre sieve, named after Adrien-Marie Legendre, is the simplest method in modern sieve theory. It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers. Because it is a simple extension of Eratosthenes' idea, it is sometimes called the Legendre–Eratosthenes sieve.

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In mathematics, more specifically in the field of analytic number theory, a Landau–Siegel zero or simply Siegel zero, named after Edmund Landau and Carl Ludwig Siegel, is a type of potential counterexample to the generalized Riemann hypothesis, on the zeros of Dirichlet L-functions associated to quadratic number fields. Roughly speaking, these are possible zeros very near to $s = 1$ .

In mathematics, a Kloosterman sum is a particular kind of exponential sum. They are named for the Dutch mathematician Hendrik Kloosterman, who introduced them in 1926 when he adapted the Hardy–Littlewood circle method to tackle a problem involving positive definite diagonal quadratic forms in four as opposed to five or more variables, which he had dealt with in his dissertation in 1924.

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:

Goldbach's conjecture: Can every even integer greater than 2 be written as the sum of two primes?
Twin prime conjecture: Are there infinitely many primes p such that p + 2 is prime?
Legendre's conjecture: Does there always exist at least one prime between consecutive perfect squares?
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 n² + 1?

In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up to a specified integer. It was discovered by Indian student S. P. Sundaram in 1934.

In number theory, the fundamental lemma of sieve theory is any of several results that systematize the process of applying sieve methods to particular problems. Halberstam & Richert write:

A curious feature of sieve literature is that while there is frequent use of Brun's method there are only a few attempts to formulate a general Brun theorem ; as a result there are surprisingly many papers which repeat in considerable detail the steps of Brun's argument.

Anatoly Alexeyevich Karatsuba was a Russian mathematician working in the field of analytic number theory, p-adic numbers and Dirichlet series.

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.

[1] Tao, Terence (2007-06-05). "Open question: The parity problem in sieve theory" . Retrieved 2008-08-11.

[2] Cojocaru, Alina Carmen; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. ISBN 0-521-61275-6.

[3] Friedlander, John; Henryk Iwaniec (1997-02-18). "Using a parity-sensitive sieve to count prime values of a polynomial". Proceedings of the National Academy of Sciences. 94 (4): 1054–1058. Bibcode:1997PNAS...94.1054F. doi: 10.1073/pnas.94.4.1054 . PMC 19742 . PMID 11038598. 1054–1058.

[4] Friedlander, John; Henryk Iwaniec (1998). "Asymptotic sieve for primes". Annals of Mathematics. 148 (3): 1041–1065. arXiv: math/9811186 . Bibcode:1998math.....11186F. doi:10.2307/121035. JSTOR 121035. S2CID 11574656.

[5] Harman, Glyn (2007). Prime-detecting sieves. London Mathematical Society Monographs. 33. Princeton University Press. pp. 45, 335. ISBN 978-0-691-12437-7. Zbl 1220.11118.

[6] Karatsuba, A. A. (2011). "A property of the set of prime numbers". Russian Mathematical Surveys. 66 (2): 209–220. Bibcode:2011RuMaS..66..209K. doi:10.1070/RM2011v066n02ABEH004739.

[7] Karatsuba, A. A. (2011). "A property of the Set of Primes as a Multiplicative Basis of Natural Numbers". Doklady Mathematics (84:1): 1–4.

[8] Landau, E. (1912). "Über die Anzahl der Gitter punkte in gewissen Bereichen". Gött. Nachricht.: 687–771.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]