Crivello di Legendre

In matematica, il crivello di Legendre è il metodo più semplice nella moderna teoria dei crivelli. Applica il concetto del crivello di Eratostene per trovare limiti inferiori e superiori alla stima della quantità di numeri primi entro un dato intervallo di interi. Poiché è una semplice estensione dell’idea di Eratostene, è a volte citato come crivello di Legendre-Eratostene.

L’idea base del metodo è espressa da questa identità, detta a volte identità di Legendre:

dove





A




{\displaystyle A}


è un intervallo di interi,





P




{\displaystyle P}


è il prodotto di numeri primi distinti,





μ





{\displaystyle \mu }


è la funzione di Möbius,






A



d






{\displaystyle A_{d}}


è l’insieme degli interi





A




{\displaystyle A}


divisibili per





d




{\displaystyle d}


, e





S


(


A


,


P


)




{\displaystyle S(A,P)}


è definito come:

ossia il numero degli interi in





A




{\displaystyle A}


che non hanno fattori comuni con





P




{\displaystyle P}


.

Nella maggior parte dei casi





A




{\displaystyle A}


sono tutti gli interi minori o uguali di qualche numero





X




{\displaystyle X}


,





P




{\displaystyle P}


è il prodotto di tutti i primi minori o uguali a qualche intero





z


<


X




{\displaystyle z<X}


, per cui l’identità di Legendre diviene:

(dove









x








{\displaystyle \lfloor x\rfloor }


denota la parte intera di





x




{\displaystyle x}


). In questo esempio il fatto che l’identità di Legendre sia derivata dal crivello di Eratostene è chiaro: il primo termine è il numero di interi minore di





X




{\displaystyle X}


, il secondo rimuove i multipli di tutti i primi, il terzo recupera i prodotti di due primi (che sono stati scartati per errore) e così via finché tutte le






2



π



(


z


)






{\displaystyle 2^{\pi (z)}}


(dove





π



(


z


)




{\displaystyle \pi (z)}


denota il numero di primi minori di





z




{\displaystyle z}


) combinazioni di primi sono state coperte.

Una volta che





S


(


A


,


P


)




{\displaystyle S(A,P)}


è stato calcolato per questo caso particolare, può essere usato per ottenere un limite superiore per





π



(


X


)




{\displaystyle \pi (X)}


usando l’espressione

che segue immediatamente dalla definizione di





S


(


A


,


P


)




{\displaystyle S(A,P)}


.

Il crivello di Legendre non tratta in maniera molto efficace le parti frazionarie dei termini, che si accumulano formando un errore abbastanza grande; questo implica che il crivello stabilisce limiti molto deboli nella maggior parte dei casi. Per questa ragione è stato ormai soppiantato da altre tecniche come il crivello di Brun e il crivello di Selberg, e non viene quasi mai usato in pratica. Tuttavia anche i crivelli più potenti sono sempre basati sulla stessa idea, per cui è utile capire il funzionamento del crivello di Legendre prima di studiare gli altri.