Les mathématiciens terminent la quête pour construire des "cubes sphériques"

Au IVe siècle, le mathématicien grec Pappus d'Alexandrie a fait l'éloge des abeilles pour leur « prévoyance géométrique ». La structure hexagonale de leur nid d'abeilles semblait être le moyen optimal de diviser l'espace bidimensionnel en cellules de surface égale et de périmètre minimal - permettant aux insectes de réduire la quantité de cire dont ils avaient besoin pour produire et de passer moins de temps et d'énergie à construire leur ruche.

Ou alors Pappus et d'autres ont émis l'hypothèse. Pendant des millénaires, personne n'a pu prouver que les hexagones étaient optimaux - jusqu'à ce que finalement, en 1999, le mathématicien Thomas Hales montre qu'aucune autre forme ne pouvait faire mieux. Aujourd'hui, les mathématiciens ne savent toujours pas quelles formes peuvent recouvrir trois dimensions ou plus avec la plus petite surface possible.

Ce problème de «mousse» s'est avéré avoir de nombreuses applications - pour les physiciens étudiant le comportement des bulles de savon (ou mousses) et les chimistes analysant la structure des cristaux, pour les mathématiciens explorant les arrangements de sphères et les statisticiens développant des techniques efficaces de traitement des données .

Au milieu des années 2000, une formulation particulière du problème de la mousse a également attiré l'attention des informaticiens théoriciens, qui ont découvert, à leur grande surprise, qu'elle était profondément liée à un problème ouvert important dans leur domaine. Ils ont pu utiliser cette connexion pour trouver une nouvelle forme de grande dimension d'une surface minimale.

"J'adore ce va-et-vient", a déclaré Assaf Naor de l'Université de Princeton. « Certaines mathématiques anciennes deviennent pertinentes pour l'informatique ; l'informatique rembourse et résout la question en mathématiques. C'est très agréable quand cela arrive.

Mais cette forme, bien qu'optimale, manquait quelque chose d'important : une base géométrique. Parce que son existence avait été prouvée à l'aide de techniques issues de l'informatique, sa géométrie réelle était difficile à saisir. C'est ce que Naor, avec Oded-Regev, informaticien au Courant Institute de l'université de New York, a entrepris de corriger en une épreuve mise en ligne le mois dernier.

"C'est une très belle fin à l'histoire", a déclaré Regev.

Mousses cubiques

Les mathématiciens ont envisagé d'autres versions du problème de la mousse - y compris ce qui se passe si vous n'êtes autorisé à partitionner l'espace qu'en fonction de ce qu'on appelle le réseau entier. Dans cette version du problème, vous prenez un tableau carré de points régulièrement espacés (chacun à 1 unité) et faites de chacun de ces points le centre d'une forme. Le problème de la mousse «cubique» demande quelle sera la surface minimale lorsque vous devrez carreler l'espace de cette manière.

Les chercheurs se sont initialement intéressés à imposer cette restriction afin de comprendre les propriétés des espaces topologiques appelés variétés. Mais la question a pris une vie propre, devenant pertinente dans l'analyse des données et d'autres applications.

C'est aussi géométriquement intéressant, car cela change ce que « optimal » pourrait signifier. En deux dimensions, par exemple, les hexagones réguliers ne peuvent plus carreler le plan s'ils ne peuvent être décalés que de quantités entières dans les directions horizontale et verticale. (Vous devez les déplacer par des quantités irrationnelles dans l'une des deux directions.)

Les carrés peuvent. Mais est-ce le mieux que l'on puisse faire ? Comme le mathématicien Jaigyoung Choe découvert en 1989, la réponse est non. La forme optimale est plutôt un hexagone qui a été écrasé dans une direction et allongé dans une autre. (Le périmètre d'un tel hexagone est d'environ 3.86 lorsque son aire est de 1 - battant le périmètre du carré de 4.)

Ces différences peuvent sembler insignifiantes, mais elles deviennent beaucoup plus importantes dans les dimensions supérieures.

Parmi toutes les formes d'un volume donné, celle qui minimise la surface est la sphère. Comme n, le nombre de dimensions, croît, la surface de la sphère augmente proportionnellement à la racine carrée de n.

Mais les sphères ne peuvent pas recouvrir un espace sans laisser de vides. D'autre part, un n-cube dimensionnel du volume 1 boîte. Le hic, c'est que sa surface est de 2n, croissant en proportion directe avec sa dimension. Un cube de 10,000 1 dimensions de volume 20,000 a une surface de 400 10,000 - beaucoup plus grande que XNUMX, la surface approximative d'une sphère de XNUMX XNUMX dimensions.

Et donc les chercheurs se sont demandé s'ils pouvaient trouver un "cube sphérique" - une forme qui tuile n-espace dimensionnel, comme un cube, mais dont la surface croît lentement, comme celle d'une sphère.

Cela semblait peu probable. "Si vous voulez que votre bulle remplisse exactement l'espace et soit centrée sur cette grille cubique, il est difficile de penser à ce que vous utiliseriez sauf pour une bulle cubique", a déclaré Ryan O'Donnell, informaticien théoricien à l'Université Carnegie Mellon. "Il semble vraiment que le cube devrait être le meilleur."

Nous savons maintenant que ce n'est pas le cas.

La dureté des problèmes difficiles

Pendant des décennies, le problème de la mousse cubique est resté relativement inexploré dans les dimensions supérieures. Les premiers chercheurs à y avoir fait des progrès ne sont pas issus du domaine de la géométrie mais de l'informatique théorique. Ils sont tombés dessus par hasard, alors qu'ils cherchaient un moyen de prouver une affirmation centrale dans leur domaine connue sous le nom de conjecture de jeux uniques. "La conjecture des jeux uniques", a déclaré Regev, "est ce que je considère actuellement comme la plus grande question ouverte en informatique théorique."

Proposé en 2002 par Subhash Khot, étudiant diplômé à l'époque, la conjecture postule que si un problème particulier - qui consiste à attribuer des couleurs aux nœuds d'un réseau - ne peut pas être résolu exactement, alors trouver une solution même approximative est très difficile. Si cela est vrai, la conjecture permettrait aux chercheurs de comprendre la complexité d'un vaste assortiment d'autres tâches de calcul d'un seul coup.

Les informaticiens classent souvent les tâches selon qu'elles peuvent être résolues avec un algorithme efficace ou qu'elles sont plutôt "NP-difficiles" (ce qui signifie qu'elles ne peuvent pas être résolues efficacement à mesure que la taille du problème augmente, tant qu'un mais la conjecture non prouvée sur la complexité de calcul est vraie). Par exemple, le problème du voyageur de commerce, qui demande le chemin le plus court nécessaire pour visiter chaque ville d'un réseau une seule fois, est NP-difficile. Il en va de même pour déterminer si un graphe - une collection de sommets reliés par des arêtes - peut être étiqueté avec au plus trois couleurs afin que deux sommets connectés aient des couleurs différentes.

Il s'avère qu'il est NP-difficile de trouver même une solution approximative à bon nombre de ces tâches. Supposons que vous souhaitiez étiqueter les sommets d'un graphe avec différentes couleurs d'une manière qui satisfasse à une liste de contraintes. S'il est NP-difficile de satisfaire toutes ces contraintes, qu'en est-il d'essayer d'en remplir seulement 90 %, ou 75 %, ou 50 % ? En dessous d'un certain seuil, il pourrait être possible de trouver un algorithme efficace, mais au-dessus de ce seuil, le problème devient NP-difficile.

Pendant des décennies, les informaticiens ont travaillé pour fixer des seuils pour différents problèmes d'optimisation d'intérêt. Mais certaines questions échappent à ce genre de description. Alors qu'un algorithme peut garantir 80% de la meilleure solution, il peut être NP-difficile d'atteindre 95% de la meilleure solution, laissant en suspens la question de savoir où exactement entre 80% et 95% le problème bascule en territoire NP-difficile.

La conjecture des jeux uniques, ou UGC, offre un moyen d'identifier immédiatement la réponse. Il fait une déclaration qui semble à première vue plus limitée : qu'il est NP-difficile de faire la différence entre un graphe pour lequel vous pouvez satisfaire la quasi-totalité d'un certain ensemble de contraintes de coloration (par exemple, plus de 99 %) et un graphe pour que vous pouvez satisfaire à peine (disons, moins de 1%).

Mais peu de temps après la proposition de l'UGC en 2002, les chercheurs ont montré que si la conjecture est vraie, alors vous pouvez facilement calculer le seuil de dureté pour tout problème de satisfaction de contraintes. (C'est parce que l'UGC implique également qu'un algorithme connu réalise la meilleure approximation possible pour tous ces problèmes.) "C'était précisément la clé de voûte de tous ces problèmes d'optimisation", a déclaré O'Donnell.

Et donc des informaticiens théoriciens ont entrepris de prouver l'UGC - une tâche qui a finalement conduit certains d'entre eux à découvrir des cubes sphériques.

Rendre les problèmes difficiles plus difficiles

En 2005, O'Donnell travaillait chez Microsoft Research. Lui et deux collègues — Uriel Feige, maintenant à l'Institut Weizmann des sciences, et Guy Kindler, maintenant à l'Université hébraïque de Jérusalem - ont fait équipe pour s'attaquer à l'UGC.

Ils avaient une vague idée de la façon dont ils voulaient procéder. Ils commenceraient par une question sur les graphiques - une question très similaire à l'UGC. Le problème dit de coupe maximale ("max-cut") demande, lorsqu'on lui donne un graphe, comment partitionner ses sommets en deux ensembles (ou couleurs) afin que le nombre d'arêtes reliant ces ensembles soit aussi grand que possible. (Vous pouvez considérer la coupe max comme une question sur la meilleure façon de colorer un graphique avec deux couleurs, de sorte que le moins d'arêtes possible relient les sommets de la même couleur.)

Si l'UGC est vrai, cela impliquerait que, étant donné un graphique aléatoire, un algorithme d'approximation efficace ne peut atteindre qu'environ 87% de la véritable coupe maximale de ce graphique. Faire mieux serait NP-difficile.

Feige, Kindler et O'Donnell voulaient plutôt aller dans la direction opposée : ils espéraient montrer que la coupe maximale est difficile à approximer, puis l'utiliser pour prouver l'UGC. Leur plan reposait sur la force d'une technique appelée répétition parallèle - une stratégie intelligente qui rend les problèmes difficiles plus difficiles.

Disons que vous savez qu'il est NP-difficile de faire la distinction entre un problème que vous pouvez résoudre et un problème que vous pouvez résoudre en grande partie. La répétition parallèle vous permet de vous baser sur cela pour montrer un résultat de dureté beaucoup plus fort : qu'il est également NP-difficile de faire la distinction entre un problème que vous pouvez résoudre et un que vous pouvez à peine résoudre du tout. "Ce phénomène profond et non intuitif … est dans les entrailles de beaucoup d'informatique aujourd'hui", a déclaré Naor.

Mais il y a un hic. La répétition parallèle n'amplifie pas toujours la difficulté d'un problème autant que les informaticiens le souhaitent. En particulier, il y a des aspects du problème de la coupe maximale qui "créent un gros casse-tête pour la répétition parallèle", a déclaré Regev.

Feige, Kindler et O'Donnell se sont concentrés sur la démonstration que la répétition parallèle pouvait fonctionner malgré les maux de tête. "C'est une chose vraiment compliquée à analyser", a déclaré Dana Moshkovitz, informaticien théoricien à l'Université du Texas, Austin. «Mais cela semblait terriblement proche. La répétition parallèle semblait [help make] cette connexion de la coupe maximale aux jeux uniques.

En guise d'échauffement, les chercheurs ont essayé de comprendre la répétition parallèle pour un cas simple de coupe maximale, ce que Moshkovitz a appelé "la coupe maximale la plus stupide". Considérez un nombre impair de sommets reliés par des arêtes pour former un cercle, ou "cycle impair". Vous souhaitez étiqueter chaque sommet avec l'une des deux couleurs afin qu'aucune paire de sommets adjacents n'ait la même couleur. Dans ce cas, c'est impossible : une arête connectera toujours des sommets de la même couleur. Vous devez supprimer cette arête, "casser" le cycle impair, pour que votre graphique satisfasse la contrainte du problème. En fin de compte, vous souhaitez minimiser la fraction totale des arêtes que vous devez supprimer pour colorer correctement votre graphique.

La répétition parallèle vous permet d'envisager une version de grande dimension de ce problème - une version dans laquelle vous devez briser tous les cycles impairs qui apparaissent. Feige, Kindler et O'Donnell avaient besoin de montrer que lorsque le nombre de dimensions devient très grand, vous devez supprimer une très grande fraction d'arêtes pour briser tous les cycles impairs. Si cela était vrai, cela signifierait que la répétition parallèle pourrait effectivement amplifier la dureté de ce problème de "coupe maximale stupide".

C'est alors que l'équipe a découvert une curieuse coïncidence : il y avait une manière géométrique d'interpréter si la répétition parallèle fonctionnerait comme ils l'espéraient. Le secret réside dans la surface des mousses cubiques.

Des citrons à la limonade

Leur problème, réécrit dans le langage des mousses, se résumait à montrer que les cubes sphériques ne peuvent pas exister - qu'il est impossible de partitionner l'espace de grande dimension le long du réseau entier en cellules avec une surface beaucoup plus petite que celle du cube. (Une plus grande surface correspond à la nécessité de supprimer plus de "mauvais" bords dans le graphique des cycles impairs, comme les informaticiens espéraient le montrer.)

"Nous étions comme, oh, quel problème de géométrie étrange, mais c'est probablement vrai, non?" dit O'Donnell. "Nous avions vraiment besoin que ce soit la vraie réponse." Mais lui, Feige et Kindler n'ont pas pu le prouver. Ainsi, en 2007, ils publié un document décrivant comment ils prévoyaient d'utiliser ce problème pour aider à attaquer l'UGC.

Bientôt, leurs espoirs ont été déçus.

Couru Raz, un informaticien théoricien à Princeton qui avait déjà prouvé plusieurs résultats majeurs sur la répétition parallèle, a été intrigué par leur article. Il a décidé d'analyser la répétition parallèle pour le problème du cycle impair, en partie à cause du lien avec la géométrie que Feige, Kindler et O'Donnell avaient découvert.

Raz n'a pas commencé par le problème de la mousse mais a attaqué de front la version informatique de la question. Il a montré que vous pouvez vous en tirer en supprimant beaucoup moins d'arêtes pour briser tous les cycles impairs d'un graphique. En d'autres termes, la répétition parallèle ne peut pas suffisamment amplifier la difficulté de ce problème de coupe maximale. "Les paramètres que l'on obtient exactement à partir de la répétition parallèle ne suffisent pas à donner cela", a déclaré Moshkovitz.

"Notre plan d'utiliser la répétition parallèle pour montrer la dureté de jeux uniques n'a même pas fonctionné dans le cas le plus simple", a déclaré O'Donnell. "Ce genre de cassé tout le plan."

Bien que décevant, le résultat de Raz laissait aussi entrevoir l'existence de cubes sphériques : des formes capables de paver n-espace dimensionnel dont la surface est proportionnelle à la racine carrée de n. "Nous étions comme, eh bien, faisons de la limonade avec des citrons et prenons ce résultat technique décevant sur la répétition parallèle et les graphiques discrets, et transformons-le en un résultat soigné et intéressant en géométrie", a déclaré O'Donnell.

Lui et Kindler, en collaboration avec les informaticiens Anup Rao et les Avi Wigderson, se sont penchés sur la preuve de Raz jusqu'à ce qu'ils aient suffisamment bien appris ses techniques pour les traduire au problème de la mousse. En 2008, ils ont montré que les cubes sphériques sont en effet possibles.

"C'est une bonne façon de raisonner sur le problème", a déclaré Marc Braverman de Princeton. "C'est beau."

Et cela a soulevé des questions sur le côté géométrique de l'histoire. Parce qu'ils avaient utilisé le travail de Raz sur la répétition parallèle pour construire leur forme de carrelage, Kindler, O'Donnell, Rao et Wigderson se sont retrouvés avec quelque chose de laid et de Frankenstein. La tuile était en désordre et pleine d'indentations. En termes mathématiques, il n'était pas convexe. Bien que cela ait fonctionné pour leurs besoins, le cube sphérique manquait des propriétés que les mathématiciens préfèrent - des propriétés qui rendent une forme plus concrète, plus facile à définir et à étudier, et plus adaptée aux applications potentielles.

"Il y a quelque chose de très insatisfaisant dans leur construction", a déclaré Regev. « Cela ressemble à une amibe. Cela ne ressemble pas à ce à quoi vous vous attendez, un joli corps de carrelage.

C'est ce que lui et Naor ont entrepris de découvrir.

Se libérer de la cage

Dès le départ, Naor et Regev ont réalisé qu'ils devaient repartir de zéro. "En partie parce que les corps convexes sont si restrictifs, aucune des techniques précédentes n'avait la moindre chance de fonctionner", a déclaré Dor Minzer, informaticien théoricien au Massachusetts Institute of Technology.

En fait, il était tout à fait plausible que la convexité soit trop restrictive - qu'un cube sphérique convexe n'existe tout simplement pas.

Mais le mois dernier, Naor et Regev ont prouvé qu'on pouvait partitionner n-espace dimensionnel le long de coordonnées entières avec une forme convexe dont la surface est assez proche de celle de la sphère. Et ils l'ont fait entièrement géométriquement - ramenant le problème à ses racines mathématiques.

Ils devaient d'abord contourner un obstacle majeur. Le problème de la mousse cubique nécessite que chaque tuile soit centrée sur des coordonnées entières. Mais dans le réseau entier, il y a de très courtes distances entre certains points - et ces courtes distances causent des problèmes.

Considérons un point dans la grille à deux dimensions. Il est situé à 1 unité de ses points les plus proches dans les directions horizontale et verticale. Mais dans la direction diagonale, le point le plus proche est à $latex sqrt{2}$ unités ; un écart qui s'aggrave dans les grands espaces. Dans le n-treillis entier dimensionnel, les points les plus proches sont toujours à 1 unité, mais ces points "diagonaux" sont maintenant $latex sqrt{n}$ unités. Dans, disons, 10,000 100 dimensions, cela signifie que le voisin "diagonal" le plus proche de n'importe quel point est à 10,000 unités de distance même s'il y a 1 XNUMX autres points (un dans chaque direction) qui ne sont qu'à XNUMX unité de distance.

Dans d'autres réseaux, ces deux types de distances croissent proportionnellement l'une à l'autre. Les mathématiciens savent depuis des décennies comment paver de tels réseaux avec des formes convexes de surface minimale.

Mais dans le treillis entier, les distances les plus courtes seront toujours bloquées à 1. Cela empêche de construire une jolie tuile de surface optimale. "Ils vous ont en quelque sorte mis dans cette cage", a déclaré Regev. "Ils rendent tout très serré autour de vous."

Alors Naor et Regev ont plutôt considéré une tranche de la totalité n-espace dimensionnel. Ils ont soigneusement choisi ce sous-espace afin qu'il soit toujours riche en points entiers, mais aucun de ces points ne soit trop rapproché.

En d'autres termes, le sous-espace avec lequel ils se sont retrouvés était précisément le type que les mathématiciens savaient déjà comment paver de manière optimale.

Mais ce n'était que la moitié du travail. Naor et Regev devaient partitionner tout l'espace, pas seulement une partie de celui-ci. Pour obtenir un ncube sphérique tridimensionnel, ils devaient multiplier leur tuile efficace avec une tuile de l'espace restant (semblable à la façon dont vous pourriez multiplier un carré bidimensionnel avec un segment de ligne unidimensionnel pour obtenir un cube tridimensionnel). Cela ramènerait leur construction dans l'espace d'origine, mais cela augmenterait également sa surface.

La paire devait montrer que la tuile de l'espace restant, qui n'était pas aussi optimale, n'ajoutait pas trop à la surface. Une fois qu'ils ont fait cela, leur construction était terminée. (La surface de leur forme finale a fini par être un peu plus grande que celle du cube sphérique non convexe, mais ils pensent qu'il pourrait être possible de trouver une tuile convexe tout aussi efficace que son homologue non convexe.)

"Leur preuve est complètement différente" des travaux antérieurs sur les cubes sphériques, a déclaré le mathématicien Noga Alon. « Et rétrospectivement, c'est peut-être une preuve plus naturelle. C'est ce que quelqu'un aurait peut-être dû essayer de commencer.

"Quand les choses sont faites différemment", a ajouté Raz, "vous trouvez parfois des implications supplémentaires intéressantes."

L'espoir ravivé

On ne sait pas encore quelles pourraient être ces implications - bien que les travaux exploitent l'utilisation potentielle de réseaux entiers dans la cryptographie et d'autres applications. Étant donné à quel point ce problème est lié à d'autres domaines, "il est susceptible de conduire à d'autres choses", a déclaré Alon.

Pour le moment, les informaticiens ne voient pas comment interpréter le résultat convexe dans le langage de la répétition parallèle et de l'UGC. Mais ils n'ont pas entièrement abandonné le plan initial d'utiliser le problème de la mousse pour prouver la conjecture. "Il existe différentes façons d'essayer de renverser les obstacles évidents que nous avons rencontrés", a déclaré Kindler.

Braverman et Minzer ont essayé un tel moyen lorsqu'ils mousses revisitées en 2020. Au lieu d'exiger que la forme de carrelage soit convexe, ils ont demandé qu'elle obéisse à certaines symétries, de sorte qu'elle ait la même apparence, peu importe la façon dont vous retournez ses coordonnées. (En 2D, un carré fonctionnerait, mais pas un rectangle ; les cubes sphériques de grande dimension décrits à ce jour non plus.) Sous cette nouvelle contrainte, la paire a pu montrer ce que Kindler et d'autres avaient espéré 15 ans plus tôt : que vous ne pouvez pas faire beaucoup mieux que la surface du cube après tout.

Cela correspondait à un autre type de répétition parallèle - une répétition qui rendrait le cas le plus simple de la coupe maximale aussi difficile que nécessaire. Bien que le résultat offre un certain espoir pour cette ligne de recherche, il n'est pas clair si cette version de la répétition parallèle fonctionnera pour tous les problèmes de coupe maximale. "Cela ne signifie pas que vous avez terminé", a déclaré Braverman. "Cela signifie simplement que vous êtes de retour dans les affaires."

"Il y a beaucoup de potentiel en géométrie", a déclaré Minzer. "C'est juste que nous ne le comprenons pas assez bien."