Ordres du groupe symétrique

Le groupe symétrique 

Structure de groupe sur les permutations

La définition 1.1.1 donne une description des permutations en terme de mots sur l’alphabet 1, . . . , n. On peut aussi les interpréter comme des bijections de {1, . . . , n} vers {1, . . . , n}. Dans ce cas, le mot correspondant à la permutation est simplement la lecture des images. Par exemple, la permutation µ = 4213 est l’application qui envoie 1 sur 4, 2 sur 2, 3 sur 1 et 4 sur 3. Vu de cette façon, l’ensemble des permutations de taille n forme un groupe non commutatif dont la loi est la composition des applications. L’élément neutre est la permutation identité, c’est-à-dire le mot 123 . . . n. Par exemple, si σ = 2314 et µ = 4213, on a 25 Ordres du groupe symétrique 26 Chapitre 2 — Ordres du groupe symétrique σµ := σ ◦ µ = 4321, (2.1) µσ := µ ◦ σ = 2143, (2.2) σ −1 = 3124. (2.3) Un point fixe de σ est un entier i tel que σ(i) = i. La permutation identité ne contient que des points fixes. Le seul point fixe de la permutation µ = 4213 est 2. Une transposition est une permutation où seuls deux points ne sont pas fixes, on dit qu’elle « échange » deux valeurs. Par exemple, 153426 est la transposition qui échange 2 et 5 et on la note (2, 5). Une transposition simple est une transposition où les valeurs échangées sont consécutives, on l’écrit si := (i, i + 1). Lorsqu’on mutliplie par la droite une permutation σ par une transposition (i, j), cela revient à échanger les lettres en positions i et j dans σ. Si l’on multiplie par la gauche, alors on échange les valeurs i et j. Par exemple : 342615.(2, 5) = 312645 (2.4) (2, 5).342615 = 345612. (2.5) En tant qu’élément de groupe, une permutation peut se décomposer en un produit de cycles disjoints. Un cycle est une permutation particulière qui s’écrit (a1, a2, . . . , ar) et qui signifie que l’image de a1 est a2, l’image de a2 est a3, etc, et l’image de ar est a1. Les éléments qui n’apparaissent pas dans a1, . . . , ar sont des points fixes. Deux cycles c1 et c2 sont dits disjoints s’ils n’agissent pas sur les mêmes valeurs, c’est-à-dire si les éléments qui apparaissent dans c1 sont des points fixes de c2. Une permutation peut toujours s’écrire comme un produit de cycles disjoints. Par exemple, si σ = 524613, on a σ = (1, 5)(3, 4, 6). Le produit entre deux cycles disjoints est commutatif, on a aussi σ = (3, 4, 6)(1, 5). Cependant, la décomposition en cycle est unique à commutation des cycles près. Les cycles de taille 1 sont des points fixes et les cycles de taille 2 des transpositions ce qui justifie l’écriture (a, b) pour la transposition qui échange a et b. Le groupe sur les permutations est aussi appelé groupe symétrique et on le note Sn. Le groupe symétrique de taille n est engendré par les transpositions simples si pour 1 ≤ i < n et admet la présentation suivante : s 2 i = 1, (2.6) sisj = sjsi pour |i − j| > 1, (2.7) sisi+1si = si+1sisi+1. (2.8) Les relations (2.7) et (2.8) sont appelées relations de tresses. Elles ne sont pas propres au groupe symétrique. En particulier, on peut définir des déformations du groupe symétrique où seule la relation (2.6) est modifiée. C’est le cas par exemple de l’algèbre de Hecke que nous verrons dans le chapitre 3. 

Le groupe symétrique

Décompositions réduites et code

Toute permutation peut donc être écrite comme un produit de transpositions simples. On appelle cette écriture une décomposition de la permutation. Au vu des relations entre générateurs, elle n’est pas unique. La taille d’une décomposition est donnée par le nombre de générateurs qu’elle contient. Si la taille d’une décomposition est minimale, c’est-à-dire s’il n’existe pas d’autres décompositions de la permutation contenant moins de générateurs, on l’appelle une décomposition réduite de la permutation et sa taille définit la longueur de la permutation, notée ℓ(σ). Une permutation admet en général plusieurs décompositions réduites. Exemple 2.1.1. La permutation σ = 523461 admet entre autres comme décompositions réduites : σ = s4s3s2s1s2s3s4s5, (2.9) σ = s1s2s3s4s5s3s2s1, (2.10) elle est donc de longueur 8. Notons que si σ admet une décomposition réduite v, une décomposition réduite de σ −1 est simplement le retourné de v car s 2 i = 1. Une permutation et son inverse ont donc même longueur. La longueur d’une permutation est aussi donnée par son nombre d’inversions. Définition 2.1.2. Une inversion d’une permutation σ est un couple (i, j) avec i < j et σ(i) > σ(j). Une coinversion d’une permutation σ est un couple (a, b) tel que a < b et σ −1 (a) > σ−1 (b). Par exemple, les inversions de σ = 523461 sont (1, 2), (1, 3), (1, 4), (1, 6), (2, 6), (3, 6), (4, 6) et (5, 6) ses coinversions sont (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 5), (3, 5), et (4, 5). Une permutation est entièrement codée par ses inversions. On peut aussi utiliser son code de Lehmer. Définition 2.1.3. Le code de Lehmer (ou tout simplement code) d’une permutation σ est le vecteur v défini par v(i) = #{σ(j) < σ(i), j > i}. Par exemple, le code de la permutation σ = 523461 est v = [4, 1, 1, 1, 1, 0]. Le code de Lehmer suffit pour retrouver la permutation de départ. En effet, si v(1) = i, alors σ(1) = i+1. Puis si v(2) = j, alors σ(2) est le j +1ème nombre restant par ordre croissant et ainsi de suite. On peut donc travailler indifféremment avec une permutation ou avec son code. De façon évidente, pour n donné, il n’existe qu’une seule permutation de taille n qui n’ait pas d’inversions. C’est la permutation identité 12 . . . n dont la longueur est 0, c’est-à-dire dont la décomposition réduite est le mot vide. Il existe aussi une seule permutation de longueur maximale, donnée par n n − 1 . . . 1. Son code est [n − 1, n − 2, . . . , 1, 0] et sa longueur est donc n(n−1) 2 . On l’appelle la permutation maximale et on la note ω. Nous aurons besoin de deux autres notions sur les permutations. 28 Chapitre 2 — Ordres du groupe symétrique Définition 2.1.4. Une descente d’une permutation σ est une position i telle que σ(i) > σ(i + 1). Un recul de σ est une descente de σ −1 , c’est-à-dire une valeur a telle que σ −1 (a) > σ−1 (a + 1). Les descentes de la permutation 523461 sont 1 et 5, ses reculs sont 1 et 4.

Groupes de Coxeter

Le groupe symétrique appartient à une catégorie plus large de groupes appelés les groupes de Coxeter. Bien que l’objet principal de cette thèse soit le groupe symétrique, de nombreuses notions que nous abordons admettent une définition plus générale. Notre travail s’inscrit donc au sein de cette théorie et nous avons jugé utile d’en donner les définitions de base. Pour une approche plus complète, nous invitons le lecteur à lire [Hil82]. Définition 2.1.5. Un groupe de Coxeter est un groupe engendré par une famille de générateurs r1, . . . , rn admettant une présentation sous forme (rirj ) mij = 1 où mij ∈ N ∪ +∞ et vérifie : 1. mii = 1 2. mij = mji 3. mij ≥ 2 si i 6= j. Pour Sn, les générateurs sont s1, . . . , sn−1 et on a mij = 2 si |i − j| 6= 1 et mi i+1 = 3. Les groupes de Coxeter finis ont été classifiés dès 1935, ils correspondent à des groupes de réflexions dans l’espace euclidien. Le groupe Sn est appelé groupe de Coxeter de type A ou An−1. Les groupes de type BC et D seront abordés dans le chapitre 5 et nous en donnons donc une définition ici. Définition 2.1.6. Le groupe de Coxeter de type BC de taille n est le groupe engendré par l’ensemble des générateurs et relations de An (s1, . . . , sn−1) et un générateur supplémentaire s B n (aussi noté s C n ) vérifiant les relations : sis B n = s B n si pour i 6= n − 1 (2.11) sn−1s B n sn−1s B n = s B n sn−1s B n sn−1. (2.12) C’est-à-dire min = 2 pour i 6= n − 1 et mn−1 n = 4. Définition 2.1.7. Le groupe de Coxeter de type D de taille n est le groupe engendré par l’ensemble des générateurs et relations de An (s1, . . . , sn−1) et un générateur supplémentaire s D n vérifiant les relations : sis B n = s B n si pour i 6= n − 2 (2.13) sn−2s D n sn−2 = sn−2s D n sn−2. (2.14) C’est-à-dire min = 2 pour i 6= n − 2 et mn−2 n = 3. § 2.2 — Ordres faibles : treillis sur les permutations 29 Nous verrons dans le chapitre 3 que les groupes BC et D peuvent être identifiés respectivement aux permutations signées et permutations signées avec un nombre pair de négatifs. Les notions de décomposition réduite et longueur des éléments décrites dans le paragraphe 2.1.2 s’étendent naturellement à l’ensemble des groupes de Coxeter. De même, les descentes peuvent être définies comme suit : un générateur ri est une descente de σ si ℓ(σri) = ℓ(σ) − 1, c’est un recul de σ si ℓ(riσ) = ℓ(σ) − 1. Dans le cas du groupe symétrique, le générateur si est identifié à la position i et on dit que la permutation a une descente en i si si vérifie la propriété ci-dessus.