Turan sieve

In mathematics, in the field of number theory, the Turán 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 Pál Turán in 1934.

Description

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 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)=|A\setminus \bigcup _{p\in P(z)}{A}_p|.$

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

$\left|A_p\right|=\frac{1}{f(p)}X+R_p$

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

$\left|A_{pq}\right|=\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)=\sum _{p\mid P(z)}f(p).$

Then

$S(A,P,z)\le \frac{X}{U(z)}+\frac{2}{U(z)}\sum _{p\mid P(z)}\left|R_p\right|+\frac{1}{U(z{)}^2}\sum _{p,q\mid P(z)}\left|R_{p,q}\right|.$

Applications

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

References

• Alina Carmen Cojocaru; M. Ram Murty. An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. pp. 47-62. ISBN 0-521-61275-6. 
• George Greaves (2001). Sieves in number theory. Springer-Verlag. ISBN 3-540-41647-1. 
• Heini Halberstam; H.E. Richert (1974). Sieve Methods. Academic Press. ISBN 0-12-318250-6. 
• Christopher Hooley (1976). Applications of sieve methods to the theory of numbers. Cambridge University Press. pp. 21. ISBN 0-521-20915-3.