Un nouveau record de densité d’empilement de sphères venu d’un lieu inattendu
(quantamagazine.org)- Dans le problème d’empilement de sphères en haute dimension, Boaz Klartag a mis en ligne en avril un court manuscrit contenant la plus forte amélioration d’efficacité depuis Claude Ambrose Rogers en 1947
- La nouvelle méthode part d’un réseau arbitraire, construit un ellipsoïde plus grand, puis applique la procédure de Rogers pour obtenir un empilement de sphères dense, redonnant vie à une approche géométrique longtemps délaissée
- La construction de Klartag permet, en dimension d, d’empiler environ d fois plus de sphères que nombre de résultats antérieurs : environ 100 fois plus en dimension 100, et environ 1 million de fois plus en dimension 1 million
- Contrairement aux discussions sur la possibilité d’empilements désordonnés amplifiées après le record non fondé sur un réseau de 2023, ce résultat suggère que l’ordre et la symétrie peuvent encore être des candidats sérieux pour l’empilement optimal en haute dimension
- Le problème de l’empilement de sphères est important pour des applications en cryptographie et en communication, mais ce résultat n’a pas d’application immédiate et pourrait surtout relier à nouveau géométrie convexe et théorie des réseaux
Une avancée majeure pour l’empilement de sphères en haute dimension
- Le problème de l’empilement de sphères consiste à trouver comment remplir un espace de haute dimension avec des sphères aussi efficacement que possible
- Ce problème fascine les mathématiciens depuis des siècles et pourrait avoir d’importantes applications en cryptographie et en communication à longue distance
- Au début du XVIIe siècle, Johannes Kepler a montré qu’en empilant des sphères en 3 dimensions comme des oranges dans une épicerie, on peut remplir environ 74 % de l’espace, et il a conjecturé que c’était optimal
- Cette conjecture n’a été démontrée que près de 400 ans plus tard
- En dimension plus élevée, on ne connaît toujours pas la réponse optimale, sauf en dimensions 8 et 24
- Les mathématiciens cherchent depuis longtemps de meilleurs empilements, mais les progrès étaient modestes et rares
- Dans un court manuscrit mis en ligne en avril, Boaz Klartag a largement dépassé le record précédent, et certains chercheurs pensent que ce résultat pourrait être proche de l’optimal
Une vieille idée allant du réseau à l’ellipsoïde
- En 1905, Hermann Minkowski a posé une manière de penser l’empilement de sphères à l’aide des réseaux (lattices)
- Il s’agit de créer un arrangement périodique de points dans l’espace, puis de dessiner une sphère autour de chaque point
- Trouver l’empilement optimal dans une dimension donnée revient alors à trouver le réseau où les points sont disposés de la manière la plus efficace
- En 2 dimensions, le réseau hexagonal est optimal
- En 1947, Claude Ambrose Rogers a proposé une autre perspective
- Il est possible de partir de n’importe quel réseau, même non optimal
- Au lieu de dessiner une sphère autour de chaque point, on trace un ellipsoïde autour d’un point de façon que sa surface touche d’autres points du réseau sans les dépasser
- Il a donné un algorithme permettant de construire un empilement de sphères dense à partir de cet ellipsoïde
- L’avantage de la méthode de Rogers est que le réseau de départ n’a pas besoin d’être particulièrement efficace
- Il suffit de choisir le bon ellipsoïde pour obtenir un empilement de sphères performant
- Mais les ellipsoïdes sont plus difficiles à manipuler que les sphères
- Une sphère est définie par un seul rayon, tandis qu’un ellipsoïde est défini par plusieurs axes de longueurs différentes
- Plus la dimension augmente, plus le nombre de directions d’étirement et de formes possibles croît rapidement
- Les mathématiciens sont finalement revenus à l’approche de type Minkowski et se sont davantage concentrés sur la théorie des réseaux, s’éloignant de l’approche géométrique de Rogers
- Cette stratégie a aussi permis d’améliorer l’empilement de sphères en haute dimension, mais les gains sont restés, pour la plupart, plus faibles que ceux de l’empilement de Rogers
Un spécialiste de géométrie convexe redonne vie à l’approche de Rogers
- Klartag est mathématicien au Weizmann Institute of Science et travaille surtout en géométrie convexe (convex geometry)
- Une forme convexe est une forme qui ne présente pas de creux vers l’intérieur
- En haute dimension, elle peut inclure diverses symétries, et Klartag voit dans ces formes de puissants outils mathématiques
- Il s’intéressait aux réseaux et à l’empilement de sphères, mais n’avait pas eu le temps d’étudier le domaine en profondeur
- Après avoir terminé un grand projet en novembre dernier, il a demandé à Barak Weiss, de la Tel Aviv University, de l’aider à découvrir un nouveau domaine
- Weiss a lancé un petit séminaire où Klartag et quelques autres lisaient ensemble la littérature
- Klartag a étudié en détail les méthodes d’empilement de sphères de Minkowski et de Rogers
- Après avoir lu la méthode de Rogers pour transformer des ellipsoïdes en empilements de sphères, Klartag s’est demandé pourquoi les mathématiciens l’avaient abandonnée
- Les ellipsoïdes sont des formes convexes, et Klartag disposait donc de méthodes sophistiquées pour les manipuler
- Il a estimé que l’ellipsoïde de départ utilisé par Rogers était intuitif, mais inefficace
- S’il pouvait construire un ellipsoïde de plus grand volume, il pourrait établir un nouveau record d’empilement en appliquant la procédure originale de Rogers
Faire croître un plus grand ellipsoïde de façon aléatoire
- Klartag est parti d’une méthode qui lui est familière, consistant à faire croître et rétrécir la frontière d’un ellipsoïde selon un processus aléatoire le long de chaque axe
- Lorsque la frontière s’étend suffisamment pour toucher un nouveau point du réseau, la croissance s’arrête dans cette direction
- Ce point n’entre donc pas dans l’ellipsoïde
- Dans d’autres directions, l’ellipsoïde continue de se dilater jusqu’à toucher d’autres points
- Au cours du processus, l’ellipsoïde avance par à-coups, s’arrêtant et repartant tout en explorant progressivement l’espace alentour
- Avec le temps, son volume augmente en moyenne
- La question centrale de Klartag était de savoir si cette augmentation de volume suffisait à dépasser l’ellipsoïde intuitif de Rogers
- Comme le processus aléatoire produisait un ellipsoïde différent à chaque exécution, Klartag a évalué l’éventail des volumes possibles
- Au départ, il n’a pas trouvé d’ellipsoïde unique suffisamment grand pour dépasser celui de Rogers
- Après avoir ajusté les détails du processus de croissance aléatoire, il a démontré en une à deux semaines que l’on obtenait parfois des ellipsoïdes assez grands pour établir un nouveau record
Ce que signifie une amélioration d’environ d fois
- La démonstration de Klartag a été vérifiée, et la conversion de son nouvel ellipsoïde de départ en empilement de sphères produit la plus forte amélioration d’efficacité depuis l’article de Rogers en 1947
- Dans une dimension donnée d, la méthode de Klartag permet d’empiler environ d fois plus de sphères que de nombreux résultats antérieurs
- Dans un espace de dimension 100, cela représente environ 100 fois plus de sphères
- Dans un espace de dimension 1 million, cela représente environ 1 million de fois plus de sphères
- Klartag a étudié le domaine de l’empilement de sphères pendant quelques mois, puis rédigé sa preuve en quelques semaines, faisant fortement progresser un problème central
- Son expérience en géométrie convexe a directement permis d’appliquer au problème de l’empilement de sphères des techniques habituellement considérées comme relevant d’un autre domaine
- Gil Kalai a qualifié ce résultat de « véritable percée stupéfiante » et l’a relié à un problème qui passionne les mathématiciens depuis près de 100 ans
Le débat entre ordre et désordre
- Le résultat de Klartag relance le débat sur la nature des empilements optimaux en haute dimension
- Pendant longtemps, les mathématiciens ont pensé que les empilements fondés sur des réseaux, très symétriques, étaient la meilleure manière de disposer les sphères le plus densément possible
- En 2023, on a découvert un empilement qui ne repose pas proprement sur un réseau périodique, et qui constituait le record avant Klartag
- Certains mathématiciens y ont vu un indice qu’il fallait davantage de désordre pour trouver l’empilement optimal
- Le travail de Klartag redonne du poids à l’idée que l’ordre et la symétrie peuvent rester les meilleurs candidats
- La densité maximale atteignable par un empilement de sphères reste toutefois débattue
- Certains mathématiciens estiment que l’empilement de Klartag est très proche de l’optimal
- D’autres pensent qu’il reste une marge d’amélioration
- Marcus Michelen, de l’University of Illinois Chicago, dit ne pas savoir aujourd’hui quoi croire et que toutes les possibilités restent ouvertes
Un lien entre disciplines plus important qu’une application immédiate
- La réponse au problème de l’empilement de sphères est importante en raison de ses applications possibles en cryptographie et en communication
- Or Ordentlich, théoricien de l’information à la Hebrew University, explique que ce problème intéresse fortement les ingénieurs mais avait peu progressé, d’où l’enthousiasme suscité par ce résultat
- Cela dit, le résultat de Klartag n’est pas immédiatement utile pour ces applications
- Klartag espère surtout que son travail favorisera un retour à une époque, comme celle de Rogers, où géométrie convexe et théorie des réseaux étaient davantage connectées
- Il estime que la compréhension actuelle des corps convexes pourrait être utile non seulement pour l’empilement de sphères, mais aussi pour les problèmes de réseaux
- Son objectif est de rendre ces deux domaines moins cloisonnés qu’ils ne le sont aujourd’hui
1 commentaires
Commentaires sur Hacker News
J’ai déjà du mal à expliquer à mes parents que mon travail est un vrai métier ; alors leur expliquer que « j’étudie uniquement des formes qui n’ont pas de parties qui dépassent ni de creux vers l’intérieur », rien que l’idée me paraît encore plus difficile.
En réalité, il n’y a que trois options. Si on l’explique brièvement avec des mots que l’autre comprend, le travail paraît facile et il se dit : « Comment peut-on être payé pour ça ? »
Si on explique, avec des mots que l’autre comprend, ce qu’on fait et pourquoi c’est important, ça devient trop long, ennuyeux, et il regrette d’avoir posé la question.
Ou alors on l’explique brièvement avec du jargon qu’il ne comprend pas : c’est ennuyeux, mais ça impressionne. Parmi les mauvaises options, c’est la meilleure.
Je n’ai toujours pas trouvé comment expliquer mon activité de façon à ce qu’une personne ordinaire puisse en comprendre ne serait-ce qu’un peu. Tout est trop obscur et éloigné de plusieurs niveaux de la vie quotidienne.
Ce n’est pas forcément compliqué, mais il y a trop de détails auxquels une personne moyenne n’a jamais été exposée, et presque aucune analogie du quotidien.
Pour les corps convexes, je ne sais pas trop.
Un ton qui paraît excessivement détaillé peut devenir toxique et faire fuir les gens.
On peut l’expliquer sous un angle du type : « J’essaie de faire XYZ, mais c’est tellement difficile que c’est frustrant ; alors je fais une hypothèse simple. Penser ce problème de manière aussi grossière le rend plus facile à traiter, et comme je connais ABC, je construis ABC. Puis, en l’utilisant, je me rapproche d’un résultat qui fonctionne mieux que tout ce que j’ai essayé jusque-là, et ça me motive. »
Pour des non-techniciens, une explication chargée d’émotion fonctionne très bien aussi. Ils sont peut-être plus habitués à penser en termes émotionnels, tandis que nous sommes plongés dans la logique de notre travail, et parfois dans les mathématiques. Il faut donc remettre de l’émotion dans l’explication.
Je l’ai expliqué ainsi à ma famille, et ils ont suivi et ont vraiment compris.
Dans l’article, il est dit que « dans un espace à 100 dimensions, sa méthode permet de remplir environ 100 fois plus de sphères, et dans un espace à un million de dimensions, environ un million de fois plus ». C’est un bon exemple de ce qui montre à quel point les espaces de grande dimension sont étranges.
Cela semble vouloir dire que, lorsque des gens intelligents ont essayé de mettre autant d’oranges à 100 dimensions que possible dans une boîte à 100 dimensions, jusqu’ici ils n’avaient même pas rempli 1 % de l’espace et, malgré des décennies de recherche, n’avaient pas trouvé où en placer une de plus.
Si l’on considère une n-sphère unité inscrite dans un hypercube unité, la proportion occupée par la sphère tend à disparaître à mesure que n augmente. À noter, chose étrange, que cette relation n’est pas monotone et atteint son maximum pour n=6.
Pour n=100, le volume de la 100-sphère unité est d’environ 10^-40, et il est évidemment impossible de placer une deuxième sphère dans cet hypercube. Il n’est donc pas si surprenant que les gains obtenus par une amélioration du remplissage puissent être aussi importants.
Beaucoup de gens disent pouvoir visualiser la 4D, mais je n’ai encore vu personne qui en soit réellement capable. Cela inclut beaucoup de mathématiciens, même si ceux qui font ce genre d’affirmation ne sont généralement pas des mathématiciens.
J’aime beaucoup l’animation[0] de ce billet sur Math Overflow, car elle contient beaucoup de complexité cachée à laquelle la plupart des gens ne pensent pas. Cette animation est en fait une illusion d’optique, et nous « hallucinons » ce que nous voyons. L’image du haut projette un cube sur un plan ? En réalité, ce n’est pas un cube. C’est déjà un cube projeté en 2D. Techniquement, c’est en 3D, mais la troisième dimension n’est pas une dimension spatiale : c’est la dimension temporelle. C’est en soi une bonne leçon pour apprendre l’abstraction des dimensions.
Nous hallucinons donc un cube en rotation, puis, après avoir vu sa projection sur un plan, nous l’hallucinons encore comme ayant de la profondeur plutôt que comme un carré non déformé. Rien que cela, c’est déjà assez étrange.
En réalité, nous avons aussi du mal avec l’imagination en 2D. La plupart des gens affirment pouvoir visualiser la 2D, et cette affirmation est rarement réfutée.
Si vous n’avez pas lu Flatland[1], je le recommande à tout le monde. Beaucoup de gens le lisent de travers. On le lit généralement comme une analogie abaissée d’une dimension : nous, êtres 3D, correspondons aux êtres 2D, et les êtres 4D nous sembleraient aussi déroutants que les êtres 3D le sont pour les habitants de Flatland. C’est juste, mais il y a un piège. Nous pensons que comprendre la 2D est très facile. Pourtant, je vous garantis que ce que vous imaginez en ce moment est faux. Honnêtement, le livre lui-même n’est pas parfaitement exact non plus.
Il faut vraiment se mettre à la place d’un habitant de Flatland. Pas celui du livre, mais un véritable habitant de Flatland. Si vous imaginez être un habitant carré de Flatland regardant un triangle, que verriez-vous ? Vous penserez probablement à une ligne, mais c’est faux. Vous lui avez donné une épaisseur et vous avez introduit une troisième dimension. Essayez encore, puis forcez-vous à ajouter davantage de profondeur pour imaginer le véritable Flatland : vous vous rendrez compte que vous n’y arrivez pas.
À la place, nous pouvons visualiser et raisonner sur un espace 2D intégré dans la 3D. On pourrait dire que je chipote, mais sinon il devrait être parfaitement acceptable de dire que ceci[2,3] n’est pas une représentation d’un hypercube 4D, mais un hypercube 4D.
Comprendre cela aide énormément, à mon avis, à appréhender les dimensions très élevées. Quand on se confronte à l’extrême difficulté de visualiser correctement l’ajout ou le retrait d’une seule dimension, on est moins susceptible de se tromper soi-même en raisonnant sur des dimensions beaucoup plus élevées.
Comme le disait Feynman, le premier principe est de ne pas se tromper soi-même, et la personne la plus facile à tromper, c’est soi-même.
[0] https://math.stackexchange.com/a/2286226
[1] http://www.geom.uiuc.edu/~banchoff/Flatland/
[2] [https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-s...](https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-simple.gif)
[3] Une bonne vidéo où Carl Sagan explique la projection 3D d’un hypercube, autrement dit son ombre. Quoi qu’on montre, cela doit nécessairement être intégré en 2D. Il le prend en main à partir de 6:20 https://www.youtube.com/watch?v=UnURElCzGc0
Intéressant. J’ai essayé pendant un mois d’utiliser une approche de remplissage par sphères pour créer un meilleur algorithme de compression.
J’avais beaucoup de vecteurs, regroupés par clustering, mais j’en ai conclu que l’approche théorique ne fonctionne correctement que sur des données uniformes et ne convient pas très bien aux données du monde réel.
Par exemple, supposons que les données aient une structure de grande dimension, mais soient localement uniformes. C’est fréquent, et cela vient de processus générateurs de bruit. Si l’on calcule et stocke des centroïdes, ils sont plus uniformes que les données d’origine et pas très nombreux, donc ce n’est de toute façon pas un gros problème.
Chaque vecteur est stocké sous forme d’un indice de centroïde et d’un décalage de vecteur. Ici, c’est du SoA, pas du AoS. Les indices peuvent être compressés avec la méthode entière à base d’entropie que vous préférez, et on peut faire encore mieux s’il n’est pas nécessaire de préserver l’ordre.
Les décalages, par hypothèse, sont désormais à peu près uniformes, ce qui permet d’utiliser la stratégie de sphères de votre choix dans la littérature.
Bien sûr, si les cas d’usage réels sont trop hétérogènes pour qu’une technique générale soit efficace, peut-être pas.
Les mathématiciens devraient pouvoir, quelques années après leur premier doctorat, obtenir un deuxième diplôme de niveau doctoral dans un domaine qui n’est pas exactement le leur, mais adjacent.
Beaucoup de chercheurs se reforment dans un domaine voisin, ou ajoutent de nouveaux centres d’intérêt de recherche, pendant leur postdoctorat ou après. À partir de ce moment-là, c’est simplement de la recherche.
Cela dit, dans l’environnement universitaire actuel, ce ne serait pas facile à faire.
Relier différents domaines des mathématiques, en particulier, peut être extrêmement puissant.
Au moins en Allemagne, cela ressemble assez à ce qui est décrit.
Pour une dimension donnée d, Klartag dit pouvoir remplir l’espace avec d fois plus de sphères que la plupart des résultats précédents.
Autrement dit, en dimension 100, cela ferait environ 100 fois plus de sphères, et en dimension un million, environ un million de fois plus ; cela paraît énorme. Est-ce que cela signifie que, dans divers systèmes de communication, la bande passante pourrait augmenter de plusieurs ordres de grandeur, ou que la consommation d’énergie pourrait baisser ?
Cela n’aide donc que pour des objets naturellement de grande dimension. Les objets numériques n’ont pas de dimension naturelle, c’est-à-dire de longueur en octets, donc on peut choisir une petite dimension.
https://en.m.wikipedia.org/wiki/Sphere_packing
Klartag n’est pas, de par sa formation, un spécialiste de l’empilement de sphères, mais il fait partie des tout meilleurs résolveurs de problèmes du moment.
Plus tôt cette année, il a résolu la conjecture de l’hyperplan, et il a contribué aux progrès sur des problèmes liés à la théorie de la convexité, comme la conjecture KLS, la conjecture de Mahler et le théorème central limite pour les corps convexes.
Les travaux de son étudiant Eldan sur la localisation stochastique (Stochastic Localization) se sont aussi révélés centraux pour les algorithmes d’échantillonnage log-concaves ; cela est lié à la conjecture KLS, et il a également donné une conférence à l’ICM.
De plus, les outils utilisés en géométrie convexe, en particulier certains outils d’analyse harmonique, sont aussi très utiles dans l’étude de l’empilement de sphères.
Il est donc difficile de parler de résultat « inattendu ».
Je suis d’accord avec Klartag pour dire que les formes convexes sont un outil mathématique sous-estimé. Je ne suis pas mathématicien, mais j’ai vu des algorithmes d’enveloppe convexe résoudre des problèmes dans des endroits totalement inattendus.
Par exemple, on n’aurait probablement pas imaginé utiliser un algorithme d’enveloppe convexe dans un article sur la décomposition automatique de palettes d’images.
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
Question de débutant : l’empilement de sphères optimal est-il corrélé à un réseau régulier ? N’est-ce pas le cas en 2D et en 3D ? Si oui, cela se généralise-t-il à n dimensions ?
Cela a été démontré en 2017 par Maryna Viazovska, avec des coauteurs pour le deuxième article. https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8
Ceci vaut aussi le détour : https://www.ams.org/journals/notices/201702/rnoti-p102.pdf
Dans les autres dimensions, c’est un problème ouvert, et il semble peu probable que ce soit vrai en général. Dans certaines dimensions, l’empilement non régulier le plus dense connu est plus dense que l’empilement régulier le plus dense connu.
Mais ils ont tous la même densité que le réseau FCC. On peut construire de tels empilements en faisant glisser horizontalement les couches horizontales du FCC les unes par rapport aux autres.
En dimension supérieure, on conjecture que l’empilement le plus dense sera toujours non réticulaire, parce que ces espaces n’ont pas assez de symétries.
Plus tôt aujourd’hui, il y avait un article disant que les Néandertaliens faisaient fondre de la graisse.
On y disait que les anthropologues ignoraient qu’il était possible de faire bouillir avant l’invention de la poterie, et aussi que les professeurs de sciences connaissaient cette possibilité parce qu’ils le font en cours.
Enfin, l’idée était que les mêmes choses peuvent être redécouvertes dans des domaines différents, comme quelqu’un qui étudiait le glucose et a redécouvert la formule des trapèzes pour l’intégration.
C’est encore un exemple où l’expertise d’un autre domaine peut aider.
Il suffit de regarder une seule vidéo YouTube montrant une méthode utilisée en situation de survie. Il doit y en avoir beaucoup du même genre : https://www.youtube.com/shorts/0zun_UxO2vU
Certes, je n’ai pas le contexte, mais une affirmation aussi surprenante sans source, ça ne tient pas. Elle ne passe même pas le « test du fou rire ».