Οι μαθηματικοί ολοκλήρωσαν την αναζήτηση για την κατασκευή «σφαιρικών κύβων»

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

Ή έτσι υπέθεσαν ο Pappus και άλλοι. Για χιλιετίες, κανείς δεν μπορούσε να αποδείξει ότι τα εξάγωνα ήταν τα βέλτιστα - μέχρι που τελικά, το 1999, ο μαθηματικός Τόμας Χέιλς έδειξε ότι κανένα άλλο σχήμα δεν μπορούσε να τα πάει καλύτερα. Σήμερα, οι μαθηματικοί δεν γνωρίζουν ακόμη ποια σχήματα μπορούν να πλακώσουν τρεις ή περισσότερες διαστάσεις με τη μικρότερη δυνατή επιφάνεια.

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

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

«Μου αρέσει αυτό πέρα ​​δώθε», είπε Ασάφ Ναόρ του Πανεπιστημίου Πρίνστον. «Μερικά παλιά μαθηματικά γίνονται σχετικά με την επιστήμη των υπολογιστών. η πληροφορική αποδίδει και λύνει την ερώτηση στα μαθηματικά. Είναι πολύ ωραίο όταν συμβαίνει αυτό».

Αλλά από αυτό το σχήμα, αν και βέλτιστο, έλειπε κάτι σημαντικό: μια γεωμετρική βάση. Επειδή η ύπαρξή του είχε αποδειχθεί χρησιμοποιώντας τεχνικές από την επιστήμη των υπολογιστών, η πραγματική του γεωμετρία ήταν δύσκολο να κατανοηθεί. Αυτό είναι που ο Naor, μαζί με Oded Regev, επιστήμονας υπολογιστών στο Ινστιτούτο Courant στο Πανεπιστήμιο της Νέας Υόρκης, ξεκίνησε να το διορθώσει μια απόδειξη που δημοσιεύτηκε στο διαδίκτυο τον περασμένο μήνα.

«Είναι ένα πολύ ωραίο τέλος της ιστορίας», είπε ο Regev.

Κυβικοί αφροί

Οι μαθηματικοί έχουν εξετάσει άλλες εκδοχές του προβλήματος του αφρού — συμπεριλαμβανομένου του τι συμβαίνει εάν επιτρέπεται να χωρίσετε τον χώρο μόνο σύμφωνα με αυτό που ονομάζεται πλέγμα ακέραιου αριθμού. Σε αυτήν την έκδοση του προβλήματος, παίρνετε έναν τετράγωνο πίνακα σημείων ομοιόμορφα κατανεμημένων (κάθε 1 μονάδα μεταξύ τους) και κάνετε καθένα από αυτά τα σημεία στο κέντρο ενός σχήματος. Το πρόβλημα του «κυβικού» αφρού ρωτά ποια θα είναι η ελάχιστη επιφάνεια όταν σας ζητηθεί να πλακώσετε χώρο με αυτόν τον τρόπο.

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

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

Τα τετράγωνα μπορούν. Είναι όμως αυτό το καλύτερο που μπορεί να γίνει; Ως ο μαθηματικός Jaigyoung Choe ανακαλύφθηκε το 1989, η απάντηση είναι όχι. Το βέλτιστο σχήμα είναι αντ' αυτού ένα εξάγωνο που έχει στριμωχτεί προς μια κατεύθυνση και επιμήκυνση προς μια άλλη. (Η περίμετρος ενός τέτοιου εξαγώνου είναι περίπου 3.86 όταν το εμβαδόν του είναι 1 — ξεπερνώντας την περίμετρο του τετραγώνου του 4.)

Αυτές οι διαφορές μπορεί να φαίνονται ασήμαντες, αλλά γίνονται πολύ μεγαλύτερες σε υψηλότερες διαστάσεις.

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

Αλλά οι σφαίρες δεν μπορούν να πλακώσουν ένα χώρο χωρίς να αφήσουν κενά. Από την άλλη πλευρά, ένα n-διαστατικό κύβο όγκου 1 κονσέρβα. Το πρόβλημα είναι ότι η επιφάνειά του είναι 2n, αυξανόμενη σε ευθεία αναλογία με τη διάστασή του. Ένας κύβος 10,000 διαστάσεων όγκου 1 έχει εμβαδόν επιφάνειας 20,000 — πολύ μεγαλύτερο από 400, το κατά προσέγγιση εμβαδόν επιφάνειας μιας σφαίρας 10,000 διαστάσεων.

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

Φαινόταν απίθανο. "Αν θέλετε η φυσαλίδα σας να γεμίζει ακριβώς χώρο και να είναι κεντραρισμένη σε αυτό το κυβικό πλέγμα, είναι δύσκολο να σκεφτείτε τι θα χρησιμοποιούσατε εκτός από μια κυβική φούσκα", είπε. Ράιαν Ο' Ντόνελ, θεωρητικός επιστήμονας υπολογιστών στο Πανεπιστήμιο Carnegie Mellon. «Φαίνεται πραγματικά ότι ο κύβος πρέπει να είναι ο καλύτερος».

Τώρα ξέρουμε ότι δεν είναι.

Η σκληρότητα των σκληρών προβλημάτων

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

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

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

Αποδεικνύεται ότι είναι δύσκολο να βρεθεί έστω και κατά προσέγγιση λύση σε πολλές από αυτές τις εργασίες. Ας υποθέσουμε ότι θέλετε να επισημάνετε τις κορυφές ενός γραφήματος με διαφορετικά χρώματα με τρόπο που να ικανοποιεί κάποια λίστα περιορισμών. Εάν είναι δύσκολο να ικανοποιηθούν όλοι αυτοί οι περιορισμοί, τι γίνεται με την προσπάθεια να εκπληρωθεί μόνο το 90% αυτών ή το 75% ή το 50%; Κάτω από κάποιο όριο, μπορεί να είναι δυνατό να βρεθεί ένας αποτελεσματικός αλγόριθμος, αλλά πάνω από αυτό το όριο, το πρόβλημα γίνεται NP-σκληρό.

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

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

Αλλά λίγο μετά την πρόταση του UGC το 2002, οι ερευνητές έδειξαν ότι εάν η εικασία είναι αληθινή, τότε μπορείτε εύκολα να υπολογίσετε το όριο σκληρότητας για οποιοδήποτε πρόβλημα ικανοποίησης περιορισμών. (Αυτό συμβαίνει επειδή το UGC υπονοεί επίσης ότι ένας γνωστός αλγόριθμος επιτυγχάνει την καλύτερη δυνατή προσέγγιση για όλα αυτά τα προβλήματα.) "Ήταν ακριβώς η βάση για όλα αυτά τα προβλήματα βελτιστοποίησης", είπε ο O'Donnell.

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

Δυσκολεύοντας τα δύσκολα προβλήματα

Το 2005, ο O'Donnell εργαζόταν στη Microsoft Research. Αυτός και δύο συνάδελφοι — Ουριέλ Φάιγκε, τώρα στο Ινστιτούτο Επιστημών Weizmann, και Γκάι Κίντλερ, τώρα στο Εβραϊκό Πανεπιστήμιο της Ιερουσαλήμ — συνεργάστηκε για να αντιμετωπίσει το UGC.

Είχαν μια αόριστη ιδέα για το πώς ήθελαν να προχωρήσουν. Θα ξεκινούσαν με μια ερώτηση σχετικά με τα γραφήματα - μια ερώτηση που μοιάζει πολύ με το UGC. Το λεγόμενο πρόβλημα μέγιστης περικοπής ("max-cut") ρωτά, όταν δίνεται σε ένα γράφημα, πώς να χωρίσετε τις κορυφές του σε δύο σύνολα (ή χρώματα) έτσι ώστε ο αριθμός των ακμών που συνδέουν αυτά τα σύνολα να είναι όσο το δυνατόν μεγαλύτερος. (Μπορείτε να σκεφτείτε τη μέγιστη περικοπή ως μια ερώτηση σχετικά με τον καλύτερο τρόπο χρωματισμού ενός γραφήματος με δύο χρώματα, έτσι ώστε όσο το δυνατόν λιγότερες άκρες να συνδέουν κορυφές του ίδιου χρώματος.)

Εάν το UGC είναι αληθές, αυτό σημαίνει ότι, με δεδομένο κάποιο τυχαίο γράφημα, ένας αποτελεσματικός αλγόριθμος προσέγγισης μπορεί να φτάσει μόνο στο 87% της πραγματικής μέγιστης περικοπής αυτού του γραφήματος. Το να κάνεις κάτι καλύτερο θα ήταν NP-σκληρό.

Ο Feige, ο Kindler και ο O'Donnell θέλησαν να πάνε προς την αντίθετη κατεύθυνση: Ήλπιζαν να δείξουν ότι η μέγιστη περικοπή είναι δύσκολο να προσεγγιστεί και στη συνέχεια να το χρησιμοποιήσουν για να αποδείξουν το UGC. Το σχέδιό τους βασίστηκε στη δύναμη μιας τεχνικής που ονομάζεται παράλληλη επανάληψη - μια έξυπνη στρατηγική που κάνει τα δύσκολα προβλήματα πιο δύσκολα.

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

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

Οι Feige, Kindler και O'Donnell επικεντρώθηκαν στο να δείξουν ότι η παράλληλη επανάληψη θα μπορούσε να λειτουργήσει παρά τους πονοκεφάλους. «Αυτό είναι ένα πολύ περίπλοκο πράγμα για ανάλυση», είπε Dana Moshkovitz, θεωρητικός επιστήμονας υπολογιστών στο Πανεπιστήμιο του Τέξας στο Ώστιν. «Αλλά αυτό φαινόταν δελεαστικά κοντά. Η παράλληλη επανάληψη φαινόταν ότι θα [βοηθούσε] να γίνει αυτή η σύνδεση από τη μέγιστη περικοπή σε μοναδικά παιχνίδια».

Ως προθέρμανση, οι ερευνητές προσπάθησαν να κατανοήσουν την παράλληλη επανάληψη για μια απλή περίπτωση μέγιστης περικοπής, αυτό που ο Μοσκοβίτς ονόμασε «η πιο ανόητη μέγιστη περικοπή». Θεωρήστε έναν περιττό αριθμό κορυφών που συνδέονται με ακμές για να σχηματίσουν έναν κύκλο ή "μονό κύκλο". Θέλετε να επισημάνετε κάθε κορυφή με ένα από τα δύο χρώματα, έτσι ώστε κανένα ζεύγος γειτονικών κορυφών να μην έχει το ίδιο χρώμα. Σε αυτήν την περίπτωση, αυτό είναι αδύνατο: Μια άκρη θα συνδέει πάντα κορυφές του ίδιου χρώματος. Πρέπει να διαγράψετε αυτό το άκρο, «σπάζοντας» τον περίεργο κύκλο, για να λάβετε το γράφημά σας ώστε να ικανοποιήσει τον περιορισμό του προβλήματος. Τελικά, θέλετε να ελαχιστοποιήσετε το συνολικό κλάσμα των άκρων που πρέπει να διαγράψετε για να χρωματίσετε σωστά το γράφημά σας.

Η παράλληλη επανάληψη σάς επιτρέπει να εξετάσετε μια έκδοση υψηλών διαστάσεων αυτού του προβλήματος — μια εκδοχή στην οποία πρέπει να σπάσετε όλους τους περίεργους κύκλους που εμφανίζονται. Οι Feige, Kindler και O'Donnell έπρεπε να δείξουν ότι καθώς ο αριθμός των διαστάσεων γίνεται πολύ μεγάλος, πρέπει να διαγράψετε ένα πολύ μεγάλο κλάσμα ακμών για να σπάσετε όλους τους περίεργους κύκλους. Εάν αυτό ίσχυε, θα σήμαινε ότι η παράλληλη επανάληψη θα μπορούσε να ενισχύσει αποτελεσματικά τη σκληρότητα αυτού του προβλήματος «ανόητης μέγιστης περικοπής».

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

Από τα λεμόνια στη λεμονάδα

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

«Ήμασταν, ω, τι περίεργο γεωμετρικό πρόβλημα, αλλά μάλλον είναι αλήθεια, σωστά;» είπε ο Ο' Ντόνελ. «Χρειαζόμασταν πραγματικά αυτή για να είναι η αληθινή απάντηση». Αλλά αυτός, η Feige και ο Kindler δεν μπορούσαν να το αποδείξουν. Έτσι το 2007, αυτοί δημοσίευσε ένα έγγραφο περιγράφοντας πώς σχεδίαζαν να χρησιμοποιήσουν αυτό το πρόβλημα για να βοηθήσουν στην επίθεση στο UGC.

Σύντομα, οι ελπίδες τους διαψεύστηκαν.

Ραν Ραζ, ένας θεωρητικός επιστήμονας υπολογιστών στο Πρίνστον, ο οποίος είχε ήδη αποδείξει αρκετά σημαντικά αποτελέσματα σχετικά με την παράλληλη επανάληψη, κίνησε το ενδιαφέρον της εργασίας τους. Αποφάσισε να αναλύσει την παράλληλη επανάληψη για το πρόβλημα του περιττού κύκλου, εν μέρει λόγω της σύνδεσης με τη γεωμετρία που είχαν αποκαλύψει οι Feige, Kindler και O'Donnell.

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

«Το σχέδιό μας να χρησιμοποιήσουμε την παράλληλη επανάληψη για να δείξουμε τη σκληρότητα των μοναδικών παιχνιδιών δεν λειτούργησε ούτε στην πιο απλή περίπτωση», είπε ο O'Donnell. «Αυτό το είδος έσπασε ολόκληρο το σχέδιο».

Αν και απογοητευτικό, το αποτέλεσμα του Raz υπαινίσσεται επίσης την ύπαρξη σφαιρικών κύβων: σχήματα ικανά να πλακώνουν n-διαστατικός χώρος με εμβαδόν επιφάνειας που κλιμακώνεται ανάλογα με την τετραγωνική ρίζα του n. «Ήμασταν σαν να φτιάξουμε λεμονάδα από λεμόνια και να πάρουμε αυτό το απογοητευτικό τεχνικό αποτέλεσμα σχετικά με την παράλληλη επανάληψη και τα διακριτά γραφήματα και να το μετατρέψουμε σε ένα προσεγμένο, ενδιαφέρον αποτέλεσμα στη γεωμετρία», είπε ο O'Donnell.

Αυτός και ο Kindler, σε συνεργασία με τους επιστήμονες υπολογιστών Ανούπ Ράο και Avi Wigderson, εξέτασαν τις αποδείξεις του Raz μέχρι να μάθουν τις τεχνικές του αρκετά καλά ώστε να τις μεταφράζουν στο πρόβλημα του αφρού. Το 2008 το έδειξαν σφαιρικοί κύβοι είναι πράγματι δυνατοί.

«Είναι ένας ωραίος τρόπος να συλλογιστεί κανείς το πρόβλημα», είπε Mark Braverman του Πρίνστον. "Είναι όμορφο."

Και έθεσε ερωτήματα για τη γεωμετρική πλευρά της ιστορίας. Επειδή είχαν χρησιμοποιήσει το έργο του Raz για την παράλληλη επανάληψη για να κατασκευάσουν το σχήμα τους, οι Kindler, O'Donnell, Rao και Wigderson κατέληξαν με κάτι άσχημο και σαν Frankenstein. Το πλακάκι ήταν ακατάστατο και γεμάτο εσοχές. Με μαθηματικούς όρους, δεν ήταν κυρτό. Ενώ αυτό λειτούργησε για τους σκοπούς τους, ο σφαιρικός κύβος δεν είχε ιδιότητες που προτιμούν οι μαθηματικοί - ιδιότητες που κάνουν ένα σχήμα πιο συγκεκριμένο, πιο εύκολο στον ορισμό και τη μελέτη και πιο κατάλληλο για πιθανές εφαρμογές.

«Υπάρχει κάτι πολύ δυσάρεστο στην κατασκευή τους», είπε ο Regev. «Μοιάζει με αμοιβάδα. Δεν μοιάζει με αυτό που θα περιμένατε, ένα ωραίο σώμα από πλακάκια.»

Αυτό προσπάθησαν να βρουν μαζί με τη Naor.

Breaking Free of the Cage

Από την αρχή, ο Naor και ο Regev συνειδητοποίησαν ότι θα έπρεπε να ξεκινήσουν από το μηδέν. «Επειδή εν μέρει τα κυρτά σώματα είναι τόσο περιοριστικά, καμία από τις προηγούμενες τεχνικές δεν είχε καμία πιθανότητα να λειτουργήσει», είπε. Ντορ Μίντζερ, θεωρητικός επιστήμονας υπολογιστών στο Τεχνολογικό Ινστιτούτο της Μασαχουσέτης.

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

Αλλά τον περασμένο μήνα, ο Naor και ο Regev απέδειξαν ότι μπορείτε να χωρίσετε n-διαστατικός χώρος κατά μήκος ακέραιων συντεταγμένων με ένα κυρτό σχήμα του οποίου το εμβαδόν επιφάνειας είναι αρκετά κοντά σε αυτό της σφαίρας. Και το έκαναν εντελώς γεωμετρικά — επιστρέφοντας το πρόβλημα στις μαθηματικές του ρίζες.

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

Εξετάστε ένα σημείο στο δισδιάστατο πλέγμα. Βρίσκεται 1 μονάδα μακριά από τα πλησιέστερα σημεία στην οριζόντια και κάθετη κατεύθυνση. Αλλά στη διαγώνια κατεύθυνση, το πλησιέστερο σημείο είναι $latex sqrt{2}$ μονάδες μακριά — μια απόκλιση που επιδεινώνεται σε μεγαλύτερους χώρους. Στο n-διαστατικό πλέγμα ακέραιου αριθμού, τα πλησιέστερα σημεία βρίσκονται ακόμα 1 μονάδα μακριά, αλλά αυτά τα "διαγώνια" σημεία είναι τώρα $latex sqrt{n}$ μονάδες μακριά. Σε, ας πούμε, 10,000 διαστάσεις, αυτό σημαίνει ότι ο πλησιέστερος «διαγώνιος» γείτονας σε οποιοδήποτε σημείο βρίσκεται 100 μονάδες μακριά, παρόλο που υπάρχουν 10,000 άλλα σημεία (ένα προς κάθε κατεύθυνση) που απέχουν μόνο 1 μονάδα.

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

Αλλά στο ακέραιο πλέγμα, οι μικρότερες αποστάσεις θα είναι πάντα κολλημένες στο 1. Αυτό εμποδίζει την κατασκευή ενός όμορφου πλακιδίου με βέλτιστη επιφάνεια. «Σε έβαλαν κάπως σε αυτό το κλουβί», είπε ο Ρέγεβ. «Στενουν τα πάντα γύρω σου».

Έτσι, ο Naor και ο Regev σκέφτηκαν αντ 'αυτού ένα κομμάτι από το πλήρες n-διαστατικός χώρος. Επέλεξαν προσεκτικά αυτόν τον υποχώρο, ώστε να εξακολουθεί να είναι πλούσιος σε ακέραια σημεία, αλλά κανένα από αυτά τα σημεία δεν θα είναι πολύ κοντά μεταξύ τους.

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

Αλλά αυτό ήταν μόνο η μισή δουλειά. Ο Naor και ο Regev έπρεπε να χωρίσουν ολόκληρο τον χώρο, όχι μόνο ένα κομμάτι του. Για να πάρετε ένα n- σφαιρικό κύβο διαστάσεων, έπρεπε να πολλαπλασιάσουν το αποτελεσματικό τους πλακίδιο με ένα πλακίδιο από τον υπόλοιπο χώρο (παρόμοιο με το πώς θα μπορούσατε να πολλαπλασιάσετε ένα δισδιάστατο τετράγωνο με ένα μονοδιάστατο τμήμα γραμμής για να πάρετε έναν τρισδιάστατο κύβο). Κάτι τέτοιο θα ανέβαζε την κατασκευή τους πίσω στον αρχικό χώρο, αλλά θα αύξανε επίσης την επιφάνεια της.

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

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

«Όταν τα πράγματα γίνονται διαφορετικά», πρόσθεσε ο Ραζ, «μερικές φορές βρίσκεις ενδιαφέρουσες πρόσθετες συνέπειες».

Η Ελπίδα αναζωπυρώθηκε

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

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

Ο Braverman και ο Minzer δοκίμασαν έναν τέτοιο τρόπο όταν το έκαναν ξαναεπισκέφτηκε τους αφρούς το 2020. Αντί να απαιτήσουν το σχήμα του πλακιδίου να είναι κυρτό, ζήτησαν να υπακούει σε ορισμένες συμμετρίες, έτσι ώστε να φαίνεται το ίδιο ανεξάρτητα από το πώς αναποδογυρίζετε τις συντεταγμένες του. (Σε 2D, ένα τετράγωνο θα λειτουργούσε, αλλά ένα ορθογώνιο όχι, ούτε οι υψηλών διαστάσεων σφαιρικοί κύβοι που περιγράφηκαν μέχρι σήμερα.) Κάτω από αυτόν τον νέο περιορισμό, το ζευγάρι μπόρεσε να δείξει τι ήλπιζαν ο Kindler και άλλοι 15 χρόνια νωρίτερα: ότι τελικά δεν μπορείτε να κάνετε πολύ καλύτερα από την επιφάνεια του κύβου.

Αυτό αντιστοιχούσε σε ένα διαφορετικό είδος παράλληλης επανάληψης — κάτι που θα έκανε την απλούστερη περίπτωση της μέγιστης κοπής τόσο δύσκολη όσο χρειαζόταν. Ενώ το αποτέλεσμα προσφέρει κάποια ελπίδα για αυτήν τη γραμμή έρευνας, δεν είναι σαφές εάν αυτή η έκδοση παράλληλης επανάληψης θα λειτουργήσει για όλα τα προβλήματα μέγιστης περικοπής. «Δεν σημαίνει ότι τελειώσατε», είπε ο Braverman. «Απλώς σημαίνει ότι έχετε επιστρέψει στην επιχείρηση».

«Υπάρχουν πολλές δυνατότητες στη γεωμετρία», είπε ο Minzer. «Απλώς δεν το καταλαβαίνουμε αρκετά καλά».