Crivo de Legendre

Em Matemática, o crivo de Legendre é o mais simples método na teoria dos crivos. Este aplica o conceito do crivo de Eratóstenes para encontrar estimativas superiores e inferiores ao número de primos dado um conjunto de inteiros. Como é uma simples extensão da ideia usada no crivo de Eratostenes, este método de crivo é também chamado por vezes crivo de Eratóstenes-Legendre.

Identidade de Legendre

A ideia central do método é expressada pela seguinte identidade, algumas vezes referida como Identidade de Legendre:

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

Onde A é um conjunto de inteiros, P é um produto de primos distintos, $\mu$ é a função de Möbius, $A_{d}$ é o conjunto de inteiros em A divisível por d, e S(A, P) é definido como:

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

Portanto S(A,P) é a quantidade de números em A sem fatores comuns a P.

Nota-se que em o caso mais típico, A é o conjunto de todos os inteiros menores ou iguais a um número real X, P é o produto de todos os primos menores ou iguais a algum inteiro z < X, assumindo isto, a identidade de Legendre ficaria desta 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_{1}p_{2}}}\right\rfloor -\sum _{p_{1}<p_{2}<p_{3}<z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots$

(onde $\lfloor X\rfloor$ é a função parte inteira). Neste exemplo, o fato de que o crivo de Legendre se derive do crivo de Eratostenes é evidenciado: a primeira parcial é o número de inteiros menores que X, a segunda parcial remove os múltiplos de todos os primos, a terceira acrescenta os múltiplos de dois primos (os quais estão sendo "descontados" porque foram "riscados duas vezes"), e assim sucessivamente todas as $2^{\pi (z)}$ (onde $\pi (z)$ é o número de primos menores que z) combinações de primos são consideradas pelo crivo de Legendre. Entende-se ainda que dado um limite no conjunto, a última parcial será a final.

Uma vez tendo sido calculados $S(A,P)$ nestes casos especiais, podem ser usado para limitar $\pi (X)$ usando a expressão

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

a qual é uma implicação clara da definição de $S(A,P)$.

Problemas

Desafortunadamente, o crivo de Legendre possui um problema com a parte fracionária das diferentes parciais, as quais acumulam-se em uma parcial de erro (isto é, parciais em notação O) demasiado grande, a qual diz que o crivo de Legendre dá limites ruins em muitos casos. Por esta razão, este crivo nunca é usado na prática, sendo sempre melhorado por outras técnicas de crivagem tais como a do crivo de Brun e a do crivo de Selberg. Contudo, dado que estes crivos mais poderosos são extensões das ideias básicas do crivo de Legendre, este método de crivagem torna-se útil para entender como funcionam os crivos.

Veja também

• Crivo de Eratóstenes
• Crivo de Selberg
• Número primo
• Teoria dos crivos