Empilements de sphères et codage de l’information

Le 5 octobre 2020  - Ecrit par  Clotilde Fermanian Kammerer Voir les commentaires

Maryna Viazovska, professeure à l’EPFL (École polytechnique fédérale de Lausanne), est la lauréate du prix Latsis 2020, prix accordé annuellement à des scientifiques en poste en Suisse. Coup d’œil sur les travaux de Marina Viazovska.

En 2016, Maryna Viazovska démontre que le réseau $E_8$ donne un empilement optimal de sphères en dimension 8, et une semaine plus tard, avec des collaborateurs, elle étend son résultat au réseau de Leech en dimension 24, complétant ainsi le programme initié par Kepler en 1611 lorsqu’il conjecture que l’empilement « de l’épicier » est le plus dense en dimension 3. Gauss démontre en 1831 que cet empilement est le plus dense parmi les empilements réguliers. En 1998, Hales obtient dans une preuve assistée par ordinateur qu’il n’existe pas d’empilement irrégulier plus dense que le fameux empilement d’orange que l’on trouve sur l’étalage de nos marchés.

Pourquoi passer de la dimension 3 à la dimension 8 ? La question de l’empilement des sphères en dimension plus grande que trois est délicate à visualiser. Une façon de le faire est de penser à la réalisation d’un empilement en 3 dimensions : on commence par un empilement plan (en deux dimensions) et on recommence par-dessus en décalant les oranges pour qu’elles soient dans les creux. On peut ensuite imaginer qu’on recommence le processus pour obtenir un empilement en 4 puis 5 dimensions. A chaque fois, entre les couches, il reste de l’espace. Or il se trouve que lorsque l’on passe de la dimension 7 à la dimension 8, cet espace est suffisamment grand pour qu’on puisse y rajouter une nouvelle orange. C’est ce qui rend spécial le cas de la dimension 8, et de la dimension 24. Pour ces deux cas, il y a des symétries surprenantes qui permettent des empilements particuliers appelés $E_8$ (en dimension 8) et réseau de Leech (en dimension 24). Et ces réseaux apparaissent dans différents domaines des mathématiques : théorie des nombres, combinatoire, géométrie hyperbolique, et même la théorie des cordes en physique, mais surtout l’algorithmique discrète. En effet, ils étaient déjà largement utilisés dans ce domaine, dans la construction de codes correcteurs, mais sans que l’on ait de preuve mathématique de leur supériorité. Maryna Viazovska a démontré que ces réseaux correspondaient à des empilements optimaux, alors que les seules preuves que l’on connaissait étaient assistées par ordinateur.

Mais pourquoi tout cela a-t-il un lien avec les codes correcteurs d’erreur ? Un code correcteur, c’est le petit logiciel qui corrige nos fautes lorsqu’on écrit un texto. Ce sont des codes permettant d’encoder des données même si elles sont brouillées. On les utilise pour les téléphones cellulaires, la transmission dans l’espace ou par Internet, et pour envoyer des signaux par des canaux brouillés. C’est exactement le rôle joué par l’alphabet Alpha, Bravo, Charlie… lorsqu’on l’utilise plutôt que d’épeler de façon classique. On remplace la donnée ponctuelle « A » par une donnée plus complexe « Alpha » pour laquelle il y a moins de source d’erreur : le récepteur corrigera « Bulpha » en « Alpha » car ce sera la donnée la plus proche.

Une donnée complexe peut être vue comme un point d’un espace de grande dimension, 100 par exemple. On va alors chercher à la remplacer par une sphère centrée en ce point et de rayon tel que ladite sphère contiendra toutes les déformations possibles qui pourraient arriver à cette donnée pendant la transmission. Bien sûr, plus la transmission est fiable, puis le rayon pourra être pris petit. La personne émettrice enverra juste au récepteur les coordonnées du centre de la sphère, si elle arrive modifiée, elle n’en restera pas moins dans la sphère et le récepteur identifiera la sphère et donc la donnée. Pour que le message puisse être décrypté de manière unique, il faut que les sphères soient disjointes, et on comprend alors l’importance de trouver des bons empilements de sphères : les seuls résultats disponibles sont en dimension 2, 3, 8 et 24 grâce au travaux respectifs de Gauss, Hales, Maryna Viazovska, et ses collaborateurs.

Question subsidiaire : s’il est maintenant démontré que $E_8$ et le réseau de Leech sont optimaux en termes de la densité de l’empilement de sphères qu’ils permettent, est-ce qu’ils sont optimaux en termes d’énergie, en considérant que ces sphères sont des atomes et contiennent des électrons qui se repoussent l’un l’autre selon la loi du carré inverse ? La question reste ouverte.

[Ref1] Why You Should Care about High-Dimensional Sphere Packing ? By Evelyn Lamb on July 29, 2016, Scientific American, Lien.

[Ref2] L’empilement des sphères en grande dimension résolu. Traduction par La recherche d’un article de Erica KLARREICH / Quantamagazine.org (lien vers le texte original sur le site de La Recherche), Lien.

Partager cet article

Pour citer cet article :

Clotilde Fermanian Kammerer — «Empilements de sphères et codage de l’information» — Images des Mathématiques, CNRS, 2020

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?