Lemme de Burnside - Burnside's lemma

Le lemme de Burnside , parfois aussi appelé théorème de comptage de Burnside , le lemme de Cauchy-Frobenius , théorème de comptage d'orbites , ou le lemme qui n'est pas celui de Burnside , est un résultat de la théorie des groupes qui est souvent utile pour tenir compte de la symétrie lors du comptage d'objets mathématiques. Ses divers éponymes sont basés sur William Burnside , George Pólya , Augustin Louis Cauchy et Ferdinand Georg Frobenius . Le résultat n'est pas dû à Burnside lui-même, qui le cite simplement dans son livre « Sur la théorie des groupes d'ordre fini », l'attribuant plutôt à Frobenius (1887) .

Dans la suite, soit G un groupe fini qui agit sur un ensemble X . Pour chaque g de G, notons X ^g l'ensemble des éléments de X qui sont fixés par g (on dit aussi qu'ils sont laissés invariants par g ), c'est-à-dire X ^g = { x ∈ X | g . x = x }. Le lemme de Burnside affirme la formule suivante pour le nombre d' orbites , notée | X / G | :

${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.}$

Ainsi le nombre d'orbites (un nombre naturel ou +∞ ) est égal au nombre moyen de points fixé par un élément de G (qui est aussi un nombre naturel ou l'infini). Si G est infini, la division par | G | peut ne pas être bien défini; dans ce cas, la déclaration suivante en arithmétique cardinale est vraie :

${\displaystyle |G||X/G|=\sum _{g\in G}|X^{g}|.}$

Exemple d'application

Le nombre de colorations distinctes en rotation des faces d'un cube utilisant trois couleurs peut être déterminé à partir de cette formule comme suit.

Soit X l'ensemble des 3 ⁶ combinaisons de couleurs de faces possibles qui peuvent être appliquées à un cube dans une orientation particulière, et le groupe de rotation G du cube agit sur X de manière naturelle. Alors deux éléments de X appartiennent à la même orbite précisément quand l'un est simplement une rotation de l'autre. Le nombre de colorations distinctes en rotation est donc le même que le nombre d'orbites et peut être trouvé en comptant les tailles des ensembles fixes pour les 24 éléments de G .

Cube aux visages colorés

• un élément d'identité qui laisse les 3 ⁶ éléments de X inchangés
• six rotations de visage à 90 degrés, chacune laissant 3 ³ des éléments de X inchangés
• trois rotations de visage à 180 degrés, chacune laissant 3 ⁴ des éléments de X inchangés
• huit rotations de sommet à 120 degrés, chacune laissant 3 ² des éléments de X inchangés
• six rotations de bord à 180 degrés, chacune laissant 3 ³ des éléments de X inchangés

Un examen détaillé de ces automorphismes peut être trouvé ici .

La taille moyenne des correctifs est donc

${\displaystyle {\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 y a donc 57 colorations distinctes en rotation des faces d'un cube en trois couleurs. En général, le nombre de colorations distinctes en rotation des faces d'un cube en n couleurs est donné par

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

Preuve

La première étape de la démonstration du lemme est de réexprimer la somme sur les éléments du groupe g  ∈  G comme une somme équivalente sur l'ensemble des éléments x  ∈  X :

${\displaystyle \sum _{g\in G}|X^{g}|=|\{(g,x)\in G\times X\mid g\cdot x=x\}|=\sum _{ x\dans X}|G_{x}|.}$

(Ici X ^g  = { x  ∈  X  |  gx  =  x } est le sous-ensemble de tous les points de X fixés par g  ∈  G , tandis que G _x  = { g  ∈  G  |  gx  =  x } est le sous - groupe stabilisateur de G qui fixe le point x  ∈  X .)

Le théorème du stabilisateur d'orbite dit qu'il existe une bijection naturelle pour chaque x  ∈  X entre l'orbite de x , Gx  = { gx  | g  ∈  G }  X , et l'ensemble des co-ensembles de gauche G/G _x de son sous-groupe stabilisateur G _x . Avec le théorème de Lagrange cela implique

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

Notre somme sur l'ensemble X peut donc être réécrite comme

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

Enfin, notez que X est l'union disjointe de toutes ses orbites dans X/G , ce qui signifie que la somme sur X peut être décomposée en sommes distinctes sur chaque orbite individuelle.

${\displaystyle \sum _{x\in X}{\frac {1}{|G\cdot x|}}=\sum _{A\in X/G}\sum _{x\in A}{\ frac {1}{|A|}}=\somme _{A\in X/G}1=|X/G|.}$

Tout mettre ensemble donne le résultat souhaité :

${\displaystyle \sum _{g\in G}|X^{g}|=|G|\cdot |X/G|.}$

Cette preuve est essentiellement aussi la preuve de la formule d' équation de classe , simplement en prenant l'action de G sur lui-même ( X = G ) pour être par conjugaison, g . x = gxg ⁻¹ , auquel cas G _x instancie au centralisateur de x dans G .

Histoire : le lemme qui n'est pas celui de Burnside

William Burnside a énoncé et prouvé ce lemme, l'attribuant à Frobenius 1887 , dans son livre de 1897 sur les groupes finis. Mais, même avant Frobenius, la formule était connue de Cauchy en 1845. En fait, le lemme était apparemment si bien connu que Burnside a simplement omis de l'attribuer à Cauchy. Par conséquent, ce lemme est parfois appelé le lemme qui n'est pas celui de Burnside (voir aussi la loi d'éponymie de Stigler ). C'est moins ambigu qu'il n'y paraît : Burnside a contribué à de nombreux lemmes dans ce domaine.

Voir également

• Théorème d'énumération de Pólya

Remarques

Les références

• Burnside, William (1897) Théorie des groupes d'ordre fini , Cambridge University Press , au Projet Gutenberg et ici à Archive.org . (Il s'agit de la première édition ; l'introduction de la deuxième édition contient la célèbre volte face de Burnside concernant l'utilité de la théorie des représentations .)
• Frobenius, Ferdinand Georg (1887), « Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul », Crelle's Journal , 101 (4) : 273-299, doi : 10.3931/e-rara-18804.
• Neumann, Peter M. (1979), "Un lemme qui n'est pas celui de Burnside", The Mathematical Scientist , 4 (2) : 133-141, ISSN  0312-3685 , MR  0562002.
• Rotman, Joseph (1995), Une introduction à la théorie des groupes , Springer-Verlag, ISBN 0-387-94285-8.

• Cheng, Yuanyou F. (1986), Une généralisation du lemme de Burnside pour multiplier les groupes transitifs , journal de l'Université de technologie du Hubei, ISSN  1003-4684.