/*a David-Olivier Jaquet ENUMERATION COMPLETE DES CLASSES DE FORMES PARFAITES EN DIMENSION 7 Thèse de doctorat ENUMERATION COMPLETE DES CLASSES DE FORMES PARFAITES EN DIMENSION 7 Thèse de doctorat de David-Olivier Jaquet, effectuée sous la direction du Professeur François Sigrist, à l'Institut de Mathématiques et d'Informatique de l'Université de Neuchâtel. L'examen de soutenance de thèse a eu lieu en présence des professeurs François Sigrist, professeur à l'Université de Neuchâtel, directeur de thèse, Ulrich Suter, professeur à l'Université de Neuchâtel, Jacques Martinet, professeur à l'Université de Bordeaux I, Joseph Ocsterlé, professeur à l'Institut Poincaré (Paris VI). 4 IMPRIMATUR POUR LA THESE ..£nufD.ératlQfì....Cflfflpl.ète...de.s....c.U.s.s.e.s....de....f.o.nnes...... ..Ra.rfa.it.es...en...d.im.e.n.s.lo.n....7............................................................ de MPPli.eu.r..Day.id-01.1yler...Jaquet.. UNIVERSITE DE NEUCHATEL FACULTÉ DES SCIENCES La Faculté des sciences de l'Université de Neuchâtel sur le rapport des membres du jury, Wi «... les... prpfes.seurs...E....S.i.g.ri.s.t;.3....U..,....S.u.ter............. ..J.,.....M.artJ.net....(ß.or.d.e.a.ux).....et..J......O.es.ter.l.e...(.P.a.r.i.s.) autorise l'impression de la présente thèse. Neuchâtel, le .....Tß Juin 1991............................................................. Le doyen : Cl. Mermod A Daphne Avant-propos Fruit de plusieurs années deformation, résultat de recherches personnelles, une thèse de doctorat est tout à la fois une étape importante et un nouveau départ. J'aimerais remercier aujourd'hui tous ceux qui m'ont accompagné durant cette période enrichissante, tous ceux qui, directement ou indirectement, m'ont permis de réaliser ma thèse de doctorat, soit par les connaissances qu'ils m'ont permis d'acquérir, soit par le soutien qu'ils m'ont apporté, soit par l'enthousiasme qu'ils ont su me transmettre. Mes remerciements s'adressent tout particulièrement à mon directeur de thèse, Monsieur François Sigrist, professeur à l'Université de Neuchâtel. François Sigrist a toujours manifesté à mon égard une très grande disponibilité. Je désire lui faire part ici de ma reconnaissance pour ses conseils, ses suggestions et son précieux soutien. Les échanges d'idées que j'ai eu la chance de partager avec lui représentent, pour moi, un apport essentiel. Je remercie également les trois experts, Messieurs les Professeurs Suter de Neuchâtel, Martinet de Bordeaux et Oesterlé de Paris. Les contacts avec chacun d'eux ont été très enrichissants. L'équipe du Centre de calcul de l'Université de Neuchâtel, son directeur Monsieur Randoald Corfu et, en particulier, Monsieur Jean-Pierre Maradan ont ap- porté, par leur compétence, un soutien technique indispensable. Ma gratitude s'adresse tout spécialement à mes parents qui n'ont cessé de me stimuler tout au long de mes études. 6 Finalement, j'aimerais faire un clin d'oeil à Daphne qui a partagé avec moi, de l'intérieur, toute l'élaboration de ma thèse, dans ses moments d'incertitude, comme dans les instants privilégiés qui suivent une découverte. Neuchûtel, juin 1991. INTRODUCTION 7 1. Introduction : La classification des formes parfaites en dimension inférieure à sept est un pro- blème résolu depuis plus de trente ans. En 1831 déjà, Gauss montre que le réseau cu- bique à faces centrées est l'unique réseau absolument extrême en dimension trois. Dans cette dimension, toute forme parfaite est équivalente à A3; il n'existe donc qu'une seule classe de formes parfaites et ces formes sont absolument extrêmes. Pour les di- mensions quatre et cinq, il faut attendre les travaux de Korkine et Zolotareff en 1877. En dimension quatre, on observe deux classes de formes parfaites (A4 et D4). En di- mension cinq, leur nombre s'élève à trois. Quatre-vingts années plus tard, en 1957, Barnes démontre qu'il n'y a que sept classes de formes parfaites à six variables, dont une qui n'est pas extrême, conformément à ce que pensait Voronoï. A la fin de son ar- ticle, Barnes prévoit que ses méthodes ne permettront certainement pas de traiter la di- mension sept, vu la complexité du problème [Ba 3]. La démonstration de Bames se base sur le seul algorithme général qui garantit l'énumération complète des classes de formes parfaites en dimension n, à savoir le fa- meux algorithme de Voronoï [ Vo 1 ]. Sa complexité croît si rapidement en fonction de la dimension, que seule l'utilisation d'ordinateurs permettait d'espérer pouvoir appli- quer cet algorithme à la dimension sept En 1963, Scott tente de traiter certaines formes, en dimension" sept, à l'aide de méthodes semblables à celles de Barnes, afin d'appliquer l'algorithme de Voronoï [Sc 1 ]. Il y réussit partiellement, mais ses résultats contiennent des erreurs. Jusqu'en 1971, on ne connaît que vingt-deux classes de formes parfaites à sept variables. Les travaux de Stacey permettent d'en découvrir onze nouvelles. Ces travaux sont basés sur des théorèmes de Watson. En fait, Stacey génère un grand nombre de formes par- faites. Mais elle n'arrive pas à décider si deux formes données sont équivalentes ou non. Pour effectuer un tri, elle considère un système de trois invariants; lorsque deux formes coïncident sur ces invariants, elle n'en retient qu'une. La liste obtenue par Stacey fut considérée comme très vraisemblablement ex- haustive. Mais rien ne permettait d'exclure, à priori, que deux formés parfaites non équivalentes coïncident sur ce système de trois invariants. Dès lors, le problème fut de montrer que cette liste de trente-trois formes était effectivement exhaustive. Dans un article paru en 1988, Conway et Sloane affirment que seules vingt-sept de ces formes ont été traitées dans l'optique de Voronoï et ils qualifient ces résultats d'incertains [CS 2]. Mes programmes, écrits en LISP, m'ont permis de traiter dans un premier temps trente-deux de ces trente-trois formes (pour D7, cf [JS I]). Une version plus complexe, que j'ai développée ultérieurement, a rendu possible le traite- ment de la dernière, à savoir E7. 8 FORMES PARFAITES A SEPT VARIABLES Mes travaux, comme ceux de Barnes, se basent sur l'algorithme de Voronoï. Par contre, les méthodes utilisées pour caractériser les faces d'un domaine sont entière- ment nouvelles. Voronoï, dans son étude générale de Dn, emploie certaines astuces très particu- lières qui permettent d'exhiber une liste suffisante de faces. De même, les travaux de Barnes contiennent très souvent des astuces de ce genre qui, dans un certain sens, lo- calisent le problème et, par conséquent, le simplifient. Dans sa version la plus com- plexe, mon programme automatise, d'un certain point de vue, cette découverte d'astuces particulières. Ces mêmes programmes, appliqués aux dimensions inférieures à sept, m'ont permis, entre autre, de confirmer très rapidement les résultats de Barnes et de donner une description plus détaillée de la manière dont s'imbriquent les domaines de Voronoï. En particulier - et ceci est un résultat nouveau - le domaine associé à Eo pos- sède exactement 38 124 faces qui se répartissent, conformément aux résultats de Barnes, en 11 orbites sous l'action du groupe des automorphismes de E&. L'ordinateur utilisé, une VAX 8530, a travaillé pendant environ cent vingt jours "CPU" pour traiter complètement la dimension sept. Les résultats de ces calculs dé- montrent le théorème suivant : Théorème : // n'existe que trente-trois classes deformes parfaites à sept variables. On notera, au passage, que ces calculs ont permis de décrire complètement le domaine associé à E7; ce domaine possède exactement 79 900 912 faces qui se répar- tissent en 157 orbites sous l'action du groupe des automorphismes de E7. Mes recherches avaient pour but - et le but est atteint - la classification des formes parfaites à sept variables. Quelles sont les motivations d'une telle classifica- tion? Toute forme extrême étant parfaite, on déduit de la connaissance des classes de formes parfaites dans une dimension, celle des classes de formes extrêmes, donc des réseaux les plus denses. En particulier, cela permet de calculer la valeur exacte de yn. Si l'on possède une description détaillée du domaine de Voronoï associé à chaque représentant des classes de formes parfaites, on en déduit un algorithme géné- ral de réduction des formes quadratiques définies positives, algorithme décrit précisé- ment par Voronoï. DEFINITIONS 9 2. Definitions : Soit E, un espace vectoriel réel de dimension n, muni d'un produit scalaire <• I •> et q : IR n----» R, une forme quadratique définie positive. A isometric près, il existe une unique base de E pour laquelle q soit l'application "norme au carré", c'est- à-dire pour laquelle le diagramme suivant soit commutatif : base où 9&v) = . fig. I Si Q représente la matrice de Gram de cette base, VxeRn, q(x) = xl Q x; on dira que le réseau engendré par les vecteurs de cette base est un réseau associé à q. Si une autre base de E engendre le même réseau, la matrice S de changement de base appartient à GLn(Z). Deux réseaux sont équivalents s'ils sont semblables (équivalence "naturelle"). Les réseaux de E associés à q étant isométriques sont donc équivalents. On en déduit une relation d'équivalence entre formes quadratiques définies positives, compatible avec l'équivalence entre réseaux : deux formes q et q' sont équivalentes s'il existe SeGLn(Z), telle que q soit positivement proportionnelle à q'°S. Ainsi, on obtient une bijection entre classes de formes quadratiques définies positives et classes de réseaux. Par définition, le minimum de q (et de Q) est : min q = min q(x) = min x'Q x = min Q où xeZn, x*0. Les paires de vecteurs ±veZn vérifiant q(v) = minq sont appelées paires de vecteurs minimaux de q (et de Q). Géométriquement, les vecteurs minimaux de q cor- respondent aux points d'un réseau associé à q, les plus proches de l'origine. Le nombre dise q = det Q est appelé discriminant de a. La racine de dise q est égale au volume d'une maille d'un réseau associé à q. On définit l'application suivante, dite invariant d'Hermite : ,i:q,— ,Kq)=JSiHiL. V dise q \i est invariante sur les classes de formes quadratiques définies positives; elle est directement liée à la densité des empilements de sphères associés aux réseaux. 10 FORMES PARFAITES A SEPT VARIABLES On définit yn, appelée constante d'Hermite. par yn = sup ji(q), lorsque q varie dans l'ensemble des formes quadratiques définies positives à n variables. On démontre que n atteint ses maxima; en particulier, la valeur de yn est atteinte. Les formes quadratiques définies positives correspondant aux maxima locaux de la fonction |i sont dites extrêmes, celles qui vérifient n(q) = yn, absolument extrêmes. Une forme quadratique définie positive est dite parfaite si elle est entièrement ca- ractérisée par la valeur de son minimum et l'ensemble de ses vecteurs minimaux. Considérons maintenant l'espace des formes quadratiques, définies ou non, à n variables. Cet espace vectoriel est isomorphe à Symn(R) qui, muni du produit scalaire (X,Y) i—> trace (XY), est un espace euclidien de dimension N = "^2+ ' : l'espace de Voronoï, noté V. Soit q une forme parfaite, indiçons ses paires de vecteurs minimaux : ±Vk, k = 1.....s. A chaque paire ±vk correspond une forme quadratique positive qk(x) : qic : x i—» qic(x) = (vkl x)2, et donc un point v^v^' dans l'espace de Voronoï. Appelons dk la demi-droite, issue de l'origine et passant par vkVk1. L'enveloppe con- vexe des dk est un cône convexe appelé domaine de Voronoï associé à q (et à Q). On appelle face du domaine tout cône convexe de codimension 1 obtenu en inter- sectant le domaine avec un de ses hyperplans d'appui. Plus généralement, une d-face sera un cône convexe de dimension d â l obtenu en intersectant des faces du domaine. Les 1-faces sont les arêtes du domaine. Si q(x) = x'Q x, on définit qad par qad : x i—> qad(x) = x'Qad x où Q/"1 est la matrice adjointe de Q. On dira que q est eutactique si qad peut s'exprimer comme combinaison linéaire à coefficients strictement positifs des qk. Géométriquement, si q est parfaite, cela revient à demander que Q3*1 soit un point intérieur du domaine associé àq. Voronoï démontre un critère, maintenant classique, pour les formes extrêmes : une forme quadratique définie positive est extrême si et seulement si elle est parfaite et eutactique. FONCTION D'HERMITE 11 3. La fonction d'Hermite \i : La recherche des réseaux les plus denses en dimension n revient à caractériser les maxima de la fonction |i. Pour n fixé, la fonction (X est bornée; Minkowski a mon- tré, par exemple, que pour n donné supérieur à l, Yn est inférieur à n. Il emploie pour cela des méthodes liées à la géométrie des nombres. On démontre que, modulo les homothéties, les maxima de n sont isolés et, qu'à équivalence près, il n'y a qu'un nombre fini de formes extrêmes. Historiquement, c'est la recherche de ces classes de formes extrêmes qui a introduit la notion de formes parfaites. La classification des formes extrêmes fut ramenée à la classification des formes parfaites. On ne connaît les valeurs exactes de Yn que pour n £ 8 : Yi = l Y2 = y \ Y3 = Va. Y4 = V~2 5 6 /------ 7 75 = Vi Y6 = y J- Y7 = VÌ4 Y8 = 2 Les valeurs de Y6. Y7 et Ys furent déterminées par Blichfeldt, voici près de soixante ans : y6 en 1925, y7 en 1929 et Ys en 1935 [Bl 1, 2, 3]. En 1944, Mordell montra à l'aide de l'inégalité qui porte son nom que, de la connaissance de fj, on peut déduire celle de Yg [MoI]. En 1966, Watson annonça qu'il était capable de vérifier les calculs de Blichfeldt... et démontra l'unicité des formes absolument extrêmes en dimension 6,7 et8 [WaI]. Plus récemment, en 1980, Vetchinkin confirma les résultats de Blichfeldt et de Watson dans un article très détaillé [ Ve 1 ]. L'énumération complète des classes de formes parfaites à sept variables a pour corollaire une confirmation immédiate des valeurs de Y7 et Y8- 12 FORMES PARFAITES A SEPT VARIABLES 4. Généralités sur les convexes : 4.1. Propriétés fondamentales : Soit E un espace euclidien et li,..., I1 des vecteurs de E. On définit C - cône convexe de E - par C = {xeE I li«x ä 0, i = l,..., t). Théorème 1 : C est une variété de dimension maximale dans E si et seulement si les /,• sont Ii- t néairement positivement indépendants, c'est-à-dire si 2^Pi '< = °> avec Pi ^ °> implique pi = 0 pour tout i. Théorème 2 : Supposons C de dimension maximale; après élimination éventuelle des Ii pouvant s'exprimer comme combinaison linéaire positive des autres Ij (jri), ceux qui restent définissent les hyperplans d'appui de C qui contiennent les faces de C1 cônes convexes de codimension 1. Théorème 3 : Supposons C de dimension maximale. Si (it'X = 0 Vi => x - 0), alors C est un cône convexe saillant; il possède des arêtes (représentées par ai, ai,—, as), et tout point de C peut s'exprimer comme combinaison linéaire positive des <%, s c'est-à-dire : C = {xeE Ix= Xp* ak. Pk Z 0}. k=i On trouvera dans la littérature diverses démonstrations de ces trois théorèmes classiques à propos des cônes convexes. Dans ce qui suit, on supposera toujours que C satisfait les hypothèses des théorèmes 2 et 3. Si 71, d'équation Ux = 0, contient une face de C, le théorème 3 garantit que K est l'enveloppe linéaire des représentants des arêtes de C qu'il contient. Il existe donc J, un ensemble d'indices, qui dépend de Tt, tel que les conditions suivantes (*) définis- sent 1 à un facteur positif près : (*) l«aj = 0 sijeJ et l.ajâO sinon. Inversement, s'il existe J, un ensemble d'indices tel que les conditions (*) défi- nissent 1 à un facteur positif près, l'hyperplan d'équation hx = 0 est un hyperplan d'appui qui contient une face de C. GENERALITES SUR LES CONVEXES 13 En effet, en appliquant le théorème 3, on constate que pour tout x appartenant à C, Lx ^ 0; d'autre part, il est clair, sous ces conditions, que l'ensemble des xeC vé- rifiant l«x = 0 est de dimension maximale dans cet hyperplan. On appellera facette d'un cône convexe saillant de dimension maximale toute face ou d-face de ce cône. Soit Fi, une facette de C : Fj = n Fj où i parcourt l'ensemble d'indices I. Appe- lons Ei le plus petit sous-espace de E contenant Fi. Dans Ei, Fj est un cône de dimen- sion maximale. Cela a donc un sens de parler des facettes de Fj. Montrons que Fi C Ei satisfait les hypothèses du théorème 3. Décomposons E en somme directe de Ei et de Ei-1-. Tout vecteur Ij s'écrit de fa- çon unique comme somme de I/eEi et de Ij^eEi-1-. Par construction, Fi= (xeE I lj«x = 0 siielet lj«x>0). Comme Fi est de dimension maximale dans Ei, si i est dans I, l;«x vaut 0 pour tout x dans Ei. Par conséquent, Fi = {xeEi | Ij.x > 0} = {xeEi I Ij1 »x â 0}. Après élimination des l^1 nuls, ou pouvant s'exprimer comme combinaison li- néaire positive des autres Ij1 (j*k), on trouve un ensemble d'indices J minimal, non- vide, disjoint de I, qui caractérise Fi : Fi= {xgEi I ljl.xâ0,jej} = {xeEi I lj.xâ O1JeJJ. Pour montrer que Fi c: Ei satisfait les hypothèses du théorème 3, il suffit de remarquer que, si un point x de Ei satisfait Ij.x = 0, VjeJ, ce même point considéré comme point de E satisfait alors l;.x = 0 Vi et, par conséquent, vaut 0. La relation "être une facette de" est une relation transitive. Plus précisément : Lemme ï : Toute facette de F/ est une facette de C. Lemme 2 : Toute facette de C strictement contenue dans Fj est une facette de F/. Les démonstrations sont pour ainsi dire triviales. Corollaire : Toute facette de C est entièrement caractérisée par la liste des arêtes de C qu'elle contient. Les arêtes d'une telle facette sont exactement les arêtes de C qu'elle contient; elle en est l'enveloppe convexe. Toute arête de C s'obtient en intersectant des faces de C. 14 FORMES PARFAITES A SEPT VARIABLES Soit a, un vecteur représentant une arête de C; il existe I, un ensemble d'indices tel que : {xeE | x = p a, p > 0) = n Fj avec iel. Cela revient à dire que les condi- tions lj«x=0 si iel et lj«x£0 Vj définissent le vecteur a à un facteur positif près. Lemme 3 : Un représentant d'une arête de C ne peut jamais s'exprimer comme combinaison linéaire positive des représentants des autres arêtes de C. Démonstration : Soit a, un représentant d'une arête de C. En temps que point de C, a peut s'exprimer comme combinaison linéaire positive des représentants de toutes les arêtes de C (théorème 3). En utilisant le fait que les conditions lj»x = 0 si iel et lj»x k 0 Vj définissent a à un facteur positif près, il est facile de voir que le seul coefficient non nul de cette combinaison linéaire est le coefficient devant a. ? L. 3 Lemme 4 : Tout point intérieur de C (resp. d'une facette de C) peut s'exprimer comme combinaison linéaire strictement positive des représentants des arêtes de C (resp. de cette facette). Démonstration : Soit x, un point intérieur de C (resp. d'une facette de C) et a;, iel, les représen- tants des arêtes de C (resp. de cette facette de C). Si \>û est suffisamment petit, x' = x-X.£ai appartient à C (resp. à cette fa- Ul cette de C) et peut s'exprimer comme combinaison linéaire positive des a,. On en conclut que x = x' + X £aj s'exprime comme combinaison linéaire strictement Ui positive des a;, iel. ' ? L. 4 4.2. Relèvement d'un cône saillant : 4.2.1. Définitions et nronriétés fondamentales : Considérons un cône convexe saillant C, de dimension d, dans un espace eucli- dien E de dimension s (s £ d). On supposera C donné par A = (ai, a2,..., as) où aj est un vecteur représentant la i6"10 arête de C. Après renumérotation éventuelle, on peut supposer ai, H2,..., ad linéairement indépendants. GENERALITES SUR LES CONVEXES 15 Notons Ed, l'enveloppe linéaire des a;. Ed est un sous-espace de dimension d de l'espace euclidien E. Construisons, maintenant, une suite d'espaces euclidiens emboî- tés Ed C Ed+1 C... CES = E, telle que Ek soit de dimension k et s'obtienne par ad- jonction à Ek_1 d'un vecteur e^ JL Ek_1. Pour tout entier k, d < k < s, on définit l'application rk : î* : A -------> Ek a; i-------> a; si 1 £ i 5 s+d-k; a; + es+d+i-i si i > s+d-k. Pour simplifier les notations, posons ajk = rk(aj) et Ak = rk(A). Ainsi : Ad = A Ad+1 = {ai, a2>..., as.!, as+ed+i} Ad+2 = Ja1, a2,..., as.i+ ed+2, as+ ed+i} etc. As = {ai, a2,..., ad, ad+i+es, ad+2+es-i,..., as.!+ed+2, as+ed+i) Dans Ek, définissons maintenant Ck, l'enveloppe convexe des demi-droites is- sues de l'origine, caractérisées par les éléments de Ak. Observons d'abord que les éléments de Ak sont linéairement positivement indépendants puisque les éléments de A le sont. En s'inspirant de la démonstration de Voronoï qui, utilisant la notion de domaine corrélatifs, montre que les arêtes d'un domaine associé à une forme parfaite sont parmi les demi-droites dont on prend l'enveloppe convexe, nous allons vérifier que Ck est un cône convexe saillant dont les arêtes sont exactement caractérisées par les éléments de Ak. . Démonstration : Soit R = { xeEk I aik»x S: 0, Vi}. Par le théorème 1, comme les a;k sont linéai- rement positivement indépendants, R est de dimension maximale. Montrons que R satisfait aussi les hypothèses du théorème 3, c'est-à-dire si xeEk satisfait aik«x = 0, Vi, x est nul. Pour cela, décomposons Ek en somme directe de Ed et de son complémentaire orthogonal. On écrira x sous la forme x = xd + x-1-, avec Xd appartenant à Ed et x-1- à son complémentaire orthogonal. Par construction, les ajk (1 5 j S d) appar- tiennent à Ed et satisfont ajk = ay Par conséquent, pour j compris entre 1 et d, l'égalité ajk»x = 0 implique aj«xd = 0. Comme, par hypothèse, les aj (l < j < d) forment une base de Ed, on en déduit Xd = 0, ou encore x = x-k Mais x1 peut s'exprimer comme combinaison linéaire des ei (d+1 £ i S k). k Donc, x1= Zyiei avec ei i.ej si i*j. i=d+l 16 FORMES PARFAITES A SEPT VARIABLES Choisissons j tel que s+d-k < j ^ s. Par construction, ajk = aj + es+d+i-j- Dans ce cas, l'égalité ajk»x = 0 implique ys+d+i-j = 0. En observant que la condition s+d-k < j < s équivaut à k+1 > s+d+l-j 2 d+1, on conclut que yj = 0 (d+1 S i S k) et, finalement, que x = 0. En appliquant le théorème 3 à R, on déduit que R possède des arêtes. Si l'on re- t présente ces arêtes par Ij, I2,..., h, on a R = { xeEk | x = £pj 1,, p, > 0}. i=l Définissons R' le domaine corrélatif de R; R' = ( xeEk I lj«x S 0, Vi }. Les représentants des arêtes d'un cône convexe étant toujours linéairement posi- tivement indépendants, on en conclut que les Ij sont linéairement positivement indépendants et que, par conséquent, R' est de dimension maximale. D'autre part, comme les Ij représentent les arêtes d'un cône convexe, aucun Ij ne peut s'exprimer comme combinaison linéaire des autres Ij (i*j). Par le théorème 2, on en déduit que R' possède des faces et que les Ij sont les vecteurs perpendi- culaires aux hyperplans d'appui de R' qui contiennent ces faces. Comme R est un cône convexe de dimension maximale engendré par les combi- naisons linéaires positives des 1;, on en déduit que les 1; forment un système de générateurs de Ek. Par conséquent, si xeEk satisfait l;«x = 0, Vi, x vaut 0. Ainsi, R' satisfait les hypothèses du théorème 3. C'est un cône saillant de di- mension maximale; il possède des arêtes. 11 suffit maintenant de montrer que les arêtes de R' sont exactement caractérisées par les éléments de Ak, ce qui démontrera que R' = Ck. Montrons d'abord que tout élément de Ak caractérise une arête de R'. Soit ajkeAk; ajk est perpendiculaire à un hyperplan d'appui de R. L'inter- section de R avec cet hyperplan d'appui est une face F. Comme toute face de R, F est l'enveloppe convexe des arêtes de R qu'elle contient. Supposons que les Ij, jej, représentent ces arêtes; l'enveloppe linéaire des Ij, jeJ, étant de codimension 1 dans Ek, les conditions aik»lj = 0 si jeJ, aik«lj>0 Vj, défi- nissent ajk à un facteur positif près. Cela revient à dire que ajk caractérise une arête de R'. Reste à voir que toute arête de R' appartient à Ak. Soit une arête de R' caractérisée par a. Les conditions lj«a = 0 si iel et lj.a ^ 0 Vi, caractérisent a à un facteur positif près. Cela revient à dire que a est perpendiculaire à un hyperplan d'appui de R et caractérise une face de R. Par le théorème 2, a est positivement proportionnel à un élément de Ak. GENERALITES SUR LES CONVEXES 17 4.2.2. Théorème fondamental : Pour tout entier k, d < k < s, notons pk la projection orthogonale de Ek sur Ed et 7tk la projection orthogonale de Ek sur Ek_1. Par construction, 7tk(aik) = a;k-' et pk(aik) = a;. On en déduit que pk(Ck)=C, Hk(Ck) = Ck-1 et pk » rk = identité. Théorème 4 : Toute face de C*"; est projection par nk, soit d'une face de Ck, soit de l'intersection de deux faces de 0-. Démonstration : Soit F, une face de Ck-1. F est une variété de dimension k-2. Considérons a', l'hyperplan d'appui dans Ek_1 qui contient cette face et a = (^"'(a'), l'hyperplan dans Ek engendré par a' et ek. Notons I, l'ensemble des indices des représentants des arêtes de Ck-1 contenues dans F. Par le corollaire des lemmes 1 et 2, ces arêtes sont les arêtes de F. Tous les points de Ck sont du même côté de a, puisque tous les points de Ck*1 sont du même côté de a'. Notons Ij, les vecteurs normaux aux hyperplans d'appui de Ck, et 1, un vecteur normal à a. On choisira le sens de 1 et celui des Ij de telle sorte que, pour tout x appartenant à Ck, on ait l;-x > 0 et Ux > 0. La variété de Ek définie par lj-x > 0, Vi et (-l)-x â 0 vit dans a. Par le théo- rème 1, il existe p S 0 et pi S 0, non tous nuls, tels que : P(-l) + 2>i Ii = 0. Comme les Ii sont linéairement positivement indépendants, p doit être non nul, et il existe au moins un pi non nul. Après renumérotation éventuelle, on peut supposer pi > 0. Donc, 1 = / f£- Ij avec pi > 0. Comme les aik, iel, sont contenus dans a, 1-ajk = o si iel. Si pi > 0, on déduit de ce qui précède que li«aik = 0 si iel. Cela signifie que les aik, iel, sont tous contenus dans la face Fi et représentent donc des arêtes de cette face. Deux cas sont possibles : Premier cas : un seul pi est non nul, disons p-. Dans ce cas, 1 est positivement proportionnel à 1-.. Toute arête de Fi étant une arête de Ck, elle se projette par itk sur une arête de Ck-1 contenue dans a', donc une arête de F. Les arêtes de F étant caractérisées par les ajk-1, iel, on en 18 FORMES PARFAITES A SEPT VARIABLES conclut que les ajk, iel, caractérisent toutes les arêtes de Fj. Par conséquent, par linéarité de Jtk, Jik(Fi) = F. Second cas : un second pi est non nul, disons pi- Notons Fi et F2, les faces correspondantes de Ck, et posons D = Fj Pi F2; nous allons montrer que Jik(D) = F. D étant une facette de Ck, il suffit de voir que les ajk, iel, caractérisent exacte- ment les arêtes de D. Comme toute arête de Ck contenue dans Fi et dans F2 est une arête de D, les ajk, iel, caractérisent des arêtes de D. Reste à voir qu'il n'y en a pas d'autres. A priori, D est un cône convexe de dimension inférieure ou égale à k-2. Mais comme a' est l'enveloppe linéaire des ajk_1, iel, la dimension de l'enveloppe li- néaire des a;k, iel, doit être supérieure ou égale à k-2. Par conséquent, dans ce cas, elle vaut exactement k-2, et D est un cône convexe, de dimension k-2, con- tenu dans l'enveloppe linéaire des ajk, iel. On en déduit que la projection par nk de toute arête de D, non seulement est une arête de Ck_1, mais est contenue dans a'; c'est une arête de F'. Comme précé- demment, les arêtes de F étant caractérisées par les ajk-', iel, on en conclut que les aik, iel, caractérisent toutes les arêtes de D. Q Th. 4 4.3. Faces voisines : 4.3.1. Définition et propriété fondamentale : On dira que deux faces Fi et F2 de C sont voisines si leur intersection est une fa- cette de codimension 2. Hemme 5 : Si D est une facette de C de codimension 2, seules exactement deux faces de C contiennent D. Démonstration : Par construction, D est contenue au moins dans deux faces de C. Considérons U, l'enveloppe linéaire des éléments de D, et U-1-, son complémen- taire orthogonal. Par hypothèse, U-1- est de dimension 2, c'est un 2-plan. Soit Fi, une face quelconque de C contenant D, Tj, l'hyperplan d'appui corres- pondant à Fj, et Ij, un vecteur perpendiculaire à Tj. Le sens de Ij est fixé par la condition lj.x S 0, VxeC. GENERALITES SUR LES CONVEXES 19 Observons que l,«x = 0, VxeD. Par conséquent, li«x = 0, Vx^U et ljeU1. Par le théorème 1, on sait que les Ij sont linéairement positivement indépendants. Par le théorème 2, on peut supposer qu'aucun 1; ne puisse s'exprimer comme combinaison linéaire positive des autres Ij (j*i). Dans un 2-plan, seul un ensemble de deux vecteurs, au plus, peut satisfaire si- multanément ces deux conditions. O L. 5 Corollaires : Soit D, une facette de C de codimension 2. Notons F et F les deux seules faces de C qui contiennent D; par définition d'une facette de C, on sait que D est exactement l'intersection de F et de F'. Aucune autre face de C ne peut contenir un point intérieur de D. En effet, si x est un point intérieur de D, il peut s'exprimer comme combinaison linéaire strictement positive des représentants des arêtes de D. Ainsi, toute face de C contenant x contient toutes les arêtes de D et, par conséquent, D tout entier. 4.3.2. Connexion : On dira que deux faces F et F de C sont connectées s'il existe une liste de faces de C : Fi = F, F2,..., Fi = F avec la propriété que Fj et Fj+i sont voisines Vj. Remarque : "être connecté" est une relation d'équivalence. 4.3.2.1. Théorème fondamental : Théorème S : Deux faces de C sont toujours connectées pour peu que C, en tant que variété, soit de dimension >2. Démonstration : s s Posons 1 = X Ii et considérons n, l'hyperplan affine d'équation 1.x = Z aj. i=i j=i Lc fait que l.aj > 0, Vj, montre que toute arête de C coupe 7t en un point. L'intersection de K et de C est donc un polyèdre P convexe, compact, d'intérieur non-vide, c'est-à-dire un polytope. Les faces de P sont en bijection avec celles de C. De plus, cette bijection est compatible avec la propriété "être voisines". On conclut en utilisant le théorème bien connu qui affirme que les faces de P sont connectées [Be 1 ]. ? Th. 5 20 FORMES PARFAITES A SEPT VARIABLES 4.3.2.2. Faces maximales : Dans ce qui suit, on supposera que C est un cône convexe saillant possédant s arêtes. On dira qu'une facette de C est maximale si seule une arête de C n'est pas conte- nue dans cette facette. Il est clair que toute facette maximale de C est une face de C. On parlera donc de face maximale. On appellera taille d'un cône convexe C (resp. d'une facette de C) la différence entre le nombre d'arêtes contenues dans C (resp. dans cette facette de C) et la dimen- sion de C (resp. de cette facette de C). Si C possède s arêtes, C possède au plus s faces maximales. Si s = dim C, C possède exactement s faces qui sont toutes maximales. La réciproque est vraie; si C possède s faces maximales, C ne possède pas d'autres faces et s = dim C (théorème 7). Théorème 6 : Soit F une face maximale de C. (i) Elle est voisine de toutes les autres faces de C. (U) Il y a bijection naturelle entre les faces de C différentes de F et les faces de F. (Ui) Cette bijection est compatible avec la relation "être voisine". (iv) Cette bijection conserve la taille. (v) Cette bijection conserve la propriété "être maximale". Démonstration : Soit F, une face de C différente de F. Considérons f = F n F. f est une fa- cette de C contenue dans F. Par le lemme 2, c'est une facette de F. La seule arête de F hors de f étant celle de C qui n'est pas dans F, f est une face maxi- male de F et dim f = (dim F)-I. (i) L'égalité dim f = (dim F) - 1 implique que F et F sont voisines. (ii) f est une facette de C strictement contenue dans F. C'est une face de F. Le lemme 5 montre que l'application qui envoie F sur f = F n F crée une bijection entre l'ensemble des faces de C différentes de F et l'ensemble des faces de F. GENERALITES SUR LES CONVEXES 21 (iii) Soit Fi et F2, deux faces de C, différentes de F; posons fi = F n Fj et f2 = F n F2. fi CY f2 est une facette de C contenue dans Fj n F2; c'est une facette de Fi n F2. Vu qu'elle contient toutes les arêtes de Fi n F2, excepté celle de C qui n'est pas dans F, fi n fjj est une face maximale de Fi n F2. En particulier, dim (fi n fi) = dim (Fi n F2) -1. On déduit facilement de cette der- nière égalité que fi et f2 sont voisines si et seulement si Fi et F2 le sont. (iv) D'une part, dim f = (dim F)-I; d'autre part, F possède exactement une arête de plus que f. Donc, taille f = taille F. (v) Comme f est toujours une face maximale de F et F une face maximale de C, f est une face maximale de F si et seulement si F est une face maximale de C. Conséquence : F possède exactement une face maximale de moins que C. ? Th. 6 On dira que deux faces F et F de C sont fortement connectées s'il existe une liste de faces non maximales de C : Fi = F, F2.....Ft = F avec la propriété que Fj et Fj+i sont voisines Vj. Théprfeme 7 ; Soit C, un cône convexe saillant de dimension supérieure ou égale à 3, possédant s arêtes. Notons y/(C), le nombre de ses faces maximales. (i) Si y/(C) > (dim C) - 3, alors y(C) = dim C = s. (U) Si XjZ(C) £ (dim C) - 3, alors C possède des faces non maximales et les faces non maximales de C sont fortement connectées. Démonstration : (par induction sur la dimension de C) Ancrage : dimC = 3 (i) Si V)/(C) > (dim C) - 3 = 0, C possède au moins une face maximale. Mais toutes les faces de C possèdent exactement deux arêtes. Donc s = 3, et les trois faces de C sont maximales. (ii) Si \|/(C) S (dim C) - 3 = 0, alors \|/(C) = 0. Aucune face n'est maximale et on conclut en se rappelant que les faces de C sont toujours connectées. Pas d'induction : dim O 3 Si \|/(C) = 0, on conclut comme pour l'ancrage (ii). On supposera donc que C possède au moins une face F maximale. On a : 22 FORMES PARFAITES A SEPT VAPIABLES \j/(F) = V(C) - 1 et dim F = (dim C) - 1 S 3. Deux cas sont à envisager : Cas 1 : V)/(C) > (dim C) - 3; dans ce cas, \|/(C) - 1 > (dim C) - 3 - l â 0, ce qui signifie y(F) > (dim F) - 3. En appliquant l'hypothèse d'induction à F, on obtient \|/(F) = dim F = (nombre d'arêtes dans F) = s - 1, puisque F est maximale. On en déduit y(C) = \|/(F) + 1 = (dim F) + 1 = dim C. En remplaçant dim F par sa valeur s -1, on obtient \y(C) = dim C = s. Cas 2 : y(C) <, (dim C) - 3; dans ce cas, y(C) - l < (dim C) - 3 - l, ce qui signifie \|/(F) < (dim F) - 3. En appliquant l'hypothèse d'induction à F, on obtient que F possède des faces non maximales et que ces faces non maximales sont fortement connectées. Les points (ii) et (v) du théorème 6 permettent alors de conclure que C possède des faces non maximales. Le point (iii) du théorème 6 montre qu'elles sont forte- ment connectées. ? Th. 7 Corollaires : 1) Si s > dim C, alors V|/(C) < (dim C) - 3 et C possède des faces non maximales. Il suffit de remarquer que l'hypothèse s > dim C implique dim C ä 3. 2) Si s > dim C, on peut appliquer l'algorithme suivant pour énumérer les faces de C : a. Chercher une face non maximale de C. b. Calculer toutes ses faces voisines. c. Mémoriser toutes les nouvelles faces. d. Pour chaque nouvelle face non maximale, recommencer à partir du point b. 4.4. Graphe des faces d'un cône saillant : Si C est un cône convexe saillant de dimension supérieure ou égale à deux, satis- faisant les hypothèses des théorèmes 2 et 3, la notion de faces voisines permet d'interpréter l'ensemble des faces de C comme un graphe localement fini; les faces jouent le rôle des sommets du graphe, les faces des faces, celui des arêtes. Le lemme 5 montre que ce graphe est bien défini : chaque arête relie exactement deux sommets! Le théorème 5 montre qu'il est connexe. Le théorème 6 nous dit qu'à une face maximale de C correspond un sommet du graphe relié, par des arêtes, à tous les autres sommets. Lorsque le nombre d'arêtes de C est égal à la dimension de C, le graphe des faces de C est complet. DOMAINES DE VORONOI 23 5. Domaines de Voronoï : 5.1. Domaine associé à une forme parfaite : On montre aisément qu'une forme est parfaite si et seulement si son domaine est de dimension maximale. Le domaine d'une forme parfaite a été défini comme l'enveloppe convexe d'un ensemble bien déterminé de demi-droites. Nous allons voir que cet ensemble de demi- droites possède une propriété géométrique de minimalité, à savoir : Lemme 6 : Si l'on retire une demi-droite de cet ensemble, l'enveloppe convexe de celles qui restent est toujours modifiée. Démonstration : Pour cela, remarquons d'abord que tout a = v vl, velR", fait un angle constant avec la matrice identité. On considère, bien entendu, la métrique définie par la trace. Cet angle satisfait cos 6 = -7= , en particulier, 0 e ] 0, f [• Vn z Considérons l'hyperplan d'équation trace X = n. Les intersections de cet hy- perplan et des demi-droites dont on prend l'enveloppe convexe sont des points distincts, tous situés sur une sphère centrée en la matrice identité. Ceci termine la démonstration. ? L. 6 On déduit facilement de ce qui précède le théorème suivant : Théorème S : Le domaine de Voronoï associé à une forme parfaite est un cône convexe sail- lant. Les demi-droites dont on prend l'enveloppe convexe pour définir le domaine sont exactement les arêtes de ce domaine. Remarque : Voronoï, dans son article, montre que les arêtes du domaine sont parmi les demi-droites dont on prend l'enveloppe convexe [ Vo 1 ]. Contrairement aux apparences, il ne démontre pas ces demi-droites sont exactement les arêtes du domaine. Il lui manque, en fait, le lemme 6 pour conclure. 24 FORMES PARFAITES A SEPT VARIABLES 5.2. Domaines voisins et formes voisines : 5.2.1. Définitions et nronriétés fondamentales : Soit q et q', deux formes parfaites, et leurs domaines C et C dans l'espace de Voronoï. Si ces deux formes sont positivement proportionnelles, il est clair que C = C Sinon, Voronoï montre que l'intersection de ces deux domaines ne contient aucun point intérieur de C ou de C; mieux, si CnC contient un point intérieur d'une facette de C, cette facette est aussi une facette de C. En particulier, si CnC contient un point intérieur d'une face de C, cette face est commune à C et C. Dans ce cas, ces deux domaines doivent donc obligatoirement se situer de part et d'autre de l'hyperplan d'appui définissant la face commune. On dira que C et C sont des domaines voisins et que les formes q et q' sont des formes voisines. A chaque face de C correspond donc, au plus, un domaine voisin. 5.2.2. Existence : Montrons qu'à chaque face de C correspond toujours un domaine voisin. Soit Q, la matrice associée à q, F, une face de C, et a, l'hyperplan d'appui d'équation Ux = O associé à F. Le sens de 1 est fixé par la condition UxSO, Vx^C. Montrons d'abord qu'il existe ueZ", tel que C et u u1 ne soient pas du même côté de a, ce qui revient à dire que la forme quadratique associée à 1 est indéfinie. Pour cela, considérons L l'application linéaire associée à la matrice 1. Observons qu'il existe une arête de F, caractérisée par a = v v' avec veZn, telle que L(v) soit non nul. En effet, comme L est non nulle, son noyau est de dimension inférieure à n; par conséquent, l'enveloppe linéaire, dans l'espace de Voronoï, des x xl avec xeKer(L), est de dimension inférieure ou égale à 2^-\ On conclut en remarquant que si n > 1, "-^ < dim F = ^^—^ -1. Soit, donc, un vecteur veZn, tel que : (a) L(v) = 1 v soit non nul et (b) v'lv=o. On choisira ensuite y et z dans Zn satisfaisant : (i) y' 1 y > 0 (penser à une arête de C qui n'est pas dans F), (ii) z' 1 v < 0 (par exemple z = - L(v)). On peut supposer que y11 v S 0 (en remplaçant éventuellement y par -y) et que z11 z S 0 (sinon, u = z est solution de notre problème). Considérons finalement w = Xy + z. En remarquant que w' 1 v est négatif pour tout X positif et que w' 1 w est positif dès que X est suffisamment grand, on construit notre vecteur u en posant u = (w11 w) v - (w11 v) w pour une certaine DOMAINES DE VORONOI 25 valeur entière de X suffisamment grande. On vérifiera sans peine que si X est assez grand, u' 1 u = - (wl 1 w) (wl 1 v)2 est négatif. Si Q' est voisine de Q relativement à la face F, on peut supposer sans restreindre la généralité que min Q = min Q'. Du fait que l'enveloppe linéaire des représentants des arêtes de F est de codimension l, on déduit que Q' - Q est proportionnelle à 1. Etudions par conséquent Q(0) = Q + 8 1, où 0 est un nombre réel. Si 9 < O, min Q(6) < min Q et les vecteurs minimaux de Q associés aux arêtes de F ne sont plus vecteurs minimaux de Q(O). Seul, le cas 9 > 0 reste donc intéressant. Lorsque 9 > 0 est suffisamment petit, min Q(9) = min Q et les vecteurs mini- maux de Q(9) sont exactement ceux correspondant aux arêtes de C contenues dans F. Considérons l'ensemble R des valeurs de 9 £ 0 pour lesquelles min Q(8) = min Q. L'existence d'un vecteur usZn satisfaisant l»(u u') < 0 montre que, si 0 est assez grand, u1 Q(0) u < min Q. ÏR, est donc borné. En observant que si min Q(0) = min Q, l'intervalle [ 0, 0 ] est entièrement contenu dans TR3, on conclut que ÏR, est lui-même un intervalle. La continuité de minQ(0) montre qu'il est fermé. ÎR, est donc de la forme [ 0, p ] pour un certain p > 0. Il est facile de voir que l'ensemble des valeurs de 0 dans ÎR,, pour lesquelles les vecteurs minimaux de Q(0) sont exactement ceux correspondant aux arêtes de F, est un ouvert; c'est même l'intérieur de ÎR,. Par conséquent, la forme Q' = Q + p 1 pos- sède au moins un vecteur minimal supplémentaire. L'arête correspondante, n'appartenant pas à F, doit être extérieure à a. Le domaine associé à Q' est alors de di- mension maximale dans l'espace de Voronoï. La forme Q' est parfaite; elle est la voi- sine de Q relativement à la face F. A ce stade, il est important de remarquer que, bien qu'une face d'un domaine C n'appartienne qu'à un seul autre domaine C, l'hyperplan a qui contient F peut conte- nir des faces d'autres domaines. Ainsi, le même hyperplan a peut être hyperplan d'appui de plusieurs domaines. La matrice 1 normale à a ne caractérise donc pas, en général, une unique face. 5.2.3. Illustration du cas des formes à 2 variables : Reprenons les notions de formes parfaites et de domaines associés aux formes parfaites dans le cas des formes à 2 variables, c'est-à-dire n = 2. L'espace des do- maines de Voronoï est difficilement visualisable dans le cas général. Seul le cas n = 2, N = 3 s'y prête bien. C'est pourquoi il est intéressant d'approfondir cette si- 26 FORMES PARFAITES A SEPT VARIABLES tuation particulière dans l'optique de Voronoï, afin de mieux saisir la géométrie de l'espace de Voronoï. Prenons, pour commencer, la matrice identité. Elle est associée à la forme x2 + y2. Son minimum vaut l. Ses vecteurs minimaux sont ± (q), ± ( A. Cette forme n'est pas parfaite. En effet, il existe une infinité de formes quadra- tiques définies positives qui possèdent ces vecteurs comme vecteurs minimaux. Une forme quadratique à deux variables est donnée par : Si ± f qÌ est un vecteur minimal, alors a = 1. Si ± f j Ì est un vecteur minimal, alors c = 1. Mais b n'est pas déterminé. On montre facilement que pour tout b inférieur en valeur absolue àj, la forme correspondante possède exactement ces vecteurs comme vecteurs minimaux. Par contre, lorsque b vaut ^, on obtient une forme qui possède un vecteur minimal supplémentaire. Cette forme est proportionnelle à A2 = f j 2 )• Elle est parfaite. En effet, le vecteur minimal supplémentaire ± ( , ) introduit la condition 1 - 2b + 1 = 1, condition qui détermine b. Lc réseau correspondant à cette matrice est engendré par deux vecteurs de même longueur et formant un angle de 60°. Cest le réseau, bien connu, d'empilement de sphères le plus dense dans le plan. fig. 2 Dans R3, le domaine associé à ( j 2 ) possède exactement trois arêtes caracté- risées par : --G)C)-(JS). <*=(??)• =»-(.',•;)• DOMAINES DE VORONOI 27 Comme s = N = 3, on calcule les faces du domaine en enlevant à tour de rôle chacune des arêtes; celles qui restent déterminent une face. Par exemple, on obtient F1 en retirant a] comme suit : Posons F1 = (.1 f2J, un vecteur normal à la face cherchée. Donc F1 est nor- mal à a2 et à a3. Ces conditions s'expriment à l'aide du produit scalaire donné par la trace. (i) F1 »a2 = Trace (F1 a2) = O, (ii) F1^a3 = Trace (F1 a3) = O. La condition (i) nous donne f3 = 0; la condition (ii) implique f] - 2 f2 + f3 = 0. Ces équations définissent F1 à un facteur près. On peut choisir F1 de telle manière que ses composantes soient entières et premières entre elles, et fixer le sens de F1 en de- mandant que Trace (F1 a^ > 0. On obtient F1 = ( j 0 V De manière analogue, on détermine F2 = (. , ) et F3 = ( _i "n )• Etudions la voisine de ( , - ) relativement à la face ( , "„ V fig. 3 28 FORMES PARFAITES A SEPT VARIABLES Cette voisine doit s'écrire (i2) + P (-1 o),Pouruncerta"1 P>0-La voisine étant unique, il n'existe qu'une seule valeur de p positive qui donne une forme par- faite de même minimum. On devine que pour p = 2, la forme correspondante ( .j 2 ) cst parfaite et de minimum 2. C'est donc la voisine cherchée. La figure ci-dessus (fig. 3) visualise, dans R3, les domaines associés à ces deux formes voisines. Les domaines correspondants sont voisins. Leur face commune admet L'.) comme vecteur normal. Pour plus de clarté, j'ai indiqué en petits carac- tères les représentants des arêtes des domaines et en caractères gras les formes corres- pondant à chacun de ces domaines. On prolongera par l'esprit les faces dont je n'ai dessiné qu'une portion. En contemplant ( 12 ) = ( o -1J (-12/ C 0 -1 /* on conc'ut Çue ces ^eux formes sont équivalentes. On peut, de même, calculer les voisines correspondant aux deux autres faces. La voisine correspondant à F1 est donnée par (32)- cc^e correspondant à F2 par (.3 6/" Après avoir calculé les voisines de A2, on peut déterminer les voisines des voisines de A2, etc. La figure 4, ci-dessous, prolonge la figure 3. Les arêtes de tout domaine sont caractérisées par des matrices de la forme [ti (ab)= (nbb2^* ^ne telle matrice sera représentée dans R3 par (a2, Vâab, b2). R 9 -6 -6 4 -1 1 0 0 0 1 1 1 1 1 4 -2 -2 1 fig. 4 DOMAINES DE VORONOI 29 Ce sont ses coordonnées dans la base orthonormée (oOy'-pvloy'Coi/- Il est facile de voir que les voisines de A2 sont équivalentes à A2, soit en explici- tant des matrices de changements de bases qui réalisent l'identification, soit en consta- tant que le groupe des automorphismes de A2 est transitif sur les faces du domaine as- socié à A2. Voronoï démontre que, de manière générale, le groupe des automor- phismes de An agit transitivement sur les faces du domaine associé à cette forme. An est donnée par X12 + x22 +... + xn2 + (xj + X2 +... + Xn) . Dans les cas n = 2 et n = 3, les voisines de An sont équivalentes à An, donc, d'après Voronoï, il n'existe qu'une seule classe de formes parfaites dans ces dimensions. Revenons au cas n = 2; en remarquant que a2 b2 = (a b)2, on conclut que les représentants de toutes arêtes appartiennent à la surface d'équation y2 = 2 x z. Il s'agit d'un cône de révolution dont le sommet est à l'origine. La section de ce cône par le plan d'équation x + z = 2 est un cercle de rayon Va centré en (l, 0,1). Remarquons, au passage, que (l, 0,1) correspond à la matrice identité. La figure S, ci-dessous, visualise cette section. O O O 1 fig. 5 30 FORMES PARFAITES A SEPT VARIABLES Ici, le chemin reliant deux domaines est unique. En effet, associons à chaque domaine un point intérieur et relions les points qui appartiennent à deux domaines voisins. Le graphe ainsi obtenu est, en fait, un arbre. Le sens d'un vecteur normal à une face d'un domaine est fixé par la condition que son produit scalaire avec un représentant d'une arête de ce domaine soit toujours positif ou nul. Pour qu'une forme B soit intérieure à un domaine, il faut et il suffit que F«B > 0 pour tout F, vecteur normal à une face du domaine. On voit facilement que A2 n'est pas intérieure à son domaine. En effet, Trace (iq) ( 12)"" °- ^ar contre, en additionnant les représentants des arêtes d'un domaine, on obtient toujours une forme qui est intérieure à ce domaine. Ici, dans chaque cas, on trouve la forme ad- jointe. Par exemple, la forme adjointe de (. 2 Ì est ( 1 2 ) •" «Ï)-(J!)*(^)*(SÏ)- La forme parfaite A2 est donc eutactique. La figure 6, ci-dessous, illustre l'eutaxie de la forme parfaite A2. 1 0 0 0 fig. 6 DOMAINES DE VORONOI 31 Je rappellerai ici le critère démontré par Voronoï : une forme est extrême si et seulement si elle est parfaite et eutactique. Lorsqu'on a une forme parfaite, on peut représenter son domaine dans l'espace de Voronoï; mais on peut aussi la considérer comme un point dans cet espace. On vient de voir qu'en général ce point n'appartient pas au domaine de la forme. Quel est alors le lien géométrique entre deux domaines voisins et les deux formes parfaites voisines correspondantes? On peut répondre à cette question par un exemple. Partons du domaine associé à A2 et considérons la face de ce domaine, donnée par ( } 2 Y Cette face appartient également à un autre domaine : le domaine associé à ( 3 6 V Ces deux domaines sont donc voisins et les formes parfaites correspondantes sont voisines. Voronoï nous dit que (35) doit s'obtenir en additionnant à ( j 2 j un multiple positif du vecteur nor- mal à la face, c'est-à-dire un multiple positif de (1 2 )• Numériquement, on obtient : GJ)-(îi)«(ïO- La figure suivante illustre cette relation. fig. 7 32 FORMES PARFAITES A SEPT VARIABLES 6. Graphe de Voronoï : 6.1. Definition : La notion de domaines voisins permet d'interpréter l'ensemble des domaines as- sociés aux formes parfaites comme un graphe localement fini; les domaines jouent le rôle des sommets du graphe, les faces des domaines celui des arêtes. Nous appelle- rons ce graphe, le graphe de Voronoï. 6.2. Connexité du graphe : Nous allons montrer que le graphe de Voronoï est connexe. La démonstration est essentiellement basée sur le lemme suivant : Lemme 7 : Soitf, la matrice d'une forme quadratique définie positive et ß, un nombre réel positif. Il n'existe au plus qu'un nombre fini de matrices A associées à,des formes parfaites de minimum J et vérifiant f-A £ß. Démonstration : Comme A est définie positive, il existe une matrice SeGLn(K), telle que A = S1S. Appelons Ux le vecteur dont les composantes sont celles de la kèmc n ligne de S. On montre facilement que f» A = 2^ Ik1 f Ik- f &ant définie positive, k=i chacun des termes Ik' f Ik doit être strictement inférieur à ß, et la norme de S est bornée supérieurement par une constante qui ne dépend que de f. La relation d'Hermite H(A) ^ yn montre que le déterminant de S ne peut de- venir arbitrairement petit. Ainsi, par Cramer, la norme de S'1 est aussi bornée supérieurement par une constante qui ne dépend que de f. On en déduit qu'en valeur absolue, les composantes des vecteurs minimaux de A sont bornées supé- rieurement par une constante qui ne dépend que de f. Considérons 6, l'ensemble des vecteurs ve Z" dont les composantes sont, en valeur absolue, inférieures à cette constante. Cet ensemble est bien évidemment fini. On peut définir une application qui, à chaque matrice A satisfaisant les hy- pothèses du lemme, fait correspondre une partie de 6 : l'ensemble des vecteurs minimaux de A. Vu que les matrices A sont associées à des formes parfaites de minimum 1, cette application est injective, ce qui permet de conclure. Q L. 7 GRAPHE DE VORONOI 33 Pour démontrer la connexité du graphe de Voronoï, il suffit de montrer que deux domaines quelconques C et C sont toujours connectés. Pour cela, considérons f, un point intérieur de C. f est toujours la matrice d'une forme quadratique définie positive. Comme f est un point intérieur de C, si f appartient à C, alors C = C. Si, par contre, f n'appartient pas à C, on peut trouver un hyperplan d'appui n de ce domaine, définissant une face de C, tel que C et f se situent de part et d'autre de n. On recom- mence alors le raisonnement en remplaçant C par son domaine voisin relativement à la face n n C. Le lemme garantit que le processus s'arrête après un nombre fini d'itérations. En effet, f«A , où A est la matrice de la forme parfaite de minimum 1 associé au domaine testé (C), décroît strictement lors de chaque itération. Considérons l'action de Gln(Z)XlR+ sur l'ensemble 5Pn des formes parfaites à n variables : a : (Gln(Z) x R+) x IPn -------> IPn , (S; X).q = Xq=S"1 Les orbites de cette action correspondent aux classes d'équivalence des formes parfaites. Théorème 9 : L'action a décompose Pn en un nombre fini d'orbites. Pour la démonstration, on se référera, par exemple, à [Vo 1 ] ou à [Oe 1 ]. Considérons la représentation o de Gln(Z) sur l'espace de Voronoï T/ : a : Gln(Z) -----------> Gl(V) S i----------> (Js : V -----------> V x i-------------> SxS1 Si aie = Vk vkl caractérise une arête du domaine associé à q, o"s(ak) caractérise une arête du domaine associé à qoS"1. Par linéarité, on conclut que as transforme le domaine associé à q en le domaine associé à q°S"' = cc((S; 1); q), et crée une bijec- tion entre les faces de ces deux domaines. Mieux : la permutation des domaines associés aux formes parfaites, induite par Os, est compatible avec la relation "être voisins". Par conséquent, a permet de définir une action de Gln(Z) sur le graphe de Voronoï. On dira que deux domaines sont équivalents s'ils appartiennent à la même orbite. On montre facilement que deux domaines sont équivalents si et seulement si les formes 34 FORMES PARFAITES A SEPT VARIABLES parfaites correspondantes sont équivalentes. Il n'existe donc qu'un nombre fini de classes d'équivalence de domaines. Le stabilisateur d'une forme parfaite par l'action a est un sous-groupe de Gln(Z) x [ 1J. Sa projection sur Gln(Z) est appelée groupe des automorphismes de cette forme. Il faut comprendre "automorphisme" dans le sens d'isométries entières de cette forme. Observons que le groupe des automorphismes d'une forme parfaite peut égale- ment être défini comme le stabilisateur du domaine associé à cette forme, par l'action de Gln(Z) sur le graphe de Voronoï. En effet, soit q, une forme parfaite, et C, le domaine qui lui est associé; SeGln(Z) est un automorphisme de q si et seulement si qoS"1 = q, c'est-à-dire Os(C) = C puisque q est parfaite. Pour rendre fidèle l'action du groupe des automorphismes d'une forme parfaite sur l'ensemble des arêtes du domaine associé à cette forme, il suffit de quotienter le groupe des automorphismes par +identité, puisque toute forme parfaite est connectée au sens de Coxeter [Co I]. J'appellerai le groupe ainsi obtenu le groupe des fijODitti£5 du domaine. Finalement, il est clair que le groupe des automorphismes d'une forme parfaite est un groupe fini, puisque, si ±vi, ±V2,..., ±vs sont les vecteurs minimaux de cette forme, son groupe des automorphismes s'injecte de façon évidente dans le groupe des permutations de 2s éléments. GRAPHES LOCALEMENT FINIS 35 7. Quelques propriétés des graphes localement finis : Soit r, un graphe localement fini, A, l'ensemble de ses sommets et Cl, l'ensemble de ses arêtes. On définit deux applications naturelles : S : AxA -----------> {0,1) (x; y) !----------> l si x et y sont liés par une arête 0 sinon §>: Cl -----------> ÎP(^) injective a i----------» {xa, ya} où xa et ya sont les deux sommets de r liés par l'arête a. Soit un groupe G opérant sur T. G opère également sur A et Cl, et il y a compa- tibilité de ces deux actions. Il existe donc deux actions, disons a^ et Oq, a^ : Gx/S -----------> A et Ot0 : G x Cl --------—> Cl (g;x) i----------> g.x (g; a) i----------> g.a satisfaisant les propriétés suivantes de compatibilité : (i) S(X, y) = S(g.x, g.y), VgeG et Vx, y e^ (ii) &(g«a) = (g.xa, g«ya), VgeG et VaeCl ou encore {xg.a, yg.a) = {g-xa, g«ya). VgeG et VaeQ. Définitions : On dira que deux sommets x et y sont voisins si U(x, y) = l. On appellera voi- sin de x. tout sommet y de T tel que S(x, y) = l. Considérons, dans un premier temps, Cc^, l'action de G sur l'ensemble Â> des sommets du graphe. Cette action partitionne /& en orbites. Soit Ox = (xi, X2,..., xj,...}, une telle orbite, et x, un sommet quelconque de Ox. Appelons Vx, l'ensemble des sommets voisins de x et Gx, le stabilisateur de x dans G. On peut considérer la restriction de a^ à Gx x Vx. Cette restriction nous fournit une action ccx de Gx sur Vx. Cette action partitionne Vx en orbites. On appellera ces orbites, les orbites de voisins de x; le nombre d'orbites de voisins de x est fini puisque, par hypothèse, le graphe est localement fini. Notons VJx, la jÈmc orbite de voisins de x. Si deux sommets appartiennent à la même orbite VJx, il est clair qu'ils sont également dans la même orbite lorsqu'on regarde l'action de G sur A. 36 FORMES PARFAITES A SEPT VARIABLES Soit maintenant Ox = [\\, X2,..., x,,...} et Oy = (yi, y2,—, yi.— }, deux orbites de sommets, distinctes ou non, par rapport à l'action de G sur /S. Pour x, un sommet quelconque de Ox, on définit la fonction suivante : f(x, Oy) = X %(v'x. Oy) où x(V'x, Oy) vaut 1 si V'xCOy, et O sinon. i f(x, Oy) compte le nombre d'orbites de voisins de x, contenues dans Oy. Théorème 10 : Avec les notations ci-dessus : (i) fix, Oy) est constante lorsque x parcourt Ox. On peut donc parler de J(Ox, Oy). (U) Avec la remarque du point (i),fest symétrique, c'est-à-dire /(Ox1Oy)^f(Oy1Ox) V Ox, Oy. Démonstration : (i) Soit x et x', deux sommets de la même orbite Ox. On doit démontrer que f(x, Oy) = f(x", Oy) VOy. Comme x et x' sont dans la même orbite, il existe geG tel que g«x = x'. Soit V1X, V2X,..., Vkx,...,Vqx, les orbites de voisins de x. Les translatés par g des orbites de voisins de x donnent les orbites de voisins de x'. On peut donc numéroter les orbites de voisins de x' de telle manière que Vkx' = g-Vkx Vk. En observant que Vkx et Vkx' sont contenues dans la même orbite de A par rap- port à l'action a^, on déduit que X(V1St. Oy) = X(V1V, Oy) Vk, VOy. En par- ticulier, f(x, Oy) = f(x', Oy) quelle que soit l'orbite Oy considérée. (ii) Si Ox = Oy, il n'y a rien à démontrer. Supposons Ox * Oy. Remarquons d'abord que la relation "être voisin de" est symétrique. Par consé- quent, f(Ox, Oy) = O si et seulement si f(Oy, Ox) = O. On supposera donc que f(Ox, Oy) > O. Soit yi et y2, deux sommets voisins de x, distincts ou non, contenus dans Oy. Il existe geG tel que y2 = g«yi- Choisissons un quelconque y dans Oy; on trouvera gjeG tels que y = gi«yi (i=l,2). Remarque : 1 = &(x, yi) = &(gi-x, gj.yi) = &(gi»x, y) signifie que gi»x et g2«x sont voisins de y. GRAPHES LOCALEMENT FINIS 37 Si gi»x et g2«x sont dans la même orbite de voisins de y, il existe h'eGy, tel que h'(gi*x) = g2*x. Dans ce cas, h = (g2-1 h' g]) appartient à Gx, et envoie yi sur y2. Par conséquent, si yi et y2 appartiennent à des orbites de voisins de x diffé- rentes, gi«x et g2«x doivent aussi appartenir à des orbites de voisins de y diffé- rentes. Ainsi, f(Ox, Oy) = f(x, Oy) £ f(y, Ox) = f(Oy. Ox). En échangeant les rôles de Ox et Oy, on obtient f(Oy, Ox) £ f(Ox, Oy), ce qui termine la démonstration. ? Th. 10 Notations : Si S(x, y) = 1, l'orbite de voisins de x qui contient y sera notée Vx(y). Si a est l'arête qui relie x et y, on notera Ga, le sous-groupe de G qui stabilise a. Lemme 8 : Soit x et y, deux sommets, XeOx etyeOy. On supposera Ox et Oy distinctes. Si %(x, y) = 1 et si a est l'arête qui relie x et y, on a : (i) Ga = Gx n Gy; (U) IGxI IVy(X)I=IGyI IV3Jy)I. Démonstration : (i) Soit geGa, c'est-à-dire g»a = a. La compatibilité des actions de G sur Cl et de G sur /&, nous dit que {x, y} = &(a) = £>(g«a) = {g«x, g«y). Comme Ox et Oy sont disjointes, on doit avoir g»x = x et g«y = y, ce qui signifie que g appar- tient à Gx et à Gy. Autrement dit, g appartient à Gx n Gy. 38 FORMES PARFAITES A SEPT VARIABLES Inversement, si g e Gx O Gy, &(a) = {x, y} = {g«x, g.y} = &(g«a). Par in- jectivité de §>, on conclut que g«a = a, c'est-à-dire geGa. (ii) On remarquera, tout d'abord, que Vx(y) et Vy(x) sont toujours des en- sembles finis puisque, par hypothèse, le graphe considéré est localement fini. Si Gx et Gy sont des groupes infinis, il n'y a rien à démontrer. On supposera donc que Gx est un groupe fini. Par (i), Ga peut être vu comme le sous-groupe de Gx qui stabilise y. En particulier, c'est un groupe fini. Par conséquent, I Gx I = IG31 I Vx(y) |. De même, en interprétant G3 comme le sous-groupe de Gy qui stabilise x, on conclut que I Gy I = IG31 I Vy(x) I et, en particulier, que Gy est un groupe fini. En éliminant I Ga I de ces deux équations, on obtient la relation annoncée. ? L. 8 Lemme ? : Soit x et x', deux sommets appartenant à Ox. Supposons que êl(x, x') = 1, et appelons a, l'arête qui relie x et x'; alors : (i) Gx n Gx- (Z Ga; (U) Gx n Gx- est soit égal à G0, soit d'indice 2 dans Ga; (Hi) Ivx-(X)I=IVx(X')!. Démonstration : (i) Comme avant, soit g e Gx n Gx-; £>(a) = (x, x'} = {g«x, g-x'} = &(g«a). L'injectivité de §> nous permet de con- clure que g«a = a, c'est-à-dire geGa. (ii) Premier cas : Aucun heG n'échange x et x'. Dans ce cas, prenons geGa; alors, {x, x'} = £>(a) = &(g»a) = {g«x, g«x'}. L'hypothèse qu'aucun élément de G n'échange x et x' permet de conclure qu'obligatoirement, g«x = x et g«x' = x'. Donc, g appartient à Gx et à Gx', ce qui signifie que g appartient à Gx n Gx'. Le point (i) nous permet de conclure Gx n Gx- = G3. Second cas : Il existe heG, tel que x'= h«x et x = h«x'. Observons que si g appartient à Gx n Gx', gh appartient à G3. En effet, &(gh.a) = {(gh).x, (gh).x'} = {g»(h.x), g.(h.x') = {g.x', g.x} = {x', x), ce qui permet de conclure, par injectivité de §>, que a = (gh)«a, c'est-à-dire ghsGa. GRAPHES LOCALEMENT FINIS 39 Ainsi, (Gx n GxO u h(Gx n Gx1) est contenu dans Ga. Pour montrer l'inclusion inverse, considérons g appartenant à Ga. Obligatoirement, (g«x, g.x'} = {x, x'}. Si g«x = x, alors g«x' = x' et, par conséquent, ge Gx n Gx'. Sinon, g.x = x' et g.x' = x. Dans ce cas, (h^g) e Gx Pi Gx1; autrement dit, g e h(Gx n Gx-). Ainsi, G3 est contenu dans (Gx O GxO u h(Gx n GxO- Finalement, cela démontre que G3 = (Gx n GxO u h(Gx n GxO, d'où le fait que Gx n Gx' est un sous-groupe de G3 d'indice 2. (iii) On regarde Gx n Gx' comme le sous-groupe de Gx qui stabilise a. La car- dinalité de l'orbite Vx(x') est l'indice de Gx n Gx- dans Gx. De même, la cardinalité de l'orbite Vx-(x) est l'indice de Gx n Gx- dans Gx-. On conclut en observant que, comme x et x' sont tous deux dans Ox, Gx et Gx- sont conjugués. O L. 9 40 FORMES PARFAITES A SEPT VARIABLES 8. Algorithme de Voronoï : 8.1. Description : Cet algorithme permet de calculer tous les maxima locaux de la fonction \i et, en particulier, la valeur de Yn- On peut vérifier que, modulo les homothéties, tous les maxima locaux de (I sont isolés. L'algorithme de Voronoï ramène le calcul des formes extrêmes à rénumération complète des classes de formes parfaites. En effet, Voronoï commence par démontrer son fameux théorème : une forme quadratique définie positive est extrême si et seulc- mentsi elle est parfaite et eutactique. On rencontre dans la littérature plusieurs démonstrations de ce théorème. A part celle de Voronoï lui-même, je citerai, entre autres, celle de Barnes [ Ba 4] basée sur un lemme de Stiemke [Sti 1 ], celle de Martin Kneser utilisant la géométrie des con- vexes [Kn 1 ] et celle, plus générale, d'Anne-Marie Berge et de Jacques Martinet [BM 2]. Pour obtenir une enumeration complète, à équivalence près, des formes parfaites à n variables, l'algorithme de Voronoï se base, d'une part, sur la connexité du graphe de Voronoï, d'autre part, sur la finitude du nombre de classes d'équivalence des do- maines associés aux formes parfaites. Partant d'un domaine quelconque, on mémorisera sa classe d'équivalence et on déterminera tous ses domaines voisins. Certains d'entre eux n'appartiendront peut-être pas à la classe de départ. Dans ce cas, on obtiendra une liste de nouvelles classes d'équivalence. On mémorisera ces nouvelles classes et, pour chacune d'entre elles, on choisira un représentant. Pour chacun de ces représentants, on déterminera à nouveau ses domaines voisins, domaines qui, à leur tour, caractériseront parfois de nouvelles classes, etc. La connexité du graphe garantit qu'en réitérant ce processus toutes les classes seront atteintes, quel que soit le domaine de départ choisi. La finitude du nombre de classes d'équivalence prouve que l'algorithme s'arrête. L'énumération de toutes les classes de domaines associés aux formes parfaites (donc de toutes les classes de formes parfaites) est complète lorsque, pour chaque classe connue, les voisins d'un représentant quelconque appartiennent tous à des classes déjà connues. 8.2. Symétries : Dans la pratique, pour déterminer tous les domaines voisins d'un domaine, il faut d'abord calculer toutes les faces de ce domaine. C'est un problème de program- ALGORITHME DE VORONOI 41 mation linéaire entière dont la complexité croît très rapidement en fonction du nombre s de paires de vecteurs minimaux. Soit q, une forme parfaite et D, le domaine qui lui est associé. Le groupe des sy- métries de D agit sur les faces de D. On dira que deux faces sont équivalentes si elle appartiennent à la même orbite. Il est clair que deux faces équivalentes donneront lieu à deux domaines voisins équivalents. Pour appliquer l'algorithme de Voronoï, il suffit de connaître au moins une face dans chaque orbite. Géométriquement, cela revient à utiliser les symétries des domaines, ce qui simplifie parfois considérablement le problème. On trouvera une illustration de cette simplification dans [JS I]. 8.3. Calcul des faces d'un domaine : Lorsque le nombre d'arêtes d'un cône convexe C est égal à sa dimension d, le calcul des faces est instantané. Il suffit, en effet, de retirer à tour de rôle chacune des arêtes; celles qui restent déterminent une face. Par contre, lorsque le nombre d'arêtes est supérieur à cette dimension, il faut re- marquer que, si l'on aborde la recherche des faces d'un point de vue combinatoire (test de tous les (d-l)-tuples d'arêtes), le problème explose rapidement. C'est là qu'interviennent mes algorithmes de la cascade et de l'explorateur. 8.3.1. Algorithme de la cascade : 8.3.1.1. Description : Considérons le relèvement de C (cf 4.2) avec d = dim C = N = "^2*" '. On sup- posera que C possède s arêtes. L'algorithme de la cascade se base sur le théorème fondamental du relèvement (th. 4, cf 4.2.2) qui garantit que toute face de Ck-1 peut s'obtenir par projection par Jtk, soit d'une face de Ck, soit de l'intersection de deux faces de Ck. Le principe de cet algorithme consiste à calculer d'abord les faces de Cs (sommet de la cascade), puis, à partir des faces de Cs, à calculer celles de Cs-1 (premier saut) en employant le fait que Cs_1 = ïts(Cs), puis, à partir des faces de Cs_1, à calculer celles de Cs"2 (second saut) en employant le fait que Cs_2 = k^KC5"1), et ainsi de suite, jusqu'au dernier saut qui, à partir des faces de CN+1, permet de calculer celles de CN.' Lc temps de calcul est ainsi considérablement rtiduiL 42 FORMES PARFAITES A SEPT VARIABLES 8.3.1.2. Symétries : Dans ce qui suit, on considérera C, un domaine de Voronoï associé à une forme parfaite q. Un élément du groupe des symétries de ce domaine peut être représenté indiffé- remment et fidèlement par une matrice dans Gln(Z), par un automorphisme de l'espace de Voronoï qui conserve le domaine, ou par une permutation des arêtes du domaine. Par ce qui précède, le groupe des symétries de ce domaine peut être vu comme un groupe G d'automorphismes de EN qui conserve C. Le relèvement de ce cône or- donne les arêtes du domaine. Pour k = N,..., s, définissons Gk par : Gk = {geG I g fixe les k - N, dernières arêtes du domaine). Il est clair que G = GN > GN+1 >...> Gs. D'autre part, il y a une représentation canonique de Gk sur Ek ^ EN : Gk -----------> Gl(Ek) g i----------> gk : Ek = EN®E-L-----------> E1^ = ENeE1 avec gk I En = g et gk | £i = identité. Comme geGk laisse fixes les k - N dernières arêtes de C, gk laisse fixes les k - N dernières arêtes de Ck. Par construction, seules, exactement, les k - N dernières arêtes de Ck ne sont pas dans EN. Ainsi, gk est un automorphisme de Ek qui conserve Ck. Cette remarque nous permet de définir le groupe des symétries de Ck; il s'agit de l'image de Gk par la représentation ci-dessus. Dans la pratique, calculer Gk peut être très long. On se contentera en général d'un sous-groupe. Soit donc G = GN= HN > HN+I >...> Hs avec, pour tout k, Hk < Gk. Dans ce qui suit, une telle suite de sous-groupes Hk sera fixée définitivement; de plus, on représentera Hk comme un sous-groupe de permutations des arêtes du do- maine, ce qui nous permet d'identifier canoniquement Hk et son image par la représen- tation ci-dessus. Par un élément de Hk, toute facette de Ck est transformée en une facette de Ck de même dimension. On dira que deux facettes de Ck sont équivalentes s'il existe un élé- ment de Hk qui envoie la première sur la seconde. Plus généralement, si l'on considère l'ensemble des arêtes de Ck, on peut définir une notion d'équivalence entre deux parties de cet ensemble. Deux parties sont équiva- lentes s'il existe un élément de Hk qui envoie la première sur la seconde. Comme Hk < Hk_1, on observe que ces équivalences sont compatibles avec la projection 7tk qui envoie Ck sur Ck-1. ALGORITHME DE VORONOI 43 On dira qu'une partie de l'ensemble des arêtes d'un cône convexe de dimension maximale caractérise une face F donnée de ce cône si les arêtes de cette partie sont dans F et si l'enveloppe linéaire des représentants des arêtes de cette partie est un sous- espace de codimension 1. Ecrivons les orbites de faces de Ck sous l'action de Hk en mettant en évidence un représentant pour chaque orbite : (Fik. Fi,2ki—iFi,t,k). représentant Fik; (F2k, F2,2k,-,F2,t2k), représentant F2k; etc. Lemme 10 : Si une face de C^1 est caractérisée par la projection des arêtes contenues dans l'intersection de deux faces de &, elle est équivalente par l'action de Hk-J à une face caractérisée par la projection des arêtes contenues dans l'intersection de deux faces de 0-, où la première face est le représentant choisi de son orbite. Démonstration : Soit deux orbites de faces de Ck, © et © ' (distinctes ou non), © = (F = Fik, F2k,..., Ftk} et ©' = (F =F!k, F'2k.....F'fk}. Soit encore F;ke© et Fjke©', deux faces de Ck. Supposons que les arêtes de 7tk(F;k O F'jk) caractérisent une face de Ck_1. Comme F et F;k appartiennent à ©, il existe geHk, tel que F = g-Fjk. Comme g appartient à Hk < Hk_1, g doit appartenir à Hk_1; ainsi, affirmer que les arêtes de 7tk(Fjk o F'jk) caractérisent une face de Ck_1 équivaut à dire que les arêtes de g-(7tk(Fik O Fjk)) caractérisent une face de Ck_1, face qui est équi- valente à la première par l'action de Hk_1. On vérifiera sans peine que nk et g commutent, en observant que la permutation des indices des arêtes induite par rck n'est autre que la permutation identité. Ainsi, dire que les arêtes de g«(jtk(Fjk o Fjk)) caractérisent une face de Ck_1, revient à dire que les arêtes de 7I1Kg-(Fi1OFj1O) caractérisent une face de C*'1. On peut maintenant conclure en remarquant que : g.(Fik O Fjk) = (g-Fik) O (g-F'jk) = F O (g-Fjk). „,, - ? L. 10 44 FORMES PARFAITES A SEPT VARIABLES Ce lemme technique permet d'éviter un nombre parfois considérable de tests de faces potentielles, lorsqu'on effectue un saut dans l'algorithme de la cascade. En effet, il suffit de tester, en les projetant, les facettes obtenues par le procédé suivant : on numérote les orbites de faces de Ck et les éléments de ces orbites; on prend la première face de la première orbite et on considère successi- vement les intersections de cette face avec toutes les faces de Ck; on prend ensuite la première face de la seconde orbite et on considère suc- cessivement les intersections de cette face avec toutes les faces de Ck ap- partenant à une orbite dont le numéro est supérieur ou égal à 2; on continue avec la première face de la troisième orbite et on considère successivement les intersections de cette face avec toutes les faces de Ck appartenant à une orbite dont le numéro est supérieur ou égal à 3; et ainsi de suite jusqu'à la dernière orbite. Pour fixer les idées, si C* possède x orbites contenant chacune y faces, le rap- port entre le nombre de cas testés en appliquant le lemme IO et le nombre de cas testés sans employer ce lemme est donné par ^~t, qui est de l'ordre de -. 8.3.1.3. Implementation en LISP : Un domaine de Voronoï est entièrement caractérisé par les représentants de ses arêtes. Nous avons vu que les arêtes d'un domaine sont exactement les demi-droites dont on prend l'enveloppe convexe pour définir ce domaine. Si +vj, ±V2,..., ±vs sont les s paires de vecteurs minimaux de la forme parfaite q (de minimum 1) corres- pondant à ce domaine, les ak = v^ v^1 (k = l,...s) caractérisent donc les arêtes du domaine. Les points, dans l'espace de Voronoï, sont des matrices symétriques nxn. Nous allons représenter ces points par des vecteurs de RN où N = 1^ ' . Plus précisé- ment, une matrice symétrique A = (ajj) sera représentée par le vecteur suivant (en no- tation transposée...) : (an a)2... am a^ a^... a^ a^... ann). Cet isomorphisme d'espace vectoriel transforme le domaine de Voronoï en un cône convexe saillant C de RN dont les arêtes sont exactement caractérisées par les vecteurs images des ajc (k =1,..., s). Il est clair que cette transformation envoie toute facette de dimension d du domaine de Voronoï sur une facette de dimension d de C. Le calcul des faces du domaine se ramène donc au calcul des faces de C. Pour des raisons de commodité, le produit scalaire utilisé pour les calculs dans RN sera le produit scalaire usuel. Il est évident que le produit scalaire usuel de RN ne correspond pas directement au produit scalaire défini par la trace dans l'espace de ALGORITHME DE VORONOI 45 Voronoï, mais cela n'a que peu d'importance. On calculera facilement, lorsque cela est nécessaire, un vecteur normal - au sens du produit scalaire défini par la trace - à une face du domaine, à partir d'un vecteur normal à une face de C - au sens du produit scalaire usuel de RN. Explicitement, (bM b,2... bin D22 D23... O2n b33... bnn) sera traduit en une matrice B = (b'ij) avec b'ü = bu et b'ij = j bjj, si i est différent de j.2 Notre problème est donc entièrement ramené à un problème de programmation linéaire entière dans EN muni du produit scalaire usuel. Pour ne pas introduire de nouvelles notations, on supposera que les ai, a2,..., as sont s vecteurs de IR N qui ca- ractérisent les arêtes de C. Après renumérotation éventuelle, on peut supposer que les N premiers vecteurs de cette liste sont linéairement indépendants, puisque la forme est parfaite. Notons TH, la Nxs-matrice dont les colonnes sont les aj. Cette matrice contient toute l'information de notre problème. Par des opérations élémentaires de lignes uni- quement, on peut transformer TR, en une matrice dont le bloc NxN de gauche est une matrice identité. Donc, il existe une matrice B inversible, telle que : * . . * \ * . . * j 2 Les différents types d'enregistrement utilises pour mémoriser les faces sont les suivants : - type "mat" la face est enregistrée sous forme d'une matrice mémorisant un vecteur normal, dans l'espace de Voronoï, à l'hypcrplan d'appui qui lui correspond. -type "mat-1" comme pour le type "mat", mis à part le choix de la structure de mémoire interne : la matrice est enregistrée sous forme d'un vecteur à n composantes où chaque com- posante de ce vecteur est une liste à n éléments, qui mémorise une ligne de Ia ma- trice; cette représentation interne permet d'effectuer des opérations de lignes sur la matrice de manière très performante; par exemple, échanger deux lignes d'une telle matrice revient à échanger deux composantes d'un vecteur! - type "vec" la face est enregistrée sous forme d'un vecteur à N composantes, mémorisant un vecteur normal, dans RN, à l'hypcrplan d'appui qui lui correspond. - type "liste" comme pour le type "vec", mis à part le choix de la structure de mémoire interne : le vecteur à N composantes est remplacé par une liste à N composantes. - type "ent" entier dont le iime bit vaut O si et seulement si la iÈm0 arête du domaine est dans la face. CcUc dernière représentation est la plus économique du point de vue de la place mémoire; d'autre part, c'est celle qui se généralise le mieux lorsqu'on veut mémoriser une facette quelconque de C ou relever C en vue d'appliquer l'algorithme de la cascade. Lorsqu'une face est représentée par un vecteur normal, le sens du vecteur sera toujours choisi de telle manière que le produit scalaire entre ce vecteur normal et le représentant d'une arête du domaine ne soit jamais négatif. Diverses fonctions sont programmées pour passer d'une représentation à une autre lorsque cela est né- cessaire. Par exemple, la traduction d'une face de type "liste" en une face de type "mat" est effectuée par la fonc- tion face-mal. Bm = f l ° O 1 k O O 46 FORMES PARFAITES A SEPT VARIABLES Par cette transformation linéaire inversible, C est envoyé sur un cône convexe saillant C, de dimension maximale, dont les arêtes sont caractérisées par les colonnes de BlU. Pour les mêmes raisons que tout à l'heure, les faces de C sont envoyées bi- jectivement sur les faces de C, et, plus généralement, B crée une bijection entre les fa- cettes de C et celles de C. Si v = (vj, V2,..., vn) est un vecteur normal à une face de C, on vérifie sans peine que v B nous donne un vecteur normal à la face correspon- dante de C. Notre problème de départ est donc ramené au calcul des faces de C.} Lorsque le nombre d'arêtes du domaine est égal à sa dimension, on devine les vecteurs normaux aux faces de C. Le vecteur e; = (0, 0,..., 0, 1, 0,..., 0), vecteur dont toutes les composantes sont nulles, excepté la i^"16 qui vaut l, est perpendiculaire à la icmc face. Les lignes de la matrice B définissent, dans ce cas, les vecteurs normaux aux faces de C'.4 Dans le cas où le nombre d'arêtes est supérieur à la dimension, on effectue le relèvement de C, en ayant préalablement réordonné les s - N dernières arêtes de telle sorte que le calcul des groupes de symétries Hk soit optimal. Mais on reviendra plus tard sur le choix et le calcul effectif des Hk.5 Pour visualiser le relèvement de C, on peut contempler la matrice carrée sxs sui- vante, obtenue à partir de la matrice BITL : Bm f X ° 0 1 ^ Ô 0 ( 0 0 0 0 V, o o 0 10 A 0 matrice (s - N)xN 0 0/ 3 Dans le programme, la matrice B est enregistrée dans la structure B-I. La matrice BTTl n'est pas en- tièrement mémorisée; en effet, seule sa partie de droite (*•¦»), qui contient l'information intéressante, est stockée dans une structure appelée matmin. La procédure qui ordonne Ic calcul de B-I cl celui de matmin est enumerer-faces. C'est clic aussi qui gère les différentes étapes de l'algorithme de la cascade et provoque le traitement séparé du cas particu- lier où le nombre d'arêtes est égal à la dimension du domaine. 4 La procédure qui traite ce cas particulier et regroupe ces faces en orbites s'appelle normales-areles- faces. 5 Lc calcul des faces, au sommet de la cascade, est effectué par inil-faces; ensuite, tout saut dans l'algorithme de la cascade est effectué pat projeter, mis à part le dernier qui est réalisé par projeier-naf. ALGORITHME DE VORONOI 47 On appellera cette grande matrice la matrice BlH augmentée. Elle est de rang maximal. Par construction du relèvement, Ck est l'enveloppe convexe des arêtes carac- térisées par les colonnes de cette matrice, pour peu qu'on ne considère que les k pre- mières lignes de cette matrice. Une face étant caractérisée par la liste des arêtes qu'elle contient, elle sera mé- morisée dans le cadre de cet algorithme, sous forme d'un entier à s bits (O ou 1) dont le ièmc 5it vaut o si et seulement si la icmc arête de Ck est dans cette face. Avec cette repré- sentation, l'intersection de deux faces se calcule simplement en appliquant un "ou" lo- gique entre les deux entiers qui les représentent. On dira qu'un entier caractérise une face si les arêtes correspondant aux bits O de cet entier caractérisent cette face. En d'autre terme, cela signifie que cet entier retient suffisamment d'arêtes de cette face. On dira qu'un entier mémorise une face s'il retient exactement toutes les arêtes de cette face. Il peut arriver que deux entiers différents ca- ractérisent la même face; par contre, deux entiers différents (à s bits significatifs) ne peuvent jamais mémoriser la même face. Pour appliquer l'algorithme de la cascade, le théorème 4 montre qu'il nous faut une procédure capable de déterminer si un entier donné mémorise une face de Ck. J'ai développé une procédure, un peu plus générale, qui permet de déterminer, tout aussi rapidement, si un entier donné caractérise une face de Ck. Il s'agit de vérifier que les représentants des arêtes retenues par cet entier engendrent un hyperplan et que toutes les arêtes de Ck sont du même côté de cet hyperplan. La méthode standard procède de la manière suivante : 1) Construire une matrice dont les colonnes sont les représentants des arêtes retenues par notre entier. 2) Vérifier que ces représentants engendrent un hyperplan, c'est-à-dire que le rang de cette matrice est inférieur de 1 au nombre de ses lignes et vaut donc k-1. 3) Calculer un vecteur normal à cet hyperplan. 4) Vérifier que le produit scalaire de ce vecteur avec les représentants des arêtes ne change pas de signe. L'inconvénient de cette méthode réside dans sa lenteur... Pour chaque face potentielle à tester, il faut en quelque sorte inverser une matrice kxk; ensuite seulement, on peut décider si l'hyperplan est bien positionné.6 La méthode que j'ai développée est beaucoup plus fine. Des tests d'arrêts (pour les mauvais candidats) ont lieu plus rapidement; on peut souvent éliminer une face Dans la situation qui nous intéresse (n=7, N=28), k varie entre 28 et 63. 48 FORMES PARFAITES A SEPT VARIABLES potentielle avant même de savoir si sa codimension est bonne; on travaille avec des matrices dont les dimensions sont beaucoup plus petites.7 Pour comprendre cette méthode, regardons plus attentivement la matrice BTl augmentée. Les colonnes de cette matrice sont de trois types, disons (a), (b) et (c). Les N premières sont de type (a), les k - N dernières de type (c) et celles qui restent de type (b). Soit F, une face de Ck; deux cas peuvent se présenter : (i) F contient toutes les arêtes de type (c); (ii) une seule arête de type (c) n'est pas dans F. En effet, si davantage d'arêtes de type (c) n'étaient pas dans F, la codimension de F ne pourrait être égale à 1. Le cas (ii) se traite théoriquement. Les (k-N) faces de ce type ne sont, en fait, pas même mémorisées. Il suffit presque de savoir qu'elles existent! Leurs vecteurs normaux sont les ej pour N < j S k. Ces faces sont des faces maximales et leurs or- bites sont réduites à un élément. Les calculs chercheront uniquement à caractériser les orbites de faces satisfaisant les hypothèses du cas (i). Seule précaution à prendre : lorsqu'on passe de Ck+1 à Ck, la (k+l-N)cmc avant-dernière arête qui est de type (c) pourCk+1, devient de type (b) pourCk. La projection par itk+1 de l'intersection d'une face maximale de Ck+1 ne conte- nant pas une des (k-N) dernières arêtes avec une face quelconque de Ck+1, ne peut ca- ractériser qu'une face de Ck satisfaisant les hypothèses du cas (ii). Par conséquent, la seule orbite de faces de Ck+1, non mémorisée, qui peut intervenir dans le calcul des faces (satisfaisant les hypothèses du cas (i)) de Ck, est l'orbite à un élément qui corres- pond à la face maximale de Ck+1 ne contenant pas la (k+l-N)^110 avant-dernière arête et qui satisfait les hypothèses du cas (ii) en dimension k + 1. Avant de commencer le calcul des faces de Ck satisfaisant les hypothèses du cas (i), on complétera donc la liste des orbites mémorisées de faces de Ck+1 en lui ad- joignant l'orbite à un élément décrite ci-dessus. Dans le cas (i), une arête au moins de type (a) n'est pas dans la face. Sinon, la face serait un cône de dimension maximale! Dans la description qui suit, on suppose donné un entier caractérisant une face potentielle F devant satisfaire les hypothèses du cas (i). Il s'agit de tester si, oui ou non, les arêtes retenues dans cet entier caractérisent effectivement une face. en général inférieures à dix, pour les formes à sept variables. ALGORITHME DE VORONOI 49 Les (k-N) dernières composantes du vecteur normal à cette face potentielle n'ont, en fait, jamais besoin d'être calculées. La jcmc composante (N < j £ k) du vec- teur normal ne peut influencer que le produit scalaire entre ce vecteur normal et un quelconque vecteur caractérisant la (s+N+l-j)imc arête, arête de type (c). Cette com- posante est définie a posteriori, dès que l'on connaît les N premières composantes du vecteur normal, de telle façon que la (s+N+l-j)cmc arête soit perpendiculaire au vec- teur normal. En réalité, elle n'est jamais calculée explicitement parce que seules les N premières composantes peuvent jouer un rôle décisif. Pour les mêmes raisons, les arêtes de type (c) n'interviennent plus directement dans le calcul. 8 Si exactement une arête de type (a) n'est pas retenue dans notre entier, le seul vecteur normal à F possible (à multiple positif près) coïncide sur ses N premières composantes avec le vecteur C1, où i est l'indice de l'arête de type (a) exclue. Dans ce cas, la codimension ne pouvant être supérieure à 1, il suffit de vérifier que la icmc composante des représentants des arêtes de type (b) retenues dans F est toujours nulle (vérification que la codimension vaut exactement 1) et que la ièmc composante des représentants des autres arêtes de type (b) n'est jamais négative (l'hyperplan considéré est un hyperplan d'appui). Si c'est le cas, notre entier caractérise une face F. Pour que cet entier mémorise cette face F, il faut mettre à O les bits correspondant aux arêtes de type (b) non encore retenues et dont la ièmc composante du représentant est nulle. En effet, ces arêtes appartiennent à F. Etudions maintenant la situation générale, c'est-à-dire celle où deux arêtes au moins de type (a) ne sont pas retenues dans notre entier. Les composantes du vecteur normal correspondant aux arêtes de type (a) rete- nues dans notre entier doivent valoir O. Les autres doivent être positives ou nulles. L'influence des arêtes de type (a) s'arrête là. Seules les arêtes de type (b) intervien- dront dans la suite du calcul. Pour ne pas stocker inutilement des O, on ne mémorisera pas la totalité des N premières composantes du vecteur normal à F, mais uniquement celles qui correspon- dent à des arêtes de type (a) non retenues. Ce "sous-vecteur" sera noté G). Supposons qu'il y ait t arêtes de type (a) non retenues dans l'entier à tester; (û possède donc exactement t composantes. On extrait de BTTL ' une petite matrice T 10, dont les lignes sont formées des représentants des arêtes de type (b) retenues dans la face potentielle, représentants dont 8 Les calculs décrits ci-après sont effectués, dans le programme, par la fonction face? ou par une de ses variantes. 9 matmin dans le programme. 10 mat-l-t dans le programme. 50 FORMES PARFAITES A SEPT VARIABLES on ne prend que les composantes correspondant aux arêtes de type (a) non retenues. On obtient ainsi une matrice à t colonnes, t S 2. Pour que la face potentielle ait la bonne dimension, il faut et il suffit que le rang de T vaille (t -1). En particulier, il est nécessaire que le nombre de lignes de T soit supérieur ou égal à (t - 1). Si cette condition sur les dimensions de T n'est pas satis- faite, il n'est pas nécessaire de poursuivre le test : l'entier dont on est parti ne caracté- rise pas une face. Dans l'exemple qui suit, la matrice T obtenue est une matrice possédant 6 lignes et 5 colonnes. Exemple : (n=4, N=IO, 8 arêtes de type (b)) entier à tester écrit en base 2: 0...0 10010000 0111010010 (6 arêtes de type (b) sont retenues, t = 5) arêtes de type (a) arêtes de type (b) arêtes de type (c) 0100101110 00001001 0...0 0 1 ****** 0 0 1 ****** 0 1 ****** J ****** ]_ ****** 0 fig. 9 Si T possède suffisamment de lignes, on cherche co perpendiculaire aux lignes de cette matrice. Je rappelle que les composantes de co doivent être positives ou nulles. Effectuer des opérations de lignes élémentaires sur T n'affecte pas tû. Par des opérations de lignes élémentaires, on essaie de trianguler supérieurement la matrice T en mettant des l sur la diagonale. Si le rang de T est inférieur à t, le processus de triangulation doit s'arrêter avant qu'on ait pu traiter la dernière colonne de T. Si le processus s'arrête et si j colonnes ont pu être traitées, 0 S j < t, on pose la (j+l)tmc composante de û) égale à l et les suivantes (s'il y en a) moralement égales àO. ALGORITHME DE VORONOI 51 Les composantes précédentes de co peuvent maintenant être calculées à l'aide des lignes supérieures de la matrice. Si une composante est négative, on est déjà sûr que l'entier de départ ne caractérise pas une face, bien que l'on ne connaisse pas en- core le rang de T et bien que le vecteur normal ne soit pas encore entièrement calculé. Si une composante est nulle, on introduit l'arête correspondante de type (a) dans la face potentielle. Lorsque les composantes de co sont connues, on introduit dans la face poten- tielle toutes les arêtes de type (a) correspondant aux dernières composantes de co posées moralement égales à O. A ce stade, le rang de T n'est pas encore forcément connu. Si nécessaire, on termine la triangulation de T en ayant effectué préalablement un saut d'une colonne. Cela permet de vérifier que le rang de T vaut effectivement t -1, c'est-à-dire que les représentants des arêtes retenues par l'entier à tester engendrent un hyperplan. Reste à tester co sur les arêtes de type (b) non encore retenues. Le "produit sca- laire" de co avec une arête de type (b) non encore retenue se fera bien sûr via les com- posantes du représentant de cette arête correspondant aux arêtes de type (a) non rete- nues. On calcule en fait le produit scalaire de ce représentant et du vecteur normal à F. Si le "produit scalaire" de co avec une de ces arêtes de type (b) est négatif, l'entier ne caractérise pas une face (toutes les arêtes ne sont pas du même côté de l'hyperplan); si le "produit scalaire" de cd avec une de ces arêtes de type (b) est nul, cette arête appartient à F et doit donc être introduite dans l'entier caractérisant la face potentielle. Si aucune obstruction n'a été rencontrée au cours du calcul, l'entier de départ complété mémorise une face F. A partir de co, il est facile de reconstituer un vecteur normal à cette face. En gé- néral, pourtant, cela n'est pas nécessaire; seule la liste complète des arêtes contenues dans la face nous intéresse. Par contre, lorsqu'on effectue le dernier saut dans l'algorithme de la cascade, il est judicieux de reconstituer un vecteur normal à la face. En effet, la plupart du temps, ce vecteur est réutilisé ultérieurement par d'autres procédures. Par exemple, ce vecteur est indispensable lorsqu'on veut calculer le domaine voisin.11 Reprenons maintenant la question des groupes de symétries Hk.12 1 ' Celte remarque explique pourquoi le dernier saut dans l'algorithme de la cascade est effectué par une procédure spéciale (projeler-naf), alors que les autres sauts sont réalisés par la procédure projeter. 12 Les deux types d'enregistrement utilisés pour mémoriser un élément du groupe des symétries sont les suivants : 52 FORMES PARFAITES A SEPT VARIABLES Supposons connu un système de générateurs du groupe des symétries de C. Notons LN l'ensemble de ces générateurs. Si les arêtes de C sont ordonnées, on peut définir Lk = {geLN | g fixe les k - N dernières arêtes de C) et prendre pour Hk le groupe engendré par les éléments de LX Pratiquement, on ordonnera les s - N dernières arêtes en essayant de maximiser IlM.'3 Lorsqu'une nouvelle face de Ck est connue, on calcule son orbite sous l'action du groupe Hk.M Par la suite, lorsqu'on devra tester un entier représentant une face po- tentielle, on vérifiera d'abord que cette face potentielle n'est pas contenue dans une des faces d'une orbite déjà connue.15 La représentation de l'information sous forme d'entiers s'avère très efficace, d'une part, parce que la densité d'information, rapport à la quantité de mémoire utilisée, est très grande et, d'autre part, parce que les opérations sur les bits des entiers jouent avec la représentation interne et physique des données informatiques. Le traitement comparatif des bits de deux entiers peut se faire à l'aide d'une seule instruc- tion logique simulant ainsi une architecture d'ordinateurs vectoriels. Une illustration des performances liées à cette représentation est donnée par le problème suivant qui peut se formaliser ainsi :16 - type "mal" matrice carrée mémorisant un aulomorphisme de la forme parfaite q. - type "ont" entier mémorisant l'action de cet aulomorphisme sur l'ensemble des arêlcs du domaine. Lc premier type est avant tout utilisé pour la saisie ou l'affichage d'un aulomorphisme. Le deuxième type d'enregistrement est beaucoup plus efficace, par exemple lorsqu'on doit effective- ment calculer l'orbite d'une face. Il s'agit, en fait, de mémoriser une permutation des arêtes du do- maine. Comme les domaines considérés (n S 7) possèdent au plus 63 arêtes, 6 bits suffisent toujours pour mémoriser l'indice d'une arête (63 < 26 ¦= 64). La numérotation "naturelle" en LISP commence à 0. Les s arêtes seront numérotées de 0 à s -1. Les blocs successifs de 6 bits de notre entier mémoriseront la permutation des arêtes du domaine de la fa- çon suivante : si l'arête numéro i a pour image l'arête numéro j, les 6 bits de notre entier à compter du bit 6i (y compris) mémoriseront j en base 2. NoU-C entier possédera 6s bits significatifs. Lorsque s vaut 63 (6s = 378), on appréciera les performances du langage LISP, langage qui accepte les entiers arbitrairement grands! La mémorisation d'une symétrie du domaine sous la forme d'un entier présente, entre autres avantages, celui de pouvoir identifier le groupe des symétries du domaine avec le groupe des symétries de C et le groupe des symétries de C. Cette représentation, d'autre part, comme je l'ai déjà mentionné, permet de considérer le groupe des symétries de Ck comme un sous-groupe du groupe des symétries de C. 13 La procédure qui définit les Lk, donc les Hk, s'appelle init-groupe; elle fait appel à Ia procédure arranger pour ordonner les s - N dernières arêtes. 14 La procédure qui calcule l'orbite d'une face est la procédure faces-equivalenies. 15 La procédure qui vérifie si Ia face potentielle n'est pas contenue dans une face déjà connue s'appelle nouveau-p. La gestion des faces de Ck est effectuée dans l'environnement de gestion-faces par des pro- cédures internes de cet environnement 16 Dans le programme, ce problême est résolu par la fonction nouveau-p (fonction interne de gestion- faces). ALGORITHME DE VORONOI 53 On se donne un ensemble ordonné E (ensemble d'arêtes dans notre cas) à s éléments et une liste L = {Pi, P2.....Pp) de parties de E (les faces déjà connues par exemple). Soit P une partie quelconque de E, est-elle contenue dans un des éléments de la liste L? Une partie de E sera représentée par un entier à s bits significatifs, le j0"10 bit va- lant O si et seulement si le jème élément de E est dans cette partie. Tester si P est con- tenu dans P, revient à tester si, à tout bit nul de P, correspond un bit nul de Pi. Considérons le tableau logique suivant : jèmc bit de P jcmc bit de Pi jèmc bit de l'entier-test O O O O 1 l 1 O O 1 1 O fig. 10 Pour effectuer ce test, on appliquera un "et logique" entre le "complémentaire logique" de P et l'entier P;. Si le résultat vaut O, cela signifie que tous les bits tests sont nuls et, par conséquent, que P est contenu dans Pj. L'instruction LISP qui effectue ce test d'inclusion est la suivante : (zerop (logandcl P P{)). En remarquant qui si P est contenu dans Pj, les entiers P et P; satisfont P S Pj, on pourra même parfois éviter le test logique logandcl, grâce à l'instruction LISP sui- vante : (and (Z P PO (zerop (logandcl P Pi))). Lorsque le test d'inclusion est fréquent, le choix de cette deuxième instruction est tout à fait justifié, puisqu'en évitant parfois l'opération logique logandcl, il dé- charge une partie de la mémoire de travail interne de LISP et entraîne ainsi une dimi- nution de la fréquence d'appel au "garbage collector". Lorsque L possède quelques centaines d'éléments, la structure LISP utilisée pour mémoriser L sera simplement celle d'une liste, les éléments de cette liste étant les entiers représentant les parties de E contenues dans L. Le test d'inclusion de P se fera par un parcours séquentiel de cette liste : on testera successivement l'inclusion de P dans chacun des éléments de la liste. Le temps d'accès à l'information dépend plus ou moins linéairement de p, c'est-à-dire du nombre d'éléments de L. 54 FORMES PARFAITES A SEPT VARIABLES Mais lorsque la liste L possède plusieurs milliers d'éléments, le test séquentiel peut être très long. On adoptera dans ce cas une autre représentation interne de l'information contenue dans L. Considérons la pxs-matrice de bits (p = nombre d'éléments de L, s = nombre d'éléments de E) dont l'élément à la icmc ligne et à la j6"10 colonne est égal au j6"10 bit du iimc élément de L. Les éléments de L correspondent aux lignes de cette matrice. La deuxième façon de mémoriser L consiste à travailler avec les s colonnes de cette ma- trice. Ainsi, L sera mémorisée à l'aide d'un vecteur Ç à s composantes, chaque com- posante étant un entier avec p bits significatifs. Lorsqu'une orbite possède 40000 élé- ments par exemple (p = 40000), les entiers mémorisés ont alors pour ordre de grandeur 240000 dont le développement en base dix avoisine les douze mille chiffres. On appré- ciera à nouveau le fait que LISP travaille avec des entiers arbitrairement grands! L'avantage principal de cette deuxième représentation est que le temps d'accès à l'information ne dépend presque plus de p. Le temps nécessaire pour tester l'inclusion d'une partie P est pour ainsi dire le même si p = 20000 ou si p = 40000. Le test d'inclusion de P s'effectue en appliquant un "ou inclusif logique" sur les composantes de Ç correspondant aux bits nuls de P. Le icmc bit de l'entier-test ainsi obtenu vaut 0 si et seulement si P est contenu dans le itmc élément de L. La fonction LISP logcount compte instantanément le nombre de bits égaux à 1, d'un entier donné; pour savoir si P est contenu dans un élément de L, il suffira de comparer le nombre de bits égaux à 1 dans notre entier-test avec le nombre d'éléments de L. 8.3.2. Algorithme de l'explorateur : Lorsque la taille d'un domaine (différence entre son nombre d'arêtes et sa di- mension) est grande,17 l'algorithme de la cascade n'est plus assez efficace.18 L'utilisation de l'algorithme de l'explorateur se révèle indispensable. 8.3.2.1. Description : L'algorithme de l'explorateur est avant tout basé sur la notion de faces voisines, notion développée dans le paragraphe 4.3. Cet algorithme se base sur les corollaires du théorème 7 en utilisant, de plus, le groupe des symétries du domaine, ce qui loca- lise considérablement le problème et, par conséquent, le simplifie. 17 empiriquement supérieure à 8. 18 En particulier, les domaines associés à E6 et à E7 y résistent. ALGORITHME DE VORONOI 55 D'une certaine manière, l'algorithme de l'explorateur est un "algorithme de Voronoï" pour les faces d'un domaine, un "algorithme de Voronoï" en profondeur. La première phase consiste à récolter les faces du domaine déjà connues. Prati- quement, dans les cas qui nous intéressent, on trouve toujours parmi ces faces au moins une face qui n'est pas maximale. Si tel n'était pas le cas, il faudrait en calculer une; mais il est toujours facile de trouver une face, même non maximale; la difficulté est de s'assurer qu'on les a toutes à équivalence près! L'existence de faces non maxi- males est garantie par le corollaire 1 du théorème 7. Parmi les faces récoltées, on en retiendra une par classe d'équivalence rencon- trée, c'est-à-dire par orbite sous l'action du groupe des symétries du domaine. Pour chaque face retenue non maximale, on calculera l'ensemble de ses faces voisines. Parmi toutes ces faces voisines, certaines, probablement, seront équivalentes à une face déjà rencontrée, d'autres, peut-être, seront nouvelles. On continuera alors l'exploration à partir de ces nouvelles faces. Plus précisément, pour chaque nouvelle orbite rencontrée de faces non maxi- males, on choisira un représentant pour lequel on calculera toutes les faces voisines et ainsi de suite, jusqu'à ce que toutes les faces voisines de toutes les faces connues soient équivalentes à une des faces connues. La connexité du graphe des faces d'un domaine garantit alors qu'on a un repré- sentant de chaque orbite. Le procédé s'arrête puisque le nombre de faces étant fini, le nombre d'orbites, a fortiori, est aussi fini. Il faut tout de même faire la remarque évidente suivante : si deux faces sont équivalentes, toute face voisine de la première est équivalente à une face voisine de la seconde. Le problème est maintenant le suivant : étant donné une face F d'un domaine, calculer ses faces voisines. L'intersection de F avec une de ses faces voisines est une facette de codimen- sion 2 du domaine donc, par le lemme 2, une face de F. Inversement, si f est une face de F, par le lemme 1, f est une facette de codi- mension 2 du domaine. Par le lemme 5, seules exactement deux faces du domaine contiennent f. La face F en est une; l'autre est une face voisine de F; c'est la face voi- sine de F, par rapport à f. Par conséquent, il s'agit de calculer les faces de F. 8.3.2.2. Symétries : Considérons H, le sous-groupe des symétries du domaine qui stabilise la face F. 56 FORMES PARFAITES A SEPT VARIABLES H agit sur les faces de F et les organise en orbites. On dira que deux faces fi et Î2 de F sont équivalentes si elles appartiennent à la même orbite, c'est-à-dire s'il existe heH.telque f2 = h»fi. Notons Fj, la voisine de F par rapport à fj (i = l, 2). Observons que h«Fi est une face du domaine qui contient f2. Comme h stabilise F, h-Fj est une face différente de F. Par unicité de la face voisine de F par rapport à fa F2 = h-Fj. Comme h est une symétrie du domaine, on conclut que Fj et F2 sont deux faces équivalentes. En résumé, à deux faces équivalentes de F correspondent deux faces voisines équivalentes; cette remarque nous permet de prendre H comme groupe des symétries de F. Pour appliquer l'algorithme de l'explorateur, il suffit de calculer les faces de F, à équivalence près." La description du calcul des faces de F, à équivalence près, et des faces voisines correspondantes est un cas particulier de la situation générale décrite dans le para- graphe suivant 8.3.3. 8.3.3. Fusion de ces deux algorithmes : 8.3.3.1. Description : L'algorithme de l'explorateur ramène, d'une certaine manière, le calcul des faces d'un domaine au calcul des faces de ses faces. Une face F d'un domaine D est aussi un cône convexe saillant. On désire calculer les faces de ce cône convexe F modulo l'action d'un groupe H de symétries. Si la taille de F est petite,20 on appliquera comme précédemment l'algorithme de la cascade mais, cette fois-ci, au cône convexe saillant F. Si, par contre, la taille de F est trop grande, on fera appel récursivement à l'algorithme de l'explorateur pour calcu- ler les faces de F. L'algorithme de l'explorateur appliqué à F ramène le calcul des faces de F au calcul des faces des faces de F et ainsi de suite : si f est une face de F, le calcul des faces de f sera effectué par l'algorithme de la cascade si la taille de f est petite, ou par l'algorithme de l'explorateur appliqué récursivement à f, si la taille de fest encore trop grande. L'algorithme de l'explorateur contourne les faces maximales. Ainsi, un appel à cet algorithme diminue toujours, non seulement la dimension, mais également la taille 19 Pour décider si deux faces d'un même domaine sont équivalentes ou non, sans devoir calculer leurs orbites, on fera appel à la fonction dans-la-meme-orbitc, fonction qui tente de construire un élément du groupe des symétries du domaine, qui envoie la première face sur la seconde (cf 8.6.3). 20 empiriquement inférieure ou égale à 8. ALGORITHME DE VORONOI 57 des cônes convexes saillants sur lesquels on espère pouvoir appliquer l'algorithme de la cascade, ce qui garantit l'efficacité de l'exploration.21 L'utilisation recursive de l'algorithme de l'explorateur crée des chaînes de cônes convexes saillants, où chaque chaînon est une face du chaînon précédent : C = Co ^ Ci ^> C2 ^...^ Ci, où pour i ä l, C; est un cône convexe saillant, face de C;_i et facette de codimension i de C. Nous appellerons une telle chaîne une chaîne inclusive de faces. Si G = Ho est le groupe des symétries de C, on définit inductivement, pour i compris entre 1 et t, Hj, le groupe des symétries de Ci par la condition suivante : Hj est le sous-groupe de Hj.j qui stabilise C;. Cette définition des Hj, comme au paragraphe 8.3.2.2, garantit qu'à deux faces de Cj, équivalentes par l'action de Hj, correspondent deux faces de Cn, voisines de Cj, équivalentes par l'action de Hj.j. 8.3.3.2. Implementation en LISP : Même si, dans la définition généralisée de l'algorithme de l'explorateur, on fait parfois appel récursivement à cet algorithme, il n'est pas nécessaire d'automatiser cette récursivité.22 21 Généralement, mais cela est un résultat tout à fait empirique, le gain sur la taille est important. Si C représente le domaine de Voronoï d'une forme parfaite dont le nombre de variables est inférieur ou égal à sept, ou une facette d'un tel domaine, la plus grande taille d'une face non maximale de C dépasse très rarement les 5 de la taille de C. Exemples importants : (i) C = domaine associé à E7 (63 arêtes); une face F de C contient au plus 46 arêtes; taille C = 63 - 28 = 35 taille F = 46 - 27 = 19. (ii) C = domaine associé à D7 (42 arêtes); à équivalence près, une seule face F de ce domaine contient plus de 27 arêtes et elle en contient 36; taille C = 42 - 28 = 14 taille F = 36 - 27 = 9. 22 Lorsqu'on doit calculer les faces d'un cône convexe Ct défini par une certaine chaîne, le choix de calculer ces faces à l'aide de l'algorithme de la cascade ou, au contraire, en faisant appel récursivement à l'algorithme de l'explorateur, peut être laissé à la libre appréciation de l'utilisateur. J'ai choisi cette op- tion dans !'implementation de l'algorithme de l'explorateur afin de garder un contrôle permanent des choix importants cl de l'état des calculs. Cette option est également motivée par certaines contraintes liées à des temps de calculs importants. Lorsque la résolution d'un problême demande plusieurs jours, voire plusieurs semaines à un ordina- teur, il ne faut pas être tributaire de certains aléas (maintenance des machines et des logiciels, orages, coupures de courant, etc.) qui peuvent interrompre prématurément l'exécution du programme. Autrement dit, je me suis fixé, a priori, la contrainte suivante : mes programmes doivent pouvoir être stoppés à n'importe quel moment (même brutalement) ct ensuite relancés sans qu'aucune erreur ne puisse s'introduire ct sans que cette manoeuvre ne coûte plus d'une heure de temps de calcul. 58 FORMES PARFAITES A SEPT VARIABLES Lorsque l'on veut traiter l'élément C[ d'une chaîne inclusive de faces, c'est-à-dire calculer les faces de C1 à l'aide de l'algorithme de l'explorateur, il faut commencer par définir cette chaîne inclusive de faces.23 Si un domaine D possède une face F pour laquelle le domaine voisin est équiva- lent au domaine associé à En, l'équivalence appliquée à F nous donne une face du do- maine associé à En." Le théorème 10 et sa démonstration montrent que les faces ainsi récoltées carac- térisent des orbites distinctes et que ces orbites contiennent toutes les faces du domaine associé à En correspondant aux voisines de En contenues dans une des autres classes connues de formes parfaites. La cardinalité de ces orbites sera calculée en appliquant le lemme 8. Dans ce cas, on est sûr, a priori, que l'algorithme de l'explorateur ne permettra de découvrir que des faces pour lesquelles le domaine voisin est équivalent au domaine associé à En, ou éventuellement des faces correspondant à des voisines de En apparte- nant à de nouvelles classes de formes parfaites.25 23 Cette définition est effectuée, dans le programme, par un appel à la procédure trajectoire. Parmi les formes parfaites dont le nombre de variables est inférieur ou égal à sept, seules E6 et E7 possèdent des domaines qui requièrent l'utilisation de l'algorithme de l'explorateur. C'est pourquoi, dans !'implementation du programme, lorsqu'une chaîne inclusive de faces est définie, on suppose que C0 est Ic domaine associé à En (n = 6 ou 7). Suivant la longueur de la chaîne inclusive de faces, le niveau de profondeur d'application de l'algorithme de l'explorateur change. Pour traiter le domaine associé à E6, le premier niveau a été lar- gement suffisant. Par contre, pour traiter le domaine associé à E7, il a fallu recourir à l'algorithme de l'explorateur jusqu'au cinquième niveau de profondeur, c'est-à-dire appliquer cet algorithme à des fa- cettes de codimension 4 du domaine associé à E7. 24 Un appel à la procédure recotter-faces-En permet de récolter les faces du domaine associé à En déjà connues, en parcourant les fichiers d'orbites de faces des domaines associés aux autres formes parfaites. 25 Au premier niveau, on applique l'algorithme de l'explorateur au domaine associé à En lui-mômc. Dans ce cas, l'appel à la procédure trajectoire n'est pas nécessaire; formellement, on devrait effectuer (trajectoire '(J)). Lc préfixe standard pour les noms des procédures qui agissent à ce niveau est Ta-". Par exemple, la gestion des représentants des orbites de faces du domaine associé à En a lieu dans l'environnement défini par fa-gestion-tiste-a-sauver, environnement dans lequel ils sont numérotés; l'accès à un tel représentant se fait via l'instruction (fa-c-s ). le paramétre étant le numéro de ce représentant; la procédure fa-enumerer-faces applique l'algorithme de la cascade à une face du domaine associé à En et calcule donc les faces de cette face; la procédure fa-toutes-Ies-voisines calcule toutes les faces voisines d'une face du domaine associé à En. Des le second niveau d'application de l'algorithme de l'explorateur, un appel préalable à la procédure trajectoire est indispensable. Pour le second niveau, l'appel sera de la forme (trajectoire '(I )) où est le numéro d'une face F de En. Lc préfixe standard pour les noms des procédures qui agissent à ce niveau est "fa-inf-". Un appel à la procédure recolter-faces permettra de récolter les faces de F déjà connues, en parcourant les listes éventuelles d'orbites de faces des autres faces du domaine associé à En : si une face F de ce domaine possède une face f dont la face voisine correspondante est équivalente à F, l'équivalence ap- pliquée à f nous donne une face de F. A nouveau, le théorème 10 et sa démonstration montrent que les faces ainsi récoltées appartiennent à des orbites de faces de F distinctes. ALGORITHME DE VORONOI 59 Pour appliquer l'algorithme de la cascade à une quelconque facette F de dimen- sion d du domaine associé à En, il faut, certes, quelque peu adapter !'implementation décrite en 8.3.1.3; pourtant, l'adaptation est minime. La gestion des représentants des orbites de faces de F a lieu dans l'environnement défini parfa-inf- gestion-lisle-a-sauver, environnement dans lequel ils sont numérotés; l'accès à un tel représentant se fait via l'instruction (fa-inf-c-s ), le paramètre étant le numéro de ce représentant; Ia procédure fa-inf-enumerer-faces applique l'algorithme de la cascade à une face f de F et calcule donc les faces de f; la procédure fa-inf-toules-les-voisines calcule toutes les faces voisines d'une face fdeF. Lorsque l'algorithme de l'explorateur appliqué à F s'arrête, c'est-à-dire lorsqu'on connaît, à équivalence près, toutes les faces de F, un appel à Ia procédure fa-enumerer-faces-from-inf permet de traduire cette information de telle façon qu'on ne puisse plus distinguer si les faces de F ont été calculées à l'aide de l'algorithme de la cascade, ou à l'aide de l'algorithme de l'explorateur. Celte traduction est indispen- sable si l'on désire pouvoir utiliser ultérieurement la procédure fa-toules-les-voisines qui, à l'aide des faces de F, calculera toutes les faces voisines de F. A partir du troisième niveau d'application de l'algorithme de l'explorateur, l'appel à la procédure trajectoire sera pour le (t+l)fcme niveau (trajectoire '(I it Ì2—Ì1)) où ij signifie qu'on prend pour Ci la face numéro ij de Cj.]. Lc préfixe standard pour les noms des procédures qui agissent à ce niveau est "under-". II arrive sporadiquement, lorsqu'on travaille à un certain niveau, qu'on doive accéder à des données et/ou à des procédures des niveaux supérieurs. Par exemple, lorsqu'on travaille au deuxième niveau de profondeur où le préfixe standard est "fa-inf-", il arrive qu'on fasse appel à Ia procédure (fa-c-s...), procédure qui vit au premier niveau, ou même à (c-s...) qui vit dans un certain sens au niveau O. C'est pourquoi, à partir du troisième niveau de profondeur (préfixe standard "under-"), il est nécessaire d'introduire deux autres préfixes relatifs aux niveaux supérieurs : le préfixe "over-" qui correspond exactement au niveau précédent de profondeur, et le préfixe "super-" qui correspond à deux niveaux précédents de profondeur. Un appel à la procédure recolter-faces-over permettra de récolter les faces de Ct déjà connues, en par- courant les listes éventuelles d'orbites de faces des autres faces de Ct_i : si une face F de Cw possède une face f dont la face voisine correspondante est équivalente à C1, l'équivalence appliquée à f nous donne une face de Ci. Pour les mêmes raisons que précédemment, les faces ainsi récollées caractérisent des orbites de faces de C1 distinctes. La gestion des représentants des orbites de faces de C1 a lieu dans l'environnement défini par under- gestion-liste-a-sauver, environnement dans lequel ils sont numérotés; l'accès à un tel représentant se fait via l'instruction (under-c-s ), le paramètre étant le numéro de ce représentant; la procédure under-enumerer-faces applique l'algorithme de la cascade à une face f de Ct et calcule donc les faces de f; la procédure under-touies-lcs-voisines calcule toutes les faces voisines d'une face fdcCf Lorsque l'algorithme de l'explorateur appliqué à C1 s'arrête, c'est-à-dire lorsqu'on connaît à équivalence près toutes les faces de C1, un appel à Ia procédure over-enumerer-faces-from-under permet de traduire cette information de telle façon qu'on ne puisse plus distinguer si les faces de C1 ont été calculées à l'aide de l'algorithme de la cascade, ou à l'aide de l'algorithme de l'explorateur. Celte traduction est in- dispensable si l'on désire pouvoir utiliser (lors d'un appel ultérieur à la procédure trajectoire au niveau précédent de profondeur) la procédure under-toutes-les-voisines qui, à l'aide des faces de la itÈmc face de Ct.i, calculera toutes les faces de C1., voisines de cette it^me face. ¦ . Dans l'environnement défini par fa-gestion-liste-a-sauver, les faces du domaine associé à En sont mé- morisées dans des structures de type "mat", c'est-à-dire sous forme matricielle. Dans les environne- ments définis parfa-inf-gestion-liste-a-sauver et under-gestion-lisie-a-sauver, les représentants des orbites de faces ne sont plus des faces du domaine associé à En et sont mémorisées dans une structure de type "cm", en tant que facettes du domaine associé à En. 60 FORMES PARFAITES A SEPT VARIABLES Tout d'abord, donnons une définition d'un vecteur v normal à une face f de F, qui facilitera cette adaptation, tout en étant suffisante pour les besoins effectifs des cal- culs. On dira qu'un vecteur v, dans l'espace de Voronoï, est normal à une face f de F si v est perpendiculaire à toute arête de f et si le produit scalaire de v avec un représen- tant d'une arête de F qui n'est pas dans f est toujours positif. La définition naturelle, plus stricte, aurait exigé en plus que v appartienne au plus petit sous-espace qui con- tient F mais, comme nous le verrons plus loin, cette restriction n'est pas utile. On définit C comme en 8.3.1.3, mais en ne retenant que les arêtes du domaine associé à En contenues dans F. Pour simplifier les notations, on supposera que F contient exactement s arêtes; s est donc inférieur au nombre d'arêtes du domaine as- socié à En. Le calcul des faces de F est ramené au calcul des faces de C Après renu- mérotation éventuelle, on peut supposer que les représentants des d premières arêtes de C sont linéairement indépendants, puisque F est de dimension d. On construit, comme précédemment, la Nxs-matrice TH qui contient toute l'information du problème. Par des opérations élémentaires de lignes uniquement, on peut transformer TTL en une matrice dont le bloc dxd, en haut à gauche, est une matrice identité et dont les (N - d) dernières lignes ne contiennent que des 0. Donc, il existe une matrice B inversible telle que : ( 1 0 0 1 BTH= V o o f 0 0 0 0 V o o 0 0 * * J 0 o) d premières lignes N-d dernières lignes On définit C, comme tout à l'heure, à l'aide des colonnes de BTH,, ce qui ra- mène, à nouveau, notre problème de départ au calcul des faces de C. D'autre part, si v = (vi, V2,..., vn) représente un vecteur normal à une face de C, on vérifie sans peine que v B nous donne un vecteur normal à la face correspondante de C, vecteur qui se traduira instantanément en un vecteur normal (au sens où nous l'avons défini dans ce paragraphe) à la face correspondante de F. Les N-d dernières composantes de v n'ont aucune importance; on peut, par exemple, les fixer à 0, ce qui nous autorise à ne considérer que les d premières lignes de la matrice B lors du calcul de v B. ALGORITHME DE VORONOI 61 La suite se déroule exactement comme en 8.3.1.3 pour peu qu'on remplace N par d et qu'on efface les (N - d) dernières lignes de BTH, celles qui ne contiennent que des 0.26 Lorsque deux facettes du domaine associé à En, f et f, sont équivalentes en tant que facettes de ce domaine, l'équivalence envoie les faces de la première sur les faces de la seconde. La connaissance des faces de f évite alors le calcul des faces de f à l'aide d'un des deux algorithmes généraux.27 Etant donné que le groupe des symétries de f peut dépendre du choix de la chaîne qui conduit jusqu'à f, même si f et f sont équivalentes, leurs groupes de symé- tries ne sont pas toujours comparables. En particulier, deux faces de f, équivalentes par l'action du groupe des symétries de f, ne correspondent pas toujours à deux faces de f, équivalentes par l'action du groupe des symétries de f. Pour calculer les faces de f à l'aide de celles de f, on traduira donc toutes les faces de f (indépendamment de leur appartenance ou non à une même orbite) et on re- calculera les orbites de faces de f en appliquant le groupe des symétries de f .28 26 Lorsqu'on applique l'algorithme de la cascade à une facette F du domaine associò à En, bien que F soit mémorisée dans une structure de type "ent" en tant que facette du domaine associé à En, les faces de F (resp. des cônes obtenus en relevant F) sont mémorisées dans des structures de type "ent" en tant que faces de F (resp. faces des cônes obtenus en relevant F), c'est-à-dire comme sous-cnscmblcs des arêtes de F (resp. des cônes obtenus en relevant F). Cc codage dépend de la manière dont sont ordon- nées les arêtes de F. Les paires de vecteurs minimaux de En correspondant à des arêtes de F sont mé- morisées dans une liste, comme propriété de F, sous le nom de 'minimaux. Leur ordre dans cette liste définit la numérotation des arêtes de F. Lc codage d'une facette f du domaine associé à En en une facette f d'une facette F de ce domaine est ef- fectué par les fonctions coder-ifa, coder-over, coder-under, suivant Ia codimension de la facette F. La traduction inverse d'une facette f d'une facette F du domaine associé à En en une facette f du do- maine associé à En s'effectue en utilisant l'information contenue dans un entier mémorisé comme pro- priété de F sous le nom de 'conversion. Lc nombre de bits significatifs de cet entier vaut exactement six fois le nombre d'arêtes de F. Les six bits à compter du bit 6j (y compris) mémorisent le numéro de la j4mo arête de F vue comme une arête du domaine associé à En. Lorsqu'on trouve une nouvelle face f d'une facette F du domaine associé à En, on mémorisera son or- bite par l'action du groupe des symétries de F, comme propriété de f, sous le nom de 'orbite. Cela permettra ultérieurement de tester si une autre face de F est nouvelle ou si, au contraire, clic est équi- valente à une face de F déjà rencontrée. Les éléments d'une orbite de face de F seront mémorisés dans des structures de type "ent", en tant que facettes de F et non pas en tant que facettes du domaine associé à En, ce qui économise de la mémoire : les entiers qui codent ces facettes possèdent ainsi un nombre plus petit de bits significatifs. Bien que ces divers codages exigent certaines conversion, l'économie de mémoire qui s'ensuit justifie pleinement leur utilisation. Dc même, les éléments du groupe des symétries d'une facette F seront mémorisés dans des structures de type "ent", via leur action sur les arêtes de F et non pas sur les arêtes du domaine associé à En; le calcul des orbites des faces de F ne s'en trouvera que facilité. 27 Lc calcul des faces d'une facette f du domaine associé à En peut prendre plusieurs heures lorsque Ia taille de cette facette est grande, voire même plusieurs jours si la taille de celle facette exige que le cal- cul de ses faces s'effectue à l'aide de l'algorithme de l'explorateur. 28 II peut arriver que deux facettes f et f d'une facette F du domaine associé à En soient équivalentes par l'action du groupe des symétries du domaine associé à En bien qu'elles ne soient pas équivalentes par l'action du groupe des symétries de F. C'est pourquoi le préfixe "pseudo-" est employé pour ca- 62 FORMES PARFAITES A SEPT VARIABLES Afin de pouvoir être éventuellement réutilisées ultérieurement, les faces de f doi- vent être mémorisées.29 L'exemple suivant est un cas particulier important à ne pas oublier. Lorsqu'une face f de F est maximale, il n'est pas nécessaire de calculer ses faces pour appliquer l'algorithme de l'explorateur à F. Mais lorsque toutes les faces de F sont connues, il est trivial, a posteriori, de calculer les faces de f : ce sont les intersections de f avec les autres faces de F. Si la taille de fest grande, on effectuera ce calcul afin de retenir les faces de f. En effet, il peut arriver qu'une face f maximale de F soit équivalente, par l'action du groupe des symétries du domaine associé à En, à une face f d'une facette F, sans pour autant que f soit maximale dans F. Reste à décrire l'algorithme qui calcule les faces voisines dans le cadre de l'algorithme de l'explorateur.30 Soit un cône D, une face F de D et une face f de F. Le but est de calculer et de caractériser F, l'unique face de D voisine de F par rapport à f. On supposera que D est une facette d'un domaine C, ou éventuellement C lui-même, et que C vit dans RN.31 On a donc : N = dim C £ dim D = (dim F) + 1 = (dim F + 1) = (dim f) + 2. Supposons connus nF et nr des vecteurs normaux respectivement à F et à f, au sens défini dans ce paragraphe; ces vecteurs np et nf satisfont les conditions ci- dessous, où a caractérise une arête quelconque de D : np«a = 0 si aeF np«a>0 si aeD, a*F nr.a = 0 si aef nr«a>0 si aeF, a*f. Le produit scalaire utilisé est le produit scalaire usuel de KN. Je rappelle que nF et nf n'appartiennent pas forcément à L(D), le plus petit sous- espace de R qui contient D. Le produit scalaire de np (resp. nf) avec les vecteurs caractérisant des arêtes de C qui ne sont pas dans D (resp. dans F) peut être quelconque (négatif, positif ou nul); cela n'a pas d'importance. On cherche à calculer F et np un vecteur normal à F satisfaisant : np'«a = 0 si aeF et np'«a>0 si aeD, a$F. raclériscr les procédures qui cherchent ou utilisent celle equivalence par l'action du groupe des symé- tries du domaine associé à En. 29 Pour ne pas submerger le disque dur de l'ordinateur (!), on ne retiendra les faces de f que si la taille de f est suffisamment grande (en fait supérieure à cinq). La gestion des facéties retenues, ainsi que de leurs faces, est essentiellement effectuée dans le programme par les procédures dont le préfixe est "g-d-" (signifiant "grand-delta", c'est-à-dire grande différence entre le nombre d'arêlcs cl Ia dimension). 30 Dans le programme, la procédure qui effectue ce calcul s'appelle chercher-faces-voisines. 31 D, F, f et F seront mémorisées dans des structures de type "cnl", en lant que facettes de C. ALGORITHME DE VORONOI 63 A nouveau, np n'a pas besoin d'appartenir à L(D). Décomposons R en somme directe de L(D) et de son complémentaire orthogo- nal L(D)1. Tout vecteur n peut être décomposé comme somme de n* et de n-1- où n* est un vecteur de L(D) et n-1- un vecteur de L(D)-1-. Représentons la situation dans un 2-plan de L(D) orthogonal à f. fig. Il Les vecteurs np* et nf* ne sont pas parallèles car, si a caractérise une arête de F qui n'appartient pas à f, on observe que nr*«a > O, alors que np*»a = O. Par consé- quent, le vecteur np* peut s'écrire comme combinaison linéaire de nf* et tip*. En ob- servant de plus que le vecteur a ci-dessus satisfait nF*«a > O, on déduit que le co- efficient devant nf*, dans cette combinaison linéaire, est positif; après normalisation éventuelle, on peut supposer que ce coefficient vaut l. Il existe donc un nombre ß, tel que nF* = nf* + ß np*. H est clair que le produit scalaire entre np* et un vecteur caractérisant une arête quelconque de f est nul, quelle que soit la valeur de ß. D'autre part, F et F n'ont comme arêtes communes que celles qui sont dans f. Regardons les arêtes de D qui ne sont pas dans F. F en contient au moins une. Soit a', un vecteur caractérisant une telle arête. Ce vecteur satisfait np*«a' = 0. D'autre part, le produit scalaire entre np* et un vecteur caractérisant une arête quelconque de D qui n'est pas dans F doit toujours être supérieur ou égal à zéro. On tire de ces deux conditions : ß = V . = -^- et ß ä f.* = ——- quel que soit le vecteur a caractérisant r nF «a IW r nF .a n,.-a n n une arête de D qui n'est pas dans F. On pose donc ß = max ^- où le vecteur a caractérise à tour de rôle chacune nF »a des arêtes de D qui n'est pas dans F. 64 FORMES PARFAITES A SEPT VARIABLES L'ensemble des arêtes de F est réunion de deux ensembles : l'ensemble des arêtes de f et l'ensemble des arêtes de D qui n'appartiennent pas à F, caractérisées par un vecteur a vérifiant -^- = ß. Pour terminer, on définit np' par l'égalité suivante : np = nf + ß np. 8.4. Calcul automatique des voisines : 8.4.1. Description : Reprenons les notations du chapitre 5. Nous supposerons données la matrice Q d'une forme parfaite et 1, une matrice mémorisant un vecteur normal à une face F du domaine associé à Q. On cherche à dé- terminer Q' la voisine de Q relativement à F. Nous avons vu qu'il existe une valeur de p positive telle que Q' = Q + p 1, que le minimum de Q est égal au minimum de Q + 0 1 si et seulement si 9 appartient à l'intervalle [ 0, p ] et que la forme Q' possède au moins un vecteur minimal vsZn qui n'est pas minimal pour Q. En contemplant l'égalité vl Q(p) v = v'Qv + pv'lv = min Q et en se rappelant que vl Q v > min Q, on déduit que vl 1 v est négatif. Par conséquent, si 8 S ° ,v-, la forme Q(8) n'est plus définie positive. min Q v1 Qv -v11 v fig. 12 Il est facile de voir que si Q(0') est définie positive pour une certaine valeur po- sitive de 8', Q(8) est définie positive pour toute valeur de 0 appartenant à l'intervalle [ 0, 0' ]. Il existe donc une valeur limite R pour 6, telle que Q(8) soit définie positive si 0 appartient à l'intervalle [ 0, R [, et indéfinie si 8 est supérieur à R. ALGORITHME DE VORONOI 65 Le graphe de min Q(6) sur l'intervalle [ O, R [ est une courbe continue, con- cave, composée de segments (fig. 12). 8.4.2. Implementation en LISP : L'algorithme qui décrit ce calcul se décompose en deux parties.32 La première partie consiste à trouver une valeur de 0 strictement comprise entre p et R, c'est-à-dire pour laquelle Q(9) est définie positive et min Q(8) < min Q.33 La seconde partie utilise cette valeur de 0 pour déterminer la valeur exacte de p.34 32 La procédure pcrmctlant le calcul automatique de Q' s'appelle voisine. 33 Prcintórc partig : Lc programme fait d'abord appel à la fonction grand-R qui rend une valeur de 9 supérieure à p. La fonction grand-R construit, en fait, une suite O1, O2,... satisfaisant O1 = 1 et 6; = 3 Q;.u et s'arrête des que Q(G;) n'est plus définie positive, ou que le minimum de Q(Oi) est strictement inférieur au mi- nimum de Q. Ensuite, la fonction osciller fournit une valeur de Ô strictement comprise entre p cl R. La fonction osciller construit récursivement une suite d'intervalles emboîtés de la forme [ aj, bj ] avec aj = 0 et a: + b: bi = valeur rendue par la fonction grand-R. Elle arrête sa recherche dès que Q(—^—) est définie posi- tive et de minimum strictement inférieur au minimum de Q. Lc principe est le suivant : si QC-1I—t) n'est pas définie positive, on continue la recherche avec , a, + bj aj+i - a; et b;+1 - 2 ; sinon, - si le minimum de Qfr^ï—') est égal au minimum de Q, on continue la a: + b; recherche avec a;+1 =—j— et b;+I = b;; a; + b; - sinon, on arrête la recherche; la valeur —^— est une solution de notre problème. 34 Seconde partie : On suppose connue une valeur de 0 strictement comprise entre p cl R. Il existe alors au moins un vec- teur veZ" satisfaisant vl Q(O) v < min Q. Cc vecteur v ne peut pas cire un vecteur minimal de Q. On calcule une nouvelle valeur pour 0 de telle manière que v1 Q(O) v soit égal au minimum de Q : on i ,> min Q - v' Q v remplace G par--------,.-----s— . Pour cette nouvelle valeur de 6, si min Q(O) < min Q, on recommence; sinon 0 est égal à la valeur de p, et v est un vecteur minimal de Q' qui n'est pas minimal pour Q. La procédure recursive minimiser effectue le travail décrit dans cette deuxième partie. Elle commence, en fait, par chercher les paires de vecteurs ±veZn satisfaisant v1 Q(O) v < min Q. Si elle trouve un vecteur pour lequel cette inégalité est stricte, elle poursuit sa recherche récursivement, après avoir calculé la nouvelle valeur de 0. 66 FORMES PARFAITES A SEPT VARIABLES 8.5. Identification automatique des voisines : Géométriquement, en terme de réseaux, il s'agit, en fait, de résoudre automati- quement (et si possible rapidement!) le problème suivant : Soit deux réseaux de Rn donnés par les matrices de Gram de deux de leurs bases respectives; ces deux réseaux sont-ils équivalents ? Dans ce qui suit, on utilisera plutôt le langage des formes quadratiques. 8.5.1. Description : Soit deux formes quadratiques définies positives données par les matrices A et B qui leur sont associées. Ces deux formes sont équivalentes si et seulement si il existe un nombre réel positif A, et une matrice S dans GLn(Z), tels que A = X S1 B S. Après normalisation éventuelle, on peut supposer A et B de même minimum Ct de même déterminant. Notre problème consiste à exhiber, si elle existe, une matrice S à coefficients entiers, telle que A = S' B S. Considérons vi, V2,..., vp (vjsZ"), un quelconque système de générateurs de Zn. Nous allons voir que S existe si et seulement si on peut trouver wj, W2,..., wp (wjsZn) tels que v;1 A vj = Wj' B Wj (Vij). Si S existe, il suffit de poser w; = S vj, i = 1, 2.....p. Pour montrer la réciproque, considérons V (resp. W), la matrice dont les co- lonnes sont les Vj (resp. les wj). L'hypothèse devient V^AV = W1BW. Dire que les vj forment un système de générateurs de Zn revient à dire qu'il existe une matrice U à p lignes et n colonnes, à coefficients entiers, telle que le produit V U soit égal à la matrice identité. Posons S = W U. S est à coefficients entiers et vérifie A = S' B S. D'un point de vue algorithmique, étant donné vi, V2,..., vp, un système bien choisi de générateurs de Zn, la recherche des wj, W2,..., wp sera une recherche en arbre avec une très forte heuristique, avant tout basée sur la notion de spectre. Notion de spectre : Soit A, la matrice d'une forme quadratique définie positive. Si ±x, ±y sont deux paires de vecteurs à coefficients entiers, on définit leur spectre relatif par : <±x, ±y>A = —t—t Ix1AyI. J " min A ' ' Soit E, un ensemble fini, non-vide, de paires ±y de vecteurs à coefficients en- tiers; on définit le spectre de ±x par rapport à E par : ALGORITHME DE VORONOI 67 spectreA(±x, E) = (Ca1 nO (a2 n2)...(ak nk)) où la liste (Ca1 nj) (a2 n2)...(ak nk)) satisfait les conditions suivantes : pour toute paire ±y dans E, il existe aj, dans cette liste, tel que aj soit égal à < ±x, ±y >A; pour tout i, n; est positif et compte le nombre de paires ±y dans E satisfai- sant < ±x, ±y >a = ai; la suite des a, est strictement croissante. Si S appartient à GLn(Z), S(E) désignera l'ensemble des paires ±Sy où ±y ap- partient à E. Pour r S l, on notera 33(A,r), l'ensemble des paires ±y satisfaisant < ±y, ±y >A < r; tß(A,r) est toujours un ensemble fini, non-vide. Considérons maintenant A et B, deux matrices associées à des formes quadra- tiques définies positives. S'il existe SeGLn(Z), telle que A = S' B S, on a l'identité spectrale suivante : < ±x, ±y >A = < +Sx, ±Sy >b- On en déduit que spectreA(±x, E) = spectreB(±Sx, S(E)) Vx.VE, et que S(tß(A,r)) = tß(B,r) VrSl. Revenons au problème du calcul des wj, les vj étant connus. Considérons ÎB(A,r) contenant tous les ±vj, avec r minimal pour cette propriété. Par ce qui précède, on voit que les ±w; doivent appartenir à tß(B,r), ce qui limite déjà considérablement les choix possibles pour w;. Mieux; comme spectreA(±vj, 33(A,r)) = spectreB(±wj, tß(B,r)), on voit que l'ensemble des images possibles, a priori, pour vj est réduit à l'ensemble des x tels que ±xeîB(B,r) et spectreB(±x, IB(B,r)) = spectrea(±vj, tö(A,r)). La valeur de r dépend des vj. Dans la pratique, il est très avantageux de choisir les Vj de façon à minimiser r. La situation particulière qui nous intéresse est l'identification des formes par- faites en dimension inférieure ou égale à sept. Dans ces dimensions, quelle que soit la forme parfaite, on peut toujours extraire de ses vecteurs minimaux une base de Zn. Cette propriété facilite considérablement les calculs. Cela montre, en particulier, qu'on peut prendre pour r la valeur minimale, c'est- à-dire l. L'heuristique sera donc basée sur le spectre des vecteurs de cette base par rapport à Ho(A,l), c'est-à-dire par rapport à l'ensemble des vecteurs minimaux de A. Par abus de langage, on appellera spectre d'un vecteur minimal, son spectre par rapport aux autres vecteurs minimaux de la forme, spectre calculé à l'aide de cette forme justement. L'heuristique se traduit ici de la manière suivante : Wi doit être un vecteur mini- mal de B dont le spectre est égal au spectre de vj. 68 FORMES PARFAITES A SEPT VARIABLES 8.5.2. Implementation en LISP : Les bases retenues pour les formes parfaites en dimension inférieure ou égale à sept ont été choisies en fonction du représentant mémorisé pour chacune des classes.35 Lorsqu'on désire identifier une forme parfaite B avec l'un des représentants des classes déjà connues, on cherche d'abord le numéro probable de la classe de B en cal- culant certains invariants : valeur du déterminant lorsque le minimum vaut 2 (normalisation), nombre de vecteurs minimaux, ensemble des spectres des vecteurs minimaux.36 Ensuite seulement, on essaie d'identifier B avec le représentant A de cette classe d'équivalence à l'aide d'une recherche en arbre avec forte heuristique.37 Soit Vi, V2,...,vn une base de Zn formée de vecteurs minimaux de A. On tente en fait de découvrir un n-tuple (wi, W2,...,wn) de vecteurs minimaux de B dont la matrice de Gram par rapport à B est égale à la matrice de Gram des v; par rapport à A. La liste mémorisée 1-m des vecteurs minimaux de B ne contient qu'un représen- tant par paire de vecteurs opposés. Un vecteur wj sera représenté par deux éléments : l'indice de son représentant dans l-m, le signe de wj par rapport à ce représentant (+1 signifie que w, est égal à ce représentant; -l signifie que wj est l'opposé de ce représentant). On commence par calculer pour chaque vi, la liste Ij des indices des vecteurs de l-m dont le spectre est égal au spectre de vj. L'indice du représentant de w, devra ap- partenir à Ij. Ce sont les listes 1, qui contiennent l'heuristique. On peut toujours supposer, sans perdre de généralité, que le signe de W1 est +1 : S est solution de notre problème si et seulement si -S est solution de notre problème. Chaque sommet de l'arbre de recherche mémorise un n-tuple (wj, W2,...,wn) partiellement rempli. La gestion des sommets de l'arbre de recherche se fait à l'aide d'une pile de type L.I.F.O. (Last In, First Out). Au départ, on introduit dans la pile, en parcourant la liste d'indices h, les sommets correspondant aux différentes images possibles pour le premier vecteur de base. Ensuite, la boucle principale de recherche est la suivante : 35 Ces bases sont de trois types : - type 1 base : C1, C2,..., Cn S = W = (w„w2.....wn) -typc2 1OSCiC11C2.....Cn-L-C1H-Cn S = (W1. W2,..., w, + Wn) - type 3 base : C1, C2,..., Cn.], - C1 - C2 + Cn S = (W1, w2.....W1 + w2 + wn) On pourra donc ainsi facilement calculer S à partir des wj. La procédure qui effectue ce calcul s'appelle mal-chgl-base-lype. 36 La fonction qui, dans Ic programme, effectue celte recherche s'appelle candidal-equi. 37 Cette deuxième recherche est effectuée par la fonction chercher-équivalence. ALGORITHME DE VORONOI 69 si la pile est vide, la recherche a échoué; sinon, on extrait le sommet en tête de pile; si ce sommet correspond à un n-tuple de Wj complètement rempli, la recherche a abouti; sinon, on calcule tous les sommets successeurs de ce sommet et on les introduit en tête de pile. Reste à décrire le calcul des successeurs d'un sommet. Supposons que ce sommet corresponde à un n-tuple de w;, partiellement rempli, c'est-à-dire où sont mémorisées les valeurs associées aux (k-i) premiers Wj. Il s'agit de calculer les valeurs possibles pour w^. Les candidats sont construits en parcourant la liste d'indices Ik- Pour chaque élément de Ik, on engendre deux va- leurs pour Wk, celle correspondant au signe positif et celle correspondant au signe né- gatif. Pour chacune de ces valeurs, on compare la matrices de Gram de wi,..., Wk et celle de vj,..., Vk. Plus précisément, si v;1 A Vk = w,1 B Wk pour tout i compris entre l et k-l, cette valeur de Wk définit un sommet successeur. Ce dernier test, couplé avec l'heuristique, permet d'éviter en grande partie le "backtracking" intrinsèquement lié à une recherche en arbre, d'où la performance du programme.38 8.6. Variantes de l'algorithme décrit au paragraphe 8.5 : 8.6.1. Calcul automatique du groupe des automorphismes : 8.6.1.1. Description : Un élément du groupe des automorphismes de A est, d'une certaine manière, une matrice S qui identifie A avec elle-même : A = S'A S. Pour connaître le groupe des automorphismes de A, il est suffisant de le con- naître modulo ±identité. Pour calculer ce groupe, il suffit de modifier la boucle princi- pale de l'algorithme décrit en 8.5 dans le sens suivant : si la pile est vide, la recherche est terminée; tous les éléments du groupe des automorphismes de A sont connus modulo +identité; 38II suffit, en général, d'une dizaine de secondes environ pour exhiber S, si elle existe, et d'une tren- taine de secondes pour démontrer, dans le cas contraire, que S n'existe pas. 70 FORMES PARFAITES A SEPT VARIABLES sinon, on extrait le sommet en tête de pile; si ce sommet correspond à un n-tuple de wj complètement rempli, il caractérise un élément du groupe cherché; on retient cet élément et on poursuit la recherche; sinon, on calcule tous les sommets successeurs de ce sommet et on les introduit en tête de pile. 8.6.1.2. Implementation en LISP : Le groupe des automorphismes d'une forme parfaite peut être très gros. On ne retiendra donc en général qu'un système de générateurs de ce groupe.3' 8.6.2. Calcul automatique du stabilisateur d'une face : Le stabilisateur d'une face du domaine associé à une forme parfaite A est un sous-groupe du groupe des symétries de ce domaine, donc un sous-groupe du groupe des automorphismes de A modulo iidentité. Supposons que la face considérée est donnée par une matrice F. On peut re- prendre tel quel l'algorithme de 8.6.1 en testant de plus, avant de le retenir définitive- ment, chaque élément S qui vient d'être calculé, afin de vérifier que S1FS = F. Remarquons que, dans cette situation, on peut affiner l'heuristique mémorisée dans les listes d'indices 1;. Notons E, l'ensemble des paires de vecteurs minimaux de A correspondant à des arêtes contenues dans F. Dans l'algorithme général, j appartient à Ij si et seulement si le spectre du jcmc vecteur de 1-m (liste mémorisée des vecteurs minimaux de A) est égal au spectre de Vj, le iemc vecteur de base. Ici, on exigera de plus que le spectre par rapport à E de la paire de vecteurs minimaux de A, représentée par le jème élément de 1-m, soit égal au spectre de ±v; par rapport à E.40 39 La procédure chercher-sys-gen calcule automatiquement un système de générateurs du groupe des automorphismes d'une forme parfaite A modulo ± identité. Elle fait appel pour cela à Ia fonction chercher-new-auto, variante de Ia fonction chercher-équivalence. 40 Dans Ie programme, la procédure qui calcule automatiquement le stabilisateur d'une face d'un do- maine s'appelle calculer-groupe. Elle fait appel à la fonction chercher-new-auto-face, variante de la fonction chercher-équivalence. Au départ, une dizaine de secondes sont nécessaires au programme pour définir un environnement adapté à la recherche des éléments du groupe; ensuite, en moyenne, trois éléments de ce groupe sont calculés chaque seconde. ALGORITHME DE VORONOI 71 8.6.3. Tests d'équivalence entre facettes d'un même domaine : Il s'agit ici de pouvoir décider rapidement si deux facettes données, Fi et F2, du domaine associé à une forme parfaite A sont équivalentes, c'est-à-dire si Fi et F2 sont dans la même orbite de facettes par l'action du groupe des symétries du domaine. On désire pouvoir faire ce test sans expliciter l'orbite d'une de ces facettes.41 Notons Ej, l'ensemble des paires de vecteurs minimaux de A associés aux arêtes du domaine contenues dans Fj. Les facettes Fi et F2 sont équivalentes si et seulement si il existe une matrice S représentant un élément du groupe des symétries du domaine vérifiant S(Ei) = E2. Il s'agit d'exhiber, si elle existe, une telle matrice S. En particulier, Ei et E2 doivent contenir le même nombre d'éléments. Comme précédemment, la condition S(Ei) = E2 permet d'affiner l'heuristique. Dans l'algorithme général, j appartient à Ij si et seulement si le spectre du jème vecteur de 1-m est égal au spectre de vj, le icmc vecteur de base. Ici, on exigera, de plus, que le spectre par rapport à E2 de la paire de vecteurs minimaux de A représentée par le j^™ élément de l-m, soit égal au spectre de ±v, par rapport à Ej. Finalement, la boucle principale de recherche sera la suivante : si la pile est vide, la recherche a échoué; sinon, on extrait le sommet en tête de pile; si ce sommet correspond à un n-tuple de W1 complètement rempli, on calcule l'élément S du groupe qui lui correspond; si S(E]) = E2, la recherche a abouti; sinon, on poursuit la recherche; sinon, on calcule tous les successeurs de ce sommet et on les intro- duit en tête de pile. 41 Dans Ie programme, on distingue deux cas. Si F1 et F2 sont des faces du domaine, mémorisées sous forme matricielle, le test d'équivalence peut se faire à l'aide de la fonction dans-la-meme-orbile qui vit dans l'environnement défini par la procédure init-dans-la-meme-orbite. Si F1 et F2 sont deux facettes du domaine, mémorisées dans des structures de type "ent", l'équivalence entre F1 et F2 sera testée par la fonction pseudo-equivalent qui vit dans l'environnement défini par la procédure init-pseudo-equivaient. Il faut, en général, entre dix et vingt secondes pour décider si deux facettes données sont équivalentes ou si, au contraire, elles appartiennent à des orbites de facettes distinctes. 72 FORMES PARFAITES A SEPT VARIABLES 9. Conclusion : Les calculs que j'ai effectués sur ordinateur démontrent qu'il n'y a que trente- trois classes de formes parfaites en dimension sept, mais les résultats de ces calculs contiennent des informations beaucoup plus précises. Ils permettent, par exemple, de connaître le nombre exact d'orbites de voisines d'une certaine forme parfaite, qui sont contenues dans une classe donnée; ils décrivent ainsi complètement l'évaluation de la fonction f du théorème 10 sur les classes d'équivalence des domaines de Voronoï. Les tableaux suivants résument cette information. Par le théorème 10, on sait qu'ils doivent être symétriques. Dimension 2 : I AMmIn.!) ] Q] fJTJ |3 i rj QQ Dimension 3 : I *l,(miii»I)"1 Q] Q] i' i q m uj Dimension 4 : ti til tin fig. 13 fig. 14 fig. 15 Dimension 5 : I