In quest’articolo cominceremo a entrare nel vivo della teoria dei crivelli, analizzando nel dettaglio il cosiddetto “crivello di Selberg”. Non si tratta, in realtà di un nuovo crivello (paragonabile ad esempio a quello di Eratostene); il crivello (inteso come funzione) è sempre quello generale, Selberg ne ha ottenuto una maggiorazione. In sintesi, possiamo dire che quello che viene chiamato “crivello di Selberg” è in realtà un modo di maggiorare una funzione di crivello con una funzione semplice da calcolare, composta da due termini: una stima e un termine di errore.
Il crivello di Selberg prende il nome da Atle Selberg, il matematico che assieme a Paul Erdős dimostrò il Teorema dei numeri primi per la prima volta in modo elementare, cioè utilizzando solo l’analisi reale.
Enunciato ed esempio
L’enunciato del crivello di Selberg, in forma leggermente semplificata, è il seguente:
crivello di Selberg, semplificato
Siano:
- A un insieme finito di numeri naturali
- \mathbb{P} l’insieme dei numeri primi
- z \gt 1 un numero reale
- P(z) il prodotto di tutti i numeri primi minori di z
- A_d l’insieme dei multipli di un numero naturale d presenti in A
- r(d) := |A_d| - \frac{|A|}{d}
- \omega(d) il numero di fattori primi distinti di d
Allora:
Sebbene l’enunciato sia relativamente complesso, possiamo sintetizzarlo in due semplici punti:
- È possibile approssimare la funzione di crivello S(A, \mathbb{P}, z) con una frazione data dal numero di elementi di A diviso per la somma dei primi termini della serie armonica, tutti quelli che hanno il denominatore minore di z.
- Con tale approssimazione si commette un errore che può essere al massimo una certa quantità positiva, calcolata a partire dagli interi minori di z^2 che dividono P(z) (che quindi sono il prodotto di fattori primi distinti).
Prima di procedere con la dimostrazione, ribadiamo che l’enunciato del Teorema C.4 è leggermente semplificato, nel senso che è meno generale di quanto potrebbe essere. Lo abbiamo enunciato in questo modo perché il caso generale non serve per capire la dimostrazione, ma lo vedremo al momento opportuno. Anticipiamo, comunque, che la generalizzazione consisterà nel sostituire \frac{|A|}{d} con |A| f(d) e \frac{1}{n} con f(n) (rispettivamente nella definizione di r(d) e nel denominatore della stima), dove f sarà una funzione che dovrà soddisfare opportuni requisiti.
Proviamo ad applicare il Teorema C.4 al crivello di Eratostene.
Come sappiamo, nel crivello di Eratostene si fissa un intero N \gt 1 e si pone A := \{1, 2, \ldots, N\} e z := \sqrt{N+1}. Sostituendo nella (1) e ricordando che, per un intero n, la condizione n \lt \sqrt{N+1} è equivalente a n \leq \sqrt{N}, abbiamo:
Supponiamo che N = 100. Allora abbiamo che:
- Esistono 4 primi minori o uguali di \sqrt{100} = 10: 2, 3, 5, 7.
- P(\sqrt{N + 1}) = P(\sqrt{101}) è il prodotto dei numeri primi del punto precedente, dunque P(\sqrt{N + 1}) = 2 \cdot 3 \cdot 5 \cdot 7
La stima fornota dal Teorema C.4 è:
Per calcolare il termine di errore, dobbiamo innanzitutto trovare quali sono gli interi d \leq 100 che dividono P(\sqrt{101}) = 2 \cdot 3 \cdot 5 \cdot 7, ossia che sono il prodotto di primi distinti appartenenti all’insieme \{2, 3, 5, 7\}; poi, per ciascuno di essi, dobbiamo calcolare \omega(d) e r(d). Il valore di \omega(d) si calcola immediatamente perché basta contare i fattori primi della fattorizzazione di d; per quanto riguarda r(d), invece, ricordiamo che il numero di multipli di d appartenenti ad A, ossia minori o uguali di N, è \left\lfloor \frac{N}{d} \right\rfloor. Quest’ultima è la parte intera della frazione \frac{N}{d}, che si può scrivere anche sottraendo dal numeratore il suo resto rispetto al denominatore: \left\lfloor \frac{N}{d} \right\rfloor = \frac{N - N \mathrm{\ mod\ } d}{d}, ad esempio 33 = \left\lfloor \frac{100}{3} \right\rfloor = \frac{100 - 100 \mathrm{\ mod\ } 3}{3} = \frac{100 - 1}{3} = \frac{99}{3}. Quindi:
da cui:
Gli elementi che ci servono per calcolare il termine di errore sono quindi i seguenti:
| d | |r(d)| | \omega(d) |
|---|---|---|
| 2 | 0 | 1 |
| 3 | \frac{1}{3} | 1 |
| 5 | 0 | 1 |
| 7 | \frac{2}{7} | 1 |
| 2 \cdot 3 = 6 | \frac{4}{6} | 2 |
| 2 \cdot 5 = 10 | 0 | 2 |
| 2 \cdot 7 = 14 | \frac{2}{14} | 2 |
| 3 \cdot 5 = 15 | \frac{10}{15} | 2 |
| 3 \cdot 7 = 21 | \frac{16}{21} | 2 |
| 5 \cdot 7 = 35 | \frac{30}{35} | 2 |
| 2 \cdot 3 \cdot 5 = 30 | \frac{10}{30} | 3 |
| 2 \cdot 3 \cdot 7 = 42 | \frac{16}{42} | 3 |
| 2 \cdot 5 \cdot 7 = 70 | \frac{30}{70} | 3 |
Osserviamo che, come valori di d, abbiamo tutti i divisori di 2 \cdot 3 \cdot 5 \cdot 7 = 210 tranne 3 \cdot 5 \cdot 7 = 105 e 2 \cdot 3 \cdot 5 \cdot 7 = 210, perché questi divisori sono maggiori di 100.
Ora possiamo calcolare il termine di errore:
Quindi per N = 100 la (a) diventa:
Tenendo conto che il vero valore è S(\{1, 2, \ldots, 100\}, \mathbb{P}, \sqrt{101}) = |\{p \mid 10 \lt p \leq 100\}| = 21, non possiamo certo dire di aver approssimato bene la funzione! Inoltre, il margine di errore di 60,58 che abbiamo ottenuto è ben più alto di quello che avrebbe l’approssimazione dell’articolo precedente, ossia 2^{k-1} = 2^3 = 8 (dove k = 4 perché esistono 4 primi minori o uguali di \sqrt{100}).
Possiamo quindi concludere che il crivello di Selberg è una pessima maggiorazione? Certamente no. Tutte queste evidenze riguardano il singolo esempio preso in considerazione, ma ciò che ci interessa maggiormente è sempre il comportamento asintotico. Il termine di errore del crivello di Selberg continua a essere maggiore di 2^{k-1} almeno fino a N = 1000:
Se però estendiamo il nostro campione fino a N = 3000, si nota che c’è un’inversione di tendenza nel margine di errore:
E se continuiamo fino a N = 10.000, l’andamento è ancora più evidente:
Dunque, ancora una volta, è bene ricordare che gli esempi vanno presi per quello che sono, ossia dei singoli casi. Non bisogna quindi scoraggiarsi se i risultati non sembrano promettenti, ma conviene esaminare molti esempi al fine di capire l’andamento asintotico delle funzioni che stiamo studiando (quando esso non è già noto a livello teorico).
Introduzione alla dimostrazione
La dimostrazione del crivello di Selberg è importante perché applica una serie di tecniche che possiamo definire “furbe”. In questo articolo vedremo l’inizio della dimostrazione, mentre negli articoli successivi approfondiremo alcune sue parti specifiche.
Dato che da qui in poi la teoria si fa più complessa, col rischio di perdere la percezione del significato pratico dei vari passaggi, porteremo avanti parallelamente sia la teoria che un esempio rappresentativo. Supporremo in particolare che i numeri primi utilizzati nel crivello siano 3, cioè P(z) = 2 \cdot 3 \cdot 5 (z potrebbe essere qualunque numero reale maggiore di 5 e minore o uguale a 7, per ora non è importante fissare un valore specifico).
Partiamo dalla Proprietà C.2 (Funzione di crivello con \mathcal{P} = \mathbb{P}, espressione puramente algebrica):
che non è altro che l’espressione algebrica della definizione di crivello: il conteggio degli elementi di A coprimi con P(z). Possiamo riscrivere la sommatoria come segue:
che è equivalente all’espressione precedente, perché stiamo contando 1 per gli elementi coprimi con P(z) e 0 per tutti gli altri. Ma la funzione definita per casi che compare all’interno della sommatoria, per la Proprietà N.11, può essere espressa come una sommatoria della funzione di Möbius:
Fin qui stiamo ancora calcolando il valore esatto della funzione di crivello. L’idea del crivello di Selberg consiste nel sostituire i valori della funzione \mu(d), con dei numeri reali \lambda_d, elevando la somma al quadrato, per ragioni tecniche che saranno chiare in seguito. L’approssimazione di Selberg è quindi del tipo seguente:
Ma il crivello di Selberg è un’approssimazione eccesso, quindi deve essere:
Come possiamo scegliere i \lambda_d in modo tale che questa proprietà sia soddisfatta? È abbastanza semplice: basta porre \lambda_1 = 1, mentre gli altri \lambda_d possono essere numeri reali qualsiasi.
Perché la (2) è soddisfatta per \lambda_1 = 1, indipendentemente dagli altri \lambda_d?
Distinguiamo due casi:
- Se \mathrm{MCD}(a, P(z)) = 1, l’unico divisore d comune tra a e P(z) è 1, quindi la (3) si riduce a:
\left( \lambda_1 \right)^2 \geq \mu(1)
Ma \mu(1) = 1, quindi deve essere \left( \lambda_1 \right)^2 \geq 1, da cui |\lambda_d| \geq 1. Dato che vogliamo un’approssimazione per eccesso più piccola possibile (cioè più vicina possibile al valore reale), abbiamo scelto \lambda_1 = 1 (la scelta \lambda_1 = -1 sarebbe stata equivalente). Ovviamente in questo caso gli altri \lambda_d possono essere qualsiasi, dato che non compaiono nella precedente disequazione.
- Se \mathrm{MCD}(a, P(z)) \gt 1, la parte destra della (3) è 0 per la Proprietà N.11, per cui la (2) si riduce a:
\left( \sum_{d \mid \mathrm{MCD}(a, P(z))} \lambda_d \right)^2 \geq 0
Ma sappiamo che il quadrato di un numero reale è sempre maggiore o uguale di zero, quindi in questo caso la (3) è soddisfatta qualunque siano i valori di \lambda_d (compreso \lambda_1).
Considerando entrambi i casi, possiamo concludere quindi che \lambda_1 dev’essere 1 (altrimenti il primo caso non sarebbe soddisfatto), mentre gli altri \lambda_d possono essere qualsiasi, dato che in nessuno dei due casi vi è un vincolo su di essi.
Dalla (2) e dalla (3) possiamo concludere:
A questo punto la dimostrazione si sviluppa in tre parti:
- la prima parte consiste nello scrivere diversamente la parte destra della formula (4) in modo da portarla nella forma |A| T + R, dove T rappresenta la frazione di elementi di A rimasti dopo aver applicato il crivello, e R è il termine di errore;
- la seconda parte è la scelta dei valori delle costanti \lambda_d che rendono minimo il valore di T (in modo da avere una stima più vicina possibile al valore reale);
- la terza parte consiste nel sostituire i valori di \lambda_d all’interno del termine di errore R effettuando le opportune semplificazioni.
Vedremo la prima parte nel prossimo paragrafo e le altre due parti negli articoli successivi.
Prima parte della dimostrazione: la forma |A| T + R
Questa parte della dimostrazione si articola in tre passaggi: vediamoli uno alla volta.
Primo passaggio
Il primo passaggio è il seguente:
che è conseguenza dell’uguaglianza:
La notazione è un po’ complessa, ma il concetto di base è semplice; è lo stesso concetto alla base dell’identità (a + b)^2 = (a + b)(a + b) = a \cdot a + a \cdot b + b \cdot a + b \cdot b (di solito abbreviata in a^2 + 2ab + b^2). In sostanza, elevando al quadrato una somma di n termini si ottiene una somma di n^2 termini, contenente tutti i possibili prodotti di due elementi.
Nel nostro caso, il numero di elementi della sommatoria elevata al quadrato è pari al numero di divisori di \mathrm{MCD}(a, P(z)), cioè è pari al numero di divisori comuni tra a e P(z) (ricordiamo che, per definizione, ogni divisore comune divide il massimo comun divisore). Per ognuno di questi divisori comuni d, la sommatoria comprende la corrispondente costante \lambda_d. Vediamo un esempio.
Supponiamo che P(z) = 2 \cdot 3 \cdot 5. Allora i divisori di P(z) sono 1, 2, 3, 5, 6, 10, 15 e 30, di conseguenza avremo le costanti \lambda_1, \lambda_2, \lambda_3, \lambda_5, \lambda_6, \lambda_{10}, \lambda_{15} e \lambda_{30}. La sommatoria \sum_{d \mid \mathrm{MCD}(a, P(z))} \lambda_d conterrà quindi una o più di queste costanti, a seconda di quali dei divisori di P(z) sono anche divisori di a. Per rendere più evidente questo concetto, possiamo utilizzare il simbolo
per indicare la sommatoria completa \lambda_1 + \lambda_2 + \lambda_3 + \lambda_5 + \lambda_6 + \lambda_{10} + \lambda_{15} + \lambda_{30} = \sum_{d \mid 30} \lambda_d, sostituendo nelle altre sommatorie le costanti mancanti con un asterisco. Ad esempio, se a = 1, l’unico divisore in comune con P(z) è 1 stesso, quindi utilizzeremo la notazione:
Se a = 5, \mathrm{MCD}(a, P(z)) = 5 e i divisori in comune sono 1 e 5, per cui utilizzeremo la notazione:
Se a = 12, \mathrm{MCD}(a, P(z)) = 6 e i divisori in comune sono 1, 2, 3 e 6, per cui utilizzeremo la notazione:
e così via.
Per a = 6 la sommatoria è la stessa di quella per a = 12, dato che il massimo comun divisore con P(z) = 30 è sempre 6 e quindi anche i divisori comuni con P(z) sono sempre gli stessi, ossia 1, 2, 3 e 6.
Questa notazione può essere facilmente estesa per rappresentare il quadrato della sommatoria \sum_{d \mid \mathrm{MCD}(a, P(z))} \lambda_d. Possiamo infatti costruire la seguente tabella moltiplicativa:
| \cdot | \mathbf{\lambda_1} | \mathbf{\lambda_2} | \mathbf{\lambda_3} | \mathbf{\lambda_6} | \mathbf{\lambda_{10}} | \mathbf{\lambda_{15}} | \mathbf{\lambda_{30}} |
|---|---|---|---|---|---|---|---|
| \mathbf{\lambda_1} | \lambda_1 \lambda_1 | \lambda_1 \lambda_2 | \lambda_1 \lambda_3 | \lambda_1 \lambda_6 | \lambda_1 \lambda_{10} | \lambda_1 \lambda_{15} | \lambda_1 \lambda_{30} |
| \mathbf{\lambda_2} | \lambda_2 \lambda_1 | \lambda_2 \lambda_2 | \lambda_2 \lambda_3 | \lambda_2 \lambda_6 | \lambda_2 \lambda_{10} | \lambda_2 \lambda_{15} | \lambda_2 \lambda_{30} |
| \mathbf{\lambda_3} | \lambda_3 \lambda_1 | \lambda_3 \lambda_2 | \lambda_3 \lambda_3 | \lambda_3 \lambda_6 | \lambda_3 \lambda_{10} | \lambda_3 \lambda_{15} | \lambda_3 \lambda_{30} |
| \mathbf{\lambda_5} | \lambda_5 \lambda_1 | \lambda_5 \lambda_2 | \lambda_5 \lambda_3 | \lambda_5 \lambda_6 | \lambda_5 \lambda_{10} | \lambda_5 \lambda_{15} | \lambda_5 \lambda_{30} |
| \mathbf{\lambda_6} | \lambda_6 \lambda_1 | \lambda_6 \lambda_2 | \lambda_6 \lambda_3 | \lambda_6 \lambda_6 | \lambda_6 \lambda_{10} | \lambda_6 \lambda_{15} | \lambda_6 \lambda_{30} |
| \mathbf{\lambda_{10}} | \lambda_{10} \lambda_1 | \lambda_{10} \lambda_2 | \lambda_{10} \lambda_3 | \lambda_{10} \lambda_6 | \lambda_{10} \lambda_{10} | \lambda_{10} \lambda_{15} | \lambda_{10} \lambda_{30} |
| \mathbf{\lambda_{15}} | \lambda_{15} \lambda_1 | \lambda_{15} \lambda_2 | \lambda_{15} \lambda_3 | \lambda_{15} \lambda_6 | \lambda_{15} \lambda_{10} | \lambda_{15} \lambda_{15} | \lambda_{15} \lambda_{30} |
| \mathbf{\lambda_{30}} | \lambda_{30} \lambda_1 | \lambda_{30} \lambda_2 | \lambda_{30} \lambda_3 | \lambda_{30} \lambda_6 | \lambda_{30} \lambda_{10} | \lambda_{30} \lambda_{15} | \lambda_{30} \lambda_{30} |
Come si può facilmente verificare, la somma degli elementi della tabella (intestazioni escluse) è il risultato dell’operazione (\lambda_1 + \lambda_2 + \lambda_3 + \lambda_5 + \lambda_6 + \lambda_{10} + \lambda_{15} + \lambda_{30})^2 = \left( \sum_{d \mid 30} \lambda_d \right)^2 = \sum_{d_1 \mid 30} \sum_{d_2 \mid 30} \lambda_{d_1} \lambda_{d_2}. Possiamo quindi rappresentare questa doppia sommatoria col simbolo:
Nei quadrati delle altre sommatorie sostituiremo i termini mancanti con degli asterischi. Ad esempio, per a = 1:
Per a = 5:
Per a = 6 o a = 12:
Secondo passaggio
Il secondo passaggio è il seguente:
Nel passaggio precedente abbiamo considerato la doppia sommatoria
come la somma degli elementi di una matrice avente elementi del tipo \lambda_{d_1} \lambda_{d_2}, dove d_1 e d_2 sono divisori comuni tra a e P(z). Fissato un valore di a, si ottiene quindi una certa matrice, che chiameremo M_{\mathrm{MCD}(a, P(z))}, avente righe e colonne numerate coi divisori di P(z), nella quale sono riempite solo le celle la cui riga e la cui colonna sono divisori di \mathrm{MCD}(a, P(z)).
Vediamo quali sono le matrici M_{\mathrm{MCD}(a, P(z))} supponendo che P(z) = 2 \cdot 3 \cdot 5 = 30. Si avrà una matrice diversa per ogni possibile valore di \mathrm{MCD}(a, 30). Ma i possibili valori di \mathrm{MCD}(a, 30) non sono altro che i divisori di 30 (la spiegazione è semplice: essendo \mathrm{MCD}(a, 30) un divisore comune tra a e 30, in particolare è un divisore di 30; inoltre ogni divisore di 30 è il massimo comun divisore tra se stesso e 30, quindi è uno dei possibili valori di \mathrm{MCD}(a, 30)). Essendo 30 il prodotto di 2, 3 e 5, i divisori di 30 sono il prodotto di zero o più fattori primi scelti dall’insieme \{2, 3, 5\}, ossia 1 (prodotto di 0 fattori primi), 2, 3 e 5 (prodotti di 1 fattore primo), 6, 10 e 15 (prodotto di due fattori primi) e 30 (prodotto di tutti e tre i fattori primi). Si avranno quindi i seguenti 8 casi:
- \mathrm{MCD}(a, 30) = 1 (a non è divisibile né per 2, né per 3, né per 5). In questo caso l’unico divisore comune è 1, quindi l’unica cella piena è quella che ha riga 1 e colonna 1:
M_1 := \left( \begin{matrix} \lambda_1 \lambda_1 & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix} \right)
- \mathrm{MCD}(a, 30) = 2 (a è divisibile per 2, non è divisibile né per 3, né per 5). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 2, ossia 1 oppure 2:
M_2 := \left( \begin{matrix} \lambda_1 \lambda_1 & \lambda_1 \lambda_2 & * & * & * & * & * & * \\ \lambda_2 \lambda_1 & \lambda_2 \lambda_2 & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 3 (a è divisibile per 3, non è divisibile né per 2, né per 5). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 3, ossia 1 oppure 3:
M_3 := \left( \begin{matrix} \lambda_1 \lambda_1 & * & \lambda_1 \lambda_3 & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ \lambda_3 \lambda_1 & * & \lambda_3 \lambda_3 & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 5 (a è divisibile per 5, non è divisibile né per 2, né per 3). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 5, ossia 1 oppure 5:
M_5 := \left( \begin{matrix} \lambda_1 \lambda_1 & * & * & \lambda_1 \lambda_5 & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ \lambda_5 \lambda_1 & * & * & \lambda_5 \lambda_5 & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 6 (a è divisibile per 2 e per 3, ma non per 5). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 6, ossia 1, 2, 3 o 6:
M_6 := \left( \begin{matrix} \lambda_1 \lambda_1 & \lambda_1 \lambda_2 & \lambda_1 \lambda_3 & * & \lambda_1 \lambda_6 & * & * & * \\ \lambda_2 \lambda_1 & \lambda_2 \lambda_2 & \lambda_2 \lambda_3 & * & \lambda_2 \lambda_6 & * & * & * \\ \lambda_3 \lambda_1 & \lambda_3 \lambda_2 & \lambda_3 \lambda_3 & * & \lambda_3 \lambda_6 & * & * & * \\ * & * & * & * & * & * & * & * \\ \lambda_6 \lambda_1 & \lambda_6 \lambda_2 & \lambda_6 \lambda_3 & * & \lambda_6 \lambda_6 & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 10 (a è divisibile per 2 e per 5, ma non per 3). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 10, ossia 1, 2, 5 o 10:
M_{10} := \left(\begin{matrix} \lambda_1 \lambda_1 & \lambda_1 \lambda_2 & * & \lambda_1 \lambda_5 & * & \lambda_1 \lambda_{10} & * & * \\ \lambda_2 \lambda_1 & \lambda_2 \lambda_2 & * & \lambda_2 \lambda_5 & * & \lambda_2 \lambda_{10} & * & * \\ \lambda_3 \lambda_1 & \lambda_3 \lambda_2 & * & \lambda_3 \lambda_5 & * & \lambda_3 \lambda_{10} & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ \lambda_{10} \lambda_1 & \lambda_{10} \lambda_2 & * & \lambda_{10} \lambda_5 & * & \lambda_{10} \lambda_{10} & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 15 (a è divisibile per 3 e per 5, ma non per 2). In questo caso le celle piene sono quelle la cui riga e la cui colonna sono divisori di 15, ossia 1, 3, 5 o 15:
M_{15} := \left( \begin{matrix} \lambda_1 \lambda_1 & * & \lambda_1 \lambda_3 & \lambda_1 \lambda_5 & * & * & \lambda_1 \lambda_{15} & * \\ * & * & * & * & * & * & * & * \\ \lambda_3 \lambda_1 & * & \lambda_3 \lambda_3 & \lambda_3 \lambda_5 & * & * & \lambda_3 \lambda_{15} & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ * & * & * & * & * & * & * & * \\ \lambda_{15} \lambda_1 & * & \lambda_{15} \lambda_3 & \lambda_{15} \lambda_5 & * & * & \lambda_{15} \lambda_{15} & * \\ * & * & * & * & * & * & * & * \end{matrix}\right)
- \mathrm{MCD}(a, 30) = 30 (a è divisibile per 2, per 3 e per 5). In questo caso abbiamo la matrice completa, perché tutte le righe e tutte le colonne sono divisori di 30:
M_{30} := \left( \begin{matrix} \lambda_1 \lambda_1 & \lambda_1 \lambda_2 & \lambda_1 \lambda_3 & \lambda_1 \lambda_5 & \lambda_1 \lambda_6 & \lambda_1 \lambda_{10} & \lambda_1 \lambda_{15} & \lambda_1 \lambda_{30} \\ \lambda_2 \lambda_1 & \lambda_2 \lambda_2 & \lambda_2 \lambda_3 & \lambda_2 \lambda_5 & \lambda_2 \lambda_6 & \lambda_2 \lambda_{10} & \lambda_2 \lambda_{15} & \lambda_2 \lambda_{30} \\ \lambda_3 \lambda_1 & \lambda_3 \lambda_2 & \lambda_3 \lambda_3 & \lambda_3 \lambda_5 & \lambda_3 \lambda_6 & \lambda_3 \lambda_{10} & \lambda_3 \lambda_{15} & \lambda_3 \lambda_{30} \\ \lambda_5 \lambda_1 & \lambda_5 \lambda_2 & \lambda_5 \lambda_3 & \lambda_5 \lambda_5 & \lambda_5 \lambda_6 & \lambda_5 \lambda_{10} & \lambda_5 \lambda_{15} & \lambda_5 \lambda_{30} \\ \lambda_6 \lambda_1 & \lambda_6 \lambda_2 & \lambda_6 \lambda_3 & \lambda_6 \lambda_5 & \lambda_6 \lambda_6 & \lambda_6 \lambda_{10} & \lambda_6 \lambda_{15} & \lambda_6 \lambda_{30} \\ \lambda_{10} \lambda_1 & \lambda_{10} \lambda_2 & \lambda_{10} \lambda_3 & \lambda_{10} \lambda_5 & \lambda_{10} \lambda_6 & \lambda_{10} \lambda_{10} & \lambda_{10} \lambda_{15} & \lambda_{10} \lambda_{30} \\ \lambda_{15} \lambda_1 & \lambda_{15} \lambda_2 & \lambda_{15} \lambda_3 & \lambda_{15} \lambda_5 & \lambda_{15} \lambda_6 & \lambda_{15} \lambda_{10} & \lambda_{15} \lambda_{15} & \lambda_{15} \lambda_{30} \\ \lambda_{30} \lambda_1 & \lambda_{30} \lambda_2 & \lambda_{30} \lambda_3 & \lambda_{30} \lambda_5 & \lambda_{30} \lambda_6 & \lambda_{30} \lambda_{10} & \lambda_{30} \lambda_{15} & \lambda_{30} \lambda_{30} \end{matrix}\right)
Come si può facilmente verificare, la somma degli elementi della matrice M_d, per d \in \{1, 2, 3, 5, 6, 10, 15, 30\}, è:
La (5) ci dice che dobbiamo sommare le matrici di tutti gli a:
Per a = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \ldots, essendo rispettivamente \mathrm{MCD}(a, 30) = 1, 2, 3, 2, 5, 6, 1, 2, 3, 10, \ldots, la sommatoria (b) diventa:
Come abbiamo visto, tutti gli elementi delle matrici M_{\mathrm{MCD}(a, P(z))} sono del tipo \lambda_{d_1} \lambda_{d_2}, con d_1, d_2 divisori di P(z); non esistono elementi di tipo diverso. Quest’osservazione suggerisce un modo alternativo di sommare tutte le matrici: invece di partire dai vari a e sommare le matrici una per volta, possiamo partire dai possibili elementi e moltiplicare ciascuno di essi per il numero di matrici in cui è presente:
In questo modo stiamo comunque sommando tutti gli elementi di tutte le matrici, perché stiamo considerando tutti i possibili elementi e ciascuno di essi è moltiplicato per il numero di matrici in cui è presente. Quindi il risultato finale deve essere lo stesso di prima:
Si tratta ora di stabilire, dati due divisori di P(z), d_1 e d_2, in quante matrici è presente l’elemento \lambda_{d_1} \lambda_{d_2}. Potrebbe sembrare una questione complicata, ma la risposta è molto semplice:
Cioè l’elemento \lambda_{d_1} \lambda_{d_2} compare in tutte e sole le matrici M_{\mathrm{MCD}(a, P(z))} dove a è multiplo sia di d_1 che di d_2. Vediamo perché:
- Se a è multiplo sia di d_1 che di d_2, essendo anche per ipotesi P(z) multiplo di entrambi, d_1 e d_2 sono divisori comuni tra a e P(z), dunque dividono \mathrm{MCD}(a, P(z)). Ma gli elementi della matrice M_{\mathrm{MCD}(a, P(z))} sono proprio quelli che hanno come numero di riga e di colonna dei divisori di \mathrm{MCD}(a, P(z)); uno di essi sarà quindi \lambda_{d_1} \lambda_{d_2}. Questo dimostra l’implicazione verso sinistra della e).
- Il ragionamento precedente si può ripetere al contrario: se l’elemento \lambda_{d_1} \lambda_{d_2} è presente in una matrice M_{\mathrm{MCD}(a, P(z))}, significa che d_1 e d_2 dividono \mathrm{MCD}(a, P(z)); ma quest’ultimo è a sua volta un divisore di a, quindi d_1 e d_2 dividono a. Questo dimostra l’implicazione verso destra.
Supponendo ancora che P(z) = 2 \cdot 3 \cdot 5 = 30, prendiamo in esame tre casi:
- d_1 = d_2 = 1.
In questo caso qualsiasi a è multiplo sia di d_1 che di d_2. Quindi, per la (e), l’elemento \lambda_{d_1} \lambda_{d_2} compare in tutte le matrici. Possiamo trovare conferma nel primo esempio: in tutte le 8 possibili matrici, la prima cella in alto a sinistra è sempre piena, e vi si trova l’elemento \lambda_1 \lambda_1. - d_1 = d_2 = 2.
In questo caso, per la (e), l’elemento \lambda_{d_1} \lambda_{d_2} compare in tutte e sole le matrici M_{\mathrm{MCD}(a, 30)} dove a è pari. Consideriamo la sommatoria (c): le matrici che troviamo quando a = 2, 4, 6, 8, 10 sono rispettivamente M_2, M_2, M_6, M_2, M_{10} ed esse, come si può verificare nel primo esempio, contengono tutte l’elemento \lambda_2 \lambda_2; al contrario, le matrici che troviamo quando a = 1, 3, 5, 7, 9 sono rispettivamente M_1, M_3, M_5, M_1, M_3, e nessuna di queste contiene l’elemento \lambda_2 \lambda_2. - d_1 = 2, d_2 = 3.
In questo caso, per la (e), l’elemento \lambda_{d_1} \lambda_{d_2} compare in tutte e sole le matrici M_{\mathrm{MCD}(a, 30)} dove a è multiplo di 6. Nella sommatoria (c), l’unico valore di a che è multiplo di 6 è 6 stesso, e la matrice corrispondente, la sesta della sommatoria, è M_6. Come si può facilmente verificare, M_6 è l’unica tra le matrici della sommatoria (c) che contiene l’elemento \lambda_2 \lambda_3. Se continuassimo la sommatoria, otterremmo la stessa matrice anche per a = 12, 18, 24, perché il massimo comun divisore tra questi numeri e 30 è sempre 6. Per a = 30 avremmo invece la matrice M_{30}, che ovviamente contiene anch’essa l’elemento, essendo quella completa.
A questo punto possiamo trarre le conclusioni:
dove l’ultimo passaggio utilizza la notazione introdotta nell’enunciato del crivello di Selberg (Teorema C.4).
Sostituendo nella (d), si ottiene la (6).
Terzo passaggio
Il terzo passaggio è il seguente:
Lo scopo di questo passaggio è mettere in evidenza |A|. Utilizzando le notazioni del Teorema C.4, abbiamo che:
In quest’uguaglianza ci sono tre quantità importanti:
- |A_d| è il numero di multipli di d in A; dato che A contiene tutti gli interi positivi da 1 a un certo numero, |A_d| è uguale a \left\lfloor \frac{|A|}{d} \right\rfloor, la parte intera della divisione del numero di elementi di A (che coincide col suo più grande elemento) per d.
- \frac{|A|}{d} è un’approssimazione del numero di multipli di d in A: invece di prendere la parte intera della divisione, qui stiamo prendendo la frazione così com’è.
- r(d) è la differenza tra le quantità precedenti, ossia indica di quanto ci si sbaglia approssimando |A_d| con \frac{|A|}{d}. In maniera forse un po’ controintuitiva, se r(d) \neq 0 il segno è negativo perché |A_d| \leq \frac{|A|}{d}, dato che la parte intera di una frazione è sempre minore o uguale della frazione stessa. Il segno ha comunque poca importanza, perché ciò che interessa maggiormente è il valore assoluto di r(d).
Se A = \{1, 2, 3, \ldots, 100\} e d = 3, abbiamo che:
- |A_3| = \left\lfloor \frac{|A|}{3} \right\rfloor = \left\lfloor \frac{100}{3} \right\rfloor = 33, perché ci sono 33 multipli di 3 minori o uguali a 100;
- \frac{|A|}{3} = \frac{100}{3} = 33,333\ldots è un’approssimazione del numero precedente, senza usare la parte intera;
- r(3) = |A_3| - \frac{|A|}{3} = 33 - \frac{100}{3} = \frac{99 - 100}{3} = -\frac{1}{3} = -0,333\ldots è la differenza tra le quantità precedenti, col segno negativo.
Dalla (f), sostituendo d := \mathrm{mcm}(d_1 d_2), si ottiene:
da cui:
Questo passaggio consente di ottenere la forma |A| T + R, ponendo:
Per cui, unendo le formule dalla (4) alla (7), si ottiene:
Da questa disuguaglianza è chiaro che T è la quantità da minimizzare per ottenere una stima |A| T il più possibile vicina al valore esatto, mentre R rappresenta il relativo errore.