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.

Pál Turán

Description

edit

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 Ap denote the set of elements of A divisible by p and extend this to let Ad be the intersection of the Ap for p dividing d, when d is a product of distinct primes from P. Further let A1 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 |Ad| may be estimated, when d is a prime p by

 

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

 

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

 

Then

 

Applications

edit

References

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