文章目錄

• 前言
• 群
• • 基本定義：
  • 子群
  • 陪集
  • 拉格朗日定理
  • 正規(guī)子群
  • 交換群
  • 商群
  • 階
• 置換
• • 定義
  • 置換的乘法
  • 循環(huán)
  • 置換群
  • 群作用
  • 等價(jià)類
  • 不動(dòng)點(diǎn)
• Burnside引理
• • 內(nèi)容
  • 證明
  • • 法1 軌道-穩(wěn)定子定理
    • 法2
• Polya 定理

所謂群論，就是對群體行為問題的討論。

（逃）

前言

個(gè)人學(xué)起來比較困難的一部分。
主要的難點(diǎn)在于抽象，常常會(huì)陷入虛空…
但當(dāng)發(fā)現(xiàn)理論推出來的花里胡哨的東西和事實(shí)相符時(shí)還是挺爽的。
行文中如果有錯(cuò)誤或者不嚴(yán)謹(jǐn)?shù)牡胤?#xff0c;歡迎指正，感謝。
沒怎么看懂但也許有用的網(wǎng)站

群

基本定義：

群是由非空集合 $G$ 和關(guān)于 $G$ 的二元運(yùn)算 $?$ 組成的代數(shù)結(jié)構(gòu)，滿足如下性質(zhì)：

封閉性。$a,b\in G?a?b\in G$

結(jié)合律。$(a?b)?c=a?(b?c)$

標(biāo)識元（單位元）。$G$ 中存在一個(gè)元素 $e$，使得 $?a\in G,a?e=e?a=a$，這樣的元素是獨(dú)一無二的。

逆元。$?a\in G,?b\in G,a?b=e$。此時(shí)稱 $b$ 為 $a^{?1}$。

子群

對于一個(gè)群 $(G,\times )$，若 $H$ 為 $G$ 的一個(gè)子集，且 $(H,\times )$ 也構(gòu)成一個(gè)群，則稱 $(H,\times )$ 為 $(G,\times )$ 的一個(gè)子群。記為 $H\le G$。
$G$ 和 $\{e\}$ 稱為 $G$ 的兩個(gè)平凡子群。
子群檢驗(yàn)法：$H\le G??h,g\in H,h?g^{?1}\in H$。

陪集

若 $H\le G,g\in G$，則稱 $Hg=\{h?g,h\in H\}$ 為 $H$ 在 $G$ 內(nèi)關(guān)于 $g$ 的右陪集（左陪集就是在左邊，同理）
陪集具有如下性質(zhì)：

$|Hg|=|H|$

因?yàn)閷τ?$h1,h2\in H,h1=h2$，都有 $g?h1=g?h2$。

$g\in Hg$

因?yàn)?$e\in H$。

$Hg=H?g\in H$

左往右：由于性質(zhì)二，$g\in Hg$；若 $g\in /H$，不可能有 $Hg=H$。
右往左：由于封閉性，$Hg$ 不可能取到 $H$ 之外的元素；對于 $?h1\in H$，設(shè) $h1?g^{?1}=h2\in H$。則有 $h1=h2?g$，所以 $h1\in Hg$。

$Ha=Hb?a?b^{?1}\in H$

左往右：因?yàn)?$?h1\in H,?h2\in H,h1?a=h2?b$，也就有 $a?b^{?1}=h2?h{1}^{?1}$，而 $h2?h{1}^{?1}\in H$。
右往左：$?h1\in H,h1?a\in Ha,?h2=h1?(a?b^{?1})\in H\to h1?a=h2?b,h2?b\in Hb$。（其實(shí)就是左往右反過來推）

$Ha\cap Hb=?\to Ha=Hb$

$Ha\cap Hb=?\to ?h1,h2\in H,h1?a=h2?b\to a?b^{?1}=h2?h{1}^{?1}\in H\to Ha=Hb$

$H$ 的所有右陪集的并集為 $G$。

由于封閉性，不可能取到 $G$ 之外的元素。
由于 $e\in H$，$g$ 取遍 $G$ 的所有元素就可以保證 $G$ 的所有元素都被取到。

拉格朗日定理

$H\le G?|H|$ 整除 $|G|$。

結(jié)合陪集的性質(zhì)即可得。由性質(zhì) $1,5,6$，$H$ 所有本質(zhì)不同的陪集互不相交，大小均為 $|H|$，共同組成了 $G$。$\frac{|G|}{|H|}$ 也就是 $H$ 本質(zhì)不同陪集的數(shù)量。

正規(guī)子群

若 $H\le G$，且 $?a\in G,aH=Ha$，則稱 $H$ 是 $G$ 的正規(guī)子群。平凡子群總是正規(guī)子群。

交換群

又稱為阿貝爾群，簡單說就是在滿足群基本性質(zhì)的基礎(chǔ)上，運(yùn)算又滿足交換律的群。
交換群的所有子群都是正規(guī)子群。

商群

設(shè) $H$ 是 $G$ 的正規(guī)子群，定義 $G/H=\{gH,g\in G\}$。
商群可以理解為一種劃分，由拉格朗日定理，$G/H$ 由 $\frac{|G|}{|H|}$ 個(gè)大小為 $|H|$，互不相交的群組成。

階

群 $G$ 中元素 $x$ 的階等于最小的正整數(shù) $d$，使得 $x^d=e$，有限群中元素的階一定存在。
有限群的階定義為群內(nèi)元素的個(gè)數(shù)，無限群的階規(guī)定為 $0$。
階的一些性質(zhì)：

群 $G$ 中元素 $x$ 的階整除 $G$ 的階。

構(gòu)造一個(gè) $G$ 的子群 $H=\{e,x,x^2,...,x^{d?1}\}$，$|H|=d$，由拉格朗日定理 $d$ 整除 $|G|$。

若 $G$ 中兩個(gè)元素 $a,b$ 的階 $m,n$ 互素，則 $a^s{b}^t=e?a^s=e\&b^t=e$。

由條件有 $a^s=b^{?t}$，同時(shí) $m$ 次方：$b^{?tm}=a^{sm}=(a^m{)}^s=e$，由于 $\gcd (m,n)=1$，就有 $b^{?t}=e$，即 $b^t=e$。$a^s=e$ 同理。

若 $g1,g2\in G$ 的階分別為 $d1,d2$，則存在一個(gè)元素 $g\in G$，其階為 $lcm(d1,d2)$。

設(shè) $\gcd (d1,d2)=d$?？紤]元素 $g{1}^d?g2$。其中 $g{1}^d$ 和 $g2$ 的階數(shù)互質(zhì)。由性質(zhì)二，$g{1}^d?g2$ 的階數(shù)就是 $\frac{d1}{d}\times d2=lcm(d1,d2)$。

置換

定義

有限集合到自身的雙射（即一一對應(yīng)）稱為置換。
可以表示為：$\left(\begin{array}{c}1,2,3,\dots ,n\\ a_1,a_2,a_3,\dots ,a_n\end{array}\right)$，表示把第 $a_i$ 個(gè)元素映射到位置 $i$。在第一行為 $1,2,3...$ 時(shí)，可以省去第一行。
置換 $f$ 作用與狀態(tài) $a$，寫作 $f?a$。（這個(gè)寫法似乎各處并不一樣）
例：
$$(3,2,1,4)?(a,b,c,d)=(c,b,a,d)$$

置換的乘法

定義 $f1?f2$ 表示先進(jìn)行 $f2$，再進(jìn)行 $f1$。
$(a_1,a_2,...,a_n)?(b_1,b_2,...,b_n)=(b_{a_1},b_{a_2},...,b_{a_n})$
例：
$$(3,2,1,4)?(2,1,3,4)=(3,1,2,4)$$

循環(huán)

如果一個(gè)置換形如 $\left(\begin{array}{c}{a}_1,a_2,a_3,...,a_{n?1},a_n\\ a_2,a_3,a_4,...,a_n,a_1\end{array}\right)$，則稱其為一個(gè)循環(huán)。
如果兩個(gè)循環(huán)不包含相同元素，則稱它們?yōu)?strong>不相交的。
任何置換都由若干個(gè)不相交置換的乘積。

置換群

元素個(gè)數(shù)為 $n$ 的所有排列的集合 $N$ 與置換乘法組成一個(gè)群 $(N,?)$。
其子群稱為置換群。
其中的單位元又叫做恒等置換 $I$。

群作用

對于一個(gè)群 $(G,?)$ 和集合 $N$，給出一個(gè)二元函數(shù) $\phi (g,n)$，滿足如下性質(zhì)：

$\phi (e,n)=n$

$\phi (a,\phi (b,n))=\phi (a?b,n)$

則稱群 $G$ 作用于集合 $N$。
（如果你沒明白這個(gè)定義想干什么，可以把 $G$ 想成置換群，把 $N$ 想成狀態(tài)）

等價(jià)類

若一個(gè)狀態(tài)可以通過置換群內(nèi)的某個(gè)置換到達(dá)另一個(gè)狀態(tài)，則稱它們屬于同一個(gè)等價(jià)類（也就是本質(zhì)相同）。

不動(dòng)點(diǎn)

若 $f?x=x$，則稱 $x$ 為 $f$ 的一個(gè)不動(dòng)點(diǎn)。

Burnside引理

重頭戲來勒！

內(nèi)容

對于作用于集合 $X$ 的群 $G$。
設(shè) $X/G$ 為在 $G$ 作用下等價(jià)類的集合。（這里雖然并不滿足商群的定義，但是寫成形式化語言后長的非常像，即 $\{Gx,x\in X\}$）
則有：
$$|X/G|=\frac{1}{|G|}\sum _{g\in G}|X^g|$$
其中 $X^g=\{x|g?x=x,x\in X\}$

證明

法1 軌道-穩(wěn)定子定理

對于一個(gè)置換群 $G$ 和狀態(tài) $x$，定義 $G(x)=\{g?x,g\in G\}$ 為 $x$ 的軌道（其實(shí)就是等價(jià)類），$G^x=\{g|g?x=x,g\in G\}$ 為 $x$ 的穩(wěn)定子（其實(shí)就是不動(dòng)點(diǎn)）。

軌道-穩(wěn)定子定理：$|G|=|G^x||G(x)|$

證明：
首先，$G^x$ 是一個(gè) $G$ 的子群，我們按照定義逐條驗(yàn)證：

封閉性：$f?x=x,g?x=x\to (f?g)?x=f?(g?x)=x$，即 $f\in G^x,g\in G^x\to f?g\in G^x$。

結(jié)合律：置換乘法本身始終有結(jié)合律。

單位元：顯然 $e?x=x$。

逆元：$f?x=x\to x=f^{?1}?x$

既然是子群，根據(jù)拉格朗日定理，就有：
$$|G|=|G^x||G:G^x|$$
其中 $|G:G^x|$ 表示 $G^x$ 在 $G$ 中本質(zhì)不同的陪集數(shù)量。
那么現(xiàn)在只需要證明 $|G:G^x|=|G(x)|$。

嘗試在 $G^x$ 的陪集和 $x$ 的軌道之間建立雙射關(guān)系。

若 $f?x=g?x$（兩個(gè)置換在 $x$ 軌道的同一位置），則有 $(g^{?1}?f)?x=x$，即 $g^{?1}?f\in G^x$，由前面陪集的性質(zhì)四，也就有 $f{G}^x=g{G}^x$。

若 $f{G}^x=g{G}^x$（兩個(gè)置換生成的陪集相同），由于第一條使用的均為充要條件，反過來推依然成立，也就有 $f?x=g?x$。

所以我們得到，如果軌道相同則陪集相同，如果陪集相同則軌道相同，建立起了雙射關(guān)系，命題得證。

有了軌道-穩(wěn)定子定理，證明 Burnside 引理就不難了。
$$\begin{gathered} \sum _{g\in G}{X}^g=\sum _{x\in X}{G}^x \\ =\sum _{x\in X}\frac{|G|}{|G(x)|} \\ =|G|\sum _{x\in X}\frac{1}{G(x)} \\ =|G|\sum _{Y\in X/G}\sum _{x\in Y}\frac{1}{|Y|} \\ =|G|\sum _{Y\in X/G}1 \\ =|G||X/G| \end{gathered}$$
得證。

法2

一本通上的魔法操作。
被中間一大堆莫名其妙啰哩啰嗦的過程以及橫空出世的“顯然”整蒙了好久
但看明白了確實(shí)還是挺優(yōu)雅的。

考慮一個(gè)大小為 $k$ 的等價(jià)類 $S$。
從里面任選一個(gè)狀態(tài) $a_1$。
那么設(shè) $g_1$ 為滿足 $g_1?a_1=a_1$ 的任意一個(gè)置換。（必然存在，至少可以是恒等置換 $I$）
那么對于 $S$ 中任意元素 $a_i$，設(shè) $f_i$ 為滿足 $f_i?a_1=a_i$ 的任意一個(gè)置換，那么 $W_i=\{g|g?a_1=a_i,g\in G\}$ 也就可以寫成 $\{f_i,f_i?g_1,f_i?g_1^2,...,f_i?g_1^{d?1}\}$，其中 $d$ 為 $g_1$ 的階數(shù)。
那么可以看出，所有的 $|W_i|$ 都是相等的，且由于 $W_i$ 必然互不相交，并集為全集，就有 $|W_1|=|W_2|=...=|W_k|=\frac{|G|}{k}$。
也就是說，對于 $S$ 中每個(gè)元素 $a_i$，$G^{a_i}=\{g|g?a_i=a_i,g\in G\}$ 的大小均為 $\frac{|G|}{k}$，$S$ 中一共有 $k$ 個(gè)元素，那么總共就貢獻(xiàn)了 $|G|$ 個(gè)不動(dòng)點(diǎn)。
每個(gè)等價(jià)類都貢獻(xiàn) $|G|$ 個(gè)不動(dòng)點(diǎn)，那么 Burnside 引理中的式子也就自然可得了。

Polya 定理

個(gè)人感覺 Polya 定理根本不配叫個(gè)定理
Burnside 給了我們計(jì)算本質(zhì)不同方案的公式：
$$|X/G|=\frac{1}{|G|}\sum _{g\in G}|X^g|$$
而 Polya 的用途就是快速計(jì)算 Burnside 的式子。
關(guān)鍵就是計(jì)算這個(gè) $|X^g|$。
以染色問題為例，假設(shè)每個(gè)點(diǎn)可以染 $m$ 中顏色，或者說，$a_{1...n}$ 都可以在 $[1,m]$ 中取值。
對于一個(gè)置換 $g$，設(shè)其循環(huán)的個(gè)數(shù)為 $c(g)$，要想成為不動(dòng)點(diǎn)，顯然每個(gè)循環(huán)的顏色必須相同，而不同循環(huán)的顏色相互獨(dú)立，因此不動(dòng)點(diǎn)個(gè)數(shù)為 $m^{c(g)}$。
那么 Burnside 的式子也就可以寫為：
$$|X/G|=\frac{1}{|G|}\sum _{g\in G}{m}^{c(g)}$$
然后嘞？
沒了。
沒了？
沒了！
Polya 就這？
Polya 就這！
你上你也行
個(gè)人實(shí)在感覺這個(gè)東西和 Burnside 引理放在一起是對 Burnside 的侮辱…
也可能是我對 Polya 的理解還不太到位吧。

總結(jié)

以上是生活随笔為你收集整理的群论学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。