Tamiz Legendre

En matemáticas , la criba de Legendre , llamada así por Adrien-Marie Legendre , es el método más simple de la teoría de cribas moderna . Aplica el concepto de la criba de Eratóstenes para hallar límites superiores o inferiores en el número de primos dentro de un conjunto dado de números enteros. Debido a que es una extensión simple de la idea de Eratóstenes , a veces se la denomina criba de Legendre-Eratóstenes . ^[1]

La identidad de Legendre

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 números enteros, P es un producto de primos distintos, es la función de Möbius , y es el conjunto de números enteros en A divisible por d , y S(A, P) se define como: ${\displaystyle \mu }$ ${\displaystyle A_{d}}$

${\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 sin factores comunes con P .

Nótese que en el caso más típico, A son todos los números 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 número 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}}}$

(donde denota la función de piso ). En este ejemplo, el hecho de que la identidad de Legendre se deriva de la Criba de Eratóstenes es claro: el primer término es el número de enteros por debajo de 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 mal 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 se hayan cubierto todas (donde denota el número de primos por debajo de  z ) combinaciones de primos. ${\displaystyle \lfloor X\rfloor }$ ${\displaystyle 2^{\pi (z)}}$ ${\displaystyle \pi (z)}$

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

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

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

Limitaciones

El tamiz de Legendre tiene un problema con las partes fraccionarias de los términos que se acumulan en un gran error, lo que significa que el tamiz solo proporciona límites muy débiles en la mayoría de los casos. Por esta razón, casi nunca se utiliza en la práctica, habiendo sido reemplazado por otras técnicas como el tamiz de Brun y el tamiz de Selberg . Sin embargo, dado que estos tamices más potentes son extensiones de las ideas básicas del tamiz de Legendre, es útil entender primero cómo funciona este tamiz.

Referencias

1. Iwaniec, Henryk. El tamiz de Eratóstenes-Legendre. Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 núm. 2 (1977), págs. 257–268 SEÑOR 453676