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$.

On pose $\rho:\mathbb{Z}/4\mathbb{Z}\to S_4,\ \bar k\mapsto(i\mapsto i+k\bmod 4)$. La rotation $r=\rho(\bar 1)$ correspond au $4$-cycle $(0\,1\,2\,3)$.

$\rho(\bar 0)=\mathrm{id}$, donc $e\cdot x=x$. Et $\rho(\bar k+\bar\ell)=\rho(\bar k)\circ\rho(\bar\ell)$ car $i+(k+\ell)=(i+k)+\ell\bmod 4$ : c'est la compatibilité $g\cdot(h\cdot x)=(gh)\cdot x$. Comme $\rho$ est un morphisme à valeurs dans $S_4$, on a bien une action.

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$.

$\mathcal O(0)=\{0,1,2,3\}$ : l'action est transitive (toute rotation amène $0$ sur un autre sommet, et on les atteint tous).

Seule $\mathrm{id}$ fixe $0$ parmi les rotations (une rotation non triviale déplace tous les sommets) : $\mathrm{Stab}(0)=\{\mathrm{id}\}$.

$\lvert\mathcal O(0)\rvert\cdot\lvert\mathrm{Stab}(0)\rvert=4\times 1=4=\lvert C_4\rvert$. ✓

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)]$).

L'application $g\,\mathrm{Stab}(x)\mapsto g\cdot x$ des classes à gauche de $\mathrm{Stab}(x)$ vers $\mathcal O(x)$ est surjective par définition de l'orbite, et la chaîne $g\cdot x=h\cdot x\iff h^{-1}g\in\mathrm{Stab}(x)\iff g\,\mathrm{Stab}(x)=h\,\mathrm{Stab}(x)$ montre qu'elle est bien définie et injective. C'est donc une bijection : $\lvert\mathcal O(x)\rvert=[G:\mathrm{Stab}(x)]$.

Par le théorème de Lagrange, $[G:\mathrm{Stab}(x)]=\dfrac{\lvert G\rvert}{\lvert\mathrm{Stab}(x)\rvert}$, d'où $\lvert\mathcal O(x)\rvert\cdot\lvert\mathrm{Stab}(x)\rvert=\lvert G\rvert$.

$\lvert D_4\rvert=8$. L'orbite d'un sommet est $\{0,1,2,3\}$ ($\lvert\mathcal O\rvert=4$) ; son stabilisateur est $\{\mathrm{id},\sigma\}$ où $\sigma$ est la réflexion d'axe la diagonale passant par ce sommet ($\lvert\mathrm{Stab}\rvert=2$). $4\times 2=8=\lvert D_4\rvert$. ✓

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 ?

$e\cdot x=ex=x$ et $g\cdot(h\cdot x)=g(hx)=(gh)x=(gh)\cdot x$ : c'est une action (translation à gauche).

Transitive : pour $x,y\in G$, l'élément $g=yx^{-1}$ vérifie $g\cdot x=y$. Libre : $g\cdot x=x\Rightarrow gx=x\Rightarrow g=e$ (donc tous les stabilisateurs sont triviaux).

Le morphisme $\rho:G\to\operatorname{Sym}(G)\cong S_n$ associé a pour noyau $\{g:gx=x\ \forall x\}=\{e\}$ : $\rho$ est injectif, donc $G$ se plonge dans $S_n$. (Exemple : $\mathbb{Z}/6\mathbb{Z}\hookrightarrow S_6$.)

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.

$exe^{-1}=x$ et $g\cdot(h\cdot x)=g(hxh^{-1})g^{-1}=(gh)x(gh)^{-1}=(gh)\cdot x$ : action (par conjugaison).

L'orbite de $x$ est $\{gxg^{-1}:g\in G\}$ : sa classe de conjugaison. Le stabilisateur est $\{g:gxg^{-1}=x\}=\{g:gx=xg\}=C_G(x)$, le centralisateur.

$\{e\}$ (taille $1$), les $3$ transpositions $\{(1\,2),(1\,3),(2\,3)\}$ (taille $3$), les $2$ tricycles $\{(1\,2\,3),(1\,3\,2)\}$ (taille $2$) : $3$ classes, de tailles $1,3,2$.

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\}$.

Réflexive : $x=e\cdot x$. Symétrique : si $y=g\cdot x$, alors $x=g^{-1}\cdot y$. Transitive : si $y=g\cdot x$ et $z=h\cdot y$, alors $z=(hg)\cdot x$. La classe de $x$ est $\{g\cdot x\}=\mathcal O(x)$.

Les classes d'une relation d'équivalence sont disjointes et de réunion $X$ : les orbites partitionnent $X$.

$\mathrm{Fix}(\mathrm{id})=X$ tout entier. Une rotation non triviale d'un collier déplace toutes les positions, donc $\mathrm{Fix}=\varnothing$ : aucun point fixe.

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.

Soit $S=\{(g,x):g\cdot x=x\}$. En sommant sur $g$ : $\lvert S\rvert=\sum_{g\in G}\lvert\mathrm{Fix}(g)\rvert$. En sommant sur $x$ : $\lvert S\rvert=\sum_{x\in X}\lvert\mathrm{Stab}(x)\rvert$.

Par orbite-stabilisateur, $\lvert\mathrm{Stab}(x)\rvert=\dfrac{\lvert G\rvert}{\lvert\mathcal O(x)\rvert}$. Sur une orbite $\mathcal O$ fixée, $\sum_{x\in\mathcal O}\dfrac{\lvert G\rvert}{\lvert\mathcal O\rvert}=\lvert G\rvert$. Il y a $N$ orbites, donc $\sum_x\lvert\mathrm{Stab}(x)\rvert=\lvert G\rvert\cdot N$.

En égalant : $\sum_{g}\lvert\mathrm{Fix}(g)\rvert=\lvert G\rvert\cdot N$, d'où $N=\dfrac{1}{\lvert G\rvert}\sum_{g}\lvert\mathrm{Fix}(g)\rvert$.

$\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.

$\mathrm{id}$ : $4$ cycles $\Rightarrow 2^4=16$. $r=(0\,1\,2\,3)$ : $1$ cycle $\Rightarrow 2^1=2$. $r^2=(0\,2)(1\,3)$ : $2$ cycles $\Rightarrow 2^2=4$. $r^3$ : $1$ cycle $\Rightarrow 2$.

$N=\dfrac{16+2+4+2}{4}=\dfrac{24}{4}=6$.

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 rotation $r^k$ envoie la position $i$ sur $i+k\bmod n$ ; ses cycles ont tous pour longueur $\dfrac{n}{\gcd(k,n)}$ et il y en a $\gcd(k,n)$. Donc $\lvert\mathrm{Fix}(r^k)\rvert=q^{\gcd(k,n)}$.

$N=\dfrac1n\sum_{k=0}^{n-1}q^{\gcd(k,n)}$. Pour $d\mid n$, le nombre de $k\in\{0,\dots,n-1\}$ avec $\gcd(k,n)=d$ est $\varphi(n/d)$ (les $k=d\,j$ avec $\gcd(j,n/d)=1$), d'où la seconde forme.

$\gcd(k,6)$ pour $k=0,\dots,5$ vaut $6,1,2,3,2,1$, donc $\sum q^{\gcd}=2^6+2+2^2+2^3+2^2+2=64+2+4+8+4+2=84$ et $N=84/6=14$. (Rappel : $C_6\cong\mathbb U_6$, les racines $6$-ièmes de l'unité.)

Réutiliser les $4$ rotations (cf. B2).

Une réflexion d'axe une diagonale fixe $2$ sommets et échange les $2$ autres.

Une réflexion d'axe les milieux d'arêtes échange les sommets deux à deux.

Comme en B2 : $16+2+4+2=24$.

$2$ axes par sommets opposés : $2$ points fixes $+$ $1$ transposition $=3$ cycles $\Rightarrow 2^3=8$ chacun. $2$ axes par milieux d'arêtes : $2$ transpositions $=2$ cycles $\Rightarrow 2^2=4$ chacun. Total réflexions : $8+8+4+4=24$.

$N=\dfrac{24+24}{8}=\dfrac{48}{8}=6$.

$D_3$ a $1$ identité, $2$ rotations, $3$ réflexions.

Une rotation non triviale est un $3$-cycle ; une réflexion fixe un sommet.

$\lvert\mathrm{Fix}(g)\rvert=q^{c(g)}$.

$\mathrm{id}$ : $3$ cycles $\Rightarrow q^3$. Les $2$ rotations ($3$-cycles) : $1$ cycle $\Rightarrow q$ chacune. Les $3$ réflexions ($1$ point fixe $+$ $1$ transposition) : $2$ cycles $\Rightarrow q^2$ chacune.

$N=\dfrac{q^3+2q+3q^2}{6}$. Pour $q=2$ : $\dfrac{8+4+12}{6}=\dfrac{24}{6}=4$. Pour $q=3$ : $\dfrac{27+6+27}{6}=10$.

Classer les rotations par axe : faces, sommets opposés, milieux d'arêtes opposées.

Pour chaque type, compter les cycles induits sur les $6$ faces.

$\lvert\mathrm{Fix}(g)\rvert=2^{c(g)}$, puis Burnside.

$1$ identité ($6$ cycles). $6$ rotations $\pm90^\circ$ d'axe une paire de faces ($3$ axes $\times2$) : $2$ faces fixes $+$ un $4$-cycle $=3$ cycles. $3$ rotations $180^\circ$ d'axe de faces : $2$ fixes $+$ deux $2$-cycles $=4$ cycles. $8$ rotations $\pm120^\circ$ d'axe deux sommets opposés ($4$ axes $\times2$) : deux $3$-cycles $=2$ cycles. $6$ rotations $180^\circ$ d'axe deux milieux d'arêtes : trois $2$-cycles $=3$ cycles.

$1\cdot 2^6 + 6\cdot 2^3 + 3\cdot 2^4 + 8\cdot 2^2 + 6\cdot 2^3 = 64+48+48+32+48=240$.

$N=\dfrac{240}{24}=10$.

Reprendre B2 (rotations) et B4 (diédral).

Ajouter des symétries ne peut que fusionner des orbites.

Comparer pour $n=4$ puis renvoyer au cas $n=6$ (E3).

Sous $C_4$ : $N_{C_4}=6$ (B2). Sous $D_4$ : $N_{D_4}=6$ (B4).

En général $N_{D_n}\leq N_{C_n}$ : un groupe plus gros identifie davantage de coloriages. Ici, pour $n=4$ et $2$ couleurs, les réflexions n'identifient rien de nouveau, d'où l'égalité $6=6$. Ce n'est plus vrai pour $n=6$ : on trouvera $14$ colliers contre $13$ bracelets (cf. E3).

Réutiliser la distribution des cycles de B6.

$N=\dfrac1{24}\sum_g q^{c(g)}$.

Regrouper par nombre de cycles : $\{6,4,3,2\}$ avec multiplicités $\{1,3,12,8\}$.

De B6 : $1$ élément à $6$ cycles, $3$ à $4$ cycles, $12$ à $3$ cycles ($6$ rotations $\pm90^\circ$ $+$ $6$ rotations d'arêtes), $8$ à $2$ cycles. Donc

$q=1:1$ ; $q=2:\dfrac{64+48+96+32}{24}=10$ ; $q=3:57$ ; $q=4:240$.

Les $6$ rotations donnent la même somme qu'en B3.

Pour $n=6$ (pair) : $3$ réflexions par sommets opposés, $3$ par milieux d'arêtes.

Pour $n=5$ (impair) : chaque réflexion passe par un sommet et le milieu de l'arête opposée.

Somme des $\lvert\mathrm{Fix}\rvert$ sur $C_6$ : $84$ (B3).

$3$ axes par sommets opposés : $2$ fixes $+$ deux $2$-cycles $=4$ cycles $\Rightarrow 2^4=16$ chacun. $3$ axes par milieux d'arêtes : trois $2$-cycles $=3$ cycles $\Rightarrow 2^3=8$ chacun. Total : $3\cdot16+3\cdot8=72$.

$N=\dfrac{84+72}{12}=\dfrac{156}{12}=13$, contre $14$ colliers : le retournement fusionne une paire chirale.

Collier $C_5$ : $\dfrac{2^5+4\cdot2}{5}=\dfrac{40}{5}=8$. Bracelet $D_5$ : les $5$ réflexions ($1$ fixe $+$ deux $2$-cycles, $2^3=8$) donnent $\dfrac{40+5\cdot8}{10}=8$. Égalité car les $8$ colliers de longueur $5$ sont tous achiraux (identiques à leur miroir) : le retournement n'identifie rien de neuf.

Mêmes cycles qu'en B2 (un $4$-cycle, etc.).

$\lvert\mathrm{Fix}(g)\rvert=3^{c(g)}$.

Appliquer Burnside avec $q=3$.

$\mathrm{id}:3^4=81$ ; $r:3^1=3$ ; $r^2:3^2=9$ ; $r^3:3$.

$N=\dfrac{81+3+9+3}{4}=\dfrac{96}{4}=24$.

Réutiliser la formule des colliers de B3 avec $q=3$.

$n=4$ : $\gcd(k,4)$ pour $k=0,1,2,3$.

$n=6$ : $\gcd(k,6)$ pour $k=0,\dots,5$.

$\dfrac{3^4+3+3^2+3}{4}=\dfrac{81+3+9+3}{4}=\dfrac{96}{4}=24$.

$\dfrac{3^6+3+3^2+3^3+3^2+3}{6}=\dfrac{729+3+9+27+9+3}{6}=\dfrac{780}{6}=130$.

On colorie avec $6$ couleurs toutes distinctes (coloration injective).

Une rotation $\neq\mathrm{id}$ peut-elle fixer une coloration où toutes les faces diffèrent ?

En déduire la taille des orbites, puis le compte.

Il y a $6!=720$ attributions. Une rotation $g\neq\mathrm{id}$ déplace au moins deux faces ; pour qu'elle fixe une coloration, ces faces devraient porter la même couleur — impossible si toutes sont distinctes. Donc seule $\mathrm{id}$ fixe une coloration injective : l'action est libre dessus.

Toutes les orbites ont donc la taille $\lvert G\rvert=24$ : $N=\dfrac{6!}{24}=\dfrac{720}{24}=30$. (Par Burnside : seule $\mathrm{id}$ contribue, $720/24=30$.)