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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

Στην θεωρία αριθμών , το θεώρημα πρώτων αριθμών περιγράφει την ασυμπτωτική κατανομή των πρώτων αριθμών μεταξύ των θετικών ακεραίων. Το θεώρημα αποδείχθηκε ανεξάρτητα από τον Jacques Hadamard και τον Charles Jean de la Vallée-Poussin το 1896 χρησιμοποιώντας ιδέες που εισήγαγε ο Bernhard Riemann (ειδικότερα, η συνάρτηση ζήτα του Riemann).

Η πρώτη τέτοια κατανομή που βρέθηκε είναι η π(N) ~ N / log(N), όπου π(N) είναι η συνάρτηση καταμέτρησης των πρώτων αριθμών και log(N) είναι ο φυσικός λογάριθμος του N. Αυτό σημαίνει ότι για αρκετά μεγάλα Ν, η πιθανότητα ένας τυχαίος ακέραιος που δεν είναι μεγαλύτερος από το Ν είναι πρώτος αν είναι πολύ κοντά στο 1 / log(N). Κατά συνέπεια, ένας τυχαίος ακέραιος με το πολύ 2n ψηφία ( για αρκετά μεγάλο n) έχει περίπου τις μισές πιθανότητες να είναι πρώτος από ένα τυχαίο ακέραιο με το πολύ n ψηφία. Για παράδειγμα, μεταξύ των θετικών ακεραίων με το πολύ 1000 ψηφία, περίπου ένα στους 2300 είναι πρώτος (log(101000) ≈ 2302.6), λαμβάνοντας υπόψη ότι μεταξύ των θετικών ακέραιων με το πολύ 2000 ψηφία περίπου ένα στους 4600 είναι πρώτος (log(102000) ≈ 4605.2). Με άλλα λόγια, η μέση διαφορά ανάμεσα στους διαδοχικούς πρώτους αριθμούς μεταξύ των πρώτων N ακεραίων είναι περίπου log(N).[1]

Παρουσίαση[Επεξεργασία | επεξεργασία κώδικα]

Το γράφημα δείχνει το λόγο της συνάρτησης καταμέτρησης των πρώτων π(x) στις δύο προσεγγίσεις της, x/log x και Li(x). Όσο το x αυξάνεται (σημείωση ο άξονας x είναι λογαριθμικός), και οι δύο λόγοι τείνουν στο 1. Ο λόγος για το x/log x συγκλίνει αργά στην πάνω συνάρτηση, ενώ ο λόγος Li(x) συγκλίνει πολύ πιο γρήγορα στην δεύτερη συνάρτηση.

Ας είναι π(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 αυξάνεται χωρίς όριο.

Η γραφική παράσταση του λογαρίθμου-λογαρίθμου δείχνει το απόλυτο σφάλμα του x/log x και Li(x), οι δύο προσεγγίσεις της συνάρτησης καταμέτρησης των πρώτων π(x). Σε αντίθεση με τον λόγο, η διαφορά μεταξύ των π(x) και x/log x αυξάνεται χωρίς όρια όσο το x αυξάνεται. Από την άλλη μεριά, το Li(x)-π(x) εναλλάσσει πρόσημο άπειρες φορές.

Το θεώρημα πρώτων αριθμών είναι ισοδύναμο με το ότι ο νιοστός πρώτος αριθμός pn ικανοποιεί

η ασυμπτωτική σημειογραφία σημαίνει, ξανά. ότι το σχετικό σφάλμα της προσέγγισης προσεγγίζει το 0 καθώς το n αυξάνεται χωρίς όριο. Για παράδειγμα, το 200  · 1015 τη πρώτος αριθμός είναι 8512677386048191063,[2] και (200 · 1015)log(200 · 1015) που είναι ο 7967418752291744388, με σχετικό σφάλμα της τάξης 6.4%.

Το θεώρημα των πρώτων αριθμών είναι επίσης ισοδύναμο με, και , όπου και είναι η πρώτη και η δεύτερη Chebyshev συνάρτηση αντίστοιχα.

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

Κατανομή των πρώτων μέχρι τον 19# (9699690).

Με βάση τους πίνακες από τους Anton Felkel και  Jurij Vega,Aο drien-Marie Legendre υποέθεσετο 1797 ή 1798 ότι το π(a) προσεγγίζεται από την συνάρτηση a/(A log(a) + B), όπου Α και Β είναι απροσδιόριστες σταθερές. Στη δεύτερη έκδοση του βιβλίου του για τη θεωρία αριθμών (1808) π,σκανε μια πιο ακριβή εικασία, με  A = 1 και B = −1.08366. Ο Carl Friedrich Gauss

μελέτησε την ίδια ερώτηση στην ηλικία των 15 ή 16 από το 1792 ή το 1793, σύμφωνα με τις δικές του αναμνήσεις το 1849.[3] 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 τείνει στο άπειρο υπάρχει, τότε είναι αναγκαστικά ίσο με το ένα.[4] Ήταν σε θέση να αποδείξει ανεπιφύλακτα ότι η αναλογία αυτή είναι φραγμένη πάνω και κάτω από δυο ρητά δοσμένες σταθερές κοντά στο 1,για όλα τα μεγάλα x.[5] Παρά το γεγονός ότι ο 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.[6]

Κατά τη διάρκεια του 20ου αιώνα, το θεώρημα του Hadamard και του de la Vallée-Poussin έγινε επίσης γνωστό ως Θεώρημα Πρώτων Αριθμών. Αρκετές διαφορετικές αποδείξεις βρέθηκαν, συμπεριλαμβανομένων των «στοιχειωδών» αποδείξεων των Atle Selberg και Πολ Έρντος (Paul Erdős, 1949). Ενώ οι αρχικές αποδείξεις των Hadamard και de la Vallée-Poussin είναι μακρές και περίτεχνες, μεταγενέστερες αποδείξεις εισήγαγαν διάφορες απλουστεύσεις μέσω της χρήσης των Tauberian θεωρημάτων αλλά παρέμεινε δύσκολο να κατανοηθούν. Μια σύντομη απόδειξη ανακαλύφθηκε το 1980 από τον Αμερικανό μαθηματικό Donald J. Newman .[7] [8]Η απόδειξη του Newman είναι αναμφισβήτητα η πιο απλή γνωστή απόδειξη του θεωρήματος, αν και δεν είναι στοιχειώδης, με την έννοια ότι χρησιμοποιεί το ολοκληρωτικό θεώρημα του Κωσύ από τη μιγαδική ανάλυση.

Μεθοδολογία απόδειξης[Επεξεργασία | επεξεργασία κώδικα]

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

Σκιαγράφηση Απόδειξης[Επεξεργασία | επεξεργασία κώδικα]

Θα παρουσιάσουμε μια σκιαγράφηση της απόδειξης του θεωρήματος όπως παρουσιάζεται στη διάλεξη του Tao που αναφέραμε προηγουμένως. Όπως οι περισσότερες αποδείξεις του Θ.Π.Α, ξεκινάμε επαναπροσδιορίζοντας το πρόβλημα χρησιμοποιώντας μια λιγότερο διαισθητική, αλλά με καλύτερη "συμπεριφορά", συνάρτηση καταμέτρησης πρώτων. Η ιδέα είναι να μετρήσουμε τους πρώτους ( ή ένα αντίστοιχο σύνολο όπως το σύνολο των δυνάμεων πρώτων) με βάρη που να πηγαίνουν σε μια συνάρτηση με ομαλότερη ασυμπτωτική συμπεριφορά. Η πιο συνήθης συνάρτηση είναι η συνάρτηση Chebyshev , που ορίζεται ως εξής:

Η συνάρτηση αυτή γράφεται κάποιες φορές ως : , όπου είναι η συνάρτηση von Mangoldt, που είναι

Τώρα είναι σχετικά εύκολο να ελέγξουμε ότι το Θ.Π.Α είναι ισοδύναμο με το να ισχυριστούμε ότι . Όντως , προκύπτει εύκολα ότι

και (χρησιμοποιώντας τον συμβολισμό του Ο) για κάθε ,

Το επόμενο βήμα είναι να βρούμε μια χρήσιμη παράσταση για την . Ας είναι η συνάρτηση ζ του Ρίμαν. Μπορούμε να δείξουμε ότι η σχετίζεται με την συνάρτηση von Mangoldt , και συνεπώς με την , μέσω της σχέσης

Μία κομψή ανάλυση της παραπάνω εξίσωσης και των σχετικών ιδιοτήτων της συνάρτησης ζ , χρησιμοποιώντας το Μετασχηματισμό Mellin και τον τύπο του Perron δείχνει ότι για μη ακέραια x η εξίσωση

ισχύει, όπου το άθροισμα είναι επάνω από όλα τα μηδενικά ( τετριμμένα και μη) της συνάρτησης ζ. Αυτός ο τύπος είναι ένας από τους γενικούς τύπους της θεωρίας αριθμών και υποδεικνύει ήδη το αποτέλεσμα το οποίο θέλουμε να αποδείξουμε, από τη στιγμή που ο όρος x εμφανίζεται στα δεξιά ακολουθούμενος από χαμηλότερης τάξης ασυμπτωτικούς όρους.

Το επόμενο βήμα της απόδειξης προϋποθέτει τη μελέτη των μηδενικών της συνάρτησης ζ.Τα τετριμμένα μηδενικά −2, −4, −6, −8, ... μπορούν να μελετηθούν ξεχωριστά:

που εξαφανίζεται για μεγάλα x. Τα μη τετριμμένα μηδενικά , δηλαδή αυτά που βρίσκονται στην κρίσιμη ζώνη , μπορούν δυνητικά να είναι ασυμπτωτικής τάξης σε σχέση με τον βασικό όρο x αν , επομένως πρέπει να δείξουμε ότι όλα τα μηδενικά έχουν πραγματικό μέρος αυστηρά μικρότερο του 1.

Για να το κάνουμε αυτό, θεωρούμε δεδομένο ότι η είναι μερομορφική στο ημι-επίπεδο , και αναλυτική εκεί εκτός από έναν απλό πόλο στο , και ότι υπάρχει ο τύπος γινόμενο για Αυτός ο τύπος γινόμενο ακολουθείται από την ύπαρξη μοναδικής παραγοντοποίησης πρώτων παραγόντων των ακεραίων και δείχνει ότι η δεν είναι ποτέ μηδέν σε αυτήν την περιοχή, έτσι ώστε ο λογάριθμος να ορίζεται εκεί και

Θέτουμε και έπειτα Παρατηρούμε τώρα την ταυτότητα έτσι ώστε για κάθε .

Υποθέτουμε τώρα ότι . Φυσικά ειναι μη μηδενικό αφού η έχει έναν απλό πόλο στο .

Έστω ότι και ας αφήσουμε το να τείνει στο από πάνω.

Αφού η έχει απλό πόλο στο και παραμένει αναλυτική, το αριστερό μέρος της προηγούμενης ανισότητας τείνει στο και έχουμε αντίφαση.

Τέλος, μπορούμε να συμπεράνουμε ότι το Θ.Π.Α είναι "ηθικά"¨σωστό. Για να ολοκληρώσουμε αυστηρά την απόδειξη υπάρχουν ακόμα μερικές σοβαρές τεχνικές δυσκολίες που πρέπει να ξεπεραστούν εξαιτίας του ότι το άθροισμα πάνω από τα μηδενικά της ζήτα στον γενικό τύπο της δεν συγκλίνει απόλυτα αλλά μόνο υπό συνθήκη. Υπάρχουν μερικοί τρόποι επίλυσης γύρω από αυτό το πρόβλημα αλλά πολλοί από αυτούς προϋποθέτουν πιο κομψές μιγαδικά αναλυτικές προσεγγίσεις που είναι πέρα από το φάσμα αυτού του άρθρου. Το βιβλίο του Edwards[10] παρέχει τις λεπτομέρειες. Μια άλλη μέθοδος είναι να χρησιμοποιήσουμε το Θεώρημα 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[11] ότι, αν και μόνο αν η υπόθεση του Ρίμαν είναι αληθής, ο όρος σφάλματος στην παραπάνω σχέση μπορεί να πάρει τη βελτιωμένη μορφή

Η σταθερά που περιέχεται στον συμβολισμό Ο προσεγγίστηκε το 1976 από τον Λόουελ Σένφιλντ[12]: υποθέτουμε από την υπόθεση Ρίμαν οτι

για όλα τα x ≥ 2657. Επίσης εξήγαγε ένα παρόμοιο φράγμα για την συνάρτηση Chebyshev ψ: για όλα τα x ≥ 73.2.

Αυτό το τελευταίο φράγμα εκφράζει μια διακύμανση στον μέσο νόμο της δύναμης ( όταν θεωρηθεί ως τυχαία συνάρτηση πάνω από τους ακεραίους), στο 1/f θόρυβο και αντιστοιχεί στην Τουίντι σύνθετη κατανομή Πουασόν[13]. Παρενθετικά, οι Τουίντι κατανομές παρουσιάζουν μια οικογένεια κλιμακωτά αμετάβλητων κατανομών που εξυπηρετούν ως εστίες σύγκλισης για μια γενίκευση του κεντρικού οριακού θεωρήματος[14].

Το λογαριθμικό ολοκλήρωμα Li(x) είναι μεγαλύτερο από την π(x) για "μικρά" x. Αυτό συμβαίνει επειδή είναι καταμέτρηση όχι πρώτων αλλά δυνάμεων πρώτων, όπου η δύναμη pn

ενός πρώτου μετράται ως 1/n ενός πρώτου. Αυτό υποδεικνύει ότι η Li(x) πρέπει συνήθως να είναι μεγαλύτερη από το π(x) κατά σχεδόν Li(x1/2)/2, γενικά όμως μεγαλύτερη από την π(x). Όμως το 1914, ο Τζον Έντενσορ Λίτλγουντ, απέδειξε ότι αυτό δεν συμβαίνει πάντα. Η πρώτη τιμή του x για να είναι η π(x) μεγαλύτερη της Li(x)

είναι κοντά στην τιμή x = 10316.

Στοιχειώδεις αποδείξεις[Επεξεργασία | επεξεργασία κώδικα]

Στο πρώτο μισό του 20ου αιώνα, κάποιοι μαθηματικοί ( σημαντικός ο Γκόντφρει Χάρολντ Χάρντι) πίστευαν ότι υπάρχει ιεραρχία στις αποδεικτικές μεθόδους των μαθηματικών, η οποία εξαρτάται από το είδος των αριθμών ( ακέραιοι, πραγματικοί,μιγαδικοί) που απαιτεί η απόδειξη και ότι το θεώρημα πρώτων αριθμών είναι ένα "βαθύ" θεώρημα λόγω της ανάγκης χρήσης μιγαδικής ανάλυσης.

Αυτό το πιστεύω κλονίστηκε λίγο από μία απόδειξη του Θ.Π.Α. βασισμένη στο ταουμπεριανό Θεώρημα του Βίνερ, ωστόσο αυτό μπορεί να αγνοηθεί αν το θεώρημα του Βίνερ κρινόταν ότι έχει βάθος αντίστοιχο με αυτό της μεθόδου μιγαδικών μεταβλητών.

Δεν υπάρχει αυστηρός και ευρέως αποδεκτός ορισμός για την έννοια της στοιχειώδους απόδειξης στη θεωρία αριθμών.Ένας ορισμός είναι "μια απόδειξη η οποία μπορεί να εκτελεστεί στην πρωτοτάξια αριθμητική του Peano." Υπάρχουν θεωρήματα της θεωρίας αριθμών ( παράδειγμα το θεώρημα Παρις-Χάρινγκτον) που μπορούν να αποδειχθούν χρησιμοποιώντας δευτεροτάξιες αλλά όχι πρωτοτάξιες μεθόδους, αλλά τέτοια θεωρήματα σπανίζουν έως και σήμερα.

Τον Μάρτιο του 1948, ο Άλτε Σέλμπεργκ καθιέρωσε, με στοιχειώδη μέσα, τον ασυμπτωτικό τύπο

όπου

για πρώτους p.[15]

Έως τον Ιούλιο της ίδιας χρονιάς, Σέλμπεργκ και Πωλ Έρντος είχαν ο καθένας ξεχωριστά μια στοιχειώδη απόδειξη του Θ.Π.Α, χρησιμοποιώντας και οι δύο τον ασυμπτωτικό τύπο του Σέλμπεργκ ως αρχικό σημείο[16][17].Αυτές οι αποδείξεις οδήγησαν αποτελεσματικά στην αποδοχή του ότι το Θ.Π.Α ήταν "βαθύ" και έδειξαν ότι τεχνικώς στοιχειώδεις μέθοδοι (με άλλα λόγια η αριθμητική του Πεάνο) ήταν πιο ισχυρές από ότι πίστευαν.

Το 1994, οι Χαράλαμπος Κορνάρος και Κώστας Δημητρακόπουλος απέδειξαν το Θ.Π.Α. χρησιμοποιώντας μόνο ,[18] ένα τυπικό σύστημα πιο αδύναμο από την αριθμητική του Πεάνο. Για την ιστορία των στοιχειωδών αποδείξεων του Θ.Π.Α, συμπεριλαμβανομένης των Έρντος-Σέλμπεργκ, δείτε το άρθρο του Ντόριαν Γκολντφελντ[16].

Επαλήθευση μέσω Υπολογιστών[Επεξεργασία | επεξεργασία κώδικα]

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

Το 2009 o Τζον Χάρισον χρησιμοποίησε τον HOL Light για να τυποποιήσει την απόδειξη μέσω μιγαδικής ανάλυσης[20]. Αναπτύσσοντας τις κατάλληλες αναλυτικές μηχανές , συμπεριλαμβανομένου του ολοκληρωτικού τύπου του Cauchy, ήταν δυνατόν ο Χάρισον να τυποποιήσει "μια άμεση, μοντέρνα και κομψή απόδειξη αντί για έναν περίπλοκο 'στοιχειώδη' διαπληκτισμό των Έρντος-Σελμπεργκ".

Το θεώρημα πρώτων αριθμών για αριθμητικές προόδους[Επεξεργασία | επεξεργασία κώδικα]

Έστω ότι δηλώνει το πλήθος των πρώτων αριθμών στην αριθμητική πρόοδο a, a + n, a + 2n, a + 3n, ... που είναι μικρότεροι από το x. Ο Lejeune Dirichlet και ο Legendre έκαναν την εικασία, και ο Βαλε-Πουσέν απέδειξε, ότι, αν a και n είναι πρώτοι μεταξύ τους τότε

όπου φ είναι η συνάρτηση Όιλερ. Με άλλα λόγια , οι πρώτοι είναι κατανεμημένοι ομοιόμορφα μεταξύ των κλάσεων υπολοίπων [a] modulo n με ΜΚΔ(a,n)=1. Αυτό είναι ισχυρότερο από το θεώρημα του Ντιρικλέ για τις αριθμητικές προόδους ( το οποίο απλώς αναφέρει ότι υπάρχουν άπειροι πρώτοι σε κάθε κλάση) και μπορεί να αποδειχθεί χρησιμοποιώντας όμοιες μεθόδους με αυτές που χρησιμοποίησε ο Νιούμαν στην απόδειξη του για το Θεώρημα πρώτων αριθμών[21].

Το Θεώρημα Ζίγκελ-Βάλφιτζ δίνει μία καλή προσέγγιση για την κατανομή πρώτων στις κλάσεις υπολοίπων.

"Κούρσα" Πρώτων Αριθμών[Επεξεργασία | επεξεργασία κώδικα]

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

Φράγματα στην συνάρτηση καταμέτρησης των πρώτων αριθμών.[Επεξεργασία | επεξεργασία κώδικα]

Το θεώρημα των πρώτων αριθμών είναι ένα ασυμπτωτικό αποτέλεσμα. Δίνει έναν αναποτελεσματικό περιορισμό στην π(x) ως άμεση συνέπεια του ορισμού του ορίου: Για όλα τα ε > 0, υπάρχει μια S τέτοια ώστε για όλα τα x > S,

Ωστόσο, καλύτερα φράγματα για τπ(x) είναι γνωστά, για παράδειγμα του Pierre Dusart

Η πρώτη ανισότητα ισχύει για κάθε x ≥ 599 και η δεύτερη για x ≥ 355991.[24]

Ένα ασθενέστερο αλλά μερικές φορές χρήσιμο φράγμα για x ≥ 55 είναι:

.[25]

Στην διατριβή του Pierre Dusart , υπάρχουν ισχυρότερες εκδόσεις αυτού του τύπου των ανισοτήτων που ισχύουν για μεγαλύτερα x. Αργότερα , το 2010,o Dusart απόδειξε:

for , και for .[26]

Η απόδειξη μέσω του de la Vallée-Poussin υπονοεί τα ακόλουθα:

Για κάθε ε > 0 , υπάρχει μια S τέτοια ώστε για όλα x> S,

Προσεγγίσεις για το νιοστό πρώτο αριθμό[Επεξεργασία | επεξεργασία κώδικα]

Ως συνέπεια του θεωρήματος των πρώτων αριθμών, παίρνουμε μια ασυμπτωτική έκφραση για τον νιοστό πρώτο αριθμό, που συμβολίζεται με :

Μια καλύτερη προσέγγιση είναι

[27]

Και πάλι θεωρώντας το 200 · 1015 πρώτο αριθμό 8512677386048191063,αυτό δίνει μια εκτίμηση της 8512681315554715386 ; τα πρώτα 5 ψηφία ταιριάζουν και το σχετικό σφάλμα είναι περίπου 0,00005 % .

Το θεώρημα του Rosser δηλώνει ότι το είναι μεγαλύτερο από το .Αυτό μπορεί να βελτιωθεί με το ακόλουθο ζεύγος φραγμάτων:[28][29]

Πίνακας των π(x),x/log(x) και li(x)[Επεξεργασία | επεξεργασία κώδικα]

Ο πίνακας συγκρίνει τις ακριβείς τιμές του π(x) με τις δύο προσεγγίσεις x/logx και li(x). Η τελευταία στήλη ,x/π(x), είναι η μέση "πρώτη διαφορά" για το χ.

x π(x) π(x) − x / log x π(x) / (x / log x) li(x) − π(x) x / π(x)
10 4 −0.3 0.921 2.2 2.500
102 25 3.3 1.151 5.1 4.000
103 168 23 1.161 10 5.952
104 1,229 143 1.132 17 8.137
105 9,592 906 1.104 38 10.425
106 78,498 6,116 1.084 130 12.740
107 664,579 44,158 1.071 339 15.047
108 5,761,455 332,774 1.061 754 17.357
109 50,847,534 2,592,592 1.054 1,701 19.667
1010 455,052,511 20,758,029 1.048 3,104 21.975
1011 4,118,054,813 169,923,159 1.043 11,588 24.283
1012 37,607,912,018 1,416,705,193 1.039 38,263 26.590
1013 346,065,536,839 11,992,858,452 1.034 108,971 28.896
1014 3,204,941,750,802 102,838,308,636 1.033 314,890 31.202
1015 29,844,570,422,669 891,604,962,452 1.031 1,052,619 33.507
1016 279,238,341,033,925 7,804,289,844,393 1.029 3,214,632 35.812
1017 2,623,557,157,654,233 68,883,734,693,281 1.027 7,956,589 38.116
1018 24,739,954,287,740,860 612,483,070,893,536 1.025 21,949,555 40.420
1019 234,057,667,276,344,607 5,481,624,169,369,960 1.024 99,877,775 42.725
1020 2,220,819,602,560,918,840 49,347,193,044,659,701 1.023 222,744,644 45.028
1021 21,127,269,486,018,731,928 446,579,871,578,168,707 1.022 597,394,254 47.332
1022 201,467,286,689,315,906,290 4,060,704,006,019,620,994 1.021 1,932,355,208 49.636
1023 1,925,320,391,606,803,968,923 37,083,513,766,578,631,309 1.020 7,250,186,216 51.939
1024 18,435,599,767,349,200,867,866 339,996,354,713,708,049,069 1.019 17,146,907,278 54.243
1025 176,846,309,399,143,769,411,680 3,128,516,637,843,038,351,228 1.018 55,160,980,939 56.546
OEIS A006880 A057835 A057752

Η τιμή π(1024) υπολογίστηκε αρχικά υποθέτοντας ότι η υπόθεση Ρίμαν είναι αληθής.[30] Έκτοτε έχει επαληθευτεί άνευ όρων.[31]

Ανάλογo Θεώρημα για τα ανάγωγα πολυώνυμα πάνω από ένα πεπερασμένο σώμα[Επεξεργασία | επεξεργασία κώδικα]

Υπάρχει ένα ανάλογο του θεωρήματος των πρώτων αριθμών που περιγράφει την "κατανομή " των ανάγωγων πολυωνύμων πάνω από ένα πεπερασμένο σώμα· η μορφή που παίρνει είναι εντυπωσιακά παρόμοια με την περίπτωση του κλασσικού θεωρήματος των πρώτων αριθμών.

Για να το αναφέρουμε με ακρίβεια, ας είναι F = GF ( q ) το πεπερασμένο σώμα με q στοιχεία , για κάποιο δεδομένο q , και ας είναι ο αριθμός των μόνικ ανάγωγων πολυωνύμων πάνω από το F των οποίων ο βαθμός είναι ίσος με n. Δηλαδή, ψάχνουμε πολυώνυμα με συντελεστές από το F, τα οποία δεν μπορούν να γραφτούν ως γινόμενα πολυωνύμων μικρότερου βαθμού. Σε αυτή την περίπτωση, τα εν λόγω πολυώνυμα παίζουν το ρόλο των πρώτων αριθμών, αφού όλα τα άλλα μόνικ πολυώνυμα έχουν δημιουργηθεί από γινόμενα μεταξύ τους. Μπορούμε τότε να αποδείξουμε ότι:

Αν κάνουμε την αντικατάσταση x = qn , τότε η δεξιά πλευρά είναι απλά

γεγονός που καθιστά την αναλογία σαφέστερη . Δεδομένου ότι υπάρχουν ακριβώς qn μόνικ πολυώνυμα βαθμού n ( συμπεριλαμβανομένων των αναγώγιμων), αυτό μπορεί να αναδιατυπωθεί ως εξής : αν επιλεγεί τυχαία ένα μόνικ πολυώνυμο βαθμού n , τότε η πιθανότητα να είναι ανάγωγο είναι περίπου 1 / n .

Μπορούμε επίσης να αποδείξουμε ένα ανάλογο της υπόθεσης Riemann, δηλαδή ότι

Οι αποδείξεις από αυτές τις περιπτώσεις είναι πολύ πιο απλές από ό, τι στην κλασική περίπτωση . Εμπεριέχουν ένα σύντομο συνδυαστικό

επιχείρημα ,[32] που συνοψίζεται ως εξής: Κάθε στοιχείο της επέκτασης βαθμού n του F είναι μια ρίζα κάποιου ανάγωγου πολυωνύμου του οποίου ο βαθμός d διαιρεί το n· μετρώντας αυτές τις ρίζες με δύο διαφορετικούς τρόπους διαπιστώνουμε ότι

όπου το άθροισμα είναι πάνω από όλους τους διαιρέτες d του n. Η αντιστροφή του Möbius δίνει ότι:

όπου μ(k) είναι η συνάρτηση Möbius . ( Ο τύπος αυτός ήταν γνωστό στον Gauss ). Ο κύριος όρος εμφανίζεται για d = n, και δεν είναι δύσκολο να φράξει τους υπόλοιπους όρους. Η "υπόθεση του Riemann" εξαρτάται από το γεγονός ότι ο μεγαλύτερος διαιρέτης του n δεν μπορεί να είναι μεγαλύτερος από το n / 2.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Hoffman, Paul (1998). The Man Who Loved Only Numbers. New York: Hyperion Books, σελ. p. 227. ISBN 0-7868-8406-1. MR 1666054. 
  2. Prime, Curios! (2011-10-09). Prime Curios!: 8512677386048191063. at Martin: University of Tennessee. 
  3. Gauss, C.F.. Werke , Bd 2 , 1st ed. Göttingen , 1863, σελ. 444-447. 
  4. Pereira, N. Costa (1985-01-01). «A Short Proof of Chebyshev's Theorem». The American Mathematical Monthly 92 (7): 494–495. doi:10.2307/2322510. http://www.jstor.org/stable/2322510. 
  5. Nair, M. (1982-01-01). «On Chebyshev-Type Inequalities for Primes». The American Mathematical Monthly 89 (2): 126–129. doi:10.2307/2320934. http://www.jstor.org/stable/2320934. 
  6. Ingham, A.E. (1990). The Distribution of Prime Numbers. Cambridge University Press, σελ. 2-5. ISBN 0-521-39789-8. 
  7. Newman, D. J. (1980-01-01). «Simple Analytic Proof of the Prime Number Theorem». The American Mathematical Monthly 87 (9): 693–696. doi:10.2307/2321853. MR 0602825. http://www.jstor.org/stable/2321853. 
  8. Zagier, D. (1997-01-01). «Newman's Short Proof of the Prime Number Theorem». The American Mathematical Monthly 104 (8): 705–708. doi:10.2307/2975232. MR 1476753. http://www.jstor.org/stable/2975232. 
  9. Video και διαφάνειες από τη διάλεξη του Τάο για τους πρώτους αριθμούς, UCLA, Ιανουάριος 2007
  10. Harold M., Edwards (2001). Riemann's zeta function. Courier Dover Publications. ISBN 0-486-41740-9. 
  11. Koch, Helge von (1901-01-01). «Sur la distribution des nombres premiers» (στα fr). Acta Mathematica 24 (1): 159–182. doi:10.1007/BF02403071. ISSN 0001-5962. http://link.springer.com/article/10.1007/BF02403071. 
  12. Schoenfeld, Lowell (1976-01-01). «Sharper Bounds for the Chebyshev Functions $\theta(x)$ and $\psi(x)$. II». Mathematics of Computation 30 (134): 337–360. doi:10.2307/2005976. http://www.jstor.org/stable/2005976. 
  13. Kendal, WS (2013). «Fluctuation scaling and 1/f noise: shared origins from the Tweedie family of statistical distributions». J Basic Appl Phys Volume 2. 
  14. Jørgensen, Bent; Martínez, José Raúl; Tsao, Min (1994-01-01). «Asymptotic Behaviour of the Variance Function». Scandinavian Journal of Statistics 21 (3): 223–243. http://www.jstor.org/stable/4616314. 
  15. Selberg, Atle (1949-01-01). «An Elementary Proof of the Prime-Number Theorem». Annals of Mathematics 50 (2): 305–313. doi:10.2307/1969455. http://www.jstor.org/stable/1969455. 
  16. 16,0 16,1 Goldfeld, D. (2004-01-01). Chudnovsky, David. επιμ. The Elementary Proof of the Prime Number Theorem: An Historical Perspective. Springer New York, σελ. 179–192. ISBN 9781461264903. http://link.springer.com/chapter/10.1007/978-1-4419-9060-0_10. 
  17. Baas, Nils; Skau, Christian (2008-01-01). «The lord of the numbers, Atle Selberg. On his life and mathematics». Bulletin of the American Mathematical Society 45 (4): 617–649. doi:10.1090/S0273-0979-08-01223-8. ISSN 0273-0979. http://www.ams.org/bull/2008-45-04/S0273-0979-08-01223-8/. 
  18. Cornaros, C.; Dimitracopoulos, C. (1994-08-01). «The prime number theorem and fragments ofP A» (στα en). Archive for Mathematical Logic 33 (4): 265–281. doi:10.1007/BF01270626. ISSN 0933-5846. http://link.springer.com/article/10.1007/BF01270626. 
  19. Avigad, Jeremy; Donnelly, Kevin; Gray, David; Raff, Paul (2007-12-01). «A Formally Verified Proof of the Prime Number Theorem». ACM Trans. Comput. Logic 9 (1). doi:10.1145/1297658.1297660. ISSN 1529-3785. http://doi.acm.org/10.1145/1297658.1297660. 
  20. Harrison, John (2009-08-19). «Formalizing an Analytic Proof of the Prime Number Theorem» (στα en). Journal of Automated Reasoning 43 (3): 243–261. doi:10.1007/s10817-009-9145-6. ISSN 0168-7433. http://link.springer.com/article/10.1007/s10817-009-9145-6. 
  21. Soprounov, Ivan (1998). A short proof of the Prime Number Theorem for arithmetic progressions. http://academic.csuohio.edu/soprunov_i/pdf/primes.pdf. 
  22. 22,0 22,1 22,2 Granville, Andrew; Martin, Greg (2006-01-01). «Prime Number Races». The American Mathematical Monthly 113 (1): 1–33. doi:10.2307/27641834. http://www.jstor.org/stable/27641834. 
  23. Guy, Richard K. (2004). Unsolved problems in number theory. Springer-Verlag, σελ. https://zbmath.org/?format=complete&q=an:1058.11001.+ISBN 978-0-387-20860-2. 
  24. Pierre, Dusart (1998). «Autour de la fonction qui compte le nombre de nombres premiers». France. http://www.unilim.fr/laco/theses/1998/T1998_01.html. 
  25. Rosser, Barkley (1941-01-01). «Explicit Bounds for Some Functions of Prime Numbers». American Journal of Mathematics 63 (1): 211–232. doi:10.2307/2371291. MR 0003018. http://www.jstor.org/stable/2371291. 
  26. Dusart, Pierre (22 April 2014). Estimates of Some Functions Over Primes without R.H.. http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.0442v1.pdf. 
  27. Cesàro, Ernesto (1894). Comptes rendus hebdomadaires des séances de l'Académie des sciences. French, σελ. "Sur une formule empirique de M. Pervouchine". 
  28. Bach Eric, Shallit, Jefrey (1996). Algorithmic Number Theory. Cambridge: MIT. ISBN 0-262-02405-5. 
  29. Dusart, Pierre (1999-01-01). «The 𝑘^{𝑡ℎ} prime is greater than 𝑘(ln𝑘+lnln𝑘-1) for 𝑘≥2». Mathematics of Computation of the American Mathematical Society 68 (225): 411–415. doi:10.1090/S0025-5718-99-01037-6. ISSN 0025-5718. MR 1620223. http://www.ams.org/mcom/1999-68-225/S0025-5718-99-01037-6/. 
  30. Caldwell, Chris K. (2010-08-03). «"Conditional Calculation of pi(1024)"». http://primes.utm.edu/notes/pi(10%5E24).html. 
  31. Platt, David (2015-01-01). «Computing 𝜋(𝑥) analytically». Mathematics of Computation 84 (293): 1521–1535. doi:10.1090/S0025-5718-2014-02884-6. ISSN 0025-5718. MR 3315519. http://www.ams.org/mcom/2015-84-293/S0025-5718-2014-02884-6/. 
  32. Chebolu, Sunil K.; Miná?, Ján (2011-01-01). «Counting Irreducible Polynomials over Finite Fields Using the Inclusion-Exclusion Principle». Mathematics Magazine 84 (5): 369–371. doi:10.4169/math.mag.84.5.369. http://www.jstor.org/stable/10.4169/math.mag.84.5.369. 

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Hardy, G. H.; Littlewood, J. E. (1916). «Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes». Acta Mathematica 41: 119–196. doi:10.1007/BF02422942. 

Granville, Andrew (1995). «Harald Cramér and the distribution of prime numbers». Scandinavian Actuarial Journal 1: 12–28. doi:10.1080/03461238.1995.10413946. http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf. 

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]