Burnsides lemma

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 ${\displaystyle X_{g}}$ beteckna fixpunktsmängden till g. Burnsides lemma säger då att antalet banor, r, är

${\displaystyle 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.

${\displaystyle |X_{g}|}$ är antalet element i ${\displaystyle X}$ som är oförändrade under g, det vill säga

${\displaystyle X_{g}=\{x\in X|x=gx\}}$.

Antalet banor kan ses som antalet ekvivalensklasser, där två element ${\displaystyle x_{1}}$ och ${\displaystyle x_{2}}$ betraktas som ekvivalenta om det finns ett ${\displaystyle g}$ så att ${\displaystyle x_{1}=gx_{2}}$.

Exempel

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 3⁶ 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 ${\displaystyle 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 3⁶ element i X oförändrade
• Sex 90-graders rotationer med avseende på en sida, dessa lämnar var och en 3³ element i X oförändrade

  Detta eftersom de två sidorna längs rotationsaxeln kan väljas fritt (3² möjligheter) och de fyra sidor som roterar måste vara samma (3 möjligheter). Totalt ger detta 3³ möjligheter.

• Tre 180-graders rotationer med avseende på en sida, som var och en lämnar 3⁴ element i X oförändrade

  Detta eftersom de två sidorna längs rotationsaxeln kan väljas fritt (3² möjligheter) och de fyra sidor som roterar måste vara parvis samma (3² möjligheter). Totalt ger detta 3⁴ möjligheter.

• Åtta 120-graders rotationer med avseende på ett hörn, som var och en lämnar 3² element i X 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 3² möjligheter.

• Sex 180-graders rotationer med avseende på en kant, som var och en lämnar 3³ element i X oförändrade.

  Vid dessa rotationer byter sidor plats parvis. Alltså måste sidorna vara parvis lika, vilket ger 3³ möjligheter.

Antalet banor är därför

${\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.}$

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

${\displaystyle {\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

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 S₄, som i sin tur är en delgrupp till S₆.

Ett annat exempel är att vridningarna av en tetraeder kan jämföras med den alternerande gruppen A₄, som är en delgrupp bestående av de jämna permutationerna i S₄ och vars cykelindexsumma Z(A₄) = 3x₂² + 8x₁x₃ + x₁⁴. Antalet sätt att 3-färga hörnen i tetraedern blir således

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

Än påtagligare 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 S₈. Cykelindexsumman blir Z(H) = 9x₂⁴ + 8x₁²x₃² + 6x₄² + x₁⁸, 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

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

${\displaystyle \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 ${\displaystyle G_{x}}$ är stabilisatorn till x. Storleken av ${\displaystyle G_{x}}$ är storleken av G delat på storleken av x:s bana:

${\displaystyle \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

${\displaystyle \sum _{x\in B}{\frac {1}{|\operatorname {orb} _{G}(x)|}}=|B|{\frac {1}{|B|}}=1}$

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

${\displaystyle \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:

${\displaystyle \sum _{g\in G}|X_{g}|=|G|r\Leftrightarrow r={\frac {1}{|G|}}\sum _{g\in G}|X_{g}|}$

vilket skulle visas.

Fylligare bevis

Vi börjar med en permutationsgrupp G={g₁, g₂, ... g_p} som vi låter verka på en mängd element, låt säga teckensträngar av en viss längd, X={x₁, x₂, ... x_q}. Betrakta produktmängden G × X = {g_ix_j: 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:

Om g_ix_j=x_j, 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å

${\displaystyle 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 G_x eller stab_G(x), och den mängd av strängar som är fixpunkter under permutationen g betecknar vi X_g. 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.:

${\displaystyle 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, orb_G(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 |orb_G(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 C₄ 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 stab_G(RGBRGBRGB)={1, r³, r⁶}, d.v.s. identitetsavbildningen 1, rotation tre steg r³=rrr och rotation sex steg r⁶=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, r⁴, r⁷}) från RGBRGBRGB, och om vi istället tar r² 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 stab_G(x) är ju en delgrupp till G, alltså har vi |stab_G(x)| ⋅ n = |G|, där n är ett heltal - som i vårt fall är lika med |orb_G(x)|).

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

${\displaystyle |\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:

${\displaystyle \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 E_x så består den av ett antal, |E_x|=n, element, och eftersom

${\displaystyle |\operatorname {orb} _{G}(x)|=n}$

så

${\displaystyle \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={E₁, E₂ ... E_r} 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

${\displaystyle \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

${\displaystyle \sum _{g\in G}|X_{g}|=|G|\sum _{x\in X}{\frac {1}{|\operatorname {orb} _{G}(x)|}}=|G|r\Leftrightarrow }$

${\displaystyle r={\frac {1}{G}}\sum _{g\in G}|X_{g}|}$

"V.s.b."

Historia

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

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

Externa länkar

• Burnside, William (1897) Theory of Groups of Finite Order, Cambridge University Press, på Project Gutenberg och här på Archive.org.