La congettura di Cramér

La congettura di Cramér afferma che la differenza tra due numeri primi consecutivi \( p_n \)  e \( p_{n+1} \) soddisfa la seguente disuguaglianza asintotica: $$ p_{n+1} - p_n = O((\log p_n)^2) $$

In altre parole, la differenza tra due numeri primi consecutivi è, al massimo, proporzionale al quadrato del logaritmo naturale del primo numero \( p_n \) e individua un intervallo entro il quale si trova il successivo numero primo.

Quindi, le lacune tra due numeri consecutivi (cioè \( p_{n+1} - p_n \)) non crescono più velocemente di \( (\log p_n)^2 \), anche se possono diventare arbitrariamente grandi.

Nota. Questa ipotesi è stata proposta da Harald Cramér nel 1936. Permette di analizzare la distribuzione dei numeri primi ed è strettamente collegata alle lacune tra numeri primi consecutivi. La congettura di Cramér è supportata da evidenze numeriche. Tuttavia, rimane irrisolta perché non è stata ancora dimostrata. Se vera, fornirebbe una descrizione precisa della distribuzione dei numeri primi e sarebbe uno dei risultati più significativi della teoria analitica dei numeri.

La congettura di Cramér afferma che la distanza tra due numeri primi consecutivi \( p_{n+1} - p_n \) è limitata da \( O((\log p_n)^2) \), ma non specifica dove si trova esattamente il prossimo numero primo.

In altre parole, la congettura fornisce un limite massimo asintotico, non una regola per determinare la posizione del prossimo primo.

Esempio pratico

Considero il terzo numero primo  \( p_3 = 5 \)

$$ p_3 = 5 $$

Calcolo il quadrato del logaritmo naturale di 5 ovvero \( (\log 5)^2 \approx 2.59 \).

$$ p_{n+1} - p_n = O((\log p_n)^2) $$

$$ p_{4} - 5 = O((\log 5)^2) $$

$$ p_{4} - 5 = O(2.59) $$

Questo vuole dire che il numero primo successivo è compreso nell'intervallo (5 , 5+2.59) ovvero (5, 7.59)

Effettivamente il numero primo successivo è $ p_4 = 7 $ con \( p_4 - p_3 = 2 \), che è molto minore di \( (\log 5)^2 = 2.59 \).

Esempio 2

Considero il numero primo

$$ p_n = 101 $$

Calcolo il quadrato del logaritmo naturale di 101 ovvero \( (\log 101)^2 \approx 21.31 \).

$$ p_{n+1} - p_n = O((\log p_n)^2) $$

$$ p_{n+1} - 101 = O((\log 101)^2) $$

$$ p_{n+1} - 101 = O(21.31) $$

Questo significa che il numero primo successivo è compreso nell'intervallo (101, 101+21.31) ovvero (101, 122.31)

In questo caso il numero primo successivo è $p_{n+1} = 103 $ con \( p_{n+1} - p_n = 2 \), che è molto minore di \( (\log 101)^2 = 21.31 \).

Nota. Nell'intervallo $ (101,122.31) $ sono presenti diversi numeri primi: $ 103, 107, 109, 113 $. Il più piccolo è $ p_{n+1} = 103 $. La congettura di Cramer è comunque rispettata perché la differenza tra i due numeri primi consecutivi $ 103 - 101 = 2 $ è inferiore al quadrato del logaritmo di 101 ovvero di \( (\log 101)^2 = 21.31 \).

Note a margine

Alcune note e osservazioni personali.

• La congettura di Cramér non è il miglior metodo diretto per trovare il numero primo successivo
  La congettura di Cramér non è ottimale per determinare il numero primo successivo, poiché richiede comunque un algoritmo di verifica della primalità per escludere i numeri composti nell'intervallo. Inoltre, sebbene la congettura sia supportata da evidenze numeriche, non è dimostrata. Potrebbero esistere casi estremi (per numeri enormemente grandi) che violano la stima. Pertanto, la congettura di Cramér è utile per stimare una fascia in cui cercare il prossimo numero primo e per analisi teoriche, ma per calcoli esatti e pratici del numero primo successivo, è meglio utilizzare altri algoritmi espliciti per testare la primalità.

  Nota. Per cercare il numero primo successivo di $ p_n $ (con $ p_n > 2 $) è preferibile fare il test di primalità direttamente sui numeri dispari successivi $ p_n + 2 $ usando un algoritmo efficiente come il test di divisione fino a \( \sqrt{n} \) o metodi avanzati come Miller-Rabin. Ad esempio, secondo la congettura d Cramer il numero primo successivo di $ 101 $ è compreso nell'intervallo $ (101, 122.31) $. E' però sufficiente testare la primalità dei dispari successivi a $ p_n=101 $ per scoprire che il numero primo successivo è $ p_{n+1} = 103 $, senza dover necessariamente calcolare l'intervallo.

E così via.