Séminaire Lotharingien de Combinatoire, B33j (1994)

LONGUEUR DES INVOLUTIONS ET CLASSIFICATION

DES GROUPES DE COXETER FINIS

PAR

Paul MOSZKOWSKI

R^{}ÉSUM^{}É. — On donne une démonstration combinatoire simple d’un résultat concernant les involutions des groupes de Coxeter. La méthode fournit un renseignement nouveau qui permet d’obtenir la classification des groupes de Coxeter finis de manière purement algébrique.

ABSTRACT. — The paper contains a simple proof of a result on involutions in Coxeter groups. Our method yields a new piece of information which allows us to derive the classification of finite Coxeter groups in a purely algebraic way.

On rappelle qu’un système de Coxeter est un couple (W, S), où W est un groupe et S un ensemble générateur de W, assujetti seulement à des relations du type (ss′)^{m(s,s′)} = 1, avec m(s, s) = 1 et m(s, s′) = m(s′, s) ≥ 2 pour s ≠ s′ dans S. Lorsqu’aucune relation n’intervient pour un couple (s, s′), on pose m(s, s′) = ∞. On supposera connus les résultats préliminaires suivants, exposés par exemple dans les premières pages de ([2], chap. 5).

L’ordre de ss′ dans W est égal à m(s, s′) et S est un système générateur minimal de W.

Pour I ⊂ S le couple (⟨I⟩, I) est un système de Coxeter, ⟨I⟩ désignant le groupe dit parabolique) engendré par I. Si l_{I}(w) désigne la longueur relative à I d’un élément w par I (c’est-à-dire le plus petit entier n tel que w = s_{1} … s_{n}, avec s_{i} ∈ I (1 ≤ i ≤ n)), on a l_{I}(w) = L_{S}(w) = l(w).

Pour J ⊂ S on pose X_{J} = {w ∈ W, l(ws) > l(w), ∀ s ∈ J}. Les mots (ss′)^{m(s,s′)} comportant un nombre pair de lettres, on a soit l(ws) = l(w) + 1, soit l(ws) = l(w) − 1. De plus, on a la condition d’échange : (w ∈ X_{s}, s′w ∉ X_{s}) ⇒ s′w = ws.

Pour w dans W et J ⊂ S, il existe une décomposition unique w = xy avec x ∈ X_{J} et y ∈ ⟨J⟩; de plus, l(w) = l(x) + l(y).

On note T l’ensemble des conjugués des éléments de S (éléments également appelés générateurs de W). Pour w ∈ W on pose

I(w) = {t ∈ T, l(wt) < l(w)}.

P. MOSZKOWSKI

Par un argument de parité, on n’a jamais l(wt) = l(w) ; on a la condition d’échange forte : pour w = s_{1} … s_{n} (s_{i} ∈ S), si t ∈ I(w), alors il existe i tel que t = s_{n} … s_{i} … s_{n}.

Le groupe W est fini si et seulement s’il existe un élément w, dit maximal, tel que l(ωs) < l(ω) pour tout s de S. Dans ce cas ω est unique (et on pose ω = ω_{S}) et ω_{S}^{2} = 1. De plus, pour tout w dans W, on a l(ω_{S}) = l(ω_{S}w) + l(w).

Dans tout ce qui suit (W, S) est un système de Coxeter, d’ensemble de réflexions T. Les résultats a) et b) de la proposition suivante font l’objet de [1].

Proposition.

a) Si (W, S) est un système de Coxeter et si w ∈ W est une involution (w^{2} = 1), alors il existe I ⊂ S d’élément maximal ω_{I} conjugué à w et commutant avec chaque élément de I.

b) Pour I, J ⊂ S, si les éléments maximaux ω_{I} et ω_{J} commutent respectivement avec chaque élément de I et de J, alors ceux-ci sont conjugués si et seulement s’il existe x tel que x^{−1}Ix = J.

c) Si w est une involution, soit il existe I ⊂ S avec w = ω_{I}, soit il existe s ∈ S avec l(w) = l(sws)+2 et par conséquent il existe J ⊂ S tel que ω_{J} commute avec chaque élément de J et il existe x tels que w = w^{−1}ω_{J}x et l(w) = l(ω_{J}) + 2l(x).

Démonstration

a) c) Soit s_{1} … s_{n} une écriture réduite de w (s_{i} ∈ S), 1 ≤ i ≤ n, l(w) = n). On a s_{1} … s_{n} = s_{n} … s_{1} ; si s_{n−1} … s_{1} ∉ X_{s_{n}}, alors w possède une écriture réduite s_{n}σ_{1} … σ_{n−2}s_{n} et on raisonne par récurrence sur n; sinon, d’après la condition d’échange s_{n−1} … s_{1} = s_{1} … s_{n−1}. Par itération, si w ne possède pas d’écriture réduite sσ_{1} … σ_{n−2}s, alors w = s_{n−1} … s_{1}s_{n} = s_{n}s_{1} … s_{n−1} = ⋯ = s_{i+1} … s_{n}s_{1} … s_{i} pour 1 ≤ i ≤ n−1, donc l(ws_{i}) < l(w). Posant I = {s_{1}, …, s_{n}}, on a w ∈ ⟨I⟩, donc w = ω_{I}. S’il existe s ∈ I avec sω_{I} ≠ ω_{I}s, alors l(sω_{I}s) < l(ω_{I}), et on conclut par récurrence.

b) Soient I, J ⊆ S conjugués tels que ω_{I} et ω_{J} commutent respectivement avec tout élément de I et de J. Soit x de longueur minimale tel que ω_{J} = xω_{I}x^{−1} ; x ∈ X_{I} car sinon x possède une écriture réduite de la forme s_{1}, …, s_{n} avec s_{n} ∈ I et n n’est pas minimal. De même x^{−1} ∈ X_{J}, et xω_{I} = ω_{J}x avec l(xω_{I}) = l(x) + l(ω_{I}) = l(x) + l(ω_{J}). Pour s ∈ I, l(ω_{J}xs) = l(ω_{J}x)−1. Puisque x ∈ X_{I}, d’après la condition d’échange forte il existe une réflexion t de ⟨I⟩ telle que ω_{J}xs = ω_{J}tx et l(ω_{J}t) = l(ω_{J})−1. Or l(t) = l(ω_{J}) − l(ω_{J}t) = 1, donc t ∈ J. De même pour s ∈ J, x^{−1}sx ∈ I.

On montre maintenant comment a) et c) ci-dessus peuvent conduire à la classification des groupes de Coxeter finis [3].

GROUPES DE COXETER FINIS

Lemme 1 [4]. — Le mot s_{1}, … s_{n} est réduit si et seulement si par remplacements successifs de facteurs de type ss′s … de longueur m(s, s′) par les mots égaux s′ss′ … de même longueur on ne peut obtenir un mot contenant un facteur de type ss.

On dira qu’un mot est rigide si cette condition est vérifiée et si de plus tous les remplacements successifs possibles sont des commutations de générateurs (m(s, s′) = 2).

Lemme 2 [5]. — Si T′ ⊆ T, alors le groupe de réflexions ⟨T′⟩ engendré par T′ est un groupe de Coxeter dont un système de générateurs est l’ensemble S′ = {t ∈ T, I(t)∩⟨T′⟩ = {t}}. De plus l’ensemble de réflexions de ce système est T ∩ ⟨T′⟩, et l′ désignant la fonction longueur de ce système, on a {l(wt) > l(w) ⇔ l′(wt) > l′(w)} pour tout w de ⟨T′⟩ et tout t de T ∩ ⟨T′⟩.

Rappelons que le graphe G du système (W, S) a pour sommets les éléments de S, pour arêtes simples les paires (s, s′) telles que m(s, s′) = 3, et pour arêtes d’ordre m(s, s′) les paires (s, s′) telles que m(s, s′) > 3. La classification se ramène évidemment au cas où G est connexe. Lorsque G contient l’un des sous-graphes suivants, on voit facilement que le mot w^{p} est rigide (p > 0), et que le groupe correspondant est infini, possédant des éléments de longueur arbitraire :

1) le cycle 1, 2, …, n, w = 12 … n.

2) 1  2  3 k  k′ •  •  •  (k ≥ 6), w = 12123.
3) 1  2 n−1  n k  k′ •  •  •  •  (k, k′ ≥ 4), w = 1 … n … 2.

4) [figure: 1; •; 2; 3; n−1; n; k; •; •; •; •; (k ≥ 4), w = 1 … n … 3.]

5) [figure: •; 1; •; 2; 3; n−2; n; n−1; •; •; •; •; w = 1 … n(n − 2) … 3.]

6) 1  2  3  4 5 •  •  •  •  w = 123234.

Cet argument a été utilisé dans [4] pour les cas 1), 3), 4), 5). Par commodité on pose |s_{n} … s_{1} = s_{1} … s_{n} … s_{1}, et pour t, t′ dans T on note (t, t′) l’ordre de tt′.

Remarque 1. — Si t ≠ |s_{n} … s_{1} commutent avec w ∈ W et si t ∈ I(|s_{n} … s_{1}), alors il existe i ∈ [1, n − 1] tel que |s_{i} … s_{1} commute avec w. En effet, d’après la condition d’échange forte on a soit t = |s_{i} … s_{1}, soit t = s_{1} … s_{n} … s_{i} … s_{n} … s_{1} (1 ≤ i ≤ n−1), auquel cas (|s_{n} … s_{1})t = (|s_{i} … s_{1})(|s_{n} … s_{1}).

Remarque 2. — Si W est fini d’élément maximal ω, on sait que l’application s → ωsω est un isomorphisme de graphe car l(ωsω) = l(ω) − (l(sω)) = l(s), et pour s, s′ dans S, (ωsω, ωs′ω) = (s, s′).

Soit B_{n} le groupe

1 commute avec le groupe < {1, |12, 3…. , n} >. D’après le lemme 2 et la remarque 1 on a là les générateurs de ce groupe, dont le graphe est

car par conjugaison (|12, 3) = (1, |32) = (1, |23) = (|13, 2) = (1, 2) = 4. Par récurrence le groupe < {|12, 3, …, n} > est fini. D’après la remarque 2 son élément maxiaml ω commute avec 3, …, n car son graphe ne possède pas d’isomorphisme non trivial. On a l(ω1) > l(ω) ; si l(ω2) > l(ω), alors ω = ω_{{3,4,...,n}} d’après c) de la proposition ci-dessus, ce qui est absurde. On a donc l(1ωi) < l(1ω) pour tout i, donc B_{n} est fini, d’élément maximal 1ω.

Soit D_{n} le groupe

On montre par récurrence que D_{2p} est fini et que son élément maximal commute avec tous les éléments : 1 commute avec 1, 2, 4, …, n. En utilisant des pseudo-commutations de type ss′\underline{s} → \underline{s′}ss′ on peut construire une réflexion t = |s_{n} … s_{1}3 ∈ {1, 2, 3, 4} commutant avec 1 de la manière suivante : t1 = (|s_{n} … s_{1}3)\underline{1} ; on pose s_{1} = 1 ; s_{n} … s_{2}13\underline{1} = s_{n} … s_{2}\underline{3}13 ; on pose alors s_{3} = 3, s_{2} = 2 (ou s_{3} = 3, s_{2} = 4) ; s_{n} … s_{4}32\underline{3}13 = s_{n} … s_{4}\underline{2}3213 ; il existe i ∈ \{1, 2, 3, 4\} commutant avec \underline{2} mais ne commutant pas avec la lettre suivante \underline{2}, à savoir 4 ; on arrête alors la construction, posant t = |43213. On a t = |43213 = |23413 = |23143, donc par symétrie |43213 commute avec 2 et 4. On raisonne alors comme plus haut : t est générateur du groupe < {1, 2, 4, …, n, t}) car 3, |13, |213 = |23, |3213 = |2313 = |2131 = |231 ne commutent pas avec 1. Le graphe de ce groupe est Soit ω l’élément maximal du groupe < {t, 4, …, 2p} >. Par récurrence ω commute avec 4, 5, …, 2p. D’autre part l(ω1) > l(ω) et l(ω2) > l(ω). Si l(ω3) > l(ω), alors ω = ω_{{<4,...,2p>}}, ce qui est absurde, donc ω12 est l’élément maximal de D_{2p}, avec ω121ω12 = 1. Enfin, D_{4} est fini, car le mot |43213 est réduit, et l(t124i) < l(t124) pour 1 ≤ i ≤ 4.

Dans tout ce qui suit, les réflexions t proviennent du même algorithme, compte tenu des valeurs m(s, s′) particulières.

Soit F_{4} le groupe

4 commute avec 4, 1, 2, t = |3243, tous générateurs du groupe < {4, 1, 2, t} > car ni 3, ni |43, ni |243 = |23 ne commute avec 4. Le graphe correspondant est

car (|3243, 2) = (|3423, 2) = (|4323, 2) = (4, |2323) = (4, 2) = 2 et (|3243, 1) = (|32, 1) = (3, |12) = (3, |21) = (3, 2) = 4. Si ω est l’élément maximal de ce groupe, on a l(ω3) < l(ω) et ω4 est l’élément maximal de F_{4}.

Le groupe

est infini car 4 commute avec le groupe infini

Soit E_{7} le groupe

On sait que 4 commute avec le groupe Soit ω l’élément maximal du groupe < {2, 1, |23543, 5, 6, 7} >. ω commute avec 2, 1, 5, 6, 7 ; on en déduit l(ω3) < l(ω) et E_{7} est fini, d’élément maxiaml ω4.

Le groupe

est infini car 4 commute avec le groupe infini

Soit E_{8} le groupe

4 commute avec le groupe

et de la même manière que plus haut E_{8} est fini.

Le groupe

est infini car 4 commute avec le groupe infini

Le groupe est infini car 4 commute avec le groupe infini

Soit H_{3} le groupe

1 commute avec 1, 3, t = |1231212, tous générateurs du groupe < {1, 3, t} > car 2, |12, |212, |1212 = |21, |31212 = |3212, |231212 = |321212 = |312121 = |32121 ne commutent pas avec 1, |32121 étant réduit. Le graphe correspondant est

car |1231212 = |1213212 = |2123212 = |2132312 = |3212132 et 3212132\underline{3} = 32121\underline{2}32 = 3\underline{1}212132 ; |1231212 étant réduit, H_{3} est fini, d’élément maximal t13.

Soit H_{4} le groupe

1 commute avec 1, 3, 4, |1231212 = t, donc avec le groupe

(|1231212, 4) = (|123, 4) = (|12, |43) = (|12, |34) = (|12, 3) = (1, |32) = (1, |23) = (1, 2) = 5. H_{4} est fini, d’élément maximal 1ω, où ω est l’élément maximal du groupe < {3, 4, t} >.

Enfin, le groupe

est infini, car 1 commute avec le groupe infini

De tout cela résulte que les groupes de Coxeter finis de graphe connexe sont bien I_{2}(k), de graphe

puis A_{n}, de graphe

enfin B_{n}, D_{n}, E_{6}, de graphe

et E_{7}, E_{8}, F_{4}, H_{3}, H_{4}.

Remarque. — Il n’existe pas dans la littérature de preuve algébrique de chacun des résultats utilisés dans cette note (en particulier l’égalité (s, s′) = m(s, s′) et le lemme 2). De telles preuves paraîtront prochainement dans [6].

On trouvera une méthode de classification plus constructive dans [7]. Le normalisateur d’une réflexion d’un groupe de Coxeter fini étant un groupe de réflexions [8], on voit a posteriori que l’on s’est ramené aux cas où l’élement maximal commute avec chaque élément, montrant que l’élement maximal du normalisateur d’un générateur (ou d’une réflexion quelconque) ne peut être que l’élément maximal du groupe tout entier. Dans chaque cas considéré, le choix du générateur a été fait en vue de la brièveté des calculs.

Références

[1] R. W. Richardson. — Conjugacy classes of involutions in Coxeter groups, Bull. Austral. Math. Soc., vol. 26, 1982, p. 1-15.

[2] J. E. Humphreys. — Reflection groups and Coxeter groups. — Cambridge Studies in Advanced Mathematics 29, Cambridge University Press, Cambridge, 1990.

[3] H. M. S. Coxeter. — The complete enumeration of finite groups of the form R_{i}^{2} = (R_{i}R_{j})^{k_{ij}} = 1, J. Lond. Math. Soc., vol. 10, 1935, p. 21-25.

[4] J. Tits. — Le problème des mots dans les groupes de Coxeter, in Symposia Mathematica (INDAM, Rome, 1967/68), Academic Press, Londres, 1969, 1, p.175-185.

[5] M. Dyer. — Reflection subgroups of Coxeter systems, J. Algebra, vol. 135, 1990, p. 57-53.

[6] P. Moszkowski. — An algebraic introduction to Coxeter groups, à paraître.

[7] P. Moszkowski. — On the involutions of Coxeter groups, à paraître.

[8] E. Witt. — Spiegelungsgruppen und Aufzählung halbeinfachen Liescher Ringe, Abhandl. Math. Sem. Univ. Hamburg, vol. 14, 1941, p. 289-337.

Paul Moszkowski, C.N.R.S., Équipe de Combinatoire, Université de Paris VI, 4, Place Jussieu, F-75005 Paris.