Exercices corrigés — Dénombrement de Burnside

Numéroter les sommets $0,1,2,3$ dans le sens direct ; $r$ envoie $i\mapsto i+1\bmod 4$.

Vérifier les deux axiomes : $e\cdot x=x$ et $g\cdot(h\cdot x)=(gh)\cdot x$.

Une action $=$ un morphisme $\mathbb{Z}/4\mathbb{Z}\to S_4$.

Une action de $G$ sur $X$ est une application $G\times X\to X$ vérifiant deux axiomes, et deux seulement :

Rien d'autre. Ni bijectivité, ni continuité — elles se déduisent, comme on le voit à l'étape 3.

Ici $G=\mathbb{Z}/4\mathbb{Z}$ agit sur $X=\{0,1,2,3\}$, les sommets du carré numérotés dans le sens direct, et $\bar k$ agit par la rotation de $k$ quarts de tour :

L'identité ne bouge aucun sommet — c'est la rotation d'angle nul.

Tourner de $l$ puis de $k$, c'est tourner de $k+l$ — et l'addition dans $\mathbb{Z}/4\mathbb{Z}$ est exactement ce dont on a besoin.

⚠️ Le calcul se fait modulo $4$ des deux côtés, ce qui est cohérent : quatre quarts de tour ramènent à la position de départ.

Chaque élément de $G$ donne une PERMUTATION de $X$ — c'est une conséquence des axiomes, pas une hypothèse :

car $\sigma_{g^{-1}}\circ\sigma_g=\sigma_{g^{-1}g}=\sigma_e=\mathrm{id}$.

Vérification sur $\bar 2$ : $0\mapsto 2$, $1\mapsto 3$, $2\mapsto 0$, $3\mapsto 1$ — la rotation d'un demi-tour échange les sommets opposés ✓

C'est la définition équivalente, et c'est elle qui rend les actions calculables : ici $\mathbb{Z}/4\mathbb{Z}\to S_4$, d'image le sous-groupe cyclique engendré par $(0\,1\,2\,3)$.

La colonne « nombre de cycles » est déjà l'outil du lot B : le lemme de Burnside comptera les points fixes, et le nombre de cycles donnera $\lvert\mathrm{Fix}\rvert=q^{c}$ pour un coloriage à $q$ couleurs.

👉 Moyenne : $(16+2+4+2)/4=6$ — c'est déjà la réponse de l'exercice B2, six colliers distincts. Tout le lot B n'est que l'exploitation de ce tableau.

L'orbite : appliquer les $4$ rotations à $0$.

Le stabilisateur : quelles rotations fixent $0$ ?

Vérifier $\lvert\mathcal O(0)\rvert\cdot\lvert\mathrm{Stab}(0)\rvert=\lvert C_4\rvert$.

$C_4$ agit sur les $4$ sommets du carré par rotation.

L'action est donc TRANSITIVE (une seule orbite) et LIBRE (stabilisateurs triviaux) — c'est le cas le plus simple possible, et il vaut d'être vu avant les autres.

Une rotation bien choisie amène le sommet $0$ sur n'importe quel autre — géométriquement évident, et c'est ce qu'on appelle la transitivité.

Seule la rotation nulle laisse un sommet en place : toute autre rotation déplace tous les sommets.

👉 C'est un SOUS-GROUPE, toujours — il contient $e$, et il est stable par produit et inverse. C'est ce qui rend le théorème de l'exercice A3 possible.

Ce contrôle doit devenir un réflexe : dès qu'on calcule une orbite ou un stabilisateur, le produit doit rendre $\lvert G\rvert$. Une erreur de calcul se voit immédiatement.

Et il vaut pour TOUT sommet : par symétrie, $\mathcal O(i)=X$ et $\mathrm{Stab}(i)=\{\mathrm{id}\}$ pour chaque $i$.

Le groupe diédral $D_4$ (rotations et réflexions, $\lvert D_4\rvert=8$) agit sur les mêmes $4$ sommets :

L'orbite ne change PAS — elle est déjà tout $X$, elle ne peut pas grandir. C'est le STABILISATEUR qui double : la réflexion d'axe passant par $0$ et $2$ fixe le sommet $0$.

👉 Un groupe plus gros agissant sur le même ensemble a des stabilisateurs plus gros, l'orbite étant bornée par $\lvert X\rvert$. C'est exactement ce que dit le théorème orbite-stabilisateur, lu comme une contrainte.

Construire une application des classes à gauche $g\,\mathrm{Stab}(x)$ vers l'orbite.

$g\cdot x=h\cdot x\iff h^{-1}g\in\mathrm{Stab}(x)$.

Conclure par Lagrange ($\lvert\mathcal O(x)\rvert=[G:\mathrm{Stab}(x)]$).

Ce qu'il apporte : il relie une donnée géométrique (combien de positions le point peut-il occuper ?) à une donnée algébrique (combien d'éléments le laissent en place ?), et il en fait des diviseurs de $\lvert G\rvert$.

👉 C'est cette divisibilité qui fait tout le lot C — équation des classes, centre d'un $p$-groupe, Cauchy, Sylow. Tous en découlent.

L'idée : deux éléments amènent $x$ au même endroit exactement quand ils diffèrent d'un élément du stabilisateur.

La première équivalence s'obtient en appliquant $h^{-1}$ aux deux membres, ce qui est licite puisque $\sigma_{h}$ est bijective (exercice A1).

On définit donc

Bien définie ET injective — c'est la même chaîne d'équivalences, lue dans les deux sens. Surjective par définition de l'orbite.

la dernière égalité étant le théorème de Lagrange, applicable car $\mathrm{Stab}(x)$ est un sous-groupe de $G$.

⚠️ $G/\mathrm{Stab}(x)$ est un ensemble de CLASSES, pas un groupe — le stabilisateur n'est pas normal en général. Cela ne gêne pas : on n'a besoin que du cardinal.

$D_4$ (ordre $8$) agit sur les $4$ sommets du carré.

Le stabilisateur du sommet $0$ contient l'identité et la réflexion d'axe la diagonale $0$–$2$, qui échange $1$ et $3$ :

Et sur les ARÊTES, même groupe, autre action :

👉 Le même groupe, deux actions, deux stabilisateurs différents — mais toujours le même produit. C'est ce qui rend le théorème utile comme contrôle.

Application typique : un groupe d'ordre $12$ ne peut pas agir transitivement sur un ensemble à $5$ éléments, car $5\nmid 12$.

👉 Et appliqué à la conjugaison (exercice A5), il donne que la taille d'une classe de conjugaison divise $\lvert G\rvert$ — d'où l'équation des classes, et toute la suite du lot C.

Vérifier les axiomes de l'action.

Libre : $g\cdot x=x$ entraîne $g=e$. Transitive : passer de $x$ à $y$.

Le morphisme associé $G\to S_n$ a quel noyau ?

Tout groupe fini est un groupe de permutations. C'est un énoncé remarquable : il dit que l'abstraction « groupe » n'ajoute rien à la notion concrète de permutation.

Le second axiome est exactement l'ASSOCIATIVITÉ du groupe — rien de plus. C'est ce qui rend cette action « gratuite » : elle existe pour tout groupe, sans hypothèse.

TRANSITIVE : pour $x,y\in G$, l'élément $g=yx^{-1}$ vérifie

LIBRE : si $g\cdot x=x$, alors $gx=x$, donc en multipliant à droite par $x^{-1}$ :

Contrôle par le théorème orbite-stabilisateur :

👉 L'existence de $x^{-1}$ est employée DEUX fois — c'est elle qui distingue un groupe d'un monoïde, et le théorème serait faux sans elle.

Une action, c'est un morphisme vers le groupe symétrique (exercice A1) :

Son noyau est trivial, précisément parce que l'action est libre :

Donc $\varphi$ est INJECTIF, et en identifiant $G$ à $\{1,\dots,n\}$ :

👉 « Libre » est exactement ce qui donne l'injectivité. Sans elle, on aurait un morphisme mais pas un plongement.

Exemple : $\mathbb{Z}/3\mathbb{Z}\hookrightarrow S_3$, l'image étant $A_3=\{\mathrm{id},(1\,2\,3),(1\,3\,2)\}$.

⚠️ Le plongement est très peu ÉCONOMIQUE : $D_4$ se plonge en réalité dans $S_4$ (il agit fidèlement sur les $4$ sommets du carré), bien mieux que dans $S_8$.

👉 Trouver le plus petit $n$ tel que $G\hookrightarrow S_n$ est un problème difficile, sans réponse générale. La force de Cayley est ailleurs : il vaut pour tout groupe, sans aucune hypothèse — et il transforme un énoncé sur les groupes abstraits en un énoncé sur les permutations, donc calculable.

Vérifier $e\cdot x=x$ et $g\cdot(h\cdot x)=(gh)\cdot x$.

$\mathrm{Stab}(x)=\{g:gxg^{-1}=x\}=\{g:gx=xg\}$.

Dans $S_3$ : regrouper par type cyclique.

C'est l'action qui fait tout le lot C. Le théorème orbite-stabilisateur y devient l'équation des classes, d'où le centre d'un $p$-groupe, Cauchy et Sylow.

Le point technique est $(gh)^{-1}=h^{-1}g^{-1}$ — l'inversion renverse l'ordre, et c'est exactement ce qu'il faut pour que les deux $g^{-1}$ et $h^{-1}$ se regroupent correctement.

👉 Sans le renversement, l'axiome tomberait. C'est la raison pour laquelle on écrit $gxg^{-1}$ et non $g^{-1}xg$ — ou plutôt, les deux marchent, mais donnent deux actions différentes (à gauche et à droite).

C'est la définition même d'une classe de conjugaison : l'ensemble des conjugués de $x$.

Le CENTRALISATEUR : les éléments qui commutent avec $x$.

Et les points fixes de l'action tout entière :

👉 Une classe est un singleton exactement quand son élément est central. C'est ce qui sépare le centre du reste dans l'équation des classes (exercice C2).

La conjugaison PRÉSERVE le type cyclique (exercice C6) : conjuguer une transposition donne une transposition.

Trois contrôles :

Vérification du centralisateur d'une transposition : $C_{S_3}\big((1\,2)\big)=\{\mathrm{id},(1\,2)\}$, d'ordre $2$ ✓

Une seule action, quatre théorèmes. C'est le meilleur exemple de ce que le point de vue « action » apporte : des énoncés qui semblaient demander des astuces deviennent des applications d'un même principe.

👉 Et le lemme de Burnside (lot B) est l'autre exploitation du même socle — cette fois pour compter des orbites plutôt que pour les décrire.

Réflexivité via $e$, symétrie via $g^{-1}$, transitivité via la composition.

La classe de $x$ pour $\sim$ est exactement $\mathcal O(x)$.

$\mathrm{Fix}(\mathrm{id})=\{x:\mathrm{id}\cdot x=x\}$.

La partition est ce qui rend le comptage possible : le lemme de Burnside compte les orbites, ce qui n'aurait aucun sens si elles pouvaient se chevaucher.

RÉFLEXIVE : $x=e\cdot x$, donc $x\sim x$ — c'est le premier axiome d'une action.

SYMÉTRIQUE : si $y=g\cdot x$, appliquons $g^{-1}$ :

donc $y\sim x$ — c'est l'existence de l'inverse.

TRANSITIVE : si $y=g\cdot x$ et $z=h\cdot y$, alors

donc $x\sim z$ — c'est le second axiome, plus la stabilité par produit.

👉 Chaque propriété correspond à un axiome de groupe : neutre, inverse, produit. Ce n'est pas un hasard, et cela montre que la structure de groupe est exactement ce qu'il faut.

Par définition même de la relation.

Et les classes d'une relation d'équivalence forment une PARTITION :

Deux orbites sont donc égales ou disjointes — jamais partiellement superposées. C'est ce qu'on utilise sans y penser, et c'est ce qui fonde le comptage.

Pour $g=e$, le premier axiome donne $e\cdot x=x$ pour tout $x$ :

👉 C'est le terme DOMINANT du lemme de Burnside, et il faut savoir le reconnaître :

Contrôle systématique : dans toute somme de Burnside, le premier terme doit valoir $\lvert X\rvert$. S'il vaut autre chose, il y a une erreur.

Sur les colliers à $4$ perles bicolores : $\lvert X\rvert=2^4=16$, et c'est bien le premier terme de la somme $(16+2+4+2)/4=6$ ✓

La troisième ligne est l'exercice C2, la quatrième l'exercice B1 — et toutes deux reposent sur la partition démontrée ici.

👉 Cette formule est la « version orbite » de l'équation des classes, et elle vaut pour n'importe quelle action. L'équation des classes n'en est que le cas particulier où l'action est la conjugaison.

Compter de deux façons l'ensemble $S=\{(g,x)\in G\times X:g\cdot x=x\}$.

Par $g$ : $\sum_g\lvert\mathrm{Fix}(g)\rvert$. Par $x$ : $\sum_x\lvert\mathrm{Stab}(x)\rvert$.

Utiliser orbite-stabilisateur puis sommer par orbite.

où $N$ est le nombre d'orbites.

Ce qu'il apporte : compter des orbites est difficile — il faudrait les construire une par une, en vérifiant qu'on ne compte pas deux fois. Compter des points fixes, en revanche, se fait élément par élément, et chaque calcul est local et facile.

👉 Attribué à Burnside, mais dû à Cauchy et Frobenius — Burnside l'a rendu célèbre en le citant dans son traité, sans le revendiquer. On l'appelle parfois « le lemme qui n'est pas de Burnside ».

L'idée : compter de deux façons les couples $(g,x)$ tels que $g$ fixe $x$.

Par $g$ d'abord — pour chaque $g$, on compte les $x$ qu'il fixe :

Par $x$ d'abord — pour chaque $x$, on compte les $g$ qui le fixent :

👉 Le double comptage est le geste central, et il ne coûte rien : c'est la même somme, regroupée dans les deux sens.

Le théorème orbite-stabilisateur (exercice A3) donne

Les orbites partitionnant $X$ (exercice A6), on regroupe la somme :

Or dans une orbite $\mathcal O$, tous les termes sont ÉGAUX — chaque $x$ de $\mathcal O$ a la même orbite. La somme intérieure vaut donc

👉 Chaque orbite contribue exactement $\lvert G\rvert$ — quelle que soit sa taille. C'est le fait remarquable qui fait apparaître $N$.

En égalant les deux expressions de $S$ :

Le nombre d'orbites est la MOYENNE du nombre de points fixes.

Deux contrôles à faire systématiquement :

Une division non entière signale une erreur de comptage — c'est le garde-fou le plus rapide.

Pour compter des COLORIAGES à $q$ couleurs, $X$ est l'ensemble des coloriages et le calcul des points fixes se fait par les cycles :

où $c(g)$ est le nombre de cycles de la permutation $g$.

Pourquoi : un coloriage est fixé par $g$ si et seulement s'il est constant sur chaque cycle — les positions d'un cycle échangent leurs couleurs, donc doivent porter la même. Il y a donc $q$ choix par cycle, indépendamment.

Sur $C_4$ agissant sur $4$ perles, $q=2$ :

👉 Tout le lot B est l'application de ce tableau à des groupes de plus en plus gros.

$\lvert\mathrm{Fix}(g)\rvert=2^{c(g)}$ où $c(g)$ est le nombre de cycles de $g$.

Compter les cycles de $\mathrm{id},r,r^2,r^3$.

Appliquer le lemme de Burnside.

Sans quotienter, il y aurait $2^4=16$ coloriages. Les rotations les regroupent en six classes.

Ce n'est PAS $16/4=4$ — et c'est tout l'intérêt de l'exercice : diviser par $\lvert G\rvert$ serait juste si l'action était libre, ce qu'elle n'est pas (certains coloriages sont invariants par rotation).

$G=C_4=\{\mathrm{id},r,r^2,r^3\}$, $X=$ les $2^4=16$ coloriages des $4$ positions.

Contrôle immédiat : le terme de l'identité vaut bien $\lvert X\rvert=16$ ✓

$\mathrm{Fix}(r)=2$. Un coloriage invariant par la rotation d'un quart de tour doit avoir les $4$ perles de la même couleur — la rotation les fait toutes circuler :

$\mathrm{Fix}(r^2)=4$. La rotation d'un demi-tour identifie les perles opposées : $0\leftrightarrow 2$ et $1\leftrightarrow 3$. Il reste $2$ choix libres, soit $2^2=4$ :

$\mathrm{Fix}(r^3)=2$, par le même argument que $r$ — c'est aussi un $4$-cycle.

👉 La règle « une couleur par cycle » (exercice B1) évite tout dénombrement à la main.

Le résultat est ENTIER ✓ — premier contrôle.

Et la liste explicite des $6$ colliers — second contrôle, indépendant :

👉 La ligne « 2 noires » est la seule non triviale : deux perles noires peuvent être adjacentes ou opposées, et aucune rotation ne transforme l'une en l'autre. C'est exactement ce que l'exercice D2 retrouvera par la série génératrice.

La division simple suppose que toutes les orbites ont $\lvert G\rvert$ éléments, c'est-à-dire que l'action est libre. Ici elle ne l'est pas :

Les orbites n'ont pas toutes la même taille : $1$, $2$ ou $4$. La moyenne pondérée est donc nécessaire.

Contrôle par la partition (exercice A6) :

(orbites de $BBBB$, $NNNN$, $NBBB$, $NBNB$, $NNBB$, $NNNB$.)

La rotation $r^k$ se décompose en $\gcd(k,n)$ cycles de longueur $n/\gcd(k,n)$.

Donc $\lvert\mathrm{Fix}(r^k)\rvert=q^{\gcd(k,n)}$.

Regrouper les $k$ selon la valeur $d=\gcd(k,n)$ : il y en a $\varphi(n/d)$.

La première est directe — un terme par élément du groupe. La seconde est efficace — un terme par diviseur, donc beaucoup moins de calculs dès que $n$ grandit.