Il postulato di Bertrand

Prerequisiti:

Medaglia che ritrae Joseph Louis François Bertrand, opera dello scultore Jules-Clément Chaplain

Lo scopo che ci poniamo adesso è dimostrare il postulato di Bertrand, proposto nel 1845 dal matematico francese Joseph Louis François Bertrand sotto forma di congettura, e successivamente dimostrato dal russo Pafnutij L’vovič Chebyshev:

Postulato di Bertrand

Per ogni n > 0, esiste un numero primo compreso tra n + 1 e 2n.

L’enunciato del teorema può essere rappresentato graficamente come segue:

Postulato di Bertrand: per ogni n > 0, esiste un numero primo compreso tra n + 1 e 2n.

Dei numeri primi compresi tra n + 1 e 2n, oggetto del teorema, abbiamo già parlato quando abbiamo analizzato il prodotto dei primi numeri primi. In quell’occasione siamo partiti con l’esempio dei prodotto dei numeri primi compresi tra 11 e 20: abbiamo visto che si può ottenere una stima per eccesso di questo prodotto attraverso il binomiale \binom{20}{10}; infatti in questa espressione i numeri al denominatore si semplificano con diversi fattori al numeratore, lasciando alla fine il prodotto che ci interessa moltiplicato per qualche fattore aggiuntivo:

\binom{20}{10} = \tag{1}
\frac{20!}{10! \cdot 10!} =
\frac{\mathbf{11} \cdot 12 \cdot \mathbf{13} \cdot 14 \cdot 15 \cdot 16 \cdot \mathbf{17} \cdot 18 \cdot \mathbf{19} \cdot 20}{10!} =
\frac{\mathbf{11} \cdot 12 \cdot \mathbf{13} \cdot 14 \cdot 15 \cdot 16 \cdot \mathbf{17} \cdot 18 \cdot \mathbf{19} \cdot 20}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10} =
\frac{\mathbf{11} \cdot 2 \cdot 6 \cdot \mathbf{13} \cdot 2 \cdot 7 \cdot 3 \cdot 5 \cdot 2 \cdot 8 \cdot \mathbf{17} \cdot 2 \cdot 9 \cdot \mathbf{19} \cdot 4 \cdot 5}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 2 \cdot 5} =
\frac{\mathbf{11} \cdot \cancel{2} \cdot \cancel{6} \cdot \mathbf{13} \cdot \cancel{2} \cdot \cancel{7} \cdot \cancel{3} \cdot \cancel{5} \cdot 2 \cdot \cancel{8} \cdot \mathbf{17} \cdot 2 \cdot \cancel{9} \cdot \mathbf{19} \cdot \cancel{4} \cdot \cancel{5}}{1 \cdot \cancel{2} \cdot \cancel{3} \cdot \cancel{4} \cdot \cancel{5} \cdot \cancel{6} \cdot \cancel{7} \cdot \cancel{8} \cdot \cancel{9} \cdot \cancel{2} \cdot \cancel{5}} = \tag{2}
\mathbf{11} \cdot \mathbf{13} \cdot 2 \cdot \mathbf{17} \cdot 2 \cdot \mathbf{19} =
\mathbf{11} \cdot \mathbf{13} \cdot \mathbf{17} \cdot \mathbf{19} \cdot 4 \tag{3}

Abbiamo poi sviluppato questa tecnica fino ad ottenere una stima del prodotto di tutti i numeri primi fino ad un certo numero x. Ora partiamo dallo stesso punto ma, analizzando la questione in maniera diversa, arriveremo alla dimostrazione del postulato di Bertrand.

Generalizzando la (1), notiamo che siamo partiti dal binomiale \binom{2n}{n} ed abbiamo ottenuto, alla fine, il prodotto dei numeri primi compresi tra n + 1 e 2n, per qualche altro fattore più piccolo. Il postulato di Bertrand afferma che esiste almeno un numero primo compreso tra n + 1 e 2n: ciò significa che nel passaggio finale, dopo la semplificazione del passaggio (2), dobbiamo trovare almeno un fattore primo maggiore di n. Ma, risalendo le equazioni fino alla (1), vediamo che il passaggio finale non è altro che la scomposizione in fattori primi del numero di partenza, il binomiale \binom{2n}{n}: quindi stiamo dicendo che questo numero, che d’ora in poi chiameremo N, ha almeno un fattore primo maggiore di n. Quindi possiamo vedere il postulato di Bertrand come un teorema sulla fattorizzazione del numero N. Poiché ci interessa quali fattori primi compaiono e quali non compaiono in questa fattorizzazione, possiamo scrivere il passaggio (3) introducendo, con esponente nullo, anche i fattori primi mancanti:

2^2 \cdot 3^0 \cdot 5^0 \cdot 7^0 \cdot \mathbf{11}^1 \cdot \mathbf{13}^1 \cdot \mathbf{17}^1 \cdot \mathbf{19}^1

A questo punto possiamo chiamare k_p l’esponente del fattore primo p in questa particolare fattorizzazione, nella quale compaiono tutti i primi fino a 2n, ossia:

k_2 = 2,\: k_3 = 0,\: k_5 = 0,\: k_7 = 0,\: k_{11} = 1,\: k_{13} = 1,\: k_{17} = 1,\: k_{19} = 1

Allora, riformulando il postulato di Bertrand, possiamo dire che almeno un primo q maggiore di n ha esponente k_q > 0.

Analizziamo in dettaglio questo numero k_p: cosa possiamo dire su di esso, dato p? Con un ragionamento interessante, ma piuttosto articolato, si dimostra il seguente Lemma, che stabilisce una soglia superiore:

Fattorizzazione del binomiale \binom{2n}{n}

Nella fattorizzazione del binomiale \binom{2n}{n}, per n > 0, un numero primo p non può avere un esponente maggiore di \log_p 2n.

Cominciamo con un esempio: vediamo perché, per p = 2, k_2 = 2.
Il 2 è un fattore primo molto comune, anche in numeri piccoli come quelli del nostro esempio: tra 1 e 10 esistono esattamente 5 multipli di 2, ma esistono anche numeri che sono multipli di una potenza di 2, cioè che contengono il fattore 2 più volte, come 8 = 2^3 o 12 = 3^2 \cdot 3. Proviamo a censire, per tutti i numeri da 1 a 20, quante volte contengono il fattore primo 2, ossia qual è l’esponente del 2 nella loro fattorizzazione:

Tabella 1: Esponente del 2 nella fattorizzazione in fattori primi dei numeri i compresi tra 1 e 20
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Esponente del 2 nella fattorizzazione 0 1 0 2 0 1 0 3 0 1 0 2 0 1 1 4 0 1 0 2

Visti così, gli esponenti del 2 sembrano seguire una legge caotica, ma tutto appare molto più chiaro se distinguiamo il 2 dalle sue potenze. Invece di chiederci quante volte compare il 2 nella fattorizzazione del numero i, ci poniamo quattro domande diverse:

  • 2 \mid i?
  • 4 \mid i?
  • 8 \mid i?
  • 16 \mid i?

A ciascuna di queste domande rispondiamo 0 se la risposta è negativa; 1 se la risposta è positiva. Alla fine, se sommiamo tutte e quattro le risposte, otteniamo proprio l’esponente del 2 nella fattorizzazione di i. Ad esempio, per i = 8 si ha:

  • 2 \mid 8? 1
  • 4 \mid 8? 1
  • 8 \mid 8? 1
  • 16 \mid 8? 0

Alla fine si ottiene 1 + 1 + 1 + 0 = 3, che è proprio l’esponente del 2 nella fattorizzazione di 8, infatti 8 = 2^3. Naturalmente si potrebbe andare all’infinito con queste domande, considerando potenze di 2 sempre maggiori, ma in questo caso i \leq 20 e 16 è la più grande potenza di 2 minore o uguale a 20, perciò non ha senso andare oltre: anche se lo facessimo, le risposte sarebbero sempre negative, ed avremmo una somma di infiniti zeri. Riscriviamo in questo modo la Tabella 1:

Tabella 2: potenze di 2 che dividono i numeri i compresi tra 1 e 20
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2 \mid i? 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
4 \mid i? 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
8 \mid i? 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
16 \mid i? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0

Per quanto abbiamo detto, la singola riga della Tabella 1 è pari alla somma delle righe della Tabella 2, come è semplice verificare.
Guardando la Tabella 2 si osserva finalmente una regolarità: su ciascuna riga, gli 0 e gli 1 si alternano in modo regolare: uno 0 seguito da un 1 nella prima riga, 3 zeri seguiti da un 1 nella seconda, e così via. Questa regolarità ci tornerà molto utile tra poco.
Chi ha familiarità coi tratteggi può riconoscere nella Tabella 2 la rappresentazione di un tratteggio lineare. In particolare la rappresentazione di questo tratteggio coincide con le prime quattro righe della tabella che si ottiene col visualizzatore di tratteggi per n = 20 selezionando l’opzione “Numeri primi minori o uguali a n e loro potenze”.

Torniamo ora al binomiale (1). Lo possiamo riscrivere come segue, focalizzandoci sul numero 2:

\frac{\mathbf{11} \cdot 12 \cdot \mathbf{13} \cdot 14 \cdot 15 \cdot 16 \cdot \mathbf{17} \cdot 18 \cdot \mathbf{19} \cdot 20}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10} =
\frac{\mathbf{11} \cdot 2 \cdot 2 \cdot 3 \cdot \mathbf{13} \cdot 2 \cdot 7 \cdot 15 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot \mathbf{17} \cdot 2 \cdot 9 \cdot \mathbf{19} \cdot 2 \cdot 2 \cdot 5}{1 \cdot 2 \cdot 3 \cdot 2 \cdot 2 \cdot 5 \cdot 2 \cdot 3 \cdot 7 \cdot 2 \cdot 2 \cdot 2 \cdot 9 \cdot 2 \cdot 5}

Il numero dei 2 che rimarranno alla fine, dopo la semplificazione, è il numero dei 2 presenti al numeratore, meno il numero di quelli presenti al denominatore. Ma ora possiamo contare quanti sono basandoci sulla Tabella 2. Per contare i 2 al numeratore, per esempio, sommiamo tutte le colonne dalla 11 alla 20, ottenendo:

(0 + 0 + 0 + 0) + (1 + 1 + 0 + 0) + (0 + 0 + 0 + 0) +
(1 + 0 + 0 + 0) + (0 + 0 + 0 + 0) + (1 + 1 + 1 + 1) +
(0 + 0 + 0 + 0) + (1 + 0 + 0 + 0) + (0 + 0 + 0 + 0) + (1 + 1 + 0 + 0) =
0 + 2 + 0 + 1 + 0 + 4 + 0 + 1 + 0 + 2 =
10

Analogamente possiamo contare i 2 al denominatore sommando le colonne da 1 a 10:

(0 + 0 + 0 + 0) + (1 + 0 + 0 + 0) + (0 + 0 + 0 + 0) +
(1 + 1 + 0 + 0) + (0 + 0 + 0 + 0) + (1 + 0 + 0 + 0) +
(0 + 0 + 0 + 0) + (1 + 1 + 1 + 0) + (0 + 0 + 0 + 0) + (1 + 0 + 0 + 0) =
0 + 1 + 0 + 2 + 0 + 1 + 0 + 3 + 0 + 1 =
8

Per cui alla fine, dopo la semplificazione, il numero di fattori 2 che resteranno, che abbiamo chiamato k_2, sarà 10 - 8 = 2.

Fin qui abbiamo solo espresso in maggior dettaglio, relativamente al 2, quello che succede nel passaggio (3), ma ora possiamo fare un salto di qualità. Lo stesso risultato, infatti, può essere ottenuto sommando la Tabella 2 non per colonne, ma per righe. Ciò significa che, per avere il numero dei 2 al numeratore, sommiamo le porzioni di righe della Tabella 2 che sono comprese tra la colonna 11 e la colonna 20:

(0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1) + (0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 1) +
(0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0) + (0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0) = \tag{4}
5 + 3 + 1 + 1 =
10

Analogamente, per avere il numero dei 2 al denominatore, sommiamo le porzioni di righe della Tabella 2 che sono comprese tra la colonna 1 e la colonna 10:

(0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1) + (0 + 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0) +
(0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0) + (0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0) = \tag{5}
5 + 2 + 1 + 0 =
8

Quindi la differenza tra questi due numeri, k_2, può essere ottenuta sottraendo membro a membro la (5) dalla (4):

k_2 =
10 - 8 =
\left(5 - 5\right) + (3 - 2) + (1 - 1) + (1 - 0) =
\left((0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1) - (0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1)\right) + \tag{6}
\left((0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 1) - (0 + 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0)\right) +
\left((0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0) - (0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0)\right) +
\left((0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0) - (0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0)\right)

Ciò significa, in pratica, sottrarre per righe la parte sinistra della Tabella 2 (colonne 1-10) dalla parte destra (colonne 11-20). Ma conosciamo le posizioni degli 1 nella Tabella 2: sulla prima riga, gli 1 si trovano nelle colonne che sono multiple di 2, nella seconda riga si trovano nelle colonne multiple di 4, eccetera. Quindi l’espressione (6) può essere riscritta come:

k_2 =
\left(\begin{aligned}(\text{numero di multipli di 2 compresi tra 11 e 20}) -\\ (\text{numero di multipli di 2 compresi tra 1 e 10})\end{aligned}\right) + \tag{7}
\left((\text{numero di multipli di 4 compresi tra 11 e 20}) - (\text{numero di multipli di 4 compresi tra 1 e 10})\right) +
\left((\text{numero di multipli di 8 compresi tra 11 e 20}) - (\text{numero di multipli di 8 compresi tra 1 e 10})\right) +
\left((\text{numero di multipli di 16 compresi tra 11 e 20}) - (\text{numero di multipli di 16 compresi tra 1 e 10})\right)

Entrambi gli insiemi \{1, \dots, 10\} e \{11, \dots, 20\} sono composti da 10 interi consecutivi. In generale, il numero di multipli di un certo numero m (non necessariamente primo) in un insieme di h numeri consecutivi è soggetto ad una limitazione ben precisa:

\left \lfloor \frac{h}{m} \right \rfloor \leq \left(\begin{aligned}\text{numero di multipli di } m \\ \text{ compresi in un intervallo di } h \text{ numeri consecutivi}\end{aligned}\right) \leq \left \lceil \frac{h}{m} \right \rceil \tag{8}

In particolare, se l’intervallo è del tipo \{1, \dots, h\}, vale l’uguaglianza a sinistra:

\left \lfloor \frac{h}{m} \right \rfloor = (\text{numero di multipli di } m \text{ compresi tra 1 ed } h) \tag{9}

La dimostrazione di queste formule meriterebbe un discorso a parte, ma per il momento ci limitiamo ad applicarle.
Sottraendo membro a membro la (8) dalla (9) abbiamo che:

0 \leq \left( \begin{aligned}(\text{numero di multipli di } m \text{ compresi in un intervallo di } h \text{ numeri consecutivi}) \\ -(\text{numero di multipli di } m \text{ compresi tra 1 ed } h) \end{aligned} \right) \leq \left \lceil \frac{h}{m} \right \rceil - \left \lfloor \frac{h}{m} \right \rfloor

Da qui, essendo \left \lceil \frac{h}{m} \right \rceil - \left \lfloor \frac{h}{m} \right \rfloor \leq 1, otteniamo:

0 \leq \left(\begin{aligned}(\text{numero di multipli di } m \text{ compresi in un intervallo di } h \text{ numeri consecutivi}) \\ -(\text{numero di multipli di } m \text{ compresi tra 1 ed } h)\end{aligned} \right) \leq 1 \tag{10}

La quantità al centro è perfettamente sovrapponibile con ciascun addendo della (7), ponendo h = n = 10 ed m = una potenza di p = 2. Sostituendo nella (7) abbiamo quindi:

k_2 \leq 1 + 1 + 1 + 1

Qui stiamo contando un 1 per ciascuna riga della Tabella 2, per cui la somma che si ottiene è il numero di righe della tabella. Essa ha 4 righe, perché 2^4 è la massima potenza di 2 (il primo p che abbiamo scelto) minore o uguale a 20 (cioè 2n). Da 2^4 \leq 20 otteniamo, calcolando il logaritmo da ambo le parti, 4 \leq \log_2 20. Riassumendo, abbiamo quindi che

k_2 \leq \text{numero di righe della Tabella 2} \leq \log_2 20

Il discorso fatto fin qui per p = 2 e 2n = 20 può essere facilmente generalizzato per ogni p e per ogni n, ottenendo il Lemma N.1.

Ora che abbiamo capito quali esponenti possono avere i fattori primi di N = \binom{2n}{n}, resta da capire meglio quali possono essere questi fattori. Come abbiamo osservato all’inizio, sono tutti minori o uguali a 2n, pertanto possiamo ripartirli in due sottoinsiemi, chiamando P quelli compresi tra n+1 e 2n, e Q quelli più piccoli. Ma nell’articolo Il prodotto dei primi numeri primi abbiamo visto che tutti i numeri primi compresi tra n+1 e 2n dividono N, per cui si ha che:

\begin{aligned}P &:= \{\text{fattori primi di } N \text{ compresi tra } n + 1 \text{ e } 2n\} \\ &= \{\text{tutti i numeri primi compresi tra } n + 1 \text{ e } 2n\}\end{aligned}\tag{11}

Questa è una fondamentale uguaglianza che lega i numeri primi ai fattori primi di un numero particolare, N. Qui entra i gioco il postulato di Bertand, secondo il quale l’insieme P non può essere vuoto, ossia, per la (11), almeno un fattore primo di N deve essere maggiore di n.

Cosa possiamo dire invece sull’insieme

Q := \{\text{fattori primi di } N \text{ minori o uguali ad } n\} \tag{12}

Riprendendo la dimostrazione del Lemma N.1, si può dimostrare che, per n \geq 3, questi fattori primi non superano i due terzi di n:

\begin{aligned}Q &:= \{\text{fattori primi di } N \text{ minori o uguali ad } n\} \\ &= \{\text{fattori primi di } N \text{ minori o uguali a } \frac{2n}{3}\}\end{aligned}\tag{12'}

Consideriamo un fattore primo q \in Q, ossia q \leq n e k_q \geq 1 (quest’ultima disuguaglianza dice che q compare effettivamente, almeno con esponente 1, nella fattorizzazione di N). Adattando la (7) e tenendo conto del Lemma N.1, sappiamo che

k_q =
\left(\begin{aligned}(\text{numero di multipli di } q \text{ compresi tra } n + 1 \text{ e } 2n) -\\ (\text{numero di multipli di } q \text{ compresi tra 1 ed } n)\end{aligned} \right)+ \tag{13}
\left(\begin{aligned}(\text{numero di multipli di } q^2 \text{ compresi tra } n + 1 \text{ e } 2n) -\\ (\text{numero di multipli di } q^2 \text{ compresi tra 1 ed } n)\end{aligned}\right) +
\dots +
\left(\begin{aligned}(\text{numero di multipli di } q^{\lfloor log_q 2n \rfloor} \text{ compresi tra } n + 1 \text{ e } 2n) -\\ (\text{numero di multipli di } q^{\lfloor log_q 2n \rfloor} \text{ compresi tra 1 ed } n)\end{aligned}\right)

Quindi se k_q \geq 1, significa che almeno uno degli addendi deve essere 1 (infatti sappiamo, per la (10), che sono tutti o 0 o 1). Supponiamo che il primo addendo sia 1. Notiamo che il termine (\text{numero di multipli di } q \text{ compresi tra 1 ed } n) è almeno 1, perché q \leq n, quindi se la differenza (13) deve essere almeno 1, vuol dire che il primo termine deve essere almeno 2:

\left(\begin{aligned}\text{numero di multipli di } q \text{ compresi tra } n + 1 \text{ e } 2n) -\\ (\text{numero di multipli di } q \text{ compresi tra 1 ed } n)\end{aligned}\right) \geq 2 - 1

Quindi esisterebbero (supponendo 1 il primo addendo) almeno 2 multipli di q compresi tra n + 1 e 2n, ed un altro compreso tra 1 ed n: in totale 3 multipli di q minori o uguali di 2n, per cui

3q \leq 2n \tag{14}

Se supponessimo che gli altri addendi siano 1, giungeremmo alla stessa conclusione. Infatti, per ottenere 1, i termini di destra come (\text{numero di multipli di } q^2 \text{ compresi tra } n + 1 \text{ e } 2n) devono essere almeno 1, ed in questo caso sarebbe q^2 \leq 2n, q^3 \leq 2n, eccetera. Tutte queste condizioni implicano che 3q \leq 2n per q \geq 3, essendo 3q \leq q^2 \leq q^3 \leq \dots. Per q = 2 non è vero che 3q \leq q^2, ma in questo caso possiamo facilmente soddisfare la (14) supponendo n \geq 3: non è un problema perché ci interessa capire cosa succede per n grandi; per n piccoli, qualunque proprietà può essere verificata direttamente.
Allora la (12), per n \geq 3, si può riscrivere come (12′).

Ora, avendo ripartito i fattori primi di N tra gli insiemi P e Q, possiamo scrivere:

N = \prod_{q \in Q} q^{k_q} \cdot \prod_{p \in P} p^{k_p} \tag{15}

A partire da questa formula si sviluppa la parte conclusiva della dimostrazione. Il punto fondamentale è che, se il postulato di Bertrand fosse falso, l’insieme P sarebbe vuoto, quindi rimarrebbe solo il primo prodotto:

N = \prod_{q \in Q} q^{k_q} \text{ (se il postulato fosse falso)}

Ma, avendo trovato una soglia superiore per gli elementi di Q con la (12′), automaticamente anche il prodotto dei suoi elementi, \prod_{q \in Q} q^{k_q} = N, non potrà andare oltre una certa soglia. Facendo i conti, si vede che per n \geq 512 il numero N è più grande della soglia di cui dovrebbe essere più piccolo, per il discorso di prima. Quindi per n \geq 512 il fatto di aver supposto falso il postulato di Bertrand porta ad una contraddizione: perciò il postulato è vero per n \geq 512.

Nella (15) possiamo ulteriormente dividere i fattori in Q tra quelli che hanno k_q = 1 e quelli che hanno k_q > 1:

N = \prod_{q \in Q, k_q = 1} q \cdot \prod_{q \in Q, k_q > 1} q^{k_q} \cdot \prod_{p \in P} p^{k_p} \tag{16}

Per capire meglio questo meccanismo, evitando inutili complicazioni simboliche, consideriamo un altro esempio. L’esempio di n = 10 che abbiamo portato avanti finora non è più sufficiente, perché in questo caso Q = \{2\} e questo è un caso troppo banale per rendere l’idea di cosa succede in generale. Consideriamo allora n = 20. In questo caso i passaggi (1) – (3) diventano:

\binom{40}{20} =
\frac{40!}{20! \cdot 20!} =
\frac{21 \cdot 22 \cdot \mathbf{23} \cdot 24 \cdot 25 \cdot 26 \cdot 27 \cdot 28 \cdot \mathbf{29} \cdot 30 \cdot \mathbf{31} \cdot 32 \cdot 33 \cdot 34 \cdot 35 \cdot 36 \cdot \mathbf{37} \cdot 38 \cdot 39 \cdot 40}{20!} =
\dots
2 \cdot 3^3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot \mathbf{23} \cdot \mathbf{29} \cdot \mathbf{31} \cdot \mathbf{37}

Separiamo, come nella (16), i primi maggiori di n = 20 da quelli minori e, tra questi ultimi, quelli con esponente 1 da quelli con esponente maggiore:

\binom{40}{20} =
\left(2 \cdot 5 \cdot 7 \cdot 11 \cdot 13\right) \cdot (3^3) \cdot \left(\mathbf{23} \cdot \mathbf{29} \cdot \mathbf{31} \cdot \mathbf{37}\right) \tag{17}

Il primo prodotto, per la (12′), è un prodotto di primi minori o uguali a \frac{2n}{3} = \frac{40}{3} = 13,3\dots, ossia minori o uguali a 13 (in questo caso l’esempio calza perfettamente con la previsione). Possiamo maggiorarlo allora con il prodotto di tutti i primi fino a 13, ossia \omega^{\star}(13), che per la Proposizione N.1, è minore o uguale a 2^{2 \cdot 12} = 2^{24}:

2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \leq 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = \omega^{\star}(13) \leq 2^{2 \cdot 12} = 2^{24}

Il prodotto seguente invece è il prodotto dei fattori primi con esponente almeno 2; nell’esempio c’è solo il fattore 3. In generale, se un primo q compare nella fattorizzazione con esponente almeno 2, vuol dire che almeno due termini della (16) sono 1, per cui almeno uno di essi è relativo ad un esponente di q compreso tra 2 e \lfloor log_q 40 \rfloor. Supponiamo, per fissare le idee, che sia 1 il termine con esponente 2:

1 = \left(\begin{aligned}(\text{numero di multipli di } q^2 \text{ compresi tra 21 e 40}) -\\ (\text{numero di multipli di } q^2 \text{ compresi tra 1 e 10})\end{aligned}\right)

Allora il membro a destra deve essere almeno 1, cioè 21 \leq q^2 \leq 40, in particolare ci interessa che q^2 \leq 40. Questo è vero a maggior ragione se fosse 1, ad esempio, il termine con esponente 3, per cui si otterrebbe, ragionando come sopra, q^3 \leq 40 e quindi di nuovo q^2 < q^3 \leq 40. Quindi q \leq \sqrt{40} = 6,3\dots. In pratica q \in {2, 3, 4, 5, 6}: possiamo dire, senza andar troppo per il sottile, supponendo di non sapere quali sono i primi, che esistono al massimo 5 valori possibili per q. Ognuno di questi q, inoltre, contribuisce alla fattorizzazione col fattore q^{k_q}, che per il Lemma N.1 è minore o uguale a q^{log_q 40} = 40. Ricapitolando, la nostra maggiorazione del secondo prodotto è la seguente:

3^3 \leq
3^{log_3 40} \leq
2^{log_2 40} \cdot 3^{log_3 40} \cdot 4^{log_4 40} \cdot 5^{log_5 40} \cdot 6^{log_6 40} =
2^{log_2 40} \cdot \dots \cdot \left \lfloor \sqrt{40} \right \rfloor^{log_{\left \lfloor \sqrt{40} \right \rfloor} 40} =
\underbrace{40 \cdot \dots \cdot 40}_{\left \lfloor \sqrt{40} \right \rfloor - 1 \text{ volte}} =
40^{\left \lfloor \sqrt{40} \right \rfloor - 1}

D’altra parte, per la Proprietà N.2, sappiamo anche che \binom{40}{20} \geq \frac{2^{40}}{40}.

Sostituendo nella (17) tutte queste stime, si ottiene:

\frac{2^{40}}{40} \leq \binom{40}{20} \leq 2^{24} \cdot 40^{\left \lfloor \sqrt{40} \right \rfloor - 1} \cdot (\mathbf{23} \cdot \mathbf{29} \cdot \mathbf{31} \cdot \mathbf{37})

A questo punto, se il postulato di Bertrand fosse falso e quindi venisse meno il terzo prodotto, ci ritroveremmo con:

\frac{2^{40}}{40} \leq 2^{24} \cdot 40^{\left \lfloor \sqrt{40} \right \rfloor - 1} \tag{18}

Quest’uguaglianza, facendo i conti, è verificata: non abbiamo trovato la contraddizione che cerchiamo. Ma non è detta l’ultima parola: dobbiamo farci un’idea di come si comportano le nostre stime al crescere di n. Generalizzando la (18), sulla base del ragionamento che abbiamo portato avanti per n = 20, si ottiene:

\frac{2^{2n}}{2n} \leq 2^{2 (\left \lfloor \frac{2n}{3} \right \rfloor - 1)} \cdot 2n^{\left \lfloor \sqrt{2n} \right \rfloor - 1}

Ebbene, questa disuguaglianza in generale è falsa. Dimostrarlo è solo una questione di calcoli, che cerchiamo di svolgere nel modo più semplice possibile. Per prima cosa eliminiamo parti intere e termini costanti che non danno grossi contributi, osservando che:

2^{2 (\left \lfloor \frac{2n}{3} \right \rfloor - 1)} \cdot 2n^{\left \lfloor \sqrt{2n} \right \rfloor - 1} \leq 2^{\frac{4n}{3}} \cdot 2n^{\sqrt{2n}}

Per cui studiamo la disuguaglianza

\frac{2^{2n}}{2n} \leq 2^{\frac{4n}{3}} \cdot 2n^{\sqrt{2n}}

Togliamo il denominatore a sinistra moltiplicando ambo i membri per 2n:

2^{2n} \leq 2^{\frac{4n}{3}} \cdot 2n^{1 + \sqrt{2n}}

Eliminiamo il denominatore all’esponente centrale elevando tutto al cubo:

2^{6n} \leq 2^{4n} \cdot 2n^{3(1 + \sqrt{2n})}

Ora possiamo semplificare dividendo per 2^{4n}:

2^{2n} \leq 2n^{3(1 + \sqrt{2n})}

Per rendere l’espressione più maneggevole numericamente, applichiamo il logaritmo in base 2 ad ambo i membri:

2n \leq 3 (1 + \sqrt{2n}) \log_2{2n}

Sebbene questa relazione sia vera per n = 3, 4, 5, 6, \dots (dobbiamo partire da 3 perché a un certo punto abbiamo supposto n \geq 3), le tecniche dell’analisi ci permettono di affermare che che il membro a sinistra cresce più velocemente del membro a destra: ciò significa che prima o poi, a partire da un certo n, la disuguaglianza non è più verificata. Facendo i conti si vede che questo n “critico” è 512. Per questa scelta di n si ottiene 2n = 2 \cdot 512 = 1024, mentre 3 (1 + \sqrt{2n}) \log_2{2n} \leq 3 (1 + 32) 10 = 990.

Ricapitolando, abbiamo visto che, se nella (16) escludiamo il prodotto \prod_{p \in P} p^{k_p}, perché supponiamo P vuoto, otteniamo una contraddizione per n \geq 512. Quindi, per tali n, P non può essere vuoto: ciò dimostra il postulato di Bertand per n \geq 512.

Per gli altri n, naturalmente, è sufficiente visionare le tavole dei numeri primi per rendersi conto che esiste sempre un primo compreso tra n + 1 e 2n. Questo completa la dimostrazione.

Lascia un commento

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