In the field of
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â ...
, 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
Viggo Brun
Viggo Brun (13 October 1885 – 15 August 1978) was a Norwegian professor, mathematician and number theorist.
Contributions
In 1915, he introduced a new method, based on Legendre's version of the sieve of Eratosthenes, now known as the ' ...
in 1915 and later generalized to the
fundamental lemma of sieve theory by others.
Description
In terms of
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 prototypical example of a sifted set is the set of prime numbers up to some prescribed lim ...
the Brun sieve is of ''combinatorial type''; that is, it derives from a careful use of the
inclusion–exclusion principle
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
: , A \cu ...
.
Let
be a finite set of positive integers.
Let
be some 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.
For each prime
in
, let
denote the set of elements of
that are divisible by
.
This notation can be extended to other integers
that are products of distinct primes in
. In this case, define
to be the intersection of the sets
for the prime factors
of
.
Finally, define
to be
itself.
Let
be an arbitrary positive real number.
The object of the sieve is to estimate:
where the notation
denotes 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 set
, which in this case is just its number of elements.
Suppose in addition that
may be estimated by
where
is some
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'') i ...
, and
is some error function.
Let
Brun's pure sieve
This formulation is fro
Cojocaru & Murty Theorem 6.1.2. With the notation as above, suppose that
*
for any squarefree
composed of primes in
;
*
for all
in
;
*There exist constants
such that, for any positive real number
,
Then
where
is any positive integer and the
invokes
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
.
In particular, letting
denote the maximum element in
, if
for a suitably small
, then
Applications
*
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 ...
: the sum of the reciprocals of the
twin prime
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 ...
s converges;
*
Schnirelmann's theorem
In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.Schnirelmann, L.G. (1930).On the ...
: every even number is a sum of at most
primes (where
can be taken to be 6);
* There are infinitely many pairs of integers differing by 2, where each of the member of the pair is the product of at most 9 primes;
* Every even number is the sum of two numbers each of which is the product of at most 9 primes.
The last two results were superseded by
Chen's theorem, and the second by
Goldbach's weak conjecture
In number theory, Goldbach's weak conjecture, also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem, states that
: Every odd number greater than 5 can be expressed as the sum of three primes. (A prime m ...
(
).
References
*
*
*
*
*
* {{cite book , author= Christopher Hooley , author-link=Christopher Hooley , title=Applications of sieve methods to the theory of numbers , publisher=Cambridge University Press , date=1976 , isbn=0-521-20915-3.
Sieve theory