Burnsides lemma

Från Wikipedia
Hoppa till: navigering, sök

Burnsides lemma eller Burnsides formel, även kallat Cauchy-Frobenius lemma, är ett resultat inom gruppteori.

Låt G vara en ändlig grupp som verkar på en mängd X, och för varje g i G, låt  X_g beteckna fixpunktsmängden till g. Burnsides lemma säger då att antalet banor, r, är

r=\frac{1}{|G|}\sum_{g \in G} |X_g|

med andra ord är antalet banor lika med det aritmetiska medelvärdet av storleken på fixpunktsmängderna.

|X_g| är antalet element i X som är oförändrade under g, det vill säga

X_g = \{x \in X | x=gx \}.

Antalet banor kan ses som antalet ekvivalensklasser, där två element x_1 och x_2 betraktas som ekvivalenta om det finns ett g så att x_1 = gx_2.

Exempel[redigera | redigera wikitext]

Kub med färgade sidor

Burnsides lemma kan användas för att beräkna antalet unika färgningar (oberoende av rotation) av en kub med tre färger.

Låt X vara mängden av de 36 möjliga färgningarna av en kub. Låt G vara gruppen av kubens rotationer. Två färgningar betraktas som lika om de är rotationer av varandra, det vill säga det finns ett g så att x_1 = gx_2. Antalet unika färgningar är alltså lika med antalet banor i X under G.

G har följande element:

  • Identitetselementet som lämnar alla 36 element i X oförändrade
  • Sex 90-graders rotationer med avseende på en sida, dessa lämnar var och en 33 element i X oförändrade
    Detta eftersom de två sidorna längs rotationsaxeln kan väljas fritt (32 möjligheter) och de fyra sidor som roterar måste vara samma (3 möjligheter). Totalt ger detta 33 möjligheter.
  • Tre 180-graders rotationer med avseende på en sida, som var och en lämnar 34 element i X oförändrade
    Detta eftersom de två sidorna längs rotationsaxeln kan väljas fritt (32 möjligheter) och de fyra sidor som roterar måste vara parvis samma (32 möjligheter). Totalt ger detta 34 möjligheter.
  • Åtta 120-graders rotationer med avseende på ett hörn, som var och en lämnar 32 element iX oförändrade.
    De tre sidorna närmast hörnet måste vara samma och de tre sidorna längst ifrån hörnet måste vara samma, totalt 32 möjligheter.
  • Sex 180-graders rotationer med avseende på en kant, som var och en lämnar 33 element i X oförändrade.
    Vid dessa rotationer byter sidor plats parvis. Alltså måste sidorna vara parvis lika, vilket ger 33 möjligheter.

Antalet banor är därför

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

Alltså finns det 57 sätt att färga en kub med 3 färger. I det allmänna fallet när n färger är tillgängliga finns det på samma sätt

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

unika sätt sätt att färga en kub på.

Cykelstruktur[redigera | redigera wikitext]

På många problem är Burnsides formel dock svår att tillämpa, om inte den aktuella rörelsens cykelstruktur analyseras. Förenkling kan ske om rörelseschemat identifieras med en symmetrisk grupp eller delgrupp till denna. Koefficienterna i cykelindexsumman kan beräknas med hjälp av de Montmort-tal.

Vridningen av kuben ovan kan beskrivas med den symmetriska gruppen S4, som i sin tur är en delgrupp till S6.

Ett annat exempel är att vridningarna av en tetraeder kan jämföras med den alternerande gruppen A4, som är en delgrupp bestående av de jämna permutationerna i S4 och vars cykelindexsumma Z(A4) = 3x22 + 8x1x3 + x14. Antalet sätt att 3-färga hörnen i tetraedern blir således

 \frac{1}{12}\left(3\cdot3^2 + 8\cdot3\cdot3 + 3^4\right) = 15.

Än mer påtaglig blir förenklingen om man vill beräkna antalet möjligheter att färglägga kubens åtta hörn och jämför rörelseschemat med en delgrupp H, av ordning 24, till den symmetriska gruppen S8. Cykelindexsumman blir Z(H) = 9x24 + 8x12x32 + 6x42 + x18, där koefficienterna 9, 8, 6 och 1 är de Montmort-tal. Om man vill 2-färga hörnen blir, med insättning av talet 2 på samma sätt som ovan, resultatet lika med 23. Med tillägg av ytterligare en färg blir antalet möjligheter 333.

Bevis[redigera | redigera wikitext]

För att bevisa satsen kan man först notera att

 \sum_{g \in G} |X_g| = | \{ (g,x) \in G \times X: g.x = x \} | = \sum_{x \in X} |G_x|

där g.x beskriver att g verkar på x och  G_x är stabilisatorn till x. Storleken av  G_x är storleken av G delat på storleken av x:s bana:

\sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|\operatorname{orb}_G(x)|}

om man väljer en godtycklig bana, B, i X, får man att summan

\sum_{x \in B} \frac{1}{|\operatorname{orb}_G(x)|} = |B| \frac{1}{|B|} = 1

för alla banor får man då att:

\sum_{x \in X} \frac{1}{|\operatorname{orb}_G(x)|} = r

där r är antalet banor. Detta ger, med föregående uträkningar, att:

\sum_{g \in G} |X_g| = |G|r \Leftrightarrow r = \frac{1}{|G|} \sum_{g \in G} |X_g|

vilket skulle visas.

Historia[redigera | redigera wikitext]

William Burnside bevisade lemmat i sin bok Theory of Groups of Finite Order från 1897, men angav Georg Frobenius som upphovsman, dock var lemmat känt redan för Augustin Louis Cauchy 1845. Därför kallas ibland lemmat för "lemmat som inte är Burnsides".

Källor[redigera | redigera wikitext]

  • Fraleigh: A First Course in Abstract Algebra, 7th ed. Addison Wesley 2003.
  • Alan Tucker: Applied Combinatorics, John Wiley & Sons 1980.