“Selberg sieve”的意思、由来-开放百科全书

词条

Selberg sieve

释义

Description
Applications
References

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. Let A_d denote the set of elements of A divisible by d when d is a product of distinct primes from P. Further let A₁ 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 |A_d| 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

where [d₁,d₂] denotes the least common multiple of d₁ and d₂. It is often useful to estimate V(z) by the bound

Applications

The Brun–Titchmarsh theorem on the number of primes in arithmetic progression;
The number of n ≤ x such that n is coprime to φ(n) is asymptotic to e^−γ x / log log log (x) .

References

{{cite book | first1=Alina Carmen | last1=Cojocaru|author1-link= Alina Carmen Cojocaru | first2=M. Ram | last2=Murty | author2-link=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=Cambridge University Press | isbn=0-521-61275-6 | pages=113–134 | year=2005 | zbl=1121.11063 }}
{{cite book | last1= Diamond | first1 = Harold G. | last2 = Halberstam | first2 = Heini | authorlink2 = Heini Halberstam | others = With William F. Galway | title = A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions |series= Cambridge Tracts in Mathematics |volume=177 | publisher =Cambridge University Press | location=Cambridge | year=2008 | isbn=978-0-521-89487-6 | zbl=1207.11099 }}
{{cite book | first=George | last=Greaves | title=Sieves in number theory | publisher=Springer-Verlag | date=2001 | isbn=3-540-41647-1 | zbl=1003.11044 | series=Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge | volume=43 | location=Berlin }}
{{cite book | first1=Heini | last1=Halberstam | authorlink1 = Heini Halberstam | first2=H.E. | last2=Richert | authorlink2=Hans-Egon Richert | title=Sieve Methods | publisher=Academic Press | date=1974 | isbn=0-12-318250-6 | zbl=0298.10026 | series=London Mathematical Society Monographs | volume=4 }}
{{cite book | first=Christopher | last=Hooley | authorlink=Christopher Hooley | title=Applications of sieve methods to the theory of numbers | publisher=Cambridge University Press | date=1976 | isbn=0-521-20915-3| pages=7–12 | zbl=0327.10044 | series=Cambridge Tracts in Mathematics | volume=70 }}
{{cite journal | first=Atle | last=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 | zbl=0041.01903 | issn=0368-6302 }}

1 : Sieve theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。