Selberg sieve: Difference between revisions
imported>Richard Pinch (→References: moving books to bibliography) |
mNo edit summary |
||
Line 36: | Line 36: | ||
==References== | ==References== | ||
* {{cite journal | author=Atle Selberg | authorlink=Atle Selberg | title=On an elementary method in the theory of primes | journal=Norske Vid. Selsk. Forh. Trondheim | volume=19 | year=1947 | pages=64-67 }} | * {{cite journal | author=Atle Selberg | authorlink=Atle Selberg | title=On an elementary method in the theory of primes | journal=Norske Vid. Selsk. Forh. Trondheim | volume=19 | year=1947 | pages=64-67 }}[[Category:Suggestion Bot Tag]] |
Latest revision as of 16:01, 16 October 2024
In mathematics, in the field of 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 terms of sieve theory the Selberg sieve is of combinatorial type: that is, derives from a careful use of the inclusion-exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an upper bound for the size of the sifted set.
Let A be a set of positive integers ≤ x and let P be a set of primes. For each p in P, let Ap denote the set of elements of A divisible by p and extend this to let Ad the intersection of the Ap 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 product of the primes in P which are ≤ z. The object of the sieve is to estimate
We assume that |Ad| may be estimated by
where f is a multiplicative function and X = |A|. Let the function g be obtained from f by Möbius inversion, that is
where μ is the Möbius function. Put
Then
It is often useful to estimate V(z) by the bound
Applications
- The Brun-Titchmarsh theorem on the number of primes in an arithmetic progression;
- The number of n ≤ x such that n is coprime to φ(n) is asymptotic to e-γ x / log log log (x) .
References
- Atle Selberg (1947). "On an elementary method in the theory of primes". Norske Vid. Selsk. Forh. Trondheim 19: 64-67.