Sieve theory is a set of general techniques in
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, 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 number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s up to some prescribed limit ''X''. Correspondingly, the prototypical example of a sieve is the
sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
, or the more general
Legendre sieve
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 o ...
. 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 number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s) by another, simpler set (e.g. the set of
almost prime
In number theory, a natural number is called ''k''-almost prime if it has ''k'' prime factors. More formally, a number ''n'' is ''k''-almost prime if and only if Ω(''n'') = ''k'', where Ω(''n'') is the total number of primes in the prime fact ...
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 function
A weight function is a mathematical device used when performing a sum, integral, or average to give some elements more "weight" or influence on the result than other elements in the same set. The result of this application of a weight function is ...
s 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 In mathematics, the term "characteristic function" can refer to any of several distinct concepts:
* The indicator function of a subset, that is the function
::\mathbf_A\colon X \to \,
:which for a given subset ''A'' of ''X'', has value 1 at points ...
of the set.
Elementary sieve theory
We start with some
finite
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
sequence of non-negative numbers
. In the most basic case this sequence is just the
indicator function
In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
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
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of a subset of
of numbers, that are
coprime
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to the
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s of
.
We can rewrite this as
:
by using the
Möbius function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most oft ...
and some functions
induced by the elements of
:
One assumes then that
can be written as
:
where
is a ''density'', meaning a
multiplicative function
In number theory, a multiplicative function is an arithmetic function ''f''(''n'') of a positive integer ''n'' with the property that ''f''(1) = 1 and
f(ab) = f(a)f(b) whenever ''a'' and ''b'' are coprime.
An arithmetic function ''f''(''n'') is ...
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
Brun may refer to:
People
* Brun (surname)
* Brun (given name)
* Brun I of Saxony (c. 830/840–880)
* Brun of Querfurt (c. 974–1009), missionary archbishop and martyr
* Brun I, Count of Brunswick (c. 975–c. 1010)
Other
* Brun (grape), ...
'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
:
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.
Types of sieving
Modern sieves include the
Brun sieve In the field of number theory, the Brun sieve (also called Brun's pure 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. It was developed by Vi ...
, the
Selberg sieve
In 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. It was developed by Atle Selberg in the 1940s.
Description
In ...
, the
Turán sieve
In number theory, the Turán 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. It was developed by Pál Turán in 1934.
Description
In terms ...
, the
large sieve, and the
larger sieve In number theory, the larger sieve is a sieve invented by Patrick X. Gallagher. The name denotes a heightening of the large sieve. Combinatorial sieves like the Selberg sieve are strongest, when only a few residue classes are removed, while the te ...
. One of the original purposes of sieve theory was to try to prove conjectures in number theory such as the
twin prime conjecture
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin pr ...
. 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:
# ''
Brun's theorem
In number theory, Brun's theorem states that the sum of the Multiplicative inverse, reciprocals of the twin primes (pairs of prime numbers which differ by 2) Convergent series, converges to a finite value known as Brun's constant, usually denoted ...
'', which shows that the sum of the reciprocals of the twin primes converges (whereas the sum of the reciprocals of all primes diverges);
# ''
Chen's theorem'', which shows that there are infinitely many primes ''p'' such that ''p'' + 2 is either a prime or a
semiprime
In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime nu ...
(the product of two primes); a closely related theorem of
Chen Jingrun asserts that every
sufficiently large
In the mathematical areas of number theory and analysis, an infinite sequence or a function is said to eventually have a certain property, if it doesn't have the said property across all its ordered instances, but will after some instances have pa ...
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
A twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair (41, 43). In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term ''twin pr ...
and the
Goldbach conjecture respectively.
# 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 prime
In number theory, a natural number is called ''k''-almost prime if it has ''k'' prime factors. More formally, a number ''n'' is ''k''-almost prime if and only if Ω(''n'') = ''k'', where Ω(''n'') is the total number of primes in the prime fact ...
s.
# The ''
Friedlander–Iwaniec theorem
In analytic number theory the Friedlander–Iwaniec theorem states that there are infinitely many prime numbers of the form a^2 + b^4. The first few such primes are
:2, 5, 17, 37, 41, 97, 101, 137, 181, 197, 241, 257, 277, 281, 337, 401, 457, 57 ...
'', which asserts that there are infinitely many primes of the form
.
#
Zhang Zhang may refer to:
Chinese culture, etc.
* Zhang (surname) (å¼µ/å¼ ), common Chinese surname
** Zhang (surname ç« ), a rarer Chinese surname
* Zhang County (漳县), of Dingxi, Gansu
* Zhang River (漳河), a river flowing mainly in Henan
* ''Zha ...
's theorem , which shows that there are infinitely many
pairs of primes within a bounded distance. The Maynard–Tao theorem generalizes Zhang's theorem to arbitrarily long sequences of primes.
Techniques of sieve theory
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
Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
or
analytic number theory
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 Diric ...
. 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 and a more modern text is .
The sieve methods discussed in this article are not closely related to the
integer factorization
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.
When the numbers are suf ...
sieve methods such as the
quadratic sieve The quadratic sieve algorithm (QS) is an 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 considerab ...
and the
general number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form
:\exp\left( ...
. Those factorization methods use the idea of the
sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime n ...
to determine efficiently which members of a list of numbers can be completely factored into small primes.
Literature
*
*
*
*
*
*
*
*
*
*
External links
*
References
{{DEFAULTSORT:Sieve Theory