Crivello di Legendre

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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)\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_1p_2}\right\rfloor - \sum_{p_1 < p_2 < p_3 < z}
\left\lfloor\frac{X}{p_1p_2p_3}\right\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) \geq \pi(X) - \pi(z) - 1

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

Problemi[modifica | modifica wikitesto]

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.

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