# Théorie des groupes/Exercices/Groupes libres : théorème de Nielsen-Schreier
## Problème 1

Soit F un groupe libre, soient x et y des éléments de F commutant entre eux. Prouver qu'il existe un élément z de F tel que x et y sont tous deux puissances (à exposants entiers relatifs) de z. (Indication. Appliquer le théorème de Nielsen-Schreier au sous-groupe de F engendré par x et y.)
D'après le théorème de Nielsen-Schreier, le sous-groupe <x, y> de F engendré par x et y est un groupe libre. Puisque x et y sont supposés commuter entre eux, le groupe libre <x, y> est abélien. D'après la remarque suivant le problème 1 dans la série Groupes libres, premiers éléments, <x, y> est donc trivial ou isomorphe à $\mathbb {Z} ,+.$ Dans les deux cas, il est monogène, donc il existe un élément z de F tel que <x, y> = <z>. Alors xet y sont tous deux puissances (à coefficients entiers relatifs) de z, d'où l'énoncé.

## Problème 2

On a vu dans le chapitre théorique que tout sous-groupe K d'un groupe libre L est un groupe libre. On va voir que si K est d'indice fini dans L, le rang de K peut s'exprimer en fonction du rang de L et de l'indice [L:K].
Soient X un ensemble, F(X) le groupe libre construit sur X, ${\tilde {X}}$ la base canonique de F(X), H un sous-groupe de F(X), T une transversale droite de Schreier de H dans F(X).
Pour t dans T et x dans ${\tilde {X}}$, on désignera par $h_{t,x}$ (comme au lemme 6 du chapitre théorique) l'unique élément de H tel que
    $tx\in h_{t,x}T.$
a) On pose
    $A=\{(t,x)\mid t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}$
et
    $B=\{h_{t,x}\mid t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}$.
Prouver que $(t,x)\mapsto h_{t,x}$ définit une bijection de A sur B.
(Indication : on peut utiliser le lemme 6 du chapitre théorique.)
L'application $A\to B:(t,x)\mapsto h_{t,x}$ est évidemment bien définie et surjective. Il reste à prouver qu'elle est injective.
Soient (t, x) et (u, y) des éléments de A tels que $h_{t,x}=h_{u,y}$ ; il s'agit de prouver que
    (thèse 1) $\qquad$t = u et x = y.
Puisque (t, x) et (u, y) appartiennent à A, nous avons
    (2) $\qquad t\in T,x\in {\tilde {X}},h_{t,x}\not =1,u\in T,y\in {\tilde {X}},h_{u,y}\not =1,$
ce qui entraîne notamment, comme on l'a noté au chapitre théorique, que $h_{t,x}$ et $h_{u,y}$ n'appartiennent pas à T.
L'hypothèse $h_{t,x}=h_{u,y}$ entraîne a fortiori que le plus court segment initial de $h_{t,x}$ n'appartenant pas à T et le plus court segment initial de $h_{u,y}$ n'appartenant pas à T sont égaux. Joint à (2), cela montre que les hypothèses du lemme 6 du chapitre théorique sont satisfaites, donc, d'après ce lemme, t = u et x = y, ce qui prouve la thèse (1) et donc l'énoncé a).
b) Prouver que le rang de H est égal au cardinal de l'ensemble
    $\{(t,x)\mid t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}.$
D'après le lemme 7 du chapitre théorique, le rang de H est égal au cardinal de l'ensemble
    $\{h_{t,x}|t\in T,x\in {\tilde {X}},h_{t,x}\not =1\},$
qu'on a désigné par B au point a). D'après le point a), cet ensemble a le même cardinal que l'ensemble
    $A=\{(t,x)|t\in T,x\in {\tilde {X}},h_{t,x}\not =1\},$
donc le rang de H est égal au cardinal de ce dernier ensemble, ce qu'il fallait démontrer.
c) Soit E l'ensemble des $(t,x)\in T\times {\tilde {X}}$ tels que $h_{t,x}=1.$
(Donc, A étant défini comme au point a), $A=(T\times {\tilde {X}})\setminus E.$)
Prouver que
    1° E est l'ensemble des $(t,x)\in T\times {\tilde {X}}$ tels que $tx\in T.$
On désigne par $T_{+}$ (resp. $T_{-}$) l'ensemble des éléments de $T\setminus \{1\}$ dont la dernière lettre signée appartient à ${\tilde {X}}$ (resp. à $({\tilde {X}})^{-1}$).
On désigne par $E_{+}$ l'ensemble des éléments (t, x) de E tels que t ne finisse pas par la lettre signée $x^{-1}$ ; on désigne par $E_{-}$ l'ensemble des éléments (t, x) de E tels que t finisse par la lettre signée $x^{-1}.$
Prouver que
    2° $E_{+}$ est équipotent à $T_{+}$ ;
    3° $E_{-}$ est équipotent à $T_{-}$ ;
    4° E est équipotent à $T\setminus \{1\}.$
Par définition, $h_{t,x}$ est l'unique élément de H tel que $tx\in h_{t,x}T.$ On en tire facilement que $h_{t,x}=1$ si et seulement tx appartient à T (on l'a d'ailleurs noté au chapitre théorique, démonstration du lemme 5, équivalence des relations (3) et (5) de la démonstration), ce qui prouve l'assertion 1° de l'énoncé, à savoir
    (1) $\qquad$E est l'ensemble des $(t,x)\in T\times {\tilde {X}}$ tels que $tx\in T.$
Prouvons que
    (thèse 2) $\qquad E_{+}$ est équipotent à $T_{+}.$
Si (t, x) désigne un élément de $E_{+}$, alors, d'après la définition de $E_{+}$ et la relation (1),
    $t\in T,x\in {\tilde {X}},tx\in T$ et t ne finit pas par la lettre signée $x^{-1}.$
Donc $tx=t_{juxt}x$ et $t_{juxt}x$ appartient à T.
Puisque x est de longueur 1, $t_{juxt}x$ est distinct de 1, donc $t_{juxt}x$ appartient à $T\setminus \{1\}.$ La dernière lettre signée de $t_{juxt}x$ est x et appartient donc à ${\tilde {X}}$, donc $t_{juxt}x$ appartient à $T_{+}.$
Nous pouvons donc considérer l'application
    $f:E_{+}\to T_{+}:(t,x)\mapsto t_{juxt}x.$
Prouvons que f est une bijection.
Prouvons d'abord que f est injective.
Si (t, x) et (t', x') sont deux éléments de $E_{+}$ tels que f(t, x) = f(t', x'), alors
    $t_{juxt}x=t'_{juxt}x'.$
La dernière lettre signée du membre gauche est x et la dernière lettre signée du membre droit est x', donc x = x'. Par exemple parce que la loi de composition $_{juxt}$ est clairement simplifiable, on a aussi t = t', d'où (t, x) = (t', x'), ce qui prouve que f est injective, comme annoncé.
Prouvons maintenant que f est surjective.
Soit $\tau$ un élément de $T_{+}$ ; il s'agit de prouver que $\tau$ est image par f d'un élément de $E_{+}.$
Par définition de $T_{+},\tau$ appartient à $T\setminus \{1\}$ et est de la forme
    $\tau =t_{juxt}x$
avec $t\in F(X)$ et $x\in {\tilde {X}}.$
Puisque $\tau$, égal à $t_{juxt}x,$ est supposé appartenir à T et que T est schreiérienne, t appartient à T.
De plus, la relation $\tau =t_{juxt}x$ peut s'écrire $\tau =tx$ ; puisque $\tau$ appartient à T, nous avons donc $tx\in T.$
Donc, d'après (1),
    $(t,x)\in E.$
Puisque $\tau$ est un mot signé réduit et est égal à $t_{juxt}x,$ la dernière lettre signée de t n'est pas $x^{-1},$ donc $(t,x)\in E_{+}.$ D'après la définition de f, nous avons
    $f(t,x)=t_{juxt}x=\tau ,$
ce qui, comme noté, prouve que f est surjective.
Nous avons donc prouvé que f est bijective, ce qui prouve la thèse (2), à savoir que
    (3) $\qquad E_{+}$ est équipotent à $T_{+}.$
L'assertion 2° de l'énoncé est donc démontrée.
Prouvons que
    (thèse 4) $\qquad E_{-}$ est équipotent à $T_{-}.$
On a défini $E_{-}$ comme l'ensemble des $(t,x)\in E$ tels que t finisses par la lettre signée $x^{-1}.$ Vu le résultat (1) sur E, les éléments de $E_{-}$ sont donc les couples $(t,x)\in T\times {\tilde {X}}$ tels que t finisse par la lettre signée $x^{-1}$ et que $tx\in T.$ Cela revient à dire que
    les éléments de $E_{-}$ sont les couples de la forme $(t'_{juxt}x^{-1},x)$ avec $t'_{juxt}x^{-1}\in T,x\in {\tilde {X}}$ et $t'\in T.$
(On pourrait ne pas mentionner la condition $t'\in T,$ car, T étant schreiérienne, cette condition est entraînée par la condition $t'_{juxt}x^{-1}\in T$.)
Pour un tel couple, $t'_{juxt}x^{-1}$ appartient à $T\setminus \{1\}$, donc, par définition de $T_{-},$
    $t'_{juxt}x^{-1}\in T_{-}.$
Nous pouvons donc considérer l'application
    $g:E_{-}\to T_{-}:(t'_{juxt}x^{-1},x)\mapsto t'_{juxt}x^{-1}.$
(Autrement dit, g applique un couple appartenant à $E_{-}$ sur la première composante de ce couple.)
On va prouver que g est une bijection.
Prouvons d'abord que g est injective.
Soient (t, x) et (u, y) des éléments de $E_{-}$ tels que g(t, x) = g(u, y) ; il s'agit de prouver que (t, x) = (u, y).
L'hypothèse g(t, x) = g(u, y) signifie t = u. Puisque (t, x) appartient à $E_{-},x^{-1}$ est la dernière signée de t. De même, puisque (u, y) appartient à $E_{-},y^{-1}$ est la dernière signée de u. Puisque, comme nous l'avons noté, t = u, nos deux derniers résultats donnent $x^{-1}=y^{-1}$, x = y, d'où (t, x) = (u, y). Comme noté, cela prouve que g est injective.
Prouvons maintenant que g est surjective.
Soit $\sigma$ un élément de $T_{-}$ ; il s'agit de prouver que $\sigma$ est image par g d'un élément de $E_{-}$.
Puisque $\sigma$ appartient à $T_{-}$, c'est un élément de $T\setminus \{1\}$ dont la dernière lettre signée appartient à $({\tilde {X}})^{-1}.$ Donc $\sigma$ est de la forme $t_{juxt}x^{-1},$ avec $t\in F(X)$ et $x\in {\tilde {X}}.$ Puisque $\sigma$ appartient à T et que T est schreiérienne, la relation $\sigma =t_{juxt}x^{-1}$ montre que t appartient à T. Puisque $t=(t_{juxt}x^{-1})\star x,$ où $\star$ désigne la loi de groupe de F(X), dire que t appartient à T revient à dire que $(t_{juxt}x^{-1})\star x\in T,$ donc, d'après (1),
    $(t_{juxt}x^{-1},x)\in E.$
Comme $t_{juxt}x^{-1}$ finit par la lettre signée $x^{-1}$, nous avons donc
    $(t_{juxt}x^{-1},x)\in E_{-}$
et, d'après la définition de g,
    $g(t_{juxt}x^{-1},x)=t_{juxt}x^{-1}=\sigma ,$
donc, comme annoncé, $\sigma$ est image par g d'un élément de $E_{-}$, ce qui, comme noté, prouve que g est surjective.
Nous avons donc prouvé que g est bijective, ce qui prouve la thèse (4), à savoir que
    (5) $\qquad E_{-}$ est équipotent à $T_{-}$.
L'assertion 3° de l'énoncé est démontrée.
D'après leurs définitions, $E_{+}$ et $E_{-}$ forment une partition de E. De même, d'après leurs définitions, $T_{+}$ et $T_{-}$ forment une partition de $T\setminus \{1\}.$ Donc nos résultats (3) et (5) montrent que
    E est équipotent à $T\setminus \{1\},$
ce qui démontre l'assertion 4° de l'énoncé.
d) On suppose que H est d'indice fini dans F(X). Prouver que le rang de H est égal à
    $[F(X):H]\cdot \vert X\vert -([F(X):H]-1).$
D'après le point b), le rang de H est égal au cardinal de l'ensemble $\{(t,x)|t\in T,x\in {\tilde {X}},h_{t,x}\not =1\}.$ Autrement dit,
    (1) le rang de H est égal au cardinal de l'ensemble $(T\times {\tilde {X}})\setminus E,$
où E désigne, comme au point c), l'ensemble des $(t,x)\in T\times {\tilde {X}}$ tels que $h_{t,x}=1.$
On a vu au point c) que E est équipotent à $T\setminus \{1\},$ donc
    (2) $\qquad \vert E\vert =\vert T\vert -1.$
Comme T est une transversale (droite) de H dans F(X), $\vert T\vert$ égale l'indice [F(X) : H], donc (2) peut s'écrire
    (3) $\qquad \vert E\vert =[F(X):H]-1.$
Puisque nous supposons que [F(X) : H] est fini, $\vert E\vert$ est donc fini, donc
    $\vert (T\times {\tilde {X}})\setminus E\vert =\vert T\times {\tilde {X}}\vert -\vert E\vert$
    $\vert (T\times {\tilde {X}})\setminus E\vert =\vert T\vert \cdot \vert {\tilde {X}}\vert -\vert E\vert$
    $\vert (T\times {\tilde {X}})\setminus E\vert =[F(X):H]\cdot \vert X\vert -\vert E\vert ,$
d'où, d'après (3),
    $\vert (T\times {\tilde {X}})\setminus E\vert =[F(X):H]\cdot \vert X\vert -([F(X):H]-1).$
D'après (1), cela revient à dire que le rang de H est égal à $[F(X):H]\cdot \vert X\vert -([F(X):H]-1),$ ce qui démontre l'énoncé.
e) Soient L un groupe libre et K un sous-groupe d'indice fini de L. Prouver que, rg désignant le rang,
    rg(K) = [L:K] rg(L) - ([L:K] - 1).
Choisissons une base X du groupe L. D'après le chapitre Groupes libres, premiers éléments, il existe un isomorphisme $\sigma$ de L sur F(X). D'après le point d),
    (1) $\qquad \mathrm {rg} (\sigma (K))=[F(X):\sigma (K)]\cdot \vert X\vert -([F(X):\sigma (K)]-1).$
Les groupes K et $\sigma (K)$sont isomorphes, donc (chapitre Groupes libres, premiers éléments)
    (2) $\qquad \mathrm {rg} (\sigma (K))=\mathrm {rg} (K).$
D'autre part, puisque X est une base de L,
    (3) $\qquad \vert X\vert =\mathrm {rg} (L).$
Enfin, puisque $\sigma$ est un isomorphisme de L sur F(X),
    (4) $\qquad [F(X):\sigma (K)]=[L:K].$
D'après (2), (3) et (4), la relation (1) peut s'écrire
    rg(K) = [L:K] rg(L) - ([L:K] - 1),
ce qui démontre l'énoncé.
f) Soient L un groupe libre de rang fini $\geq 2$ et K un sous-groupe d'indice 2 de L. (On sait, par un exercice de la série Groupes libres, premiers éléments, qu'il existe un tel sous-groupe K.) Prouver que le rang de K est strictement supérieur à celui de L.
D'après le point e), nous avons, rg désignant le rang,
    (1) $\qquad$ rg(K) = 2 rg(L) - 1.
Comme rg(L) est supposé fini et >1,
    2 rg(L) - 1 > rg(L),
donc (1) donne rg(K) > rg(L), ce qu'il fallait démontrer.
Remarque. Dans les hypothèses et notations du point f), choisissons une base Y de K. Alors Y est une partie libre de L. (En effet, Y est une base du sous-groupe de L qu'elle engendre, à savoir du sous-groupe K, donc, d'après une des définitions d'une partie libre, Y est une partie libre de L.) D'après le point f), le rang de K, autrement dit le cardinal de Y, est strictement supérieur au rang de L. Cela montre que le cardinal d'une partie libre d'un groupe libre L peut être strictement supérieur au rang de L.
g) Soit {a,b} un ensemble à 2 éléments ($a\not =b$). Prouver que le dérivé F'({a,b}) du groupe libre F({a,b}) est de rang infini (ce qui montre qu'un sous-groupe d'un groupe libre de rang fini peut être de rang infini).
Indication : utiliser le point b) et une caractérisation du dérivé de F(X) donnée dans un exercice de la série Groupes libres, premiers éléments ; noter que les éléments $((a,1))^{r}((b,1))^{s}$, avec r, s dans $\mathbb {Z}$ forment une transversale droite de Schreier de F'({a,b}) dans F({a,b}).
Soient X, H, T et $h_{t,x}$ comme dans les hypothèses générales du problème. On a noté dans la solution du point c) que, pour t dans T et x dans ${\tilde {X}}$, la relation $h_{t,x}=1$ équivaut à ce que tx appartienne à T.
Donc, d'après le point b),
    (1) le rang de H est égal au cardinal de l'ensemble $\{(t,x)\vert t\in T,x\in {\tilde {X}},tx\notin T\}.$
Appliquons cela au cas où X est l'ensemble {a,b} et H le dérivé F'({a,b}) de F({a,b}).
Prouvons d'abord que l'ensemble des $((a,1))^{r}((b,1))^{s}$, avec r, s dans $\mathbb {Z}$ est une transversale droite de Schreier de F'({a,b}) dans F({a,b}). (En fait, puisque F'({a,b}) est un sous-groupe normal de F({a,b}), il n'est pas nécessaire de préciser « droite »).
Posons a' = ((a, 1)) et b' = ((b, 1)), de sorte que {a', b'} est la base canonique de F({a,b}). Pour chaque élément x de {a', b'}, il existe un et un seul homomorphisme $w\mapsto n_{x}(w)$ de F({a,b}) dans $\mathbb {Z} ,+$ qui vaut 1 en x et vaut 0 en l'autre élément de {a', b'}. D'après un exercice de la série Groupes libres, premiers éléments, F'({a,b}) est l'ensemble des éléments w de F({a,b}) tels qu'on ait à la fois $n_{a'}(w)=0$ et $n_{b'}(w)=0$.
Pour tout élément w de F({a,b}), nous avons alors
    $w\equiv a'\ ^{n_{a'}(w)}b'\ ^{n_{b'}(w)}{\pmod {F'(\{a,b\})}},$
donc tout élément de F({a,b}) est congru modulo F'({a,b}) à un élément de la forme $a'\ ^{r}b'\ ^{s},$ avec r, s dans $\mathbb {Z} .$
Si r, s, r', s' sont des entiers rationnels tels que
    $a'\ ^{r}b'\ ^{s}\equiv a'\ ^{r'}b'\ ^{s'}{\pmod {F'(\{a,b\})}},$
alors
    $a'\ ^{r}b'\ ^{s}=a'\ ^{r'}b'\ ^{s'}c$ avec c dans F'({a,b}).
En appliquant l'homomorphisme $w\mapsto n_{a'}(w)$ (resp. $n_{b'}(w)$) de F({a,b}) dans $\mathbb {Z} ,+$, nous trouvons r = r' (resp. s = s').
Donc, pour un élément donné w de F({a,b}), il existe un et un seul élément $a'\ ^{r}b'\ ^{s}$, avec r, s dans $\mathbb {Z} ,$ tel que
    $w\equiv a'\ ^{r}b'\ ^{s}{\pmod {F'(\{a,b\})}}.$
Cela prouve que l'ensemble des $a'\ ^{r}b'\ ^{s}$, avec r, s dans $\mathbb {Z} ,$ est une transversale (droite) de F'({a,b}) dans F({a,b}).
Le raisonnement qu'on vient de tenir montre aussi que
    (2) $\qquad (r,s)\mapsto a'\ ^{r}\ b'\ ^{s}$ définit une bijection de $\mathbb {Z} \times \mathbb {Z}$ sur cette transversale.
Désignons cette transversale par T. Il est clair que T est schreiérienne. Donc, d'après (1),
    (3) le rang de F'({a,b}) est égal au cardinal de l'ensemble
    $\{(t,x)\vert t\in T,x\in \{a',b'\},tx\notin T\}.$
Soit $t=a'\ ^{r}b'\ ^{s}$ un élément de T, soit x un élément de {a', b'}.
Si tout d'abord x = a', la condition $tx\notin T$ équivaut à
    $a'\ ^{r}b'\ ^{s}a'\notin T,$
ce qui a lieu si et seulement si $s\not =0.$
Si maintenant x = b', la condition $tx\notin T$ n'est satisfaite pour aucun élément $t=a'\ ^{r}b'\ ^{s}$ de T. Donc (3) revient à dire que le rang de F'({a,b}) est égal au cardinal de l'ensemble des $(a'\ ^{r}b'\ ^{s},a')$ avec $r\in \mathbb {Z}$ et $r\in \mathbb {Z} \setminus \{0\}.$ Cela revient encore à dire que le rang de F'({a,b}) est égal au cardinal de l'ensemble des $a'\ ^{r}b'\ ^{s}$ avec $r\in \mathbb {Z}$ et $r\in \mathbb {Z} \setminus \{0\}.$ D'après (2), ce cardinal est égal à celui de $\mathbb {Z} \times (\mathbb {Z} \setminus \{0\})$ et est donc égal au cardinal de $\mathbb {N} .$ (Rappelons que ce cardinal est appelé « aleph-zéro » et noté ℵ$_0$.)
Donc F'({a,b}) est un sous-groupe de rang infini du groupe libre F({a,b}), qui, lui, est de rang fini (égal à 2).
Remarque : à l'aide du lemme 7 du chapitre théorique et des raisonnements tenus dans la solution du présent point g), on montre facilement que les $a'\ ^{r}b'\ ^{s}a'b'\ ^{-s}a'\ ^{-r-1}$, avec r' dans $\mathbb {Z}$ et s' dans $\mathbb {Z} \setminus \{0\},$ forment une base de F'({a,b}).
Puisque le rang de F'({a,b}) est infini et que le rang d'un groupe libre est le plus petit cardinal de partie génératrice de ce groupe, F'({a,b}) n'est donc pas de type fini. D'autre part, F({a,b}), ayant une base à deux éléments, est de type fini. Cela montre que, comme annoncé dans le chapitre Classes modulo un sous-groupe, un sous-groupe d'un groupe de type fini n'est pas forcément de type fini.
Remarque. La démonstration du point g) peut être étendue à l'énoncé suivant : le dérivé d'un groupe libre de rang au moins égal à 2 est de rang infini. Nous déduirons l'énoncé général de l'énoncé particulier dans un exercice de la série Groupes libres : théorème de Howson.
h) Il résulte du point e) que si L est un groupe libre et K un sous-groupe d'indice fini de L, le rang de K est déterminé par le rang de L et l'indice de K dans L. Montrer qu'il n'en est pas forcément de même si l'indice de K dans L est infini. Pour cela, donner un exemple de la situation suivante : L est un groupe libre, $K_{1}$ et $K_{2}$ sont deux sous-groupes de même indice (infini) de L et les rangs de $K_{1}$ et de $K_{2}$ sont différents. (On peut utiliser les résultats du point g) et le fait, démontré dans un exercice de la série Groupes, premières notions, que tout groupe engendré par une partie dénombrable est lui-même dénombrable, où « dénombrable » signifie « fini ou équipotent à $\mathbb {N}$ ».)
Soit {a,b} un ensemble à deux éléments ($a\not =b$). Prenons L égal au groupe libre F({a,b}), $K_{1}$ au sous-groupe 1 de F({a,b}) et $K_{2}$ égal au dérivé F'({a,b}) de F({a,b}). Le rang de $K_{1}$ est nul et, d'après le point g), le rang de $K_{2}$ est infini. Donc
    (1) les rangs de $K_{1}$ et de $K_{2}$ sont différents.
Nous avons trouvé au point g) une transversale infinie dénombrable de $K_{2}$ = F'({a,b}) dans L = F({a,b}), donc
    (2) l'indice de $K_{2}$ dans L est aleph-zéro (cardinal de $\mathbb {N}$).
Le groupe L est engendré par une partie à deux éléments. Une telle partie est dénombrable, donc, d'après un exercice de la série Groupes, premières notions, L est dénombrable. D'autre part, par exemple d'après (2), L est infini. Donc l'ordre de L est aleph-zéro, donc l'indice de 1 dans L est aleph-zéro, autrement dit
    l'indice de $K_{1}$ dans L est aleph-zéro.
Joint à (2), cela montre que les indices de $K_{1}$ et de $K_{2}$ sont égaux. Puisque, d'après (1), les rangs de $K_{1}$ et de $K_{2}$ sont différents, notre exemple répond à la question.
i) Soit G un groupe ayant une partie génératrice de cardinla fini m, soit H un sous-groupe d'indice fini j de G. On a vu au chapitre Classes modulo un sous-groupe que H admet une partie génératrice de cardinal $\leq jm.$ Prouver, à l'aide du point e) que H admet une partie génératrice de cardinal $\leq jm-(j-1).$
Choisissons une partie génératrice X de cardinal m de G. D'après l'énoncé 9 du chapitre Groupes libres, premiers éléments, il existe un homomorphisme surjectif f de F(X) sur G.
Puisque H est supposé d'indice j dans G, il existe des éléments $x_{1},\ldots ,x_{j}$ de G tels que
    (1) $\qquad G=Hx_{1}\cup \cdots \cup Hx_{j}.$
Pour tout i dans {1, ... , j}, choisissons un élément $y_{i}$ de F tel que
    (2) $\qquad f(y_{i})=x_{i}.$
Prouvons que
    (thèse 3) $\qquad F(X)=f^{-1}(H)y_{1}\cup \ldots \cup f^{-1}(H)y_{j}.$
Soit z un élément de F(X). D'après (1), nous avons, pour un certain i dans {1, ... , j},
    $f(z)\in Hx_{i}.$
D'après(2), cela peut s'écrire
    $f(z)\in Hf(y_{i})$
    $f(z)f(y_{i})^{-1}\in H$
    $f(zy_{i}^{-1})\in H$
    $zy_{i}^{-1}\in f^{-1}(H)$
    $z\in f^{-1}(H)y_{i},$
ce qui prouve notre thèse (3), à savoir
    $F=f^{-1}(H)y_{1}\cup \ldots \cup f^{-1}(H)y_{j}.$
Donc l'indice du sous-groupe $f^{-1}(H)$ de F(X) est $\leq j.$
(Il est même égal à j, car on montre facilement que les $y_{i}$ appartiennent à des classes à droite deux à deux distinctes modulo $f^{-1}(H)$.)
Puisque F(X) est libre de rang m, il résulte donc du point e) que le rang de $f^{-1}(H)$ est inférieur ou égal à jm - (j-1). (Il est même égal à jm - (j-1), d'après une remarque qu'on vient de faire.)
Il existe donc une partie P de $f^{-1}(H)$ telle que
    (4) $\qquad \vert P\vert \leq jm-(j-1)$
et
    (5) $\qquad \langle P\rangle =f^{-1}(H),$
où $\langle P\rangle$ désigne le sous-groupe de F(X) engendré par P.
En passant aux images par f dans l'égalité (5), on trouve
    $\langle f(P)\rangle =f(f^{-1}(H))$ dans G.
Puisque f est surjectif, le membre droit égale H, donc $\langle f(P)\rangle =H$ dans G, donc
    (6) f(P) est une partie génératrice de H.
Puisque $\vert f(P)\vert \leq \vert P\vert$, la relation (4) donne $\vert f(P)\vert \leq jm-(j-1),$ ce qui, joint à (6), démontre l'énoncé.
Remarque. Le point i) montre que les groupes libres ont un rôle d'outil, puisqu'ils permettent de démontrer des théorèmes qui se formulent indépendamment de la notion de groupe libre. Un autre rôle d'outil des groupes libres est qu'ils nous permettront de fonder rigoureusement la notion de présentation d'un groupe.

## Problème 3 (une preuve du théorème de Nielsen-Schreier reposant sur la notion d'action de groupe)

Soient L un groupe libre de base X, H un sous-groupe, T une transversale droite de Schreier de H dans L. Pour tout $w\in L$, on note ${\bar {w}}$ l'élément de T tel que $w{\bar {w}}^{-1}\in H$ et l'on pose
    $B:=\{tx({\overline {tx}})^{-1}\mid t\in T,x\in {\tilde {X}}\}\setminus \{1\}$.
On sait, d'après le lemme de Schreier, que B est une partie génératrice de H, et le but de l'exercice est de redémontrer que c'est une base de H, en utilisant le problème 7 de « Groupes libres, premiers éléments ».
Soient A un ensemble et $\sigma$ une application de B dans le groupe symétrique $S_{A}$, que l'on étend en posant $\sigma (1)=\mathrm {id} _{A}$. On considère (cf. problème 7 mentionné ci-dessus) l'action à droite de L sur A×(L/H) telle que pour tout $x\in X$ :
    $(a,Hw)x:=(\sigma ({\bar {w}}x{\overline {wx}}^{-1})(a),Hwx)$.
* Démontrer que pour tout $t\in T$, $(a,H)t=(a,Ht)$.
* En déduire que pour tout $b\in B$, $(a,H)b=(\sigma (b)(a),H)$.
* Conclure.
Référence : (en) Benjamin Steinberg, « An elementary proof that subgroups of free groups are free », arXiv, 2010 [texte intégral].
* On procède par récurrence sur la longueur n de t (relativement à la base X). Si $n=0$ il n'y a rien à démontrer. Si $n>0$, on a $t=wx$ ou $wx^{-1}$ avec $w\in T$ de longueur $n-1$ et $x\in X$. Par hypothèse de récurrence, $(a,H)w=(a,Hw)$ donc :
** si $t=wx$, $(a,H)t=(a,Hw)x=(\sigma ({\bar {w}}x{\overline {wx}}^{-1})(a),Hwx)=(\sigma (wxt^{-1})(a),Ht)=(a,Ht)$ et
** si $t=wx^{-1}$, on a aussi $(a,H)t=(a,Ht)$ car $(a,H)tx=(a,Ht)x$. En effet :
*** $(a,H)tx=(a,H)w=(a,Hw)$ et
*** $(a,Ht)x=(\sigma ({\bar {t}}x{\overline {tx}}^{-1})(a),Htx)=(\sigma (txw^{-1})(a),Hw)=(a,Hw)$.
* Soient $t\in T$, $x\in {\tilde {X}}$ et $b=tx{\overline {tx}}^{-1}$. En appliquant la question précédente à $t$ et à ${\overline {tx}}$, on obtient : $(a,H)b=(a,Ht)x{\overline {tx}}^{-1}=(\sigma ({\bar {t}}x{\overline {tx}}^{-1})(a),Htx){\overline {tx}}^{-1}=(\sigma (tx{\overline {tx}}^{-1})(a),Htx{\overline {tx}}^{-1})=(\sigma (b)(a),Hb)=(\sigma (b)(a),H)$.
* D'après le problème 7 de « Groupes libres, premiers éléments », il s'agit de prouver que $\sigma$ s'étend de façon unique en une action de H sur A. L'unicité résulte du fait que B engendre H, et l'existence vient de la question précédente.

## Problème 4 (une preuve d'existence de transversales de Schreier s'appuyant sur le lemme de Zorn)

Soient L un groupe libre de base X et H un sous-groupe. On considère l'ensemble ${\mathcal {P}}$ des parties schreiériennes de L (relativement à la base X) contenant au plus un élément de chaque classe à droite suivant H.
* Vérifier que $({\mathcal {P}},\subset )$ est inductif.
* Soit T un élément maximal de ${\mathcal {P}}$. Démontrer (par l'absurde) que T rencontre toute classe à droite suivant H.
Référence : (en) Benjamin Steinberg, « An elementary proof that subgroups of free groups are free », arXiv, 2010 [texte intégral].
** ${\mathcal {P}}$ est non vide car $\{1\}\in {\mathcal {P}}$.
** L'union de toute chaîne d'éléments de ${\mathcal {P}}$ appartient à ${\mathcal {P}}$.
* Supposons que T ne rencontre pas toutes les classes à droite. Soit $w\in L$ de longueur minimum $n$ (relativement à la base X) tel que $T\cap Hw=\varnothing$. Alors, $n>1$ et $w=ux$ pour un certain $u\in L$ de longueur $n-1$ et $x\in X\cup X^{-1}$. Par minimalité de $n$, T rencontre $Hu$, en un certain $t$, donc $Hw=Hux=Htx$, si bien que (par choix de $w$) $tx\notin T$. Or (que tx soit réduit ou pas) $T\cup \{tx\}\in {\mathcal {P}}$. Ceci contredit la maximalité de T.
Remarque. (en) Marshall Hall, Jr., The Theory of Groups, AMS, 1976, 2e éd. [lire en ligne] , lemme 7.2.1, propose une variante, reposant sur le théorème de Zermelo (équivalent, comme le lemme de Zorn, à l'axiome du choix) : on choisit un bon ordre sur $X\cup X^{-1}$, et on l'étend lexicographiquement à L. Puis on pose $T=\{\min(Hw)\mid w\in L\}$.