Lemme 14.3.2.
Soit \(X\) un \(G\)-ensemble et supposons que \(x \sim y\text{.}\) Alors \(G_x\) est isomorphe à \(G_y\text{.}\) En particulier, \(|G_x| = |G_y|\text{.}\)
Section 14.3 Le théorème de dénombrement de Burnside
Supposons que nous souhaitons colorier les sommets d’un carré avec deux couleurs différentes, disons noir et blanc. On pourrait penser qu’il y aurait \(2^4=16\) coloriages différents. Cependant, certains de ces coloriages sont équivalents. Si nous colorions le premier sommet en noir et les sommets restants en blanc, c’est la même chose que de colorier le deuxième sommet en noir et les autres en blanc, puisque nous pourrions obtenir le second coloriage simplement en faisant pivoter le carré de \(90^\circ\) (Figure 14.3.1).
Le théorème de dénombrement de Burnside offre une méthode pour calculer le nombre de façons distinguables dont quelque chose peut être fait. En plus de ses applications géométriques, le théorème a des applications intéressantes dans les domaines de la théorie des commutateurs et de la chimie. La démonstration du théorème de dénombrement de Burnside repose sur le lemme suivant.
Démonstration.
Faisons agir \(G\) sur \(X\) par \((g,x) \mapsto g \cdot x\text{.}\) Puisque \(x \sim y\text{,}\) il existe un \(g \in G\) tel que \(g \cdot x=y\text{.}\) Soit \(a \in G_x\text{.}\) Puisque
\begin{equation*}
gag^{-1} \cdot y = ga \cdot g^{-1}y = ga \cdot x = g \cdot x = y\text{,}
\end{equation*}
nous pouvons définir une application \(\phi: G_x \rightarrow G_y\) par \(\phi(a) = gag^{-1}\text{.}\) L’application \(\phi\) est un homomorphisme puisque
\begin{equation*}
\phi(ab) = gabg^{-1} = gag^{-1} gbg^{-1} = \phi(a) \phi(b)\text{.}
\end{equation*}
Supposons que \(\phi(a) = \phi(b)\text{.}\) Alors \(gag^{-1}= gbg^{-1}\) ou \(a=b\) ; donc l’application est injective. Pour montrer que \(\phi\) est surjective, soit \(b\) dans \(G_y\) ; alors \(g^{-1}bg\) est dans \(G_x\) puisque
\begin{equation*}
g^{-1}bg \cdot x = g^{-1}b \cdot gx = g^{-1}b \cdot y = g^{-1} \cdot y = x ;
\end{equation*}
et \(\phi(g^{-1}bg ) = b\text{.}\)
Théorème 14.3.3. Burnside.
Soit \(G\) un groupe fini agissant sur un ensemble \(X\) et soit \(k\) le nombre d’orbites de \(X\text{.}\) Alors
\begin{equation*}
k = \frac{1}{|G|} \sum_{g \in G} |X_g|\text{.}
\end{equation*}
Démonstration.
Nous examinons tous les points fixes \(x\) de tous les éléments \(g \in G\) ; c’est-à-dire que nous considérons tous les \(g\) et tous les \(x\) tels que \(gx =x\text{.}\) Vu en termes d’ensembles de points fixes, le nombre de tous les \(g\) qui fixent des \(x\) est
\begin{equation*}
\sum_{g \in G} |X_g|\text{.}
\end{equation*}
Cependant, vu en termes de sous-groupes stabilisateurs, ce nombre est
\begin{equation*}
\sum_{x \in X} |G_x| ;
\end{equation*}
donc \(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\text{.}\) Par Lemme 14.3.2,
\begin{equation*}
\sum_{y \in {\mathcal O}_x} |G_y| = | {\mathcal O}_x| \cdot |G_x|\text{.}
\end{equation*}
Par Théorème 14.1.11 et le théorème de Lagrange, cette expression est égale à \(|G|\text{.}\) En sommant sur toutes les \(k\) orbites distinctes, nous concluons que
\begin{equation*}
\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = k \cdot |G|\text{.}
\end{equation*}
Exemple 14.3.4.
Soit \(X = \{1, 2, 3, 4, 5 \}\) et supposons que \(G\) est le groupe de permutations \(G= \{(1), (1 \, 3), (1 \, 3)(2 \, 5), (2 \, 5) \}\text{.}\) Les orbites de \(X\) sont \(\{1, 3\}\text{,}\) \(\{2, 5\}\) et \(\{4\}\text{.}\) Les ensembles de points fixes sont
\begin{align*}
X_{(1)} & = X\\
X_{(1 \, 3)} & = \{2, 4, 5 \}\\
X_{(1 \, 3)(2 \, 5)} & = \{4\}\\
X_{(2 \, 5)} & = \{1, 3, 4 \}\text{.}
\end{align*}
Le théorème de Burnside affirme que
\begin{equation*}
k = \frac{1}{|G|} \sum_{g \in G} |X_g| = \frac{1}{4}(5 + 3 + 1 + 3) = 3\text{.}
\end{equation*}
Sous-section 14.3.1 Un exemple géométrique
Avant d’appliquer le théorème de Burnside aux problèmes de théorie des commutateurs, examinons le nombre de façons dont les sommets d’un carré peuvent être coloriés en noir ou en blanc. Remarquons que nous pouvons parfois obtenir des coloriages équivalents en appliquant simplement un mouvement rigide au carré. Par exemple, comme nous l’avons signalé, si nous colorions l’un des sommets en noir et les trois autres en blanc, peu importe quel sommet a été colorié en noir puisqu’une rotation donnera un coloriage équivalent.
Le groupe de symétrie d’un carré, \(D_4\text{,}\) est donné par les permutations suivantes :
\begin{align*}
&(1) & &(1 \, 3) & & (2 \, 4) & & (1 \, 4 \, 3 \, 2)\\
&(1 \, 2 \, 3 \, 4) & &(1 \, 2)(3 \, 4) & & (1 \, 4)(2 \, 3) & & (1 \, 3)(2 \, 4)
\end{align*}
Le groupe \(G\) agit sur l’ensemble des sommets \(\{ 1, 2, 3, 4\}\) de la manière habituelle. Nous pouvons décrire les différents coloriages par des applications de \(X\) dans \(Y = \{ N, B \}\) où \(N\) et \(B\) représentent les couleurs noir et blanc, respectivement. Chaque application \(f : X \rightarrow Y\) décrit une façon de colorier les coins du carré. Tout \(\sigma \in D_4\) induit une permutation \(\widetilde{ \sigma }\) des coloriages possibles donnée par \(\widetilde{\sigma}(f) = f \circ \sigma\) pour \(f : X \rightarrow Y\text{.}\) Par exemple, supposons que \(f\) est définie par
\begin{align*}
f(1) & = N\\
f(2) & = B\\
f(3) & = B\\
f(4) & = B
\end{align*}
et \(\sigma = (1 2)(3 4)\text{.}\) Alors \(\widetilde{\sigma}(f) = f \circ \sigma\) envoie le sommet \(2\) vers \(N\) et les sommets restants vers \(B\text{.}\) L’ensemble de tous ces \(\widetilde{\sigma}\) est un groupe de permutations \(\widetilde{G}\) sur l’ensemble des coloriages possibles. Notons \(\widetilde{X}\) l’ensemble de tous les coloriages possibles ; c’est-à-dire que \(\widetilde{X}\) est l’ensemble de toutes les applications possibles de \(X\) vers \(Y\text{.}\) Nous devons maintenant calculer le nombre de classes d’équivalence sous \(\widetilde{G}\text{.}\)
-
\(\widetilde{X}_{(1)} = \widetilde{X}\) puisque l’identité fixe tout coloriage possible. \(|\widetilde{X}| = 2^4 =~16\text{.}\)
-
\(\widetilde{X}_{(1 \, 2 \, 3 \, 4)}\) est constitué de tous les \(f \in \widetilde{X}\) tels que \(f\) est inchangé par la permutation \((1 \, 2 \, 3 \, 4)\text{.}\) Dans ce cas \(f(1) = f(2) = f(3) = f(4)\text{,}\) de sorte que toutes les valeurs de \(f\) doivent être identiques ; c’est-à-dire que soit \(f(x)= N\) soit \(f(x)= B\) pour tout sommet \(x\) du carré. Donc \(|\widetilde{X}_{(1 \, 2 \, 3 \, 4)}| = 2\text{.}\)
-
\(|\widetilde{X}_{(1 \, 4 \, 3 \, 2)}| = 2\text{.}\)
-
Pour \(\widetilde{X}_{(1 \, 3)(2 \, 4)}\text{,}\) \(f(1) = f(3)\) et \(f(2) = f(4)\text{.}\) Donc \(|\widetilde{X}_{(1 \, 3)(2 \, 4)}| = 2^2 = 4\text{.}\)
-
\(|\widetilde{X}_{(1 \, 2)(3 \, 4)}| = 4\text{.}\)
-
\(|\widetilde{X}_{(1 \, 4)(2 \, 3)}| = 4\text{.}\)
-
Pour \(\widetilde{X}_{(1 \, 3 )}\text{,}\) \(f(1) = f(3)\) et les autres coins peuvent être de n’importe quelle couleur ; donc \(|\widetilde{X}_{(1 \, 3)}| = 2^3 = 8\text{.}\)
-
\(|\widetilde{X}_{(2 \, 4)}| = 8\text{.}\)
Par le théorème de Burnside, nous pouvons conclure qu’il y a exactement
\begin{equation*}
\frac{1}{8} ( 2^4 + 2^1 + 2^2 + 2^1 + 2^2 + 2^2 +2^3 + 2^3) = 6
\end{equation*}
façons de colorier les sommets du carré.
Proposition 14.3.5.
Soit \(G\) un groupe de permutations de \(X\) et \(\widetilde{X}\) l’ensemble des applications de \(X\) vers \(Y\text{.}\) Alors \(G\) induit un groupe \(\widetilde{G}\) qui permute les éléments de \(\widetilde{X}\text{,}\) où \(\widetilde{\sigma} \in \widetilde{G}\) est défini par \(\widetilde{\sigma}(f) = f \circ \sigma\) pour \(\sigma \in G\) et \(f \in \widetilde{X}\text{.}\) De plus, si \(n\) est le nombre de cycles dans la décomposition en cycles de \(\sigma\text{,}\) alors \(|\widetilde{X}_{\sigma}| = |Y|^n\text{.}\)
Démonstration.
Soit \(\sigma \in G\) et \(f \in \widetilde{X}\text{.}\) Puisque \(\sigma\) permute les éléments de \(X\text{,}\) \(f \circ \sigma\) doit aussi être dans \(\widetilde{X}\text{.}\) Supposons que \(g\) est une autre application de \(X\) vers \(Y\) telle que \(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\text{.}\) Alors pour chaque \(x \in X\text{,}\)
\begin{equation*}
f( \sigma(x )) = \widetilde{\sigma}(f)(x) = \widetilde{\sigma}(g)(x) = g( \sigma(x ))\text{.}
\end{equation*}
Puisque \(\sigma\) est une permutation de \(X\text{,}\) tout élément \(x'\) de \(X\) est l’image d’un certain \(x\) de \(X\) par \(\sigma\) ; donc \(f\) et \(g\) coïncident sur tous les éléments de \(X\text{.}\) Par conséquent, \(f=g\) et \(\widetilde{\sigma}\) est injective. L’application \(\sigma \mapsto \widetilde{\sigma}\) est surjective puisque les deux ensembles ont la même taille.
Supposons que \(\sigma\) est une permutation de \(X\) avec décomposition en cycles \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\text{.}\) Tout \(f\) dans \({\widetilde{X}}_{\sigma}\) doit avoir la même valeur sur chaque cycle de \(\sigma\text{.}\) Puisqu’il y a \(n\) cycles et \(|Y|\) valeurs possibles pour chaque cycle, \(|{\widetilde{X}}_{\sigma}| = |Y|^n\text{.}\)
Exemple 14.3.6.
Soit \(X = \{1, 2, \ldots, 7\}\) et supposons que \(Y = \{ A, B, C \}\text{.}\) Si \(g\) est la permutation de \(X\) donnée par \((1 \, 3)(2 \, 4 \, 5) = (1 \, 3)(2 \, 4 \, 5)(6)(7)\text{,}\) alors \(n = 4\text{.}\) Tout \(f \in \widetilde{X}_g\) doit avoir la même valeur sur chaque cycle de \(g\text{.}\) Il y a \(|Y|=3\) choix possibles pour chaque valeur, donc \(|\widetilde{X}_g| = 3^4 = 81\text{.}\)
Exemple 14.3.7.
Supposons que nous souhaitons colorier les sommets d’un carré en utilisant quatre couleurs différentes. Par Proposition 14.3.5, nous pouvons immédiatement conclure qu’il y a
\begin{equation*}
\frac{1}{8} (4^4 + 4^1 + 4^2 + 4^1 + 4^2 + 4^ 2 + 4^3 + 4^3) = 55
\end{equation*}
façons possibles.
Sous-section 14.3.2 Fonctions de commutation
En théorie des commutateurs, nous nous intéressons à la conception de circuits électroniques à entrées et sorties binaires. Le plus simple de ces circuits est une fonction de commutation qui possède \(n\) entrées et une seule sortie (Figure 14.3.8). Les grands circuits électroniques peuvent souvent être construits en combinant des modules plus petits de ce type. Le problème inhérent est que même pour un circuit simple, un grand nombre de fonctions de commutation différentes peuvent être construites. Avec seulement quatre entrées et une seule sortie, nous pouvons construire 65 536 fonctions de commutation différentes. Cependant, nous pouvons souvent remplacer une fonction de commutation par une autre simplement en permutant les fils d’entrée du circuit (Figure 14.3.9).
Nous définissons une fonction de commutation ou fonction booléenne à \(n\) variables comme une application de \({\mathbb Z}_2^n\) vers \({\mathbb Z}_2\text{.}\) Puisque toute fonction de commutation peut prendre deux valeurs possibles pour chaque \(n\)-uplet binaire et qu’il y a \(2^n\) \(n\)-uplets binaires, \(2^{2^n}\) fonctions de commutation sont possibles pour \(n\) variables. En général, autoriser des permutations des entrées réduit considérablement le nombre de types de modules différents nécessaires à la construction d’un grand circuit.
Les fonctions de commutation possibles à deux variables d’entrée \(a\) et \(b\) sont listées dans Table 14.3.10. Deux fonctions de commutation \(f\) et \(g\) sont équivalentes si \(g\) peut être obtenue à partir de \(f\) par une permutation des variables d’entrée. Par exemple, \(g(a, b, c) = f(b, c, a)\text{.}\) Dans ce cas \(g \sim f\) via la permutation \((a,c,b)\text{.}\) Dans le cas des fonctions de commutation à deux variables, la permutation \((a,b)\) réduit les 16 fonctions de commutation possibles à 12 fonctions équivalentes puisque
\begin{align*}
f_2 & \sim f_4\\
f_3 & \sim f_5\\
f_{10} & \sim f_{12}\\
f_{11} & \sim f_{13}\text{.}
\end{align*}
| Entrées | Sorties | ||||||||
| \(f_0\) | \(f_1\) | \(f_2\) | \(f_3\) | \(f_4\) | \(f_5\) | \(f_6\) | \(f_7\) | ||
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) |
| Entrées | Sorties | ||||||||
| \(f_8\) | \(f_9\) | \(f_{10}\) | \(f_{11}\) | \(f_{12}\) | \(f_{13}\) | \(f_{14}\) | \(f_{15}\) | ||
| \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(0\) | \(1\) |
Pour trois variables d’entrée, il y a \(2^{2^3} = 256\) fonctions de commutation possibles ; dans le cas de quatre variables, il y en a \(2^{2^4} =65{,}536\text{.}\) Le nombre de classes d’équivalence est trop grand pour être calculé directement de manière raisonnable. Il est nécessaire d’utiliser le théorème de Burnside.
Considérons une fonction de commutation à trois entrées possibles, \(a\text{,}\) \(b\) et \(c\text{.}\) Comme nous l’avons mentionné, deux fonctions de commutation \(f\) et \(g\) sont équivalentes si une permutation des variables d’entrée de \(f\) donne \(g\text{.}\) Il est important de remarquer qu’une permutation des fonctions de commutation n’est pas simplement une permutation des valeurs d’entrée \(\{a, b, c\}\text{.}\) Une fonction de commutation est un ensemble de valeurs de sortie pour les entrées \(a\text{,}\) \(b\) et \(c\text{,}\) de sorte que lorsque nous considérons des fonctions de commutation équivalentes, nous permutons \(2^3\) sorties possibles, et non simplement trois valeurs d’entrée. Par exemple, chaque triplet binaire \((a, b, c)\) a une sortie spécifique associée. La permutation \((acb)\) modifie les sorties comme suit :
\begin{align*}
(0, 0, 0) & \mapsto (0, 0, 0)\\
(0, 0, 1) & \mapsto (0, 1, 0)\\
(0, 1, 0) & \mapsto (1, 0, 0)\\
& \vdots\\
(1, 1, 0) & \mapsto (1, 0, 1)\\
(1, 1, 1) & \mapsto (1, 1, 1)\text{.}
\end{align*}
Soit \(X\) l’ensemble des valeurs de sortie d’une fonction de commutation à \(n\) variables. Alors \(|X|=2^n\text{.}\) Nous pouvons énumérer ces valeurs comme suit :
\begin{align*}
(0, \ldots, 0, 1) & \mapsto 0\\
(0, \ldots, 1, 0) & \mapsto 1\\
(0, \ldots, 1, 1) & \mapsto 2\\
& \vdots\\
(1, \ldots, 1, 1) & \mapsto 2^n-1\text{.}
\end{align*}
Considérons maintenant un circuit à quatre variables d’entrée et une seule sortie. Supposons que nous puissions permuter les fils de n’importe quel circuit selon le groupe de permutations suivant :
\begin{gather*}
(a), \quad (a,c), \quad (b,d), \quad (a,d,c,b),\\
(a,b,c,d), \quad (a,b)(c,d), \quad (a,d)(b,c), \quad (a,c)(b,d)\text{.}
\end{gather*}
Les permutations des quatre variables d’entrée possibles induisent les permutations des valeurs de sortie dans Table 14.3.11.
Donc, il y a
\begin{equation*}
\frac{1}{8} (2^{16} + 2 \cdot 2^{12} + 2 \cdot 2^6 + 3 \cdot 2^{10}) = 9616
\end{equation*}
fonctions de commutation possibles à quatre variables sous ce groupe de permutations. Ce nombre sera encore plus petit si nous considérons le groupe symétrique complet sur quatre lettres.
| Permutation | Nombre | |
| du groupe | Permutation de la fonction de commutation | de cycles |
| \((a)\) | \((0)\) | 16 |
| \((a, c)\) | \((2,8)(3,9)(6,12)(7,13)\) | 12 |
| \((b, d)\) | \((1,4)(3,6)(9,12)(11,14)\) | 12 |
| \((a, d, c, b)\) | \((1,2,4,8)(3,6.12,9)(5,10)(7,14,13,11)\) | 6 |
| \((a, b, c, d)\) | \((1,8,4,2)(3,9,12,6)(5,10)(7,11,13,14)\) | 6 |
| \((a, b)(c, d)\) | \((1,2)(4,8)(5,10)(6,9)(7,11)(13,14)\) | 10 |
| \((a, d)(b, c)\) | \((1,8)(2,4)(3,12)(5,10)(7,14)(11,13)\) | 10 |
| \((a, c)(b, d)\) | \((1,4)(2,8)(3,12)(6,9)(7,13)(11,14)\) | 10 |
Sous-section 14.3.3 Note historique
William Burnside est né à Londres en 1852. Il fréquenta l’université de Cambridge de 1871 à 1875 et remporta le prix Smith lors de sa dernière année. Après sa remise de diplôme, il enseigna à Cambridge. Il fut élu membre de la Royal Society en 1893. Burnside a écrit environ 150 articles sur des sujets de mathématiques appliquées, de géométrie différentielle et de probabilités, mais ses contributions les plus célèbres concernent la théorie des groupes. Plusieurs conjectures de Burnside ont stimulé la recherche jusqu’à nos jours. L’une d’elles était que tout groupe d’ordre impair est résoluble ; c’est-à-dire que pour un groupe \(G\) d’ordre impair, il existe une suite de sous-groupes
\begin{equation*}
G = H_n \supset H_{n-1} \supset \cdots \supset H_1 \supset H_0 = \{ e \}
\end{equation*}
telle que \(H_i\) est normal dans \(H_{i+1}\) et \(H_{i+1} / H_i\) est abélien. Cette conjecture fut finalement démontrée par W. Feit et J. Thompson en 1963. L’ouvrage de Burnside The Theory of Groups of Finite Order, publié en 1897, fut l’un des premiers livres à traiter les groupes dans un contexte moderne par opposition aux groupes de permutations. La deuxième édition, publiée en 1911, est toujours un classique.
