Criba de Legendre

Criba de Legendre

Criba de Legendre

En matemáticas, la criba de Legendre es el más simple método en teoría de cribas. Este aplica el concepto de la criba de Eratostenes para encontrar estimativos superiores e inferiores al número de primos en un conjunto de enteros dado. Debido a que este es una extensión simple de la idea usada en la criba de Eratostenes, este método de cribado es llamado algunas veces la criba de Eratostenes-Legendre.

Identidad de Legendre

La idea central del método es expresada por la siguiente identidad, algunas veces llamada la Identidad de Legendre:

S(A,P)= \sum_{a\in A}\sum_{d|a;d|P} \mu(d) =\sum_{d|P}\mu(d)|A_d|

Donde A es un conjunto de enteros, P es un producto de distintos primos, μ es la función de Möbius, Ad es el conjunto de enteros en A divisible por d, y S(A, P) es definido como:

S(A, P) = |\{n: n \in A, (n, P) = 1\}|

Luego S(A,P) es la cantidad de números en A sin factores comunes con P.

Note que en el caso más típico, A es el conjunto de todos los enteros menores o iguales a un número real X, P es el producto de todos los primos menores o iguales a algún entero z < X, asumiendo esto, la identidad de Legendre tomaría la forma:

S(A,P) =\sum_{d|P}\mu(d)\left\lfloor\frac{X}{p_1}\right\rfloor
=[X] - \sum_{p_1 < z} \left\lfloor\frac{X}{p_1}\right\rfloor + \sum_{p_1 < p_2 < z}
\left\lfloor\frac{X}{p_1p_2}\right\rfloor - \sum_{p_1 < p_2 < p_3 < z}
\left\lfloor\frac{X}{p_1p_2p_3}\right\rfloor + \cdots

(donde \lfloor X \rfloor denota la función parte entera). En este ejemplo, el hecho de que la criba de Legendre se derive de la criba de Eratostenes es claro: el primer término es el número de interos menores que X, el segundo término remueve los múltiplos de todos los primos, el tercero añade los múltiplos de dos primos (los cuales fueron descontados por que se "tacharon dos veces"), y así de manera sucesiva todos las 2π(z) (donde π(z) denota el número de primos menores que z) combinaciones de primos son consideradas por la criba de Legendre.

Una vez se ha calculado S(A,P) para este caso especial, este puede ser usado para acotar π(X) usando la expresión

S(A,P) \geq \pi(X) - \pi(z) + 1

la cual es una implicación clara de la definición de S(A,P).

Problemas

Desafortunadamente, la criba de Legendre tiene un problema con la parte fraccionaria de los diferentes términos, los cuales se acumulan en un término de error (esto es, términos en notación O) demasiado grande, la cual dice que la criba de Legendre da cotas muy débiles en muchos casos. Por esta razón, esta criba nunca es usada en la práctica, siendo siempre mejorada por otras técnicas de cribado tales como la Criba de Brun y la Criba de Selberg. Sin embargo, dado que estas cribas más poderosas son extensiones de las ideas básicas de la criba de Legendre, este método de cribado se vuelve util para entender cómo trabajan las cribas.

Véase

Obtenido de "Criba de Legendre"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Teoría de cribas — La teoría de cribas es un conjunto de técnicas generales en teoría de números, diseñadas para contar o estimar el tamaño de un conjunto de números enteros. El ejemplo primordial de un conjunto tamizado es conjunto de números primos menores… …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Viggo Brun — (13 de octubre de 1885, Lier – 15 agosto de 1978, Drøbak) fue un matemático Noruego. Estudió en la Universidad de Oslo y comenzó su carrera investigativa en la Universidad de Gottingen en 1910. En 1923, Brun comenzó trabajó como profesor en… …   Wikipedia Español

Compartir el artículo y extractos

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