Εισαγωγή
Στα μέσα Οκτωβρίου, Τζάστιν Γκίλμερ πέταξε από την Καλιφόρνια στη Νέα Υόρκη για να παρευρεθεί στον γάμο ενός φίλου. Ενώ βρισκόταν στην Ανατολική Ακτή επισκέφτηκε τον πρώην σύμβουλό του, Μάικλ Σακς, μαθηματικός στο Πανεπιστήμιο Rutgers, όπου ο Gilmer είχε πάρει το διδακτορικό του επτά χρόνια νωρίτερα.
Ο Σακς και ο Γκίλμερ έπιασαν τη συζήτηση στο μεσημεριανό γεύμα, αλλά δεν μίλησαν για μαθηματικά. Στην πραγματικότητα, ο Gilmer δεν είχε σκεφτεί σοβαρά τα μαθηματικά από τότε που τελείωσε στο Rutgers το 2015. Τότε ήταν που αποφάσισε ότι δεν ήθελε μια καριέρα στον ακαδημαϊκό χώρο και αντ' αυτού άρχισε να μαθαίνει τον εαυτό του να προγραμματίζει. Καθώς αυτός και ο Σακς έτρωγαν, ο Γκίλμερ είπε στον παλιό του μέντορα για τη δουλειά του στη Google, όπου εργάζεται στη μηχανική μάθηση και την τεχνητή νοημοσύνη.
Ήταν ηλιόλουστη τη μέρα που ο Γκίλμερ επισκέφτηκε το Ράτγκερς. Καθώς περπατούσε, θυμήθηκε πώς το 2013 είχε περάσει το μεγαλύτερο μέρος ενός έτους περπατώντας στα ίδια μονοπάτια της πανεπιστημιούπολης, σκεπτόμενος ένα πρόβλημα που ονομάζεται εικασία κλειστής ένωσης. Ήταν μια καθήλωση, αν και άκαρπη: Παρ' όλη την προσπάθειά του, ο Γκίλμερ είχε καταφέρει μόνο να διδάξει τον εαυτό του γιατί το απλό φαινομενικό πρόβλημα σχετικά με τα σύνολα αριθμών ήταν τόσο δύσκολο να λυθεί.
«Νομίζω ότι πολλοί άνθρωποι σκέφτονται το πρόβλημα μέχρι να νιώσουν ικανοποιημένοι ότι καταλαβαίνουν γιατί είναι δύσκολο. Πιθανότατα ξόδεψα περισσότερο χρόνο σε αυτό από τους περισσότερους ανθρώπους», είπε ο Gilmer.
Μετά την επίσκεψή του τον Οκτώβριο, συνέβη κάτι απροσδόκητο: Πήρε μια νέα ιδέα. Ο Γκίλμερ άρχισε να σκέφτεται τρόπους για να εφαρμόσει τεχνικές από τη θεωρία της πληροφορίας για να λύσει την εικασία που είχε κλείσει η ένωση. Ακολούθησε την ιδέα για ένα μήνα, περιμένοντας σε κάθε στροφή να αποτύχει. Αντίθετα, ο δρόμος προς μια απόδειξη συνέχιζε να ανοίγει. Τέλος, στις 16 Νοεμβρίου ο ίδιος δημοσίευσε ένα πρώτο στο είδος του αποτέλεσμα Αυτό δίνει στους μαθηματικούς μεγάλο δρόμο για να αποδείξουν την πλήρη εικασία.
Η εφημερίδα πυροδότησε μια αναταραχή συνεχόμενων εργασιών. Οι μαθηματικοί του Πανεπιστημίου της Οξφόρδης, του Ινστιτούτου Τεχνολογίας της Μασαχουσέτης και του Ινστιτούτου Προηγμένων Μελετών, μεταξύ άλλων ιδρυμάτων, χτίστηκαν γρήγορα στις νέες μεθόδους του Γκίλμερ. Αλλά πριν το κάνουν, έκαναν μια δική τους ερώτηση: Ποιος είναι αυτός ο τύπος;
Μισογεμάτο
Η εικασία κλειστής ένωσης αφορά συλλογές αριθμών που ονομάζονται σύνολα, όπως {1, 2} και {2, 3, 4}. Μπορείτε να εκτελέσετε λειτουργίες σε σύνολα, συμπεριλαμβανομένης της συνένωσής τους, που σημαίνει να τα συνδυάσετε. Για παράδειγμα, η ένωση των {1, 2} και {2, 3, 4} είναι {1, 2, 3, 4}.
Μια συλλογή ή οικογένεια συνόλων θεωρείται «κλειστή ως προς την ένωση» εάν η ένωση οποιωνδήποτε δύο συνόλων στην οικογένεια ισούται με οποιοδήποτε υπάρχον σύνολο στην οικογένεια. Για παράδειγμα, εξετάστε αυτήν την οικογένεια τεσσάρων σετ:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Συνδυάστε οποιοδήποτε ζευγάρι και θα έχετε ένα σετ που είναι ήδη στην οικογένεια, κάνοντας την οικογενειακή ένωση-κλειστή.
Οι μαθηματικοί μιλούσαν για εκδοχές της εικασίας που είχε κλείσει η ένωση ήδη από τη δεκαετία του 1960, αλλά έλαβε την πρώτη επίσημη δήλωση το 1979, σε μια εργασία του Πέτερ Φράνκλ, ένας Ούγγρος μαθηματικός που μετανάστευσε στην Ιαπωνία τη δεκαετία του 1980 και ο οποίος συγκαταλέγει τις παραστάσεις στο δρόμο στις επιδιώξεις του.
Ο Frankl υπέθεσε ότι εάν μια οικογένεια συνόλων είναι κλειστή, πρέπει να έχει τουλάχιστον ένα στοιχείο (ή αριθμό) που εμφανίζεται τουλάχιστον στα μισά σύνολα. Ήταν ένα φυσικό κατώφλι για δύο λόγους.
Πρώτον, υπάρχουν άμεσα διαθέσιμα παραδείγματα οικογενειών κλειστών συνδικάτων στις οποίες όλα τα στοιχεία εμφανίζονται ακριβώς στο 50% των συνόλων. Όπως όλα τα διαφορετικά σετ που μπορείτε να φτιάξετε από τους αριθμούς 1 έως 10, για παράδειγμα. Υπάρχουν 1,024 τέτοια σύνολα, τα οποία σχηματίζουν μια κλειστή οικογένεια, και κάθε ένα από τα 10 στοιχεία εμφανίζεται σε 512 από αυτά. Και δεύτερον, τη στιγμή που ο Frankl έκανε την εικασία, κανείς δεν είχε ποτέ παρουσιάσει ένα παράδειγμα κλειστής οικογένειας στην οποία η εικασία δεν ίσχυε.
Άρα το 50% φαινόταν σωστή πρόβλεψη.
Αυτό δεν σήμαινε ότι ήταν εύκολο να αποδειχτεί. Στα χρόνια μετά την εργασία του Frankl, υπήρξαν λίγα αποτελέσματα. Πριν από την εργασία του Gilmer, αυτά τα έγγραφα κατάφεραν να καθορίσουν μόνο κατώφλια που διέφεραν ανάλογα με τον αριθμό των συνόλων στην οικογένεια (σε αντίθεση με το ίδιο όριο 50% για οικογένειες συνόλων όλων των μεγεθών).
"Αισθάνεται ότι θα έπρεπε να είναι εύκολο και είναι παρόμοιο με πολλά προβλήματα που είναι εύκολα, αλλά έχει αντισταθεί σε επιθέσεις", είπε Ο Γουίλ Σόουιν του Πανεπιστημίου Κολούμπια.
Η έλλειψη προόδου αντανακλούσε τόσο τη δύσκολη φύση του προβλήματος όσο και το γεγονός ότι πολλοί μαθηματικοί προτίμησαν να μην το σκεφτούν. Ανησυχούσαν ότι θα χάσουν χρόνια από την καριέρα τους κυνηγώντας ένα σαγηνευτικό πρόβλημα που ήταν αδύνατο να λυθεί. Ο Gilmer θυμάται μια μέρα το 2013 όταν πήγε στο γραφείο του Saks και ανέφερε την εικασία που έκλεισε το συνδικάτο. Ο σύμβουλός του - που στο παρελθόν είχε παλέψει ο ίδιος με το πρόβλημα - παραλίγο να τον πετάξει έξω από το δωμάτιο.
«Ο Μάικ είπε, «Τζάστιν, θα με κάνεις να σκεφτώ ξανά αυτό το πρόβλημα και δεν θέλω να το κάνω», είπε ο Γκίλμερ.
Μια επίγνωση της αβεβαιότητας
Μετά την επίσκεψή του στο Ράτγκερς, ο Γκίλμερ έφερε το πρόβλημα στο μυαλό του, προσπαθώντας να καταλάβει γιατί ήταν τόσο δύσκολο. Προέτρεψε τον εαυτό του με ένα βασικό γεγονός: Εάν έχετε μια οικογένεια 100 σετ, υπάρχουν 4,950 διαφορετικοί τρόποι να επιλέξετε δύο και να πάρετε την ένωσή τους. Στη συνέχεια αναρωτήθηκε: Πώς είναι δυνατόν 4,950 διαφορετικές ενώσεις να αντιστοιχίζονται σε μόλις 100 σύνολα εάν κανένα στοιχείο δεν εμφανίζεται σε αυτές τις ενώσεις με τουλάχιστον κάποια συχνότητα;
Ακόμη και σε εκείνο το σημείο ήταν καθ' οδόν για μια απόδειξη, αν και δεν το ήξερε ακόμα. Τεχνικές από τη θεωρία της πληροφορίας, που παρέχει έναν αυστηρό τρόπο σκέψης για το τι να περιμένετε όταν τραβάτε ένα ζευγάρι αντικειμένων τυχαία, θα τον οδηγούσαν εκεί.
Η θεωρία της πληροφορίας αναπτύχθηκε στο πρώτο μισό του 20ου αιώνα, με πιο διάσημο το έγγραφο του Claude Shannon το 1948, "Μια Μαθηματική Θεωρία της Επικοινωνίας.» Το έγγραφο παρείχε έναν ακριβή τρόπο υπολογισμού του όγκου των πληροφοριών που απαιτούνται για την αποστολή ενός μηνύματος, με βάση την ποσότητα της αβεβαιότητας σχετικά με το τι ακριβώς θα έλεγε το μήνυμα. Αυτός ο σύνδεσμος - μεταξύ πληροφοριών και αβεβαιότητας — ήταν η αξιοσημείωτη, θεμελιώδης διορατικότητα της Shannon.
Για να πάρω ένα παράδειγμα παιχνιδιού, φανταστείτε ότι γυρίζω ένα νόμισμα πέντε φορές και σας στέλνω τη σειρά που προκύπτει. Εάν είναι ένα κανονικό νόμισμα, χρειάζονται πέντε bit πληροφοριών για να μεταδοθούν. Αλλά αν είναι ένα φορτωμένο νόμισμα - ας πούμε, 99% πιθανότητες να προσγειωθεί στα κεφάλια - χρειάζεται πολύ λιγότερο. Για παράδειγμα, θα μπορούσαμε να συμφωνήσουμε εκ των προτέρων ότι θα σας στείλω ένα 1 (ένα κομμάτι πληροφοριών) εάν το φορτωμένο νόμισμα φτάσει και τις πέντε φορές, κάτι που είναι πολύ πιθανό να συμβεί. Υπάρχει μεγαλύτερη έκπληξη στο αποτέλεσμα μιας δίκαιης αναστροφής νομίσματος από ό,τι με μια προκατειλημμένη, και επομένως περισσότερες πληροφορίες.
Η ίδια σκέψη ισχύει για τις πληροφορίες που περιέχονται σε σύνολα αριθμών. Αν έχω μια οικογένεια με κλειστά σετ - ας πούμε τα 1,024 σετ από τους αριθμούς 1 έως 10 - θα μπορούσα να διαλέξω δύο σετ τυχαία. Τότε θα μπορούσα να σας κοινοποιήσω τα στοιχεία κάθε σετ. Ο όγκος των πληροφοριών που απαιτούνται για την αποστολή αυτού του μηνύματος αντικατοπτρίζει την ποσότητα της αβεβαιότητας σχετικά με το ποια είναι αυτά τα στοιχεία: Υπάρχει 50% πιθανότητα, για παράδειγμα, το πρώτο στοιχείο στο πρώτο σετ να είναι 1 (επειδή το 1 εμφανίζεται στα μισά σετ η οικογένεια), ακριβώς όπως υπάρχει 50% πιθανότητα το πρώτο αποτέλεσμα σε μια ακολουθία δίκαιων ανατροπών νομισμάτων είναι τα κεφάλια.
Η θεωρία πληροφοριών εμφανίζεται συχνά στη συνδυαστική, μια περιοχή των μαθηματικών που ασχολείται με την καταμέτρηση αντικειμένων, κάτι που είχε σπουδάσει ο Gilmer ως μεταπτυχιακός φοιτητής. Αλλά καθώς επέστρεφε στο σπίτι στην Καλιφόρνια, ανησυχούσε ότι ο τρόπος που σκέφτηκε να συνδέσει τη θεωρία της πληροφορίας με την εικασία της κλειστής ένωσης ήταν η αφελής αντίληψη ενός ερασιτέχνη: Σίγουρα οι εργαζόμενοι μαθηματικοί είχαν συναντήσει αυτό το γυαλιστερό αντικείμενο στο παρελθόν και το είχαν αναγνωρίσει ως χρυσάφι του ανόητου .
«Για να είμαι ειλικρινής, είμαι λίγο έκπληκτος που κανείς δεν το είχε σκεφτεί αυτό πριν», είπε ο Gilmer. «Αλλά ίσως δεν θα έπρεπε να εκπλαγώ, γιατί ο ίδιος το είχα σκεφτεί για ένα χρόνο και ήξερα τη θεωρία της πληροφορίας».
Πιο πιθανό παρά όχι
Ο Gilmer εργάστηκε για το πρόβλημα τη νύχτα, αφού τελείωσε τη δουλειά του στη Google, και τα Σαββατοκύριακα κατά το δεύτερο μισό του Οκτωβρίου και τις αρχές Νοεμβρίου. Ενθαρρυνόταν από ιδέες που μια ομάδα μαθηματικών είχε εξερευνήσει χρόνια νωρίτερα σε ένα ανοιχτή συνεργασία στο blog ενός εξέχοντος μαθηματικού ονόματι Tim Gowers. Δούλεψε επίσης έχοντας δίπλα του ένα εγχειρίδιο για να μπορεί να αναζητήσει τύπους που είχε ξεχάσει.
«Θα σκεφτείτε ότι κάποιος που έχει ένα εξαιρετικό αποτέλεσμα δεν πρέπει να συμβουλευτεί το Κεφάλαιο 2 του Στοιχεία Θεωρίας Πληροφοριών, αλλά το έκανα», είπε ο Γκίλμερ.
Η στρατηγική του Gilmer ήταν να φανταστεί μια οικογένεια κλειστή από συνδικάτα στην οποία κανένα στοιχείο δεν εμφανιζόταν ούτε στο 1% όλων των σετ - ένα αντιπαράδειγμα που, αν υπήρχε πραγματικά, θα παραποιούσε την εικασία του Frankl.
Ας υποθέσουμε ότι επιλέγετε δύο σετ, το Α και το Β, από αυτήν την οικογένεια τυχαία και εξετάζετε τα στοιχεία που θα μπορούσαν να υπάρχουν σε αυτά τα σετ, ένα κάθε φορά. Ρωτήστε τώρα: Ποιες είναι οι πιθανότητες που το σύνολο Α περιέχει τον αριθμό 1; Και σετ Β; Δεδομένου ότι κάθε στοιχείο έχει λίγο μικρότερη από 1% πιθανότητα να εμφανιστεί σε οποιοδήποτε δεδομένο σύνολο, δεν θα περιμένατε ούτε το Α ούτε το Β να περιέχει 1. Πράγμα που σημαίνει ότι υπάρχει μικρή έκπληξη — και ελάχιστες πληροφορίες — εάν μάθετε ότι ούτε στην πραγματικότητα κάνει.
Στη συνέχεια, σκεφτείτε την πιθανότητα η ένωση του Α και του Β να περιέχει 1. Είναι ακόμα απίθανο, αλλά είναι πιο πιθανό από τις πιθανότητες να εμφανίζεται σε κάποιο από τα μεμονωμένα σύνολα. Είναι το άθροισμα της πιθανότητας να εμφανίζεται στο Α και της πιθανότητας να εμφανίζεται στο Β μείον την πιθανότητα να εμφανίζεται και στα δύο. Άρα, ίσως λίγο λιγότερο από 2%.
Αυτό είναι ακόμα χαμηλό, αλλά είναι πιο κοντά σε μια πρόταση 50-50. Αυτό σημαίνει ότι χρειάζονται περισσότερες πληροφορίες για να μοιραστείτε το αποτέλεσμα. Με άλλα λόγια, εάν υπάρχει μια οικογένεια κλειστής ένωσης στην οποία κανένα στοιχείο δεν εμφανίζεται τουλάχιστον στο 1% όλων των συνόλων, υπάρχουν περισσότερες πληροφορίες στην ένωση δύο συνόλων από ό,τι σε κάποιο από τα ίδια τα σύνολα.
«Η ιδέα να αποκαλύπτεις τα πράγματα στοιχείο προς στοιχείο και να κοιτάς τον όγκο των πληροφοριών που μαθαίνεις είναι εξαιρετικά έξυπνη. Αυτή είναι η κύρια ιδέα της απόδειξης», είπε Ράιαν Αλβάις του Πανεπιστημίου του Πρίνστον.
Σε αυτό το σημείο ο Γκίλμερ άρχιζε να κλείνει τις εικασίες του Φράνκλ. Αυτό συμβαίνει επειδή είναι εύκολο να αποδειχθεί ότι σε μια οικογένεια κλειστή από ένωση, η ένωση δύο συνόλων περιέχει απαραίτητα λιγότερες πληροφορίες από τα ίδια τα σύνολα — όχι περισσότερες.
Για να καταλάβετε γιατί, σκεφτείτε αυτή την κλειστή οικογένεια που περιέχει τα 1,024 διαφορετικά σύνολα που μπορείτε να φτιάξετε από τους αριθμούς 1 έως 10. Εάν επιλέξετε δύο από αυτά τα σετ τυχαία, κατά μέσο όρο θα καταλήξετε σε σετ που περιέχουν πέντε στοιχεία. (Από αυτά τα 1,024 σύνολα, τα 252 περιέχουν πέντε στοιχεία, καθιστώντας αυτό το πιο κοινό μέγεθος συνόλου.) Είναι επίσης πιθανό να καταλήξετε σε μια ένωση που περιέχει περίπου επτά στοιχεία. Υπάρχουν όμως μόνο 120 διαφορετικοί τρόποι για να φτιάξεις σετ που περιέχουν επτά στοιχεία.
Το θέμα είναι ότι υπάρχει μεγαλύτερη αβεβαιότητα για τα περιεχόμενα δύο τυχαία επιλεγμένων συνόλων παρά για την ένωσή τους. Η ένωση παραμορφώνεται σε μεγαλύτερα σύνολα με περισσότερα στοιχεία, για τα οποία υπάρχουν λιγότερες δυνατότητες. Όταν λαμβάνετε την ένωση δύο συνόλων σε μια οικογένεια κλειστή από ένωση, ξέρετε κάπως τι πρόκειται να πάρετε - όπως όταν γυρίζετε ένα προκατειλημμένο νόμισμα - που σημαίνει ότι η ένωση περιέχει λιγότερες πληροφορίες από τα σύνολα από τα οποία αποτελείται.
Με αυτό, ο Gilmer είχε μια απόδειξη. Ήξερε αν δεν εμφανίζεται κανένα στοιχείο έστω και στο 1% των σετ, το σωματείο αναγκάζεται να περιέχει περισσότερες πληροφορίες. Αλλά η ένωση πρέπει να περιέχει λιγότερες πληροφορίες. Επομένως πρέπει να υπάρχει τουλάχιστον ένα στοιχείο που εμφανίζεται στο 1% τουλάχιστον των σετ.
Το Push to 50
Όταν ο Gilmer δημοσίευσε την απόδειξή του στις 16 Νοεμβρίου, συμπεριέλαβε μια σημείωση ότι πίστευε ότι ήταν δυνατό να χρησιμοποιήσει τη μέθοδό του για να πλησιάσει ακόμη περισσότερο μια απόδειξη της πλήρους εικασίας, αυξάνοντας ενδεχομένως το όριο στο 38%.
Πέντε μέρες αργότερα, τρία διαφορετικές ομάδες των μαθηματικών δημοσίευσαν έγγραφα μέσα σε λίγες ώρες ο ένας από τον άλλο που βασίστηκαν στη δουλειά του Gilmer για να κάνει ακριβώς αυτό. Πρόσθετος χαρτιά ακολουθείται, αλλά η αρχική έκρηξη φαίνεται ότι οδήγησε τις μεθόδους του Gilmer μέχρι εκεί που φτάνουν. Το να φτάσετε στο 50% πιθανότατα θα απαιτήσει επιπλέον νέες ιδέες.
Ωστόσο, για ορισμένους από τους συγγραφείς των εγγράφων παρακολούθησης, το να φτάσει στο 38% ήταν σχετικά απλό και αναρωτήθηκαν γιατί ο Gilmer δεν το έκανε μόνος του. Η απλούστερη εξήγηση αποδείχθηκε η σωστή: Μετά από πάνω από μισή δεκαετία στα μαθηματικά, ο Gilmer απλά δεν ήξερε πώς να κάνει λίγη από την τεχνική αναλυτική εργασία που απαιτούνταν για να τα καταφέρει.
«Ήμουν λίγο σκουριασμένος και για να είμαι ειλικρινής, είχα κολλήσει», είπε ο Gilmer. «Αλλά ήμουν πρόθυμος να δω πού θα το πήγαινε η κοινότητα».
Ωστόσο, ο Gilmer πιστεύει ότι οι ίδιες συνθήκες που τον άφησαν εκτός πρακτικής μάλλον κατέστησαν δυνατή την απόδειξή του από την αρχή.
«Είναι ο μόνος τρόπος που μπορώ να εξηγήσω γιατί σκέφτηκα το πρόβλημα για ένα χρόνο στο μεταπτυχιακό και δεν έκανα καμία πρόοδο, άφησα τα μαθηματικά για έξι χρόνια, μετά επέστρεψα στο πρόβλημα και έκανα αυτή την ανακάλυψη», είπε. "Δεν ξέρω πώς να το εξηγήσω, εκτός από το ότι το να είμαι στη μηχανική μάθηση προκατέλαβε τη σκέψη μου."
διόρθωση: Ιανουάριος 3, 2023
Ο αρχικός τίτλος αναφερόταν στον Gilmer ως «μηχανικό της Google». Στην πραγματικότητα είναι ερευνητής.
