Lemma di Burnside

Il lemma di Burnside, a volte detto teorema del conteggio di Burnside, lemma di Cauchy–Frobenius, teorema del numero delle orbite, o lemma di Frobenius, è un risultato della teoria dei gruppi che è spesso utile nel tenere conto della simmetria quando si contano oggetti matematici. I suoi eponimi si basano sui matematici William Burnside, George Pólya, Augustin-Louis Cauchy e Ferdinand Georg Frobenius. Il risultato non è dovuto allo stesso Burnside, che si limita a citarlo nel suo libro On the Theory of Groups of Finite Order, attribuendolo invece a Frobenius.

Il lemma di Burnside conta le orbite dell'azione di un gruppo G su un insieme X, che è la stessa cosa che contare oggetti distinti tenendo conto di una simmetria. Altri modi per dirlo sono contare oggetti distinti rispetto una data relazione di equivalenza R, o contare gli oggetti che sono in forma canonica.

Punti fissi di un G-set X finito

Consideriamo l'azione di un gruppo finito detta G - set X. In particolare un'azione sinistra su X: α:G×X→X(g, x)↦g⋅x con la relazione binaria naturale su X

x∼y⟺∃g∈G:g⋅x=y∀x,y∈X

che partiziona l'insieme X in insiemi digiunti ciascuno detto orbita di x, dove x è l'elemento rappresentativo. Da notare che tali classi di equivalenza sono dei sottoinsiemi e non dei sottogruppi di G. Nel seguito denotiamo con nO=|X/G| il numero di orbite distinte, e definiamo l'insieme degli elementi rappresentativi delle singole classi come:

{x1, x2…,xnO}⊆X.

Allora il corrispondente stabilizzatore di x, è il sottogruppo di tutti gli g che lasciano x invariato g⋅x=x∀g∈G. Se, per un certo x fissato, si verifica

OG(x)={x}|OG(x)|=1
Gx=G|Gx|=|G|

diremo x punto fisso per G-set X. Data questa definizione ha senso definire l'insieme dei punti fissi dell'azione:

FixX(⋅G)={(g, x)∈G×X|g⋅x=x}⊆X.

Fissiamo un elemento g di G, con il simbolo Xg denotiamo l'insieme degli elementi in X che sono fissati da g (anche detti essere invarianti a sinistra per g), riportiamo pure la definizione analoga degli g che sono fissati o invarianti a sinistra per x (sottogruppo stabilizzatore), cioè:

Xg=Fix(g)={x∈X | g⋅x=x, g∈G}⊆X
Gx=Sta(x)={g∈G| g⋅x=x, x∈X}}≤G

da notare la differenza tra l'insieme dei punti fissi di X rispetto ad un g dato e il sottogruppo stabilizzatore di G per un x dato, cioè gli elementi g di G che lasciano x invariato. Allora la cardinalita dell'insieme dei punti fissi si può esprimere con due espressioni equivalenti

|FixX(⋅G)|=∑g∈G|Xg|=∑x∈X|Gx|.

Enunciato

Il lemma di Burnside consiste nella seguente formula per il numero di orbite, che abbiamo denotato |X/G|:

Lemma di Burnside (1897) - Frobenius (1887) — 
G-set X finito ⟹|X/G| = 1|G|∑g∈G|Xg|.

Quindi il numero di orbite (un numero naturale o +∞) è uguale alla media di punti fissati da un elemento g di G (con l'ordine di G che è anche un numero naturale o infinito). Se G è infinito, la divisione per |G| potrebbe non essere ben definita; in questi casi vale la seguente definizione in aritmetica cardinale: |G||X/G|=∑g∈G|Xg|.

Dimostrazione

Il primo passo nella dimostrazione del lemma è già stato visto e consiste nell'esplicitare la somma sugli elementi del gruppo g ∈ G come somma equivalente sull'insieme degli elementi x ∈ X:

∑g∈G|Xg|=∑x∈X|Gx|.

Se consideriamo l'orbita OG(x) formata da |OG(x)| elementi di X, ogni suo punto y∈Og(x) è fissato dagli elementi g del suo stabilizzatore Gy. Il teorema orbita-stabilizzatore dice che esiste una biiezione naturale per ogni x∈X tra l'orbita di x, G⋅x=OG(x)={y∈X|g⋅x=y, g∈G}⊆X, e l'insieme dei coset sx G/∼⋅Gx del suo sottogruppo stabilizzatore Gx o in notazione |OG(x)|=[G:Gx]. Allora si ha pure:

g⋅x=y⟹g Gx g−1=Gy

cioè sono sottogruppi coniugati con |Gx|=|Gy| e con stesso indice [G:Gx]=[G:Gy]. Inoltre per il teorema di Lagrange fissato un elemento rappresentativo dell'orbita si ha:

|G⋅x|=|OG(x)|=[G:Gx]=|G|/|Gx|⟹|G|=[OG(x)||Gx|.

Quindi ogni orbita dell'azione G su X ha |G| punti fissi, per cui la sommatoria sull'insieme X può anche scriversi

∑x∈X|Gx|=∑i=1nO∑y∈OG(xi)|Gy|=∑i=1nO|OG(xi)| |Gxi|=∑i=1nO|G|=nO|G|=|X/G||G|

ottenendo la tesi

|X/G|=1|G|∑g∈G|Xg|=1|G|∑g∈G|Fix(g)|.

Questa dimostrazione è essenzialmente anche la dimostrazione dell'equazione di classe, semplicemente considerando l'azione di coniugio di G su se stesso (X = G), g.x = gxg−1, nel qual caso Gx dicesi centralizzatore di x in G.

Esempi di applicazioni

Colorare gli n-vertici di un poligono con q-colori distinti

D3 ≅ S3
Triangolo con vertici colorati da due colori: nero (b) e bianco (w). L'insieme S formato dagli 8 triangoli viene partizionato, per il lemma di Burnside, in 4 sottoinsiemi dal gruppo simmetrico S3.

Consideriamo una collana con tre perle di due colori diversi, oppure un vettore di tre bit (ogni bit può assumere solo i valori 0 ed 1). Vogliamo conoscere le configurazioni non equivalenti quando muoviamo la collana nello spazio o shiftiamo i bit a sinistra.

Teoricamente equivale a considerare il gruppo diedrale D3 applicato ad un triangolo in cui i tre vertici sono punti con due colori diversi. Cioè analizziamo il semplice caso q=2, n=3.

Se consideriano il triangolo fisso, allora ogni punto dei 3 vertici può avere solo due distinti colori, nero (b) e bianco (w) ad esempio. Per calcolare le configurazioni usiamo il calcolo combinatorio come si può notare dalla prima tabella che segue. Quindi le configurazioni fisse sono date dalle disposizioni con ripetizione di 2 oggetti di classe 3 cioè qn = 23 = 8, come si nota dall'immagine sulla destra. Adesso supponiamo di effettuare operazioni di movimento e notiamo che certe configurazioni sono indistinguibili. Tali operazioni sono quelle del gruppo S3 formato dai 6 elementi

S3=D3={π3,π32,π33,σ',σ'',σ'''}|S3|=3!=2⋅3=6

che agiscono sull'insieme dei vertici V={1,2,3} del triangolo equilatero. Adesso, per estensione, consideriamo l'azione di S3 sull'insieme delle configurazioni dei triangoli, cioè

X=S={C1,C2,C3,C4,C5,C6,C7,C8}|S|=8

La rotazione di 2/3 π⋅3 in senso antiorario, che corrisponde all'elemento identità π33 di G, applicata agli 8 triangoli si rappresenta con la permutazione

π‾33=id=(C1C2C3C4C5C6C7C8C1C2C3C4C5C6C7C8)=(C1)(C2)(C3)(C4)(C5)(C6)(C7)(C8)

tale operazione di simmetria lascia tutte le configurazioni invariate, quindi si ha Fix(π‾33)=8. Analogamente abbiamo

π‾3=(C1C2C3C4C5C6C7C8C1C4C2C3C7C5C6C8)=(C1)(C2 C4 C3)(C5 C7 C6)(C8)

tale operazione (rotazione di 2/3 π in senso antiorario) lascia due configurazioni invariate che sono C1,C8, quindi Fix(π‾3)=2. Idem per l'azione di π‾32. Per le riflessioni si ottiene:

σ‾'=(C1C2C3C4C5C6C7C8C1C3C2C4C7C6C5C8)=(C1)(C3 C2)(C4)(C5 C7)(C6)(C8)

quindi restano 4 configurazioni invariate (in questo caso sono C1,C4,C6,C8), cioè Fix(σ‾')=4. Idem per σ‾'', σ‾'''. Adesso possiamo applicare il lemma di Burnside per trovare il numero di classi di equivalenza (il numero delle orbite) in cui viene partizionato S dall'azione di G=S3:

|SG|=1|G|∑g∈G|Sg|=Fix(π‾33) +Fix(π‾3) +Fix(π‾32) +Fix(σ‾') +Fix(σ‾'') +Fix(σ‾''')6=8 +2 +2 +4 +4 +46=246=4.

Come si nota nell'immagine sulla destra ci sono esattamente 4 classi di equivalenza che partizionano l'insieme delle configurazioni possibili S.

Utilizzando la rappresentazione di ciascun elemento di g∈G come cicli digiunti, possiamo costruire il polinomio indice ciclico PG(x1, x2, x3) per il gruppo G delle permutazioni, come si nota dalla seconda tabella.

Pattern (r1 ,r2) P'n,k=k!r1! r2!
w w w(3 ,0)1
w w b(2 ,1)3
w b b(1 ,2)3
b b b(0 ,3)1
D'n,k=nk=∑i=0C'n,k−1=k!rC'n,k−1−i! ri!=1 +3 +3 +1=8=23
g∈D3 Ci∈S invarianti rappresentazione algebrica di g
π33=(1)(2)(3)23: C1,…,C8x13
π3=(1 2 3)2: C1,C8x3
π32=(1 3 2)2: C1,C8x3
σ'=(1 2)(3)22: C1,C4,C6,C8x2 x1
σ''=(1 3)(2)22: C1,C2,C7,C8x2 x1
σ'''=(2 3)(1)22: C1,C3,C5,C8x2 x1
PG(x1, x2, x3)=x13 +3x2x1 +2x3|G|

ricordo che la notazione xlk indica la rappresentazione della struttura ciclica dell'elemento g∈G, cioè che vi sono un numero k di l-cicli. Ad esempio g=(1)(2)(34)(56)(789) viene rappresentato algebricamente come x12 x22 x3. Tale polinomio permette di generalizzare a q-colori di S non equivalenti ottenendo:

PG(q, q, q)=q3 +3⋅q⋅q +2⋅q6=q3 +3 q2 +2 q6=|SG|

ed applicandolo al caso di 2-colori si ottiene il risultato visto prima

PG(2, 2, 2)=23 +3⋅2⋅2 +2⋅26=8 +12 +46=246=4.

Ponendo il problema su 3-colori si ottiene |S|=33=27 possibili configurazioni che vengono partizionate in

PG(3, 3, 3)=33 +3⋅3⋅3 +2⋅36=27 +27 +66=606=10.

classi di equivalenza o numero di orbite.

Nel contesto dei quesiti iniziali otteniamo risultati analoghi: nel caso delle collane con 3 perle con 2 colori considerando le operazioni di rotazione e riflessione abbiamo le classi di equivalenza cl1={bbb}, cl2={bbw,bwb,wbb}, cl3={wwb,wbw,bww} e cl4={www}. Nel caso dei vettori bit (con 2 valori possibili:0,1) di lunghezza 3 considerando solo le operazioni di rotazione abbiamo le classi di equivalenza cl1={000}, cl2={001,100,010}, cl3={011,110,101} e cl4={111}. Quindi stiamo considerando come gruppo G=A3≤S3, e l'insieme S={000,001,010,011,100,101,110,111} su cui agisce shiftando i bit verso sinistra. G agisce su S tramite 3 rotazioni: 0-rotazione lascia tutti e 8 vettori di bit invariati, la 1-rotazione lascia 2 vettori fissi, la 2-rotazione lascia 2 vettori fissi. Il numero di orbite o classi di equivalenza sono:

|SG|=13(8+2+2)=4.
D4 ≤ S4
Insieme S di 16 quadrati con vertici a due colori: nero (b) e bianco (w). S viene partizionato in 6 sottoinsiemi dal gruppo diedrale D4.

Consideriamo una collana con quattro perle con due colori distinti, oppure un vettore di quattro bit. Equivale a considerare il gruppo diedrale D4 applicato ad un quadrato i cui quattro vertici sono punti con due diversi colori.

Se consideriano il quadrato fisso, allora ogni punto dei 4 vertici può avere solo due distinti colori, nero (b) e bianco (w). Quindi le configurazioni fisse sono qn = 24 = 16, come si nota dall'immagine sulla destra. Tali operazioni sono quelle del gruppo D4, cioè

D4 = {π4,π42,π43,π44,σ1,σ2,σ3,σ4}|D4|=2⋅4=8

che agisce sui vertici V={1,2,3,4} del quadrato (poligono con 4 lati e 4 vertici). Per estensione possiamo considerare l'azione sull'insieme delle configurazioni dei quadrati con vertici a due colori, cioè dell'insieme

X=S={C1,C2,⋯,C15,C16}|S|=16.

Con ragionamenti analoghi al caso precedente del triangolo equilatero, le operazioni di rotazione e riflessione sull'insieme S produce le seguenti classi di equivalenza (avendo numerato i vertici in senso orario partendo da quello sx-alto) cl1={wwww}, cl2={wwwb,bwww,wbww,wwbw}, cl3={wwbb,bwwb,bbww,wbbw} cl4={bwbw,wbwb}, cl5={wbbb,bwbb,bbwb,bbbw}, cl6={bbbb}.

Utilizzando la rappresentazione di ciascun elemento di g∈G come cicli digiunti, possiamo costruire il polinomio indice ciclico PG(x1, x2, x3) per il gruppo G delle permutazioni:

Pattern (r1 ,r2) P'n,k=k!r1! r2!
w w w w(4 ,0)1
w w w b(3 ,1)4
w w b b(2 ,2)6
w b b b(1 ,3)4
b b b b(0 ,4)1
D'n,k=nk=∑i=0C'n,k −1 = k!rC'n,k−1−i! ri!=1 +4 +6 +4 +1=16=24
g∈D4 Ci∈S invarianti rappresentazione algebrica di g
π44=(1)(2)(3)(4)24: C1,…,C16x14
π4=(1 2 3 4)2: C1,C16x4
π42=(1 3)(2 4)22: C1,C10,C11,C16x22
π43=(1 4 3 2)2: C1,C16x4
σ1=(1 4)(2 3)22: C1,C7,C9,C16x22
σ2=(1 2)(3 4)22: C1,C6,C8,C16x22
σ3=(1 3)(2)(4)23: C1,C2,C4,C10,C11,C12,C15,C16x12 x2
σ4=(1)(2 4)(3)23: C1,C3,C5,C10,C11,C12,C14,C16x12 x2
PG(x1, x2, x3, x4)=x14 +2x4 +3x22 +2x2x12|G|

Tale polinomio permette di generalizzare a q-colori di S non equivalenti ottenendo:

PG(q, q, q, q)=q4 +2⋅q +3⋅q2 +2⋅q⋅q28=q4 +2 q3 +3 q2 +2 q8=|SG|

ed applicandolo al caso di 2-colori si ottiene il risultato visto prima

PG(2, 2, 2, 2)=24 +2⋅23 +3⋅22 +2⋅28=16 +16 +12 +48=488=6.

Quindi per vettori di 4 bit, abbiamo 24=16 elementi di S; G agisce su S tramite 4 rotazioni; la rotazione nulla lascia invariati tutti i vettori a 16 bit; le rotazioni tipo 1 e 3 lasciano invariati due vettori di bit (0000, 1111); la rotazione tipo 2 lascia invariati 4 vettori di bit (0000, 0101, 1010, 1111); ottenendo un totale di vettori

6=14(16+2+4+2).

I sei vettori distinti sono rappresentati dalle stringhe 0000, 0001, 0011, 0101, 0111 e 1111.

Dn

Generalizzando ad n-vertici, q-colori, supponiamo che la fattorizzazione in numeri interi di n sia:

n=p1k1 p2k2 ⋯ prkrD⁡= {p1,p2,…, pr, n}|D⁡|=r+1

cioè, p1,p2,…,pr sono numeri primi distinti. Con D definiamo l'insieme dei divisori. Adesso richiamiamo la funzione totiente di Eulero

φ(n)=p1k1−1(p1−1)p2k2−1(p2−1)⋯prkr−1(pr−1)=φ(p1)φ(p2)⋯φ(pr)=∏i=1rφ(pi);φ(p1)=φ(1)=def1

da notare la definizione di φ(p1). Quindi una permutazione di ordine pi ammette un numero n/pi di cicli ognuno di lunghezza pi. Allora il gruppo ciclico delle sole rotazioni Cn ammette il polinomio indice ciclico seguente:

PG(x1, x2,⋯, xn)=1n[φ(p1)xp1n/p1 +φ(p2)xp2n/p2 +⋯+φ(pr)xprn/pr +φ(n)xn]=1n[∑i=1rφ(pi) xpin/pi +φ(n)xn].

Per esempio n=4=1k⋅22∀k∈ℕ ammette come divisori l'insieme {p1k1, p2k2, p3k3}={1, 2, 22} e quindi il polinomio indice ciclico diventa:

PG(x1, x2, x3, x4)=14[φ(1)x1(4/1) +φ(2)x2(4/2) +φ(22)x4]=14[x14 +x22 +2x4].

o nella forma generalizzata q-colori:

PG(q, q, q, q)=q4 +q2 +2q4.

Il gruppo diedrale è come il gruppo ciclico, ma include anche le operazioni di riflessione. Per cui

PG(x1, x2,⋯, xn)=12n∑i=1rφ(pi) xpin/pi +12nφ(n)xn+{12nn x1x2(n−1)/2,n dispari, 12nn2(x12x2(n−2)/2+x2n/2),n pari.

Ad esempio consideriamo una collana con 17 perle con due colori distinti. Equivale a considerare il gruppo diedrale D17 applicato ad un n-agono i cui i 17 vertici sono punti con due diversi colori. Quindi la fattorizzazione e la funzione di eulero diventano:

n=17=1⋅17φ(17)=171−1 (17−1)=16

per cui l'insieme dei divisori diventa D⁡ = {1, 17} ed otteniamo il polinomio

PG(x1, x2,⋯, x17)=12 17[φ(1) x117/1 +φ(17) x17+17 x1x2(17−1)/2]=x117 +16 x17 +17 x1x2834

essendo n dispari. Per n=17,q=2 si ottengono

PG(q, q,⋯, q)=q17 +17 q9 +16 q34=217 +17⋅29 +16⋅234=216 +17⋅28 +1617=65536 +4352 +1617=6990417=4112

Teorici del lemma

Burnside ha esposto e dimostrato questo lemma, attribuendolo a Frobenius, che lo menziona nel suo libro del 1887 sui gruppi finiti. Ma, già prima di Frobenius, la formula era nota a Cauchy nel 1845. Di fatto, il lemma era a quanto pare così ben noto che Burnside ha omesso di attribuirlo a Cauchy. Di conseguenza, questo lemma viene talvolta indicato come il "lemma che non è di Burnside".. La denominazione errata di lemmi e teoremi è definita come la legge dell'eponimia di Stigler.