Θεώρημα πρώτων αριθμών

Στη θεωρία αριθμών , το θεώρημα πρώτων αριθμών περιγράφει την ασυμπτωτική κατανομή των πρώτων αριθμών μεταξύ των θετικών ακεραίων. Το θεώρημα αποδείχθηκε ανεξάρτητα από τον Jacques Hadamard και τον Charles Jean de la Vallée-Poussin το 1896 χρησιμοποιώντας ιδέες που εισήγαγε ο Μπέρναρντ Ρίμαν (ειδικότερα, η συνάρτηση ζήτα του Riemann).
Η πρώτη τέτοια κατανομή που βρέθηκε είναι η π(N) ~ N / log(N), όπου π(N) είναι η συνάρτηση καταμέτρησης των πρώτων αριθμών και log(N) είναι ο φυσικός λογάριθμος του N. Αυτό σημαίνει ότι για αρκετά μεγάλα Ν, η πιθανότητα ένας τυχαίος ακέραιος που δεν είναι μεγαλύτερος από το Ν είναι πρώτος αν είναι πολύ κοντά στο 1 / log(N). Κατά συνέπεια, ένας τυχαίος ακέραιος με το πολύ 2n ψηφία ( για αρκετά μεγάλο n) έχει περίπου τις μισές πιθανότητες να είναι πρώτος από ένα τυχαίο ακέραιο με το πολύ n ψηφία. Για παράδειγμα, μεταξύ των θετικών ακεραίων με το πολύ 1000 ψηφία, περίπου ένα στους 2300 είναι πρώτος (log(10¹⁰⁰⁰) ≈ 2302.6), λαμβάνοντας υπόψη ότι μεταξύ των θετικών ακέραιων με το πολύ 2000 ψηφία περίπου ένα στους 4600 είναι πρώτος (log(10²⁰⁰⁰) ≈ 4605.2). Με άλλα λόγια, η μέση διαφορά ανάμεσα στους διαδοχικούς πρώτους αριθμούς μεταξύ των πρώτων N ακεραίων είναι περίπου log(N).

Παρουσίαση

Ας είναι π(x) η συνάρτηση καταμέτρησης των πρώτων αριθμών που δίνει τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι με το x, για οποιοδήποτε πραγματικό αριθμό x.
Για παράδειγμα, π(10)=4 επειδή υπάρχουν 4 πρώτοι αριθμοί (2,3,5 και 7) μικρότεροι ή ίσοι με το 10.Το θεώρημα πρώτων αριθμών αναφέρει ότι x / log(x) είναι μια καλή προσέγγιση της π(x), με την έννοια ότι το όριο του πηλίκου από τις δύο συναρτήσεις π(x) και x / log(x) όσο αυξάνεται το x χωρίς όριο είναι 1 :
που είναι γνωστό ως ο ασυμπτωτικός κανόνας της κατανομής των πρώτων αριθμών. Χρησιμοποιώντας την ασυμπτωτική σημειογραφία το αποτέλεσμα αυτό μπορεί να επαναδιατυπωθεί ως 
Αυτή η σημείωση (και το θεώρημα) δεν αναφέρεται στο όριο της διαφοράς των δυο συναρτήσεων όσο το x αυξάνεται χωρίς όριο. Αντί αυτού, το θεώρημα αναφέρει ότι x / log(x) προσεγγίζει την π(x) με την έννοια ότι το σχετικό σφάλμα της προσέγγισης προσεγγίζει το 0 όσο το x αυξάνεται χωρίς όριο.
Το θεώρημα πρώτων αριθμών είναι ισοδύναμο με το ότι ο νιοστός πρώτος αριθμός pₙ ικανοποιεί 
 
η ασυμπτωτική σημειογραφία σημαίνει, ξανά. ότι το σχετικό σφάλμα της προσέγγισης προσεγγίζει το 0 καθώς το n αυξάνεται χωρίς όριο. Για παράδειγμα, το 200  · 10¹⁵ τη πρώτος αριθμός είναι 8512677386048191063, και (200 · 10¹⁵)log(200 · 10¹⁵) που είναι ο 7967418752291744388, με σχετικό σφάλμα της τάξης 6.4%.
Το θεώρημα των πρώτων αριθμών είναι επίσης ισοδύναμο με, και , όπου  και  είναι η πρώτη και η δεύτερη Chebyshev συνάρτηση αντίστοιχα.

Η ιστορία του ασυμπτωτικού κανόνα της κατανομής των πρώτων αριθμών και η απόδειξη της.

Με βάση τους πίνακες από τους Anton Felkel και  Jurij Vega, o  Adrien-Marie Legendre υπέθεσε το 1797 ή 1798 ότι το π(a) προσεγγίζεται από τη συνάρτηση  a/(A log(a) + B), όπου Α και Β είναι απροσδιόριστες σταθερές. Στη δεύτερη έκδοση του βιβλίου του για τη θεωρία αριθμών (1808) έκανε μια πιο ακριβή εικασία, με  A = 1 και B = −1.08366. Ο Carl Friedrich Gauss
μελέτησε την ίδια ερώτηση στην ηλικία των 15 ή 16 από το 1792 ή το 1793, σύμφωνα με τις δικές του αναμνήσεις το 1849. To 1838 o Peter Gustav Lejeune Dirichlet συνέλαβε μια νέα προσεγγιστική συνάρτηση, το λογαριθμικό ολοκλήρωμα li(x) (από μια  ελαφρώς διαφορετική μορφή μιας σειράς, την οποία ο ίδιος κοινοποίησε στον Gauss). Οι τύποι των Legendre και Dirichlet υπονόησαν την ίδια εικασία της ασυμπτωτικής ισοδυναμίας των π(x) και x / log(x) που προαναφέρθηκαν, αν και αποδείχθηκε ότι η προσέγγιση του Dirichlet είναι σημαντικά καλύτερη, αν μελετήσει κανείς τις διαφορές αντί για το πηλίκο.
Σε δύο έγγραφα από το 1848 και το 1850, ο Ρώσος μαθηματικός Παφνούτι Τσεμπισιόφ προσπάθησε να αποδείξει τον ασυμπτωτικό νόμο της κατανομής των πρώτων αριθμών. Το έργο του είναι αξιοσημείωτο για τη χρήση της ζήτα συνάρτησης ζ(s) (για πραγματικές τιμές του ορίσματος "s", όπως είναι οι εργασίες του Λέοναρντ Όιλερ (Leonard Euler), ήδη από το 1737) πριν από τα απομνημονεύματα του  Riemann  το 1859, και κατάφερε να αποδείξει μια ελαφρώς ασθενέστερη μορφή του ασυμπτωτικού νόμου, δηλαδή, ότι αν το όριο του π(x)/(x/log(x)) καθώς το x τείνει στο άπειρο υπάρχει, τότε είναι αναγκαστικά ίσο με το ένα. Ήταν σε θέση να αποδείξει ανεπιφύλακτα ότι η αναλογία αυτή είναι φραγμένη πάνω και κάτω από δυο ρητά δοσμένες σταθερές κοντά στο 1, για όλα τα μεγάλα x. Παρά το γεγονός ότι ο Chebyshev δεν είχε αποδείξει στο έγγραφό του το Θεώρημα πρώτων αριθμών, οι εκτιμήσεις του για το π(x) ήταν αρκετά ισχυρές για να αποδείξει το αξίωμα του Bertrand, ότι υπάρχει ένας πρώτος αριθμός μεταξύ των n και 2n για κάθε ακέραιο n ≥ 2.
Ένα σημαντικό έγγραφο σχετικά με την κατανομή των πρώτων αριθμών ήταν τα απομνημονεύματα του Riemann το 1859 σχετικά με τον αριθμό των πρώτων αριθμών που είναι μικρότερος από ένα δεδομένο μέγεθος, το μόνο έγγραφο που έγραψε ποτέ για αυτό το θέμα. Ο Riemman εισήγαγε νέες ιδέες σε αυτό το θέμα, η επικεφαλής των οποίων είναι ότι η κατανομή των πρώτων αριθμών είναι στενά συνδεδεμένη με τα μηδενικά της αναλυτικά επεκταμένης συνάρτησης ζήτα του Riemann μιας σύνθετης μεταβλητής. Ειδικότερα, από αυτό το έγγραφο του Riemann προέρχεται η ιδέα του να εφαρμόσει τις μεθόδους της μιγαδικής ανάλυσης με τη μελέτη της πραγματικής συνάρτησης π(x). Επεκτείνοντας τις ιδέες του Riemann, δύο αποδείξεις του ασυμπτωτικού κανόνα της κατανομής των πρώτων αριθμών εξασφαλίστηκαν ανεξάρτητα από τον Jacques Hadamard και τον Charles Jean de la Vallée- Poussin και εμφανίστηκαν την ίδια χρονιά (1896). Και στις δύο αποδείξεις χρησιμοποιούνται μέθοδοι από την ανάλυση, που καθόρισαν ως κύριο βήμα ότι η συνάρτηση ζήτα του Riemman ζ(s) είναι μη μηδενική για όλες τις πολύπλοκες τιμές της μεταβλητής s που έχουν τη μορφή s= 1+ με t > 0.
Κατά τη διάρκεια του 20ου αιώνα, το θεώρημα του Hadamard και του de la Vallée-Poussin έγινε επίσης γνωστό ως Θεώρημα Πρώτων Αριθμών. Αρκετές διαφορετικές αποδείξεις βρέθηκαν, συμπεριλαμβανομένων των «στοιχειωδών» αποδείξεων των  Atle Selberg και Πολ Έρντος (Paul Erdős, 1949). Ενώ οι αρχικές αποδείξεις των Hadamard και de la Vallée-Poussin είναι μακρές και περίτεχνες, μεταγενέστερες αποδείξεις εισήγαγαν διάφορες απλουστεύσεις μέσω της χρήσης των Tauberian θεωρημάτων αλλά παρέμεινε δύσκολο να κατανοηθούν. Μια σύντομη απόδειξη ανακαλύφθηκε το 1980 από τον Αμερικανό μαθηματικό Donald J. Newman . Η απόδειξη του Newman είναι αναμφισβήτητα η πιο απλή γνωστή απόδειξη του θεωρήματος, αν και δεν είναι στοιχειώδης, με την έννοια ότι χρησιμοποιεί το ολοκληρωτικό θεώρημα του Κωσύ από τη μιγαδική ανάλυση.

Μεθοδολογία απόδειξης

Σε μια διάλεξη σχετικά με τους πρώτους αριθμούς για το ευρύ κοινό, o Terence Tao που απέκτησε το μετάλλιο Fields περιέγραψε μια προσέγγιση της απόδειξης του Θ.Π.Α. με ποιητικούς όρους: ακούγοντας τη "μουσική" των πρώτων αριθμών . Ξεκινάμε με ένα " ηχητικό κύμα " που είναι "θορυβώδες " στους πρώτους αριθμούς και σιωπηλό σε άλλους αριθμούς. Αυτή είναι η συνάρτηση του von Mangoldt· Στη συνέχεια αναλύουμε τις  "νότες" ή συχνότητές του, υποβάλλοντας το σε μια διαδικασία παρόμοια με το μετασχηματισμό Fourier· Αυτό είναι ο μετασχηματισμός Mellin. Το επόμενο και πιο δύσκολο βήμα είναι να αποδειχθεί ότι συγκεκριμένες "νότες" δεν μπορούν να προκύψουν σε αυτή τη μουσική.  Αυτή η εξαίρεση συγκεκριμένων "νοτών" οδηγεί στη διατύπωση του Θεωρήματος των Πρώτων Αριθμών.Σύμφωνα με τον Τάο , η απόδειξη αυτή παράγει πολύ βαθύτερες γνώσεις σχετικά με την κατανομή των πρώτων αριθμών από τις «στοιχειώδεις» αποδείξεις.

Σκιαγράφηση Απόδειξης

Θα παρουσιάσουμε μια σκιαγράφηση της απόδειξης  του θεωρήματος όπως παρουσιάζεται στη διάλεξη του Tao που αναφέραμε προηγουμένως. Όπως οι περισσότερες αποδείξεις του Θ.Π.Α, ξεκινάμε επαναπροσδιορίζοντας το πρόβλημα χρησιμοποιώντας μια λιγότερο διαισθητική, αλλά με καλύτερη "συμπεριφορά",  συνάρτηση καταμέτρησης πρώτων. Η ιδέα είναι να μετρήσουμε τους πρώτους ( ή ένα αντίστοιχο σύνολο όπως το σύνολο των δυνάμεων πρώτων) με βάρη που να πηγαίνουν σε μια συνάρτηση με ομαλότερη ασυμπτωτική συμπεριφορά. Η πιο συνήθης συνάρτηση  είναι η συνάρτηση Chebyshev , που ορίζεται ως εξής: 
Η συνάρτηση αυτή γράφεται κάποιες φορές ως : , όπου  είναι η συνάρτηση von Mangoldt, που είναι 
Τώρα είναι σχετικά εύκολο να ελέγξουμε ότι το Θ.Π.Α είναι ισοδύναμο με το να ισχυριστούμε ότι . Όντως , προκύπτει εύκολα ότι 
και (χρησιμοποιώντας τον συμβολισμό του Ο) για κάθε ,
Το επόμενο βήμα είναι να βρούμε μια χρήσιμη παράσταση για την . Ας είναι  η συνάρτηση ζ του Ρίμαν. Μπορούμε να δείξουμε ότι  η  σχετίζεται με τη συνάρτηση von Mangoldt , και συνεπώς με την  , μέσω της σχέσης 
Μία κομψή ανάλυση της παραπάνω εξίσωσης και των σχετικών ιδιοτήτων της συνάρτησης ζ , χρησιμοποιώντας το Μετασχηματισμό Mellin και τον τύπο του Perron δείχνει ότι για μη ακέραια x η εξίσωση
 
ισχύει, όπου το άθροισμα είναι επάνω από όλα τα μηδενικά ( τετριμμένα και μη) της συνάρτησης ζ. Αυτός ο τύπος είναι ένας από τους γενικούς τύπους της θεωρίας αριθμών και υποδεικνύει ήδη το αποτέλεσμα το οποίο θέλουμε να αποδείξουμε, από τη στιγμή που ο όρος x εμφανίζεται στα δεξιά ακολουθούμενος από χαμηλότερης τάξης ασυμπτωτικούς όρους.
Το επόμενο βήμα  της απόδειξης προϋποθέτει τη μελέτη των μηδενικών της συνάρτησης ζ.Τα τετριμμένα μηδενικά −2, −4, −6, −8, ... μπορούν να μελετηθούν ξεχωριστά:
που εξαφανίζεται για μεγάλα x. Τα μη τετριμμένα μηδενικά , δηλαδή αυτά που βρίσκονται στην κρίσιμη ζώνη , μπορούν δυνητικά να είναι ασυμπτωτικής τάξης σε σχέση με τον βασικό όρο x αν , επομένως πρέπει να δείξουμε ότι όλα τα μηδενικά έχουν πραγματικό μέρος αυστηρά μικρότερο του 1.
Για να το κάνουμε αυτό, θεωρούμε δεδομένο ότι η  είναι μερομορφική στο ημι-επίπεδο , και αναλυτική εκεί εκτός από έναν απλό πόλο στο , και ότι υπάρχει  ο τύπος γινόμενο  για  Αυτός ο τύπος γινόμενο ακολουθείται από την ύπαρξη μοναδικής παραγοντοποίησης πρώτων παραγόντων των ακεραίων και δείχνει ότι η  δεν είναι ποτέ μηδέν σε αυτήν την περιοχή, έτσι ώστε ο λογάριθμος να ορίζεται εκεί και 
Θέτουμε  και έπειτα Παρατηρούμε τώρα την ταυτότητα  έτσι ώστε για κάθε .
Υποθέτουμε τώρα ότι . Φυσικά  είναι μη μηδενικό  αφού η   έχει έναν απλό πόλο στο .
Έστω ότι  και ας αφήσουμε το  να τείνει στο  από πάνω.
Αφού η  έχει απλό πόλο στο  και  παραμένει αναλυτική, το αριστερό μέρος της προηγούμενης ανισότητας τείνει στο  και έχουμε αντίφαση.
Τέλος, μπορούμε να συμπεράνουμε ότι το Θ.Π.Α είναι "ηθικά"¨σωστό. Για να ολοκληρώσουμε αυστηρά την απόδειξη υπάρχουν ακόμα μερικές σοβαρές τεχνικές δυσκολίες που πρέπει να ξεπεραστούν εξαιτίας του ότι το άθροισμα πάνω από τα μηδενικά της ζήτα στον γενικό τύπο της  δεν συγκλίνει απόλυτα αλλά μόνο υπό συνθήκη. Υπάρχουν μερικοί τρόποι επίλυσης γύρω από αυτό το πρόβλημα αλλά πολλοί από αυτούς προϋποθέτουν πιο κομψές μιγαδικά αναλυτικές προσεγγίσεις που είναι πέρα από το φάσμα αυτού του άρθρου. Το βιβλίο του Edwards παρέχει τις λεπτομέρειες. Μια άλλη μέθοδος είναι να χρησιμοποιήσουμε το Θεώρημα Ikehara , αν και αυτό το θεώρημα είναι αρκετά δύσκολο από μόνο του να αποδειχθεί.
Ο D.J.Newman παρατήρησε ότι η πλήρης "δύναμη" του θεωρήματος του Ikehara δεν είναι αναγκαία για το Θεώρημα Πρώτων Αριθμών και κάποιος μπορεί απλά να χρησιμοποιήσει μία ειδική περίπτωση του που είναι ευκολότερο να αποδειχθεί.

H συνάρτηση καταμέτρησης πρώτων σαν όροι λογαριθμικού ολοκληρώματος

Σε ένα χειρόγραφο σημείωμα σε μια ανατύπωση της εργασίας του του 1838 με τίτλο  "Sur l'usage des séries infinies dans la théorie des nombres", την οποία ταχυδρόμησε στον Καρλ Φρίντριχ Γκάους, ο  Πίτερ Γκουστάβ Ντιρικλέ , είκασε ότι μια καλύτερη προσέγγιση του π(x) δίνεται από την ολοκληρωτική λογαριθμική συνάρτηση Li(x) , που ορίζεται ως: 
Όντως το ολοκλήρωμα αυτό υποδεικνύει ότι η πυκνότητα των πρώτων αριθμών γύρω από το t πρέπει να είναι 1/logt.  Αυτή η συνάρτηση σχετίζεται με τον λογάριθμο μέσω του ασυμπτωτικού αναπτύγματος  
Άρα, το Θ.Π.Α. μπορεί αλλιώς να γραφεί ως π(x)~Li(x). 
Σε μια άλλη εργασία, το 1899, ο Λα Βαλε Πουσσεν απέδειξε ότι  για κάποια θετική σταθερά a και η βελτιωμένη μορφή του είναι 
Λόγω της σύνδεσης μεταξύ της συνάρτησης ζ και της π(x), η υπόθεση του Ρίμαν έχει μεγάλη σημαντικότητα στην θεωρία αριθμών: αν αποδειχθεί αληθής, θα προκύψει μια πολύ καλύτερη προσέγγιση του σφάλματος που εμπλέκεται στο θεώρημα πρώτων αριθμών από αυτήν που υπάρχει σήμερα. Πιο συγκεκριμένα, ο Χέλγκε φον Κοχ έδειξε το 1901 ότι, αν και μόνο αν η υπόθεση του Ρίμαν είναι αληθής, ο όρος σφάλματος στην παραπάνω σχέση μπορεί να πάρει τη βελτιωμένη μορφή 
Η σταθερά που περιέχεται στον συμβολισμό Ο προσεγγίστηκε το 1976 από τον Λόουελ Σένφιλντ: υποθέτουμε από την υπόθεση Ρίμαν οτι
  για όλα τα x ≥ 2657. Επίσης εξήγαγε ένα παρόμοιο φράγμα για τη συνάρτηση Chebyshev ψ:  για όλα τα x ≥ 73.2. 
Αυτό το τελευταίο φράγμα εκφράζει μια διακύμανση στον μέσο νόμο της δύναμης ( όταν θεωρηθεί ως τυχαία συνάρτηση πάνω από τους ακεραίους), στο 1/f θόρυβο  και αντιστοιχεί στην  Τουίντι σύνθετη κατανομή Πουασόν. Παρενθετικά, οι Τουίντι κατανομές παρουσιάζουν μια οικογένεια κλιμακωτά αμετάβλητων κατανομών που εξυπηρετούν ως εστίες σύγκλισης για μια γενίκευση του κεντρικού οριακού θεωρήματος.
Το λογαριθμικό ολοκλήρωμα Li(x) είναι μεγαλύτερο από την π(x) για "μικρά" x. Αυτό συμβαίνει επειδή είναι καταμέτρηση όχι πρώτων αλλά δυνάμεων πρώτων, όπου η δύναμη  pⁿ 
ενός πρώτου μετράται ως 1/n ενός πρώτου. Αυτό υποδεικνύει ότι η Li(x) πρέπει συνήθως να είναι μεγαλύτερη από το π(x) κατά σχεδόν Li(x1/2)/2, γενικά όμως  μεγαλύτερη από την π(x). Όμως το 1914, ο Τζον Έντενσορ Λίτλγουντ, απέδειξε ότι αυτό δεν συμβαίνει πάντα. Η πρώτη τιμή του x για να είναι η π(x) μεγαλύτερη της Li(x) 
είναι κοντά στην τιμή x = 10316.

Στοιχειώδεις αποδείξεις

Στο πρώτο μισό του 20ου αιώνα, κάποιοι μαθηματικοί ( σημαντικός ο Γκόντφρει Χάρολντ Χάρντι) πίστευαν ότι υπάρχει ιεραρχία στις αποδεικτικές μεθόδους των μαθηματικών, η οποία εξαρτάται από το είδος των αριθμών ( ακέραιοι, πραγματικοί,μιγαδικοί) που απαιτεί η απόδειξη και ότι το θεώρημα πρώτων αριθμών είναι ένα "βαθύ" θεώρημα λόγω της ανάγκης χρήσης μιγαδικής ανάλυσης.
Αυτό το πιστεύω κλονίστηκε λίγο από μία απόδειξη του βασισμένη στο ταουμπεριανό Θεώρημα του Βίνερ, ωστόσο αυτό μπορεί να αγνοηθεί αν το θεώρημα του Βίνερ κρινόταν ότι έχει βάθος αντίστοιχο με αυτό της μεθόδου μιγ Θ.Π.Α.αδικών μεταβλητών.
Δεν υπάρχει αυστηρός και ευρέως αποδεκτός ορισμός για την έννοια της στοιχειώδους απόδειξης στη θεωρία αριθμών.Ένας ορισμός είναι "μια απόδειξη η οποία μπορεί να εκτελεστεί στην πρωτοτάξια αριθμητική του Peano." Υπάρχουν θεωρήματα της θεωρίας αριθμών ( παράδειγμα το θεώρημα Παρις-Χάρινγκτον) που μπορούν να αποδειχθούν χρησιμοποιώντας δευτεροτάξιες αλλά όχι πρωτοτάξιες μεθόδους, αλλά τέτοια θεωρήματα σπανίζουν έως και σήμερα.
Τον Μάρτιο του 1948, ο Άλτε Σέλμπεργκ καθιέρωσε, με στοιχειώδη μέσα, τον ασυμπτωτικό τύπο 
όπου 
 για πρώτους p. 
Έως τον Ιούλιο της ίδιας χρονιάς,  Σέλμπεργκ και  Πωλ Έρντος είχαν ο καθένας ξεχωριστά μια στοιχειώδη απόδειξη του Θ.Π.Α, χρησιμοποιώντας και οι δύο τον ασυμπτωτικό τύπο του Σέλμπεργκ ως αρχικό σημείο.Αυτές οι αποδείξεις οδήγησαν αποτελεσματικά στην αποδοχή του ότι το Θ.Π.Α ήταν "βαθύ" και έδειξαν ότι τεχνικώς στοιχειώδεις μέθοδοι (με άλλα λόγια η αριθμητική του Πεάνο) ήταν πιο ισχυρές από ότι πίστευαν.
Το 1994, οι Χαράλαμπος Κορνάρος και Κώστας Δημητρακόπουλος απέδειξαν το Θ.Π.Α. χρησιμοποιώντας μόνο , ένα τυπικό σύστημα πιο αδύναμο από την αριθμητική του Πεάνο. Για την ιστορία των στοιχειωδών αποδείξεων του Θ.Π.Α, συμπεριλαμβανομένης των Έρντος-Σέλμπεργκ, δείτε το άρθρο του Ντόριαν Γκολντφελντ.

Επαλήθευση μέσω Υπολογιστών

Το 2005, ο Avigad κ.α, έβαλαν τον αποδεικτή θεωρημάτων Ιζαμπελ να σχεδιάσει μια υπολογιστικώς επαληθευμένη παραλλαγή της απόδειξης Έρντος-Σελμπεργκ του Θ.Π.Α. Αυτή ήταν η πρώτη μηχανικά επαληθευμένη απόδειξη του Θ.Π.Α. Ο Avigad επέλεξε να τυποποιήσει την απόδειξη των Έρντος-Σελμπεργκ αντί μιας αναλυτικής επειδή ενώ η βιβλιοθήκη του Ιζαμπελ μπορούσε να αναγνωρίσει έννοιες όπως όριο,παράγωγος και άλλες συναρτήσεις, δεν περιείχε καθόλου θεωρία ολοκλήρωσης να αναφέρει ( Avigad et al.p.19). 
Το 2009 o Τζον Χάρισον χρησιμοποίησε τον HOL Light για να τυποποιήσει την απόδειξη μέσω μιγαδικής ανάλυσης. Αναπτύσσοντας τις κατάλληλες αναλυτικές μηχανές , συμπεριλαμβανομένου του ολοκληρωτικού τύπου του Cauchy, ήταν δυνατόν ο Χάρισον να τυποποιήσει "μια άμεση, μοντέρνα και κομψή απόδειξη αντί για έναν περίπλοκο 'στοιχειώδη' διαπληκτισμό των  Έρντος-Σελμπεργκ".

Το θεώρημα πρώτων αριθμών για αριθμητικές προόδους

Έστω ότι  δηλώνει το πλήθος των πρώτων αριθμών στην αριθμητική πρόοδο a, a + n, a + 2n, a + 3n, ... που είναι μικρότεροι από το x. Ο Lejeune Dirichlet και ο Legendre έκαναν την εικασία, και ο Βαλε-Πουσέν απέδειξε, ότι, αν a και n είναι πρώτοι μεταξύ τους τότε 
 όπου φ είναι η συνάρτηση Όιλερ. Με άλλα λόγια , οι πρώτοι είναι κατανεμημένοι ομοιόμορφα μεταξύ των κλάσεων υπολοίπων [a] modulo n με ΜΚΔ(a,n)=1. Αυτό είναι ισχυρότερο από το θεώρημα του Ντιρικλέ για τις αριθμητικές προόδους ( το οποίο απλώς αναφέρει ότι υπάρχουν άπειροι πρώτοι σε κάθε κλάση) και μπορεί να αποδειχθεί χρησιμοποιώντας όμοιες μεθόδους με αυτές που χρησιμοποίησε ο Νιούμαν στην απόδειξη του  για το Θεώρημα πρώτων αριθμών.
Το Θεώρημα Ζίγκελ-Βάλφιτζ δίνει μία καλή προσέγγιση για την κατανομή πρώτων στις κλάσεις υπολοίπων.

"Κούρσα" Πρώτων Αριθμών

Αν και έχουμε λεπτομερώς ότι  εμπειρικά, οι πρώτοι που συγκλίνουν στο 3 είναι περισσότεροι και είναι σχεδόν πάντα πιο μπροστά στην "κούρσα", με την πρώτη αντιστροφή να γίνεται στο x = 26,861. Όμως ο Λίτλγουντ έδειξε το 1914 ότι υπάρχουν απείρως πολλές εναλλαγές προσήμου για τη συνάρτηση  και άρα η πρωτιά στην "κούρσα" εναλλάσσεται συνεχώς άπειρες φορές. Το φαινόμενο όπου το π4,3(x) είναι μπροστά τις περισσότερες φορές ονομάζεται κλίση του Chebyshev. H "κούρσα" πρώτων αριθμών γενικεύεται και σε άλλα modulo και είναι αντικείμενο έρευνας. Ο Pál Turán ερωτήθηκε αν συμβαίνει πάντα  π(x;a,c) και π(x;b,c) να αλλάζουν θέση όταν a και b είναι πρώτοι με το c. Οι  Granville και Martin δίνουν μια πλήρη έκθεση και έρευνα.