Crivello di Legendre

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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:

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

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

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

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

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

${\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 }$

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

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

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

che segue immediatamente dalla definizione di ${\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.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica