Turan sieve: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
(remove WPmarkup; subpages)
mNo edit summary
 
Line 35: Line 35:
* {{cite book | author=Heini Halberstam | coauthors=H.E. Richert | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6}}
* {{cite book | author=Heini Halberstam | coauthors=H.E. Richert | title=Sieve Methods | publisher=[[Academic Press]] | date=1974 | isbn=0-12-318250-6}}
* {{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}}
* {{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}}
[[Category:Suggestion Bot Tag]]

Latest revision as of 07:00, 31 October 2024

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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 Ap denote the set of elements of A divisible by p and extend this to let Ad 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

References