tamiz de Legendre

En matemáticas , la criba de Legendre , que recibe su nombre de Adrien-Marie Legendre , es el método más sencillo de la teoría moderna de cribas . Aplica el concepto de la criba de Eratóstenes para hallar cotas superiores o inferiores del número de primos dentro de un conjunto dado de enteros. Debido a que es una simple extensión de la idea de Eratóstenes , a veces se la denomina criba de Legendre-Eratóstenes . ^{[ 1 ]}

La idea central del método se expresa mediante la siguiente identidad, a veces llamada identidad de Legendre :

${\displaystyle S(A,P)=\sum _{a\in A}\sum _{d\mid a;\,d\mid P}\mu (d)=\sum _{d\mid P}\mu (d)|A_{d}|,}$

donde A es un conjunto de enteros, P es un producto de primos distintos,${\displaystyle \mu }$es la función de Möbius y${\displaystyle A_{d}}$es el conjunto de enteros en A divisibles por d , y S(A, P) se define como:

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

es decir, S ( A , P ) es el recuento de números en A que no tienen factores comunes con P . 

Nótese que, en el caso más típico, A son todos los enteros menores o iguales a algún número real X , P es el producto de todos los primos menores o iguales a algún entero z < X , y entonces la identidad de Legendre se convierte en:  

${\displaystyle {\begin{aligned}S(A,P)={}&\sum _{d\mid P}\mu (d)\left\lfloor {\frac {X}{d}}\right\rfloor \\[6pt]={}&\lfloor X\rfloor -\sum _{p_{1}\leq z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor \\[4pt]&{}-\sum _{p_{1}<p_{2}<p_{3}\leq z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots +\mu (P)\left\lfloor {\frac {X}{P}}\right\rfloor \end{aligned}}}$

(dónde${\displaystyle \lfloor X\rfloor }$denota la función piso ). En este ejemplo, es evidente que la identidad de Legendre se deriva de la criba de Eratóstenes: el primer término es el número de enteros menores que X , el segundo término elimina los múltiplos de todos los primos, el tercer término vuelve a sumar los múltiplos de dos primos (que se contaron erróneamente al ser "tachados dos veces") pero también vuelve a sumar los múltiplos de tres primos una vez de más, y así sucesivamente hasta que todos${\displaystyle 2^{\pi (z)}}$(dónde${\displaystyle \pi (z)}$denota el número de primos menores que z ) combinaciones de primos que se han cubierto. 

Una vez que se ha calculado S ( A , P ) para este caso especial, se puede utilizar para acotar ${\displaystyle \pi (X)}$utilizando la expresión

${\displaystyle S(A,P)\geq \pi (X)-\pi (z)+1,\,}$

lo cual se deduce inmediatamente de la definición de S ( A , P ).  

El método de cribado de Legendre presenta el problema de que las fracciones de los términos se acumulan, generando un error considerable. Esto significa que, en la mayoría de los casos, solo proporciona límites muy débiles. Por esta razón, casi nunca se utiliza en la práctica, habiendo sido reemplazado por otras técnicas como el método de Brun y el de Selberg . Sin embargo, dado que estos métodos más potentes son extensiones de las ideas básicas del método de Legendre, resulta útil comprender primero cómo funciona este último.