Lemat Burnside’a

Lemat Burnside’a, lemat Cauchy’ego-Frobeniusa-Burnside’a – twierdzenie z pogranicza kombinatoryki i teorii grup stosowane, gdy należy znaleźć liczbę różnych obiektów matematycznych z dokładnością do pewnych symetrii. Lemat Burnside’a określa liczbę różnych orbit elementów zbioru, na którym działa grupa symetrii, czyli liczbę różnych elementów tego zbioru przy założeniu, że utożsamiamy ze sobą obiekty symetryczne – takie, że pewien element grupy przekształca jeden z tych obiektów w drugi.

Historia i nazwa

Lemat Burnside’a został spopularyzowany przez brytyjskiego matematyka Williama Burnside’a, autora pierwszego podręcznika do teorii grup w języku angielskim. Choć w pierwszym wydaniu tej książki z 1897 roku Burnside przypisał autorstwo tego wzoru Ferdinardowi Frobeniusowi, w drugim wydaniu z 1911 roku tej informacji zabrakło. Zapewne właśnie dlatego omawiany wynik zaczął być nazywany „lematem Burnside’a”. Pomyłkę tę zauważył Peter Neumann w 1979 roku, nie tylko przypominając, że Burnside swój lemat zaczerpnął z pracy Frobeniusa, lecz zwracając również uwagę na to, że można go było znaleźć w znacznie wcześniejszych pracach francuskiego matematyka Augustina Cauchy’ego.

Kontrowersyjna nazwa „lemat Burnside’a” stanowi zatem przykład działania prawa Stiglera. Neumann zaproponował, by lemat nazywać nazwiskami Cauchy’ego i Frobeniusa. Nie przyjęło się to jednak wśród tych autorów, którzy doceniają wkład Burnside’a w spopularyzowanie tego twierdzenia, pozostając przy starej nazwie lub nazywając je lematem Cauchy’ego-Frobeniusa-Burnside’a.

Twierdzenie

Niech grupa $G$ działa na zbiorze $X$. Elementy grupy będziemy nazywać operatorami, a elementy zbioru – punktami. Dla ustalonego punktu $x\in X$ zbiór $\operatorname {Orb} (x)=\{gx\;\colon \,g\in G\}$ nazwijmy jego orbitą. Poprzez $|\operatorname {Fix} (g)|$ oznaczamy liczbę punktów stałych operatora $g$, czyli liczność zbioru $\{x\in X\;\colon \,gx=x\}$.

Lemat Burnside’a daje następujący wzór na liczbę orbit $|X/G|$:

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

Liczba orbit jest zatem średnią arytmetyczną liczby punktów stałych poszczególnych operatorów.

Dowód

Niech $n=|X/G|$ oraz $O_{1},O_{2},\dots ,O_{n}$ będą wszystkimi orbitami. Znajdziemy teraz dwoma sposobami wartość sumy

$S=\sum _{x\in X}{\frac {1}{{\mid }Orb(x){\mid }}}$.

Ponieważ orbity są klasami abstrakcji relacji równoważności zdefiniowanej poprzez

$x\sim y\iff \exists g\in G\colon gx=y$,

dzielą one zbiór $X$ na rozłączne podzbiory. Stąd zachodzi równość

$S=\sum _{k=1}^{n}\sum _{x\in O_{k}}{\frac {1}{{\mid }O_{k}{\mid }}}=\sum _{k=1}^{n}{\mid }O_{k}{\mid }\cdot {\frac {1}{{\mid }O_{k}{\mid }}}=n$.

(1)

Z drugiej strony zdefiniujmy $\operatorname {Stab} (x)=\{g\in G\;\colon \,gx=x\}$. Wówczas na mocy twierdzenia o orbitach i stabilizatorach dla każdego $x\in X$ mamy

${\mid }\operatorname {Orb} (x){\mid }\cdot {\mid }\operatorname {Stab} (x){\mid }={\mid }G{\mid }$,

zatem

$S=\sum _{x\in X}{\frac {{\mid }\operatorname {Stab} (x){\mid }}{{\mid }G{\mid }}}={\frac {1}{{\mid }G{\mid }}}\sum _{x\in X}{\mid }\operatorname {Stab} (x){\mid }={\frac {1}{{\mid }G{\mid }}}\sum _{g\in G}{\mid }\operatorname {Fix} (g){\mid }$.

(2)

Ostatnia równość wynika z tego, że obie sumy równe są liczbie takich par $(g,x)$, że $gx=x$.

Przyrównując prawe strony równości (1) i (2), natychmiast otrzymujemy tezę lematu.

Przykład

Zliczanie naszyjników

Dysponujemy dowolną liczbą białych i czarnych paciorków, które nawlekamy na sznurek i łączymy go w pętlę. Chcemy ustalić, ile istotnie różnych naszyjników o $n$ paciorkach możemy stworzyć. Równoważnie możemy zapytać, ile jest różnych pokolorowań wierzchołków $n$-kąta foremnego dwoma kolorami, przy czym pokolorowania uznajemy za takie same, jeśli pewne przekształcenie z grupy diedralnej $D_{n}$ przekształca jedno z nich w drugie.

Przeanalizujmy ten problem dla $n=5$. Każdy operator z grupy $D_{5}$ potraktujmy jako permutację wierzchołków pięciokąta foremnego. Wówczas pokolorowanie jest punktem stałym pewnego operatora wtedy i tylko wtedy, gdy wierzchołki należące do tego samego cyklu odpowiadającej mu permutacji są zawsze pokolorowane tym samym kolorem. Grupa $D_{5}$ składa się z następujących elementów:

• identyczność – odpowiada jej permutacja o 5 cyklach, stąd ma ona oczywiście $2^{5}$ punktów stałych,
• 5 odbić względem osi symetrii – każdemu z nich odpowiada permutacja o 3 cyklach, więc mają po $2^{3}$ punktów stałych,
• 4 obroty o odpowiednio $72^{\circ }$, $144^{\circ }$, $216^{\circ }$ i $288^{\circ }$ stopni – każdemu odpowiada permutacja o jednym cyklu, czyli obroty mają po 2 punkty stałe.

Korzystając teraz z lematu Burnside’a, otrzymujemy liczbę istotnie różnych naszyjników o 5 paciorkach:

${\frac {1}{10}}(1\cdot 2^{5}+5\cdot 2^{3}+4\cdot 2)=8$.

Zobacz też

• Grupa symetrii
• Działanie grupy na zbiorze
• Relacja równoważności

Linki zewnętrzne

• Film w ramach ćwiczeń z Matematyki Dyskretnej MIMUW
• PawełP. Burzyński PawełP., Teoria grup w kombinatoryce, [w:] pismo „Delta”, deltami.edu.pl, 2016, ISSN 0137-3005 [dostęp 2024-04-28]  (pol.).