Tamiz de turán

Estimar el tamaño de los conjuntos tamizados

Pal Turán

En teoría de números , la criba de Turán es una técnica para estimar el tamaño de "conjuntos cribados" de números enteros positivos que satisfacen un conjunto de condiciones que se expresan mediante congruencias . Fue desarrollada por Pál Turán en 1934.

Descripción

En términos de la teoría de tamices, el tamiz de Turán es de tipo combinatorio : se deriva de una forma rudimentaria del principio de inclusión-exclusión . El resultado proporciona un límite superior para el tamaño del conjunto tamizado.

Sea A un conjunto de números enteros positivos ≤ x y sea P un conjunto de números primos. Para cada p en P , sea A _p el conjunto de elementos de A divisibles por p y extendamos esto para que sea A _d la intersección de A _p para p dividiendo a d , cuando d es un producto de primos distintos de P . Además, sea A ₁ el propio A. Sea z un número real positivo y P ( z ) el producto de los primos en P que son ≤ z . El objeto de la criba es estimar

${\displaystyle S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .}$

Suponemos que | A _d | puede estimarse, cuando d es un primo p por

${\displaystyle \left\vert A_{p}\right\vert ={\frac {1}{f(p)}}X+R_{p}}$

y cuando d es un producto de dos primos distintos d = p q por

${\displaystyle \left\vert A_{pq}\right\vert ={\frac {1}{f(p)f(q)}}X+R_{p,q}}$

donde X   = | A | y f es una función con la propiedad de que 0 ≤ f ( d ) ≤ 1. Ponga

${\displaystyle U(z)=\sum _{p\mid P(z)}f(p).}$

Entonces

${\displaystyle S(A,P,z)\leq {\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 .}$

Aplicaciones

• El teorema de Hardy-Ramanujan establece que el orden normal de ω( n ), el número de factores primos distintos de un número n , es log(log( n ));
• Casi todos los polinomios enteros (tomados en orden de altura) son irreducibles .

Referencias

• Alina Carmen Cojocaru; M. Ram Murty. Introducción a los métodos de tamizado y sus aplicaciones . Textos para estudiantes de la London Mathematical Society. Vol. 66. Cambridge University Press . Págs. 47–62. ISBN 0-521-61275-6.
• Greaves, George (2001). Tamices en la teoría de números . Springer-Verlag. ISBN 3-540-41647-1.
• Halberstam, Heini ; Richert, H.-E. (1974). Métodos de tamizado . Monografías de la London Mathematical Society. Vol. 4. Academic Press . ISBN 0-12-318250-6.MR  0424730.Zbl 0298.10026  .​
• Christopher Hooley (1976). Aplicaciones de los métodos de criba a la teoría de números . Cambridge University Press. pág. 21. ISBN 0-521-20915-3.