Sieve theory

Summary

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.[citation needed] 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.[citation needed]

One successful approach is to approximate a specific sifted set of numbers (e.g. the set of prime numbers) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight functions on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze than the characteristic function of the set.

Basic sieve theory edit

For information on notation see at the end.

We start with some countable sequence of non-negative numbers  . In the most basic case this sequence is just the indicator function   of some set   we want to sieve. However this abstraction allows for more general situations. Next we introduce a general set of prime numbers called the sifting range   and their product up to   as a function  .

The goal of sieve theory is to estimate the sifting function

 

In the case of   this just counts the cardinality of a subset   of numbers, that are coprime to the prime factors of  .

The inclusion–exclusion principle edit

For   define

 

and for each prime   denote the set   and let   be the cardinality.

If one wants to calculate the cardinality of  , one can apply the inclusion–exclusion principle. This algorithm works like this: first one removes from the cardinality of   the cardinality   and  . Now since one has removed the numbers that are divisble by   and   twice, one has to add the cardinality  . In the next step one removes   and adds   and   again. Additionally one has now to remove  , i.e. the cardinality of all numbers divisible by   and  . This leads to the inclusion–exclusion principle

 

Legendre's identity edit

We can rewrite the sifting function with Legendre's identity

 

by using the Möbius function and some functions   induced by the elements of  

 

Example edit

Let   and  . The Möbius function is negative for every prime, so we get

 

Approximation of the congruence sum edit

One assumes then that   can be written as

 

where   is a density, meaning a multiplicative function such that

 

and   is an approximation of   and   is some remainder term. The sifting function becomes

 

or in short

 

One tries then to estimate the sifting function by finding upper and lower bounds for   respectively   and  .

The partial sum of the sifting function alternately over- and undercounts, so the remainder term will be huge. Brun's idea to improve this was to replace   in the sifting function with a weight sequence   consisting of restricted Möbius functions. Choosing two appropriate sequences   and   and denoting the sifting functions with   and  , one can get lower and upper bounds for the original sifting functions

 [1]

Since   is multiplicative, one can also work with the identity

 

Notation: a word of caution regarding the notation, in the literature one often identifies the set of sequences   with the set   itself. This means one writes   to define a sequence  . Also in the literature the sum   is sometimes notated as the cardinality   of some set  , while we have defined   to be already the cardinality of this set. We used   to denote the set of primes and   for the greatest common divisor of   and  .

Types of sieving edit

Modern sieves include the Brun sieve, the Selberg sieve, the Turán sieve, the large sieve, the larger sieve and the Goldston-Pintz-Yıldırım sieve. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the twin prime conjecture. While the original broad aims of sieve theory still are largely unachieved, there have been some partial successes, especially in combination with other number theoretic tools. Highlights include:

  1. Brun's theorem, which shows that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of all primes diverges);
  2. Chen's theorem, which shows that there are infinitely many primes p such that p + 2 is either a prime or a semiprime (the product of two primes); a closely related theorem of Chen Jingrun asserts that every sufficiently large even number is the sum of a prime and another number which is either a prime or a semiprime. These can be considered to be near-misses to the twin prime conjecture and the Goldbach conjecture respectively.
  3. The fundamental lemma of sieve theory, which asserts that if one is sifting a set of N numbers, then one can accurately estimate the number of elements left in the sieve after   iterations provided that   is sufficiently small (fractions such as 1/10 are quite typical here). This lemma is usually too weak to sieve out primes (which generally require something like   iterations), but can be enough to obtain results regarding almost primes.
  4. The Friedlander–Iwaniec theorem, which asserts that there are infinitely many primes of the form  .
  5. Zhang's theorem (Zhang 2014), which shows that there are infinitely many pairs of primes within a bounded distance. The Maynard–Tao theorem (Maynard 2015) generalizes Zhang's theorem to arbitrarily long sequences of primes.

Techniques of sieve theory edit

The techniques of sieve theory can be quite powerful, but they seem to be limited by an obstacle known as the parity problem, which roughly speaking asserts that sieve theory methods have extreme difficulty distinguishing between numbers with an odd number of prime factors and numbers with an even number of prime factors. This parity problem is still not very well understood.

Compared with other methods in number theory, sieve theory is comparatively elementary, in the sense that it does not necessarily require sophisticated concepts from either algebraic number theory or analytic number theory. Nevertheless, the more advanced sieves can still get very intricate and delicate (especially when combined with other deep techniques in number theory), and entire textbooks have been devoted to this single subfield of number theory; a classic reference is (Halberstam & Richert 1974) and a more modern text is (Iwaniec & Friedlander 2010).

The sieve methods discussed in this article are not closely related to the integer factorization sieve methods such as the quadratic sieve and the general number field sieve. Those factorization methods use the idea of the sieve of Eratosthenes to determine efficiently which members of a list of numbers can be completely factored into small primes.

Literature edit

  • Cojocaru, Alina Carmen; Murty, M. Ram (2006), An introduction to sieve methods and their applications, London Mathematical Society Student Texts, vol. 66, Cambridge University Press, ISBN 0-521-84816-4, MR 2200366
  • Motohashi, Yoichi (1983), Lectures on Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 72, Berlin: Springer-Verlag, ISBN 3-540-12281-8, MR 0735437
  • Greaves, George (2001), Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Berlin: Springer-Verlag, doi:10.1007/978-3-662-04658-6, ISBN 3-540-41647-1, MR 1836967
  • Harman, Glyn (2007). Prime-detecting sieves. London Mathematical Society Monographs. Vol. 33. Princeton, NJ: Princeton University Press. ISBN 978-0-691-12437-7. MR 2331072. Zbl 1220.11118.
  • Halberstam, Heini; Richert, Hans-Egon (1974). Sieve Methods. London Mathematical Society Monographs. Vol. 4. London-New York: Academic Press. ISBN 0-12-318250-6. MR 0424730.
  • Iwaniec, Henryk; Friedlander, John (2010), Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, Providence, RI: American Mathematical Society, ISBN 978-0-8218-4970-5, MR 2647984
  • Hooley, Christopher (1976), Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics, vol. 70, Cambridge-New York-Melbourne: Cambridge University Press, ISBN 0-521-20915-3, MR 0404173
  • Maynard, James (2015). "Small gaps between primes". Annals of Mathematics. 181 (1): 383–413. arXiv:1311.4600. doi:10.4007/annals.2015.181.1.7. MR 3272929.
  • Tenenbaum, Gérald (1995), Introduction to Analytic and Probabilistic Number Theory, Cambridge studies in advanced mathematics, vol. 46, Translated from the second French edition (1995) by C. B. Thomas, Cambridge University Press, pp. 56–79, ISBN 0-521-41261-7, MR 1342300
  • Zhang, Yitang (2014). "Bounded gaps between primes". Annals of Mathematics. 179 (3): 1121–1174. doi:10.4007/annals.2014.179.3.7. MR 3171761.

External links edit

References edit