Leçons de niveau 14

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Groupes libres : théorème de Nielsen-Schreier
Icône de la faculté
Chapitre no 45
Leçon : Théorie des groupes
Chap. préc. :Groupes libres, premiers éléments
Chap. suiv. :Groupes libres : théorème de Howson

Exercices :

Groupes libres : théorème de Nielsen-Schreier
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des groupes : Groupes libres : théorème de Nielsen-Schreier
Théorie des groupes/Groupes libres : théorème de Nielsen-Schreier
 », n'a pu être restituée correctement ci-dessus.

Dans ce chapitre, on va démontrer le théorème de Nielsen-Schreier, selon lequel tout sous-groupe d'un groupe libre est lui-même un groupe libre. La longueur du chapitre tient surtout à ce qu'on est entré dans des minuties dont on espère qu'elles aideront le lecteur à se sentir en terrain solide[1].

Pour un ensemble X, nous définirons, comme au chapitre Groupes libres, premiers éléments, le groupe libre F(X) construit sur X comme l'ensemble des mots signés réduits sur X, muni de la loi de groupe « juxtaposition suivie de réduction ».

Comme au chapitre Groupes libres, premiers éléments, nous noterons la base canonique de F(X), c'est-à-dire l'ensemble des ((x, 1)), où x parcourt X. Donc est l'ensemble de ce que nous appelons les lettres signées sur X, autrement dit l'ensemble des mots signés (réduits) de longueur 1 sur X.

Pour un mot signé et un mot signé , nous utiliserons de nouveau la notation pour désigner le mot signé

Segments initiaux et parties schreiériennes[modifier | modifier le wikicode]


Dire que est un segment initial de revient à dire qu'il existe un mot signé tel que . Le mot signé vide et w lui-même sont des segments initiaux de w. Si le plus long segment initial propre de est



Par exemple d'après la seconde des caractérisations qu'on vient de donner d'une partie schreiérienne, il est clair que toute partie schreiérienne de F(X) comprend l'élément 1 de F(X), c'est-à-dire le mot signé vide.

Transversales droites de Schreier[modifier | modifier le wikicode]


Début d’un théorème
Fin du théorème

Démonstration. Dans la présente démonstration, on dira simplement « classe à droite » pour « classe à droite de H dans F(X) ».
Pour toute classe à droite C, définissons la longueur de C comme le plus petit nombre naturel n tel que C comprenne un élément (mot signé) de longueur n.
Pour tout nombre naturel n, désignons par l'ensemble des classes à droite de longueur n. (Il est possible que soit vide. Si H est d'indice fini dans F(X), il n'y a qu'un nombre fini de classes à droite, donc les longueurs de ces classes ne prennent qu'un nombre fini de valeurs.)
Soit n un nombre naturel, soit une partie de F(X) possédant les propriétés suivantes :

(1) tout élément de est de longueur n et appartient à une classe à droite de longueur n;
(2) pour toute classe à droite C de longueur n, il existe un et un seul élément de qui appartient à C.

Soit maintenant K une classe à droite de longueur n + 1 (s'il en existe). Nous allons prouver

(thèse 3) qu'il existe dans K un mot signé de longueur n + 1 dont le plus long segment initial propre (autrement dit le segment initial de longueur n) appartient à .

Choisissons dans K un élément de longueur n + 1, soit

Alors est de longueur n.
Prouvons que

(thèse 4) la classe à droite est de longueur n.

Puisqu'elle comprend l'élément , qui, comme on l'a noté, est de longueur n, la classe à droite est de longueur Si elle était de longueur elle serait donc de longueur < n et comprendrait donc un élément w de longueur < n.
Pour un tel élément w, on aurait

d'où

d'où, par choix de

donc K comprendrait l'élément de longueur long(w) + 1 donc K serait de longueur ce qui contredit les hypothèses sur K. La contradiction obtenue prouve notre thèse (4), à savoir que

la classe à droite est de longueur n.

Nous pouvons donc faire dans l'hypothèse (2). Nous trouvons que

(5) comprend un élément de longueur n qui appartient à .

De

résulte

d'où, par choix de

(6)

(Nous allons voir que le mot signé est réduit.)
Puisque la classe à droite K est supposée de longueur n + 1, son élément est de longueur au moins n + 1, ce qui n'est possible que s'il est de longueur n + 1 exactement.
Donc est un mot signé réduit de longueur n + 1 qui, d'après (6), appartient à K et dont, d'après (5), le plus long segment initial propre appartient à .
Nous avons donc démontré notre thèse (3), à savoir que si satisfait aux hypothèses (1) et (2), alors toute classe à droite K de longueur n + 1 comprend un mot signé de longueur n + 1 dont le plus long segment initial propre appartient à .
D'après l'axiome du choix, il existe donc une application de (ensemble des classes à droite de longueur n + 1) dans F(S) telle que, pour toute classe à droite K de longueur n + 1,

(7)n soit un mot signé de longueur n + 1 appartenant à K

et

(8) le plus long segment initial propre de appartienne à

Désignons par l'image de l'application .
Alors, d'après (7) et (8),

(9) tout élément de est un mot signé de longueur n + 1 et appartient à une classe à droite de longueur n + 1;
(10) pour toute classe à droite K de longueur n + 1, il existe un et un seul élément de qui appartient à K;
(11) pour tout élément v de , le plus long segment initial propre de v appartient à

Les deux premières de ces trois propriétés sont les analogues de (1) et (2) avec n + 1 au lieu de n. D'après la théorie des ensembles, nous pouvons donc construire inductivement, en partant de une suite infinie

possédant les propriétés suivantes :

(12) tout élément de est de longueur n et appartient à une classe à droite de longueur n;
(13) pour toute classe à droite C de longueur n, il existe un et un seul élément de qui appartient à C;
(14) pour tout élément v de , le plus long segment initial propre de v appartient à

Prouvons que est alors une transversale droite de Schreier de H dans F(X).
Prouvons d'abord que c'est une transversale droite de H dans F(X).
Soit C une classe à droite; il s'agit de prouver

(thèse 15) qu'il existe un et un seul élément de qui appartient à C.

Notons la longueur de la classe à droite C. D'après (13),

(16) il existe un et un seul élément de qui appartient à C.

Si est un nombre naturel distinct de , si w est un élément de , alors, d'après (12), la classe à droite de w modulo H est de longueur et est donc distincte de C, donc aucun élément de n'appartient à C.
Joint à (16), cela prouve notre thèse (15), donc

est une transversale droite de H dans F(X).

Prouvons que cette transversale droite est schreiérienne.
Soit w un mot signé de longueur non nulle appartenant à ; il s'agit de prouver que

(thèse 17) le plus long segment initial propre de w appartient à .

Notons la longueur de w; donc Puisque w appartient à pour un certain et que, d'après (12), les éléments de sont de longueur , ce nombre est égal à , donc w appartient à D'après (14), le plus long segment initial propre de w appartient donc à ce qui prouve notre thèse (17) et achève la démonstration.

Théorème de Nielsen-Schreier[modifier | modifier le wikicode]

On va maintenant démontrer le théorème de Nielsen-Schreier, selon lequel tout sous-groupe d'un groupe libre est libre. Quelques lemmes qu'on utilisera à cette fin serviront encore à démontrer un autre théorème, le théorème de Howson.

Soient X un ensemble, T une partie schreiérienne de F(X), w un élément de F(X) n'appartenant pas à T. Il existe au moins un segment initial de w qui n'appartient pas à T (à savoir w), donc nous pouvons considérer le plus court segment initial de w n'appartenant pas à T.

Début d’un théorème
Fin du théorème

Démonstration. Il est clair que si désigne le plus court segment initial de w n'appartenant pas à T, les conditions (i), (ii) et (iii) sont satisfaites. (La condition (i) est satisfaite parce que, comme on l'a noté, toute partie schréiérienne de F(X) comprend le neutre de F(X).)
Il reste à prouver que si un segment initial de w satisfait aux conditions (i), (ii) et (iii), ce segment est le plus court segment initial de w n'appartenant pas à T.
Soit v un segment initial de w strictement plus court que ; il s'agit de prouver que v appartient à T. Or v est un segment initial de Puisque, d'après l'hypothèse (ii), appartient à T et puisque T est schreiérienne, v appartient à T, comme annoncé.

Soient X un ensemble, T une partie schreiérienne de F(X), w un élément de F(X). Il existe au moins un segment initial de w qui appartient à T (à savoir le segment initial vide), donc nous pouvons considérer le plus long segment initial de w qui appartient à T.

Début d’un théorème
Fin du théorème

Démonstration. Il est clair que si désigne le plus long segment initial de w appartenant à T, les conditions (i), (ii) et (iii) sont satisfaites.
Il reste à prouver que si un segment initial de w satisfait aux conditions (i), (ii) et (iii), ce segment est le plus court segment initial de w n'appartenant pas à T.
Soit s un nombre naturel tel que ; il s'agit de prouver que

n'appartient pas à T. Or est un segment initial de et, d'après l'hypothèse (iii), n'appartient pas à T. Puisque T est schreiérienne, il en résulte que n'appartient pas à T, comme annoncé.

Nous avons ainsi démontré la première assertion de l'énoncé. La seconde résulte de la première et du lemme 2.


Début d’un théorème
Fin du théorème

Démonstration. C'est une conséquence immédiate du lemme 2.

Début d’un théorème
Fin du théorème

Démonstration. Soit w un élément de F(X). Puisque T est une transversale droite de H dans F(X),

(1) w s'écrit d'une et une seule façon sous la forme avec h dans H et t dans T.

Alors

(2) h est l'unique élément de H tel que

D'autre part, t appartient à Hw, donc, dans les notations de l'énoncé, donc Donc, d'après (2), est l'unique élément h de H tel que En faisant w = tx, nous obtenons l'assertion 1° de l'énoncé.

Soient t un élément de T et x un élément de tels que

(3)

Puisque appartient à H et que (ceci parce que T est une transversale droite de H dans F(X) et que T, étant schreiérienne, comprend l'élément 1), nous avons donc

De même, puisque appartient à H et que , nous avons

Nous avons donc prouvé l'assertion 2° de l'énoncé (ce qui nous permet de parler de la lettre signée pivot de et de celle de ).

L'hypothèse (3), à savoir signifie

autrement dit

(4)

On vérifie facilement que pour tout élément v de F(X), la condition équivaut à Donc l'hypothèse (3), compte tenu de sa forme (4), revient à

(5)

Prouvons que

(thèse 6)

Dans le cas contraire, on aurait

d'où, en passant aux inverses,

avec t' dans T,
avec t' dans T,

d'où, d'après l'unicité affirmée en (1), ce qui contredit l'hypothèse (3). Nous avons donc prouvé la thèse (6), à savoir

(7)

Prouvons que

(thèse 8)

Dans le cas contraire, t serait de longueur au moins 1 et sa dernière lettre signée serait donc tx serait un segment initial de t (son plus long segment initial propre); puisque t appartient à T et que T est schreiérienne, tx appartiendrait donc à T, ce qui contredit (5). Nous avons donc prouvé la thèse (8), à savoir

(9)

Prouvons que

(thèse 10) ne commence pas par la lettre signée

Dans le cas contraire, finirait par la lettre signée x, donc serait un segment intial de . Mais appartient à T et T est schreiérienne, donc appartiendrait à T, ce qui contredit (7). Nous avons donc prouvé notre thèse (10), à savoir que

(11) ne commence pas par la lettre signée

D'après (9), la dernière lettre signée de tx est x, donc, d'après (11),

ce qui, d'après (9), peut s'écrire

(12)

ce qui prouve l'assertion 3° de l'énoncé.

Nous avons vu en (5) que tx n'appartient pas à T. Puisque t appartient à T, notre résultat (12) et les lemmes 3 et 4 montrent donc que le plus long segment initial de appartenant à T est égal à t et que la lettre signée pivot de (par rapport à T) est x, ce qui prouve les assertions 4° et 5° de l'énoncé.

En passant aux inverses dans la relation (12), nous trouvons

(13)

Nous avons vu en (7) que n'appartient pas à T. Puisque appartient à T, la relation (13) et les lemmes 3 et 4 montrent donc que le plus long segment initial de appartenant à T est égal à et que la lettre signée pivot de (par rapport à T) est , ce qui prouve les assertions 6° et 7° de l'énoncé.

Début d’un théorème
Fin du théorème

Démonstration. Posons x = ((x', 1)) et y = ((y', 1)), avec x' et y' dans X.
D'après le lemme 5, assertions 5° et 7°, la lettre signée pivot de (par rapport à T) est égale à et la lettre signée pivot de (par rapport à T) est D'après l'hypothèse (ii) de l'énoncé, nous avons donc

d'où

(1)

et

(2) x = y,

ce qui prouve les assertions 1° et 2° de l'énoncé.
D'après (1), nous avons

(3) ou bien ou bien

Supposons d'abord

(hyp. 4)

Alors l'hypothèse (i) de l'énoncé signifie que

le plus long segment initial de appartenant à T est égal au plus long segment initial de appartenant à T.

D'après le lemme 5, assertion 4°, cela revient à dire que t = u, ce qui achève de démontrer l'énoncé dans l'hypothèse (4).
Si maintenant l'hypothèse (4) n'est pas satisfaite, alors, d'après (3),

Donc l'hypothèse (i) de l'énoncé signifie que

le plus long segment initial de appartenant à T est égal au plus long segment initial de appartenant à T.

D'après le lemme 5, assertion 6°, cela revient à dire que

(5)

où, pour tout élément w de F(X), désigne l'unique élément de T appartenant à Hw.
Nous avons vu en (2) que y = x, donc notre résultat (5) peut s'écrire

d'où

Htx = Hux
Ht = Hu,

Comme t appartient à T et que u est l'unique élément de T qui appartient à Hu, on a donc t = u, ce qui achève de démontrer l'énoncé.

Début d’un théorème
Fin du théorème

Démonstration. Rappelons que d'après le lemme 5, assertion 2°, de sorte qu'il est légitime de parler du plus court segment initial de n'appartenant pas à T.
On raisonne par récurrence sur r. Pour r = 1, l'énoncé est banal. Supposons que r est au moins égal à 2 et que l'énoncé est vraie pour r - 1 au lieu de r.

(1) Notons , avec le plus court segment initial de n'appartenant pas à T.

Par hypothèse de récurrence sur r, commence par On peut donc écrire

(2)

avec
Alors

(3)

désigne la loi de groupe de F(X). D'après le lemme 5, assertion 3°, est de la forme

(4) avec

Le résultat (3) s'écrit alors

(5)

Supposons que l'énoncé soit faux, c'est-à-dire que

(hyp. 6) ne commence pas par le plus court segment initial de n'appartenant pas à T.

D'après (4) et le lemme 2, cela revient à dire que

ne commence pas par

ce qui, d'après (5), revient à dire que

ne commence pas par

Vu la définition de la loi de groupe de F(X), il faut donc que

(7) commence par

On a vu en (4) que appartient à T et que n'appartient pas à T, donc, d'après (7) et le lemme 2,

(8) est le plus court segment initial de n'appartenant pas à T.

D'autre part, d'après (1), appartient à T et n'appartient pas à T, donc, d'après le lemme 2, le plus court segment initial de n'appartenant pas à T est La comparaison de ceci avec (8) donne

(9)

D'après (4) et le lemme 2, le membre gauche de (9) est le plus court segment initial de n'appartenant pas à T et, d'après (1), le membre droit de (9) est le plus court segment initial de n'appartenant pas à T. La relation (9) signifie donc que

le plus court segment initial de n'appartenant pas à T et le plus court segment initial de n'appartenant pas à T sont égaux.

D'après le lemme 6, on a donc

(10)

et , ces deux égalités entraînant évidemment

(11)

Les résultats (10) et (11) contredisent l'hypothèse (2), selon laquelle le mot signé sur Y est réduit. Cette contradiction prouve que notre hypothèse (6) est fausse, donc l'énoncé est vrai.

Début d’un théorème
Fin du théorème

Démonstration. Désignons par Y l'ensemble

Il s'agit donc de prouver que Y est une base du groupe H.
D'après le chapitre Classes modulo un sous-groupe, section Sous-groupe d'indice fini d'un groupe de type fini, l'ensemble des avec et est une partie génératrice de H. Il est clair que si on ôte l'élément 1 d'une partie génératrice d'un groupe, on obtient encore une partie génératrice de ce groupe (le sous-groupe engendré par une partie A contient , donc, par minimalité du sous-groupe engendré par , le sous-groupe engendré par est contenu dans le sous-groupe engendré par A). Donc

Y est une partie génératrice de H.

D'après la définition d'une partie libre donnée au chapitre Groupes libres, premiers éléments, une partie d'un groupe G est une partie libre de G si et seulement c'est une base du sous-groupe de G qu'elle engendre. Donc, pour prouver que Y est une base de H, il suffit de prouver que

(thèse 1) Y est une partie libre de F(X).

Soient r un nombre naturel des éléments de T, des éléments de la base canonique de F(X), des éléments de tels que

soient tous dans F(X)

et que

(hyp. 2) le mot signé sur Y soit réduit.

Pour prouver notre thèse (1), il s'agit de prouver que

(thèse 3) dans F(X).

Puisque les sont distincts de 1, ils n'appartiennent pas à T (voir lemme 5, assertion 2°), donc on peut parler du plus court segment initial de n'appartenant pas à T. D'après le lemme 7,

(4) commence (une fois explicité dans F(X)) par le plus court segment initial de n'appartenant pas à T.

Puisque ce segment initial n'appartient pas à T, il est distinct de 1, donc le résultat (4) entraîne la thèse (3), donc l'énoncé est démontré.

On va maintenant introduire quelques définitions qui permettront d'étendre le lemme 8 aux groupes libres généraux au lieu des groupes libres F(X). C'est un petit travail assez trivial, sur lequel on peut passer rapidement.

Remarques. 1. Toujours dans l'hypothèse où X est une base de L, désignons par l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X qui représente a dans la base X de L (voir chapitre Groupes libres, premiers éléments, énoncé 6). Pour des éléments v, w de L, dire que v est un segment intial de w relativement à la base X de L revient à dire que est un segment initial de dans le premier sens de l'expression « segment initial ».
2. Soient v et w des éléments du groupe libre F(X) construit sur l'ensemble X. Dire que v est un segment initial de w relativement à la base canonique de F(X) revient à dire que v est un segment initial de w dans le premier sens de l'expression « segment initial ». En effet, soient et . Alors et , où les membres droits sont calculés selon la loi de groupe de F(X). Donc, si désigne l'isomorphisme de F(X) sur qui à tout élément u de F(X) (mot signé sur X) fait correspondre le mot signé sur qui représente u dans la base de F(X), nous avons

où le membre droit est calculé dans le groupe . Autrement dit,

De même,

Donc, d'après la remarque 1, v est un segment initial de w relativement à la base de F(X) si et seulement si est un segment initial de au premier sens de l'expression « segment initial ». Ceci revient clairement à ce que soit un segment initial de au premier sens de l'expression « segment initial », autrement dit à ce que v soit un segment initial de w au premier sens de l'expression « segment initial ».

Remarques. 1. Dans les mêmes hypothèses, désignons de nouveau par l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. D'après la première remarque sur la définition d'un segment initial relativement à une base, dire que S est une partie schreiérienne de L relativement à la base X de L revient à dire que est une partie schreiérienne de F(X) dans le premier sens de l'expression « partie schreiérienne ».
2. D'après la seconde remarque sur la définition d'un segment initial relativement à une base, dire qu'une partie S du groupe libre F(X) construit sur X est une partie schreiérienne de F(X) relativement à la base revient à dire que S est une partie schreiérienne de F(X) au premier sens de l'expression « partie schreiérienne ».

Début d’un théorème
Fin du théorème

Démonstration. Désignons par l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. D'après le lemme 1, il existe une transversale droite T de dans F(X) qui est une partie schreiérienne de F(X) au premier sens de l'expression « partie schreiérienne ». Alors, d'après la première remarque sur la définition d'une partie schreiérienne relativement à une base, est une partie schreiérienne de L relativement à la base de X. D'autre part, puisque T est une transversale droite de dans F(X), est une transversale droite de K dans L (cela tient simplement à ce que est un isomorphisme).
Donc est une transversale droite de Schreier de K dans L relativement à la base X, ce qui démontre l'énoncé.

Début d’un théorème
Fin du théorème

Démonstration. D'après la remarque 2 suivant la définition d'une partie schreiérienne relativement à une base, le lemme 8 est un cas particulier du lemme 10. On aurait pu rédiger la démonstration du lemme 8 de façon qu'elle fournisse tout de suite l'énoncé général, mais on va déduire l'énoncé général de l'énoncé particulier.
Désignons de nouveau par l'isomorphisme de L sur F(X) qui à tout élément a de L fait correspondre le mot signé sur X représentant a dans la base X. Alors (pour u dans U et x dans X) est l'unique élément de tel que

autrement dit tel que

Donc, si on pose et ,

T est une transversale droite de Schreier (au premier sens) de H dans F(X)

et

où, comme au lemme 8, désigne l'unique élément de H tel que

D'après le lemme 8, les avec forment une base de En passant aux images par on trouve que

les avec forment une base du groupe K.

Puisque les avec sont les cela revient à dire que les avec forment une base du groupe K, ce qu'il fallait démontrer.

Début d’un théorème
Fin du théorème

Démonstration. C'est une conséquence immédiate du lemme 10.

Remarques. 1. On déduit immédiatement du lemme 8 que tout sous-groupe de F(X) est un groupe libre, ce qui est un cas particulier du théorème de Nielsen-Schreier. Puisque tout groupe libre est isomorphe à un groupe F(X), on en déduit facilement le théorème de Nielsen-Schreier dans sa forme générale. Donc, si on ne s'intéressait qu'au théorème de Nielsen-Schreier, on pourrait se passer de ce qui suit le lemme 8 et précède l'énoncé 11. Néanmoins, le lemme 10 n'est pas sans intérêt, car il permet de traiter directement des groupes libres qui ne sont pas du type F(X) (voir les exercices).
2. On verra dans les exercices que le rang d'un sous-groupe d'un groupe libre L peut être strictement supérieur au rang de L (ce qui rompt l'analogie entre les bases d'un groupe et les bases d'un espace vectoriel).

Notes et références[modifier | modifier le wikicode]

  1. La démonstration qu'on trouvera ici est essentiellement celle que donnent Baumslag et Chandler, Group Theory, 1968, p. 259-263. Il existe d'autres démonstrations, qui, contrairement à celle-ci, font intervenir des théories étrangères.