Brun sieve

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 Viggo Brun in 1915.

Description

In terms of sieve theory the Brun sieve is of "combinatorial type": that is, derives from a careful use of the inclusion-exclusion principle.

Let "A" be a set of positive integers ≤ "x" and let "P" be a set of primes. For each "p" in "P", let "A""p" denote the set of elements of "A" divisible by "p" and extend this to let "A""d" the intersection of the "A""p" for "p" dividing "d", when "d" is a product of distinct primes from "P". Further let A1 denote "A" itself. Let "z" be a positive real number and "P"("z") denote the primes in "P" ≤ "z". The object of the sieve is to estimate

:S(A,P,z) = leftvert A setminus igcup_{p in P(z)} A_p ightvert .

We assume that |"A""d"| may be estimated by

: leftvert A_d ightvert = frac{w(d)}{d} X + R_d .

where "w" is a multiplicative function and "X" = |"A"|. Let

: W(z) = prod_{p in P(z)} left(1 - frac{w(p)}{p} ight) .

Brun's pure sieve

This formulation is from Cocojaru & Murty, Theorem 6.1.2. With the notation as above, assume that
*|"R""d"| ≤ "w"("d") for any squarefree "d" composed of primes in "P" ;
* "w"("p") < "C" for all "p" in "P" ;
* sum_{p in P_z} frac{w(p)}{p} < D loglog z + E;

where "C", "D", "E" are constants.

Then

: S(A,P,z) = X cdot W(z) cdot left({1 + Oleft(((log z)^{-b log b} ight)} ight) + Oleft(z^{b loglog z} ight) .

In particular, if log "z" &lt; "c" log "x" / log log "x" for a suitably small "c", then

: S(A,P,z) = X cdot W(z) (1+o(1)) . ,

Applications

* Brun's theorem: the sum of the reciprocals of the twin primes converges;
* Schnirelmann's theorem: every even number is a sum of at most "C" primes (where "C" 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.

References

*
*
*
*
*
*.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

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

  • Brun's constant — In 1919 Viggo Brun showed that the sum of the reciprocals of the twin primes (pairs of prime numbers which differ by 2) converges to a mathematical constant now called Brun s constant for twin primes and usually denoted by B 2 OEIS|id=A065421::B… …   Wikipedia

  • Brun's theorem — In mathematics, Brun s theorem is a result in number theory proved by Viggo Brun in 1919. It states that the sum of the reciprocals of the twin primes is convergent with a finite value known as Brun s constant. It has historical importance in the …   Wikipedia

  • Brun–Titchmarsh theorem — In analytic number theory, the Brun–Titchmarsh theorem is an upper bound on the distribution of primes in arithmetic progression. It states that, if pi(x;a,q) counts the number of primes p congruent to a modulo q with p ≤ x , then:pi(x;a,q) le… …   Wikipedia

  • Viggo Brun — (13 October 1885, Lier ndash; 15 August 1978, Drøbak) was a Norwegian mathematician.He studied at the University of Oslo and began research at the University of Gottingen in 1910. In 1923, Brun became a professor at the Technical University in… …   Wikipedia

  • Legendre sieve — In mathematics, the Legendre sieve 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… …   Wikipedia

  • Viggo Brun — est un mathématicien norvégien né en le 13 octobre 1882 à Lier et mort le 15 août 1978 à Drøbak. Il est essentiellement connu pour son théorème montrant que la somme des inverses des nombres premiers jumeaux est convergente. En son honneur on a… …   Wikipédia en Français

  • Viggo Brun — (13 de octubre de 1885, Lier – 15 agosto de 1978, Drøbak) fue un matemático Noruego. Estudió en la Universidad de Oslo y comenzó su carrera investigativa en la Universidad de Gottingen en 1910. En 1923, Brun comenzó trabajó como profesor en… …   Wikipedia Español

  • 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

  • Viggo Brun — (* 13. Oktober 1885 in Lier; † 15. August 1978 in Drøbak) war ein norwegischer Mathematiker. Brun war das jüngste von zehn Kindern eines Artillerie Hauptmanns. Er studierte Mathematik und Naturwissenschaften an der Universität Oslo, um Lehrer zu… …   Deutsch Wikipedia

Share the article and excerpts

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