Εικασία του Κόλατζ

Η εικασία του Κόλατζ (αγγλικά: Collatz conjecture) είναι μια εικασία στα μαθηματικά η οποία πήρε την ονομασία της από τον Λόθαρ Κόλατζ (Lothar Collatz), ο οποίος την πρότεινε για πρώτη φορά το 1937. Η εικασία είναι επίσης γνωστή ως εικασία 3n+1, εικασία Ούλαμ από τον Στάνιλσαβ Ούλαμ (Stanislaw Ulam), πρόβλημα Κακουτάνι από τον Σιζούο Κακουτάνι (Shizuo Kakutani), εικασία Θουέιτς από τον Μπράιν Θουέιτς (Bryan Thwaites), αλγόριθμος του Χάσε από τον Χέλμουτ Χάσε (Helmut Hasse), ή πρόβλημα των Συρακουσών. Η ακολουθία των αριθμών που εμπλέκονται αναφέρεται ως ακολουθία χαλαζιού (επειδή οι τιμές συνήθως υπόκεινται σε πολλαπλές καταβάσεις και αναβάσεις σαν τους κόκκους του χαλαζιού σε ένα σύννεφο, είτε ως θαυμαστοί αριθμοί.
Η εικασία συνοψίζεται ως εξής. Πάρτε οποιοδήποτε θετικό ακέραιο n. Αν ο n είναι άρτιος, διαιρέστε τον δια το 2, για να πάρετε το n/2. Εάν ο n είναι περιττός, πολλαπλασιάστε τον επί 3 και προσθέστε 1 για να πάρετε το 3n+1. Επαναλάβετε τη διαδικασία (η οποία έχει χαρακτηριστεί ως "Μισό Ή Τριπλό Συν Ένα", αγγλικά "Half Or Triple Plus One, HOTPO) επ' αόριστον. Κατά την εικασία, από όποιο αριθμό κι αν ξεκινήσετε, θα καταλήξετε πάντα στο ένα.
Ο Πωλ Έρντος δήλωσε σχετικά με την εικασία του Κόλατζ: "Τα μαθηματικά μπορεί να μην είναι έτοιμα για τέτοια προβλήματα." Επίσης, πρόσφερε $500 για την λύση του.

Κύκλοι

Κάθε αντιπαράδειγμα στην εικασία Κόλατζ θα έπρεπε να αποτελείται είτε από μία άπειρη αποκλίνουσα τροχιά ή ένα κύκλο διαφορετικό από τον τετριμμένο (4, 2, 1). Έτσι αν κάποιος μπορούσε να αποδείξει ότι αυτά τα είδη αντιπαραδειγμάτων είναι αδύνατο να υπάρχουν, τότε όλοι οι θετικοί ακέραιοι θα είχαν τροχιά που θα έφτανε στον τετριμμένο κύκλο. Ένα τέτοιο ισχυρό αποτέλεσμα δεν έχει αποδειχτεί, ωστόσο ορισμένοι τύποι κύκλων έχουν αποκλειστεί.
Ο τύπος ενός κύκλου μπορεί να οριστεί χρησιμοποιώντας τον "συντομευμένο" ορισμό της συνάρτησης Κόλατζ,  για περιττά n και για άρτια n. Ένας κύκλος είναι μια ακολουθία  όπου,  και ούτω καθεξής, μέχρι σε κλειστό βρόχο. Σύμφωνα με αυτό τον ορισμό, ο μόνος γνωστός κύκλος είναι ο τετριμμένος (1, 2). Αν και το 4 είναι μέρος του τετριμμένου κύκλου για την αρχική συνάρτηση Κόλατζ, δεν ανήκει στον κύκλο της "συντομευμένης" συνάρτησης (1, 2). 
Ένας k-κύκλος είναι ένας κύκλος που μπορεί να χωριστεί σε 2k συνεχόμενες υποακολουθίες: k αύξουσες ακολουθίες περιττών αριθμών εναλλασσόμενες με k φθίνουσες ακολουθίες άρτιων αριθμών. Για παράδειγμα, εάν ο κύκλος αποτελείται από μια μοναδική αύξουσα ακολουθία περιττών αριθμών ακολουθούμενη από μία φθίνουσα ακολουθία άρτιων αριθμών, ονομάζεται 1-κύκλος.
Ο Steiner (1977) απέδειξε ότι δεν υπάρχει 1-κύκλος, εκτός από τον τετριμμένο (1, 2). Ο Simons (2004) χρησιμοποίησε την μέθοδο του Steiner για να αποδείξει ότι δεν υπάρχει 2-κύκλος. Οι Simons & de Weger (2003) επέκτειναν αυτήν την απόδειξη φτάνοντας μέχρι τους 68-κύκλους: δεν υπάρχει k-κύκλος με k = 68. Πέραν του 68, η μέθοδος αυτή δίνει άνω φράγματα για τα στοιχεία σε ένα τέτοιο κύκλο: για παράδειγμα, αν υπάρχει 75-κύκλος, τότε τουλάχιστον ένα στοιχείο του κύκλου είναι μικρότερο από 2385×2⁵⁰. Όσο συνεχίζουν  εξαντλητικές αναζητήσεις με υπολογιστές, τόσο αποκλείεται η ύπαρξη όλο και μεγαλύτερων κύκλων. Διαισθητικά, το επιχείρημα πάει ως εξής: δεν χρειάζεται να ψάχνουμε για κύκλους που έχουν το πολύ 68 τροχιές, όπου κάθε τροχιά αποτελείται από συνεχόμενα ανεβάσματα ακολουθούμενα από συνεχόμενα κατεβάσματα. Δείτε παρακάτω για μια ιδέα για το πώς θα μπορούσε κανείς να βρει άνω φράγμα για τα στοιχεία ενός κύκλου.

Υποστηρικτικά επιχειρήματα

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

Πειραματικές αποδείξεις

Η εικασία έχει ελεγχθεί από τον υπολογιστή για όλες τις τιμές έως 2⁶⁰. Όλες οι αρχικές τιμές που έχουν δοκιμαστεί μέχρι σήμερα καταλήγουν στην επανάληψη του κύκλου (4, 2, 1), που έχει μόνο τρεις όρους. Από αυτό το κάτω φράγμα για την τιμή εκκίνησης, έχει βρεθεί κατώτερο όριο για τον αριθμό των όρων επαναλαμβανόμενων κύκλων, εκτός του (4, 2, 1). Όταν ανακαλύφθηκε αυτή η σχέση το 1981, ο τύπος έδωσε κάτω φράγμα με 35.400 όρους.
Η απόδειξη που έδωσε ο υπολογιστής δεν είναι 'κανονική' απόδειξη ότι η εικασία Κόλατζ είναι αληθινή. Όπως φαίνεται σε διάφορες περιπτώσεις, όπως η εικασία Pólya, η εικασία Μέρτενς και ο αριθμός Skewes, μερικές φορές τα αντιπαραδείγματα για μια εικασία εντοπίζονται σε πολύ μεγάλους αριθμούς.

Ένα πιθανοτικό ευρεστικό επιχείρημα

Αν κάποιος πάρει μόνο τους περιττούς αριθμούς με τη σειρά που παράγονται από την διαδικασία  του Κόλατζ, τότε κάθε περιττός αριθμός είναι, κατά μέσο όρο, μεγαλύτερος κατά τα 3/4 του προηγούμενου. (Για την ακρίβεια, ο  γεωμετρικός μέσος των λόγων των αποτελεσμάτων είναι 3/4.) Αυτό παράγει ένα ευρεστικό επιχείρημα ότι κάθε ακολουθία χαλαζιού θα πρέπει να φθίνει μακροπρόθεσμα, αν και αυτό δεν είναι απόδειξη για όλους τους κύκλους, παρά μόνον κατά της απόκλισης. Το επιχείρημα αυτό δεν είναι απόδειξη, επειδή υποθέτει ότι οι ακολουθίες χαλαζιού συναρμολογούνται από πιθανοτικά ασυσχέτιστα γεγονότα. (Ωστόσο, καθιερώνει αυστηρά ότι η 2-αδική επέκταση της συνάρτησης Κόλατζ  έχει δύο βήματα διαίρεσης για κάθε βήμα πολλαπλασιασμού για σχεδόν όλες τις 2-αδικές τιμές εκκίνησης.)
Αλλά ακόμη κι αν το πιθανοτικό επιχείρημα ήταν αυστηρό, αυτό πάλι θα συνεπαγόταν ότι η εικασία είναι σχεδόν σίγουρα αληθής για κάθε δεδομένο ακέραιο, που δεν συνεπάγεται απαραίτητα ότι είναι αληθής για όλους τους ακεραίους.

Αυστηρά όρια

Αν και δεν γνωρίζουμε υπό την αυστηρή έννοια ότι όλοι οι θετικοί αριθμοί καταλήγουν στο 1 με την ακολουθία Κόλατζ, είναι γνωστό ότι πολλοί αριθμοί φτάνουν. Ειδικότερα, οι Krasikov και Lagarias έδειξαν ότι το πλήθος των ακεραίων στο διάστημα [1, x] που τελικά φτάνουν στο ένα είναι τουλάχιστον ανάλογο με το x0.84.

Αντίστροφη

Υπάρχει και μια άλλη προσέγγιση για  να αποδειχθεί η εικασία, που χρησιμοποιεί την κάτω-προς-επάνω μέθοδο ανάπτυξης του λεγόμενου γράφου Κόλατζ. Ο γράφος Κόλατζ  είναι ένας γράφος που ορίζεται από την αντίστροφη σχέση
Έτσι, αντί να αποδείξουμε ότι όλοι οι θετικοί ακέραιοι καταλήγουν τελικά στο 1, μπορούμε να προσπαθήσουμε να αποδείξουμε ότι το 1 οδηγεί σε όλους τους θετικούς ακεραίους. Για κάθε ακέραιο ,  αν και μόνον αν (ανν) . Ισοδύναμα,  ανν . Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο αν εξαιρέσουμε τον βρόχο 1-2-4 (τον αντίστροφο του κύκλου (4, 2, 1) της αρχικής συνάρτησης f όπως ορίζεται στην ενότητα Διατύπωση του προβλήματος αυτού του άρθρου).
Όταν η σχέση 3n+1 της συνάρτησης f αντικαθίσταται από τη "συντομευμένη" μορφή (3n+1)/2, ο γράφος Κόλατζ ορίζεται από την αντίστροφη σχέση,
Για κάθε ακέραιο n,  ανν . Ισοδύναμα,  ανν . Σύμφωνα με την εικασία, αυτή η αντίστροφη σχέση σχηματίζει ένα δέντρο, αν εξαιρέσουμε τον βρόχο 1-2 (τον αντίστροφο του κύκλου (2, 1) της "συντομευμένης" συνάρτησης).
Εναλλακτικά, αντικαταστήστε το 3n+1 με το  n' / H(n'), όπου  n' = 3n+1 και  H(n')  είναι η μεγαλύτερη δύναμη του 2 που διαιρεί το n'  (χωρίς να αφήνει υπόλοιπο). Η προκύπτουσα συνάρτηση f είναι μια απεικόνιση από περιττούς αριθμούς σε περιττούς αριθμούς. Τώρα, ας υποθέσουμε ότι για κάποιον περιττό αριθμό n, εφαρμογή αυτής της συνάρτησης k φορές καταλήγει στον αριθμό 1 (δηλαδή ). Τότε στο δυαδικό σύστημα, ο αριθμός n μπορεί να γραφτεί ως συνένωση των συμβολοσειρών wₖ wₖ₋₁ ... w₁, όπου κάθε wₕ είναι πεπερασμένo και συνεχόμενo τμήμα της αναπαράστασης του 1 / 3ʰ. Η αναπαράσταση του n ως εκ τούτου περιέχει το επαναλαμβανόμενο τμήμα του 1 / 3ʰ, όπου κάθε επαναλαμβανόμενο τμήμα μπορεί να περιστρέφεται και έπειτα να αναπαράγεται μέχρι έναν πεπερασμένο πλήθος δυαδικών ψηφίων. Αυτό συμβαίνει μόνο στη δυαδική αναπαράσταση. Σύμφωνα με την εικασία, κάθε δυαδική συμβολοσειρά s που τελειώνει σε '1' μπορεί να επιτευχθεί με μια αναπαράσταση αυτής της μορφής (προθέτοντας μηδενικά '0' στο s).

Παράδειγμα

Ξεκινάμε με το 7 που στο δυαδικό σύστημα γράφεται 111. Προκύπτει η εξής ακολουθία χαλαζιού:
         111
        1111+
       10110
      10111+
     100010
    100011+
    110100
   11011+
  101000
 1011+
10000

Σύστημα ετικετών

Για την συνάρτηση Κόλατζ με τον τύπο
οι ακολουθία χαλαζιού μπορεί να υπολογιστεί από το εξαιρετικά απλό σύστημα 2-ετικετών με κανόνες παραγωγής a→ bc, b → a, c → aaa. Σε αυτό το σύστημα, ο θετικός ακέραιος n αντιπροσωπεύεται από μια σειρά από n a και η επανάληψη της λειτουργίας ετικέτας τερματίζεται σε οποιαδήποτε λέξη μήκους λιγότερου από 2 (προσαρμοσμένο από το De Mol.)
Η εικασία Κόλατζ ισοδύναμεί με τη δήλωση ότι αυτό το σύστημα ετικετών με μια αυθαίρετη πεπερασμένη συμβολοσειρά από a, όπως η αρχική λέξη, τελικά σταματά.

Κυκλικά όρια

Η εξίσωση 1 μας δίνει επίσης μια ιδέα για το πώς μπορεί κανείς να αποδείξει ότι δεν υπάρχουν κύκλοι με συγκεκριμένα μήκη. Για έναν υποθετικό κύκλο μήκους n, ο αριθμητής φράσσεται άνω από το 3ⁿ - 2ⁿ (αυτό αντιστοιχεί σε ένα κύκλο με περιττούς αριθμούς μόνον). Ένα κάτω φράγμα για τον παρονομαστή μπορεί να ληφθεί θεωρώντας το n/m ως μια βέλτιστη κλασματική προσέγγιση του log(3)/log(2). Αυτά μαζί δίνουν ένα άνω φράγμα για το μοναδικό κλάσμα που παράγει ένα κύκλο μήκους n. Αν αυτό το άνω φράγμα είναι μικρότερο από τον μεγαλύτερο αριθμό για τον οποίο η εικασία έχει επαληθευτεί ότι ισχύει, τότε ένας κύκλος μήκους n είναι αδύνατος.

Το φράκταλ του Κόλατζ

Η επανάληψη της βελτιστοποιημένης απεικόνισης παραπάνω στο μιγαδικό επίπεδο παράγει το φράκταλ του Κόλατζ.  
Η επανάληψη κατά μήκος του άξονα των πραγματικών διερευνήθηκε από τον Chamberland και στο επίπεδο των μιγαδικών από τους Letherman, Schleicher, and Wood.

Η Απόλυτη Πρόκληση: Το  πρόβλημα 3x+1

Αυτός ο τόμος, επιμελημένος από τον Jeffrey Lagarias και δημοσιευμένος από την Αμερικανική Μαθηματική Εταιρεία, είναι μια συλλογή πληροφοριών σχετικά με την εικασία Κόλατζ, τις μεθόδους προσέγγισης και τις γενικεύσεις της. Περιλαμβάνει δύο επισκοπήσεις από τον επιμελητή και πέντε από άλλους συγγραφείς, σχετικά με την ιστορία του προβλήματος, τις γενικεύσεις, στατιστικές προσεγγίσεις και αποτελέσματα από την θεωρία υπολογισμού. Περιλαμβάνει, επίσης, ανατυπώσεις των πρώτων δημοσιεύσεων σχετικά με το θέμα (συμπεριλαμβανομένης μιας καταχώρισης από τον Λόθαρ Κόλατζ).