Lemma di Burnside

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

D₃ ≅ S₃

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 ${\displaystyle D_{3}}$ applicato ad un triangolo in cui i tre vertici sono punti con due colori diversi. Cioè analizziamo il semplice caso ${\displaystyle 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è ${\displaystyle q^{n}\ =\ 2^{3}\ =\ 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 ${\displaystyle \color {Blue}S_{3}}$ formato dai 6 elementi

${\displaystyle S_{3}=D_{3}=\{\pi _{3},\pi _{3}^{2},\pi _{3}^{3},\sigma ^{\text{'}},\sigma ^{\text{''}},\sigma ^{\text{'''}}\}\quad |S_{3}|=3!=2\cdot 3=6}$

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

${\displaystyle X=S=\{C_{1},C_{2},C_{3},C_{4},C_{5},C_{6},C_{7},C_{8}\}\quad |S|=8}$

La rotazione di ${\displaystyle 2/3\ \pi \cdot 3}$ in senso antiorario, che corrisponde all'elemento identità ${\displaystyle \pi _{3}^{3}}$ di G, applicata agli 8 triangoli si rappresenta con la permutazione

${\displaystyle {\overline {\pi }}_{3}^{3}=id={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\end{pmatrix}}=(C_{1})(C_{2})(C_{3})(C_{4})(C_{5})(C_{6})(C_{7})(C_{8})}$

tale operazione di simmetria lascia tutte le configurazioni invariate, quindi si ha ${\displaystyle Fix\left({\overline {\pi }}_{3}^{3}\right)=8}$. Analogamente abbiamo

${\displaystyle {\overline {\pi }}_{3}={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{4}&C_{2}&C_{3}&C_{7}&C_{5}&C_{6}&C_{8}\end{pmatrix}}=(C_{1})(C_{2}\ C_{4}\ C_{3})(C_{5}\ C_{7}\ C_{6})(C_{8})}$

tale operazione (rotazione di ${\displaystyle 2/3\ \pi }$ in senso antiorario) lascia due configurazioni invariate che sono ${\displaystyle C_{1},C_{8}}$, quindi ${\displaystyle Fix({\overline {\pi }}_{3})=2}$. Idem per l'azione di ${\displaystyle {\overline {\pi }}_{3}^{2}}$. Per le riflessioni si ottiene:

${\displaystyle {\overline {\sigma }}^{\text{'}}={\begin{pmatrix}C_{1}&C_{2}&C_{3}&C_{4}&C_{5}&C_{6}&C_{7}&C_{8}\\C_{1}&C_{3}&C_{2}&C_{4}&C_{7}&C_{6}&C_{5}&C_{8}\end{pmatrix}}=(C_{1})(C_{3}\ C_{2})(C_{4})(C_{5}\ C_{7})(C_{6})(C_{8})}$

quindi restano 4 configurazioni invariate (in questo caso sono ${\displaystyle C_{1},C_{4},C_{6},C_{8}}$), cioè ${\displaystyle Fix\left({\overline {\sigma }}^{\text{'}}\right)=4}$. Idem per ${\displaystyle {\overline {\sigma }}^{\text{''}},\ {\overline {\sigma }}^{\text{'''}}}$. 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=S₃:

${\displaystyle \left|{\frac {S}{G}}\right|={\frac {1}{|G|}}\sum _{g\in G}|S^{g}|={\frac {Fix\left({\overline {\pi }}_{3}^{3}\right)\ +Fix\left({\overline {\pi }}_{3}\right)\ +Fix\left({\overline {\pi }}_{3}^{2}\right)\ +Fix\left({\overline {\sigma }}^{\text{'}}\right)\ +Fix\left({\overline {\sigma }}^{\text{''}}\right)\ +Fix\left({\overline {\sigma }}^{\text{'''}}\right)}{6}}={\frac {8\ +2\ +2\ +4\ +4\ +4}{6}}={\frac {24}{6}}=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 ${\displaystyle g\in G}$ come cicli digiunti, possiamo costruire il polinomio indice ciclico ${\displaystyle P_{G}(x_{1},\ x_{2},\ x_{3})}$ per il gruppo ${\displaystyle G}$ delle permutazioni, come si nota dalla seconda tabella.

Pattern	${\displaystyle (r_{1}\ ,r_{2})}$	${\displaystyle {P^{'}}_{n,k}={\frac {k!}{r_{1}!\ r_{2}!}}}$
${\displaystyle w\ w\ w}$	${\displaystyle (3\ ,0)}$	${\displaystyle 1}$
${\displaystyle w\ w\ b}$	${\displaystyle (2\ ,1)}$	${\displaystyle 3}$
${\displaystyle w\ b\ b}$	${\displaystyle (1\ ,2)}$	${\displaystyle 3}$
${\displaystyle b\ b\ b}$	${\displaystyle (0\ ,3)}$	${\displaystyle 1}$
	${\displaystyle {\begin{alignedat}{2}{D^{'}}_{n,k}&=n^{k}=\sum _{i=0}^{{C^{'}}_{n,k}-1}={\frac {k!}{r_{{C^{'}}_{n,k}-1-i}!\ r_{i}!}}\\&=1\ +3\ +3\ +1=8=2^{3}\\\end{alignedat}}}$

${\displaystyle g\in D_{3}}$	${\displaystyle C_{i}\in S}$ invarianti	rappresentazione algebrica di ${\displaystyle g}$
${\displaystyle \pi _{3}^{3}=(1)(2)(3)}$	${\displaystyle 2^{3}:\ C_{1},\ldots ,C_{8}}$	${\displaystyle x_{1}^{3}}$
${\displaystyle \pi _{3}=(1\ 2\ 3)}$	${\displaystyle 2:\ C_{1},C_{8}}$	${\displaystyle x_{3}}$
${\displaystyle \pi _{3}^{2}=(1\ 3\ 2)}$	${\displaystyle 2:\ C_{1},C_{8}}$	${\displaystyle x_{3}}$
${\displaystyle {\sigma }^{\text{'}}=(1\ 2)(3)}$	${\displaystyle 2^{2}:\ C_{1},C_{4},C_{6},C_{8}}$	${\displaystyle x_{2}\ x_{1}}$
${\displaystyle {\sigma }^{\text{''}}=(1\ 3)(2)}$	${\displaystyle 2^{2}:\ C_{1},C_{2},C_{7},C_{8}}$	${\displaystyle x_{2}\ x_{1}}$
${\displaystyle {\sigma }^{\text{'''}}=(2\ 3)(1)}$	${\displaystyle 2^{2}:\ C_{1},C_{3},C_{5},C_{8}}$	${\displaystyle x_{2}\ x_{1}}$
	${\displaystyle P_{G}(x_{1},\ x_{2},\ x_{3})={\frac {x_{1}^{3}\ +3x_{2}x_{1}\ +2x_{3}}{|G|}}}$

ricordo che la notazione ${\displaystyle x_{l}^{k}}$ indica la rappresentazione della struttura ciclica dell'elemento ${\displaystyle g\in G}$, cioè che vi sono un numero k di l-cicli. Ad esempio ${\displaystyle g=(1)(2)(34)(56)(789)}$ viene rappresentato algebricamente come ${\displaystyle x_{1}^{2}\ x_{2}^{2}\ x_{3}}$. Tale polinomio permette di generalizzare a q-colori di ${\displaystyle S}$ non equivalenti ottenendo:

${\displaystyle P_{G}(q,\ q,\ q)={\frac {q^{3}\ +3\cdot q\cdot q\ +2\cdot q}{6}}={\frac {q^{3}\ +3\ q^{2}\ +2\ q}{6}}=\left|{\frac {S}{G}}\right|}$

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

${\displaystyle P_{G}(2,\ 2,\ 2)={\frac {2^{3}\ +3\cdot 2\cdot 2\ +2\cdot 2}{6}}={\frac {8\ +12\ +4}{6}}={\frac {24}{6}}=4.}$

Ponendo il problema su 3-colori si ottiene ${\displaystyle |S|=3^{3}=27}$ possibili configurazioni che vengono partizionate in

${\displaystyle P_{G}(3,\ 3,\ 3)={\frac {3^{3}\ +3\cdot 3\cdot 3\ +2\cdot 3}{6}}={\frac {27\ +27\ +6}{6}}={\frac {60}{6}}=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 ${\displaystyle cl_{1}=\{bbb\}}$, ${\displaystyle cl_{2}=\{bbw,bwb,wbb\}}$, ${\displaystyle cl_{3}=\{wwb,wbw,bww\}}$ e ${\displaystyle cl_{4}=\{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 ${\displaystyle cl_{1}=\{000\}}$, ${\displaystyle cl_{2}=\{001,100,010\}}$, ${\displaystyle cl_{3}=\{011,110,101\}}$ e ${\displaystyle cl_{4}=\{111\}}$. Quindi stiamo considerando come gruppo ${\displaystyle G=A_{3}\leq S_{3}}$, e l'insieme ${\displaystyle 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:

${\displaystyle \left|{\frac {S}{G}}\right|={\frac {1}{3}}(8+2+2)=4}$.

D₄ ≤ S₄

Consideriamo una collana con quattro perle con due colori distinti, oppure un vettore di quattro bit. Equivale a considerare il gruppo diedrale ${\displaystyle D_{4}}$ 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 ${\displaystyle q^{n}\ =\ 2^{4}\ =\ 16}$, come si nota dall'immagine sulla destra. Tali operazioni sono quelle del gruppo ${\displaystyle \color {Blue}D_{4}}$, cioè

${\displaystyle \operatorname {D} _{4}\ =\ \{\pi _{4},\pi _{4}^{2},\pi _{4}^{3},\pi _{4}^{4},\sigma ^{\text{1}},\sigma ^{\text{2}},\sigma ^{\text{3}},\sigma ^{\text{4}}\}\quad |D_{4}|=2\cdot 4=8}$

che agisce sui vertici ${\displaystyle 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

${\displaystyle X=S=\{C_{1},C_{2},\cdots ,C_{15},C_{16}\}\quad |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) ${\displaystyle cl_{1}=\{wwww\},\ cl_{2}=\{wwwb,bwww,wbww,wwbw\},\ cl_{3}=\{wwbb,bwwb,bbww,wbbw\}}$ ${\displaystyle cl_{4}=\{bwbw,wbwb\},\ cl_{5}=\{wbbb,bwbb,bbwb,bbbw\},\ cl_{6}=\{bbbb\}}$.

Utilizzando la rappresentazione di ciascun elemento di ${\displaystyle g\in G}$ come cicli digiunti, possiamo costruire il polinomio indice ciclico ${\displaystyle P_{G}(x_{1},\ x_{2},\ x_{3})}$ per il gruppo ${\displaystyle G}$ delle permutazioni:

Pattern	${\displaystyle (r_{1}\ ,r_{2})}$	${\displaystyle {P^{'}}_{n,k}={\frac {k!}{r_{1}!\ r_{2}!}}}$
${\displaystyle w\ w\ w\ w}$	${\displaystyle (4\ ,0)}$	${\displaystyle 1}$
${\displaystyle w\ w\ w\ b}$	${\displaystyle (3\ ,1)}$	${\displaystyle 4}$
${\displaystyle w\ w\ b\ b}$	${\displaystyle (2\ ,2)}$	${\displaystyle 6}$
${\displaystyle w\ b\ b\ b}$	${\displaystyle (1\ ,3)}$	${\displaystyle 4}$
${\displaystyle b\ b\ b\ b}$	${\displaystyle (0\ ,4)}$	${\displaystyle 1}$
	${\displaystyle {\begin{alignedat}{2}{D^{'}}_{n,k}&=n^{k}=\sum _{i=0}^{{C^{'}}_{n,k}\ -1}\ =\ {\frac {k!}{r_{{C^{'}}_{n,k}-1-i}!\ r_{i}!}}\\&=1\ +4\ +6\ +4\ +1=16=2^{4}\\\end{alignedat}}}$

${\displaystyle g\in D_{4}}$	${\displaystyle C_{i}\in S}$ invarianti	rappresentazione algebrica di ${\displaystyle g}$
${\displaystyle {\pi _{4}}^{4}=(1)(2)(3)(4)}$	${\displaystyle 2^{4}:\ C_{1},\ldots ,C_{16}}$	${\displaystyle x_{1}^{4}}$
${\displaystyle {\pi _{4}}=(1\ 2\ 3\ 4)}$	${\displaystyle 2:\ C_{1},C_{16}}$	${\displaystyle x_{4}}$
${\displaystyle {\pi _{4}}^{2}=(1\ 3)(2\ 4)}$	${\displaystyle 2^{2}:\ C_{1},C_{10},C_{11},C_{16}}$	${\displaystyle x_{2}^{2}}$
${\displaystyle {\pi _{4}}^{3}=(1\ 4\ 3\ 2)}$	${\displaystyle 2:\ C_{1},C_{16}}$	${\displaystyle x_{4}}$
${\displaystyle {\sigma }^{1}=(1\ 4)(2\ 3)}$	${\displaystyle 2^{2}:\ C_{1},C_{7},C_{9},C_{16}}$	${\displaystyle x_{2}^{2}}$
${\displaystyle {\sigma }^{2}=(1\ 2)(3\ 4)}$	${\displaystyle 2^{2}:\ C_{1},C_{6},C_{8},C_{16}}$	${\displaystyle x_{2}^{2}}$
${\displaystyle {\sigma }^{3}=(1\ 3)(2)(4)}$	${\displaystyle 2^{3}:\ C_{1},C_{2},C_{4},C_{10},C_{11},C_{12},C_{15},C_{16}}$	${\displaystyle x_{1}^{2}\ x_{2}}$
${\displaystyle {\sigma }^{4}=(1)(2\ 4)(3)}$	${\displaystyle 2^{3}:\ C_{1},C_{3},C_{5},C_{10},C_{11},C_{12},C_{14},C_{16}}$	${\displaystyle x_{1}^{2}\ x_{2}}$
	${\displaystyle P_{G}(x_{1},\ x_{2},\ x_{3},\ x_{4})={\frac {x_{1}^{4}\ +2x_{4}\ +3x_{2}^{2}\ +2x_{2}x_{1}^{2}}{|G|}}}$

Tale polinomio permette di generalizzare a q-colori di ${\displaystyle S}$ non equivalenti ottenendo:

${\displaystyle P_{G}(q,\ q,\ q,\ q)={\frac {q^{4}\ +2\cdot q\ +3\cdot q^{2}\ +2\cdot q\cdot q^{2}}{8}}={\frac {q^{4}\ +2\ q^{3}\ +3\ q^{2}\ +2\ q}{8}}=\left|{\frac {S}{G}}\right|}$

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

${\displaystyle P_{G}(2,\ 2,\ 2,\ 2)={\frac {2^{4}\ +2\cdot 2^{3}\ +3\cdot 2^{2}\ +2\cdot 2}{8}}={\frac {16\ +16\ +12\ +4}{8}}={\frac {48}{8}}=6.}$

Quindi per vettori di 4 bit, abbiamo ${\displaystyle 2^{4}=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

${\displaystyle 6={\frac {1}{4}}(16+2+4+2)}$.

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

D_n

Generalizzando ad n-vertici, q-colori, supponiamo che la fattorizzazione in numeri interi di ${\displaystyle n}$ sia:

${\displaystyle n=p_{1}^{k_{1}}\ p_{2}^{k_{2}}\ \cdots \ p_{r}^{k_{r}}\qquad \operatorname {D} =\ \left\{p_{1},p_{2},\ldots ,\ p_{r},\ n\right\}\quad |\operatorname {D} |=r+1}$

cioè, ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$ sono numeri primi distinti. Con D definiamo l'insieme dei divisori. Adesso richiamiamo la funzione totiente di Eulero

${\displaystyle \varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1)=\varphi (p_{1})\,\varphi (p_{2})\cdots \varphi (p_{r})=\prod _{i=1}^{r}\varphi (p_{i});\quad \varphi (p_{1})=\varphi (1)\,{\overset {def}{=}}\,1}$

da notare la definizione di ${\displaystyle \varphi (p_{1})}$. Quindi una permutazione di ordine ${\displaystyle p_{i}}$ ammette un numero ${\displaystyle n/p_{i}}$ di cicli ognuno di lunghezza ${\displaystyle p_{i}}$. Allora il gruppo ciclico delle sole rotazioni ${\displaystyle C_{n}}$ ammette il polinomio indice ciclico seguente:

${\displaystyle P_{G}(x_{1},\ x_{2},\cdots ,\ x_{n})={\frac {1}{n}}\left[\varphi (p_{1})x_{p_{1}}^{n/p_{1}}\ +\varphi (p_{2})x_{p_{2}}^{n/p_{2}}\ +\cdots +\varphi (p_{r})x_{p_{r}}^{n/p_{r}}\ +\varphi (n)x_{n}\right]={\frac {1}{n}}\left[\sum _{i=1}^{r}\varphi (p_{i})\ x_{p_{i}}^{n/p_{i}}\ +\varphi (n)x_{n}\right]}$.

Per esempio ${\displaystyle n=4=1^{k}\cdot 2^{2}\quad \forall k\in \mathbb {N} \;}$ ammette come divisori l'insieme ${\displaystyle \{p_{1}^{k_{1}},\ p_{2}^{k_{2}},\ p_{3}^{k_{3}}\}=\{1,\ 2,\ 2^{2}\}}$ e quindi il polinomio indice ciclico diventa:

${\displaystyle P_{G}(x_{1},\ x_{2},\ x_{3},\ x_{4})={\frac {1}{4}}\left[\varphi (1)x_{1}^{(4/1)}\ +\varphi (2)x_{2}^{(4/2)}\ +\varphi (2^{2})x_{4}\right]={\frac {1}{4}}\left[x_{1}^{4}\ +x_{2}^{2}\ +2x_{4}\right].}$

o nella forma generalizzata q-colori:

${\displaystyle P_{G}(q,\ q,\ q,\ q)={\frac {q^{4}\ +q^{2}\ +2q}{4}}.}$

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

${\displaystyle P_{G}(x_{1},\ x_{2},\cdots ,\ x_{n})={\frac {1}{2n}}\sum _{i=1}^{r}\varphi (p_{i})\ x_{p_{i}}^{n/p_{i}}\ +{\frac {1}{2n}}\varphi (n)x_{n}+{\begin{cases}{\frac {1}{2n}}n\ x_{1}x_{2}^{(n-1)/2},&n{\mbox{ dispari, }}\\{\frac {1}{2n}}{\frac {n}{2}}\left(x_{1}^{2}x_{2}^{(n-2)/2}+x_{2}^{n/2}\right),&n{\mbox{ pari.}}\end{cases}}}$

Ad esempio consideriamo una collana con 17 perle con due colori distinti. Equivale a considerare il gruppo diedrale ${\displaystyle D_{17}}$ 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:

${\displaystyle n=17=1\cdot 17\quad \varphi (17)=17^{1-1}\ (17-1)=16}$

per cui l'insieme dei divisori diventa ${\displaystyle \operatorname {D} \ =\ \{1,\ 17\}}$ ed otteniamo il polinomio

${\displaystyle P_{G}(x_{1},\ x_{2},\cdots ,\ x_{17})={\frac {1}{2\ 17}}\left[\varphi (1)\ x_{1}^{17/1}\ +\varphi (17)\ x_{17}+17\ x_{1}x_{2}^{(17-1)/2}\right]={\frac {x_{1}^{17}\ +16\ x_{17}\ +17\ x_{1}x_{2}^{8}}{34}}\,}$

essendo n dispari. Per ${\displaystyle n=17,q=2}$ si ottengono

${\displaystyle P_{G}(q,\ q,\cdots ,\ q)={\frac {q^{17}\ +17\ q^{9}\ +16\ q}{34}}={\frac {2^{17}\ +17\cdot 2^{9}\ +16\cdot 2}{34}}={\frac {2^{16}\ +17\cdot 2^{8}\ +16}{17}}={\frac {65536\ +4352\ +16}{17}}={\frac {69904}{17}}=4112}$

Postille