Burnside William

Imaginez quatre sommets d'un carré auxquels on attribue chacun une couleur. Deux coloriages qui se déduisent par une rotation du carré représentent le même motif. Le lemme de Burnside compte alors les motifs différents en observant, pour chaque rotation, combien de coloriages restent exactement en place. Il additionne ces nombres de coloriages fixes, puis divise par le nombre de rotations considérées. Cette idée transforme un comptage brouillé par les symétries en une moyenne vérifiable.

Le lemme de Burnside s'applique à l'action d'un groupe fini G sur un ensemble fini X. Une action décrit comment chaque élément de G transforme les éléments de X, en respectant l'identité et la composition des transformations. Deux éléments de X appartiennent à la même orbite lorsqu'une transformation du groupe permet de passer de l'un à l'autre.

Pour chaque transformation g de G, on note Fix(g) l'ensemble des éléments de X laissés inchangés par g. Le nombre d'orbites est alors la moyenne des nombres d'éléments fixes :

Les transformations doivent être celles qui définissent l'équivalence recherchée : les rotations seules ne donnent pas le même résultat que les rotations et les réflexions. Le lemme compte des orbites, et non des éléments bruts de X ; sans symétrie à quotienter, chaque élément forme simplement sa propre orbite.

On colorie en noir ou en blanc les quatre sommets d'un carré. On considère seulement ses quatre rotations : l'identité, un quart de tour, un demi-tour et trois quarts de tour. Deux coloriages sont identifiés lorsqu'une de ces rotations transforme l'un en l'autre.

Les données sont les suivantes : quatre sommets ; deux couleurs pour chaque sommet ; quatre rotations ; les nombres de coloriages fixes 16, 2, 4 et 2 dans cet ordre.

L'identité laisse chaque coloriage en place : 2⁴ = 16.
Un quart de tour impose une couleur commune aux quatre sommets : 2 coloriages restent fixes.
Un demi-tour impose seulement l'égalité entre les deux paires de sommets opposés : 2² = 4 coloriages restent fixes.
Un trois-quarts de tour a le même nombre fixe qu'un quart de tour : 2 coloriages.

La moyenne vaut (16 + 2 + 4 + 2) / 4 = 6. Il existe donc exactement six motifs de coloriage différents sous les rotations du carré. Le contrôle consiste à vérifier que la somme des nombres fixes vaut 24, puis que 24 divisé par les quatre rotations donne bien 6.

En combinatoire, le lemme sert à compter des configurations considérées comme identiques après une rotation ou une autre symétrie. Le geste consiste à dresser la liste des transformations autorisées et à compter séparément les configurations fixes de chacune.

Pour des motifs sur un objet qui peut aussi être retourné, il faut inclure les réflexions dans le groupe. Cette alternative est préférable lorsque le retournement ne change effectivement pas le motif recherché ; sinon, les rotations seules constituent le bon référentiel.

En théorie des groupes finis, le lemme relie une question globale sur les orbites à des comptages locaux de points fixes. Il donne ainsi une méthode de vérification lorsque les transformations et l'ensemble de départ sont finis et explicitement connus.

Le lemme de Burnside ne se confond pas avec le théorème de Burnside sur les groupes finis. Le critère qui tranche est l'objet du résultat : le lemme calcule un nombre d'orbites à partir de points fixes, tandis qu'un théorème sur la structure d'un groupe répond à une autre question. Dans un problème de coloriages, la présence de transformations et de configurations fixes signale le lemme.

Il ne se confond pas non plus avec un simple comptage de configurations. Si aucune transformation ne rend deux configurations équivalentes, il n'y a pas de quotient par symétrie à effectuer : compter directement les éléments de X suffit.

Le résultat exige un groupe et un ensemble finis. Si l'ensemble de configurations ou le groupe de transformations est infini, la moyenne finie des nombres de points fixes n'est plus directement disponible ; il faut un autre cadre de comptage.

Le piège le plus visible est de choisir le mauvais groupe. Pour le carré de l'exemple, quatre rotations donnent 6 motifs, tandis que l'ajout des quatre réflexions modifierait le nombre recherché. Le symptôme est un résultat qui identifie des motifs que l'énoncé ne déclarait pas équivalents ; il faut alors retirer ces transformations ou reformuler l'équivalence.

Chaque transformation doit agir sur le même ensemble X et compter les éléments exactement fixes, pas ceux qui reviennent à leur position après plusieurs transformations. Dans l'exemple, un quart de tour fixe 2 coloriages, alors qu'un demi-tour en fixe 4 : confondre ces deux contraintes fausse la moyenne.

L'article Faciliter les dénombrements d’objets montre comment les symétries peuvent alléger le dénombrement de configurations. Il permet de replacer le calcul des orbites dans une démarche plus large de comptage d'objets.