Το πρόβλημα του Collatz (δεν) λύθηκε!

Όταν ο Εrdos έμαθε για πρώτη φορά για την εικασία του Collatz σίγουρα θα του φάνηκε ένα πολύ ενδιαφέρον πρόβλημα που αξίζει κάποιος να ασχοληθεί μαζι του. Όταν ξεκίνησε να ασχολείται με το πρόβλημα κατέληξε στο συμπέρασμα ότι τα μαθηματικά δεν είναι ακόμη έτοιμα για να προσεγγίσουν τέτοιου είδους προβλήματα.

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

Εν μέρει ο Erdos είχε δίκιο, αφού για μισό αιώνα τουλάχιστον δεν είχε γίνει καμία πρόοδος, μέχρι προχτές στις 01/06, όπου δημοσιεύτηκε ένα σχετικό άρθρο [~], γραμμένο από τον Gerhard Opfer, του πανεπιστημίου του Hamburg.(*)

Η εικασία του Collatz ή αλλιώς το πρόβλημα $3n + 1$ προκαλεί ιδιαίτερη έκπληξη, γιατί παρόλο που η διατύπωσή του είναι εξαιρετικά απλή, η λύση του δεν είναι καθόλου εύκολη.

Επιλέξτε όποιον αριθμό θέλετε. Αν είναι ζυγός διαιρέστε τον με το 2. Αν είναι περιττός πολλαπλασιαστε με το 3 και προσθέστε 1. Αν επαναλάβετε αυτή την απλή διαδικασία θα καταλλήξετε στον αριθμό 1.

Η τελευταία πρόταση δεν έχει αποδειχτεί. Το άρθρο του Opfer υποστηρίζει ότι παρουσιάζει μία αναλυτική απόδειξη αυτής της πρότασης.

(*) UPDATE: To πρόβλημα του Collatz δυστυχώς δεν λύθηκε. Η απόδειξη που παρουσίασε ο Οpfer φαίνεται να έχει σημαντικά κενά, τα οποία επεσήμαναν διάφοροι μαθηματικοί στο διαδίκτυο [~]

Μία σύντομη αναδρομή*

Η καταγωγή του προβλήματος δεν είναι γνωστή με βεβαιότητα. Το σίγουρο είναι ότι για πολύ καιρό κυκλοφορούσε στους μαθηματικούς κύκλους και ιδιαίτερα μεταξύ μαθηματικών που δούλευαν στη θεωρία αριθμών. Ο ίδιος ο Collatz από τα φοιτητικά του χρόνια έδειξε ενδιαφέρον για το πρόβλημα από τις αρχές της δεκαετίας του 1930 και από ότι φαίνεται αναφερόταν ήδη στις διαλέξεις των Edmund Landau, Oskar Perron και Issai Schur.

Η πρώτη γραπτή εμφάνιση του προβλήματος υπάρχει στο σημειωματάριό του με ημερομηνία 1η Ιουλίου 1930 και δεν δημοσίευσε ποτέ κάποιο σχετικό άρθρο με το πρόβλημα παρά μόνο το κυκλοφόρησε προφορικά στο διεθνές συνέδριο μαθηματικών στο Cambridge το 1950. Στα πρακτικά του συνεδρίου εμφανίζεται και το πρόβλημα.

Στα επόμενα χρόνια το πρόβλημα γίνεται ιδιαίτερα δημοφιλές. O Hasse συζητούσε με διάφορους άλλους μαθηματικούς πιθανές γενικεύσεις, ενώ ο Kakutani ευθύνεται σε μεγάλο βαθμό για τη διάδοσή του, που είχε λάβει διαστάσεις επιδημίας! Χαρακτηριστική είναι η μαρτυρία του Kakutani  ότι "Για έναν περίπου μήνα όλος ο κόσμος στο Yale δούλευε πάνω στο πρόβλημα χωρίς αποτέλεσμα". Εκτός από τον Kakutani στο πανεπιστήμιο του Chicago ο Lagarias φρόντισε να μεταδώσει την επιδημία του προβλήματος χωρίς πάλι κανένα αποτέλεσμα. Κυκλοφορούσε μάλιστα και ένα αστείο πως το πρόβλημα ήταν κομμάτι μιας συνομωσίας που είχε σκοπό να καθυστερήσει τη μαθηματική έρευνα στις Η.Π.Α.

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

Δουλεύοντας με το πρόβλημα $3n+1$

Η πρώτη εντύπωση για την παραπάνω διαδικασία είναι ότι πρόκειται για κάτι πολύ απλό. Τί είδους όμως ακολουθίες αριθμών μπορούν να προκύψουν. Ας δούμε μερικά παραδείγματα, όπου γρήγορα θα διαπιστώσετε ότι ο όρος $3n+1$ μπορεί να περιπλέξει αρκετά τα πράγματα. Ξεκινάμε με τον 5,

$$ 5\rightarrow 16\rightarrow 8\rightarrow 4 \rightarrow 2\rightarrow 1$$

Ας περάσουμε στον επόμενο

$$ 6\rightarrow 3\rightarrow 10\rightarrow 5 \rightarrow 16\rightarrow 8\rightarrow 4 \rightarrow 2\rightarrow 1$$

ενώ για τον 8 έχουμε

$$8\rightarrow 4 \rightarrow 2\rightarrow 1$$

Οι ακολουθίες των ακεραίων έχοντας ως αρχική τους τιμή μεγαλύτερους ακέραιους δεν μεταβάλλεται σε πλήθος αρκετά. Μέχρι που φτάνουμε στον αριθμό 27 όπου δημιουργείται μία ακολουθία με 111 ακέραιους και μέχρι να καταλήξει στο 1 έχει φτάσει μέχρι και το 9232... Ωστόσο, όσο μεγάλες κι αν είναι αυτές οι ακολουθίες πάντοτε τερματίζουν στον 1. Και αυτό είναι που απέδειξε ο Gerhard Opfen.

Στη συνέχεια διατρέχουμε τον άξονα τον ακεραίων μέχρι το 1000 και μελετάμε τη συμπεριφορά που έχει η παραπάνω διαδικασία, την οποία μπορούμε να καλούμε Κανόνα του Collatz. Στην πλαίσιο, έχω φτιάξει σε Mathematica μία εφαρμογή για τον υπολογισμό της ακολουθίας ακεραίων που παράγει ο κανόνας του Collatz. Για να τη χρησιμοποιήσετε θα πρέπει να έχετε το σχετικό plugin (διαβάστε παρακάτω).

Αν το παραπάνω το βλέπετε ως στατική εικόνα τότε δεν έχετε εγκατεστημένο το plugin του CDF player, της εταιρίας Wolfram Research. Εγκαθιστώντας το  plugin θα μπορείτε να αλληλεπιδράσετε με την παραπάνω εφαρμογή αλλάζοντας τις τιμές κατα βούληση. Μπορείτε να κατεβάσετε δωρεάν τον CDF player από εδώ [~] .

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

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

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

Ο οριζόντιος άξονας αντιστοιχεί στον άξονα των ακέραιων μεταξύ 100 και 10000 χωρισμένο σε διαδοχικές πενηντάδες (2000 πενηντάδες ακέραιων). Για καθεμία πενηντάδα αντιστοιχεί και μία τιμή στη συνάρτηση. Η τιμή της συνάρτησης φαίνεται στον κάθετο άξονα και αντιστοιχεί στη μέση τιμή του μήκους που έχουν οι ακολουθίες των ακέραιων της εκάστοτε πενηντάδας. Παρατηρούμε ότι υπάρχει μία γενική αυξητική τάση του πλήθους των στοιχείων μιας ακολουθίας, που όμως περιέχει έντονες αυξομειώσεις.

Γενικά, όσο ξεκινάει να "παίζει" κανείς με τις ακολουθίες, ή και με άλλα μεγέθη σχετικά με το πρόβλημα $3n + 1$ μπορούν να προκύψουν ιδιαίτερα ενδιαφέροντα θέματα. Σε επόμενη ανάρτηση θα ασχοληθούμε ξανά με το πρόβλημα εξετάζοντας διάφορες κλάσεις αριθμών. Για παράδειγμα, αν θέσουμε ως αρχικές τιμές μόνο πρώτους, τί ακολουθίες παράγουν; Από την άλλη ποιοι αριθμοί παράγουν στατιστικά μεγαλύτερες ακολουθίες, οι ζυγοί ή οι περιττοί; Τί λέτε;


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

* Η ενότητα αυτή προέρχεται από το 
Γ.-Α. Δημάκης, Χ. Ερμόπουλος, Ο.Βάτζος, "Το πρόβλημα του $3n+1$ σαν ένα διακριτό δυναμικό σύστημα", Τάξη και Χάος, τόμος έβδομος, Εκδόσεις Πνευματικός, Αθήνα 2002.