Η εικασία Collatz (5)

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

Για να θυμηθείτε όσα είπαμε την προηγούμενη εβδομάδα, δείτε εδώ, ενώ για όλες τις αναρτήσεις της σειράς, δείτε εδώ.

Απλές σκέψεις…

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

50 κόμβοι και με το ζόρι χωράνε στην οθόνη…

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

Ένα άλλο συμπέρασμα που μπορούμε να βγάλουμε εύκολα από το παραπάνω γράφημα είναι ότι αν ένας αριθμός $n$ εμφανίζεται στο γράφημα Collatz, τότε θα εμφανιστούν στην ίδια ευθεία – και πουθενά αλλού, δεδομένου ότι δεν σχεδιάζουμε διπλότυπους κόμβους – και όλοι οι αριθμοί της μορφής $2^kn$ για $k=0,1,\ldots$ Αυτό έχει κάποιο ενδιαφέρον, καθώς, αν προσέξει κανείς λίγο παραπάνω ένα γράφημα Collatz, θα δει ότι στην ουσία είναι σαν να διαμερίζει τους φυσικούς αριθμούς – ή, έστω, τους αριθμούς που εμφανίζονται στις κορυφές του – με τον τρόπο που φανερώνεται από τις γραμμές του. Με αυτό κατά νου, έχει νόημα να εξετάσουμε αν η σχέση $\sim_2$ που σχετίζει δύο θετικούς ακέραιους αριθμούς $m,n$ αν και μόνο αν το πηλίκο τους είναι (μη αρνητική) δύναμη του 2 είναι μία σχέση ισοδυναμίας. Αυστηρά, η παραπάνω σχέση ορίζεται ως εξής:

$n\sim_2m\Leftrightarrow\dfrac{n}{m}=2^k,$ για κάποιο $k=0,1,\ldots$

Αρχικά, σαφώς και ικανοποιείται η αυτοπάθεια, καθώς:

$\dfrac{n}{n}=2^0,$

για κάθε θετικό ακέραιο αριθμό $n.$ Τώρα, με τη συμμετρία έχουμε ένα θέμα, καθώς αν $n\sim_2m$ τότε έπεται ότι $\frac{n}{m}=2^k$ για κάποιον $k=0,1,\ldots$ άρα $n\geq m$ και, στην μη τετριμμένη περίπτωση που $n\neq m,$ έχουμε σαφώς $n>m$ άρα δε γίνεται να ισχύει $m\sim_2n.$ Επομένως, δεν είναι η $\sim_2$ μία σχέση ισοδυναμίας. Ωστόσο, αυτό δε μας πτοεί, καθώς η μεταβατικότητα ισχύει. Πράγματι, αν $n\sim_2m\sim_2k$ τότε υπάρχουν $a,b=0,1,\ldots$ έτσι ώστε:

$\displaystyle\frac{n}{m}=2^a,\ \frac{m}{k}=2^b.$

Πολλαπλασιάζοντας κατά μέλη, έχουμε:

$\displaystyle \frac{nm}{mk}=2^a2^b\Rightarrow \frac{n}{k}=2^{a+b},$

επομένως $n\sim_2k.$ Άρα, μπορεί να μην έχουμε στα χέρια μας μία σχέση ισοδυναμίας, έχουμε ωστόσο μία μεταβατική και αυτοπαθή σχέση η οποία μπορεί να μας πει κάποια πράγματα. Για την ακρίβεια, μπορεί να μην έχουμε καταφέρει να πετύχουμε τη συμμετρία, αλλά αυτό απλά σημαίνει ότι ίσως να πρέπει να ορίσουμε λίγο διαφορετικά τη σχέση μας. Αντί να ασχοληθούμε με πηλίκα, θα κάνουμε το εξής κόλπο: θα λέμε ότι δύο θετικοί ακέραιοι $n,m$ σχετίζονται με τη σχέση $\sim$ αν έχουν τα ίδια αναπτύγματα σε γινόμενο πρώτων, εξαιρώντας τις δυνάμεις του 2. Η εν λόγω σχέση είναι εύκολο να διαπιστωθεί ότι είναι σχέση ισοδυναμίας και ότι οι κλάσεις της έχουν ακριβώς αυτή τη μορφή, για κάποιον $\displaystyle n=2^{a_0}\prod_{k=1}^np_k^{a_k}$ , όπου $p_k$ πρώτοι διάφοροι του 2 και $a_k>0$ , ενώ $a_0\geq0$ :

$\displaystyle[n]=\left\{2^i\prod_{k=1}^np_k^{a_k}:i\geq0\right\}.$

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

Πιο σύνθετες σκέψεις…

Η πρώτη μας απλή σκέψη δεν έβγαλε σε κάτι ιδιαίτερα χρήσιμο, αλλά αυτό συμβαίνει συχνά στα μαθηματικά, κι όχι μόνο με απλές σκέψεις, είναι η αλήθεια. Κοιτάζοντας το παραπάνω γράφημα βλέπουμε ότι υπάρχουν κάποια κλαδιά που συνεχίζουν στο μοτίβο του πρώτου κλαδιού – δηλαδή κάθε δύο βήματα κι από μία διακλάδωση – κι άλλα κλαδιά, όπως αυτό που ξεκινά με το 21, που δεν έχουν καμία διακλάδωση. Γιατί να συμβαίνει αυτό, άραγε; Αν το καλοσκεφτούμε, η κλάση του 21 θα περιέχει αριθμούς που έχουν τη μορφή $2^k21.$ Για να εμφανιστεί κάπου διακλάδωση πρέπει να φτάσουμε σε έναν αριθμό της μορφής $3n+1$ για κάποιον θετικό ακέραιο $n>1.$ Επομένως, πρέπει να εξετάσουμε αν έχει ακέραιες λύσεις ως προς $k$ για τις διάφορες τιμές του $n$ η εξίσωση:

$2^k21=3n+1.$

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

Παραπάνω δείξαμε ότι, επί της ουσίας, αν $n$ είναι ένα πολλαπλάσιο του τρία, τότε όλοι οι αριθμοί της μορφής $2^kn$ περιέχονται στο γράφημα Collatz αν περιέχεται κι ο $n$ και μάλιστα – γιατί αυτό ισχύει για κάθε $n$ – ότι το γράφημα από εκεί και μετά δεν περιέχει διακλαδώσεις σε κανένα σημείο του – είναι μία ευθεία γραμμή, δηλαδή. Τι γίνεται όμως με τους αριθμούς που αφήνουν υπόλοιπο 1 ή 2 όταν διαιρεθούν με το 3;

Ας πάρουμε έναν αριθμό που αφήνει με το 3 υπόλοιπο 1, οπότε γράφεται στη μορφή $3x+1.$ Τότε, αυτός ο αριθμός αντιστοιχεί σε έναν κόμβο από τον οποίο μπορεί να προκύψει διακλάδωση, επομένως, τα κλαδιά που ξεκινάνε με κόμβο που είναι της μορφής $3x+1$ είναι κλαδιά που έχουν εκεί μία διακλάδωση και, όπως έχουμε παρατηρήσει, στο ίδιο κλαδί θα εμφανίζονται διακλαδώσεις κάθε 2 κόμβους. Αναλόγως, αν ένας αριθμός είναι της μορφής $3x+2$ τότε δεν αντιστοιχεί σε κόμβο διακλάδωσης, αλλά ο αμέσως επόμενος (διπλάσιος) κόμβος θα είναι της μορφής $6x+4=3(2x+1)+1,$ που είναι κόμβος διακλάδωσης. Επομένως, για κάθε κόμβο έχουμε ακριβώς τρεις περιπτώσεις:

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

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

Αν και το πρόβλημά μας σχετίζεται με φυσικούς αριθμούς, δεν έχουμε ακόμα ασχοληθεί με το βασικότερο εργαλείο που σχετίζεται με αυτούς: το Θεμελιώδες Θεώρημα της Άλγεβρας! Το εν λόγω θεώρημα μας λέει ότι κάθε φυσικός αριθμός μεγαλύτερος της μονάδας μπορεί να γραφτεί σαν γινόμενο δυνάμεων διακεκριμένων πρώτων αριθμών, το οποίο μάλιστα είναι μοναδικό αν αγνοήσουμε τη σειρά με την οποία εμφανίζονται οι αριθμοί στο γινόμενο. Έχοντας αυτό το βασικό εργαλείο στα χέρια μας, μπορούμε να ρωτήσουμε – τον εαυτό μας, αλλά και το σύμπαν, γενικότερα – πολλά ενδιαφέροντα πράγματα όπως, για παράδειγμα:

το γράφημα Collatz περιέχει όλους τους πρώτους;
αν το γράφημα Collatz περιέχει έναν πρώτο, περιέχει και όλες τις δυνάμεις του;
αν το γράφημα Collatz περιέχει δύο αριθμούς, περιέχει και το γινόμενό τους;

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

Περισσότερα γι’ αυτά, όμως, την επόμενη Παρασκευή!

Η κεντρική εικόνα είναι Ο Γιος (Boris) του Leonid Pasternak.

Διαβάστε επίσης: Τι λέει το Θεώρημα του Bolzano;

Ακολουθήστε το aftermathsgr στα social media:

One comment

Ο/Η Η εικασία Collatz (6) – aftermaths.gr λέει:

8 Οκτωβρίου 2021 στο 13:19

[…] τι συζητήσαμε την προηγούμενη εβδομάδα, δείτε εδώ, ενώ για όλες τις δημοσιεύσεις της σειράς, δείτε εδώ. […]

Μου αρέσει!Μου αρέσει!

Απάντηση