群论

· · 个人记录

群论

群的一系列定义及性质

群

定义集合G与作用与G的运算\oplus

若满足以下四个性质，则称其为一个群(G,\oplus)

注意，群不具有交换律a \in G,b \in G,a \oplus b= b \oplus a是不成立的

子群

存在集合H \in G，且(H,\oplus)构成群

则(H,\oplus)是(G,\oplus)的子群

记为 H \le G

陪集

对于子群H \le G

对于某一个g \in G,称\{g \oplus h,h \in H\}为H的一个左陪集，记作gH

对于某一个g \in G,称\{h \oplus g,h \in H\}为H的一个右陪集，记作Hg

陪集的性质

仅讨论左陪集，右陪集同理

证明，注意到逆元唯一，所以对\forall h_1 \not= h_2 \in H,h_1 \oplus g \not= h_2 \oplus g

证明，注意到H是个群，具有单位元，所以e\in H,g=e \oplus g \in Hg

证明，显然

证明，Hab^{-1} = Hbb^{-1} = H,所以a \oplus b^{-1} \in H

证明，若有c \in Ha \cap Hb，则有h_1,h_2 \in H,h_1 \oplus a=c,h_2 \oplus b=c，所以h_1 \oplus a =h_2 \oplus b,a \oplus b^{-1}=h_2 \oplus h_1^{-1}，a \oplus b^{-1} \in H,Ha=Hb

意味着一个子群 H 的陪集的交集要么是空要么两个相等

一些表示:

$[G:H]$表示$H$的不同陪集的数量 ## 拉格朗日定理 对于有限群$G$,有$H \le G$，则 $$ |H|*[G:H]=|G| $$ 不证了，看着挺对的 ## 置换的一系列定义及性质 一个置换$\sigma = (a_1,a_2 \cdots a_n)$表示用第$a_i$个元素替换第$i$个元素 **运算：**先做置换$\sigma_1$,再做置换$\sigma_2$,记为$\sigma_1 \oplus \sigma_2

置换群

不妨令集合 N = \{1,2,3 \cdots n\} ，令集合 M为 N 的若干个排列构成的集合，\oplus为置换的运算，我们令群 G=(M,\oplus)，则称其为置换群

群作用

对于一个集合M与一个置换群G

若给定的二元函数\mu(g,m)，g \in G,m \in M满足

则称置换群G作用于集合M

轨道-稳定子定理

轨道

考虑一个作用在X上的群G，X中的元素x的轨道就是x通过G中的置换可以转移到的元素的集合

记为G(x)，同时，为了方便，\mu(g,x)记为g(x)

稳定子

一个元素x的稳定子被定义为G^x=\{g|g \in G ,g(x)=x\}

人话就是，对于元素x，置换群G中满足g(x)=x的置换的集合

轨道-稳定子定理

对于置换群G作用与集合X，有集合X中的一个元素x，

|G^x|*|G(x)|=|G|

首先，证明G^x \le G，（G^x是G的子群）

所以G^x是G的子群

根据拉格朗日定理，

|G^x|*[G:G^x]=|G|

对于f \in G^x,g \in G^x因为f(x)=g(x)=x，

所以f \oplus g^{-1}(x)=x,f \oplus g^{-1} \in G^x

由于陪集的性质，fG^x=gG^x

所以相同的g(x)对应相同的陪集

所以|G(x)|=[G:G^x]

Burnside定理

置换群G作用于集合X，如果x,y \in X在G的作用下可以相等，即存在f \in G,f(x)=y，则定义x,y属于一个等价类，则不同等价类的数量|X/G|为：

|X/G|=\frac{1}{|G|} \sum_{g \in G}X^g 证明： 由于每个元素属于仅属于一个轨道，轨道内部在群 $G$作用下互达，(陪集性质) 所以我们可以得到 $$ |X/G|=\sum_{x \in X}\frac{1}{[G:G^x]} $$ (就是以前按$g$分在一起，现在按$x$分在一起)，得证 所以根据轨道-稳定子定理可推知 $$ |X/G|=\frac{1}{|G|}\sum_{x \in X}G^x $$ ## Polya引理 在一般的染色问题/类似的问题求本质不同的xxx的问题当中，我们往往是在求不动点的数量 对于一个置换$g$，我们从$i$向$a_i$连边，这样会构成若干环，记作$c(g)

那么有m种可用颜色的本质不同的染色方法就是

\frac{1}{|G|}\sum_{g \in G} m^{c(g)}

就这样