Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

「学习笔记」群在集合上的作用及 Burnside 引理

posted on 2022-02-09 22:27:25 | under 学习笔记 |

注:下文若未特殊说明,默认 $G$ 是一个群,$\Sigma$ 是一个集合。

置换表示

$G$ 到 $S(\Sigma)$ 的同态 $f:G\longrightarrow S(\Sigma)$ 称为 $G$ 在 $\Sigma$ 上的一个置换表示。对于每个 $g\in G$,$f(g)$ 是 $\Sigma$ 上的置换。群 $G$ 借助置换作用在集合 $\Sigma$ 上,我们定义这样的作用是 $G\times\Sigma$ 到 $\Sigma$ 的映射 $\circ$,由 $g\circ a=f(g)(a)$ 给出。

若 $f$ 是单同态,则称 $f$ 是忠实的

G-轨道

设 $\pi:G\longrightarrow S(\Sigma)$ 是置换表示,对于 $\Sigma$ 中的元素 $a,b$,若存在 $g\in G$,使得 $g\circ a=b$,则称 $a\sim b$。

定理 $\sim$ 是 $\Sigma$ 上的等价关系。

证明:因为 $\pi$ 是同态,所以 $\pi(1_G)=1_{\Sigma}$,因此 $1_G\circ a=a$,从而 $a\sim a$。

若 $a\sim b$,则存在 $g\in G$,使得 $g\circ a=b$,即 $\pi(g)(a)=b$,故 $a=\pi(g)^{-1}b=\pi(g^{-1})b$,所以 $b\sim a$。

若 $a\sim b$ 且 $b\sim c$,则存在 $g_1,g_2\in G$,使得 $g_1\circ a=b,g_2\circ b=c$,故 $(g_2g_1)\circ a=g_2\circ(g_1\circ a)=g_2\circ b=c$,即 $a\sim c$。

综上,$\sim$ 满足自反性,对称性和传递性,因此 $\sim$ 是 $\Sigma$ 上的等价关系。证毕。

因为 $\sim$ 是 $\Sigma$ 上的等价关系,所以它给出了 $\Sigma$ 的一个划分。记 $a$ 所在的等价类为 $G^a:=\{g\circ a|g\in G\}$。$G^a$ 称为一个 $G-$轨道

若 $\Sigma$ 在 $G$ 的作用下只存在一个轨道,则称 $G$ 在 $\Sigma$ 上的作用是传递的。

不动点与稳定核

设 $\pi:G\longrightarrow S(\Sigma)$ 是置换表示。

对于每个 $g\in G$,我们关注在置换 $\pi(g)$ 下保持不变的元素,这些元素的集合记为 $C(g)$,称之为 $g$ 下的不动点,即$$C(g):=\{a\in \Sigma|g\circ a=a\}$$ 对于每个 $a\in G$,我们关注使 $a$ 保持不变的置换 $\pi(g)$,这些群元的集合即为 $G(a)$,称之为 $a$ 的稳定核,即$$G(a):=\{g\in G|g\circ a=a\}$$$C(g)$ 与 $G(a)$ 满足等式$$\sum_{g\in G}C(g)=\sum_{a\in \Sigma} G(a)$$ 证明:考虑计数满足 $g\circ a=a$ 的二元组 $(g,a)$ 的数量 $t$。

枚举 $g$,计算合法的 $a$,有$$t=\sum_{g\in G}C(g)$$ 枚举 $a$,计算合法的 $g$,有$$t=\sum_{a\in \Sigma} G(a)$$ 联立两式可知证毕。

轨道稳定子定理

若 $G$ 为有限群,对于任意 $a\in \Sigma$,都有$$|G^a||G(a)|=|G|$$ 这一结论称为轨道稳定子定理

证明:先证 $G(a)$ 是 $G$ 的子群。

若 $g_1,g_2\in G(a)$,则 $(g_1g_2)\circ a=g_1\circ (g_2\circ a)=g_1\circ a=a$,所以 $g_1g_2\in G(a)$。

若 $g_1\in G(a)$,则 $g_1\circ a=a$,即 $\pi(g)\circ a=a$,所以 $g^{-1}\circ a=\pi(g^{-1})(a)=\pi(g)^{-1}(a)=a$,从而 $g^{-1}\in G(a)$。

根据子群判定定理可知 $G(a)\le G$。

因此 $G$ 有陪集分解$$G=\bigcup_{i=1}^ng_iG(a)$$ 其中 $n=[G:G(a)]$。

令 $a_i=g_i\circ a$,则对于任意 $g\in G$,存在唯一的 $1\le i\le n$,使得 $g\in g_iG(a)$,设 $g=g_ih$,其中 $h\in G(a)$,则 $g\circ a=(g_ih)\circ a=g_i\circ(h\circ a)=g_i\circ a=a_i$。

令 $a_i=a_j$,则 $g_i\circ a=g_j\circ a$,则 $g_i^{-1}g_j\in G(a)$,则 $g_j\in g_iG(a)$,则 $i=j$。因此 $a_1,a_2,\cdots,a_n$ 两两不同。

综上,$G^a=\{a_1,a_2,\cdots,a_n\}$,从而$$|G^a|=n=[G:G(a)]=\frac{|G|}{|G(a)|}$$ 移向可得 $|G^a||G(a)|=|G|$。

Burnside 引理

接下来我们考虑一个重要的计数问题,如何求出 $\Sigma$ 在 $G$ 下的等价类个数?

我们将贡献分配 $\Sigma$ 的每一个元素上,且令每个等价类的贡献之和恰好为 1,一种自然且可行的分配方案为:对于某个元素 $a$,令它的贡献为 $1/|G^a|$。

所以我们有$$|G/\Sigma|=\sum_{a\in \Sigma}\frac{1}{|G^a|}$$ 根据轨道稳定子定理,又有$$|G/\Sigma|=\sum_{a\in \Sigma}\frac{|G(a)|}{|G|}=\frac{1}{|G|}\sum_{a\in \Sigma}|G(a)|$$ 再根据稳定核与不动点的关系,可得$$|G/\Sigma|=\frac{1}{|G|}\sum_{g\in G}|C(g)|$$ 这便是 Burnside 引理。