3.2. Bổ đề Burnside¶

Các trạng thái khác nhau của tập hợp $M$ là tương đương nhau nếu chúng nằm trong cùng lớp tương đương dưới tác động của nhóm $G$.

Các ví dụ về bổ đề Burnside và định lý Polya được tham khảo tại [6].

Bổ đề 3.1 (Bổ đề Burnside)

Với nhóm $G$ tác động lên tập hợp $M$, ta có:

\[t_G = \frac{1}{\lvert G \rvert} \sum_{g \in G} \lvert M^g \rvert,\]

trong đó:

$t_G$ là số lớp tương đương của tập $M$ dưới tác động của nhóm $G$;
$\lvert M^g \rvert$ là số điểm bất động của tập $M$ dưới tác động của phần tử $g$, nghĩa là $M^g = \{ m \in M : gm = m\}$.

Chứng minh

Xét tập hợp

\[S = \{ (g, m) \in G \times M : g m = m \}.\]

Ta đếm số phần tử của $S$ theo hai cách.

Cách 1: đếm theo từng phần tử $g in G$.

Với mỗi phần tử $g$, số phần tử $m \in M$ cố định dưới tác động của $g$ là $\lvert M^g \rvert$. Khi đó lấy tổng các phần tử $g$ lại ta được

\[\lvert S \rvert = \sum_{g \in G} \lvert M^g \rvert.\]

Cách 2: đếm theo từng phần tử $m in M$.

Với mỗi $m$, stabilizer

\[G_m = \{ g \in G : g m = m \}\]

có số phần tử là $\lvert G_m \rvert$. Khi đó

\[\lvert S \rvert = \sum_{m \in M} \lvert G_m \rvert.\]

Ở trên mình đã nói về một công thức là

\[\lvert G \rvert = \lvert G(m) \rvert \cdot \lvert G_m \rvert,\]

tương đương với $\lvert G_m \rvert = \dfrac{\lvert G \rvert}{\lvert G(m) \rvert}$.

Giả sử $M$ có $n$ orbit là $G(m_1)$, $G(m_2)$, ..., $G(m_n)$. Với mỗi orbit $G(m_i)$ thì mọi $m \in G(m_i)$ có cùng kích thước $\lvert G_m \rvert$. Khi đó

\[\sum_{m \in G(m_i)} \lvert G_m \rvert = \sum_{m \in G(m_i)} \dfrac{\lvert G \rvert}{\lvert G(m_i) \rvert} = \lvert G \rvert.\]

Cộng tất cả quỹ đạo lại ta có

\[\sum_{m \in M} \lvert G_m \rvert = \underbrace{\lvert G \rvert + \cdots + \lvert G \rvert}_{n \ \text{lần}} = n \cdot \lvert G \rvert.\]

Kết hợp hai cách đếm suy ra

\[\sum_{g \in G} \lvert M^g \rvert = \sum_{m \in M} \lvert G_m \rvert = n \cdot \lvert G \rvert,\]

tương đương với

\[n = \dfrac{1}{\lvert G \rvert} \sum_{g \in G} \lvert M^g \rvert.\]

Ở đây $n = t_G$ và ta có điểm phải chứng minh.

3.2.1. Bài toán tô màu bốn đỉnh tứ diện¶

Cho hình tứ diện đều. Ta tô bốn đỉnh của nó bằng ba màu xanh, đỏ, vàng. Hỏi có bao nhiêu cách tô như vậy?

Ta cần lưu ý một điều, hai cách tô là tương đương nhau (giống nhau) nếu tồn tại một phép quay các đỉnh biến cách tô này thành cách tô kia (ví dụ như hình 3.2 và hình 3.3).

../../_images/tetrahedron-1.jpg — Hình 3.2 Cách tô 1¶

../../_images/tetrahedron-2.jpg — Hình 3.3 Cách tô 2¶

Như hình trên ta thấy nếu chọn trục quay là đường thẳng nối trung điểm hai cạnh đối diện (hai điểm xanh lá) thì đỉnh trên và đỉnh dưới đổi chỗ cho nhau (xanh và vàng), đỉnh trái và đỉnh phải đổi chỗ cho nhau (xanh và đỏ).

Ta giải bài này như sau:

Đầu tiên ta đánh số các đỉnh của tứ diện như hình 3.4.

../../_images/tetrahedron-3.jpg — Hình 3.4 Đánh số các đỉnh tứ diện¶

Ta có ba trường hợp biến đổi sau:

Trường hợp 1. Giữ nguyên một đỉnh và trục quay là đường thẳng đi qua đỉnh đó và tâm của mặt đối diện.

../../_images/tetrahedron-4.jpg — Hình 3.5 Trường hợp 1¶

Khi đó phép quay (ngược chiều đồng hồ) tương ứng hoán vị $(1)(2,3,4)$ (quay $60$ độ) và $(1)(2,4,3)$ (quay $120$ độ).

Do ta chọn một đỉnh cố định thì ta có $4$ cách chọn, và với mỗi cách chọn đỉnh cố định ta có thể quay hai cách nên ta có tổng là $8$ hoán vị.

Trường hợp 2. Ta chọn trung điểm hai cạnh đối nhau và nối lại thành trục quay như hình trong ví dụ. Khi đó tương ứng với hoán vị $(1,4)(2,3)$.

../../_images/tetrahedron-5.jpg — Hình 3.6 Trường hợp 2¶

Ta có $\dfrac{C^2_4}{2!} = 3$ hoán vị.

Trường hợp 3. Hoán vị đồng nhất $(1)(2)(3)(4)$.

Tóm lại, tập hợp $M$ ở đây là tập hợp $4$ đỉnh của tứ diện, và nhóm tác động lên $M$ là nhóm con $12$ phần tử của $\mathcal{S}_4$.

Như vậy, ví dụ với hoán vị $(1)(2,3,4)$, nếu ta muốn sau phép quay giữ nguyên trạng thái (hay nói cách khác là tìm $M^g$) thì ta tô màu đỉnh $1$ tùy ý, các đỉnh $2-3-4$ chung màu (cũng tùy ý).

Suy ra ta có $3 \cdot 3$ cách tô. Tương tự với các hoán vị dạng $(1,4)(2,3)$.

Như vậy có tất cả

\[t_G = \dfrac{1}{12}(1 \cdot 3^4 + 8 \cdot 3^2 + 3 \cdot 3^2) = 15\]

cách tô màu khác nhau.

Tổng quát, nếu có $k$ màu thì số lớp tương đương là

\[t_G = \dfrac{1}{12}\left(1 \cdot k^4 + 8 \cdot k^2 + 3 \cdot k^2\right) = \dfrac{1}{12}(k^4 + 11 k^2).\]

3.2.2. Tác động nhóm lên vector¶

Xét nhóm $G$ và không gian vector $\mathbb{F}_2^n$, $n \in \mathbb{N}$. Khi đó hai vector $\bm{x}$ và $\bm{y}$ thuộc $\mathbb{F}_2^n$ được gọi là quan hệ với nhau nếu tồn tại $g \in G$ mà $\bm{x} = g \bm{y}$.

Ví dụ, xét nhóm hoán vị $\mathcal{S}_3$. Giả sử các vector trong $\mathbb{F}_2^3$ có dạng

\[\bm{x} = (x_1, x_2, x_3) \in \mathbb{F}_2^3.\]

Khi đó vector $(1, 0, 0)$ có quan hệ với $(0, 0, 1)$ với hoán vị $(1, 3)(2)$. Cụ thể là $(x_1, x_2, x_3) \xrightarrow{(1, 3)(2)} (x_3, x_2, x_1)$.

Tương tự, vector $(1, 0, 0)$ cũng có quan hệ với $(0, 1, 0)$ với hoán vị $(1, 2)(3)$.

Thêm nữa, vector $(1, 0, 0)$ có quan hệ với chính nó qua hoán vị đồng nhất $(1)(2)(3)$.

Câu hỏi đặt ra là, có bao nhiêu lớp tương đương dưới tác động của nhóm $\mathcal{S}_3$?

Để giải quyết vấn đề này ta sử dụng bổ đề Burnside.

Nhóm $\mathcal{S}_3$ có các hoán vị

\[\mathcal{S}_3 = \{ (1)(2)(3), (1, 2)(3), (1, 3)(2), (2, 3)(1), (1, 3, 2), (1, 2, 3) \}.\]

Lần lượt xét từng hoán vị. Đầu tiên, với $(1)(2)(3)$ thì các phần tử trong vector đứng yên. Do đó dưới tác động của hoán vị này, $x_1$ biến thành $x_1$, $x_2$ biến thành $x_2$ và $x_3$ biến thành $x_3$. Số cách chọn cho mỗi $x_i$ là $2$ nên theo quy tắc nhân ta có $2^3 = 8$ cách.

Tiếp theo, với hoán vị $(1, 2)(3)$ thì $x_1 \to x_2$, $x_2 \to x_1$ và $x_3 \to x_3$. Do đó $x_1$ và $x_2$ có cùng giá trị (nằm cùng chu trình), thành ra có $2$ cách chọn, $x_3$ cũng có $2$ cách chọn nên tổng số cách là $2 \cdot 2 = 4$. Hoán vị $(1, 3)(2)$ và $(2, 3)(1)$ tương tự.

Với hoán vị $(1, 2, 3)$ thì $x_1 \to x_2$, $x_2 \to x_3$ và $x_3 \to x_1$ nên $x_1 = x_2 = x_3$, có $2$ cách chọn trong trường hợp này. Hoán vị $(1, 3, 2)$ tương tự.

Như vậy, theo bổ đề Burnside, số lớp tương đương các vector trong $\mathbb{F}_2^3$ là

\[t(\mathcal{S}_3) = \frac{1}{6} (1 \cdot 2^3 + 3 \cdot 2^2 + 2 \cdot 2) = 4.\]

Thật vậy, ta có thể chia các vector thành $4$ lớp tương đương là

\[\{ 000 \}, \{ 001, 010, 011 \}, \{ 011, 101, 110 \}, \{ 111 \}.\]

Ngoài nhóm $\mathcal{S}_3$ ra còn các nhóm khác cũng tác động lên các vector. Một số nhóm hay được sử dụng là:

Nhóm general linear: gồm các ma trận khả nghịch $n \times n$ trên $\mathbb{F}_2$. Tác động nhóm lúc này là phép nhân ma trận $\bm{A} \in \mathrm{GL} (n, 2)$ với vector $\bm{x} \in \mathbb{F}_2^n$, hay $\bm{A} \cdot \bm{x}$.
Nhóm general affine: gồm các ma trận khả nghịch $n \times n$ trên $\mathbb{F}_2$ và vector bất kì trong $\mathbb{F}_2^n$. Tác động nhóm lúc này là biến đổi affine $\bm{A} \cdot \bm{x} + \bm{b}$ với $\bm{A} \in \mathrm{GL} (n, 2)$ và $\bm{b} \in \mathbb{F}_2^n$.

Nhận xét 3.5

Số lượng phần tử của nhóm $\mathrm{GL} (n, 2)$ là

\[(2^n - 1) \cdot (2^n - 2) \cdots (2^n - 2^{n-1}).\]

Ví dụ, khi $n = 3$ thì

\[\lvert \mathrm{GL}(3, 2) \rvert = (2^3 - 1) \cdot (2^3 - 2) \cdot (2^3 - 4) = 168\]

ma trận.

3.2.3. Tác động nhóm lên hàm boolean¶

Ta tiếp tục xét nhóm $G$ và không gian vector $\mathbb{F}_2^n$, $n \in \mathbb{N}$. Khi đó hai hàm boolean $n$ biến $f(x_1, \ldots, x_n)$ và $g(x_1, \ldots, x_n)$ được gọi là quan hệ với nhau nếu tồn tại $\tilde{g} \in G$ mà $g(\bm{x}) = f(\tilde{g} \bm{x})$ với mọi $\bm{x} \in \mathbb{F}_2^n$.

Ta cũng xét hoán vị $\mathcal{S}_3$ làm ví dụ. Ta cũng lần lượt xét các phần tử của nhóm.

Đặt $f_0$, $f_1$, ..., $f_7$ lần lượt là các giá trị hàm $f$ với các vector $\bm{x} \in \mathbb{F}_2^3$.

Đầu tiên, với $(1)(2)(3)$, ta có bảng chuyển vector như hình 3.7.

../../_images/burnside-1.jpg — Hình 3.7 Hoán vị $(1)(2)(3)$¶

Ta thấy rằng $f_0 \to f_0$, $f_1 \to f_1$, ..., $f_7 \to f_7$ nên có $8$ chu trình. Vậy số lượng cách chọn là $2^8$.

Tiếp theo, xét các hoán vị dạng $(1)(2, 3)$, ta có bảng chuyển vector như hình 3.8.

../../_images/burnside-2.jpg — Hình 3.8 Hoán vị $(1)(2, 3)$¶

Ta thấy rằng $f_0 \to f_0$, $f_1 \to f_2 \to f_1$, $f_3 \to f_3$, $f_4 \to f_4$, $f_5 \to f_6 \to f_5$, $f_7 \to f_7$. Ở đây có $6$ chu trình nên số cách chọn là $2^6$.

Tiếp theo ta xét các hoán vị dạng $(1, 2, 3)$ (Hình 3.9).

../../_images/burnside-3.jpg — Hình 3.9 Hoán vị $(1, 2, 3)$¶

Ta thấy rằng $f_0 \to f_0$, $f_1 \to f_2 \to f_4 \to f_1$, $f_3 \to f_6 \to f_5 \to f_3$, $f_7 \to f_7$ nên ở đây có $4$ chu trình. Số cách chọn là $2^4$.

Như vậy theo bổ đề Burnside, số lớp hàm bool tương đương dưới tác động của nhóm $\mathcal{S}_3$ là

\[t (\mathcal{S}_3) = \dfrac{1}{6}(2^8 + 3 \cdot 2^6 + 2 \cdot 2^4) = 80.\]

3.2.4. Định lý Polya¶

Với mỗi hoán vị trong tập $G$, ta viết dưới dạng các chu trình độc lập

\[\underbrace{(g_1) (g_2) \ldots (g_{t_{1}})}_{t_1} \underbrace{(g_{j_1} g_{j_2}) (g_{j_3} g_{j_4})}_{t_2} \ldots\]

Nếu ta viết hoán vị dưới dạng các chu trình rời nhau, ta gọi

Kí hiệu	Ý nghĩa
$t_1$	số chu trình có độ dài $1$
$t_2$	số chu trình có độ dài $2$
...	tương tự
$t_n$	số chu trình có độ dài $n$

Khi đó, cycle index (hay chỉ số chu trình) của hoán vị ứng các biến $z_1$, $z_2$, ..., $z_n$ là

\[I_g (z_1, z_2, ,\ldots, z_n) = z_1^{t_1} z_2^{t_2} \cdots z_n^{t_n}.\]

Ví dụ 3.6

Xét hoán vị $(1,2,3)(4)(5)(6,7) \in \mathcal{S}_7$.

Ta có hai chu trình độ dài $1$, một chu trình độ dài $2$ và một chu trình độ dài $3$ và không có chu trình độ dài $4$, $5$, $6$, $7$.

Do đó chỉ số chu trình là

\[I_g (z_1, z_2, z_3) = z_1^2 z_2^1 z_3^1.\]

Nhận xét 3.6

Bất kì hoán vị nào thuộc $\mathcal{S}_n$ đều thỏa

\[1 \cdot t_1 + 2 \cdot t_2 + \ldots + n \cdot t_n = n.\]

Định nghĩa 3.4 (Cyclic index, chỉ số chu trình)

Chỉ số chu trình của nhóm $G$ là:

\[P_G (z_1, z_2, \ldots, z_n) = \frac{1}{G}\sum_{g \in G} I_g (z_1, z_2, \ldots, z_n).\]

Nhìn lại ví dụ về tứ diện bên trên, các đỉnh nằm trong cùng chu trình cần được tô cùng màu. Từ đó ta có chỉ số chu trình

\[P_G(z_1, z_2, z_3) = \frac{1}{12}\left(z_1^4 + 8 z_1 z_3 + 3 z_2^2\right).\]

Cho mỗi $z_i = 3$ ta có kết quả phép tính theo bổ đề Burnside.

Định lý Polya là một mở rộng cho bổ đề Burnside, cho phép chúng ta đếm số lớp tương đương thỏa mãn điều kiện nhất định (về số lượng phần tử).

Ví dụ với hình tứ diện như trên nhưng ta thêm điều kiện tô hai đỉnh màu vàng, một đỉnh màu đỏ và một đỉnh màu xanh.

Ta kí hiệu tập $R$ là tập hợp các trạng thái có thể nhận của mỗi phần tử $m \in M$.

\[R = \{r_1, r_2, \ldots, r_c \}.\]

Ở ví dụ trên thì $R = \{\text{đỏ}, \text{xanh}, \text{vàng}\}$.

Ta thay mỗi $z_i$ trong chỉ số chu trình bằng tổng $\sum\limits_{r \in R} r^i$.

Ví dụ 3.7

Giả sử ta tô màu bốn đỉnh tứ diện với hai màu $R = \{r_1, r_2\}$.

Với $z_1$ ta thay bằng $r_1 + r_2$.

Với $z_2$ ta thay bằng $r_1^2 + r_2^2$.

Với $z_3$ ta thay bằng $r_1^3 + r_2^3$.

Khi đó $P_G$ tương đương với

\[\frac{1}{12}\left[ (r_1 + r_2)^4 + 8 \cdot (r_1 + r_2)(r_1^3 + r_2^3) + 3 \cdot (r_1^2 + r_2^2)^2 \right].\]

Ta khai triển $P_G$ (lưu ý là ở đây không có tính giao hoán phép nhân).

\[\begin{split}(r_1 + r_2)^4 = & r_1 r_1 r_1 r_1 + r_1 r_1 r_1 r_2 + r_1 r_1 r_2 r_1 + r_1 r_1 r_2 r_2 \\ + & r_1 r_2 r_1 r_1 + r_1 r_2 r_1 r_2 + r_1 r_2 r_2 r_1 + r_1 r_2 r_2 r_2 \\ + & r_2 r_1 r_1 r_1 + r_2 r_1 r_1 r_2 + r_2 r_1 r_2 r_1 + r_2 r_1 r_2 r_2 \\ + & r_2 r_2 r_1 r_1 + r_2 r_2 r_1 r_2 + r_2 r_2 r_2 r_1 + r_2 r_2 r_2 r_2.\end{split}\]

Mình thấy rằng có $16$ cấu hình khác nhau tương ứng $16$ cách tô hai màu cho bốn đỉnh. Tương tự

\[\begin{split}(r_1 + r_2) (r_1^3 + r_2^3) & = r_1^4 + r_1 r_2^3 + r_2 r_1^3 + r_2^4 \\ & = r_1 r_1 r_1 r_1 + r_1 r_2 r_2 r_2 + r_2 r_1 r_1 r_1 + r_2 r_2 r_2 r_2.\end{split}\]

Cuối cùng là

\[\begin{split}(r_1^2 + r_2^2)^2 & = r_1^4 + r_1^2 r_2^2 + r_2^2 r_1^2 + r_2^4 \\ & = r_1 r_1 r_1 r_1 + r_1 r_1 r_2 r_2 + r_2 r_2 r_1 r_1 + r_2 r_2 r_2 r_2.\end{split}\]

Việc không có tính giao hoán với phép nhân làm biểu thức cồng kềnh và phức tạp.

Do đó mình thêm một tập hợp $W$ là vành giao hoán, và xét ánh xạ $w: R \mapsto W$ với:math:w(r_i) = w_i.

Khi đó nếu thay $r_i$ bởi $w_i$ vào bên trên biểu thức sẽ rất đẹp:

\[P_G(w_1, w_2) = \frac{1}{12} \left[(w_1 + w_2)^4 + 8 (w_1 + w_2) (w_1^3 + w_2^3) + 3 (w_1^2 + w_2^2)^2\right].\]

Khai triển và thu gọn ta có

\[\begin{split}P_G(w_1, w_2) & = \frac{1}{12} \left[12 w_1^4 + 12 w_1^3 w_2 + 12 w_1^2 w_2^2 + 12 w_1 w_2^3 + 12 w_2^4\right] \\ & = w_1^4 + w_1^3 w_2 + w_1^2 w_2^2 + w_1 w_2^3 + w_2^4.\end{split}\]

Ở đây, định lý Polya nói rằng, số mũ của $w_i$ thể hiện số lượng phần tử của tập $M$ nhận giá trị $r_i$, và hệ số trước mỗi toán hạng là số lớp tương đương tương ứng với số lượng phần tử của tập $M$ nhận các giá trị $r_i$.

Nói cách khác:

có $1$ lớp tương đương mà $4$ đỉnh nhận màu $r_1$;
có $1$ lớp tương đương mà $3$ đỉnh nhận màu $r_1$ và $1$ đỉnh nhận màu $r_2$;
có $1$ lớp tương đương mà $2$ đỉnh nhận màu $r_1$ và $2$ đỉnh nhận màu $r_2$;
có $1$ lớp tương đương mà $1$ đỉnh nhận màu $r_1$ và $3$ đỉnh nhận màu $r_2$;
có $1$ lớp tương đương mà $4$ đỉnh nhận màu $r_2$.

Quay lại vấn đề tô bốn đỉnh tứ diện với ba màu xanh, đỏ, vàng. Tìm số cách tô hai đỉnh màu vàng, một đỉnh màu đỏ và một đỉnh màu xanh.

Đặt

\[w(\text{vàng}) = x, w(\text{đỏ}) = y, w(\text{xanh}) = z.\]

Ta có:

\[P_G = \frac{1}{12} \left[(x + y + z)^4 + 8 \cdot (x + y + z) (x^3 + y^3 + z^3) + 3 \cdot (x^2 + y^2 + z^2)^2\right].\]

Như vậy đề bài tương ứng việc tìm hệ số của hạng tử $x^2 yz$ trong biểu thức trên. Kết quả là $1$.

Kí hiệu	Ý nghĩa
\(t_1\)	số chu trình có độ dài \(1\)
\(t_2\)	số chu trình có độ dài \(2\)
...	tương tự
\(t_n\)	số chu trình có độ dài \(n\)