# Théorie des groupes/Groupes libres : théorème de Howson

Dans ce chapitre, on va démontrer un théorème de Howson selon lequel l'intersection de deux sous-groupes de type fini d'un groupe libre est elle-même un groupe de type fini. Ce théorème n'est pas une matière classique et peut donc être négligé par le lecteur. On lui fait une place ici parce qu'il peut être démontré à l'aide de lemmes qui nous ont servi à démontrer le théorème de Nielsen-Schreier.

## Classes à droite à terminaisons multiples

Soit X un ensemble ; notons F(X) le groupe libre construit sur X. Soit H un sous-groupe de F(X), soit C une classe à droite modulo H dans F(X).
Nous dirons que C est à terminaisons multiples s'il existe dans C deux mots signés non vides n'ayant pas la même dernière lettre signée.
Exemples
    1) Si H est réduit à l'élément neutre, toute classe à droite modulo H est un singleton, donc aucune classe à droite modulo H n'est à terminaison multiples.
    2) Soit a un élément de X, soit H le sous-groupe <a> de F(X) engendré par a. H comprend a, dont la dernière lettre signée est a, et H comprend aussi a$^{-1}$, dont la dernière lettre signée est a$^{-1}$, donc la classe H est à terminaisons multiples.
    3) Soit X = {a,b,c} un ensemble de cardinal 3, soit H le sous-groupe (monogène) de F(X) engendré par l'élément b$^{-1}$ab. La classe à droite H1 = H n'est pas à terminaisons multiples, car ses éléments distincts de 1 ont tous b pour dernière lettre signée. La classe à droite Hc n'est pas à terminaisons multiples, car ses éléments ont tous c pour dernière lettre signée. La classe à droite Hb$^{-1}$a$^{-1}$ est à terminaisons multiples, puisqu'elle comprend 1b$^{-1}$a$^{-1}$ = b$^{-1}$a$^{-1}$, dont la dernière lettre signée est a$^{-1}$, et qu'elle comprend aussi (b$^{-1}$ab)b$^{-1}$a$^{-1}$ = b$^{-1}$, dont la dernière lettre signée est b$^{-1}$.
Soient X un ensemble fini, soit H un sous-groupe du groupe libre F(X) construit sur X. Alors H est de type fini (ce qui, d'après le théorème de Nielsen-Schreier, revient à dire que H est un groupe libre de rang fini) si et seulement si les classes à droite modulo H à terminaisons multiples sont en nombre fini.
Démonstration. D'après le chapitre Groupes libres : théorème de Nielsen-Schreier, nous pouvons choisir une transversale droite de Schreier T de H dans F(X). Comme dans les notations du chapitre Groupes libres : théorème de Nielsen-Schreier, désignons par :
* ${\overline {w}}$, pour tout élément w de F(X), l'unique élément de T tel que $w\in H{\overline {w}}$ ;
* $h_{t,x}$, pour tout élément t de T et tout élément x = ((x', 1)) de la base ${\tilde {X}}$ de F(X), l'unique élément de H tel que
       $tx\in h_{t,x}T.$
    Cela revient à dire que
       $tx=h_{t,x}{\overline {tx}}$.
* Y l'ensemble
       $Y=\{h_{t,x}\mid t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}.$
Les notations $h_{t,x}$, ${\overline {w}}$ et Y dépendent implicitement de H et de T, qui seront fixés durant toute la démonstration.
D'après le lemme 8 du chapitre Groupes libres : théorème de Nielsen-Schreier,
    (1) Y est une base du groupe H.
Supposons d'abord que
    (hyp. 2) H est de rang fini.
Alors, puisque, comme rappelé en (1), Y est une base de H,
    (3) l'ensemble Y est fini.
Notons alors T' l'ensemble (fini et schreiérien) des segments initiaux appartenant à T des éléments de $Y\cup Y^{-1}$.
Nous avons vu (chapitre Groupes libres : théorème de Nielsen-Schreier, lemme 7) que
    si r est un nombre naturel > 0,
    si $y_{1},\dots ,y_{r}$ sont des éléments de Y,
    si $\epsilon _{1},\ldots ,\epsilon _{r}$ sont des éléments de $\{1,-1\}\subset \mathbb {Z} ,$
    si le mot signé sur Y
       $((y_{1},\epsilon _{1}),\ldots ,(y_{r},\epsilon _{r}))$
    est réduit sur Y,
    alors
    (4) l'élément $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ de F(X) commence (une fois explicité dans F(X) ) par le plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T.
Puisque, d'après le lemme 3 du chapitre Groupes libres : théorème de Nielsen-Schreier, le plus long segment initial de $y_{1}^{\epsilon _{1}}$ appartenant à T est un segment initial du plus court segment initial de $y_{1}^{\epsilon _{1}}$ n'appartenant pas à T, il résulte de (4) que, sous les mêmes hypothèses,
    le plus long segment initial de $y_{1}^{\epsilon _{1}}\cdots y_{r}^{\epsilon _{r}}$ appartenant à T appartient à T'.
Par conséquent, comme T' est schreiérienne :
    (5) pour tout élément h de H, tout segment initial de h appartenant à T appartient à T'.
Soit C une classe à droite modulo H.
Puisque T est une transversale droite de H dans F(X), il existe un (et un seul) élément t de T tel que
    (6) C = H t.
Si C est à terminaisons multiples, elle contient deux mots non vides ht et h't n'ayant pas la même dernière lettre signée. Cela exige que h ou h' finisse par le mot signé t$^{-1}$.
Puisque t est alors un segment initial d'un élément de H, il résulte donc de (5) que l'élément t considéré en (6) appartient à T'. Puisque l'ensemble T' est fini, cela prouve que les classes à droite modulo H à terminaisons multiples sont en nombre fini.
L'énoncé du lemme est donc démontré dans l'hypothèse (2), où H est de rang fini.
Supposons maintenant que
    (hyp. 7) H est de rang infini.
Alors, puisque, comme rappelé en (1), l'ensemble $\{h_{t,x}\mid t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}$ est une base de H, cet ensemble est infini.
Donc, puisque, par hypothèse de l'énoncé, X est fini,
    (8) il existe une partie infinie T$_0$ de T possédant la propriété suivante :
    pour tout élément t de T$_0$, il existe au moins un élément x de ${\tilde {X}}$ tel que $h_{t,x}\not =1.$
Puisque T$_0$ est contenue dans la transversale droite T de H,
    (9) les classes à droite Ht, où t parcourt T$_0$, sont deux à deux distinctes et sont donc en quantité infinie.
Prouvons que
    (thèse 10) pour tout élément t de T$_0$, Ht est à terminaisons multiples.
Soit t un élément de T$_0$.
D'après (8), nous pouvons choisir x dans ${\tilde {X}}$ tel que
    (11) $h_{t,x}\neq 1.$
Compte tenu de (11) et du chapitre Groupes libres : théorème de Nielsen-Schreier, lemme 5, deuxième et troisième assertions du point 3°,
    (12) t ne finit pas par la lettre signée x$^{-1}$ et
    (13) ${\overline {tx}}x^{-1}$ finit par la lettre signée $x^{-1}.$
Or par définition de $h_{t,x}$,
    (14) ${\overline {tx}}x^{-1}=h_{t,x}^{-1}t\in Ht.$
Des résultats (12) à (14), il résulte que Ht comprend deux mots signés non vides ($t$ et ${\overline {tx}}x^{-1}$) qui ne finissent pas par la même lettre signée. Cela prouve notre thèse (10), à savoir que, pour tout élément t de T$_0$, Ht est à terminaisons multiples.
Puisque, d'après (9), les classes à droite Ht, où t parcourt T$_0$, sont en quantité infinie, nous avons donc prouvé que dans l'hypothèse (7), où H est de rang infini, il y a une infinité de classes à droite modulo H qui sont à terminaisons multiples. Joint au résultat obtenu dans le cas où H est de rang fini, cela prouve l'énoncé.
Remarque. L'énoncé devient faux si on ne suppose pas X fini. En effet, supposons X infini et prenons pour sous-groupe H de F(X) le groupe F(X) lui-même. Alors H n'est pas de type fini mais il n'y a qu'une classe à droite modulo H dans F(X) (à savoir F(X)), donc «les» classes à droite modulo H à terminaisons multiples sont en nombre fini (égal à 1).

## Théorème de Howson

Soit F un groupe libre, soient H et K deux sous-groupes de type fini de F. Alors $H\cap K$ est lui aussi un groupe de type fini. (Puisque, d'après le théorème de Nielsen-Schreier, $H,K$ et $H\cap K$ sont des groupes libres, « de type fini » pourrait être remplacé par « libre(s) de rang fini ».)
Démonstration. Puisque H et K sont supposés de type fini, il résulte d'un problème de la série Groupes, premières notions que
    (1) le sous-groupe <H, K> de F engendré par H et K est lui aussi de type fini.
D'autre part, d'après le théorème de Nielsen-Schreier, <H, K> est un groupe libre. Joint à (1), cela montre que H et K sont sous-groupes d'un même sous-groupe libre de type fini de F. Nous sommes donc ramenés au cas où F est libre de rang fini. Puisque tout groupe libre est isomorphe à un groupe F(X) de même rang, on se ramène facilement au cas où il existe un ensemble fini X tel que H et K soient des sous-groupes de rang fini de F(X). Soit $(H\cap K)a$, avec a dans F(X), une classe à droite modulo $H\cap K$ dans F(X). Alors (vérification facile)
    (2) $(H\cap K)a=(Ha)\cap (Ka).$
Du fait que $(H\cap K)a$ est contenue dans Ha et dans Ka, il résulte que
    (3) si $(H\cap K)a$ est à terminaisons multiples, Ha et Ka sont à terminaisons multiples.
Puisque H est de rang fini, il résulte du précédent lemme qu'il n'y a qu'un nombre fini de classes à droite modulo H dans F(X) qui sont à terminaisons multiples ; soient $Hb_{1},\ldots Hb_{m}$ ces classes. De même, il n'y a qu'un nombre fini de classes à droite modulo K dans F(X) qui sont à terminaisons multiples ; soient $Kc_{1},\ldots Kc_{n}$ ces classes. Alors, d'après (2) et (3),
    $(H\cap K)a$ est égale à un ensemble $Hb_{i}\cap Kc_{j}.$
Cela montre qu'il n'y a qu'un nombre fini de classes à droite modulo $H\cap K$ qui sont à terminaisons multiples. D'après le lemme qui précède (applicable parce que X est fini), $H\cap K$ est donc de type fini.