Πρώτοι Αριθμοί - Η ασυμπτωτική κατανομή πυκνότητας των πρώτων και οι πειραματισμοί του Gauss

Πόσο πυκνοί είναι οι πρώτοι αριθμοί στο σύνολο των ακέραιων; Με ποιον τρόπο μεταβάλλεται η πυκνότητα αυτή; Το πλήθος των πρώτων αυξάνεται στις γειτονιές μεγαλύτερων ακέραιων; Στην ανάρτηση αυτή μαθαίνουμε να μετράμε τους πρώτους, να υπολογίζουμε την πυκνότητά τους ακολουθώντας τη σκέψη του Gauss!

Σε μία προηγούμενη σειρά αναρτήσεων [~] ξεκινήσαμε με τον υπολογισμό της πιθανότητας ένας ακέραιος να είναι πρώτος και καταλήξαμε σε ένα γενικό συμπέρασμα για την ασυμπτωτική τάση που έχει η κατανομή των πρώτων αριθμών στο σύνολο των ακέραιων. Το γεγονός αυτό εκφράζεται μέσω της συνάρτησης καταμέτρησης των πρώτων αριθμών $\pi(x)$ που είναι μικρότεροι ενός δεδομένου ακέραιου $x\gt 2$.

Η συνάρτηση $\pi(x)$ εκφράζεται με όρους συναρτήσεων βήματος, δηλαδή με μικρά σκαλοπατάκια που εμφανίζονται κάθε φορά που συναντάμε κάποιον πρώτο αριθμό καθώς διατρέχουμε τον άξονα των ακέραιων. Αν ο άξονας αυτός αντιστοιχεί στον οριζόντιο άξονα του παρακάτω διαγράμματος και υποθέσουμε ότι κάθε σκαλοπάτι έχει ύψος 1, τότε ο κάθετος άξονας αντιστοιχεί στο πλήθος των πρώτων που είναι μικρότεροι από κάποιον αριθμό $x$ στον οριζόντιο άξονα. Για παράδειγμα, σύμφωνα με το παρακάτω γράφημα της συνάρτησης $\pi(x)$ για το διάστημα $[2,\ 20]$, η τιμή της $\pi(x)$ είναι 8, που αντιστοιχεί στο πλήθος των πρώτων που βρίσκονται σε αυτό το διάστημα.

Η συνάρτηση καταμέτρησης των πρώτων $\pi(x)$ που είναι μικρότεροι από κάποιον αριθμό $x$. Καθώς διατρέχουμε τον αξονα των ακέραιων, που αντιστοιχεί στον οριζόντιο άξονα της γραφικής παράστασης, όταν συναντούμε έναν πρώτο αριθμό προστίθεται και ένα σκαλοπάτι στο γράφημα της $\pi(x)$. Έτσι, όπως φαίνεται και στην γραφική παράσταση, υπάρχουν 4 πρώτοι που είναι μικρότεροι του 10 και 8 που είναι μικρότεροι του 20.

Παριστάνοντας τη συνάρτηση $\pi(x)$ σε μία μεγαλύτερη περιοχή του οριζόντιου άξονα παρατηρούμε όλο και περισσότερα σκαλοπάτια, και φυσικά, σύμφωνα με την απόδειξη οτυ Ευκλείδη για το άπειρο πλήθος των πρώτων αριθμών, πρόκειται για μία άπειρη ακολουθία σκαλοπατιών που δεν καταλήγει κάπου (δεν υπάρχει τελευταίο σκαλοπάτι!). (Μπορεί ο Ligeti όταν έγραφε το κομμάτι για πιάνο "The devil's  Staircase" να μην εμπνέονταν από τη συνάρτηση  $\pi(x)$, αλλά σίγουρα της ταιριάζει...[~] )

Γραφικές παραστάσεις της συνάρτησης $\pi(x)$ σε δύο διαφορετικά διαστήματα, (α) $x\in[2, 100]$ και (β) $x\in[2,\ 350]$. Στα γραφήματα αυτά φαινεται καλύτερα η κλιμακωτή δομή της συνάρτησης $\pi(x)$.

Πριν όμως προχωρήσουμε, κρίνεται αρκετά οφέλιμο να βαδίσουμε στα χνάρια του Gauss και να δούμε τον τρόπο με τον οποίο ο μεγάλος γερμανός μαθηματικός κατέληξε σε ένα πολύ σημαντικό αποτέλεσμα σχετικά με τη συνάρτηση $\pi(x)$. 

Ιχνηλατώντας τη σκέψη του Gauss

H μελέτη του Gauss για την κατανομή των πρώτων ξεκίνησε με την διερεύνηση της τοπικής πυκνότητας των πρώτων κοντά σε έναν αριθμό $x$, [1]. O Gauss μετρούσε τους πρώτους χωρίζοντας το σύνολο των ακεραίων σε διαστήματα των χιλίων. Η καταμέτρηση γινόταν με τη βοήθεια της συναρτησης

\[
\Delta(x):=\frac{\pi(x+500) - \pi(x - 500)}{1000} \]

Η έκφραση αυτή αντιστοιχεί στην πιθανότητα κάποιος που επιλέγει τυχαία και με ομοιόμορφο τρόπο σε όλη την έκταση του διαστήματος έναν ακέραιο, αυτός να είναι πρώτος. Αυτό μπορεί να γίνει για κάθε διάστημα $(x-500,\ x+500]$. Ο Gauss θεώρησε το αντίστροφο της συνάρτησης $\Delta(x)$ και εμπειρικά κατέληξε στο $\Delta(x)\approx 1/\log{x}$. Δηλαδή αυτό που έκανε ο Gauss ήταν να υπολογίζει τιμές της συνάρτησης $\Delta(x)$ και για τις εκάστοτε τιμές της μεταβλητής $x$ υπολόγισε τις τιμές της συνάρτησης $1/\log{x}$. Αυτό που διαπίστωσε ήταν ότι η διαφορά των δύο αυτών συναρτήσεων κατά γενικό κανόνα να μειώνεται καθώς αυξάνει το $x$.

Το διαισθητικό αποτέλεσμα του Gauss μοιάζει πάρα πολύ με τα αποτελέσματα που καταλήξαμε όταν μελετούσαμε τους πρώτους πιθανοκρατικά, σε μία παλιότερη σειρά αναρτήσεων (βλ. [~]).

Αυτό βέβαια δεν είναι τυχαίο. Την έμπνευση αυτής της ανάλυσης την οφείλουμε στον Gauss, μόνο που ορίσαμε τη συνάρτηση της τοπικής πυκνότητας με έναν διαφορετικό τρόπο. Ωστόσο, το αποτέλεσμα είναι το ίδιο.

Carl Friedrich Gauss (1777 - 1855)

Με τη βοήθεια του υπολογιστή και του Mathematica θα επιχειρήσουμε να επαναλάβουμε τους  υπολογισμούς του Gauss. Πρέπει να λάβουμε υπόψη ότι την εποχή του Gauss ήταν γνωστό το πλήθος των πρώτων μέχρι το 3 000 000 από έναν πίνακα που είχε καταρτίσει από μόνος του, [3].  Σε ηλικία 15 ετών ο Gauss άρχισε να ασχολείται με το συγκεκριμένο θέμα. Μέχρι τότε είχε καταφέρει να  καταρτίσει ακριβείς πίνακες με τους πρώτους που είναι μικρότεροι του 10009.

Ο Gauss ξεκίνησε από την παρατήρηση ότι μέχρι το 10 υπάρχουν 4 πρώτοι (οι 2, 3, 5 και 7) και διπλασιάζοντας το διάστημα των ακέραιων μέχρι το 20, συναντάμε 4 καινούργιους πρώτους (11,13, 17 και 19), έχοντας συνολικά 8 πρώτους (βλέπε σχήμα 1). Όμως μέχρι το 100 το σύνολο των πρώτων είναι μόλις 25. Αυτό σημαίνει ότι η συχνότητα με την οποία εμφανίζονται οι πρώτοι καθώς αυξάνουμε το διάστημα μειώνεται. Για παράδειγμα υπάρχουν μόνο 2 πρώτοι μεταξύ του 20 και του 30.

Το ενδιαφέρον του Gauss δεν ήταν η εύρεση των πρώτων σε μεγαλύτερα διαστήματα ακέραιων,  αλλά επικεντρώνονταν περισσότερο στον τρόπο που κατανέμονται. Για να ερευνήσει κάτι τέτοιο χρειαζόταν να γνωρίζει όλους τους πρώτους σε αυτά τα διαστήματα. Έχοντας φτιάξει ακριβείς πίνακες με τους πρώτους μέχρι και τον 10009  ήταν σε θέση να πειραματιστεί με την συνάρτηση της τοπικής πυκνότητας. Όπως φαίνεται και από το παρακάτω γράφημα η προσέγγιση του αντίστροφου λογάριθμου $1/\log{x}$ φαίνεται να είναι καλή, παρόλο που οι ταλαντώσεις της $\Delta(x)$ για τις τελευταίες χιλιάδες γίνονται όλο και μεγαλύτερες.

Τα πρώτα πειράματα του Gauss με τη συνάρτηση τοπικής πυκνότητας των πρώτων $\Delta(x)$ στην προσπάθειά του να επαληθεύσει την υπόθεσή του σχετικά με την τάση που έχει η συνάρτηση να μειώνεται για όλο και περισσότερα διαστήματα. Ο Gauss υπολόγιζε την τιμή της $\Delta(x)$ σε διαστήματα ανά 1000 ακέραιους, έχοντας έτσι 10 τιμές που ταλαντώνονται γύρω από την συνάρτηση $1/\log{x}$. Παρόλα αυτά, ο Gauss αναγνώρισε το γεγονός ότι για την καλύτερη  εξέταση της υπόθεσής του απαιτούνταν περισσότεροι πρώτοι σε μεγαλύτερα διαστήματα ακέραιων.

Όπως είχε αναφέρει,

Πολύ συχνά αφιέρωνα ένα τέταρτο της ώρας προκειμένου να μετράω μία χιλιάδα. Όμως, κατέληξα να τα παρατήσω εντελώς, χωρίς να έχω προλάβει να ολοκληρώσω το πρώτο εκατομμύριο (ακεραίων).(δική μου ελεύθερη μετάφραση [2])

Το θέμα αυτό δεν έπαψε να απασχολεί τον Gauss. Αυτό το διαπιστώνουμε έμμεσα από τις σημειώσεις του, όπου δε φαίνεται να δείχνουν ότι προσπαθούσε να βρει μία απλή σχέση (όπως εκείνη του αντίστροφου λογάριθμου). Ωστόσο οι σημειώσεις του βρίθουν από τέτοιες σχέσεις. Συνέχεια πειραματίζονταν και διατύπωνε υποθέσεις, τις οποίες διερευνούσε με ακόμη περισσότερα πειράματα και τις άλλαζε διαρκώς με καινούργιες σε όλη σχεδόν τη διάρκεια της ζωής του [2]. Παρόλα αυτά η αρχική υπόθεση, που είχε κάνει στα εφηβικά του χρόνια, κατείχε κεντρική θέση και σε όλη τη διάρκεια των ερευνών του επέκτεινε τη λίστα των πρώτων μέχρι και το 3000000, [3]. Με άλλα λόγια ήταν γνωστή ακριβώς η τιμή της $\pi(x)$ για $x \le 3 000 000$. Επομένως, μπορούμε να υπολογίσουμε 3000 τιμές της $\Delta(x)$ σε διαστήματα 1000 ακέραιων. Στην παρακάτω γραφική παράσταση παρουσιάζεται η συνάρτηση $\Delta(x)$ σε κοινό σύστημα αξόνων με την συνάρτηση $1/\log{x}$ στο διάστημα $[2, 3\times10^{6}]$.

Κοινή γραφική παράσταση της αντίστροφης λογαριθμικής συνάρτησης (κόκκινο) και της τοπικής πυκνότητας των πρώτων ανά 1000 ακέραιους (μπλε) στο διάστημα $[2,\ 3000000]$. Παρόλο που η συνάρτηση $\Delta(x)$ εμφανίζει απότομες ταλαντώσεις η αντίστροφη λογαριθμική συνάρτηση $1/\log{x}$ καταφέρνει να προσεγγίσει τη μέση μεταβολή της $\Delta(x)$.

Ωστόσο, η υπόθεση του Gauss παρέμενε αναπόδεικτη. Σημαντικό στοιχείο που διαφωτίζει την έρευνα του Gauss αποτελεί ένα γράμμα που είχε στείλει στον μαθητή του Johann Franz Encke [~], που χρονολογείται προς το τέλος του 1849, πέντε χρόνια πριν από το θάνατό του.

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

Την ίδια χρονιά, o Gauss έστρεψε το ενδιαφέρον της ακαδημίας του Hamburg στην περίπτωση του Johann Martin Zacharias Dase (1824 - 1861). O Dase έχει μείνει στην ιστορία για τις αξιοσημείωτες υπολογιστικές του ικανότητες. Ο Gauss αξιολογώντας τις ικανότητες αυτές συνέταξε μία συστατική επιστολή γράφοντας, μεταξύ άλλων,

"(...) Με μικρούς αριθμούς, οποιοσδήποτε που διαθέτει μία υπολογιστική ευχέρεια μπορεί να απαντήσει σε ερωτήματα σχετικά με τη διαιρετότητα ενός αριθμού σχεδόν αμέσως, για μεγαλύτερους αριθμούς κάτι τέτοιο είναι επίσης δυνατόν με λιγότερο ή περισσότερο κόπο, ο οποίος όμως αυξάνεται για μεγαλύτερους αριθμούς, που ακόμα και για έναν έμπειρο λογιστή θα χρειάζονταν ώρες ή άκόμα και ημέρες, για έναν και μόνο αριθμό, ενώ για ακόμα μεγαλύτερους η λύση σε τέτοια ζητήματα καταλήγει να είναι πρακτικά αδύνατη. Διαθέτετε όλα τα απαραίτητα προσόντα (για την κατάρτιση πινάκων με τους παράγοντες των ακέραιων) σε έναν υψηλό βαθμό, μία αξιοσημείωτη οξύνοια και σβελτάδα στην διαχείρηση αριθμητικών πράξεων(...)"(δική μου ελεύθερη μετάφραση [2])

Η ακαδημία επιστημών του Hamburg προσέλαβε τον Dase για να κατασκευάσει τους πίνακες των παραγόντων για τους ακέραιους μεταξύ του 7 000 000 και 10 000 000. Όμως ο Dase μετά από δύο χρόνια πέθανε χώρις να καταφέρει να ολοκληρώσει το έργο του, φτάνοντας μέχρι το 8 000 000, [4].

Από τον ορισμό της, η $\Delta(x)$ αντιστοιχεί σε μία μέση τιμή της μεταβολής της συνάρτησης $\pi(x)$ σε αυτά τα διαστήματα. Επομένως, διαδοχικές τιμές της συνάρτησης $\Delta(x)$ υποδεικνύουν τον ρυθμό που μεταβάλλεται η διακριτή συνάρτηση $\pi(x)$. Αυτό με τη σειρά του, μας δίνει στοιχεία για τον τρόπο που μεταβάλλεται η κατανομή των πρώτων σε ίσα διαστήματα όλο και μεγαλύτερων ακέραιων. Πρόκειται, λοιπόν, για τον τρόπο που μεταβάλλεται η πυκνότητα των πρώτων στο σύνολο των ακέραιων.

Όπως θα δούμε και αργότερα πίσω από την υπόθεση του Gauss κρύβεται το θεώρημα των πρώτων αριθμών, ένα πολύ σημαντικό αποτέλεσμα που έχει μία ισοδύναμη διατύπωση. Εντούτοις, άργησε πολύ να αποδειχτεί, περίπου 100 χρόνια από τότε που ο Gauss είχε γράψει τη σημείωση


πρώτοι αριθμοί μικρότεροι από έναν ακέραιο $x$: $\frac{x}{L{x}}$
όπου με $L$ συμβόλιζε τον λογάριθμο. Η παραπάνω πρόταση σήμερα γράφεται ως εξής


\[
\pi(x)\approx \frac{x}{\log{x}} \]
 Σε μια άλλη ανάρτηση θα εξετάσουμε τη σχέση αυτή εστιάζοντας το ενδιαφέρον μας περισσότερο στη συνάρτηση $\pi(x)$.







_______________________ΣΗΜΕΙΩΣΕΙΣ & ΑΝΑΦΟΡΕΣ

[1] - Pollack P. Not Always Burried Deep - A Second Course in Εlementary Number Theory, American Mathematical Societym 2009.

[2] - Dunnington G.W., Gauss - Titan of Science, The Mathematical Association of America, 2004.

[3] - Yan S. Y., Number Theory for Computing, Springer, 2002.

[4] - Υπάρχει μία μαρτυρία για τις υπολογιστικές ικανότητες του Dase, από τις σημειώσεις του μαθηματικού και αστρονόμου Heinrich Christian Schumacher, και παρατίθενται από τον Scripture στο άρθρο Αrithmetical Prodiges, The American Journal of Psychology 4 (1)(1891),  ως εξής

"...μπορούσε να πολλαπλασιάσει μεγάλους αριθμούς στο μυαλό του, όμως όταν οι αριθμοι ήταν αρκετά μαγάλοι απαιτούνταν περισσότερος χρόνος. Μια φορά ο Schumacher του έδωσε τους αριθμούς 79532853 και 93758479 να τους πολλαπλασιάσει και μέχρι να καταγράψει το αποτέλεσμα , που είχε υπολογίσει με το μυαλό του, σε ένα χαρτί, πέρασαν 54 δευτερόλεπτα. Μπορούσε ναολλαπλασιάσει δύο εικοσαψήφιους αριθμούς σε 6 λεπτά, δύο σαρανταψήφιους σε 40 λεπτά και δύο εκατονταψήφιους σε 8 ώρες και τρία τέταρτα. Επίσης ο χρόνος των 52 λεπτών είχε καταγραφεί για την εξαγωγή της τετραγωνικής ρίζας ενός εκατονταψήφιου ακέραιου."

O υπολογιστικός χρόνος του Dase είναι πολυωνυμικός (!!!) και βάσει των παρατιθέμενων δεδομένων προσεγγίζεται από την καμπύλη 2ου βαθμού $1067.67- 140.525 x+4.44707x^2$ όπως δίνει η εντολή Fit του Μathematica.