Théorème de Burnside (lemme de Burnside) : démonstration (preuve)

Théorème de Burnside (Lemme de Burnside)
Contexte : Action de Groupe

Pour comprendre ce théorème, il faut se placer dans le cadre d’un groupe fini $G$ qui agit sur un ensemble fini $X$. Cela signifie qu’à chaque élément $g \in G$, on associe une permutation de $X$, de manière compatible avec la loi du groupe.

  • Orbite : L’orbite d’un élément $x \in X$, notée $Orb(x)$, est l’ensemble de tous les éléments de $X$ que l’on peut atteindre à partir de $x$ en appliquant les transformations du groupe $G$. Les orbites forment une partition de $X$.
  • Points Fixes : Pour un élément $g \in G$, l’ensemble des points fixes de $g$, noté $X^g$, est l’ensemble des éléments de $X$ qui sont inchangés par l’action de $g$. C’est-à-dire $X^g = \{x \in X \mid g \cdot x = x\}$.

Le but du lemme de Burnside est de compter le nombre d’orbites distinctes.

Lemme de Burnside

Soit $G$ un groupe fini agissant sur un ensemble fini $X$. Le nombre d’orbites, noté $|X/G|$, est égal à la moyenne du nombre de points fixes pour chaque élément du groupe.

Formellement : $$ |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g| $$

Démonstration Détaillée

La démonstration est un exemple classique de comptage par double dénombrement.

  1. Double Dénombrement : On considère la somme $\sum_{g \in G} |X^g|$. On peut la voir comme le comptage de tous les couples $(g, x)$ où $g \in G$, $x \in X$ et $g \cdot x = x$. On va calculer cette somme d’une autre manière. $$ \sum_{g \in G} |X^g| = \sum_{g \in G} \sum_{x \in X, g \cdot x = x} 1 $$
  2. Interversion de la Sommation : On peut intervertir l’ordre des deux sommes : $$ = \sum_{x \in X} \sum_{g \in G, g \cdot x = x} 1 $$
  3. Introduction du Stabilisateur : L’ensemble $\{g \in G \mid g \cdot x = x\}$ est précisément le stabilisateur de $x$, noté $Stab(x)$. La somme devient donc : $$ = \sum_{x \in X} |Stab(x)| $$
  4. Théorème Orbite-Stabilisateur : Un résultat fondamental de la théorie des actions de groupe est le théorème orbite-stabilisateur, qui affirme que pour tout $x \in X$, on a $|G| = |Orb(x)| \cdot |Stab(x)|$. On peut donc exprimer la taille du stabilisateur par $|Stab(x)| = \frac{|G|}{|Orb(x)|}$.
  5. Substitution : En substituant cette relation dans notre somme, on obtient : $$ \sum_{g \in G} |X^g| = \sum_{x \in X} \frac{|G|}{|Orb(x)|} $$
  6. Regroupement par Orbites : On peut regrouper les termes de la somme par orbites. Si deux éléments $x$ et $y$ sont dans la même orbite, alors $|Orb(x)| = |Orb(y)|$. Soit $\mathcal{O}$ une orbite. Tous les $x \in \mathcal{O}$ contribuent au même terme $\frac{|G|}{|\mathcal{O}|}$. Comme il y a $|\mathcal{O}|$ éléments dans cette orbite, la contribution totale de l’orbite $\mathcal{O}$ à la somme est : $$ \sum_{x \in \mathcal{O}} \frac{|G|}{|\mathcal{O}|} = |\mathcal{O}| \times \frac{|G|}{|\mathcal{O}|} = |G| $$
  7. Conclusion : Chaque orbite contribue pour une valeur de $|G|$ à la somme totale. Si l’on note $|X/G|$ le nombre d’orbites, la somme totale est donc $|X/G| \times |G|$. On a donc l’égalité : $$ \sum_{g \in G} |X^g| = |X/G| \cdot |G| $$ En divisant par $|G|$, on obtient la formule du lemme de Burnside.

Implications et Utilisation

Le lemme de Burnside est un outil de dénombrement très puissant, particulièrement utile pour compter des objets à symétrie près.

Exemple : Combien de colliers différents peut-on faire avec 4 perles, si l’on a des perles de 3 couleurs (Rouge, Vert, Bleu) ?

  • L’ensemble $X$ est l’ensemble de tous les coloriages possibles du collier « fixe », soit $3^4 = 81$ coloriages.
  • Le groupe $G$ est le groupe diédral $D_4$ des symétries du carré, qui a 8 éléments (4 rotations, 4 réflexions).
  • On calcule le nombre de coloriages laissés invariants (points fixes) par chaque symétrie :
    • Identité : Laisse les 81 coloriages invariants.
    • Rotations de $\pm 90^\circ$ (2) : Les 4 perles doivent être de la même couleur. 3 coloriages invariants pour chacune.
    • Rotation de $180^\circ$ (1) : Les perles opposées doivent avoir la même couleur. $3^2=9$ coloriages invariants.
    • Réflexions par rapport aux diagonales (2) : Les perles sur une diagonale peuvent être de n’importe quelle couleur, la 4ème perle doit être de la même couleur que la 2ème. $3^3=27$ coloriages invariants pour chacune.
    • Réflexions par rapport aux médianes (2) : Les paires de perles adjacentes doivent être de la même couleur. $3^2=9$ coloriages invariants pour chacune.
  • On applique la formule : Nombre de colliers distincts = $\frac{1}{8}(81 + 2 \times 3 + 1 \times 9 + 2 \times 27 + 2 \times 9) = \frac{1}{8}(81+6+9+54+18) = \frac{168}{8} = 21$.