Prerequisiti:
- Il crivello di Selberg: enunciato e inizio della dimostrazione
- Il crivello di Selberg: studio dei parametri λ
Abbiamo visto che, grazie al crivello di Selberg, si può calcolare una stima del valore della funzione di crivello S(A, \mathbb{P}, z), dove, come sempre, A è un insieme finito di numeri naturali, \mathbb{P} è l’insieme dei numeri primi e z \gt 1 è un numero reale. Tale stima è del tipo:
dove:
in cui P(z) è il prodotto dei numeri primi minori di z.
Nell’articolo precedente abbiamo calcolato i parametri \lambda_d che rendono la stima T più bassa possibile. Ora non resta che sostituire questi valori di \lambda_d nella funzione R che rappresenta il termine di errore della nostra stima: questo sarà lo scopo del presente articolo. Procederemo per passi successivi.
Passo 1: maggiorazione dei parametri \lambda_d
L’espressione dei parametri \lambda_d che abbiamo trovato nello scorso articolo è abbastanza complicata, per cui eviteremo di sostituirla nell’espressione di R e adotteremo un approccio più semplice. La questione fondamentale è che non è necessario calcolare esattamente l’errore, ma è sufficiente maggiorarlo, o meglio, per trattare allo stesso modo errori per eccesso e errori per difetto, è sufficiente maggiorarlo in valore assoluto, cioè stabilire quanto può valere al massimo |R|. Di conseguenza, anche per quanto riguarda i parametri \lambda_d non è importante tanto il loro valore esatto; piuttosto è importante sapere quanto può valere al massimo |\lambda_d|. In particolare, si dimostra la seguente proprietà:
Riprendiamo la formula per \lambda_d che abbiamo visto nell’articolo precedente (passo 6, formula 10):
dove (articolo citato, passo 7, formula 11):
Per cui, unendo le due formule:
Osserviamo innanzitutto che:
Infatti:
- La frazione \frac{d^{\prime}}{d} è in realtà un numero intero, dove sia il numeratore che il denominatore sono prodotti di fattori primi distinti; se indichiamo il numero di fattori primi distinti del numeratore e quelli del denominatore dispettivamente coi simboli M ed m, il numero di fattori primi distinti del rapporto è pari a M - m, ossia il numero di fattori del numeratore che non vengono semplificati nella frazione. A questo punto ci sono vari casi:
- Se M e m sono entrambi pari, allora per definizione \mu(d^{\prime}) = 1, \mu(d) = 1 e \mu\left( \frac{d^{\prime}}{d} \right) = 1 perché anche M - m è pari;
- Se M è pari e m è dispari, allora per definizione \mu(d^{\prime}) = 1, \mu(d) = -1 e \mu\left( \frac{d^{\prime}}{d} \right) = -1 perché M - m è dispari;
- Se M è dispari e m è pari, allora per definizione \mu(d^{\prime}) = -1, \mu(d) = 1 e \mu\left( \frac{d^{\prime}}{d} \right) = -1 perché M - m è dispari;
- Se M e m sono entrambi dispari, allora per definizione \mu(d^{\prime}) = -1, \mu(d) = -1 e \mu\left( \frac{d^{\prime}}{d} \right) = 1 perché M - m è pari;
Come si vede, in tutti i casi \mu\left( \frac{d^{\prime}}{d} \right) = \frac{\mu(d^{\prime})}{\mu(d)} (ad esempio, nell’ultimo caso, \mu\left( \frac{d^{\prime}}{d} \right) = 1 = \frac{-1}{-1} = \frac{\mu(d^{\prime})}{\mu(d)}).
- L’intero \mu(d^{\prime}) può essere solamente 1 o -1, perché d^{\prime} è prodotto di fattori primi distinti; in entrambi i casi \mu(d^{\prime})^2 = 1
- Come \mu(d^{\prime}), anche \mu(d) può essere 1 o -1; se è 1 allora \frac{1}{\mu(d)} = \frac{1}{1} = 1, mentre se è -1 allora \frac{1}{\mu(d)} = \frac{1}{-1} = -1: in entrambi i casi il risultato della frazione è uguale a \mu(d)
Quindi la formula di \lambda_d si può semplificare come segue:
dove nell’ultimo passaggio abbiamo messo in evidenza i fattori che non dipendono dalla variabile della sommatoria, che è d^{\prime}. Concentriamoci ora sull’ultima sommatoria che abbiamo ottenuto. Per maggiore chiarezza, vediamo un esempio.
Se P(z) = 2 \cdot 3 \cdot 5 \cdot 7 e d = 2 \cdot 3, abbiamo:
Per semplificare quest’ultima espressione bisogna utilizzare un’importante proprietà della funzione \phi che dimostreremo in un articolo specifico: essa è moltiplicativa. In base a questa proprietà, se a e b sono due interi positivi coprimi, allora \phi(ab) = \phi(a) \cdot \phi(b). Ad esempio, nel nostro caso \phi(2 \cdot 3 \cdot 5) = \phi(2 \cdot 3) \cdot \phi(5), \phi(2 \cdot 3 \cdot 7) = \phi(2 \cdot 3) \cdot \phi(7) e \phi(2 \cdot 3 \cdot 5 \cdot 7) = \phi(2 \cdot 3) \cdot \phi(5 \cdot 7). Ciò consente di mettere in evidenza il primo termine nella (b):
Ragionando in termini generali, abbiamo che:
Sostituendo nella (a), abbiamo:
Concentriamoci ora sul rapporto \frac{d}{\phi(d)}. Anche in questo caso per chiarezza vediamo un esempio.
Se d = 2 \cdot 3, ricordando che \phi è moltiplicativa, possiamo sviluppare il rapporto come segue:
Applicando la nostra definizione di \phi (Il crivello di Selberg: studio dei parametri \lambda, passo 2):
Infatti le uniche due coppie di numeri interi d^{\prime}, d^{\prime \prime} aventi come prodotto 2 sono (1, 2) e (2, 1). Ma la stessa proprietà vale anche se sostituiamo 2 con qualsiasi altro numero primo p, per cui in generale \phi(p) = p - 1, da cui p = \phi(p) + 1. Nel nostro caso:
In generale:
Sostituendo nella (e), abbiamo:
Moltiplicando le due sommatorie e ricordando ancora una volta che la funzione \phi è moltiplicativa, abbiamo:
Nell’ultimo passaggio abbiamo posto c := b \cdot a, da cui, essendo b un divisore di d e a un divisore di \frac{P(z)}{d}, certamente il loro prodotto c è un divisore di d \cdot \frac{P(z)}{d} = P(z), per cui ciascun termine presente nella penultima sommatoria è presente anche nell’ultima. Vale però anche il viceversa: preso qualunque divisore c di P(z), è sempre possibile scomporre c nel prodotto dei suoi fattori primi in comune con d – il prodotto dei quali possiamo chiamare b – moltiplicato per il prodotto dei suoi fattori primi in comune con \frac{P(z)}{d} – il prodotto dei quali possiamo chiamare a – per questa ragione anche ogni elemento dell’ultima sommatoria può essere trovato nella penultima (si noti che è possibile scomporre c nel modo descritto perché d e \frac{P(z)}{d} non hanno divisori in comune). Questo spiega l’ultima uguaglianza.
L’ultima sommatoria però la conosciamo già: non è altro che la definizione di V(z) (Il crivello di Selberg: studio dei parametri \lambda, formula 12); quindi nella (f) possiamo semplificare come segue:
che è proprio quello che avevamo osservato nell’esempio conclusivo dell’articolo precedente.
A questo punto, ricordando che \mu(d) = \pm 1 essendo d privo di quadrati, la conclusione è semplice:
da cui, in particolare, si ha la conclusione richiesta:
Per la dimostrazione appena conclusa, avremmo potuto enunciare il risultato più forte |\lambda_d| = 1 invece di accontentarci della disuguaglianza, ma non l’abbiamo fatto perché l’uguaglianza non è più vera se si aggiungono ulteriori ipotesi, cosa che faremo alla fine di questo articolo.
Sostituendo nella (2), si ottiene un’espressione abbastanza semplice della maggiorazione di |R|:
Il passo successivo è semplificare quest’ultima relazione.
Passo 2: raggruppare per minimo comune multiplo
Si può osservare un aspetto importante riguardo alla formula (2′): se d_1 e d_2 sono divisori di P(z), anche il loro minimo comune multiplo deve essere un divisore di P(z).
Perché il minimo comune multiplo tra d_1 e d_2 deve dividere P(z)?
Il motivo sta proprio nella definizione di minimo comune multiplo: se d_1 e d_2 sono divisori di P(z), vuol dire che P(z) è un comune multiplo di d_1 e d_2; ma per definizione il minimo comune multiplo divide qualsiasi comune multiplo, quindi divide anche P(z). Ad esempio, 6 e 4 sono divisori di 24, quindi 24 è un multiplo comune per entrambi; quindi il minimo comune multiplo tra 4 e 6 deve dividere 24 (in effetti, il minimo comune multiplo è 12, che divide 24).
Quindi i possibili valori di \mathrm{mcm}(d_1, d_2), nella (2′), sono i divisori di P(z), ma è possibile che diverse coppie (d_1, d_2) abbiano lo stesso minimo comune multiplo, per cui esisteranno valori di r(\mathrm{mcm}(d_1, d_2)) ripetuti. Possiamo quindi pensare di raggruppare i valori di r(\mathrm{mcm}(d_1, d_2)) uguali, moltiplicando ciascuno per il numero di volte in cui è presente nella sommatoria, ossia per il numero di coppie (d_1, d_2) aventi il minimo comune multiplo indicato nel pedice:
Supponiamo che P(z) = 2 \cdot 3 \cdot 5 = 30. Allora i divisori di P(z) sono 2, 3, 5, 6, 10, 15 e 30. La (2′), ponendo per brevità r(\mathrm{m}(x, y)) := f(x, y), si sviluppa come segue:
Come si può vedere, valori uguali di r(\mathrm{mcm}(d_1, d_2)) sono ripetuti più volte, per cui, contando il numero di ripetizioni di ciascun valore, la sommatoria si può scrivere più brevemente come:
Come si può vedere, il numero di ripetizioni di ciascun |r(d)| è sempre una potenza di 3: questo non è un caso, come vedremo tra poco.
Resta quindi da calcolare, per ogni d, la cardinalità dell’insieme \{d_1, d_2 \mid P(z) \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}, ossia il numero di coppie di divisori di P(z) che hanno come minimo comune multiplo d.
Per prima cosa possiamo osservare che la condizione d_1, d_2 \mid P(z) è superflua: infatti può essere ricavata dalla condizione \mathrm{mcm}(d_1, d_2) = d ricordando che d a sua volta un divisore di P(z); quindi possiamo contare semplicemente quante coppie di interi hanno come minimo comune multiplo d senza vincoli particolari, e la condizione d_1, d_2 \mid P(z) sarà automaticamente soddisfatta. In altri termini, vale la seguente uguaglianza:
Il conteggio del numero di coppie è dato dalla Proposizione N.29, di cui per comodità riportiamo l’enunciato (seguendo il link precedente si possono trovare anche la dimostrazione e un esempio):
Numero di coppie di interi aventi un minimo comune multiplo fissato, privo di quadrati
Sia d un numero intero positivo privo di quadrati. Il numero di coppie ordinate di interi positivi aventi minimo comune multiplo d è pari a:
Applicando la Proposizione N.29 al nostro caso, abbiamo che:
Per cui, unendo le formule (4), (5) e (6), otteniamo:
Infine, unendo quest’ultima formula con la (2′), otteniamo la maggiorazione che cercavamo:
Come si può notare, questa funzione dipende solo da z, che è uno dei parametri fissati inizialmente, dunque il risultato sarà un numero.
Nel primo esempio, con P(z) = 2 \cdot 3 \cdot 5 = 30, abbiamo visto che:
Dalla (8) sappiamo che i numeri che moltiplicano r(d) si possono esprimere come 3^{\omega(d)}, ad esempio il 9 che moltiplica |r(15)| è dato da 3^{\omega(15)}, come stabilito nel precedente esempio.
Ora svolgiamo i calcoli per ottenere una maggiorazione concreta di R. A tal proposito ricordiamo che la funzione r è definita (Teorema C.4) dalla relazione r(d) := |A_d| - \frac{|A|}{d}, dove |A_d| è il numero di multipli di d presenti nell’insieme A. Se come insieme A prendiamo tutti gli interi da 1 a un certo intero N fissato, come abbiamo visto negli articoli precedenti, la formula diventa r(d) = \left\lfloor \frac{N}{d} \right\rfloor - \frac{N}{d}. Se in particolare poniamo N := 50, abbiamo:
- |r(1)| = \left| \left\lfloor \frac{N}{1} \right\rfloor - \frac{N}{1} \right| = \left| \left\lfloor \frac{50}{1} \right\rfloor - \frac{50}{1} \right| = |50 - 50| = 0
- |r(2)| = \left| \left\lfloor \frac{N}{2} \right\rfloor - \frac{N}{2} \right| = \left| \left\lfloor \frac{50}{2} \right\rfloor - \frac{50}{2} \right| = |25 - 25| = 0
- |r(3)| = \left| \left\lfloor \frac{N}{3} \right\rfloor - \frac{N}{3} \right| = \left| \left\lfloor \frac{50}{3} \right\rfloor - \frac{50}{3} \right| = \left|16 - \frac{50}{3}\right| = \left|- \frac{2}{3}\right| = \frac{2}{3}
- |r(5)| = \left| \left\lfloor \frac{N}{5} \right\rfloor - \frac{N}{5} \right| = \left| \left\lfloor \frac{50}{5} \right\rfloor - \frac{50}{5} \right| = |10 - 10| = 0
- |r(6)| = \left| \left\lfloor \frac{N}{6} \right\rfloor - \frac{N}{6} \right| = \left| \left\lfloor \frac{50}{6} \right\rfloor - \frac{50}{6} \right| = \left|8 - \frac{50}{6}\right| = \left|- \frac{2}{3}\right| = \frac{2}{3}
- |r(10)| = \left| \left\lfloor \frac{N}{10} \right\rfloor - \frac{N}{10} \right| = \left| \left\lfloor \frac{50}{10} \right\rfloor - \frac{50}{10} \right| = |5 - 5| = 0
- |r(15)| = \left| \left\lfloor \frac{N}{15} \right\rfloor - \frac{N}{15} \right| = \left| \left\lfloor \frac{50}{15} \right\rfloor - \frac{50}{15} \right| = \left|3 - \frac{50}{15}\right| = \left|- \frac{5}{15}\right| = \frac{1}{3}
- |r(30)| = \left| \left\lfloor \frac{N}{30} \right\rfloor - \frac{N}{30} \right| = \left| \left\lfloor \frac{50}{30} \right\rfloor - \frac{50}{30} \right| = \left|1 - \frac{50}{30}\right| = \left|- \frac{20}{30}\right| = \frac{2}{3}
Quindi, sostituendo, otteniamo:
Anche solo limitandoci a questo esempio, possiamo vedere che questa stima dell’errore è abbastanza alta: stiamo stimando il conteggio dei numeri non divisibili per 2, 3 e 5 minori di 50, e sbagliare di 29 è davvero tanto, considerando che i numeri fino a 50 che non siano divisibili per 2, 3 e 5 sono molti meno di 29 (precisamente, sono: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, e 47). Nel prossimo paragrafo vedremo come migliorare questo aspetto.
Passo 3: limitare d per rendere piccolo l’errore
Come abbiamo visto nell’esempio precedente, la formula (8) tende a generare stime dell’errore molto grandi. Ciò non deve stupire, in quanto la sommatoria è estesa a tutti i divisori di P(z), che crescono in modo esponenziale rispetto a P(z). Inoltre, il numero dei fattori primi di ciascuno (\omega(d)) compare come esponente di 3, generando potenzialmente valori molto grandi; quindi non solo la sommatoria ha molti termini, ma anche ciascun termine è potenzialmente molto grande.
Rendere più piccoli i termini della sommatoria è difficile, perché significherebbe ragionare in modo completamente diverso rispetto a quanto fatto finora, ma è possibile ridurre il numero di termini modificando solo alcuni dettagli. Per fare ciò, però, bisogna fare un passo indietro. È possibile dimostrare che la maggiorazione
continua a valere se per T ed R, al posto delle formule (1) e (2), si utilizzano le seguenti:
Rispetto a prima, quindi, abbiamo imposto una condizione aggiuntiva su d_1 e d_2, stabilendo che devono essere minori di z. Ma come è possibile fare un cambiamento di questa portata senza stravolgere il ragionamento?
Il motivo è che abbiamo piena libertà nella scelta dei parametri \lambda_d. Ricordiamo infatti (Il crivello di Selberg: enunciato e inizio della dimostrazione) che essi possono essere numeri reali qualsiasi, eccetto \lambda_1 che deve essere uguale a 1. Quindi possiamo sceglierli in modo arbitrario, per cui nulla vieta di porre:
In questo modo le equazioni (1) e (2) sarebbero equivalenti rispettivamente a (1′) e (2′); infatti in tutti i termini con d_1 \gt z o con d_2 \gt z avremmo che \lambda_{d_1} \lambda_{d_2} = 0, e quindi sarebbero pari a zero.
Questa modifica può essere introdotta fin dall’inizio e, a parte una sola eccezione, non modifica i passaggi logici e algebrici degli articoli precedenti; aggiunge solamente una condizione in più in ogni formula (a seconda dei casi, d \lt z, d_1 \lt z, d_2 \lt z o d^{\prime} \lt z). Ad esempio, le formule (10) e (12) dell’articolo Il crivello di Selberg: studio dei parametri λ diventerebbero rispettivamente:
In questo articolo, invece, il significato del simbolo d è un po’ diverso: esso è il minimo comune multiplo di d_1 e d_2, i quali a loro volta sono entrambi minori di z. A tal proposito, essendo d_1, d_2 \lt z \Rightarrow d_1 d_2 \lt z^2, e \mathrm{mcm}(d_1, d_2) \leq d_1 d_2, vale la proprietà:
che però non vale nell’altro senso, come è facile verificare (se ad esempio z = 10, \mathrm{mcm}(50, 50) = 50 \lt 100 ma 50 non è minore di 10). Quindi, essendo d = \mathrm{mcm}(d_1, d_2), possiamo dire che:
Infatti la sommatoria di destra avrà almeno gli stessi termini di quella di sinistra, perché i minimi comuni multipli minori di z^2 sono almeno quelli ottenibili partendo da due numeri minori di z. Il \leq di destra quindi è meno stringente di quello di sinistra (e di conseguenza la maggiorazione è meno precisa); tuttavia si preferisce comunque la formula di destra perché quella di sinistra è meno esplicita, dato che d_1 e d_2 non compaiono esplicitamente come variabili della sommatoria; compare solo d che è ricavato da essi.
Qual è l’unica eccezione in cui la (9) modifica i passaggi logici della dimostrazione?
L’unico punto della dimostrazione che viene modificato in modo sostanziale dall’ipotesi (9) è la dimostrazione che |\lambda_d| \leq 1. Come abbiamo visto sopra, senza quell’ipotesi si riesce a dimostrare che \lambda_d = \mu(d), da cui |\lambda_d| = 1, mentre questo non è più vero aggiungendo l’ipotesi aggiuntiva. Ciò che cambia è questo singolo passaggio della dimostrazione della (3):
che, dopo aver considerato la nuova ipotesi nelle formule precedenti (passaggi abbastanza meccanici che trascuriamo), diventa:
dove abbiamo una disuguaglianza al posto della precedente uguaglianza.
Un esempio ci può aiutare a chiarire il motivo della disuguaglianza.
Supponiamo che z = 20, da cui P(z) = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19; supponiamo inoltre che d = 6. Allora nella sommatoria di sinistra della (g’) abbiamo che:
- b \mid d \Rightarrow b \mid 6 \Rightarrow b \in \{1, 2, 3, 6\}
- a \mid \frac{P(z)}{d} \Rightarrow a \mid 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19, da cui ci sono 2^6 possibilità per a, tante quanti i possibili divisori di un prodotto di sei interi distinti
- da \lt z \Rightarrow 6a \lt 20 \Rightarrow a \in \{1, 2, 3\}
- Dagli ultimi due punti segue che a = 1, perché 1 è l’unico numero che soddisfa entrambe le condizioni
In definitiva abbiamo quindi 4 possibilità per b e una possibilità per a, per cui ci saranno 4 \cdot 1 = 4 possibili termini del tipo \frac{1}{\phi(b \cdot a)}: \frac{1}{\phi(1)}, \frac{1}{\phi(2)}, \frac{1}{\phi(3)} e \frac{1}{\phi(6)}.
Nella sommatoria di destra invece abbiamo che:
- c \mid P(z) \Rightarrow c \mid 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19, da cui ci sono 2^8 possibilità per b, tante quanti i possibili divisori di un prodotto di otto interi distinti
- c \lt z \Rightarrow c \lt 20
I valori di c che soddisfano entrambe le condizioni sono i seguenti: 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19: questa volta ci sono 13 possibilità, ossia 13 possibili termini del tipo \frac{1}{\phi(c)}, dove c è uno dei valori appena elencati. È evidente quindi che la sommatoria di destra contiene tutti i termini della sommatoria di sinistra più altri, dunque vale la relazione di \leq, che alla fine viene ereditata dalla relazione |\lambda_d| \leq 1.
Se invece non considerassimo l’ipotesi aggiuntiva, cioè nella (g), entrambe le sommatorie avrebbero gli stessi termini, del tipo \frac{1}{\phi(c)}, dove c è uno dei 2^8 divisori di P(z); nella sommatoria di sinistra in particolare avremmo le stesse 4 possibilità per b e 2^6 possibilità per a, per un totale appunto di 2^8 possibilità.
La nostra stima finale dell’errore sarà quindi la seguente:
Questa limitazione su d abbassa molto la stima per eccesso di R; infatti, al crescere di z, i divisori di P(z) minori di z^2 diventano una frazione sempre più piccola del totale, per cui la condizione tende a escludere la maggior parte dei possibili termini, rendendo la maggiorazione molto più vicina al valore reale. Per rendersi conto dell’entità di questo effetto, è utile confrontare i grafici delle maggiorazioni (8) e (8′). Lo faremo riprendendo l’esempio dell’articolo Il crivello di Selberg: enunciato e inizio della dimostrazione, dove abbiamo utilizzato i parametri del crivello di Eratostene, ossia N \gt 1, A = \{1, 2, \ldots, N\} e z = \sqrt{N + 1}:


Come si vede, le due maggiorazioni hanno ordini di grandezza molto diversi. I grafici sono anche diversi qualitativamente, perché quello della funzione di errore senza la limitazione su d mostra dei salti, che si verificano quando, da un valore di N all’altro, si aggiunge un nuovo numero primo nel prodotto P(z): questo causa il raddoppio del numero dei valori di d considerati nella sommatoria (perché il numero di divisori di un prodotto di k+1 numeri primi è il doppio di quello di un prodotto di k numeri primi), dunque si ottiene improvvisamente un valore finale molto più grande del precedente.