Una stima per eccesso del numero di coppie di Goldbach

Come si può calcolare il numero di coppie non ordinate partendo dal numero di coppie ordinate?

Se N non è della forma p + p, tutte le coppie hanno addendi distinti, dunque il numero di quelle non ordinate è esattamente la metà di quelle ordinate, quindi è \frac{\mathfrak{R}(N)}{2}.
Se invece N = p + p, bisogna osservare che la coppia ordinata p + p resta identica cambiando l’ordine degli addendi, quindi non viene contata due volte come le altre coppie ordinate. Allora, per ottenere il numero di coppie non ordinate, conviene calcolare prima la metà del numero delle altre coppie ordinate, ossia \frac{\mathfrak{R}(N) - 1}{2}, poi aggiungere 1 per considerare la coppia p + p (vista questa volta come coppia non ordinata) che era stata esclusa. In questo caso il numero di coppie non ordinate è quindi \frac{\mathfrak{R}(N) - 1}{2} + 1, che a sua volta è uguale a \frac{\mathfrak{R}(N) + 1}{2}.

Sia G := \{(p, q) \mid p + q = N\} l’insieme delle coppie di Goldbach per N (come sempre indichiamo con p e q dei numeri primi). Possiamo partizionare questo insieme in tre sottoinsiemi:

• G_1 := \{(p, q) \mid p + q = N, p \leq z\}
• G_2 := \{(p, q) \mid p + q = N, z \lt p \lt N - z\}
• G_3 := \{(p, q) \mid p + q = N, p \geq N - z\}

Sicuramente |G_1| \leq z, perché gli elementi di G_1 sono al massimo quanti i numeri primi p \leq z, che a loro volta sono al massimo z (sarebbero z se tutti gli interi compresi tra 1 e z fossero primi, che non è vero, ma come maggiorazione va bene; per essere più precisi potremmo dire che |G_1| \leq \pi(z), ma ciò non migliorerebbe l’enunciato finale in modo significativo).
Analogamente possiamo dire che |G_3| \leq z, perché gli elementi di G_3 sono al massimo quanti i numeri primi p compresi tra N - z e N - 1, che a loro volta sono al massimo z (sarebbero z se tutti gli interi compresi tra N - z e N - 1 fossero primi).

Per quanto riguarda G_2, dalla condizione z \lt p \lt N - z otteniamo immediatamente che p \gt z, ma possiamo anche ottenere che q = N - p \gt N - (N - z) = z, cioè q \gt z. Essendo sia p che q maggiori di z e primi, certamente non sono divisibili per nessun primo minore di z; lo stesso potrà dirsi quindi del loro prodotto pq. Ricordiamo che la funzione di crivello S(A, \mathbb{P}, z) conta gli elementi della famiglia A che non sono divisibili per nessun numero primo minore di z: uno di questi elementi sarà quindi pq. Dato che questo vale per ogni p e q che rientrano nella definizione dell’insieme G_2, possiamo concludere che tutti gli elementi di G_2 rientrano nel conteggio del crivello, quindi |G_2| \leq S(A, \mathbb{P}, z).

Concludendo, abbiamo che:

Come si comporta la funzione f nel crivello, quando si contano nell’insieme A i multipli di un numero che non è privo di quadrati?

Si può osservare che, se d non è privo di quadrati, applicando nel crivello la funzione f che abbiamo definito si ottiene un risultato errato.
Ad esempio, se N = 20 e d = 9, gli elementi della famiglia A che sono multipli di 9 sono 36, 99, 99 e 36, per un totale di 4 (le coppie corrispondenti sono (2, 18), (9, 11), (11, 9) e (18, 2)), mentre applicando la formula |A| f(d) otteniamo più del doppio: |A| f(d) = 20 f(9) = 20 f(3) f(3) = 20 \cdot \frac{2}{3} \cdot \frac{2}{3} = \frac{80}{9} \geq 8.

Questo però non rappresenta un problema, perché in realtà non è il valore della funzione a essere errato, ma la domanda iniziale. Infatti, tutto il ragionamento che sta alla base del crivello di Selberg, sviluppato nei precedenti articoli, considera solo numeri d privi di quadrati; infatti, come si può vedere in molte formule della dimostrazione, d è sempre un divisore di P(z), che è privo di quadrati, sia nella stima del crivello che nel termine d’errore.
L’unica parte del Teorema dove serve che f sia definita su tutti gli interi è quella finale, che avviene dopo aver già trovato la seguente maggiorazione (formula (7) dell’articolo Il crivello di Selberg: generalizzazione e fine della dimostrazione):

per ottenere la quale, durante la dimostrazione, è stato sufficiente applicare f a numeri privi di quadrati (per approfondire, v. ultimo dettaglio dell’articolo citato).

L’esigenza che f sia definita su tutti i numeri interi (e che sia completamente moltiplicativa) nasce quindi a posteriori rispetto al crivello, quando per semplificare la disuguaglianza precedente si dimostra che (formula (8) dell’articolo citato):

dove, come sappiamo, \frac{1}{n} viene generalizzato come f(n) nella forma più generale del Teorema (quindi serve che f sia definita almeno su tutti gli interi positivi minori di z). La maggiorazione precedente, tuttavia, è un passaggio di natura puramente numerica che non ha nulla a che fare con il meccanismo del crivello, per cui non importa se f(n), per numeri non privi di quadrati, assume valori che, se fossero utilizzati nel crivello, sarebbero errati. Ciò che conta, in questa fase “numerica” della dimostrazione del Teorema, è solo che la funzione sia completamente moltiplicativa, non i particolari valori che essa assume.

Consideriamo un intero positivo n \lt z. Fattorizziamo n distinguendo tra i fattori primi che dividono N, che chiameremo p_1, \ldots, p_k, e quelli che non lo dividono, che chiameremo q_1, \ldots, q_r:

con a_1, \ldots, a_k, b_1, \ldots, b_r \gt 0.

Calcoliamo f(n), ricordando che è completamente moltiplicativa:

Consideriamo ora il numero di divisori di n coprimi con N e indichiamo con d(n, N) la loro cardinalità:

Possiamo calcolare esattamente quali sono questi divisori; infatti, se d è un divisore di n coprimo con N, nella sua fattorizzazione possono comparire come fattori primi solo q_1, \ldots, q_r, ciascuno con un esponente non superiore a quello che ha nella fattorizzazione di n. Quindi d deve essere del tipo:

con 0 \leq c_1 \leq b_1, \ldots, 0 \leq c_r \leq b_r (se l’esponente è zero, il numero primo è assente nella fattorizzazione di d).
Considerando tutte le possibili combinazioni di esponenti, abbiamo (1 + b_1)\cdot\ldots\cdot(1 + b_r) possibilità per d, per cui

Possiamo osservare che, se b_1 = \ldots = b_r = 1, cioè se n è privo di quadrati, questo numero è uguale a \underbrace{2 \cdot \ldots \cdot 2}_{r \textrm{ volte}} = 2^r = 2^{b_1 + \ldots + b_r}, quindi coinciderebbe col numeratore di f(n) dato dalla (a). In generale, senza fare ipotesi aggiuntive su b_1, \ldots, b_r, possiamo dire che:

Infatti, per ogni b_i \in \set{b_1, \ldots, b_r}, se b_i = 1 allora 1 + b_i = 2 = 2^{b_1}, mentre se b_i \gt 1, è facile vedere che la funzione esponenziale genera valori più grandi dell’altra (per 1 + b_i = 3, 4, 5, \ldots, mentre 2^{b_i} = 4, 8, 16, \ldots, rispettivamente); lo si può dimostrare ad esempio con il principio di induzione.
Quindi dalla (a) e dalla (b) possiamo concludere che:

Ora consideriamo il prodotto \prod_{p \mid N}\left( 1 - \frac{1}{p} \right)^{-1}. Per la Proprietà A.26 abbiamo che:

dove

Dalla (c) e dalla (d) abbiamo:

Poniamo s := na.

La sommatoria più interna contiene tutte le frazioni del tipo \frac{1}{s} con 1 \leq s \lt z, perché, dato un tale s, possiamo porre n := s e a := 1 (tali scelte sono lecite perché per ipotesi n = s soddisfa la condizione 1 \leq n \lt z della prima sommatoria, mentre, come richiesto dalla seconda sommatoria, a = 1 \in A, perché 1 non ha fattori primi). Una frazione del tipo \frac{1}{s} può però comparire anche più volte, perché possono esistere varie scelte di n e di a il cui prodotto è s. In particolare, possiamo scegliere n tra i divisori di s e verificare poi se a = \frac{s}{n} \in A: la frazione \frac{1}{s} comparirà tutte le volte in cui la verifica ha esito positivo, e ogni volta sarà moltiplicata per lo stesso termine d(n, N) della sommatoria esterna. Possiamo quindi invertire le sommatorie in questo modo:

dove il \geq è dovuto al fatto che la sommatoria interna della (e) contiene anche frazioni aventi s \geq z che non abbiamo considerato, mentre la (f) comprende solo le frazioni del tipo \frac{1}{s}, con 1 \leq s \lt z, che però compaiono anche nella (e). Quindi, se espandessimo le doppie sommatorie, i termini della (f) sarebbero un sottoinsieme dei termini della (e).

Ora semplifichiamo la sommatoria \sum_{\substack{n \mid s \\ \frac{s}{n} \in A}} d(n, N).

Nel seguito useremo la funzione d che restituisce il numero di divisori di un numero naturale; useremo anche la notazione d(s, N) per indicare il numero di divisori di s coprimi con N.

Fattorizziamo s distinguendo tra i fattori primi che dividono N, che chiameremo p_1, \ldots, p_k, e quelli che non lo dividono, che chiameremo q_1, \ldots, q_r (stiamo usando gli stessi simboli dell’inizio della dimostrazione, ma le due parti della dimostrazione sono da intendersi come separate, quindi questi p_1, \ldots, p_k, q_1, \ldots, q_r non sono gli stessi di prima). Inoltre, chiameremo a il prodotto dei fattori che dividono N e b il prodotto degli altri:

con a_1, \ldots, a_k, b_1, \ldots, b_r \gt 0.

Ora dimostriamo che:

1. d(a) \cdot d(b) = d(s)
2. d(s, N) = d(b)
3. Se n \mid s e \frac{s}{n} \in A, allora d(n, N) = d(s, N)
4. Il numero di interi positivi n tali che n \mid s e \frac{s}{n} \in A è d(a)

Dimostrazione:

1. Se n \mid s, allora possiamo scrivere n come:

   n = \underbrace{p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}}}_{a^{\prime}} \cdot \underbrace{q_1^{b_1^{\prime}} \ldots q_r^{b_r^{\prime}}}_{b^{\prime}} \tag{j}

   con 0 \leq a_1^{\prime} \leq a_1, \ldots, 0 \leq a_k^{\prime} \leq a_k, 0 \leq b_1^{\prime} \leq b_1, \ldots, 0 \leq b_r^{\prime} \leq b_r.

   In particolare, a^{\prime} \mid a e b^{\prime} \mid b, per cui a ogni divisore di s possiamo associare una coppia (a^{\prime}, b^{\prime}) dove a^{\prime} \mid a e b^{\prime} \mid b. Vale però anche il viceversa: se a^{\prime} \mid a, allora a^{\prime} è del tipo p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}} con 0 \leq a_1^{\prime} \leq a_1, \ldots, 0 \leq a_k^{\prime} \leq a_k e se b^{\prime} \mid b, allora b^{\prime} è del tipo q_1^{b_1^{\prime}} \ldots q_k^{b_k^{\prime}} con 0 \leq b_1^{\prime} \leq b_1, \ldots, 0 \leq b_k^{\prime} \leq b_k; quindi il loro prodotto, dato dalla (j), è un divisore di s. In sintesi, esiste una corrispondenza biunivoca tra i divisori di s, la cui cardinalità è d(s), e le coppie (a^{\prime}, b^{\prime}) con a^{\prime} \mid a e b^{\prime} \mid b, la cui cardinalità è d(a) \cdot d(b). Quindi d(a) \cdot d(b) = d(s).

2. Partendo dalla (i), possiamo osservare che i divisori di s coprimi con N sono i divisori di b. Infatti, se un divisore è coprimo con N può avere come fattori primi solo q_1, \ldots, q_r, quindi divide b; viceversa, un divisore di b è anche un divisore di s, ed è coprimo con N perché ha solo fattori primi che non dividono N. Quindi, passando alle cardinalità, d(s, N) = d(b).

3. Dalla (i) e dalla (j) abbiamo:

   \frac{s}{n} = p_1^{a_1 - a_1^{\prime}} \ldots p_k^{a_k - a_k^{\prime}} \cdot q_1^{b_1 - b_1^{\prime}} \ldots q_r^{b_r - b_r^{\prime}}

   ma per ipotesi \frac{s}{n} \in A, cioè deve avere solo fattori primi di N, quindi i fattori q_1, \ldots, q_r devono avere esponente nullo. Quindi:

   \begin{aligned} n \mid s, \frac{s}{n} \in A & \Rightarrow \\ b_1 = b_1^{\prime}, \ldots, b_r = b_r^{\prime} & \Rightarrow \\ q_1^{b_1^{\prime}} \ldots q_r^{b_r^{\prime}} = q_1^{b_1} \ldots q_r^{b_r} & \Rightarrow \\ b^{\prime} = b & \Rightarrow \\ d(b^{\prime}) = d(b) \end{aligned} \tag{k}

   Partendo dalla (i) abbiamo dimostrato che d(s, N) = d(b); allo stesso modo, partendo dalla (j), possiamo dimostrare che d(n, N) = d(b^{\prime}). Quindi, per la (k), d(n, N) = d(s, N).

   Consideriamo l’ultima riga della (g):

   \frac{1}{10} \cdot \left( d(\colorbox{aqua}{1}, 20) + d(\colorbox{aqua}{2}, 20) + d(\colorbox{aqua}{5}, 20) + d(\colorbox{aqua}{10}, 20) \right)

   I numeri evidenziati sono gli n dell’ipotesi, ossia i divisori di s = 10 tali che \frac{s}{n} \in A. Questo terzo punto ci sta dicendo, per tutti questi numeri, il numero di divisori coprimi con N = 20 è uguale al numero di divisori di s = 10 coprimi con N = 20.
   In effetti, l’unico divisore di 10 coprimo con 20 è 1, e lo stesso si può dire per 1, 2, 5 e 10: l’unico divisore coprimo con 20 di ciascuno di essi è 1, perché sono tutti divisori di 20.

   Analizziamo ora quest’altra riga:

   \frac{1}{6} \cdot \left( d(\colorbox{aqua}{3}, 20) + d(\colorbox{aqua}{6}, 20) \right)

   In questo caso i divisori di s = 6 coprimi con 20 sono 1 e 3, per un totale di 2, quindi d(s, 20) = d(6, 20) = 2. Possiamo osservare che anche per i due n evidenziati si ha che d(n, 20) = d(s, 20): per n = 6 ciò è ovvio perché n = s, ma la formula vale anche per l’altro n che è 3; infatti, entrambi i divisori di 3 sono coprimi con 20.

4. Dalla (j) e dalla (k) abbiamo che:

   \begin{aligned} n \mid s, \frac{s}{n} \in A & \Rightarrow \\ b^{\prime} = b & \Rightarrow \\ n = \underbrace{p_1^{a_1^{\prime}} \ldots p_k^{a_k^{\prime}}}_{a^{\prime}} \cdot \underbrace{q_1^{b_1} \ldots q_r^{b_r}}_{b} \end{aligned}

   Ma b è fisso, perché dipende solo da s che è stato fissato inizialmente, quindi il numero di possibili n è pari al numero di possibili a^{\prime}. Questi ultimi, per come è stato definito n, sono i possibili divisori di a; quindi, per transitività, possiamo concludere che il numero di possibili n è d(a).

   Questo quarto punto ci dice quanti addendi ci sono dentro le parentesi in ogni riga della (g), perché ogni addendo è associato a un diverso valore di n. Ad esempio, analizziamo di nuovo questa riga:

   \frac{1}{10} \cdot \left( d(1, 20) + d(2, 20) + d(5, 20) + d(10, 20) \right)

   Osserviamo che ci sono 4 termini tra parentesi: secondo quanto abbiamo dimostrato, anche i divisori di a dovrebbero essere 4, dove a è quella parte della fattorizzazione di s = 10 che comprende solo i fattori primi di N = 20. In questo caso a = 10 perché tutti i fattori primi di s sono anche fattori primi di N, ed effettivamente 10 ha 4 divisori.

   Ora analizziamo quest’altra riga:

   \frac{1}{6} \cdot \left( d(3, 20) + d(6, 20) \right)

   In questo caso s = 6. Per capire il valore di a, fattorizziamo 6 come nella (i), separando i fattori che dividono N = 20 da quelli che non lo dividono:

   6 = \underbrace{2}_{a} \cdot \underbrace{3}_{b}

   Quindi a = 2, che ha 2 divisori. Ciò è in accordo col quarto punto, perché effettivamente nella riga abbiamo trovato 2 termini dentro le parentesi.

In base ai quattro punti dimostrati, possiamo concludere che:

Riprendendo la (e) e la (f), abbiamo quindi:

La sommatoria \sum_{s \lt z} \frac{d(s)}{s} ha un ordine asintotico noto; in particolare, per la Proposizione N.31, \sum_{s \lt z} \frac{d(s)}{s} \gg \log^2 z. Quindi:

da cui:

Applicando la Proprietà A.27, abbiamo:

Il termine della produttoria può essere riscritto come segue:

Sostituendo nella (l), abbiamo:

Ora, in analogia con la formula (d), utilizzando la stessa logica della dimostrazione della Proprietà A.26, si può dimostrare che:

dove:

Ma i numeri che nella loro fattorizzazione hanno solo fattori primi con esponente pari sono i quadrati, per cui:

In particolare, questo insieme Q è un sottoinsieme dell’insieme di tutti i numeri che sono quadrati, per cui sicuramente la serie \sum_{q \in Q} \frac{1}{q} è minore o uguale della serie dei reciproci di tutti i quadrati, ossia \sum_{n \geq 1} \frac{1}{n^2}. Quindi, partendo dalla (n), abbiamo:

Ma quest’ultima serie, com’è possibile dimostrare, è convergente, perché l’esponente di n è strettamente maggiore di 1. Essa ha quindi una somma finita L \in \mathbb{R}. Quindi, per la (o), anche la produttoria è limitata dallo stesso L:

Ciò rende la produttoria irrilevante dal punto di vista asintotico; essa può quindi essere eliminata dalla (m), ottenendo:

Abbiamo così completato la dimostrazione.

Dato che d \mid P(z), la fattorizzazione di d è un prodotto di primi distinti, che possiamo suddividere tra quelli che dividono N e quelli che non dividono N. Poniamo quindi d := q_1 \ldots q_k p_1 \ldots p_r, dove q_1, \ldots, q_k sono divisori di N; p_1, \ldots, p_r non dividono N; k, r \geq 0.

Consideriamo l’insieme A_d. Per ipotesi, esso è l’insieme dei multipli di d presenti nella famiglia A, ossia l’insieme di tutti gli interi n \leq N tali che d \mid n(N - n). Sotto forma di congruenza, l’ultima relazione può essere scritta come n(N - n) \equiv 0\ \textrm{(mod }d\textrm{)}. Essendo d = q_1 \ldots q_k p_1 \ldots p_r, questa congruenza equivale al sistema di congruenze:

Per quanto riguarda le prime k congruenze, per ogni q_i \in \{q_1, \ldots, q_k\}, essendo q_i primo, si ha che n(N - n) \equiv 0 \textrm{ (mod }q_i\textrm{)} se e solo se n \equiv 0 \textrm{ (mod }q_1\textrm{)} oppure (N - n) \equiv 0 \textrm{ (mod }q_i\textrm{)}. Possiamo osservare però che queste due congruenze sono equivalenti. Infatti, dato che q_i \mid N, la seconda congruenza è equivalente a - n \equiv 0 \textrm{ (mod }q_i\textrm{)} che a sua volta è equivalente a n \equiv 0 \textrm{ (mod }q_i\textrm{)}, che corrisponde alla prima congruenza. Quindi possiamo concludere che:

Per quanto riguarda le ultime r congruenze, per ogni p_j \in \{p_1, \ldots, p_r\}, essendo esso primo, si ha che n(N - n) \equiv 0 \textrm{ (mod }p_j\textrm{)} se e solo se n \equiv 0 \textrm{ (mod }p_j\textrm{)} oppure (N - n) \equiv 0 \textrm{ (mod }p_j\textrm{)}; questa volta le due congruenze ottenute non sono equivalenti, perché dalla seconda si ottiene n - N \equiv 0 \textrm{ (mod }p_j\textrm{)} che a sua volta equivale a n \equiv N \textrm{ (mod }p_j\textrm{)}, che non è equivalente alla prima congruenza perché per ipotesi N \not \equiv 0 \textrm{ (mod }p_j\textrm{)}. Quindi in questo caso abbiamo due soluzioni distinte modulo p_j:

Sostituendo nella (a), abbiamo:

A seconda se scegliamo 0 oppure N in ciascuna delle ultime r congruenze, otteniamo un sistema di congruenze del tipo:

dove a_1, \ldots, a_r \in \{0, N\}. Le soluzioni del sistema (a) saranno quindi date dall’unione delle soluzioni di ciascun sistema (b), al variare di a_1, \ldots, a_r \in \{0, N\}. Essendoci due possibili scelte per ogni a_i \in \set{a_1, \ldots, a_r}, i sistemi del tipo (b) sono in totale 2^r. Ciascuno di essi, per il Teorema cinese del resto, individua un’unica soluzione modulo d (essendo d = q_1 \ldots q_k p_1 \ldots p_r). Possiamo concludere quindi che il sistema (a) ammette 2^r soluzioni modulo d, che possiamo indicare, utilizzando la notazione delle classi di equivalenza, come [\alpha_1], \ldots, [\alpha_{2^r}], con 0 \leq \alpha_1, \ldots, \alpha_{2^r} \lt d. In altri termini, possiamo dire che d \mid n(N - n) per tutti gli interi n che divisi per d hanno un resto appartenente all’insieme \set{\alpha_1, \ldots, \alpha_{2^r}}. Quindi possiamo calcolare |A_d| come segue:

dove nell’ultimo passaggio si è osservato che gli insiemi dell’unione sono tutti disgiunti, perché gli \alpha_i rappresentano classi di resto distinte.
L’insieme \set{n \leq N \textrm{\ tale che\ } n \equiv \alpha_i \textrm{ (mod }d\textrm{)}} contiene tutti gli interi compresi tra 1 ed N che sono congrui a \alpha_i modulo d. Per calcolarne la cardinalità, dividiamo N per d, ottenendo N = \left\lfloor \frac{N}{d} \right\rfloor d + h, dove abbiamo indicato con \left\lfloor \frac{N}{d} \right\rfloor la parte intera della divisione e con h il resto. Possiamo dire che certamente, qualunque sia \alpha_i, solo uno degli interi compresi tra 1 e d sarà congruo ad esso modulo d; lo stesso si può dire per gli interi compresi tra d + 1 e 2d, tra 2d + 1 e 3d, eccetera, fino agli interi compresi tra \left( \left\lfloor \frac{N}{d} \right\rfloor - 1\right) d + 1 e \left\lfloor \frac{N}{d} \right\rfloor d. Quindi ci sono esattamente \left\lfloor \frac{N}{d} \right\rfloor interi congrui a \alpha_i compresi tra 1 e \left\lfloor \frac{N}{d} \right\rfloor d. Ma N = \left\lfloor \frac{N}{d} \right\rfloor d + h, quindi restano da analizzare gli interi compresi tra \left\lfloor \frac{N}{d} \right\rfloor d + 1 e \left\lfloor \frac{N}{d} \right\rfloor d + h. Non possiamo dire esattamente quanti di questi interi sono congrui ad \alpha_i, però possiamo dire che ce ne potrà essere al massimo uno solo, perché, per lo stesso principio di prima, ce n’è esattamente uno compreso tra \left\lfloor \frac{N}{d} \right\rfloor d + 1 e \left\lfloor \frac{N}{d} \right\rfloor d + d \gt \left\lfloor \frac{N}{d} \right\rfloor d + h. Quindi il massimo numero di interi compresi tra 1 ed N che sono congrui a \alpha_i modulo d è \left\lfloor \frac{N}{d} \right\rfloor + 1. Allora:

dove nell’ultimo passaggio abbiamo applicato il Corollario 1 della Proprietà A.8 (osserviamo che 2^r va trattato come una funzione non costante, in quanto r dipende da N).
Ma \frac{2^r}{d} è proprio il valore di f(d), infatti:

Infatti, come abbiamo già osservato in precedenza, la f utilizzata nel crivello di Goldbach è stata definita proprio in modo tale da stimare con più precisione possibile le cardinalità degli insiemi A_d.

Dalle formule (c), (d) ed (e) possiamo concludere che:

Utilizzando questa disuguaglianza possiamo calcolare r(d), concludendo la dimostrazione:

dove nell’ultimo passaggio si è osservato che r \leq r + k = \omega(d).

Come si trovano i valori \frac{a}{b} := \frac{1}{8} e \alpha := 0,9?

Cominciando dalla seconda relazione, si può osservare che 2 + 2 \log_2 6 = 7,169\ldots, per cui ad esempio moltiplicando questo numero per \frac{1}{8} si ottiene un numero minore di 1; in particolare \frac{1}{8} \left(2 + 2 \log_2 6\right) \lt 0,9. Quindi possiamo porre \frac{a}{b} := \frac{1}{8} e \alpha := 0,9, ottenendo che \frac{a}{b} \left(2 + 2 \log_2 6\right) \lt \alpha e quindi N^{\frac{a}{b} \left(2 + 2 \log_2 6\right)} \ll N^{\alpha}.
Infine, i valori trovati per \frac{a}{b} e \alpha soddisfano anche la prima relazione; infatti, essendo \frac{a}{b} \lt \alpha, si ha che N^{\frac{a}{b}} \ll N^{\alpha} e quindi, per il Corollario 2 della Proprietà A.8, 2 N^{\frac{a}{b}} \ll N^{\alpha}.