Introduction aux Générateurs d’un Groupe
En théorie des groupes, l’un des concepts les plus puissants est celui de partie génératrice. Plutôt que d’étudier un groupe en listant tous ses éléments (ce qui est impossible pour les groupes infinis et fastidieux pour les grands groupes finis), on cherche souvent à identifier un petit sous-ensemble d’éléments, appelés générateurs, qui permettent de reconstruire le groupe entier par composition et inversion.
Formellement, si $G$ est un groupe et $S$ est une partie de $G$, le sous-groupe engendré par $S$, noté $\langle S \rangle$, est le plus petit sous-groupe de $G$ contenant $S$. C’est l’ensemble de tous les produits finis d’éléments de $S$ et de leurs inverses. Si $\langle S \rangle = G$, on dit que $S$ est une partie génératrice de $G$.
Le groupe symétrique $\mathcal{S}_n$ est un terrain de jeu fascinant pour l’étude des générateurs. Bien qu’il contienne $n!$ éléments, il peut être engendré par des ensembles d’éléments étonnamment petits et structurés. Comprendre ces ensembles de générateurs nous donne un aperçu profond de la structure combinatoire de $\mathcal{S}_n$ et a des applications pratiques, notamment en algorithmique.
Soit $(G, \cdot)$ un groupe et $S$ une partie de $G$. On dit que $S$ engendre $G$ (ou que $S$ est une partie génératrice de $G$) si tout élément de $G$ peut s’écrire comme un produit fini d’éléments de $S$ et de leurs inverses. On note alors $G = \langle S \rangle$.
1. Génération par l’Ensemble de toutes les Transpositions
Le premier ensemble de générateurs, et le plus naturel, est celui qui contient toutes les permutations les plus simples (autres que l’identité) : les transpositions, c’est-à-dire les cycles de longueur 2.
Pour tout entier $n \ge 2$, le groupe symétrique $\mathcal{S}_n$ est engendré par l’ensemble de toutes les transpositions de la forme $(i \ j)$ avec $1 \le i < j \le n$.
Démonstration
La preuve est constructive et repose sur la décomposition en cycles disjoints.
- Toute permutation est un produit de cycles : Nous savons que toute permutation $\sigma \in \mathcal{S}_n$ peut s’écrire comme un produit de cycles à supports disjoints. Si nous pouvons montrer que chaque cycle peut être écrit comme un produit de transpositions, alors par substitution, toute permutation pourra l’être aussi.
- Tout cycle est un produit de transpositions : Considérons un $k$-cycle quelconque $(a_1 \ a_2 \ \dots \ a_k)$. On peut vérifier par calcul direct qu’il admet la décomposition suivante : $$ (a_1 \ a_2 \ \dots \ a_k) = (a_1 \ a_k) \circ (a_1 \ a_{k-1}) \circ \dots \circ (a_1 \ a_3) \circ (a_1 \ a_2) $$ Cette formule montre comment « construire » un cycle en enchaînant des échanges qui ramènent progressivement les éléments à leur place. Une autre décomposition possible est : $$ (a_1 \ a_2 \ \dots \ a_k) = (a_1 \ a_2) \circ (a_2 \ a_3) \circ \dots \circ (a_{k-1} \ a_k) $$
- Conclusion : Puisque toute permutation est un produit de cycles, et que tout cycle est un produit de transpositions, il s’ensuit que toute permutation est un produit de transpositions. L’ensemble des transpositions engendre donc bien $\mathcal{S}_n$.
Exemple
Soit la permutation $\sigma = (1 \ 5 \ 3) \circ (2 \ 4)$ dans $\mathcal{S}_5$. On décompose chaque cycle en transpositions :
- $(1 \ 5 \ 3) = (1 \ 3) \circ (1 \ 5)$
- $(2 \ 4)$ est déjà une transposition.
Ce premier résultat est fondamental, mais l’ensemble de toutes les transpositions est assez grand (il contient $\frac{n(n-1)}{2}$ éléments). On peut faire beaucoup mieux.
2. Génération par les Transpositions Adjacentes
On peut réduire drastiquement la taille de notre ensemble générateur en ne conservant que les transpositions qui échangent des éléments consécutifs.
Pour tout entier $n \ge 2$, le groupe symétrique $\mathcal{S}_n$ est engendré par l’ensemble des $n-1$ transpositions adjacentes : $$ S = \{ (1 \ 2), (2 \ 3), \dots, (n-1 \ n) \} $$
Démonstration
Puisque nous savons déjà que l’ensemble de toutes les transpositions engendre $\mathcal{S}_n$, il suffit de montrer que nous pouvons obtenir n’importe quelle transposition $(i \ j)$ en utilisant uniquement des transpositions adjacentes.
Soit une transposition quelconque $(i \ j)$ avec $i < j$. Nous pouvons l'obtenir en "rapprochant" $i$ de $j$ par des échanges successifs, en effectuant l'échange, puis en "remettant" les autres éléments à leur place. Une formule explicite utilise la conjugaison. Montrons comment obtenir $(i \ i+2)$ : $$ (i+1 \ i+2) \circ (i \ i+1) \circ (i+1 \ i+2) = (i \ i+2) $$ De manière générale, pour obtenir $(i \ j)$ avec $j > i+1$, on peut utiliser la relation de conjugaison : $$ (j-1 \ j) \circ (i \ j-1) \circ (j-1 \ j) = (i \ j) $$ En appliquant cette formule de manière récursive, on peut construire toute transposition $(i \ j)$ à partir de $(i \ i+1)$. Par exemple, pour obtenir $(i \ j)$, on construit d’abord $(i \ j-1)$, puis on le conjugue par $(j-1 \ j)$.
Exemple : Obtenir $(1 \ 3)$ dans $\mathcal{S}_3$ ou $\mathcal{S}_4$
Les générateurs adjacents sont $(1 \ 2)$ et $(2 \ 3)$. En appliquant la formule de conjugaison : $$ (1 \ 3) = (2 \ 3) \circ (1 \ 2) \circ (2 \ 3) $$ Vérifions :
- $1 \xrightarrow{(2 \ 3)} 1 \xrightarrow{(1 \ 2)} 2 \xrightarrow{(2 \ 3)} 3$
- $3 \xrightarrow{(2 \ 3)} 2 \xrightarrow{(1 \ 2)} 1 \xrightarrow{(2 \ 3)} 1$
- $2 \xrightarrow{(2 \ 3)} 3 \xrightarrow{(1 \ 2)} 3 \xrightarrow{(2 \ 3)} 2$ (point fixe)
3. Génération par Seulement Deux Éléments
Peut-on être encore plus minimaliste ? La réponse est oui. Il est remarquable que le groupe symétrique, malgré sa taille factorielle, puisse être engendré par seulement deux permutations bien choisies.
Pour tout entier $n \ge 2$, le groupe symétrique $\mathcal{S}_n$ est engendré par la transposition $(1 \ 2)$ et le cycle long $(1 \ 2 \ \dots \ n)$. $$ \mathcal{S}_n = \langle (1 \ 2), (1 \ 2 \ \dots \ n) \rangle $$
Démonstration
L’idée est de montrer que l’on peut générer toutes les transpositions adjacentes à partir de ces deux éléments. Comme les transpositions adjacentes engendrent $\mathcal{S}_n$, cela suffira à prouver le théorème. Notons $\tau = (1 \ 2)$ et $c = (1 \ 2 \ \dots \ n)$.
Calculons les conjugués successifs de $\tau$ par les puissances de $c$. Rappelons la formule de conjugaison d’un cycle : si $\sigma = (a_1 \ \dots \ a_k)$, alors $g \sigma g^{-1} = (g(a_1) \ \dots \ g(a_k))$.
- $c \tau c^{-1} = c(1 \ 2)c^{-1} = (c(1) \ c(2)) = (2 \ 3)$
- $c^2 \tau c^{-2} = c(2 \ 3)c^{-1} = (c(2) \ c(3)) = (3 \ 4)$
- …
- $c^{k-1} \tau c^{-(k-1)} = (k \ k+1)$
- …
- $c^{n-2} \tau c^{-(n-2)} = (n-1 \ n)$
En conjuguant la transposition $(1 \ 2)$ par le cycle long, nous avons réussi à générer toutes les transpositions adjacentes : $(2 \ 3), (3 \ 4), \dots, (n-1 \ n)$. Nous avons donc l’inclusion : $$ \{ (2 \ 3), \dots, (n-1 \ n) \} \subset \langle \tau, c \rangle $$ Le sous-groupe engendré par $\tau$ et $c$ contient également $\tau=(1 \ 2)$. Il contient donc toutes les transpositions adjacentes. D’après le Théorème 2, ce sous-groupe est $\mathcal{S}_n$ tout entier.
Conclusion : L’Économie des Générateurs
L’étude des générateurs du groupe symétrique illustre un principe clé en algèbre : la recherche de la structure minimale qui définit un objet complexe. Nous sommes passés d’un ensemble de $\frac{n(n-1)}{2}$ transpositions à un ensemble de $n-1$ transpositions adjacentes, pour finalement arriver à seulement deux éléments bien choisis.
Cette hiérarchie de générateurs n’est pas seulement une curiosité théorique. Elle est fondamentale en algèbre computationnelle, où la complexité des algorithmes dépend souvent du nombre de générateurs. Elle est aussi à la base de la théorie des présentations de groupes, qui vise à décrire un groupe par ses générateurs et les relations qu’ils satisfont, offrant ainsi une description finie et complète de la structure du groupe.