Μαθηματικά κόλπα για να δαμάσουν τη μέση απόσταση | Περιοδικό Quanta

Μέχρι τώρα φέτος, Quanta έχει καταγράψει τρεις σημαντικές προόδους στη θεωρία Ramsey, τη μελέτη του τρόπου αποφυγής δημιουργίας μαθηματικών προτύπων. ο πρώτο αποτέλεσμα βάλτε ένα νέο ανώτατο όριο στο πόσο μεγάλο μπορεί να είναι ένα σύνολο ακεραίων χωρίς να περιέχει τρεις ίσους αριθμούς, όπως {2, 4, 6} ή {21, 31, 41}. ο δεύτερος και τρίτος Ομοίως, βάλτε νέα όρια στο μέγεθος των δικτύων χωρίς συστάδες σημείων που είτε είναι όλα συνδεδεμένα είτε όλα απομονωμένα μεταξύ τους.

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

Για παράδειγμα, εξετάστε δύο ερωτήσεις σχετικά με ένα κλάσμα με πολύ μεγάλο παρονομαστή. Μπορείτε να ρωτήσετε ποια είναι η δεκαδική επέκταση, ας πούμε, 1/42503312127361. Ή θα μπορούσατε να ρωτήσετε εάν αυτός ο αριθμός θα πλησιάζει στο μηδέν καθώς αυξάνεται ο παρονομαστής. Η πρώτη ερώτηση είναι μια συγκεκριμένη ερώτηση σχετικά με μια ποσότητα του πραγματικού κόσμου και είναι πιο δύσκολο να υπολογιστεί από τη δεύτερη, η οποία ρωτά πώς η ποσότητα 1/n θα αλλάξει «ασυμπτωτικά» ως n μεγαλώνει. (Κοντεύει όλο και πιο κοντά στο 0.)

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

Ο Gasarch έχει μελετήσει ερωτήσεις στη θεωρία Ramsey που περιλαμβάνουν πεπερασμένους αριθμούς που είναι πολύ μεγάλοι για να επιλυθεί το πρόβλημα με ωμή βία. Σε ένα έργο, ανέλαβε την πεπερασμένη έκδοση της πρώτης από τις φετινές ανακαλύψεις - μια εργασία του Φεβρουαρίου από Zander Kelley, μεταπτυχιακός φοιτητής στο Πανεπιστήμιο του Ιλινόις, Urbana-Champaign, και Raghu Meka του Πανεπιστημίου της Καλιφόρνια στο Λος Άντζελες. Ο Kelley και ο Meka βρήκαν ένα νέο άνω όριο για το πόσοι ακέραιοι αριθμοί ήταν μεταξύ 1 και N μπορείτε να βάλετε σε ένα σύνολο αποφεύγοντας προόδους τριών όρων ή μοτίβα ομοιόμορφων αριθμών.

Αν και το αποτέλεσμα των Kelley και Meka ισχύει ακόμα κι αν N είναι σχετικά μικρό, δεν δίνει ένα ιδιαίτερα χρήσιμο όριο σε αυτήν την περίπτωση. Για πολύ μικρές τιμές του N, καλύτερα να επιμείνετε σε πολύ απλές μεθόδους. Αν N είναι, ας πούμε, 5, απλά κοιτάξτε όλα τα πιθανά σύνολα αριθμών μεταξύ 1 και N, και επιλέξτε τη μεγαλύτερη χωρίς εξέλιξη: {1, 2, 4, 5}.

Αλλά ο αριθμός των διαφορετικών πιθανών απαντήσεων αυξάνεται πολύ γρήγορα και καθιστά πολύ δύσκολη την εφαρμογή μιας τόσο απλής στρατηγικής. Υπάρχουν περισσότερα από 1 εκατομμύριο σετ που αποτελούνται από αριθμούς μεταξύ 1 και 20. Υπάρχουν πάνω από 10⁶⁰ χρησιμοποιώντας αριθμούς μεταξύ 1 και 200. Η εύρεση του καλύτερου συνόλου χωρίς πρόοδο για αυτές τις περιπτώσεις απαιτεί μια μεγάλη δόση υπολογιστικής ισχύος, ακόμη και με στρατηγικές βελτίωσης της απόδοσης. «Πρέπει να μπορείς να αποσπάσεις πολλές επιδόσεις από τα πράγματα», είπε Τζέιμς Γκλεν, επιστήμονας υπολογιστών στο Πανεπιστήμιο Yale. Το 2008, οι Gasarch, Glenn και Κλάιντ Κρουσκάλ του Πανεπιστημίου του Μέριλαντ έγραψε ένα πρόγραμμα για να βρείτε τα μεγαλύτερα σετ χωρίς εξέλιξη έως ένα N από 187. (Η προηγούμενη εργασία είχε λάβει τις απαντήσεις έως και 150, καθώς και για 157.) Παρά τον κατάλογο των τεχνασμάτων, το πρόγραμμά τους χρειάστηκε μήνες για να ολοκληρωθεί, είπε ο Glenn.

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

Οι Gasarch, Glenn και Kruskal δοκίμασαν επίσης αρκετές άλλες στρατηγικές. Μια πολλά υποσχόμενη ιδέα στηριζόταν στην τυχαιότητα. Ένας απλός τρόπος για να δημιουργήσετε ένα σύνολο χωρίς πρόοδο είναι να βάλετε 1 στο σετ σας και, στη συνέχεια, να προσθέσετε πάντα τον επόμενο αριθμό που δεν δημιουργεί αριθμητική πρόοδο. Ακολουθήστε αυτή τη διαδικασία μέχρι να πατήσετε τον αριθμό 10 και θα λάβετε το σύνολο {1, 2, 4, 5, 10}. Αλλά αποδεικνύεται ότι αυτή δεν είναι η καλύτερη στρατηγική γενικά. «Κι αν δεν ξεκινήσουμε από το 1;» είπε ο Γκασάρχης. «Αν ξεκινάς από ένα τυχαίο μέρος, στην πραγματικότητα τα καταφέρνεις καλύτερα». Οι ερευνητές δεν έχουν ιδέα γιατί η τυχαιότητα είναι τόσο χρήσιμη, πρόσθεσε.

Ο υπολογισμός των πεπερασμένων εκδόσεων των δύο άλλων νέων αποτελεσμάτων της θεωρίας Ramsey είναι ακόμη πιο ενοχλητικός από τον προσδιορισμό του μεγέθους των συνόλων χωρίς πρόοδο. Αυτά τα αποτελέσματα αφορούν μαθηματικά δίκτυα (που ονομάζονται γραφήματα) που αποτελούνται από κόμβους που συνδέονται με γραμμές που ονομάζονται ακμές. Ο αριθμός Ramsey r(s, t) είναι ο μικρότερος αριθμός κόμβων που πρέπει να έχει ένα γράφημα για να καταστεί αδύνατο να αποφευχθεί η συμπερίληψη μιας ομάδας s συνδεδεμένους κόμβους ή t αποσυνδεδεμένοι. Ο αριθμός Ramsey είναι τόσο πονοκέφαλος για να υπολογίσουμε ότι είναι ακόμη r(5, 5) είναι άγνωστο — είναι κάπου μεταξύ 43 και 48.

Σε 1981, Μπρένταν ΜακΚέι, τώρα επιστήμονας υπολογιστών στο Εθνικό Πανεπιστήμιο της Αυστραλίας, έγραψε ένα πρόγραμμα λογισμικού που ονομάζεται nauty, το οποίο είχε σκοπό να κάνει τον υπολογισμό των αριθμών Ramsey απλούστερο. Το Nauty διασφαλίζει ότι οι ερευνητές δεν χάνουν χρόνο ελέγχοντας δύο γραφήματα που είναι απλώς αναποδογυρισμένα ή περιστρεφόμενα το ένα του άλλου. «Αν κάποιος είναι στην περιοχή και δεν χρησιμοποιεί ναυτιλία, το παιχνίδι έχει τελειώσει. Πρέπει να το χρησιμοποιήσετε», είπε Stanisław Radziszowski, μαθηματικός στο Ινστιτούτο Τεχνολογίας του Ρότσεστερ. Ωστόσο, ο όγκος του υπολογισμού που εμπλέκεται είναι σχεδόν ακατανόητος. Το 2013, ο Radziszowski και Jan Goedgebeur το απέδειξε αυτό rΤο (3, 10) είναι το πολύ 42. «Χρειάστηκαν, νομίζω, σχεδόν 50 χρόνια CPU», είπε ο Goedgebeur, επιστήμονας υπολογιστών στο Πανεπιστήμιο KU Leuven στο Βέλγιο.

Εάν δεν μπορείτε να υπολογίσετε έναν ακριβή αριθμό Ramsey, μπορείτε να δοκιμάσετε να περιορίσετε την τιμή του με παραδείγματα. Εάν βρείτε ένα γράφημα 45 κόμβων χωρίς πέντε κόμβους που ήταν όλοι συνδεδεμένοι και χωρίς πέντε κόμβους που ήταν όλοι αποσυνδεδεμένοι, αυτό θα αποδείκνυε ότι rΤο (5, 5) είναι μεγαλύτερο από 45. Οι μαθηματικοί που μελετούσαν τους αριθμούς Ramsey συνήθιζαν να πιστεύουν ότι η εύρεση αυτών των παραδειγμάτων, που ονομάζονται γραφήματα Ramsey, θα ήταν απλή, είπε ο Radziszowski. Αλλά δεν ήταν έτσι. «Υπήρχε αυτή η προσδοκία ότι οι ωραίες, δροσερές μαθηματικές κατασκευές θα δώσουν τις καλύτερες δυνατές κατασκευές και χρειαζόμαστε απλώς περισσότερους ανθρώπους να δουλέψουν πάνω σε αυτό», είπε. «Η αίσθηση μου είναι όλο και περισσότερο ότι είναι χαοτικό».

Η τυχαιότητα είναι ταυτόχρονα εμπόδιο στην κατανόηση και χρήσιμο εργαλείο. Geoffrey Exoo, επιστήμονας υπολογιστών στο Πολιτειακό Πανεπιστήμιο της Ιντιάνα, έχει περάσει χρόνια βελτιώνοντας τυχαίες μεθόδους για τη δημιουργία γραφημάτων Ramsey. Σε ένα χαρτί 2015 Ανακοινώνοντας δεκάδες νέα γραφήματα Ramsey που ξεπέρασαν το ρεκόρ, οι Exoo και Milos Tatarevic δημιούργησαν τυχαία γραφήματα και στη συνέχεια τα άλλαξαν σταδιακά διαγράφοντας ή προσθέτοντας άκρες που μείωσαν τον αριθμό των ανεπιθύμητων συστάδων μέχρι να βρουν ένα γράφημα Ramsey. Ωστόσο, οι τεχνικές του Exoo είναι τόσο τέχνη όσο τίποτα άλλο, είπε ο Radziszowski. Μερικές φορές απαιτούν από αυτόν να συνδυάσει πολλαπλές μεθόδους ή να χρησιμοποιήσει την κρίση του για το είδος των γραφημάτων να ξεκινήσει. «Πολλοί, πολλοί άνθρωποι το δοκιμάζουν και δεν μπορούν να το κάνουν», είπε ο Radziszowski.

Οι τεχνικές που αναπτύχθηκαν για τη δημιουργία γραφημάτων Ramsey θα μπορούσαν να είναι πιο χρήσιμες κάποια μέρα, είπε ο Goedgebeur, ο οποίος έχει εργάστηκαν για παραγωγή άλλων ειδών γραφημάτων, όπως γραφήματα που αντιπροσωπεύουν χημικές ενώσεις. «Δεν είναι απίθανο αυτές οι τεχνικές να μπορούν επίσης να μεταφερθούν και να προσαρμοστούν για να βοηθήσουν στη δημιουργία άλλων κατηγοριών γραφημάτων πιο αποτελεσματικά (και αντίστροφα)», έγραψε σε ένα email.

Για τον Radziszowski, ωστόσο, ο λόγος για τη μελέτη των μικρών αριθμών Ramsey είναι πολύ πιο απλός. «Επειδή είναι ανοιχτό, γιατί κανείς δεν ξέρει ποια είναι η απάντηση», είπε. «Οι ασήμαντες υποθέσεις που κάνουμε με το χέρι. λίγο μεγαλύτερο, χρειάζεστε έναν υπολογιστή και λίγο μεγαλύτερο, ακόμη και ο υπολογιστής δεν είναι αρκετά καλός. Και έτσι προκύπτει η πρόκληση».