David Madore's WebLog: Notes sur les réseaux euclidiens, et le réseau de Leech

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2299 [older|newer] / Entrée #2299 [précédente|suivante]:

(lundi)

Notes sur les réseaux euclidiens, et le réseau de Leech

Je mets ici les transparents d'un exposé que j'ai donné vendredi matin dans le cadre d'une journée Télécom-UPS (Le Numérique pour tous) s'adressant aux professeurs de classes préparatoires : le sujet que j'ai évoqué était celui des réseaux euclidiens[#] et de leurs applications en cryptographie. Comme j'ai moi-même appris plein de choses en préparant cet exposé (entre autres en me plongeant un peu plus que je ne l'avais fait jusqu'alors dans le célèbre livre Sphere Packings, Lattices and Groups des deux mathémagiciens John Conway et Neil Sloane), je n'ai pas résisté à partir un peu dans tous les sens, et forcément j'avais beaucoup plus de choses sur mes planches que je ne pouvais en exposer en une heure : inversement, j'espère que leur lecture peut être intéressante sans l'exposé oral pour les accompagner.

Je n'ai notamment pas pu m'empêcher d'évoquer (le réseau) E₈, même s'il n'a aucun rapport avec la crypto dont j'étais censé parler. Ce qui me fait penser que si j'ai beaucoup parlé de E₈ sur ce blog, soit de l'algèbre ou du groupe de Lie de ce nom, soit du système de racines qui le définit, je n'ai pas vraiment parlé du réseau E₈ (celui engendré par le système de racines), qui est pourtant un objet plus simple (dans sa définition sans doute la plus compacte, c'est l'ensemble {(x₁,…,x₈) ∈ (ℤ⁸∪(ℤ+½)⁸) : x₁+⋯+x₈ ∈ 2ℤ} des octuplets de réels soit tous entiers soit tous ½+entiers, et dont la somme est un entier pair) ; et je n'ai jamais parlé du réseau de Leech de dimension 24 (qui est pourtant presque aussi ubiquiste dans les mathématiques que E₈, et peut-être encore plus exceptionnel). Voici une façon concise (mais peu constructive) de caractériser ces deux objets : si vous vivez dans un espace de dimension 8 (resp. 24) et que vous cherchez à empiler des boules toutes identiques, vous remarquerez qu'il y a une unique façon de mettre le nombre maximum de boules autour d'une boule centrale de façon à ce qu'elle la touchent toutes, à savoir 240 d'entre elles (resp. 196560), et de plus, une fois réalisé ce motif, il se continue de façon périodique (chaque boule ayant toujours ce même nombre maximum de voisines) ; en regardant le centre des boules, vous avez ainsi réalisé le réseau E₈ (resp. le réseau de Leech ou son symétrique). À part en dimension 2 où on obtient facilement le réseau hexagonal par la même construction (en disposant six cercles identiques autour d'un septième qu'ils touchent tous), les dimensions 8 et 24 sont exceptionnelles, au moins parmi celles qu'on connaît (j'ignore si on sait dire quelque chose sur les dimensions telles que l'arrangement maximal de boules identiques autour d'une boule centrale soit unique et engendre de plus un réseau, mais il n'y en a pas d'autre que 2,8,24 en dimension ≤24, et pas d'autre connue : dans les autres dimensions, les boules ne sont pas du tout rigides — par exemple, en dimension 3, on peut placer au maximum 12 boules identiques touchant une autre donnée, mais il y a beaucoup de façons de le faire, et elles peuvent se déplacer tout en gardant le contact avec la boule centrale).

Ceci étant, si les questions d'empilement de sphère sont frappantes, elles ne permettent pas vraiment de travailler avec le réseau de Leech. Sur le modèle de la définition que j'ai donnée ci-dessus du réseau E₈ (les octuplets de réels, soit tous entiers soit tous ½+entiers, dont la somme est un entier pair), voici la façon la plus simple et constructive que je connaisse de définir le réseau de Leech. Comme il vit en 24 dimensions, il y a 24 coordonnées à donner, et je disposerai ces 24 coordonnées sur les sommets d'un icosaèdre régulier (rappelons qu'un icosaèdre régulier a 12 sommets), deux par sommet, que j'appellerai arbitrairement la coordonnéee rouge et la coordonnée bleue (pour ce sommet). Le réseau de Leech est formé des points dont les coordonnées multipliées par √8 sont 24-uplet d'entiers vérifiant les conditions suivantes : (0) les bits 0 (=bits de poids faible) de ces 24 entiers sont tous les mêmes (i.e., ils sont soit tous pairs, soit tous impairs), (1) le bit 1 de l'entier rouge sur chaque sommet de l'icosaèdre est égal au XOR des bits 1 des entiers bleus des sommets qui ne sont pas adjacents à lui [la même chose est alors automatiquement vraie en échangeant bleue et rouge, et cette condition est une façon de dire que les bits 1 forment un mot du code de Golay binaire (24,12,8)], et enfin (2) le XOR des bits 2 de tous les entiers est égal à leur bit 0 commun [on a déjà dit que les bits 0 sont tous les mêmes]. (Note : le facteur √8 est un simple facteur de normalisation. Il a pour but d'assurer que le réseau de Leech a un covolume — c'est-à-dire la valeur absolue du déterminant d'une base — égal à 1, et alors les produits scalaires de deux vecteurs quelconques sont toujours entiers.)

±?/√8±?/√8±?/√8±?/√8±?/√8±?/√8
±?/√8±?/√8±?/√8±?/√8±?/√8±?/√8
±?/√8±?/√8±?/√8±?/√8±?/√8±?/√8
±?/√8±?/√8±?/√8±?/√8±?/√8±?/√8

Le tableau ci-contre, si mon JavaScript est bien fait, est censé afficher des vecteurs aléatoires de la plus petite longueur non nulle (à savoir 2) uniformément choisis parmi les 196560 possibles dans le réseau de Leech (qui est engendré par eux, c'est-à-dire, est l'ensemble de toutes les combinaisons entières de ces vecteurs) ; j'ai laissé non simplifiées des expressions comme 2/√8 (ou 4/√8, qui apparaît très rarement) pour mieux coller avec la présentation que je viens de donner. Ici, les coordonnées ont été disposées en tableau 6×4 parce que c'est plus commode à mettre sur une page Web qu'un icosaèdre avec deux coordonnées par sommet : si on veut faire le lien entre ces deux présentations, on peut reprendre l'étiquetage des cases que j'avais utilisée dans une entrée récente, et qui est rappelée en attributs title (i.e., si on passe la souris au-dessus d'une case), et les disposer sur un icosaèdre de la façon suivante : en appelant un premier sommet, les cinq sommets adjacents s'appelleront cycliquement , et les six sommets opposés aux six que je viens de nommer seront et respectivement (à chaque fois, les deux étiquettes que je donne servent à définir la coordonnée « rouge » et la coordonnée « bleue » au sommet en question de l'icosaèdre).

Mais bon, il y a quantité de manières de décrire ou de construire le réseau de Leech (dans un seul chapitre du livre précédemment mentionné — le chapitre 24, et je soupçonne d'ailleurs que le numéro n'est pas un hasard —, Conway et Sloane donnent d'ailleurs 23 constructions différentes, une pour chacun des types de trous profonds [sic] du réseau). C'est un des signes qu'il s'agit d'un objet mathématique riche et extraordinaire qu'il y ait tellement de façons de le décrire. En voici une autre : on considère d'abord le réseau appelé II25,1 (dans l'espace Minkowskien de dimension 25+1) dont les points sont (exactement comme pour ma description de E₈ ci-dessus) les 26-uplets de réels, soit tous entiers soit tous ½+entiers, dont la somme est un entier pair ; dans ce réseau, on considère le vecteur v = (0,1,2,3,…,24|70), qui, vu que 70² = 0² + 1² + ⋯ + 24², est orthogonal à lui-même pour le produit scalaire Minkowskien ; on considère alors les vecteurs de II25,1 qui sont orthogonaux à v (c'est-à-dire que la somme des 25 premières coordonnées multipliées par 0,1,2,3,…,24 respectivement, est égale à la dernière multipliée par 70), modulo v lui-même : le réseau ainsi formé est isométrique au réseau de Leech. Ou, pour parler en physicien, on se place dans un espace-temps de relativité restreinte avec 25 dimensions d'espace et 1 de temps, on considère un photon qui se déplace à la vitesse (0/70, 1/70, …, 24/70), et le réseau très simple II25,1, vu par ce photon (dans l'espace perpendiculaire à son déplacement) est le réseau de Leech. Le passage entre cette description et la précédente, cependant, n'est pas évident.

[#] La terminologie prête vraiment à confusion, parce que le mot français réseau correspond à la fois à l'anglais network et lattice, et c'est du second qu'il est question. Mais l'anglais n'est pas moins ambigu, puisque lattice correspond à la fois au français réseau et treillis. Il ne reste plus qu'à inventer une quatrième sorte d'objet, qui s'appellerait treillis en français et network en anglais, et on aura un beau graphe bipartite complet K(2,2) dans les traductions.

↑Entry #2299 [older|newer] / ↑Entrée #2299 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées