Crivello di Legendre

Template:F 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'identità di Legendre

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

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

dove $A$ è un intervallo di interi, $P$ è il prodotto di numeri primi distinti, $\mu$ è la funzione di Möbius, $A_d$ è l'insieme degli interi $A$ divisibili per $d$, e $S(A,P)$ è definito come:

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

ossia il numero degli interi in $A$ che non hanno fattori comuni con $P$.

Nella maggior parte dei casi $A$ sono tutti gli interi minori o uguali di qualche numero $X$, $P$ è il prodotto di tutti i primi minori o uguali a qualche intero $z<X$, per cui l'identità di Legendre diviene:

$S(A,P)$	$=\sum _{d|P}\mu (d)\lfloor \frac{X}{p_1}\rfloor$
	$=[X]-\sum _{p_1<z}\lfloor \frac{X}{p_1}\rfloor +\sum _{p_1<p_2<z}\lfloor \frac{X}{p_1{p}_2}\rfloor -\sum _{p_1<p_2<p_3<z}\lfloor \frac{X}{p_1{p}_2{p}_3}\rfloor +\cdots$

(dove $\lfloor x\rfloor$ denota la parte intera di $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$, 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^{\pi (z)}$ (dove $\pi (z)$ denota il numero di primi minori di $z$) combinazioni di primi sono state coperte.

Una volta che $S(A,P)$ è stato calcolato per questo caso particolare, può essere usato per ottenere un limite superiore per $\pi (X)$ usando l'espressione

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

che segue immediatamente dalla definizione di $S(A,P)$.

Problemi

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.