LA DISTRIBUZIONE DEI NUMERI PRIMI
 

Home Page

Storia

Algoritmi

Distribuzione

T. Numeri Primi

Ipotesi Riemann

Considerazioni

Applets JAVA

Si può costruire una tavola di tutti i numeri primi minori di un dato numero n scrivendo in ordine tutti i numeri interi minori di n, cancellando tutti i multipli di 2, tutti i multipli di 3, ecc. sino ad avere eliminato tutti i numeri composti. Questo procedimento è il noto "Crivello di Eratostene", a questo metodo se ne sono aggiunti altri più perfezionati, soprattutto dopo l'avvento dei calcolatori.

Ciò permette di avere a disposizione quantità immense di dati sui quali i matematici possono formulare congetture sulle proprietà dei primi e in particolare sulla loro distribuzione. Il passo decisivo nella ricerca della legge che descrive la distribuzione dei primi fu fatto quando i matematici rinunciarono all'inutile tentativo di trovare formule che permettessero di determinare tutti i primi o che dessero il numero esatto di primi £ n, e affrontarono il problema con un approccio che potremmo chiamare statistico o in media.
Nel seguito, indicheremo con
p(n) il numero dei primi £ ad n. Come è facile verificare:


p(1) = 0, p(2) = 1, p(3) = p(4) = 2, p(5) = p(6) = 3, p(7) = p(8) = p(9) = p(10) = 4, p(11) = p(12) = 5, ecc.


Se ora consideriamo una successione di valori n che cresca indefinitamente, (
n ® +¥), allora anche p(n) crescerà indefinitamente (si ricordi che i numeri primi sono infiniti). E' immediato constatare che la distribuzione dei primi tra gli interi è estremamente irregolare ma questa irregolarità "in piccolo" (relativa cioè alla comparsa dei singoli primi), sparisce se si considera la distribuzione media dei primi data da p(n)/n. Questo rapporto soddisfa una legge che per la sua semplicità ed eleganza è sbalorditiva. Tale legge può essere intuita e congetturata scorrendo tabelle di primi ti questo tipo:

n

p(n)/n

1/ln(n)

(p(n)/n)/(1/ln(n))

103

0,168

0,145

1,159

106

0,078498

0,072382

1,084

109

0,0050847478

0,048254942

1,053

...

...

...

...

 

Già Gauss, dopo aver studiato empiricamente tavole di primi aveva formulato la congettura che il rapporto p(n) è approssimato da n/ln(n), e anche dal numero:

 

Dove la funzione Li(n) è detta logaritmo integrale. La seguente tabella  fornisce i diversi valori delle funzioni approssimanti per valori di n fino a 100 milioni; risulta che Li(n) è un’approssimazione di p(n) migliore delle altre due.

n

p(n)

Li(n)

1000

168

172

145

178

10000

1229

1231

1086

1246

100000

9592

9588

8686

9630

1000000

78498

78534

72382

78628

10000000

664579

665138

620420

664918

100000000

5761455

5769341

5428681

5762209

 

Nel 1896 Charles de la Vallée Poussin mostrò che questo è vero per tutti i valori di n a partire da un dato punto.

Dalla tabella sembra che Li(n), sia lievemente maggiore di p(n), e se si dovesse proseguire nella tabulazione è probabile che si continuerebbe a mostrare la stessa cosa. Sarebbe da scettici non concludere che Li(n) approssima  p(n) per eccesso. Ma se si arrivasse a tale conclusione si sarebbe in errore, poiché nel 1914 il matematico inglese J. E. Littlewood (un collega di G. H. Hardy) dimostrò che la differenza Li(n) - p(n) passa da un valore positivo a uno negativo infinite volte all’aumentare di n negli interi positivi. Così, ci saranno certamente valori di n per i quali Li(n) è minore dip(n), e S. Skewes mostrò nel 1955 che un tale n dovrà apparire prima del cosiddetto numero di Skewes:

http://matmedia.ing.unina.it/Concorsi%20a%20cattedra/quesiti%2011%20gennaio%202000/soluzioni%20gruppo2/distribuzione%20dei%20primi/la_dis44.gif(approssimativamente http://matmedia.ing.unina.it/Concorsi%20a%20cattedra/quesiti%2011%20gennaio%202000/soluzioni%20gruppo2/distribuzione%20dei%20primi/la_dis45.gif),

un valore incomprensibilmente grande. Molto più piccolo, ma ancora ben al di fuori della nostra immaginazione, è il numero 1,65x101165. Nel 1966 Lehman mostrò che esso sostituisce il numero di Skewes, nel senso che Li(n) - p(n) cambierà segno per qualche valore inferiore a quel numero. Più piccolo ancora è il numero 6,69x10370, e nel 1986 Hermann J. J. de Riele dimostrò che un cambiamento di segno avverrà per qualche n al di sotto di questo limite. Ma questi sono ancora numeri estremamente grandi, e ciò ha portato a concludere che è possibile che non si arrivi mai a scoprire un numero n per il quale Li(n) sia effettivamente minore di  p(n) (quel che è certo è che una ricerca al calcolatore fatta fino a un miliardo non è approdata a nulla).

Nel 1896 i francesi J. Hadamard e C. Poussin, indipendentemente, riuscirono a dimostrare formalmente ciò che l’evidenza suggeriva: al crescere di n, il valore di n/ln si avvicina sempre più a p(n), approssimandolo con un qualunque grado di precisione richiesta, per n abbastanza grande. Ne consegue che anche Li(n) diventa arbitrariamente vicino a  p(n) al crescere di n. Questo famoso risultato, che mostra una volta per tutte che i numeri primi appaiono secondo un modello matematico definito, è noto come teorema dei numeri primi

TEOREMA DEI NUMERI PRIMI (DE LA VALLEE POUSSIN - HADAMARD)

 

Una dimostrazione rigorosa del teorema non è facile. Comunque, nel seguito cercheremo di rendere plausibile il teorema dei numeri primi utilizzando ragionamenti che, pur non fornendo una dimostrazione rigorosa, suggeriscono tuttavia la soluzione corretta e indicano la via per cercare una dimostrazione rigorosa.


Viene utilizzato un approccio probabilistico.

La probabilità che un dato intero sia divisibile per n è 1/n, infatti un numero ogni n è divisibile per n. La probabilità che un dato numero NON sia divisibile per n è allora 1 - 1/n.
Consideriamo ora i numeri primi p
i.
Facciamo ora l'ipotesi che le divisibilità per i diversi primi siano proprietà indipendenti, ciò è ovviamente falso se non si considerano numeri primi (si pensi ad esempio alla divisibilità per due e per otto).
Tenendo conto di questa indipendenza, la probabilità che un generico numero n non sia divisibile per alcun primo più piccolo è data dal prodotto:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f5c8.JPG(1)

Se n non è divisibile per alcun primo più piccolo, non è naturalmente divisibile per alcun numero più piccolo, cioè n è primo!
Applichiamo il logaritmo ad entrambi i membri di e otteniamo:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f6c8.JPG(2)

Utilizziamo ora il noto sviluppo in serie di Mac-Laurin del logaritmo e tronchiamolo al primo termine, è un'approssimazione accettabile soprattutto per i primi più grandi.

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f7c8.JPG

Sarebbe "comodo" che la somma fosse eseguita su tutti gli interi, non solo sui primi "difficili da scovare".
Per far ciò usiamo un argomento probabilistico: un dato elemento 1/p nella somma si presenta con probabilità W(p); perciò scriviamo:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f8c8.JPG(3)

Questo è un passo fondamentale perché permette di scrivere un equazione in W(n). Nel seguito vedremo come è possibile trovare la funzione incognita W.

Lavorare sul continuo (equazioni differenziali ed integrali) è più comodo che sul discreto, perciò sostituiamo in luogo di una serie un integrale, ciò è plausibile: basti pensare ai ragionamenti utilizzati per giustificare il criterio dell'integrale improprio nei criteri di convergenza delle serie.
Si ottiene:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f9c8.JPG

Vediamo di eliminare anche il segno "-" introducendo la distanza media tra due primi:

 http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f10c8.JPG

si ottiene quindi:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f11c8.JPG(4)

E, se deriviamo ambo i membri otteniamo un equazione differenziale nell'incognita A(n):

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f12c8.JPG


da cui:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f13c8.JPG

che integrata ci consente di ottenere :

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f14c8.JPG

e finalmente:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f15c8.JPG


Prendendo per buona la stima precedente della densità media dei primi, il numero dei primi
£ a n , indicato con p(n) è approssimato da:

 http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f16c8.JPG.

Tale integrale non ammette primitiva elementare, possiamo però fare questa considerazione: la funzione

 http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f17c8.JPGha come derivata: http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f18c8.JPG. Il secondo fattore è asintoticamente ininfluente rispetto al primo, perciò: http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f19c8.JPG, da cui per il Teorema Fondamentale del calcolo:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f20c8.JPG


il fattore costante si può tralasciare, perciò:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f21c8.JPG

da cui la dimostrazione dell'enunciato del teorema.

Ribadiamo che le argomentazioni precedenti NON hanno pretesa di rigore assoluto, ma suggeriscono la soluzione corretta ed indicano la via per una dimostrazione rigorosa.

LA CONGETTURA DI RIEMANN E I NUMERI PRIMI

L'ipotesi o congettura di Riemann è una congettura sulla distribuzione degli zeri nella funzione zeta di Riemann ζ(s):

Essa fu formulata la prima volta dal matematico di Gottinga Bernhard Riemann nel 1859. La sua dimostrazione risulta tuttora uno dei principali problemi aperti della matematica e figura nella lista dei sette Millennium Problems, per la soluzione di ciascuno dei quali il Clay Mathematics Institute ha offerto un premio da un milione di dollari. Sebbene la maggior parte dei matematici ritenga l'ipotesi di Riemann vera, vi sono alcune eccezioni, come quelle notevoli di J. E. Littlewood e Atle Selberg.

La funzione zeta di Riemann ζ(s) ha alcuni zeri definiti "banali" per s = - 2, s = - 4, s = - 6, ma la congettura di Riemann riguarda invece gli zeri non banali e dice che:

"La parte reale di ogni radice non banale è 1/2"

Così le radici non banali dovrebbero trovarsi tutte sulla linea critica, e sarebbero della forma s = 1/2 + it con t numero reale e i unità immaginaria.

La congettura, espressa in questo modo, potrebbe sembrare limitata alla conoscenza di questa funzione; ha invece una correlazione sottile ed importante con la teoria dei numeri primi. Eulero scoprì infatti che, effettuando la produttoria con p che spazia su tutti i numeri primi, la funzione zeta può anche essere scritta come:

dove {pj} è l'insieme di tutti i numeri primi.

L'andamento della funzione zeta (ed in particolare la distribuzione dei suoi zeri) risulta quindi (attraverso altri passaggi che non riportiamo) legato alla distribuzione dei numeri primi immersi nell'insieme dei numeri naturali.

Pare che Riemann avesse risolto la congettura che porta il suo nome, ma purtroppo parte delle sue carte furono distrutte dopo la sua morte da una troppo zelante domestica; non possiamo quindi sapere per certo se egli avesse solo impostato o risolto il problema.

Stabilire una regola matematica che dimostri se esiste o no una logica nell'assenza di una cadenza nella distribuzione dei numeri primi, significherebbe comprendere se vi è una "aritmia" totale in quest'ultima o meno; questo potrebbe avere importanti ricadute sulle applicazioni informatiche odierne e future, poiché la crittografia utilizza sovente come chiavi numeri interi la cui fattorizzazione in numeri primi (molto grandi) non deve essere calcolabile in tempi accettabili.

L'eventuale conoscenza della distribuzione di tale sequenza permetterebbe quindi di facilitare la fattorizzazione di cui sopra: si renderebbe perciò necessario trovare altre tecniche di sicurezza telematica, quali ad esempio la crittografia con le funzioni ellittiche modulari, che però sono anch'esse soggette ad una congettura pendente, o la crittografia quantistica, che per il momento sembra inattaccabile e la cui prima versione Qnet è già disponibile.

Nel 1914 G.H. Hardy giunse a dimostrare che z possiede infiniti zeri per i quali risulta vera la supposizione Riemanniana. A tutt'oggi, nonostante gli sforzi delle menti più brillanti del XX° secolo, la congettura non è stata ancora dimostrata e risulta essere una delle più importanti della matematica. La sua importanza deriva dal fatto che moltissimi importanti teoremi sono stati "dimostrati" supponendo vera la congettura di Riemann, quindi se si dovesse dimostrarla automaticamente si dimostrerebbe una valanga di proposizioni. Soprattutto dopo l'avvento del calcolo automatico la congettura è stata verificata per molti valori, ma ovviamente ciò non basta.
L'importanza della congettura di Riemann, come precedentemente accennato, è strettamente legata ad alcune questioni sui numeri primi. Molte ricerche sulla distribuzione dei primi sono state condotte assumendo come ipotesi la congettura di Riemann. Illustreremo uno degli esempi più celebri.
Come visto in precedenza, il numero dei primi
£ ad n, indicato con p(n) può così essere stimato:

http://www2.polito.it/didattica/polymath/htmlS/argoment/APPUNTI/TESTI/Ott_02/Img/f4c9.JPG

Tale stima per "piccoli" valori di n (cioè centinaia di milioni) è per eccesso; la prima dimostrazione data da Skewes della non veridicità di questa affermazione per esempio si basava sulla accettazione della validità della ipotesi di Riemann, e solo nel 1955 lo stesso Skewes riuscì a dimostrare una diversa limitazione per il numero sopracitato senza fare ricorso alla congettura di Riemann.
Terminiamo accennando ad un risultato sorprendente che lega
p(n) con z: si dimostra che "esiste" un formula esatta che esprime p(n) come procedimento di limite di funzioni analitiche definite utilizzando z.

Nel giugno 2004, Louis de Branges de Bourcia, della Purdue University, lo stesso che ha risolto la congettura di Bieberbach, ha affermato di aver dimostrato l'ipotesi di Riemann nell'articolo "Apology for the proof of the Riemann Hypothesis". Non è la prima volta che il matematico fa un tale annuncio, tuttavia la sua prova è ora al vaglio dei matematici di tutto il mondo. Al momento, non è chiaro se i controesempi forniti da Conrey e Li relativamente alla precedente rivendicazione di Branges de Bourcia siano validi anche per questa.

Nel marzo 2007 Tribikram Pati affermò al contrario di avere dimostrato che la congettura di Riemann è falsa, ma la sua dimostrazione è stata dimostrata essere erronea.

ALTRE CONSIDERAZIONI SULLA DISTRIBUZIONE DEI PRIMI

E' facile dimostrare che esistono infiniti numeri primi, (Euclide) nella successione degli interi.

Con la proposizione 20 del libro IX degli Elementi, Euclide dimostrò, con un semplice ed elegante ragionamento, che i numeri primi sono infiniti.

Proposizione 20:

"I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi"

Ragionando per assurdo supponiamo che i numeri primi siano in numero finito e siano essi p1, p2, p3,..., pn. Consideriamo il numero

n=p1·p2·p3·...·pn+1

e cioè il successivo del prodotto di tutti i numeri primi. n è maggiore di tutti i pi ma diviso per ognuno di essi da come resto 1 e quindi non ammette alcuno dei pi come divisore. Ma allora n è un numero primo, oppure se non lo è, risulta divisibile per un numero primo maggiore di tutti i numeri primi della successione data. Ciò è in contraddizione con quanto supposto e dunque la proposizione risulta vera.


Riportiamo la bella dimostrazione di Godfrey H. Hardy, dalla sua "Apologia di un matematico":

I numeri primi o, semplicemente, i primi, sono quei numeri:
(A) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
che non possono essere scomposti in prodotto di fattori minori. Per questo 37 e 317 sono numeri primi.
I numeri primi sono il materiale attraverso cui dalla moltiplicazione, si costruiscono tutti i numeri, per esempio si ha 666 = 2 × 3 × 3 × 37. Ogni numero che non è un numero primo è divisibile per almeno un numero primo (in genere, naturalmente, per molti). Dobbiamo dimostrare che esistono infiniti numeri primi e cioè che la successione (A) non termina mai.
Supponiamo invece che abbia fine e che 2,3,5,…,P rappresenti la successione completa dei numeri primi (per cui P risulta il massimo numero primo). Con questa ipotesi, consideriamo il numero Q definito dalla formula
Q = (2 × 3 × 5 × … × P) + 1.
E’ evidente che Q non è divisibile per nessuno dei numeri 2, 3, 5,…,P, perché il resto della divisione per ognuno di questi numeri sarà sempre 1. Ma, se Q stesso non è un numero primo, esso è divisibile per
qualche numero primo (che può essere lo stesso numero Q) che supera tutti quelli della successione. Questo contraddice l’ipotesi che non esiste un numero primo maggiore di P, e perciò la nostra ipotesi è falsa.
Questa è una dimostrazione per
reductio ad absurdum, e la reductio ad absurdum, tanto amata da Euclide, è una delle più belle armi del matematico. E’ un gambetto molto più raffinato di qualsiasi gambetto degli scacchi: un giocatore di scacchi può offrire in sacrificio un pedone o anche qualche altro pezzo, ma il matematico offre la partita.

Ma assai più difficile è il problema di dimostrare che ogni progressione aritmetica del tipo a + nb con a, b primi tra loro contenga infiniti primi. Benché ogni "verifica sperimentale" convalidasse questa ipotesi, solo nel 1837 Le Jeune Dirichlet (1805-1059) successore di Gauss a Gottinga , applicando i metodi più progrediti della matematica del tempo riuscì a dimostrare, in un famoso e celebrato scritto, tale ipotesi. La dimostrazione generale del Teorema è molto complessa, però è possibile citare la dimostrazione di casi particolari.

Dimostriamo il teorema per la progressione del tipo: 4n + 3.

Teorema: Ogni progressione del tipo 4n + 3 , contiene infiniti primi:

Dimostrazione:


Premettiamo:

  1. Ogni primo > 2 è dispari, e quindi della forma o 4n + 1 o 4n + 3.

  2. Il prodotto di due numeri del tipo 4n + 1 è ancora un numero di tale tipo; infatti si considerino 4a + 1 e  4b + 1 il loro prodotto (4a + 1)×(4b + 1) = 16ab + 4a + 4b + 1=4k + 1. Supponiamo per assurdo, ora che esistano solo un numero finito di primi del tipo 4n + 3, siano p1, p2, p3,...,pn. Consideriamo il numero n tale che n = 4×(p1×p2×p3×………×pn) - 1 = 4×(p1×p2×p3×………×pn-1) + 3. Allora:

  3. Poiché n + 1 è divisibile per ognuno dei fattori pi, ne consegue che n non contiene alcuno dei fattori pi.

  4. Se n è primo, è del tipo 4n + 3 ed è diverso da ogni pi e ciò va contro l'ipotesi.

  5. Se n non è primo, allora i suoi fattori (per 3.) sono tutti del tipo 4n + 1, ma allora (per 2.) n è del tipo 4n + 1, e ciò è assurdo poiché per costruzione è del tipo 4n + 3.

C.V.D

Abbiamo visto in precedenza che utilizzando opportuni ragionamenti statistici la distanza media tra due primi è approssimativamente ln(n).
Vediamo ora un’altra considerazione sulla distanza tra primi che però non coinvolge ragionamenti "in media" e di conseguenza è sempre vera.

Teorema: Esistono intervalli arbitrariamente grandi che NON contengono primi

Dimostrazione:


Mostriamo come costruire sequenze di qualunque dimensione NON contenenti primi. Si desideri per esempio ottenere 1000 interi NON primi consecutivi. Consideriamo la sequenza così generata:

(1000 + 1)! + n ; n = 2,3,…., 1001.

Ognuno di questi 1000 interi è composto infatti:

1×2×3×4× …….. ×999×1000×1001 + 2, raccolgo 2 è quindi 2 è fattore

1×2×3×4× …….. ×999×1000×1001 + 3, raccolgo 3 è quindi 3 è fattore

1×2×3×4× …….. ×999×1000×1001 + 4, raccolgo 4 è quindi 4 è fattore

……

……

……

……

1×2×3×4× …….. ×999×1000×1001 + 1000, raccolgo 1000 e quindi…

1×2×3×4× …….. ×999×1000×1001 + 1001, raccolgo 1001 e quindi…

E' facile dall'esempio precedente estendere il procedimento ad una sequenza di lunghezza arbitraria.

 


Home Page | Storia | Algoritmi | Distribuzione | Applet