Turán sieve

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

:S(A,P,z) = leftvert A setminus igcup_{p in P(z)} A_p ightvert .

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

*
*
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Histoire de la fonction zêta de Riemann — En mathématiques, la fonction zêta de Riemann est définie comme la somme d une série particulière, dont les applications à la théorie des nombres et en particulier à l étude des nombres premiers se sont avérées essentielles. Cet article présente… …   Wikipédia en Français

  • Alfréd Rényi — (20 March 1921 ndash; 1 February 1970) was a Hungarian mathematician who made contributions in combinatorics and graph theory but mostly in probability theory. [citation|title=Obituary: Alfred Renyi|first=David|last=Kendall|journal=Journal of… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of inequalities — This page lists Wikipedia articles about named mathematical inequalities. Inequalities in pure mathematics =Analysis= * Askey–Gasper inequality * Bernoulli s inequality * Bernstein s inequality (mathematical analysis) * Bessel s inequality *… …   Wikipedia

  • Islamic arts — Visual, literary, and performing arts of the populations that adopted Islam from the 7th century. Islamic visual arts are decorative, colourful, and, in religious art, nonrepresentational; the characteristic Islamic decoration is the arabesque.… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”