Coxeter

English version

Ordre de Bruhat

Le traitement de l'ordre de Bruhat sur le groupe est déterminant pour toutes les questions de polynômes de Kazhdan-Lusztig. La comparaison de deux éléments donnés ne pose pas de problème, comme on le rappelle ici. Mais pour effectuer ces comparaisons de façon massive, il faut utiliser d'autres moyens.

Dans notre implémentation, un groupe de Coxeter possède toujours une partie énumérée; c'est une partie finie P du groupe, qui est un idéal d'ordre pour l'ordre de Bruhat (cela signifie que si y appartient à P, et x <= y, alors x appartien à P), numérotée de façon croissante pour l'ordre de Bruhat, et pour laquelle on a tabulé les informations suivantes:

• le diagramme de Hasse de l'ordre de Bruhat (cela signifie que pour chaque y dans P on donne la liste des x qui sont immédiatement inférieurs à y);
• l'action à gauche et à des générateurs sur les éléments de P (dans la mesure où le résultat reste dans P);
• pour chaque y dans P, l'ensemble de descente, à gauche et à droite, de y (la principale raison de limiter le rang à la moitié du nombre de bits d'un mot-machine est de pouvoir faire tenir ces deux ensembles de descente ensemble sur un seul mot, sous forme d'un bitmap);
• les longueurs des éléments de P.

Au départ du programme, la partie énumérée est réduite au seul élément neutre e du groupe. Nous avons donné dans [1] un algorithme purement combinatoire, qui étant donnés une partie énumérée P et un élément y de W n'appartenant pas à P, permet d'énumérer le plus petit idéal d'ordre contenant P et y (qui est simplement la réunion de P et de l'intervalle [e,y]), et d'étendre à ce nouvel idéal les tables ci-dessus. Cet algorithme permet aussi de déterminer de façon raisonnablement efficace le bitmap représentant l'intervalle [e,y], pour un y quelconque dans P; cette extraction est l'un des piliers des calculs de Kazhdan-Lusztig.

En fait, les fonctions concernant l'ordre de Bruhat sont utilisées surtout de façon interne, et ne sont pas facilement accessibles pour l'utilisateur. L'étude purement combinatoire de l'ordre de Bruhat est un sujet fascinant, qui mériterait sans doute un programme (beaucoup plus élémentaire) pour lui-même; Coxeter ne contient malheureusement pas actuellement les fonctions, telles que l'extraction d'un intervalle de Bruhat entre deux éléments donnés, qu'on aurait pu souhaiter. Peut-être dans l'avenir?