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.

Fylligare bevis[redigera | redigera wikitext]

Vi börjar med en permutationsgrupp G={g1, g2, ... gp} som vi låter verka på en mängd element, låt säga teckensträngar av en viss längd, X={x1, x2, ... xq}. Betrakta produktmängden G × X = {gixj: 1 ≤ i ≤ p, 1 ≤ j ≤ q}, d.v.s. resultatet av varje enskild permutation på varje enskild sträng, nedan åskådliggjord i en Cayleytabell:

* g1 g2 ... gp
x1 g1x1 g2x1 ... gpx1
x2 g1x2 g2x2 ... gpx2
:  :  :  :::  :
xq g1xq g2xq ... gpxq

Om gixj=xj, eller med underförstådda index, gx=x innebär detta att permutationen g avbildar strängen x på sig själv - d.v.s. gx=x är en så kallad fixpunkt. Det totala antalet fixpunkter i vår tabell är då

fix(G \times X) = | \{ (g,x) \in G \times X: gx = x \} |

Vi kallar den undergrupp av permutationer som avbildar strängen x på sig själv för stabilisatorn till x, betecknad Gx eller stabG(x), och den mängd av strängar som är fixpunkter under permutationen g betecknar vi Xg. Om vi tar stabilisatorernas storlek (d.v.s. antalet permutationer som avbildar strängen x på sig själv) i varje rad (d.v.s. för varje sträng) och sedan lägger ihop dem, eller om vi räknar antalet fixpunkter i varje kolumn (d.v.s. för varje permutation) och lägger ihop dem, blir det i båda fallen självklart lika med antalet fixpunkter i hela tabellen, d.v.s.:

fix(G \times X) = \sum_{g \in G} |X_g| = \sum_{x \in X} |G_x| = \sum_{x \in X}|\operatorname{stab}_G(x))|

Banan för strängen x, orbG(x), är den mängd strängar i X man kan bilda från x med permutationerna i G. Enligt "The Orbit–Stabilizer Theorem" har vi att antalet strängar i banan för x multiplicerat med antalet permutationer i stabilisatorn för x är lika med antalet permutationer i G. D.v.s. permutationerna i G delas så att lika många avbildar vardera av de |orbG(x)| strängarna i banan för x.

Exempel: Strängen "0001" kan genom de fyra permutationerna (representerande rotationerna 0°, 90°, 180° respektive 270°) i den cykliska gruppen C4 ge upphov till "0001", "0010", "0100" och "1000". Antalet strängar i denna bana är sålunda fyra. Antalet stabilisatorer för "0001" är en (identitet, eller "rotation 0°" - den avbildas inte på sig själv av någon annan rotation). "Antalet permutationer totalt är fyra. Strängen "0101" kan å andra sidan bara ge upphov till "0101" och "1010" vilket innebär att banans storlek är två, antalet stabilisatorer för "0101" är två (rotationerna 0° och 180°) och antalet permutationer totalt är fyra. En sträng som "0000" kan bara ge upphov till sig själv: den är ensam i sin bana och producerar sig själv hur man än vrider och vänder den och har sålunda alla fyra permutationerna i sin stabilisator.

Eftersom G är en permutationsgrupp måste varje permutation som är en sammansättning av permutationer som ingår i gruppen också finnas med i G - och om en sträng i X kan produceras från x via andra strängar i X och via en kedja av permutationer, måste det finnas en permutation som motsvarar denna kedja så att strängen kan produceras direkt av x med en permutation. Strängar som är periodiska (d.v.s. kan åstadkommas från samma sträng i X genom mer än en permutation i G - t.ex. som i fallet med "0101" och "0000" i exemplet ovan) har ett antal permutationer som avbildar dem på sig själva - då följder det intuitivt att samma antal permutationer måste finnas från varje x i banan till vart och ett av de andra i densamma: strängarna i klassen är ju ekvivalenta och har ju därför samma symmetriegenskaper.

Exempel: Låt r vara rotationen av ett halsband med nio "pärlor" från 123456789 till 234567891 och betrakta halsbandet RGBRGBRGB under rotationer. Stabilisatorn för halsbandet är stabG(RGBRGBRGB)={1, r3, r6}, d.v.s. identitetsavbildningen 1, rotation tre steg r3=rrr och rotation sex steg r6=rrrrrr. Om vi låter r verka en gång på stabilisatorn får vi en sidoklass (höger eller vänster kvittar i detta fall), d.v.s. vi roterar ett steg till (före eller efter), innehållande de permutationer som ger upphov till GBRGBRGBR (alltså {r, r4, r7}) från RGBRGBRGB, och om vi istället tar r2 får vi de tre permutationerna som ger BRGBRGBRG. För varje permutation i stabilisatorn finns det alltså en "motsvarande" i de båda sidoklasser som ger upphov till de båda andra elementen, vilket ju måste leda till att produkten av antalet permutationer i stabilisatorn och antalet element i banan blir lika med det totala antalet permutationer som tillåts för halsbandet. Tillåter vi även speglingar (för ett verkligt halsband att vi lägger det med andra sidan upp) fördubblas antalet permutationer i G till arton - stabilisatorn påverkas inte, däremot blir banan dubbelt så stor (upprepningarna av följden RBG, i stället för RGB, har ju tillkommit). Se även Lagranges sats (som säger att det är nödvändigt att en delgrupps ordning delar gruppens ordning och stabG(x) är ju en delgrupp till G, alltså har vi |stabG(x)| ⋅ n = |G|, där n är ett heltal - som i vårt fall är lika med |orbG(x)|).

Sålunda, har vi nu bevisat, eller åtminstone resonerat kring:


|\operatorname{stab}_G(x)| . |\operatorname{orb}_G(x)| = |G| \quad  \Leftrightarrow  \quad |\operatorname{stab}_G(x)| = \frac{|G|}{|\operatorname{orb}_G(x)|}

Vi har nu att:

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

Om vi nu tittar på en godtycklig bana Ex så består den av ett antal, |Ex|=n, element, och eftersom

 |\operatorname{orb}_G(x)| = n

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

Om vi nu kallar mängden av banor för E={E1, E2 ... Er} och sålunda med |E|=r avser antalet i denna mängd, d.v.s. antalet banor, så får vi för alla banorna

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

vilket ger att

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

"V.s.b."

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 (i §119), 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.

Externa länkar[redigera | redigera wikitext]