Lemme de Burnside

Le lemme de Burnside, ou lemme de Cauchy-Frobenius ou encore formule de Burnside, est un résultat de théorie des groupes souvent utile lorsqu'on doit prendre en compte les symétries lors d'un dénombrement. Il a été découvert par Augustin Louis Cauchy et Ferdinand Georg Frobenius puis est devenu célèbre après que William Burnside l'ait mentionné. Ce résultat permet de dénombrer les orbites de l'action d'un groupe sur un ensemble, autrement dit les classes d'équivalence formées par l'action de ce groupe. Par exemple, certains composés organiques sont chimiquement identiques si on effectue des rotations et le lemme permet de les dénombrer.

Formellement, soit $G$ un groupe fini opérant sur un ensemble $X$. Pour tout élément $g$ de $G$, $\operatorname {Fix} (g)$ désigne le fixateur de $g$, ensemble des éléments de $X$ fixés par $g$ (soit laissés invariants sous l'action de $g$) : $\operatorname {Fix} (g)=\{x\in X\,|\,g.x=x\}$. Le lemme de Burnside consiste en la formule suivante donnant le nombre d'orbites sous l'action de $G$, autrement dit le nombre d'éléments de l'ensemble quotient $X/G$  :

$$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|\operatorname {Fix} (g)|.$$

Autrement dit, le nombre d'orbites est égal au nombre moyen d'éléments de $X$ fixés par les éléments de $G$. Pour un groupe $G$ infini, le lemme s'énonce sous la forme de l'existence d'une bijection :

$$G\times X/G\ \longrightarrow \ \coprod _{g\in G}\operatorname {Fix} (g).$$

Exemples d'application du lemme

Colliers bicolores

Il existe 8 chaînes de bits possibles de longueur 3, mais relier les extrémités des chaînes ne donne plus que quatre colliers bicolores distincts de longueur 3, donnés par les formes canoniques 000, 001, 011, 111 : les autres chaînes 100 et 010 sont équivalentes à 001 par rotation, tandis que 110 et 101 sont équivalentes à 011. Autrement dit, l'équivalence par rotation partage l'ensemble $X$ des chaînes en quatre orbites :

$X=\{000\}\cup \{001,010,100\}\cup \{011,101,110\}\cup \{111\}.$

La formule de Burnside fait intervenir le nombre de rotations, égal à 3, y compris la rotation nulle, et le nombre de chaînes de bits laissées inchangées par chacune des rotations. Les huit chaines sont inchangées par la rotation nulle, et deux chaines (000 et 111) sont inchangées par les deux autres rotations. Donné par le lemme de Burnside, le nombre de colliers est donc :

$$4={\frac {1}{3}}(8+2+2).$$

Le nombre de colliers dans le cas général ($n$ bits et $c$ couleurs) obtenu par le lemme de Burnside est :

$N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi \left({\frac {n}{d}}\right)c^{d}$

où $\varphi$ est l'indicatrice d'Euler.

Démonstration

Pour chaque diviseur $d$ de $n$, la rotation d'angle $2\pi d/n$ fixe $c^{d}$ colliers et il en est de même pour les $\varphi (n/d)$ rotations d'angle $2k\pi d/n$ avec $k$ premier avec $n/d$.

Colorations d'un cube

Le lemme de Burnside permet de déterminer le nombre de colorations distinctes à rotation près des faces d'un cube en utilisant trois couleurs.

Soit $X$ l'ensemble des 3⁶ colorations possibles des 6 faces d'un cube, et faisons opérer le groupe des rotations $G$ du cube sur $X$ : deux colorations appartiennent à la même orbite précisément lorsque l'une est image de l'autre par rotation. Les colorations distinctes à rotation près correspondent aux orbites de l'action de groupe, et leur nombre peut être trouvé grâce au lemme de Burnside en cherchant le nombre de colorations laissées invariantes par chacune des 24 rotations de $G$ :

Cube à faces colorées

• la rotation identique laisse invariantes les 3⁶ colorations
• les six rotations d'axes passant par les centres des faces et d'angle droit fixent chacune 3³ colorations (l'axe étant vertical, on peut choisir 3 couleurs pour la face du haut et celle du bas, et on ne peut choisir qu'une couleur pour les faces latérales)
• les trois retournements autour des mêmes axes fixent chacun 3⁴ colorations
• les huit rotations d'axes passant par les sommets et d'angle 120 degrés fixent chacune 3² colorations
• les six retournements d'axes passant par les milieux de deux arêtes opposées fixent chacun 3³ colorations.

Une démonstration détaillée peut être trouvée ici.

Le nombre moyen d’un ensemble de points fixes est donc :

$|X/G|={\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57.$

Il existe donc 57 colorations distinctes à rotation près des faces d'un cube par trois couleurs. En général, le nombre de colorations distinctes à rotation près des faces d'un cube par $n$ couleurs est :

${\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right).$

On trouvera d'autres exemples dans.

Démonstration du lemme

La première étape consiste à reformuler la somme portant sur les éléments $g$ du groupe  $G$ sous forme de somme portant sur éléments $x$ de $X$ :

$\sum _{g\in G}|\operatorname {Fix} (g)|=\operatorname {Card} \{(g,x)\in G\times X\mid g\cdot x=x\}=\sum _{x\in X}|G_{x}|.$

Ici $\operatorname {Fix} (g)=\{x\in X\,|\,g.x=x\}$ est l'ensemble des points de $X$ fixés par g ∈ $G$, et $G_{x}=\{g\in G\,|\,g.x=x\}$est le sous-groupe stabilisateur de $x$, ensemble des éléments de $G$ fixant $x\in X$.

Le théorème des stabilisateurs dit que pour tout élément $x$ de  $X$, il existe une bijection naturelle entre l'orbite $G\cdot x=\{g.x\,|\,g\in G\}$ et l'ensemble quotient $G/G_{x}$. Le théorème de Lagrange donne alors:

$|G\cdot x|=[G\,/\,G_{x}]=|G|/|G_{x}|.$

La somme peut donc être réécrite comme suit :

$\sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.$

L'ensemble quotient $X/G$ étant la réunion disjointe des orbites, on a :

$\sum _{x\in X}{\frac {1}{|G\cdot x|}}\ =\sum _{O\in X/G}\,\sum _{x\in O}{\frac {1}{|O|}}\ =\sum _{O\in X/G}1\ =\ |X/G|.$

On obtient le résultat souhaité :

$\sum _{g\in G}|\operatorname {Fix} (g)|=\sum _{x\in X}|G_{x}|=|G|\cdot |X/G|.$

Historique : le lemme "qui n'est pas de Burnside"

William Burnside a énoncé et prouvé ce lemme dans son livre de 1897 sur les groupes finis, en l'attribuant à Frobénius dans un article de 1887. Mais même avant Frobenius, la formule était connue de Cauchy en 1845. Selon la loi de Stigler ce lemme ne porte donc pas le nom du premier découvreur. Par boutade, ce lemme est parfois appelé le lemme qui n'est pas de Burnside.

Voir aussi

• Théorème de dénombrement de Pólya
• Indicateur de cycle

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Burnside's lemma » (voir la liste des auteurs).