Correlation swap

2011-05-14T22:42:10Z

160.39.51.111: /* Payoff Definition */ Corrected definition with i ≠ j + minor precisions

In [[number theory]], the '''Turán sieve''' is a technique for estimating the size of "sifted sets" of [[positive integer]]s which satisfy a set of conditions which are expressed by [[Congruence relation#Modular arithmetic|congruence]]s. 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''1 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

:<math>S(A,P,z) = \left\vert A \setminus \bigcup_{p \in P(z)} A_p \right\vert . </math>

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

:<math> \left\vert A_p \right\vert = \frac{1}{f(p)} X + R_p </math>

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

:<math> \left\vert A_{pq} \right\vert = \frac{1}{f(p)f(q)} X + R_{p,q} </math>

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

:<math> U(z) = \sum_{p \mid P(z)} f(p) . </math>

Then

:<math> S(A,P,z) \le \frac{X}{U(z)} + \frac{2}{U(z)} \sum_{p \mid P(z)} \left\vert R_p \right\vert +
\frac{1}{U(z)^2} \sum_{p,q \mid P(z)} \left\vert R_{p,q} \right\vert . </math>

==Applications==
* The [[Hardy–Ramanujan theorem]] that the [[normal order of an arithmetic function|normal order]] of ω(''n''), the number of distinct [[prime factor]]s of a number ''n'', is log(log(''n''));
* Almost all integer polynomials (taken in order of height) are irreducible.

==References==
* {{cite book | author=Alina Carmen Cojocaru | coauthors=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=54:12689 | 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]]

formulasearchengine - User contributions [en]

Correlation swap