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é[1]. 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 un groupe fini opérant sur un ensemble . Pour tout élément de , désigne le fixateur de , ensemble des éléments de fixés par (soit laissés invariants sous l'action de ) : . Le lemme de Burnside consiste en la formule suivante donnant le nombre d'orbites sous l'action de , autrement dit le nombre d'éléments de l'ensemble quotient [2] :Autrement dit, le nombre d'orbites est égal au nombre moyen d'éléments de fixés par les éléments de . Pour un groupe infini, le lemme s'énonce sous la forme de l'existence d'une bijection :

Exemples d'application du lemme

modifier

Colliers bicolores

modifier

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   des chaînes en quatre orbites :

 

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 : Le nombre de colliers dans le cas général (  bits et   couleurs) obtenu par le lemme de Burnside est :

 

  est l'indicatrice d'Euler[3].

Colorations d'un cube

modifier

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   l'ensemble des 36 colorations possibles des 6 faces d'un cube, et faisons opérer le groupe des rotations   du cube sur   : 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   :

 
Cube à faces colorées
  • la rotation identique laisse invariantes les 36 colorations
  • les six rotations d'axes passant par les centres des faces et d'angle droit fixent chacune 33 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 34 colorations
  • les huit rotations d'axes passant par les sommets et d'angle 120 degrés fixent chacune 32 colorations
  • les six retournements d'axes passant par les milieux de deux arêtes opposées fixent chacun 33 colorations.

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

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

 

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   couleurs est :

 

On trouvera d'autres exemples dans[4],[5],[3].

Démonstration du lemme

modifier

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

 

Ici   est l'ensemble des points de   fixés par g ∈  , et  est le sous-groupe stabilisateur de  , ensemble des éléments de   fixant  .

Le théorème des stabilisateurs dit que pour tout élément   de   , il existe une bijection naturelle entre l'orbite   et l'ensemble quotient  . Le théorème de Lagrange donne alors:

 

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

 

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

 

On obtient le résultat souhaité :

 

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

modifier

William Burnside a énoncé et prouvé ce lemme dans son livre de 1897 sur les groupes finis[1], en l'attribuant à Frobénius dans un article de 1887[6]. Mais même avant Frobenius, la formule était connue de Cauchy en 1845[7],[8]. 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[9],[4].

Voir aussi

modifier

Références

modifier
  1. a et b (en) William Burnside, Theory of Groups of Finite Order, Cambridge University Press, (lire en ligne)
  2. Louis Comtet, Analyse combinatoire,, t. 2, Presses universitaires de France, , p. 90
  3. a et b « Dénombrement des colliers à n perles et c couleurs », sur agregmaths.free.fr/
  4. a et b J. P. Delahaye, « Le miraculeux « lemme de Burnside » », Pour La Science, no 350,‎ , p. 144-149 (lire en ligne)
  5. El Ji, « Lemme de Burnside : exemples et applications », sur Choux Romanesco, Vache qui rit et Intégrales curvilignes,
  6. (de) Ferdinand Georg Frobenius, « Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul », Journal de Crelle, vol. 101, no 4,‎ , p. 273–299 (lire en ligne)
  7. A. Cauchy, « Mémoire sur diverses propriétés remarquables des substitutions régulières ou irrégulières, et des systèmes de substitutions conjuguées », Comptes Rendus de l'Académie des Sciences, vol. 21,‎ , p. 835
  8. A. Cauchy, Œuvres Complètes d'Augustin Cauchy, t. IX, Paris, Gauthier-Villars, , p. 342-360
  9. Neumann, « A lemma that is not Burnside's », The Mathematical Scientist, vol. 4, no 2,‎ , p. 133–141 (ISSN 0312-3685, MR 562002).