L'usage de calculatrices électroniques de poche à alimentation autonome, non imprimantes et sans document d'accompagnement, est autorisé. Cependant, une seule calculatrice à la fois est admise sur la table ou le poste de travail, et aucun échange n'est autorisé entre les candidats.

On appelle alphabet tout ensemble fini non vide. Si est un alphabet, on appelle ses éléments des lettres. Un mot sur l'alphabet est une suite finie de lettres de . La longueur de cette suite est appelée la longueur du mot, notée . Par exemple, si est un mot de longueur 3 et est un mot de longueur 7. Par convention, on considère aussi une suite de longueur 0 , appelée le mot vide et notée 1 . On note l'ensemble de tous les mots sur l'alphabet , y compris le mot vide.

Un ensemble muni d'une loi de composition interne sera noté ( ) ou simplement lorsque la loi considérée est sans ambiguïté. Si la loi est associative et si contient un élément neutre pour noté , on dit que est un monoïde. Si est un alphabet, muni de la concaténation est un monoïde. On rappelle que la concaténation de deux mots et , notée , est la suite de lettres qui commence par la suite et continue avec la suite . Pour les mots et cités en exemple ci-dessus, on a . Si est un mot et est un entier strictement positif, on note la concaténation de copies de . On peut ainsi écrire et .
et sont des monoïdes, un morphisme est une application telle que et telle que pour tout . Un isomorphisme est un morphisme bijectif. Un élément d'un monoïde ( ) est dit inversible s'il existe tel que . Dans ce cas, est unique et est appelé l'inverse de , noté . Rappelons qu'un groupe est un monoïde dont tout élément est inversible.

On notera le cardinal d'un ensemble fini , c'est-à-dire le nombre d'éléments de .

Dans ce sujet, on étudie les groupes libres. Ces groupes se caractérisent par le fait qu'ils sont entièrement déterminés par un ensemble de générateurs abstraits (ce qui justifie la terminologie, puisqu'ils sont libres de toute relation entre leurs générateurs). On examinera des propriétés élémentaires des groupes libres et quelques problèmes algorithmiques les concernant. On démontrera en particulier que tout sousgroupe d'un groupe libre est lui-même un groupe libre s'il est engendré par un nombre fini d'éléments.

Note : Quand on parle d'algorithmes ici, on demande de préciser les principes d'un algorithme et non de donner du pseudo-code.

Dans cette partie, on reprend quelques propriétés élémentaires des monoïdes et des groupes.
Question 1.1 Soient et des monoïdes et un morphisme.
1.1.1 Montrer que si est un isomorphisme alors sa réciproque est un morphisme.
1.1.2 Montrer que si et sont des groupes alors, pour tout .

Soit un monoïde et une partie de . On dit que ( ) est un sous-monoïde de si et si pour tout . Si, de plus, est un groupe et pour tout , on dit que ( ) est un sous-groupe de .

Question 1.2 Soit une partie d'un monoïde ( ).
1.2.1 Soit l'ensemble consistant en l'élément neutre et les produits finis d'éléments de , c'est- -dire les éléments avec et chaque . Montrer que * est un sous-monoïde de M qui est minimal pour l'inclusion parmi tous les sous-monoïdes contenant .
1.2.2 Si est un groupe, soit . Montrer alors que est un sous-groupe de qui est minimal pour l'inclusion parmi tous les sous-groupes contenant .

Dans ce dernier cas, on appelle le sous-groupe engendré par .

Soit un alphabet. Pour chaque lettre , on introduit une nouvelle lettre et on note l'alphabet . On étend l'application à en posant pour tout .

Soient . On dit que se réduit en une étape en , noté , si avec , et . Si , on note s'il existe des mots tels que , et pour . On note encore si s'il existe tel que , et s'il existe tel que . Enfin, on dit qu'un mot est réduit s'il n'existe aucun mot tel que , c'est-à-dire si ne contient pas deux lettres consécutives de la forme avec . En particulier, le mot vide est réduit.

Question 2.1 Montrer que pour tout mot , il existe un mot réduit tel que . Calculer un tel mot lorsque .

Question 2.2 Soient . Montrer que si et , alors il existe tel que et .

Question 2.3 Montrer que pour tout mot , il existe un unique mot réduit tel que .
Question 2.4 Donner un algorithme qui, étant donné , calcule l'unique mot réduit tel que . Estimer la complexité (le nombre d'opérations élémentaires) de cet algorithme en fonction de la longueur . Essayer de réduire cette complexité autant que possible en ordre de grandeur.

Soit un alphabet. On note l'ensemble des mots réduits de et l'application qui à associe l'unique mot réduit tel que . On définit une loi de composition interne sur en posant . Enfin, on étend l'application à en posant

Question 3.1 Montrer que si alors . En déduire que est un groupe et que, pour tout .

On appelle le groupe libre sur . On appelle groupe libre tout groupe isomorphe à un groupe de la forme .

Question 3.2 Sous quelles hypothèses le groupe est-il commutatif (c'est-à-dire tel que pour tout ) ?

Question 3.3 Soit un groupe et soit une application. Montrer qu'il existe un et un seul morphisme tel que pour tout .

Dans la situation de la question 3.3, on dit que le morphisme est induit par l'application , ou qu'il la prolonge. Dans la suite, on utilisera librement le résultat de cette question : toute application de dans un groupe induit un unique morphisme de dans .

Question 3.4 Soit et deux alphabets de même cardinal. Montrer que et sont isomorphes.

Soit une partie finie non vide de . On dit que est une base de s'il existe un alphabet de même cardinal que et une bijection tels que le morphisme induit par est un isomorphisme.

Le but de cette partie est de montrer que toutes les bases de ont le même cardinal.
Question 4.1 Vérifier que est une base de . Montrer que la condition pour qu'une partie de soit une base ne dépend pas du choix de l'alphabet et de la bijection .

Question 4.2 Supposons que .
4.2.1 Soient et . Exprimer a et comme produits (pour la loi ) d'éléments de la forme et et en déduire que est une base de .
4.2.2 Montrer que n'est pas une base de . On montrera que si , le morphisme induit par tel que et a n'est pas surjectif.

Question 4.3 Soient et deux alphabets et soit un morphisme. On considère un -espace vectoriel de dimension card et une base de . Comme muni de l'addition est un groupe, on peut définir un morphisme induit par une bijection ( et ont même cardinal). De même, on définit , une base de et un morphisme à partir d'une bijection .
4.3.1 Montrer qu'il existe une application linéaire telle que , comme ci-dessous :

4.3.2 Montrer que si le morphisme est surjectif, alors card . Pour cela, on pourra montrer que l'application linéaire est surjective.
4.3.3 Montrer que toutes les bases de ont le même cardinal.

Le cardinal commun des bases de , à savoir card , est appelée le rang de . Si est un groupe isomorphe à , on dit que est un groupe libre de rang card . Si est un isomorphisme et si est une partie de telle que est une base de , on dit que est une base de .

Question 4.4 Soit , soit un alphabet à éléments, , et soit le morphisme induit par l'application .
4.4.1 Montrer que si et est un entier relatif non nul, alors . (Si , dénote le mot .)
4.4.2 Montrer que est injectif.
4.4.3 En déduire qu'un groupe libre de rang 2 admet comme sous-groupes des groupes libres de tout rang fini.

Soit . On dit que le mot est cycliquement réduit si est le mot vide ou si ( et pour tout ) est réduit et . On observera que est cycliquement réduit si et seulement si le mot est réduit.

Question 5.1 Montrer que tout mot réduit admet une unique factorisation de la forme , où est cycliquement réduit. En déduire que si n'est pas le mot vide, alors pour tout entier , .

Soient . On dit que et sont conjugués et on note s'il existe un mot tel que .

Question 5.2 Montrer que la relation de conjugaison est une relation réflexive, symétrique et transitive.

Question 5.3 Soient et deux mots cycliquement réduits non vides. Montrer que u et v sont conjugués si et seulement si est une permutation cyclique de , c'est-à-dire s'il existe des mots tels que et .

Question 5.4 Donner un algorithme pour décider si deux mots sont conjugués.

On définit un graphe orienté -étiqueté (on dira simplement un -graphe) comme une paire où est un ensemble fini, appelé ensemble des sommets, et est une partie de , appelée ensemble des arêtes. Il est commode de représenter une arête ( ) par une flèche du sommet vers le sommet étiquetée par la lettre , comme illustré figure 1 .

Si , on note le triplet . Soit . Un chemin dans le -graphe est une suite finie de la forme

où chaque . On dit alors que est un chemin de à , de longueur et d'étiquette le mot . Par convention, on considère que, pour tout sommet , il existe un chemin de longueur 0 de à , appelé chemin vide en . Dans le -graphe de la figure 1 , il existe par exemple des chemins de à étiquetés (il en existe une infinité d'autres), ainsi que des chemins étiquetés et de à .

Si un chemin ne comporte pas deux arêtes consécutives de la forme avec , on dit qu'il est réduit. Enfin, on dit que le graphe est réduit si, pour tout sommet et toute lettre contient au plus une arête de la forme et au plus une arête de la forme . Le -graphe de la figure 1 n'est pas réduit puisque deux arêtes étiquetées partent du sommet .

Dans toute cette partie, on considère un -graphe fini réduit .

Question 6.1 Montrer que l'étiquette d'un chemin est réduite si et seulement si le chemin est réduit.
Question 6.2 Montrer que si est l'étiquette d'un chemin du sommet au sommet , alors est l'étiquette d'un chemin réduit de à .

Si est un sommet de , on note l'ensemble des étiquettes des chemins réduits de à .

Question 6.3 Montrer que est un sous-groupe de .
On dit que le -graphe est connexe si, pour tous sommets de , il existe au moins un chemin de à (et donc au moins un chemin réduit, d'après la question 6.2). On dit que est une forêt si, pour tous sommets de , il existe au plus un chemin réduit de à . Une forêt connexe est appelée un arbre.

Question 6.4 Que peut-on dire de lorsque est une forêt ?
Pour le reste de cette partie, le -graphe fini réduit est supposé connexe et on fixe un sommet de .

Si et , on dit que le graphe est un sous-graphe de , et qu'il est couvrant si . On parle enfin de sous-arbre couvrant si de plus est un arbre.

Question 6.5 Montrer que admet un sous-arbre couvrant et donner un algorithme de calcul d'un tel arbre.

Soit un sous-arbre couvrant de . Pour tout sommet de , soit l'étiquette de l'unique chemin réduit de à dans . Pour chaque arête de n'appartenant pas à , posons . On notera que par construction, est un mot réduit.

Question 6.6 Montrer que tout élément de est le produit, dans , de mots de la forme ou .

Indication. On pourra pour cela considérer un élément , un chemin réduit d'étiquette de à , une factorisation où les sont des chemins réduits dans et les sont des éléments de , puis montrer que l'étiquette de est égale à où est le sommet final de et le sommet initial de .

Question 6.7 Soit . Montrer que est isomorphe à un groupe libre de rang de base .

Dans cette partie, on va montrer que tout sous-groupe finiment engendré d'un groupe libre est libre.
Soit la paire consistant en un -graphe et un sommet de . On note l'ensemble des étiquettes des chemins de à dans le -graphe ( ) et ) l'ensemble .

Si n'est pas réduit, il existe deux arêtes de de la forme ( ) et ( ), ou bien ( ) et ( ). Soit alors la paire obtenue à partir de en "fusionnant" les sommets et . Plus précisément, on définit et de la façon suivante. L'ensemble des sommets de est
où est un nouveau symbole n'appartenant pas à . L'ensemble d'arêtes est obtenu à partir de en remplaçant partout et par et en ôtant les doublons éventuels. Le sommet est égal à si , à sinon. On dit alors que se réduit en une étape en , noté .

On dit que la paire est réduite si le -graphe est réduit.
Question 7.1 Montrer que si , alors

Question 7.2 Montrer que si est le sous-groupe de engendré par les mots , alors est un groupe libre.
Indication. Pour cela on pourra construire une paire telle que , puis réduire .
Question 7.3 Soient des éléments de et soit le sous-groupe de qu'ils engendrent. Donner un algorithme pour trouver une base de et en évaluer la complexité.

Les questions de cette dernière partie donnent deux représentations d'un groupe libre , c'est-àdire des morphismes injectifs de dans un autre groupe, moins abstrait.

Question 8.1 Dans cette question, on suppose que . Soit le groupe des matrices carrées d'ordre 2 à coefficients réels, inversibles pour le produit de matrices, et soient

Montrer qu'il existe un morphisme injectif de dans tel que et .
Indication. On considérera les quatre régions du plan et décrites ci-dessous et représentées figure 2:

On regardera dans quelles régions se situent les images de ces régions par les applications linéaires , et . Enfin, pour et , on discutera de l'image de ces régions en fonction de et .