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" 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

:

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

:$leftvert\; A\_p\; ightvert\; =\; frac\{1\}\{f(p)\}\; X\; +\; R\_p$

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

:$leftvert\; A\_\{pq\}\; ightvert\; =\; 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)\}\; leftvert\; R\_p\; ightvert\; +frac\{1\}\{U(z)^2\}\; sum\_\{p,q\; mid\; P(z)\}\; leftvert\; R\_\{p,q\}\; ightvert\; .$

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

*
*
*
*