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

Στην θεωρία αριθμών , το θεώρημα πρώτων αριθμών περιγράφει την ασυμπτωτική κατανομή των πρώτων αριθμών μεταξύ των θετικών ακεραίων. Το θεώρημα αποδείχθηκε ανεξάρτητα από τον 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(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 :

$\lim _{x\to \infty }{\frac {\pi (x)}{x/\log(x)}}=1,$

που είναι γνωστό ως ο ασυμπτωτικός κανόνας της κατανομής των πρώτων αριθμών. Χρησιμοποιώντας την ασυμπτωτική σημειογραφία το αποτέλεσμα αυτό μπορεί να επαναδιατυπωθεί ως

$\pi (x)\sim {\frac {x}{\log x}}.\!$

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

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

$p_{n}\sim n\log(n)$

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

Το θεώρημα των πρώτων αριθμών είναι επίσης ισοδύναμο με$\lim _{x\to \infty }{\frac {\vartheta \left(x\right)}{x}}=1$, και $\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1$, όπου $\vartheta$ και $\psi$ είναι η πρώτη και η δεύτερη Chebyshev συνάρτηση αντίστοιχα.

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

Με βάση τους πίνακες από τους Anton Felkel και  Jurij Vega, 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's και ο Dirichlet's υπονόησαν την ίδια εικασία της ασυμπτωτικής ισοδυναμίας των π(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 $\psi (x)$, που ορίζεται ως εξής: $\psi (x)=\sum _{p^{k}\leq x, \atop p\,{\text{prime}}}\log p.$

Η συνάρτηση αυτή γράφεται κάποιες φορές ως : $\psi (x)=\sum _{n\leq x}\Lambda (n)$, όπου $\Lambda (n)$ είναι η συνάρτηση von Mangoldt, που είναι $\Lambda (n)={\begin{cases}\log p&{\text{if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{\text{otherwise.}}\end{cases}}$

Τώρα είναι σχετικά εύκολο να ελέγξουμε ότι το Θ.Π.Α είναι ισοδύναμο με το να ισχυριστούμε ότι $\lim _{x\to \infty }\psi (x)/x=1$. Όντως , προκύπτει εύκολα ότι $\psi (x)=\sum _{p\leq x}\log p\left\lfloor {\frac {\log x}{\log p}}\right\rfloor \leq \sum _{p\leq x}\log x=\pi (x)\log x$

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

$\psi (x)\geq \sum _{x^{1-\epsilon }\leq p\leq x}\log p\geq \sum _{x^{1-\epsilon }\leq p\leq x}(1-\epsilon )\log x=(1-\epsilon )(\pi (x)+O(x^{1-\epsilon }))\log x.$

Το επόμενο βήμα είναι να βρούμε μια χρήσιμη παράσταση για την $\psi (x)$. Ας είναι $\zeta (s)$ η συνάρτηση ζ του Ρίμαν. Μπορούμε να δείξουμε ότι η $\zeta (s)$ σχετίζεται με την συνάρτηση von Mangoldt $\Lambda (n)$, και συνεπώς με την $\psi (x)$ , μέσω της σχέσης

$-{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }\Lambda (n)n^{-s}.$

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

$\psi (x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\log(2\pi )$

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

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

$\sum _{n=1}^{\infty }{\frac {1}{2n\,x^{2n}}}=-{\frac {1}{2}}\log \left(1-{\frac {1}{x^{2}}}\right),$

που εξαφανίζεται για μεγάλα x. Τα μη τετριμμένα μηδενικά , δηλαδή αυτά που βρίσκονται στην κρίσιμη ζώνη $0\leq \Re (s)\leq 1$, μπορούν δυνητικά να είναι ασυμπτωτικής τάξης σε σχέση με τον βασικό όρο x αν $\Re (\rho )=1$, επομένως πρέπει να δείξουμε ότι όλα τα μηδενικά έχουν πραγματικό μέρος αυστηρά μικρότερο του 1.

Για να το κάνουμε αυτό, θεωρούμε δεδομένο ότι η $\zeta (s)$ είναι μερομορφική στο ημι-επίπεδο $\Re (s)>0$, και αναλυτική εκεί εκτός από έναν απλό πόλο στο $s=1$, και ότι υπάρχει ο τύπος γινόμενο $\zeta (s)=\prod _{p}(1-p^{-s})^{-1}$ για $\Re (s)>1.$ Αυτός ο τύπος γινόμενο ακολουθείται από την ύπαρξη μοναδικής παραγοντοποίησης πρώτων παραγόντων των ακεραίων και δείχνει ότι η $\zeta (s)$ δεν είναι ποτέ μηδέν σε αυτήν την περιοχή, έτσι ώστε ο λογάριθμος να ορίζεται εκεί και

$\log \zeta (s)=-\sum _{p}\log(1-p^{-s})=\sum _{p,n}p^{-ns}/n.$

Θέτουμε $s=x+iy$ και έπειτα $|\zeta (x+iy)|=\exp(\sum _{n,p}{\frac {\cos ny\log p}{np^{nx}}}).$Παρατηρούμε τώρα την ταυτότητα $3+4\cos \phi +\cos 2\phi =2(1+\cos \phi )^{2}\geq 0,$ έτσι ώστε $|\zeta (x)^{3}\zeta (x+iy)^{4}\zeta (x+2iy)|=\exp \sum _{n,p}{\frac {3+4\cos(ny\log p)+\cos(2ny\log p)}{np^{nx}}}\geq 1$για κάθε $x>1$.

Υποθέτουμε τώρα ότι $\zeta (1+iy)=0$. Φυσικά $y$ ειναι μη μηδενικό αφού η $\zeta (s)$ έχει έναν απλό πόλο στο $s=1$.

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

Αφού η $\zeta (s)$ έχει απλό πόλο στο $s=1$ και $\zeta (x+2iy)$ παραμένει αναλυτική, το αριστερό μέρος της προηγούμενης ανισότητας τείνει στο $0$ και έχουμε αντίφαση.

Τέλος, μπορούμε να συμπεράνουμε ότι το Θ.Π.Α είναι "ηθικά"¨σωστό. Για να ολοκληρώσουμε αυστηρά την απόδειξη υπάρχουν ακόμα μερικές σοβαρές τεχνικές δυσκολίες που πρέπει να ξεπεραστούν εξαιτίας του ότι το άθροισμα πάνω από τα μηδενικά της ζήτα στον γενικό τύπο της $\psi (x)$ δεν συγκλίνει απόλυτα αλλά μόνο υπό συνθήκη. Υπάρχουν μερικοί τρόποι επίλυσης γύρω από αυτό το πρόβλημα αλλά πολλοί από αυτούς προϋποθέτουν πιο κομψές μιγαδικά αναλυτικές προσεγγίσεις που είναι πέρα από το φάσμα αυτού του άρθρου. Το βιβλίο του Edwards παρέχει τις λεπτομέρειες. Μια άλλη μέθοδος είναι να χρησιμοποιήσουμε το Θεώρημα Ikehara , αν και αυτό το θεώρημα είναι αρκετά δύσκολο από μόνο του να αποδειχθεί.

Ο D.J.Newman παρατήρησε ότι η πλήρης "δύναμη" του θεωρήματος του Ikehara δεν είναι αναγκαία για το Θεώρημα Πρώτων Αριθμών και κάποιος μπορεί απλά να χρησιμοποιήσει μία ειδική περίπτωση του που είναι ευκολότερο να αποδειχθεί.

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

Σε ένα χειρόγραφο σημείωμα σε μια ανατύπωση της εργασίας του του 1838 με τίτλο "Sur l'usage des séries infinies dans la théorie des nombres", την οποία ταχυδρόμησε στον Καρλ Φρίντριχ Γκάους, ο Πίτερ Γκουστάβ Ντιρικλέ , είκασε ότι μια καλύτερη προσέγγιση του π(x) δίνεται από την ολοκληρωτική λογαριθμική συνάρτηση Li(x) , που ορίζεται ως:

$\mathrm {Li} (x)=\int _{2}^{x}{\frac {1}{\log t}}\,\mathrm {d} t=\mathrm {li} (x)-\mathrm {li} (2).$

Όντως το ολοκλήρωμα αυτό υποδεικνύει ότι η πυκνότητα των πρώτων αριθμών γύρω από το t πρέπει να είναι 1/logt. Αυτή η συνάρτηση σχετίζεται με τον λογάριθμο μέσω του ασυμπτωτικού αναπτύγματος $\mathrm {Li} (x)\sim {\frac {x}{\log x}}\sum _{k=0}^{\infty }{\frac {k!}{(\log x)^{k}}}={\frac {x}{\log x}}+{\frac {x}{(\log x)^{2}}}+{\frac {2x}{(\log x)^{3}}}+\cdots .$

Άρα, το Θ.Π.Α. μπορεί αλλιώς να γραφεί ως π(x)~Li(x).

Σε μια άλλη εργασία, το 1899, ο Λα Βαλε Πουσσεν απέδειξε ότι $\pi (x)={\rm {Li}}(x)+O\left(x\mathrm {e} ^{-a{\sqrt {\log x}}}\right)\quad {\text{as }}x\to \infty$ για κάποια θετική σταθερά a και η βελτιωμένη μορφή του είναι

$\pi (x)={\rm {Li}}(x)+O\left(x\,\exp \left(-{\frac {A(\log x)^{3/5}}{(\log \log x)^{1/5}}}\right)\right).$

Λόγω της σύνδεσης μεταξύ της συνάρτησης ζ και της π(x), η υπόθεση του Ρίμαν έχει μεγάλη σημαντικότητα στην θεωρία αριθμών: αν αποδειχθεί αληθής, θα προκύψει μια πολύ καλύτερη προσέγγιση του σφάλματος που εμπλέκεται στο θεώρημα πρώτων αριθμών από αυτήν που υπάρχει σήμερα. Πιο συγκεκριμένα, ο Χέλγκε φον Κοχ έδειξε το 1901 ότι, αν και μόνο αν η υπόθεση του Ρίμαν είναι αληθής, ο όρος σφάλματος στην παραπάνω σχέση μπορεί να πάρει τη βελτιωμένη μορφή $\pi (x)={\rm {Li}}(x)+O\left({\sqrt {x}}\log x\right).$

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

$|\pi (x)-{\rm {li}}(x)|<{\frac {{\sqrt {x}}\,\log x}{8\pi }}$ για όλα τα x ≥ 2657. Επίσης εξήγαγε ένα παρόμοιο φράγμα για την συνάρτηση Chebyshev ψ: $|\psi (x)-x|<{\frac {{\sqrt {x}}\,\log ^{2}x}{8\pi }}$ για όλα τα x ≥ 73.2.

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

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

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

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

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

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

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

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

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

$\vartheta \left(x\right)\log \left(x\right)+\sum \limits _{p\leq x}{\log \left(p\right)}\ \vartheta \left({\frac {x}{p}}\right)=2x\log \left(x\right)+O\left(x\right)$όπου

$\vartheta \left(x\right)=\sum \limits _{p\leq x}{\log \left(p\right)}$ για πρώτους p.

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

Το 1994, οι Χαράλαμπος Κορνάρος και Κώστας Δημητρακόπουλος απέδειξαν το Θ.Π.Α. χρησιμοποιώντας μόνο $I\Delta _{0}+\exp$, ένα τυπικό σύστημα πιο αδύναμο από την αριθμητική του Πεάνο. Για την ιστορία των στοιχειωδών αποδείξεων του Θ.Π.Α, συμπεριλαμβανομένης των Έρντος-Σέλμπεργκ, δείτε το άρθρο του Ντόριαν Γκολντφελντ.

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

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

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

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

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

$\pi _{n,a}(x)\sim {\frac {1}{\varphi (n)}}\mathrm {Li} (x),$ όπου φ είναι η συνάρτηση Όιλερ. Με άλλα λόγια , οι πρώτοι είναι κατανεμημένοι ομοιόμορφα μεταξύ των κλάσεων υπολοίπων [a] modulo n με ΜΚΔ(a,n)=1. Αυτό είναι ισχυρότερο από το θεώρημα του Ντιρικλέ για τις αριθμητικές προόδους ( το οποίο απλώς αναφέρει ότι υπάρχουν άπειροι πρώτοι σε κάθε κλάση) και μπορεί να αποδειχθεί χρησιμοποιώντας όμοιες μεθόδους με αυτές που χρησιμοποίησε ο Νιούμαν στην απόδειξη του για το Θεώρημα πρώτων αριθμών.

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

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

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

Φράγματα στην συνάρτηση καταμέτρησης των πρώτων αριθμών.

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

$(1-\varepsilon ){\frac {x}{\log x}}<\pi (x)<(1+\varepsilon ){\frac {x}{\log x}}.$

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

${\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}\right)<\pi (x)<{\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2.51}{(\log x)^{2}}}\right).$

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

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

${\frac {x}{\log x+2}}<\pi (x)<{\frac {x}{\log x-4}}$.

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

${\frac {x}{\log x-1}}<\pi (x)$ for $x\geq 5393$, και $\pi (x)<{\frac {x}{\log x-1.1}}$ for $x\geq 60184$.

Η απόδειξη μέσω του de la Vallée-Poussin υπονοεί τα ακόλουθα. Για κάθε ε > 0 , υπάρχει μια S τέτοια ώστε για όλα x> S,

${\frac {x}{\log x-(1-\varepsilon )}}<\pi (x)<{\frac {x}{\log x-(1+\varepsilon )}}.$

Προσεγγίσεις για το νιοστό πρώτο αριθμό

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

$p_{n}\sim n\log n.$

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

${{\frac {p_{n}}{n}}=\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}-{\frac {(\log \log n)^{2}-6\log \log n+11}{2(\log n)^{2}}}+o\left({\frac {1}{(\log n)^{2}}}\right).}$

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

Το θεώρημα του Rosser δηλώνει ότι το pn είναι μεγαλύτερο από το n log n .Αυτό μπορεί να βελτιωθεί με το ακόλουθο ζεύγος ορίων :

$\log n+\log \log n-1<{\frac {p_{n}}{n}}<\log n+\log \log n\quad {\text{for }}n\geq 6.$

Ακριβέστερη προσέγγιση

Σύγκριση των π(x) (μπλε), x / ln x (πράσινο) και Li(x) (κόκκινο)

Έστω το λογαριθμικό ολοκλήρωμα (logarithmic integral):

$Li(x)=\int _{2}^{x}{\frac {dt}{\log t}},$

που μπορεί να γραφεί και ως:

$Li(x)={\frac {x}{\ln x}}\sum _{k=0}^{\infty }{\frac {k!}{(\ln x)^{k}}}={\frac {x}{\ln x}}+{\frac {x}{(\ln x)^{2}}}+{\frac {2x}{(\ln x)^{3}}}+\cdots .$

Σύμφωνα to θεώρημα πρώτων αριθμών ισχύει $\,\pi (x)\sim Li(x)$. Πιο συγκεκριμένα ισχύει:

$\pi (x)=Li(x)+O(xe^{-c{\sqrt {\ln x}}}),$

όπου ο όρος λάθους είναι μικρότερος από αυτόν που δίνει το θεώρημα πρώτων αριθμών. Η σχέση

$\pi (x)=Li(x)+O({\sqrt {x}}\ln x),$

που δηλώνει καλύτερη προσέγγιση από την προαναφερθείσα, είναι ισοδύναμη της υπόθεσης του Riemann.

Αριθμητικά παραδείγματα

Ο πίνακας δίνει τον αριθμό των πρώτων μέχρι το x σε σύγκριση με τις προαναφερθήσες προσεγγίσεις.

x	π(x)	π(x) / x	x / ln(x)	π(x)·ln(x) / x	Li(x)
10	4	0,400000	4	0,921034	6
102	25	0,250000	22	1,151292	30
103	168	0,168000	145	1,160503	178
104	1.229	0,122900	1.086	1,131951	1.246
105	9.592	0,095920	8.686	1,104320	9.630
106	78.498	0,078498	72.382	1,084490	78.628
107	664.579	0,066458	620.421	1,071175	664.918
108	5.761.455	0,057615	5.428.681	1,061299	5.762.209
109	50.847.534	0,050848	48.254.942	1,053727	50.849.235
1010	455.052.511	0,045505	434.294.482	1,047797	455.055.615
1011	4.118.054.813	0,041181	3.948.131.654	1,043039	4.118.066.401
1012	37.607.912.018	0,037608	36.191.206.825	1,039145	37.607.950.281
1013	346.065.536.839	0,034607	334.072.678.387	1,035899	346.065.645.810
1014	3.204.941.750.802	0,032049	3.102.103.442.166	1,033151	3.204.942.065.692
1015	29.844.570.422.669	0,029845	28.952.965.460.217	1,030795	29.844.571.475.288
1016	279.238.341.033.925	0,027924	271.434.051.189.532	1,028752	279.238.344.248.557
1017	2.623.557.157.654.233	0,026236	2.554.673.422.960.305	1,026964	2.623.557.165.610.822
1018	24.739.954.287.740.860	0,024740	24.127.471.216.847.324	1,025385	24.739.954.309.690.415
1019	234.057.667.276.344.607	0,023406	228.576.043.106.974.646	1,023982	234.057.667.376.222.382
1020	2.220.819.602.560.918.840	0,022208	2.171.472.409.516.259.138	1,022725	2.220.819.602.783.663.484
1021	21.127.269.486.018.731.928	0,021127	20.680.689.614.440.563.222	1,021594	21.127.269.486.616.126.182
1022	201.467.286.689.315.906.290	0,020147	197.406.582.683.296.285.296	1,020570	201.467.286.691.248.261.498
1023	1.925.320.391.606.803.968.923	0,019253	1.888.236.877.840.225.337.614	1,019639	1.925.320.391.614.054.155.139
OEIS	A006880	A057835		A057752

Ανάλογα για τα ανάγωγα πολυώνυμα πάνω από ένα πεπερασμένο πεδίο

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

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

$N_{n}\sim {\frac {q^{n}}{n}}.$

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

${\frac {x}{\log _{q}x}},$

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

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

$N_{n}={\frac {q^{n}}{n}}+O\left({\frac {q^{n/2}}{n}}\right).$

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

$q^{n}=\sum _{d\mid n}dN_{d},$

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

$N_{n}={\frac {1}{n}}\sum _{d\mid n}\mu (n/d)q^{d},$

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

Δείτε επίσης

• Θεμελιώδες θεώρημα άλγεβρας
• Θεμελιώδες θεώρημα αριθμητικής