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 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.

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).

Modern sieves include the Brun sieve, the Selberg sieve, and the large 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 has been some partial successes, especially in combination with other number theoretic tools. Highlights include:

# "Brun's theorem", which asserts that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of the primes themselves diverge);
# "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.
# The "fundamental lemma of sieve theory", which (very roughly speaking) 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 N^epsilon iterations provided that epsilon 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 N^{1/2} iterations), but can be enough to obtain results regarding almost primes.
# The "Bombieri–Friedlander–Iwaniec theorem", which asserts that there are infinitely many primes of the form a^2 + b^4.

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 harv|Halberstam|Richert|1974.

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.

References

* | series= London Mathematical Society Student Texts | volume= 66
*
*
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Fundamental lemma of sieve theory — 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] Rp|92–93write:Common notationWe use these notations: * A is a set …   Wikipedia

  • 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… …   Wikipedia

  • Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… …   Wikipedia

  • Sieve method — Sieve method, or the method of sieves, can mean: in combinatorics, the set of methods dealt with in sieve theory or more specifically, the Inclusion exclusion principle in statistics, and particularly econometrics, the use of sieve estimators in… …   Wikipedia

  • Sieve (mathematics) — In mathematics, sieve has several possible definitions: * In number theory, a sieve is a technique for counting the size of certain sets whose precise number of elements is hard to determine. See sieve theory, general number field sieve, and… …   Wikipedia

  • Sieve — In general, a sieve separates wanted/desired elements from unwanted material using a tool such as a mesh, net or other filtration or distillation methods, but it is also used for classification of powders by particle size, or for size measurement …   Wikipedia

  • Sieve of Sundaram — In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered by an Indian student S. P. Sundaram from Sathyamangalam in 1934. [cite journal |author=V.… …   Wikipedia

  • Sieve (category theory) — In category theory, a branch of mathematics, a sieve is a way of choosing arrows with a common codomain. It is a categorical analogue of a collection of open subsets of a fixed open set in topology. In a Grothendieck topology, certain sieves… …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Large sieve — In mathematics, the large sieve is a method of analytic number theory. As the name implies, it was developed in sieve theory, (for example) sifting from an integer sequence by means of congruence conditions modulo prime numbers in which a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”