Turán sieve

In terms of sieve theory the Turán sieve is of combinatorial type: deriving from a rudimentary form of the inclusion–exclusion principle. 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 A_p denote the set of elements of A divisible by p and extend this to let A_d be the intersection of the A_p for p dividing 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

:$S(A,P,z)\; =\; \backslash left\backslash vert\; A\; \backslash setminus\; \backslash bigcup\_\{p\; \backslash mid\; P(z)\}\; A\_p\; \backslash right\backslash vert\; .$

We assume that |A_d| may be estimated, when d is a prime p by

:$\backslash left\backslash vert\; A\_p\; \backslash right\backslash vert\; =\; \backslash frac\{1\}\{f(p)\}\; X\; +\; R\_p$

and when d is a product of two distinct primes d = p q by

:$\backslash left\backslash vert\; A\_\{pq\}\; \backslash right\backslash vert\; =\; \backslash frac\{1\}\{f(p)f(q)\}\; X\; +\; R\_\{p,q\}$

where X   =   |A| and f is a function with the property that 0 ≤ f(d) ≤ 1. Put

:$U(z)\; =\; \backslash sum\_\{p\; \backslash mid\; P(z)\}\; f(p)\; .$

Then

:$S(A,P,z)\; \backslash le\; \backslash frac\{X\}\{U(z)\}\; +\; \backslash frac\{2\}\{U(z)\}\; \backslash sum\_\{p\; \backslash mid\; P(z)\}\; \backslash left\backslash vert\; R\_p\; \backslash right\backslash vert\; +$

\frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert .

• The Hardy–Ramanujan theorem that the normal order of ω(n), the number of distinct prime factors of a number n, is log(log(n));
• Almost all integer polynomials (taken in order of height) are irreducible.

• {{cite book | author=Alina Carmen Cojocaru |author2=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=47–62 }}
• {{cite book | first=George | last=Greaves | title=Sieves in number theory | publisher=Springer-Verlag | date=2001 | isbn=3-540-41647-1}}
• {{cite book | last1= Halberstam | first1=Heini |author1-link=Heini Halberstam | author2-link=Hans-Egon Richert | first2=H.-E. | last2=Richert | title=Sieve Methods | series=London Mathematical Society Monographs | volume=4 | publisher=Academic Press | date=1974 | isbn=0-12-318250-6 | mr=424730 | zbl=0298.10026 }}
• {{cite book | author= Christopher 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=21}}

{{DEFAULTSORT:Turan sieve}}

Category:Sieve theory