Turán Sieve

In 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'' 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) = \left\vert A \setminus \bigcup_ A_p \right\vert .$

We assume that , ''A''_''d'', may be estimated, when ''d'' is a prime ''p'' by

:$\left\vert A_p \right\vert = \frac X + R_p$

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

:$\left\vert A_ \right\vert = \frac X + R_$

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

:$U(z) = \sum_ f(p) .$

Then

:$S(A,P,z) \le \frac + \frac \sum_ \left\vert R_p \right\vert + \frac \sum_ \left\vert R_ \right\vert .$

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

*
*
*
*

{{DEFAULTSORT:Turan sieve
Sieve theory