théorème de Burnside

Imaginez les quatre sommets d’un carré, chacun colorié en jaune ou en rouge. Il existe 16 coloriages si le carré reste immobile. Mais certains deviennent identiques dès que l’on autorise les rotations et les réflexions du carré.

Le lemme de Burnside évite de comparer les coloriages deux à deux. Pour chaque symétrie, il compte ceux qui ne changent pas, puis fait la moyenne de ces nombres. Cette moyenne donne exactement le nombre de familles de coloriages réellement différentes.

Le nom « théorème de Burnside » recouvre plusieurs résultats de William Burnside. Le plus courant en combinatoire est le lemme de Burnside, aussi nommé théorème de Cauchy-Frobenius. Il concerne un groupe fini G qui agit sur un ensemble fini X. Deux éléments de X sont considérés comme équivalents lorsqu’une transformation de G envoie l’un sur l’autre ; chaque classe ainsi obtenue est une orbite.

Pour une transformation g du groupe, Fix(g) désigne l’ensemble des éléments de X laissés inchangés par g. Le nombre d’orbites est la moyenne des nombres de points fixes : $\mathrm{\mid }X\mathrm{/}G\mathrm{\mid }=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}{\sum }_{g\in G}\mathrm{\mid }\mathrm{Fix}(g)\mathrm{\mid }|X/G|=\backslash frac\{1\}\{|G|\}\backslash sum\_\{g\backslash in\; G\}|\backslash operatorname\{Fix\}(g)|$. Ici, |G| est le nombre de transformations du groupe et |X/G| le nombre d’orbites.

Un autre théorème de Burnside relève de la structure des groupes finis : si l’ordre d’un groupe vaut p^aq^b, avec p et q premiers et a et b entiers positifs, alors ce groupe est résoluble. Ce résultat est distinct du procédé de comptage par points fixes.

Si un groupe fini G agit sur un ensemble fini X, alors le nombre d’orbites de cette action est égal à la moyenne, sur toutes les transformations g de G, du nombre d’éléments de X fixés par g.

En notant Fix(g) l’ensemble des éléments fixés par g, l’énoncé s’écrit : $\mathrm{\mid }X\mathrm{/}G\mathrm{\mid }=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}{\sum }_{g\in G}\mathrm{\mid }\mathrm{Fix}(g)\mathrm{\mid }|X/G|=\backslash frac\{1\}\{|G|\}\backslash sum\_\{g\backslash in\; G\}|\backslash operatorname\{Fix\}(g)|$. Le quotient X/G désigne ici l’ensemble des orbites, non une division numérique.

Le comptage s’applique lorsqu’un groupe fini agit sur un ensemble fini. Il faut connaître toutes les transformations du groupe et pouvoir déterminer, pour chacune, combien d’objets restent inchangés. L’action doit aussi traduire exactement l’équivalence recherchée : pour des coloriages de carré, on choisit par exemple les huit symétries du carré, et non des permutations arbitraires des sommets.

Avec un groupe infini, additionner les nombres de points fixes puis diviser par |G| ne fournit pas cette moyenne finie. Il faut alors employer un autre cadre de comptage. De même, oublier une réflexion ou compter deux fois une rotation fausse le diviseur et la somme.

On colorie les quatre sommets d’un carré en jaune ou en rouge. Deux coloriages sont déclarés équivalents si une rotation ou une réflexion du carré transforme l’un en l’autre. Les données sont donc 2 couleurs, 4 sommets et 8 symétries.

1. L’identité fixe les 16 coloriages.
2. Les rotations d’un quart et de trois quarts de tour en fixent 2 chacune.
3. La rotation d’un demi-tour en fixe 4.
4. Chacune des deux réflexions passant par deux sommets opposés en fixe 8.
5. Chacune des deux réflexions passant entre deux paires de sommets en fixe 4.

La somme des points fixes vaut $16+2+2+4+8+8+4+4=4816+2+2+4+8+8+4+4=48$. Le lemme donne donc $48÷8=648\backslash div\; 8=6$ orbites : il existe 6 coloriages différents à symétrie près. Comme la somme 48 est divisible par l’ordre 8 du groupe, le contrôle arithmétique est cohérent.

Pour compter des coloriages à symétrie près, on décrit d’abord les rotations et réflexions admises. Le lemme devient avantageux lorsque la liste des objets est longue, mais que les points fixes de chaque symétrie sont simples à compter.

Pour contrôler un calcul, on regroupe les transformations qui imposent les mêmes contraintes. Si toutes les configurations peuvent être énumérées sans ambiguïté, une liste directe peut être plus rapide ; sinon, la moyenne des points fixes évite les doublons.

Le bon réflexe consiste à vérifier que le groupe choisi représente exactement les équivalences autorisées. Retourner un objet n’est pas permis dans tous les problèmes, même si une réflexion existe géométriquement.

Lemme de Burnside et théorème p^aq^b. Le premier compte les orbites d’une action finie grâce aux points fixes. Le second affirme la résolubilité d’un groupe fini dont l’ordre possède seulement les deux facteurs premiers indiqués. Un problème de coloriages relève du premier ; une question sur la structure d’un groupe d’ordre p^aq^b relève du second.

Point fixe et orbite. Un point fixe reste inchangé sous une transformation précise. Une orbite rassemble tous les objets que l’ensemble des transformations autorisées relie. Dans l’exemple du carré, un coloriage peut ne pas être fixé par une rotation donnée tout en appartenant à une orbite bien définie.

Action mal choisie. Si les transformations retenues ne correspondent pas à l’équivalence du problème, le résultat compte d’autres orbites. Pour le carré, autoriser les réflexions alors que seules les rotations sont permises change le groupe ; il faut reconstruire la somme avec les seules transformations admises.

Points fixes mal interprétés. Un objet doit être inchangé par la transformation considérée, pas seulement envoyé sur un objet qui lui ressemble. Il faut examiner les cycles imposés sur les positions et attribuer une même couleur à toutes les positions d’un cycle.

Cadre infini. La formule présentée exige ici 8 transformations et 16 coloriages, deux ensembles finis. Si le groupe ou l’ensemble à compter devient infini, la somme finie et sa division par |G| ne sont plus directement disponibles ; il faut changer de cadre.

La notion d’action de groupe précise comment chaque élément d’un groupe transforme un ensemble et permet de définir rigoureusement orbites, stabilisateurs et points fixes.