Un nouveau record d’empilement de sphères venu d’une source inattendue

• Boaz Klartag a introduit des outils de géométrie convexe dans le problème de l’empilement de sphères en très haute dimension, à rebours des approches existantes
• La nouvelle méthode aléatoire de Klartag produit des ellipsoïdes de plus grand volume, mettant largement à jour les records précédents
• Cette approche permet d’empiler beaucoup plus de sphères dans les espaces de grande dimension
• Ce résultat relance le débat sur l’importance de l’ordre et de la symétrie dans l’empilement
• La recherche attire l’attention pour ses applications potentielles dans des domaines variés, notamment la cryptographie et les communications

---

Limites des recherches antérieures sur l’empilement de sphères

• L’avantage de la méthode de Rogers était qu’il n’était pas nécessaire que le réseau de départ soit efficace : il suffisait de choisir un ellipsoïde approprié
• Mais comme les axes de l’ellipsoïde peuvent se déformer de multiples façons en grande dimension, le nombre de choix sur la manière de le faire croître était excessif
• Par la suite, les mathématiciens sont revenus à l’approche de Minkowski en se concentrant sur le réseau lui-même, se spécialisant dans la théorie des réseaux et s’éloignant de l’approche géométrique de Rogers
• Cette stratégie a apporté des améliorations progressives pour l’empilement de sphères en haute dimension, mais seulement une hausse marginale d’efficacité par rapport à la méthode de Rogers
• Pendant des décennies, aucun grand bond en avant n’a eu lieu, et la situation est restée bloquée

Une innovation née d’un regard extérieur

• Boaz Klartag, du Weizmann Institute of Science, est à l’origine un spécialiste non pas de la théorie des réseaux, mais de la géométrie convexe
• Il s’intéressait depuis longtemps au problème de l’empilement de sphères, sans avoir eu l’occasion de l’étudier
• En 2023, disposant de plus de temps, il a organisé avec Barak Weiss de la Tel Aviv University un séminaire pour explorer de près la littérature classique (Minkowski, Rogers)
• Klartag a jugé que la méthode des ellipsoïdes de Rogers était inefficace par manque de savoir-faire dans la manipulation des formes convexes
• Il a acquis la conviction qu’en construisant des ellipsoïdes plus efficaces, il serait possible de battre le record de l’empilement de sphères

Introduction d’un algorithme de croissance aléatoire

• Klartag a appliqué sa propre méthode, qui consiste à dilater ou contracter aléatoirement la frontière de l’ellipsoïde selon chaque direction d’axe
• Lorsque la frontière touche un point du réseau, la croissance s’arrête dans cette direction, tandis qu’elle continue dans les autres
• Au cours de ce processus, l’ellipsoïde explore l’espace sous une forme irrégulière et grandit progressivement
• Comme le caractère aléatoire fait varier le volume d’un ellipsoïde à l’autre, il a fallu répéter l’expérience pour évaluer la possibilité d’obtenir des ellipsoïdes de plus grand volume
• En quelques semaines, il a démontré qu’on pouvait obtenir des ellipsoïdes plus grands que ceux de Rogers

Nouveau record et impact

• La nouvelle méthode par ellipsoïdes réalise la plus forte amélioration d’efficacité de l’empilement de sphères depuis Rogers (1947)
• Quand la dimension vaut d, elle permet d’empiler d fois plus de sphères que les méthodes précédentes
  • 100 dimensions → environ 100 fois plus, 1 000 000 de dimensions → environ 1 000 000 de fois plus
• Grâce à des intuitions venues de la géométrie convexe, Klartag a percé en quelques mois plusieurs problèmes centraux anciens sur les réseaux et l’empilement de sphères
• Son résultat remet en avant l’idée que des empilements fondés sur l’ordre et la symétrie peuvent atteindre les configurations les plus denses
• À l’inverse, des travaux récents soutiennent aussi qu’il faut exploiter le désordre sans réseau régulier

Évaluations et perspectives

• Au sein du monde académique, le débat porte encore sur le fait de savoir si la méthode de Klartag s’approche réellement de l’optimum ou s’il reste une marge d’amélioration
• La réponse à cette question est également cruciale pour des applications concrètes comme la cryptographie et les télécommunications
• La méthode n’en est pas encore au stade d’une application pratique, mais elle attire déjà l’attention comme nouvelle technologie dans les milieux de l’ingénierie
• Klartag espère que cette avancée renforcera les liens entre la géométrie convexe et la théorie des réseaux
• Il souhaite dépasser la séparation entre ces deux domaines et voir cette convergence s’étendre à la résolution de problèmes de réseaux autres que l’empilement

[GN⁺]

Avis sur Hacker News

• Aveu qu’il est toujours difficile d’expliquer à ses parents que son métier existe vraiment, et qu’il est encore plus embarrassant d’imaginer devoir dire : « J’étudie les formes, mais seulement celles qui n’ont pas de creux. »
  • Conclusion tirée de l’expérience : le mieux pour expliquer son métier est d’utiliser un jargon difficile. Trois options se dégagent : si l’on donne une explication relativement simple que ses parents peuvent comprendre, le travail paraît trop facile et on obtient une réaction du type « On te paie vraiment pour ça ? » ; si l’on explique correctement pourquoi c’est important, l’explication devient trop longue et les parents finissent par se lasser et regretter d’avoir posé la question ; sinon, on peut en parler brièvement avec des termes techniques compliqués, ils ne comprennent rien mais ça a l’air impressionnant, et c’est finalement la meilleure option
  • Quelqu’un raconte gérer une micro-entreprise qui fabrique des composants pour des équipements de physique des hautes énergies, et ne toujours pas avoir trouvé comment expliquer son travail aux autres, tant le sujet est extrêmement étrange, ultra-spécialisé, et à plusieurs degrés de distance de toute expérience du grand public ou de la vie quotidienne
  • « Je travaille avec des ordinateurs », c’est tout ce que dit une personne, ce qui a l’avantage pratique de clore la conversation avec un simple « Ah, d’accord, c’est bien »
  • Une autre personne explique que la vraie difficulté n’est pas tant la question « Tu fais quoi ? » que la suivante : « Et à quoi ça sert / où est-ce que ça s’utilise ? » ; le problème est de savoir comment expliquer de façon courte et efficace la longue chaîne qui relie la recherche fondamentale à des applications concrètes
  • Au moins, le sphere packing est étroitement lié à un problème central de la théorie de l’information, avec un contexte historique et une importance claire via son lien avec l’amélioration de la fiabilité du système Bell Telephone (pour les corps convexes, cette personne ne sait pas)
• Quelqu’un raconte avoir réfléchi à des algorithmes de compression de données vectorielles à l’aide du sphere packing ; l’approche théorique n’était efficace que lorsque les données étaient très uniformes, et s’appliquait mal aux données réelles
  • Pour transformer des données irrégulières (non uniformes) en données uniformes, l’astuce classique consiste à utiliser la connaissance du domaine pour réduire les asymétries ; par exemple, même si les données ont une structure de grande dimension, elles deviennent souvent assez uniformes localement à cause du bruit ; si l’on calcule et stocke des centroïdes, ceux-ci deviennent plus uniformes, puis chaque vecteur peut être stocké en séparant l’indice du centroïde et l’offset du vecteur ; l’indice se prête à une compression entropique efficace, et l’offset, désormais presque uniforme, se prête mieux à la stratégie classique de sphere packing
  • Cela a sans doute déjà été essayé, mais on suggère de tester si une précompression peut réduire la sparsité des vecteurs et améliorer leur uniformité
  • Remarque humoristique disant qu’il faut faire attention quand on manipule réellement des vecteurs (grope signifiant « tâtonner », faute de frappe pour group)
  • Mise en avant de la nécessité d’étendre la portée de la théorie à des problèmes plus pratiques, c’est-à-dire des données non homogènes ; si les cas d’usage réels sont trop variés, une approche générale sera peut-être difficile, mais cela mérite quand même d’élargir la recherche
  • Observation que, dans les vieux domaines à forte importance commerciale, la plupart des résultats faciles à obtenir ont déjà été cueillis
• Quelqu’un se dit d’accord avec l’affirmation de Klartag selon laquelle « les corps convexes sont très puissants et très utiles » et, sans être mathématicien, partage avoir souvent vu des algorithmes de convex hull apparaître dans des endroits inattendus, notamment pour la décomposition automatique de palette d’images, avec un lien vers l’article de référence Convex Hull and automatic palette decomposition
• La nouvelle méthode de sphere packing de Klartag permettrait, en dimension d, d’empiler d fois plus de sphères qu’auparavant : 100 fois plus en 100 dimensions, un million de fois plus en un million de dimensions ; quelqu’un se demande si cela signifie, dans divers systèmes de communication, une bande passante multipliée par plusieurs dizaines ou centaines, ou une forte baisse de la consommation électrique
  • En pratique, la densité se dégrade exponentiellement avec la dimension, en n^2/2^n, donc l’amélioration linéaire théorique ne se traduit pas intégralement en performances réelles ; autrement dit, cela peut être utile pour des données ayant naturellement une structure de grande dimension, mais pour des données numériques (dont on peut choisir la longueur), on peut prendre une petite dimension ; voir les détails sur le sphere packing dans ce lien Wikipédia
• Idée selon laquelle les mathématiciens devraient pouvoir obtenir un deuxième doctorat dans une discipline voisine, quelques années après le premier, plutôt que dans exactement le même domaine
  • Le but fondamental du doctorat étant de prouver sa capacité à mener des recherches de façon indépendante, beaucoup de chercheurs changent effectivement de domaine ou de sujet d’intérêt après leur thèse ; à partir de là, c’est la « recherche » elle-même qui devient centrale
  • Comme exemple réel, le célèbre mathématicien Bela Bollobas possède deux doctorats, l’un en géométrie discrète et l’autre en analyse fonctionnelle ; même si, dans le monde académique actuel, il serait très difficile de refaire cela
  • Si une telle flexibilité institutionnelle existait dans toute la science, les techniques et idées de différents domaines pourraient circuler plus rapidement, ce qui accélérerait potentiellement le progrès scientifique, avec un bénéfice particulièrement fort dans des disciplines comme les mathématiques où les liens entre sous-domaines sont importants
• Question de débutant : le sphere packing optimal est-il toujours associé à un réseau régulier ? C’est le cas en 2D et 3D, mais quelqu’un se demande si cela s’étend à la ND
  • Au-delà des dimensions 2 et 3, il existe aussi des cas prouvés où le meilleur packing est un réseau régulier, en dimension 8 (réseau E₈) et 24 (réseau de Leech) ; cela a été démontré en 2017 par Maryna Viazovska et ses collègues, avec des liens vers les articles et documents de référence : papier 1, papier 2, pdf explicatif ; mais dans d’autres dimensions, il peut exister des contre-exemples où le packing optimal n’est pas un réseau régulier, et dans certaines dimensions des formes irrégulières peuvent être plus denses
  • Pas nécessairement : même en 3D, en plus des empilements en lattice (réseau régulier), on peut obtenir une infinité d’empilements non réguliers en décalant horizontalement chaque couche ; ils ont pourtant la même densité que le réseau FCC ; en grande dimension, certains soupçonnent même que le packing optimal soit toujours non régulier faute de symétrie suffisante
• Question sur la dimension minimale à partir de laquelle cette nouvelle structure de sphere packing devient meilleure que les dimensions où les meilleures densités précédentes étaient déjà démontrées
• Suggestion d’une piste de développement : ces résultats pourraient-ils être utilisés en cryptographie et dans les communications pour concevoir des systèmes de communication réellement plus sûrs, plus fiables et plus sobres en énergie ? Domaine de recherche très intéressant
• Comparaison spirituelle mentionnant qu’en physique réelle, le « cow packing » (des recherches théoriques sur la manière de remplir l’espace avec des vaches à densité optimale, etc.) pourrait lui aussi avoir des applications pratiques
• Le sphere packing est fascinant parce qu’il réapparaît dans une très grande variété de problèmes appliqués ; quelqu’un dit attendre avec impatience une lecture approfondie de l’article