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:

${\displaystyle 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, ${\displaystyle \mu }$ é a função de Möbius, ${\displaystyle A_{d}}$ é o conjunto de inteiros em A divisível por d, e S(A, P) é definido como:

${\displaystyle 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:

${\displaystyle S(A,P)}$	${\displaystyle =\sum _{d|P}\mu (d)\left\lfloor {\frac {X}{p_{1}}}\right\rfloor }$
	${\displaystyle =[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 ${\displaystyle \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 ${\displaystyle 2^{\pi (z)}}$ (onde ${\displaystyle \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 ${\displaystyle S(A,P)}$ nestes casos especiais, podem ser usado para limitar ${\displaystyle \pi (X)}$ usando a expressão

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

a qual é uma implicação clara da definição de ${\displaystyle 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

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e