Ένα μοντέλο της OpenAI κατέρριψε μια κεντρική εικασία στη διακριτή γεωμετρία

Για σχεδόν 80 χρόνια, οι μαθηματικοί μελετούν ένα παραπλανητικά απλό ερώτημα: αν τοποθετήσετε $n$ σημεία στο επίπεδο, πόσα ζεύγη σημείων μπορούν να απέχουν ακριβώς $1$ μεταξύ τους;

Πρόκειται για το πρόβλημα των μοναδιαίων αποστάσεων στο επίπεδο, το οποίο διατυπώθηκε για πρώτη φορά από τον Πολ Έρντος το 1946. Είναι ένα από τα πιο γνωστά ερωτήματα στη συνδυαστική γεωμετρία, εύκολο να διατυπωθεί και εξαιρετικά δύσκολο να επιλυθεί. Το βιβλίο του 2005 Research Problems in Discrete Geometry, των Μπρας, Μόουζερ και Πακ, το αποκαλεί «ίσως το πιο γνωστό (και το απλούστερο να εξηγηθεί) πρόβλημα στη συνδυαστική γεωμετρία». Ο Νόγκα Άλον, κορυφαίος συνδυαστικός στο Πρίνστον, το περιγράφει ως «ένα από τα αγαπημένα προβλήματα του Έρντος». Ο Έρντος προσέφερε μάλιστα χρηματικό έπαθλο για την επίλυση αυτού του προβλήματος.

Σήμερα, μοιραζόμαστε μια σημαντική ανακάλυψη για το πρόβλημα της μοναδιαίας απόστασης. Από το αρχικό έργο του Erdős, η επικρατούσα πεποίθηση ήταν ότι οι κατασκευές «τετραγωνικού πλέγματος» που απεικονίζονται παρακάτω ήταν ουσιαστικά βέλτιστες για τη μεγιστοποίηση του αριθμού των ζευγών σε μοναδιαία απόσταση. Ένα εσωτερικό μοντέλο της OpenAI κατέρριψε αυτή τη μακρόχρονη εικασία, παρέχοντας μια άπειρη οικογένεια παραδειγμάτων που αποδίδουν πολυωνυμική βελτίωση. Η απόδειξη έχει ελεγχθεί από μια ομάδα εξωτερικών μαθηματικών. Έχουν επίσης γράψει μια συνοδευτική εργασία που εξηγεί το επιχείρημα και παρέχει περαιτέρω υπόβαθρο και πλαίσιο για τη σημασία του αποτελέσματος.

Το αποτέλεσμα είναι επίσης αξιοσημείωτο για τον τρόπο με τον οποίο βρέθηκε. Η απόδειξη προήλθε από ένα νέο γενικής χρήσης μοντέλο συλλογιστικής, και όχι από ένα σύστημα εκπαιδευμένο ειδικά για τα μαθηματικά, ενισχυμένο ώστε να αναζητά στρατηγικές απόδειξης ή στοχευμένο ειδικά στο πρόβλημα της μοναδιαίας απόστασης. Στο πλαίσιο μιας ευρύτερης προσπάθειας να δοκιμαστεί αν προηγμένα μοντέλα μπορούν να συμβάλουν σε έρευνα αιχμής, το αξιολογήσαμε σε μια συλλογή προβλημάτων του Erdős. Σε αυτή την περίπτωση, παρήγαγε μια απόδειξη που επιλύει το ανοικτό πρόβλημα.

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

Ο βραβευμένος με Μετάλλιο Fields Tim Gowers, γράφοντας στη συνοδευτική εργασία, αποκαλεί το αποτέλεσμα «ορόσημο στα μαθηματικά της TN». Σύμφωνα με τον κορυφαίο θεωρητικό αριθμών Arul Shankar, «Κατά τη γνώμη μου αυτή η εργασία δείχνει ότι τα σημερινά μοντέλα TN ξεπερνούν τον ρόλο του απλού βοηθού για τους ανθρώπους μαθηματικούς – είναι ικανά να έχουν πρωτότυπες ευφυείς ιδέες και έπειτα να τις φέρνουν εις πέρας».

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

Έστω $u(n)$ ο μέγιστος δυνατός αριθμός ζευγών σε μοναδιαία απόσταση μεταξύ $n$ σημείων στο επίπεδο. Παραδείγματα που επιτυγχάνουν γραμμικό ρυθμό αύξησης είναι εύκολο να κατασκευαστούν: η τοποθέτηση $n$ σημείων σε μια γραμμή δίνει $n-1$ ζεύγη, ενώ ένα τετράγωνο πλέγμα δίνει περίπου $2n$ ζεύγη. Η προηγουμένως καλύτερη γνωστή κατασκευή, που προέρχεται από ένα ανακλιμακωμένο τετράγωνο πλέγμα, αποδεικνύεται ότι δίνει ακόμη περισσότερα: $n^{1 + C / \log \log(n)}$ για μια σταθερά $C$. Εφόσον το $\log \log(n)$ τείνει στο άπειρο μαζί με το $n$, ο πρόσθετος όρος στον εκθέτη τείνει στο $0$, πράγμα που σημαίνει ότι αυτές οι κατασκευές επιτυγχάνουν αύξηση μόνο ελαφρώς ταχύτερη από τη γραμμική. Για δεκαετίες, ήταν ευρέως αποδεκτό ότι αυτός ο ρυθμός ήταν ουσιαστικά ο καλύτερος δυνατός και ότι καμία κατασκευή δεν μπορούσε να βελτιωθεί σημαντικά σε σχέση με το τετράγωνο πλέγμα. Με τεχνικούς όρους, ο Έρντος υπέθεσε ένα άνω φράγμα της μορφής $n^{1+o(1)}$, όπου το πρόσθετο $o(1)$ δηλώνει έναν όρο που τείνει στο $0$ μαζί με το $n$.

Το νέο μας αποτέλεσμα καταρρίπτει αυτήν την εικασία. Πιο συγκεκριμένα, για άπειρες τιμές του $n$, η απόδειξη κατασκευάζει διατάξεις $n$ σημείων με τουλάχιστον $n^{1+\delta}$ ζεύγη σε μοναδιαία απόσταση, για κάποιον σταθερό εκθέτη $\delta > 0$. (Η αρχική απόδειξη της ΤΝ δεν δίνει ρητό $\delta$, αλλά μια επερχόμενη βελτίωση του καθηγητή μαθηματικών του Πρίνστον Γουίλ Σόουιν έδειξε ότι μπορεί να ληφθεί $\delta=0,014$.)

Η ιστορία του προβλήματος βοηθά να κατανοήσουμε γιατί το αποτέλεσμα είναι απροσδόκητο. Το καλύτερο γνωστό κάτω φράγμα είχε παραμείνει ουσιαστικά αμετάβλητο από την αρχική κατασκευή του Έρντος το 1946. Το καλύτερο άνω φράγμα, $O(n^{4/3})$, ανάγεται σε εργασία των Σπένσερ, Σεμερέντι και Τρότερ το 1984 και, παρά μεταγενέστερες βελτιώσεις και σχετική δομική εργασία των Σέκελι,Κατζ και Σίλιερ, Πακ, Ραζ και Σολιμόσι και άλλων, το άνω φράγμα έχει παραμείνει ουσιαστικά αμετάβλητο. Ως ένδειξη υπέρ της εικασίας, οι Ματουτσέκ, Άλον, Μπούτσιτς και Σάουερμαν μελέτησαν το πρόβλημα με μη ευκλείδειες αποστάσεις στο επίπεδο και απέδειξαν ότι «οι περισσότερες» από αυτές τις μη ευκλείδειες αποστάσεις υπακούουν κατά κάποιον τρόπο στην εικασία.

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

Σε υψηλό επίπεδο, η απόδειξη ξεκινά από μια οικεία γεωμετρική ιδέα και την ωθεί σε μια απρόσμενη κατεύθυνση.

Το αρχικό κάτω φράγμα του Erdős μπορεί να γίνει κατανοητό μέσω των γκαουσιανών ακεραίων: αριθμών της μορφής $a+bi$, όπου $a$ και $b$ είναι ακέραιοι και το $i$ είναι η τετραγωνική ρίζα του $-1$. Οι γκαουσιανοί ακέραιοι επεκτείνουν τους συνηθισμένους ακεραίους και, όπως κι αυτοί, έχουν ιδιότητες όπως η μοναδική παραγοντοποίηση σε πρώτους. Τέτοιες επεκτάσεις των συνηθισμένων ακεραίων ή ρητών είναι γνωστές ως αλγεβρικά σώματα αριθμών. Το νέο επιχείρημα αντικαθιστά τους γκαουσιανούς ακεραίους με πιο περίπλοκες γενικεύσεις από την αλγεβρική θεωρία αριθμών, με πλουσιότερες συμμετρίες που μπορούν να δημιουργήσουν πολύ περισσότερες διαφορές μοναδιαίου μήκους.

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

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

Όπως γράφει ο Thomas Bloom στη συνοδευτική σημείωση:

«Όταν αξιολογώ τη σημασία και την επιρροή μιας απόδειξης που έχει παραχθεί από TN, ένα ερώτημα που θέτω στον εαυτό μου είναι: μας δίδαξε αυτό κάτι νέο για το πρόβλημα; Κατανοούμε τώρα καλύτερα τη διακριτή γεωμετρία; Νομίζω ότι η απάντηση είναι ένα μετριασμένο ναι: αυτό δείχνει ότι οι κατασκευές της θεωρίας αριθμών έχουν να πουν πολύ περισσότερα για τέτοιου είδους ερωτήματα απ’ ό,τι υποψιαζόμασταν· επιπλέον, ότι η απαιτούμενη θεωρία αριθμών μπορεί να είναι πολύ βαθιά. Χωρίς αμφιβολία, πολλοί αλγεβρικοί θεωρητικοί αριθμών θα εξετάσουν προσεκτικά άλλα ανοικτά προβλήματα στη διακριτή γεωμετρία τους επόμενους μήνες.»

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

Ο Bloom υποδεικνύει επίσης μια ευρύτερη δυνατότητα:

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

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

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

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

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

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