Come abbiamo visto, nella formula del crivello di Selberg compaiono dei parametri \lambda_d, che vengono utilizzati sia nella stima della funzione di crivello che nel relativo termine di errore. In questo articolo calcoleremo questi parametri in modo da ottenere una stima più bassa possibile.
Nell’articolo precedente abbiamo visto che, se A è un insieme finito di numeri naturali, z \gt 1 è un numero reale e P(z) è il prodotto dei numeri primi minori di z, allora:
S(A, \mathbb{P}, z) \leq |A| T + R
dove:
T := \sum_{d_1, d_2 \mid P(z)} \frac{\lambda_{d_1} \lambda_{d_2}}{\mathrm{mcm}(d_1, d_2)} \tag{1}
Ricordiamo che i \lambda_d (dove d rappresenta un generico divisore di P(z)) sono numeri reali che possono essere scelti a piacimento, con l’unico vincolo che \lambda_1 = 1. In questo articolo ci concentreremo sulla formula (1) e calcoleremo quali valori dovrebbero avere i \lambda_d per fare in modo che la sommatoria T sia più bassa possibile. Il calcolo si può strutturare nei passi che analizzeremo nel seguito.
Passo 1: dal minimo comune multiplo al massimo comun divisore
Il minimo comune multiplo risulta un po’ fastidioso in teoria dei numeri, perché quasi tutte le formule ragionano in termini di divisori piuttosto che di multipli: si tratta di una scelta puramente convenzionale alla quale però conviene adeguarsi. Trasformiamo il minimo comune multiplo nel massimo comun divisore mediante la nota proprietà \mathrm{mcm}(d_1, d_2) = \frac{d_1 d_2}{\mathrm{MCD}(d_1, d_2)}, applicando la quale dalla formula (1) si ottiene:
Passo 2: introduzione dei divisori del massimo comun divisore, mediante la formula di inversione di Möbius
A questo punto introduciamo un ulteriore livello di divisori mediante la formula di inversione di Möbius. Applicando la Proprietà N.18 (compresa l’Osservazione che la segue) con n := \mathrm{MCD}(d_1, d_2) e f := \mathrm{id} (funzione identità f(x) = x), otteniamo:
Supponiamo che P(z) = 2 \cdot 3 \cdot 5 = 30 e calcoliamo i possibili valori di \phi(d). A tal proposito bisogna osservare che d è un divisore di \mathrm{MCD}(d_1, d_2), che a sua volta è un divisore di d_1 e d_2 i quali a loro volta sono divisori di P(z); quindi, per transitività, anche d è un divisore di P(z). Per essere certi di calcolare tutti i valori possibili, calcoliamo allora \phi(d) per tutti i divisori di 30:
Abbiamo chiamato \phi questa funzione perché, per gli esempi che ci interessano, coincide con la funzione di Eulero, che di solito viene indicata con lo stesso simbolo. In generale le due funzioni coincidono su tutti i numeri privi di quadrati, ossia che sono il prodotto di fattori primi distinti. Questa coincidenza è abbastanza sorprendente, dato che le due funzioni sono definite in due modi molto diversi.
Passo 3: raccogliere i valori di \phi(d) ripetuti
Nella (4), si può osservare che più coppie di interi d_1 e d_2, divisori di P(z), possono avere lo stesso massimo comun divisore; in tal caso i divisori d del massimo comun divisore saranno gli stessi, e quindi i valori di \phi(d) della sommatoria interna saranno ripetuti per ciascuna coppia. Ad esempio, se P(z) = 2 \cdot 3 \cdot 5, il valore \phi(2) si avrà sia con la coppia (d_1, d_2) = (2, 2) che con la coppia (d_1, d_2) = (10, 6), perché entrambe le coppie di numeri hanno minimo comune multiplo pari a 2. Più in generale, \phi(2) si ripeterà per tutte le coppie (d_1, d_2) che hanno come massimo comun divisore un multiplo di 2, come si può vedere dalla sommatoria interna sostituendo d = 2.
Raccogliendo questi valori di \phi(d) ripetuti, si ottiene:
T = \sum_{d \mid P(z)} \phi(d) \sum_{\substack{d_1, d_2 \mid P(z) \\ d \mid \mathrm{MCD}(d_1, d_2)}} \frac{\lambda_{d_1} \lambda_{d_2}}{d_1 d_2} \tag{5}
Supponiamo che P(z) = 2 \cdot 3. Allora la formula (4) si sviluppa come segue:
Osserviamo che \phi(1) è moltiplicato per tutti i termini \frac{\lambda_{d_1} \lambda_{d_2}}{d_1 d_2}, perché 1 \mid \mathrm{MCD}(d_1, d_2) qualunque siano d_1 e d_2, mentre, all’opposto, \phi(6) compare solo una volta. Raccogliendo \phi(1), \phi(2), \phi(3) e \phi(6), si ottiene:
Il motivo sta nel fatto che la condizione d \mid \mathrm{MCD}(d_1, d_2) è equivalente a d \mid d_1 \land d \mid d_2, dove abbiamo usato il simbolo \land logico per indicare che entrambe le condizioni devono essere soddisfatte. Infatti, per definizione di massimo comun divisore, tutti i divisori del massimo comun divisore tra due numeri dividono i numeri stessi e, viceversa, due numeri che li dividono entrambi sono divisori comuni, quindi divisori del massimo divisore comune. Quindi la parte sinistra della (6) si può riscrivere come:
\sum_{\substack{d_1, d_2 \mid P(z) \\ d \mid d_1 \land d \mid d_2}} \frac{\lambda_{d_1} \lambda_{d_2}}{d_1 d_2}
che a sua volta si può scrivere diversamente come segue:
Da quest’ultima sommatoria si può ottenere la parte destra della (6) mediante le stesse considerazioni del “primo passaggio” (formula 5) dell’articolo precedente.
Riprendiamo l’esempio precedente, in cui P(z) = 2 \cdot 3 e quindi d \mid P(z) \Leftrightarrow d \mid 6 \Leftrightarrow d \in \{1, 2, 3, 6\}. Analizziamo i singoli casi.
Dalla condizione 6 \mid \mathrm{MCD}(d_1, d_2) segue che d_1 e d_2 sono multipli di 6, ma per la condizione d_1, d_2 \mid 6 essi dividono 6, per cui deve essere d_1 = d_2 = 6. Quindi:
Dalla condizione 3 \mid \mathrm{MCD}(d_1, d_2) segue che d_1 e d_2 sono multipli di 3, ma per la condizione d_1, d_2 \mid 6 essi dividono 6, quindi ciascuno di essi può essere o 3 o 6. Quindi:
La condizione 1 \mid \mathrm{MCD}(d_1, d_2) è sempre vera, perciò questa condizione non impone nessuna ulteriore restrizione su d_1 e d_2, che in base alla condizione d_1, d_2 \mid 6 possono essere 1, 2, 3 oppure 6. Quindi:
Questa espressione ci serve per minimizzare T, infatti a questo punto possiamo procedere in due fasi:
Trovare i valori di w_d che minimizzano T nella formula (9)
Calcolare i valori di \lambda_d partendo dai valori di w_d, utilizzando la (8)
Saranno questi i passi successivi.
Vediamo in modo più esplicito la formula (8), supponendo che P(z) = 2 \cdot 3 \cdot 5. La variabile d, come si evince dalla formula (7), è un divisore di P(z), quindi i possibili w_d sono w_1, w_2, w_3, w_5, w_6, w_{10}, w_{15}, w_{30}. Vediamoli uno per volta:
Per motivi che saranno chiari tra poco, analizziamo i due passi rimanenti in ordine inverso, cominciando dal secondo. Chiediamoci quindi: come potremo calcolare i valori di \lambda_d, una volta che avremo calcolato quelli di w_d?
Vediamo un esempio.
Come abbiamo visto nell’esempio precedente, la formula (8) corrisponde al seguente sistema di equazioni:
Supponendo di aver già calcolato i w_d, abbiamo quindi un sistema di 8 equazioni nelle 8 incognite \lambda_1, \lambda_2, \lambda_3, \lambda_5, \lambda_6, \lambda_{10}, \lambda_{15}, \lambda_{30}. Potremmo risolverlo con qualunque metodo risolutivo generale, ma in questo caso particolare esiste un metodo più semplice.
Per prima cosa, dall’ultima equazione è possibile ricavare direttamente \lambda_{30} = 30 \cdot w_{30}.
Per calcolare \lambda_{15} invece possiamo partire da w_{15} e procedere in questo modo:
Analogamente si possono calcolare \lambda_2 e \lambda_3.
Il calcolo di \lambda_1 è ancora più complesso; infatti, come si può verificare, la formula finale è la seguente:
In generale il calcolo di \lambda_d avviene secondo la seguente procedura:
Si comincia da w_d
Si sommano/sottraggono tutti i w_{d^{\prime}} dove d^{\prime} è multiplo di d
Si moltiplica tutto per d
Restano da determinare i segni dei w_{d^{\prime}}. Per poterli visualizzare utilizziamo il diagramma di Hasse, mediante cui si possono rappresentare tutti i divisori di un dato numero, in questo caso P(z) = 30:
Figura 1: il diagramma di Hasse del numero 30
Gli indici d^{\prime} dei w_{d^{\prime}} da sommare/sottrarre per ottenere \lambda_d corrispondono a tutti i numeri raggiungibili da d nel diagramma di Hasse, andando verso l’alto. Ad esempio, abbiamo visto che la formula per d = 5 è 5 \left( w_5 - w_{10} - w_{15} + w_{30} \right), e i numeri raggiungibili da 5 andando verso l’alto sono gli stessi indici che compaiono nella formula:
Figura 2: il diagramma di Hasse del numero 30, evidenziando i multipli di 5
Una volta individuati i w_{d^{\prime}}, i segni seguono la seguente regola:
Il segno di w_{d^{\prime}} è positivo se d^{\prime} è raggiungibile da d in un numero pari di passaggi
Il segno di w_{d^{\prime}} è negativo se d^{\prime} è raggiungibile da d in un numero dispari di passaggi
Ad esempio, per d = 5 i segni sono i seguenti:
Figura 3: il diagramma di Hasse del numero 30, evidenziando i multipli di 5 col segno che essi hanno nella formula di inversione duale di Möbius
Infatti:
5 è raggiungibile da 5 in 0 passaggi; 0 è un numero pari e quindi w_5 ha segno positivo.
10 e 15 sono raggiungibili da 5 in 1 passaggio; 1 è un numero dispari e quindi w_{10} e w_{15} hanno segno negativo.
30 è raggiungibile da 5 in 2 passaggi; 2 è un numero pari e quindi w_{30} ha segno positivo. Osserviamo che 30 è raggiungibile da 5 tramite due percorsi diversi ma entrambi composti di due passaggi, quindi il segno non dipende dal percorso considerato; questa è una proprietà generale dei diagrammi di Hasse che consente di non rendere ambiguo il calcolo del segno.
Infatti \frac{d^{\prime}}{d} ha tanti fattori primi distinti quanti sono i passaggi che separano d e d^{\prime} nel diagramma di Hasse (dato che ogni passaggio corrisponde alla moltiplicazione per un fattore primo diverso); inoltre la funzione \mu restituisce 1 quando questo numero è pari, -1 quando è dispari.
Partendo dall’esempio e utilizzando il generico P(z) al posto di 30, si ottiene la formula:
In cosa consiste la formula di inversione duale di Möbius e come si applica per dimostrare la (10)?
Riportiamo per comodità l’enunciato della formula di inversione duale di Möbius (seguendo il link precedente si possono trovare anche la dimostrazione e un esempio):
Formula di inversione duale di Möbius
Sia n un numero naturale positivo e sia f una funzione definita sui divisori di n.
Sia g la seguente funzione definita sui divisori di n:
In questo modo g(d) = \sum_{d \mid d^{\prime} \mid n} f(d^{\prime}) = \sum_{d \mid d^{\prime} \mid P(z)} \frac{\lambda_{d^{\prime}}}{d^{\prime}} = w_d per la (8), per cui possiamo sostituire w_d al posto di g(d).
Partiamo ora dalla formula del teorema:
f(k) = \sum_{k \mid d \mid n} \mu \left(\frac{d}{k}\right) g(d)
Effettuando le sostituzioni, si ottiene:
\frac{\lambda_k}{k} = \sum_{k \mid d \mid P(z)} \mu \left(\frac{d}{k}\right) w_d
Moltiplicando per k e cambiando i nomi delle variabili, si ottiene la formula (10).
Passo 7: trovare i valori di w_d che minimizzano T
Questo passo ha più a che fare con il calcolo algebrico che con la teoria dei numeri, perciò lo lasciamo ai lettori interessati. La cosa importante per il seguito è solamente il risultato finale:
Il nostro scopo è trovare un’opportuna funzione h in modo da rendere più piccolo possibile questo valore di T, ottenuto sostituendo w_d := h(d).
Abbiamo detto che \lambda_1 deve essere 1, ma \lambda_1 possiamo ottenerlo anche dalla (10). Per inciso, il motivo per cui abbiamo visto come calcolare i \lambda_d dai w_d prima di calcolare effettivamente i w_d è che ora ci serve la formula (10), in base alla quale:
Abbiamo ottenuto così un primo vincolo che deve essere soddisfatto dalle nostre w_d. Confrontando con la (d), possiamo tentare di ricondurre la sommatoria \sum_{d \mid P(z)} \phi(d) w_d h(d) a \sum_{d \mid P(z)} \mu(d) w_{d}; il modo più semplice per farlo è porre h(d) := \frac{\mu(d)}{\phi(d)}. Proviamo a sostituire questo valore nella (d):
dove nell’ultimo passaggio abbiamo applicato la (e), inoltre abbiamo osservato che \mu(d)^2 = 1 perché \mu(d) = \pm 1, essendo dprivo di quadrati.
Il valore di T che abbiamo trovato non va bene perché per z \to +\infty tende a -\infty, mentre chiaramente la quantità da stimare (i numeri che restano dopo il crivello) è positiva.
Per risolvere il problema chiamiamo V(z) l’ultima sommatoria ottenuta e, invece di porre h(d) := \frac{\mu(d)}{\phi(d)} come prima, dividiamo per V(z) ottenendo h(d) := \frac{\mu(d)}{\phi(d) V(z)}. Sostituendo questo valore nella (d), con poche modifiche rispetto ai passaggi visti prima, si ottiene:
Questo valore di T è soddisfacente perché positivo. Non escludiamo che altre scelte di w_d possano generare valori di T ancora più piccoli, ma il crivello di Selberg effettua questa scelta, e invitiamo i nostri lettori a farci sapere se esistono scelte migliori (ossia che minimizzino T senza però aumentare troppo il termine di errore R, che studieremo nel prossimo articolo).
Esempio conclusivo
Calcoliamo T e i vari \lambda_d quando P(z) = 2 \cdot 3 \cdot 5 = 30.
Dopo varie semplificazioni, abbiamo visto che T si può esprimere nella forma della formula (9):
Quindi possiamo dire che, secondo il crivello di Selberg, il numero di elementi dell’insieme A che rimangono dopo aver eliminato i multipli di 2, quelli di 3 e quelli di 5, è circa i \frac{4}{15} del totale (senza tener conto del termine di errore).
Per concludere, calcoliamo i valori di \lambda_d utilizzando la formula (10).
Questi valori ci serviranno nel prossimo articolo per maggiorare il termine di errore R dato dalla formula (2).
I valori ottenuti per \lambda(d) corrispondono, in questo caso, a \mu(d). Questo si verifica sempre per il crivello di Selberg nella forma semplificata, come dimostreremo in una parte di dettaglio del prossimo articolo.
Mostra i dettagli del calcolo di \lambda_3, \lambda_5, \lambda_6, \lambda_{10}, \lambda_{15}, \lambda_{30}
