Μια κοντινή προβολή αποκαλύπτει το σημείο «τήξης» ενός άπειρου γραφήματος | Περιοδικό Quanta

Το 2008, ο μαθηματικός Oded Schramm πέθανε σε ένα ατύχημα πεζοπορίας στα βουνά Cascade περίπου 50 μίλια ανατολικά του Σιάτλ. Αν και ήταν μόλις 46 ετών, είχε κατασκευάσει εντελώς νέους τομείς των μαθηματικών.

«Ήταν ένας φανταστικός μαθηματικός», είπε Itai Benjamini, μαθηματικός στο Ινστιτούτο Επιστημών Weizmann και φίλος και συνεργάτης του Schramm. “Εξαιρετικά δημιουργικό, εξαιρετικά κομψό, εξαιρετικά πρωτότυπο.”

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

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

Σε προεκτύπωση δημοσιεύτηκε τον Οκτώβριο, Τομ Χάτσκροφτ του Ινστιτούτου Τεχνολογίας της Καλιφόρνια και ο διδακτορικός του φοιτητής Φίλιππος Εάσο απέδειξε την εικασία τοπικότητας του Schramm. Η απόδειξή τους βασίζεται σε σημαντικές ιδέες από όλη τη θεωρία πιθανοτήτων και άλλους τομείς των μαθηματικών, τις οποίες συνδύασαν με έξυπνο τρόπο.

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

Άπειρες συστάδες

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

Το 1957, οι μαθηματικοί Simon Ralph Broadbent και John Michael Hammersley ανέπτυξαν ένα μαθηματικό μοντέλο αυτής της φυσικής διαδικασίας. Τις δεκαετίες από τότε, αυτό το μοντέλο έχει γίνει αντικείμενο μελέτης από μόνο του. Οι μαθηματικοί μελετούν τη διήθηση επειδή επιτυγχάνει μια σημαντική ισορροπία: Η ρύθμιση είναι απλή, αλλά παρουσιάζει πολύπλοκα και αινιγματικά χαρακτηριστικά.

«Είναι ένα κανονικό μοντέλο για τους μαθηματικούς», είπε ο Hutchcroft. «Μπορείς να σκεφτείς τα πράγματα οπτικά. Αυτό το κάνει πολύ ωραίο να δουλεύεις μαζί του».

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

Λίγο πριν από το θάνατό του, ο Schramm υπέθεσε ότι το θεώρημα των Grimmett και Marstrand θα μπορούσε να γενικευτεί. Σκέφτηκε ότι το κατώφλι διήθησης καθορίζεται εξ ολοκλήρου από την κοντινή ή «μικροσκοπική» προοπτική για μια μεγάλη κατηγορία γραφημάτων που είναι γνωστά ως μεταβατικά γραφήματα.

Το 2009, ο Benjamini, Ασάφ Ναχμίας και Γιουβάλ Πέρες αποδείχθηκε Η εικασία τοποθεσίας του Schramm, όπως είναι τώρα γνωστή, για έναν συγκεκριμένο τύπο μεταβατικού γραφήματος που μοιάζει με δέντρο. Ο Schramm, ωστόσο, είχε υποθέσει ότι θα ίσχυε για όλα τα μεταβατικά γραφήματα (με εξαίρεση τα μονοδιάστατα γραφήματα).

Σε ένα μεταβατικό γράφημα, όλες οι κορυφές μοιάζουν. Ένα δισδιάστατο πλέγμα είναι ένα παράδειγμα. Εάν επιλέξετε δύο κορυφές, μπορείτε πάντα να βρείτε μια συμμετρία που μετακινεί τη μια κορυφή στην άλλη.

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

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

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

«Ο χώρος όλων των πιθανών γεωμετριών είναι τόσο απέραντος και πάντα κρύβονται παράξενα πράγματα», είπε ο Χάτσκροφτ.

Διεύρυνση του φακού

Ο Easo και ο Hutchcroft δεν έψαχναν αρχικά για μια λύση στην εικασία τοποθεσίας του Schramm, η οποία ισχύει για άπειρα γραφήματα. Αντίθετα, μελετούσαν τη διήθηση σε πεπερασμένα γραφήματα. Είχαν όμως μια ιδέα που ξαφνικά έστρεψε την προσοχή τους στην εικασία.

"Καταλήξαμε σε αυτό το νέο εργαλείο και σκεφτήκαμε, ω, αυτό φαίνεται σαν κάτι που θα μπορούσε να είναι χρήσιμο για να επιτεθούμε σε μια τοποθεσία", είπε ο Easo.

Για να αποδείξουν την εικασία, χρειάστηκε να δείξουν ότι η μικροσκοπική προοπτική δίνει ένα ακριβές στιγμιότυπο του ορίου διήθησης. Όταν βλέπετε μόνο μέρος ενός γραφήματος και παρατηρείτε ένα μεγάλο συνδεδεμένο σύμπλεγμα, μπορεί να υποθέσετε ότι το γράφημα έχει ένα άπειρο σύμπλεγμα και επομένως είναι πάνω από το όριο διήθησης. Ο Easo και ο Hutchcroft ξεκίνησαν να το αποδείξουν.

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

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

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

Για το τετράγωνο πλέγμα, ο αριθμός των κορυφών αυξάνεται σχετικά αργά. Είναι περίπου το πλάτος του φακού σας στο τετράγωνο. Μετά από 10 βήματα, θα βρείτε περίπου 100 κορυφές. Αλλά ένα κανονικό δέντρο με 3 τεμάχια μεγαλώνει εκθετικά πιο γρήγορα — περίπου 2 ανυψώνονται στην ισχύ του πλάτους του φακού σας. Μετά από 10 βήματα, θα δείτε περίπου 1,024 κορυφές. Η παρακάτω εικόνα δείχνει πώς το 3-κανονικό δέντρο είναι πολύ μεγαλύτερο μετά από μόνο επτά βήματα, παρόλο που το τετράγωνο πλέγμα έχει περισσότερες κορυφές στην αρχή. Γενικά, τα γραφήματα μπορεί να έχουν διαφορετικούς ρυθμούς ανάπτυξης σε διαφορετικές κλίμακες — μπορεί να ξεκινήσουν γρήγορα και μετά να επιβραδύνουν.

Πίσω στο 2018, Hutchcroft χρησιμοποίησε παρόμοια ιδέα για να αποδείξει την εικασία τοποθεσίας για ταχέως αναπτυσσόμενα γραφήματα όπως το 3-κανονικό δέντρο. Αλλά δεν λειτούργησε για γραφήματα αργής ανάπτυξης όπως το τετράγωνο πλέγμα ή για γραφήματα που αναπτύσσονται με ενδιάμεση ταχύτητα, χωρίς να πληρούν ούτε τα μαθηματικά κριτήρια για γρήγορη ανάπτυξη ούτε εκείνα για αργή ανάπτυξη.

"Εδώ είναι όπου τα πράγματα γίνονται πραγματικά απογοητευτικά για περίπου τρία χρόνια", είπε ο Hutchcroft.

Δομή έναντι επέκτασης

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

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

Το 2021, ο Sébastien Martineau του Πανεπιστημίου της Σορβόννης στο Παρίσι, συνεργαζόμενος με τον Daniel Contreras και Vincent Tassion του ETH Zurich, μπόρεσε να χρησιμοποιήσει αυτή την ιδιοκτησία για να να αποδείξει την εικασία τοπικότητας του Schramm για γραφήματα που τελικά μεγαλώνουν αργά.

Σε αυτό το σημείο, οι δύο ομάδες μαθηματικών είχαν αντιμετωπίσει με επιτυχία την εικασία από διαφορετικές κατευθύνσεις: γρήγορη ανάπτυξη και αργή ανάπτυξη. Αυτό όμως άφησε σημαντικά κενά. Πρώτον, υπάρχει μια κατηγορία ενδιάμεσης ανάπτυξης που δεν καλύφθηκε από την τεχνική των Easo και Hutchcroft ή από την απόδειξη των Contreras, Martineau και Tassion. Ένα άλλο πρόβλημα ήταν ότι τα επιχειρήματα εξακολουθούσαν να μην εφαρμόζονται σε γραφήματα με μεταβαλλόμενους ρυθμούς ανάπτυξης — μόνο σε αυτά που παρέμειναν γρήγορα ή αργά. Για να εφαρμοστεί το επιχείρημα Contreras, Martineau και Tassion σε αυθαίρετα γραφήματα, δεν ήταν αρκετό ότι η γεωμετρία φαίνεται τελικά ήμερη όταν κάνετε σμίκρυνση, ο Easo εξήγησε: «Χρειαζόμαστε να φαίνεται ήμερο τώρα, κοντά στην τρέχουσα κλίμακα».

Η μέση του πουθενά

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

Οι Easo και Hutchcroft πέρασαν μεγάλο μέρος του περασμένου έτους εργάζονται για να επεκτείνουν τα αποτελέσματά τους ώστε να εφαρμόζονται σε γραφήματα που δεν καλύπτονταν από καμία από τις προηγούμενες μεθόδους.

Αρχικά, τροποποίησαν την τεχνική του 2018 που είχε εφαρμόσει ο Hutchcroft σε ταχέως αναπτυσσόμενα γραφήματα για να δουλέψουν σε γραφήματα που αλλάζουν τα επίπεδα ανάπτυξης σε διαφορετικές κλίμακες. Στη συνέχεια αντιμετώπισαν την υπόθεση της βραδείας ανάπτυξης, μέσα ένα χαρτί 27 σελίδων μοιράστηκαν τον Αύγουστο ότι επεκτάθηκε στη δουλειά για τους Contreras, Martineau και Tassion. Τέλος, στην προεκτύπωσή τους τον Οκτώβριο, επινόησαν ένα άλλο επιχείρημα χρησιμοποιώντας τη θεωρία των τυχαίων περιπάτων — γραμμές που κινούνται τυχαία στο διάστημα — για να χειριστούν την περίπτωση της ενδιάμεσης ανάπτυξης. Με την τριχοτομή ολοκληρωμένη, είχαν αποδείξει την εικασία εντοπιότητας του Schramm.

«Έπρεπε να ρίξουμε όλα όσα γνωρίζαμε στο πρόβλημα», είπε ο Χάτσκροφτ.

Η λύση δίνει στους μαθηματικούς μια καλύτερη εικόνα για το τι συμβαίνει πάνω από το κατώφλι διήθησης, όπου η πιθανότητα ενός άπειρου συμπλέγματος είναι 100%, και κάτω από αυτό, όπου η πιθανότητα είναι 0%. Αλλά οι μαθηματικοί εξακολουθούν να παραξενεύονται από το τι συμβαίνει ακριβώς στο κατώφλι για τα περισσότερα γραφήματα, συμπεριλαμβανομένου του τρισδιάστατου πλέγματος. «Αυτή είναι ίσως η πιο διάσημη, πιο βασική ανοιχτή ερώτηση στη θεωρία διήθησης», είπε Ράσελ Λάιονς του Πανεπιστημίου της Ιντιάνα.

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

Το 1996, ο Benjamini και ο Schramm εικάζεται ότι η πιθανότητα εύρεσης ενός άπειρου συμπλέγματος ακριβώς στο κατώφλι είναι μηδενική για όλα τα μεταβατικά γραφήματα — όπως ακριβώς συμβαίνει για το πλέγμα 2D ή για το πλέγμα 3D κομμένο στη μέση. Τώρα που η εικασία τοποθεσίας έχει διευθετηθεί, η κατανόηση του τι συμβαίνει ακριβώς στο σημείο της μετάβασης μπορεί να είναι λίγο πιο κοντά.

διόρθωση: Δεκέμβριος 18, 2023
Ο αριθμός των κόμβων μέσα σε n συνδέσμους ενός αρχικού κόμβου σε ένα 3-κανονικό γράφημα αυξάνεται περίπου ως 2ⁿ, όχι 3ⁿ όπως έλεγε αρχικά αυτό το άρθρο. Το άρθρο έχει διορθωθεί.

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