Il crivello di Selberg: studio del termine di errore

Prerequisiti:

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:

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}

R := \sum_{d_1, d_2 \mid P(z)} \lambda_{d_1} \lambda_{d_2} r(\mathrm{mcm}(d_1, d_2)) \tag{2}

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à:

\forall d: |\lambda_d| \leq 1 \tag{3}

Riprendiamo la formula per \lambda_d che abbiamo visto nell’articolo precedente (passo 6, formula 10):

\lambda_d = d \sum_{d \mid d^{\prime} \mid P(z)} \mu\left( \frac{d^{\prime}}{d} \right) w_{d^{\prime}}

dove (articolo citato, passo 7, formula 11):

w_d := \frac{\mu(d)}{\phi(d) V(z)}

Per cui, unendo le due formule:

\lambda_d = d \sum_{d \mid d^{\prime} \mid P(z)} \mu\left( \frac{d^{\prime}}{d} \right) \frac{\mu(d^{\prime})}{\phi(d^{\prime}) V(z)}

Osserviamo innanzitutto che:

\mu\left( \frac{d^{\prime}}{d} \right) \mu(d^{\prime}) = \frac{\mu(d^{\prime})}{\mu(d)} \mu(d^{\prime}) = \frac{\mu(d^{\prime})^2}{\mu(d)} = \frac{1}{\mu(d)} = \mu(d)

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:

\lambda_d = d \sum_{d \mid d^{\prime} \mid P(z)} \frac{\mu(d)}{\phi(d^{\prime}) V(z)} = \frac{d \cdot \mu(d)}{V(z)} \sum_{d \mid d^{\prime} \mid P(z)} \frac{1}{\phi(d^{\prime})} \tag{a}

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:

\sum_{d \mid d^{\prime} \mid P(z)} \frac{1}{\phi(d^{\prime})} = \sum_{2 \cdot 3 \mid d^{\prime} \mid 2 \cdot 3 \cdot 5 \cdot 7} \frac{1}{\phi(d^{\prime})} = \frac{1}{\phi(2 \cdot 3)} + \frac{1}{\phi(2 \cdot 3 \cdot 5)} + \frac{1}{\phi(2 \cdot 3 \cdot 7)} + \frac{1}{\phi(2 \cdot 3 \cdot 5 \cdot 7)} \tag{b}

Per semplificare quest’ultima espressione bisogna utilizzare un’importante proprietà della funzione \phi che dimostreremo in un articolo specifico: essa è moltiplicativa. Ciò significa che, se a e b sono due interi positivi, 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):

\textrm{(b)} = \frac{1}{\phi(2 \cdot 3)} \left( 1 + \frac{1}{\phi(5)} + \frac{1}{\phi(7)} + \frac{1}{\phi(5 \cdot 7)} \right) \tag{c}

Ragionando in termini generali, abbiamo che:

\sum_{d \mid d^{\prime} \mid P(z)} \frac{1}{\phi(d^{\prime})} = \sum_{\frac{d^{\prime}}{d} \mid \frac{P(z)}{d}} \frac{1}{\phi \left( d \frac{d^{\prime}}{d} \right)} = \sum_{a \mid \frac{P(z)}{d}} \frac{1}{\phi ( d a )} = \frac{1}{\phi(d)} \sum_{a \mid \frac{P(z)}{d}} \frac{1}{\phi(a)} \tag{d}

Sostituendo nella (a), abbiamo:

\lambda_d = \frac{\mu(d)}{V(z)} \frac{d}{\phi(d)} \sum_{a \mid \frac{P(z)}{d}} \frac{1}{\phi(a)} \tag{e}

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:

\frac{2 \cdot 3}{\phi(2 \cdot 3)} = \frac{2}{\phi(2)} \cdot \frac{3}{\phi(3)}

Applicando la nostra definizione di \phi (Il crivello di Selberg: studio dei parametri \lambda, passo 2):

\phi(2) = \sum_{d^{\prime} d^{\prime \prime} = 2} \mu(d^{\prime}) d^{\prime \prime} = \mu(1) \cdot 2 + \mu(2) \cdot 1 = 1 \cdot 2 + (-1) \cdot 1 = 2 - 1

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:

\begin{aligned} \frac{2}{\phi(2)} \cdot \frac{3}{\phi(3)} &= \\ \frac{\phi(2) + 1}{\phi(2)} \cdot \frac{\phi(3) + 1}{\phi(3)} &= \\ \left( 1 + \frac{1}{\phi(2)} \right)\left( 1 + \frac{1}{\phi(3)} \right) &= \\ 1 + \frac{1}{\phi(2)} + \frac{1}{\phi(3)} + \frac{1}{\phi(2) \cdot \phi(3)} &= \\ 1 + \frac{1}{\phi(2)} + \frac{1}{\phi(3)} + \frac{1}{\phi(2 \cdot 3)} &= \\ \sum_{b \mid 6} \frac{1}{\phi(b)} \end{aligned}

In generale:

\frac{d}{\phi(d)} = \prod_{p \mid d} \frac{p}{\phi(p)} = \prod_{p \mid d} \frac{\phi(p) + 1}{\phi(p)} = \prod_{p \mid d} \left( 1 + \frac{1}{\phi(p)} \right) = \sum_{b \mid d} \frac{1}{\prod_{p \mid b} \phi(p)} = \sum_{b \mid d} \frac{1}{\phi(b)}

Sostituendo nella (e), abbiamo:

\lambda_d = \frac{\mu(d)}{V(z)} \sum_{b \mid d} \frac{1}{\phi(b)} \sum_{a \mid \frac{P(z)}{d}} \frac{1}{\phi(a)} \tag{f}

Moltiplicando le due sommatorie e ricordando ancora una volta che la funzione \phi è moltiplicativa, abbiamo:

\begin{aligned} \sum_{b \mid d} \frac{1}{\phi(b)} \sum_{a \mid \frac{P(z)}{d}} \frac{1}{\phi(a)} &= \\ \sum_{\substack{b \mid d \\ a \mid \frac{P(z)}{d}}} \frac{1}{\phi(b) \phi(a)} &= \\ \sum_{\substack{b \mid d \\ a \mid \frac{P(z)}{d}}} \frac{1}{\phi(b \cdot a)} &= \\ \sum_{c \mid P(z)} \frac{1}{\phi(c)} \end{aligned}

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:

\lambda_d = \frac{\mu(d)}{V(z)} \sum_{c \mid P(z)} \frac{1}{\phi(c)} = \frac{\mu(d)}{V(z)} V(z) = \mu(d)

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:

|\lambda_d| = |\mu(d)| = 1

da cui, in particolare, si ha la conclusione richiesta:

|\lambda_d| \leq 1

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|:

|R| \leq \sum_{d_1, d_2 \mid P(z)} |r(\mathrm{mcm}(d_1, d_2))| \tag{2'}

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:

\sum_{d_1, d_2 \mid P(z)} |r(\mathrm{mcm}(d_1, d_2))| = \sum_{d \mid P(z)} |r(d)| |\{d_1, d_2 \mid P(z) \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}| \tag{4}

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:

\begin{aligned} R \leq \\ \sum_{d_1, d_2 \mid 30} |f(d_1, d_2)| = \\ \sum \left( \begin{matrix} |f(1,1)| & |f(1,2)| & |f(1,3)| & |f(1,5)| & |f(1,6)| & |f(1,10)| & |f(1,15)| & |f(1,30)| \\ |f(2,1)| & |f(2,2)| & |f(2,3)| & |f(2,5)| & |f(2,6)| & |f(2,10)| & |f(2,15)| & |f(2,30)| \\ |f(3,1)| & |f(3,2)| & |f(3,3)| & |f(3,5)| & |f(3,6)| & |f(3,10)| & |f(3,15)| & |f(3,30)| \\ |f(5,1)| & |f(5,2)| & |f(5,3)| & |f(5,5)| & |f(5,6)| & |f(5,10)| & |f(5,15)| & |f(5,30)| \\ |f(6,1)| & |f(6,2)| & |f(6,3)| & |f(6,5)| & |f(6,6)| & |f(6,10)| & |f(6,15)| & |f(6,30)| \\ |f(10,1)| & |f(10,2)| & |f(10,3)| & |f(10,5)| & |f(10,6)| & |f(10,10)| & |f(10,15)| & |f(10,30)| \\ |f(15,1)| & |f(15,2)| & |f(15,3)| & |f(15,5)| & |f(15,6)| & |f(15,10)| & |f(15,15)| & |f(15,30)| \\ |f(30,1)| & |f(30,2)| & |f(30,3)| & |f(30,5)| & |f(30,6)| & |f(30,10)| & |f(30,15)| & |f(30,30)| \end{matrix}\right) = \\ \sum \left( \begin{matrix} |r(1)| & |r(2)| & |r(3)| & |r(5)| & |r(6)| & |r(10)| & |r(15)| & |r(30)| \\ |r(2)| & |r(2)| & |r(6)| & |r(10)| & |r(6)| & |r(10)| & |r(30)| & |r(30)| \\ |r(3)| & |r(6)| & |r(3)| & |r(15)| & |r(6)| & |r(30)| & |r(15)| & |r(30)| \\ |r(5)| & |r(10)| & |r(15)| & |r(5)| & |r(30)| & |r(10)| & |r(15)| & |r(30)| \\ |r(6)| & |r(6)| & |r(6)| & |r(30)| & |r(6)| & |r(30)| & |r(30)| & |r(30)| \\ |r(10)| & |r(10)| & |r(30)| & |r(10)| & |r(30)| & |r(10)| & |r(30)| & |r(30)| \\ |r(15)| & |r(30)| & |r(15)| & |r(15)| & |r(30)| & |r(30)| & |r(15)| & |r(30)| \\ |r(30)| & |r(30)| & |r(30)| & |r(30)| & |r(30)| & |r(30)| & |r(30)| & |r(30)| \end{matrix}\right) \end{aligned}

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:

\begin{aligned} \sum_{d \mid 30} |r(d)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}| &= \\ |r(1)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 1\}| + & \\ |r(2)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 2\}| + & \\ |r(3)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 3\}| + & \\ |r(5)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 5\}| + & \\ |r(6)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 6\}| + & \\ |r(10)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 10\}| + & \\ |r(15)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 15\}| + & \\ |r(30)| |\{d_1, d_2 \mid 30 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = 30\}| & = \\ |r(1)| \cdot 1 + |r(2)| \cdot 3 + |r(3)| \cdot 3 + |r(5)| \cdot 3 + |r(6)| \cdot 9 + |r(10)| \cdot 9 + |r(15)| \cdot 9 + |r(30)| \cdot 27 \end{aligned}

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:

\sum_{d \mid P(z)} |r(d)| \cdot |\{d_1, d_2 \mid P(z) \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}| = \\ \sum_{d \mid P(z)} |r(d)| \cdot |\{d_1, d_2 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}| \tag{5}

Il conteggio del numero di coppie è dato dalla seguente Proprietà:

Numero di coppie di interi aventi un minimo comune multiplo fissato

Sia d un numero intero positivo privo di quadrati. Il numero di coppie ordinate di interi positivi aventi minimo comune multiplo d è pari a:

3^{\omega(d)}

dove \omega(d) è il numero di fattori primi (distinti) che compaiono nella fattorizzazione di d.

La proprietà parla di coppie ordinate nel senso che, ad esempio, le coppie (2, 3) e (3, 2) sono da considerarsi distinte (ed entrambe hanno come minimo comune multiplo 6). Inoltre, essendo d privo di quadrati, nella fattorizzazione di d non ci sono fattori primi ripetuti: la parola “(distinti)” è riportata tra parentesi per indicare che si tratta una conseguenza diretta delle ipotesi.

Se d = 15 = 3 \cdot 5, le coppie ordinate di interi positivi che hanno come minimo comune multiplo d sono le seguenti:

(15, 1), (3, 5), (15, 5), (5, 3), (1, 15), (5, 15), (15, 3), (3, 15), (15, 15)

Il numero di coppie è 9 = 3^2 = 3^{\omega(15)}, come previsto dalla Proprietà.

Per contare quante coppie di interi positivi hanno minimo comune multiplo d, dobbiamo ricordarci un metodo di calcolo del minimo comune multiplo basato sulla fattorizzazione: dopo aver fattorizzato i due numeri, il loro minimo comune multiplo è dato dal prodotto dei loro fattori primi comuni e non comuni, col massimo esponente. Se ad esempio i due numeri sono d_1 = 2^2 \cdot 3 e d_2 = 2 \cdot 5^2, il loro minimo comune multiplo sarà d = 2^2 \cdot 3 \cdot 5^2. Questo esempio, però, non può verificarsi nel nostro caso, perché siamo partiti dal numero P(z) che è il prodotto di fattori primi distinti, per cui la stessa cosa varrà per d che è un divisore di P(z) (ad esempio, se P(z) = 2 \cdot 3 \cdot 5 allora d può essere 2 \cdot 3, che è sempre un prodotto di fattori primi distinti). Quindi nella fattorizzazione di d possiamo trovare solo numeri primi con esponente 1.
Date queste premesse, per contare quante possibili coppie di numeri interi hanno d come minimo comune multiplo, dobbiamo ragionare al contrario: cioè, se tutti i fattori primi di d hanno esponente 1, essendo quindi 1 il massimo esponente con cui tali fattori compaiono in d_1 o in d_2, vuol dire per ciascun fattore primo p si possono verificare solo tre casi:

  • p è presente in d_1 con esponente 1 e non è presente in d_2;
  • p è presente in d_2 con esponente 1 e non è presente in d_1;
  • p è presente sia in d_1 che in d_2, in entrambi con esponente 1.

Infatti, se p fosse assente in entrambi, sarebbe assente anche nel minimo comune multiplo, mentre se esso avesse in uno dei due numeri un esponente maggiore di 1, avrebbe un esponente maggiore di 1 anche nel minimo comune multiplo; ma entrambe queste circostanze sono da escludersi, per cui sono possibili solo i tre casi elencati.
Questo discorso vale per tutti i fattori primi p di d: se ce ne sono più di uno, i tre casi citati si combinano per ciascun fattore, moltiplicandosi. Ad esempio, se nel minimo comune multiplo ci sono due fattori p e q, i casi possibili diventano 9, perché ciascuno dei tre casi possibili per p può combinarsi con ciascuno dei tre casi possibili per q. In generale, se in d vi sono k fattori primi, il numero dei casi possibili è 3 moltiplicato per se stesso k volte, ossia 3^k.
Ciascuno dei casi così ottenuti dice esattamente quali fattori primi compaiono in d_1 e in d_2: infatti, d_1 e d_2 non possono avere fattori primi che non sono in d. Quindi i due numeri sono univocamente determinati da quali fattori primi di d essi contengono, che è esattamente quanto stabilito da ciascun caso, per cui il numero di possibili coppie coincide col numero di casi possibili, ossia 3^k, dove k è il numero di fattori primi di d.

Supponiamo che d = 3 \cdot 5, un prodotto di k = 2 numeri primi distinti. Allora, se \mathrm{mcm}(d_1, d_2) = d, si possono verificare 3^2 = 9 casi:

  • 3 è presente in d_1 con esponente 1 e non è presente in d_2; 5 è presente in d_1 con esponente 1 e non è presente in d_2;
  • 3 è presente in d_1 con esponente 1 e non è presente in d_2; 5 è presente in d_2 con esponente 1 e non è presente in d_1;
  • 3 è presente in d_1 con esponente 1 e non è presente in d_2; 5 è presente sia in d_1 che in d_2, in entrambi con esponente 1;
  • 3 è presente in d_2 con esponente 1 e non è presente in d_1; 5 è presente in d_1 con esponente 1 e non è presente in d_2;
  • 3 è presente in d_2 con esponente 1 e non è presente in d_1; 5 è presente in d_2 con esponente 1 e non è presente in d_1;
  • 3 è presente in d_2 con esponente 1 e non è presente in d_1; 5 è presente sia in d_1 che in d_2, in entrambi con esponente 1;
  • 3 è presente sia in d_1 che in d_2, in entrambi con esponente 1; 5 è presente in d_1 con esponente 1 e non è presente in d_2;
  • 3 è presente sia in d_1 che in d_2, in entrambi con esponente 1; 5 è presente in d_2 con esponente 1 e non è presente in d_1;
  • 3 è presente sia in d_1 che in d_2, in entrambi con esponente 1; 5 è presente sia in d_1 che in d_2, in entrambi con esponente 1.

In corrispondenza di ciascun caso, si ottengono rispettivamente le seguenti coppie ordinate di interi aventi come minimo comune multiplo d:

  • (d_1, d_2) = (15, 1)
  • (d_1, d_2) = (3, 5)
  • (d_1, d_2) = (15, 5)
  • (d_1, d_2) = (5, 3)
  • (d_1, d_2) = (1, 15)
  • (d_1, d_2) = (5, 15)
  • (d_1, d_2) = (15, 3)
  • (d_1, d_2) = (3, 15)
  • (d_1, d_2) = (15, 15)

Abbiamo così ritrovato le coppie viste nell’esempio precedente.

Applicando la Proprietà C.6, nel nostro caso abbiamo che:

|\{d_1, d_2 \textrm{\ tali che\ } \mathrm{mcm}(d_1, d_2) = d\}| = 3^{\omega(d)} \tag{6}

Per cui, unendo le formule (4), (5) e (6), otteniamo:

\sum_{d_1, d_2 \mid P(z)} |r(\mathrm{mcm}(d_1, d_2))| = \sum_{d \mid P(z)} |r(d)| 3^{\omega(d)} \tag{7}

Infine, unendo quest’ultima formula con la (2′), otteniamo la maggiorazione che cercavamo:

|R| \leq \sum_{d \mid P(z)} |r(d)| 3^{\omega(d)} \tag{8}

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:

\begin{aligned} R \leq & \\ \sum_{d_1, d_2 \mid 30} |r(\mathrm{m}(d_1, d_2))| & =\\ |r(1)| \cdot 1 + |r(2)| \cdot 3 + |r(3)| \cdot 3 + |r(5)| \cdot 3 + |r(6)| \cdot 9 + |r(10)| \cdot 9 + |r(15)| \cdot 9 + |r(30)| \cdot 27 \end{aligned}

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:

\begin{aligned} R \leq & \\ |r(1)| \cdot 1 + |r(2)| \cdot 3 + |r(3)| \cdot 3 + |r(5)| \cdot 3 + |r(6)| \cdot 9 + |r(10)| \cdot 9 + |r(15)| \cdot 9 + |r(30)| \cdot 27 = & \\ 0 \cdot 1 + 0 \cdot 3 + \frac{2}{3} \cdot 3 + 0 \cdot 3 + \frac{2}{3} \cdot 9 + 0 \cdot 9 + \frac{1}{3} \cdot 9 + \frac{2}{3} \cdot 27 = & \\ 2 + 6 + 3 + 18 = & \\ 29 \end{aligned}

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

S(A, \mathbb{P}, z) \leq |A| T + R

continua a valere se per T ed R, al posto delle formule (1) e (2), si utilizzano le seguenti:

T := \sum_{\substack{d_1, d_2 \mid P(z) \\ d_1, d_2 \lt z}} \frac{\lambda_{d_1} \lambda_{d_2}}{\mathrm{mcm}(d_1, d_2)} \tag{1'}
R := \sum_{\substack{d_1, d_2 \mid P(z) \\ d_1, d_2 \lt z}} \lambda_{d_1} \lambda_{d_2} r(\mathrm{mcm}(d_1, d_2)) \tag{2'}

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:

\forall d \gt z: \lambda_d = 0 \tag{9}

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:

\lambda_d = d \sum_{\substack{d^{\prime} \lt z \\ d \mid d^{\prime} \mid P(z)}} \mu\left( \frac{d^{\prime}}{d} \right) w_{d^{\prime}} \tag{10'}
V(z) := \sum_{\substack{d \lt z \\ d \mid P(z)}} \frac{1}{\phi(d)} \tag{12'}

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à:

d_1, d_2 \lt z \Rightarrow \mathrm{mcm}(d_1, d_2) \lt z^2

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:

d_1, d_2 \lt z\ \land\ |R| \leq \sum_{d \mid P(z)} |r(d)| 3^{\omega(d)} \Rightarrow |R| \leq \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} |r(d)| 3^{\omega(d)}

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):

\sum_{\substack{b \mid d \\ a \mid \frac{P(z)}{d}}} \frac{1}{\phi(b \cdot a)} = \sum_{c \mid P(z)} \frac{1}{\phi(c)} \tag{g}

che, dopo aver considerato la nuova ipotesi nelle formule precedenti (passaggi abbastanza meccanici che trascuriamo), diventa:

\sum_{\substack{b \mid d \\ a \mid \frac{P(z)}{d} \\ da \lt z}} \frac{1}{\phi(b \cdot a)} \leq \sum_{\substack{c \mid P(z) \\ c \lt z}} \frac{1}{\phi(c)} \tag{g'}

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:

|R| \leq \sum_{\substack{d \lt z^2 \\ d \mid P(z)}} |r(d)| 3^{\omega(d)} \tag{8'}

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}:

Confronto tra il termine di errore del crivello di Selberg con e senza limitazione su d, coi parametri del crivello di Eratostene applicato ai numeri naturali fino a 1000
Confronto tra il termine di errore del crivello di Selberg con e senza limitazione su d, coi parametri del crivello di Eratostene applicato ai numeri naturali fino a 3000

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.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *