群论 Day 3 群作用
Published:
群作用
考虑二面体群 $\mathbb D_n$。群中的每个元素都是一个“操作”（旋转或翻转），而二面体上的每一个顶点经过“操作”后会被映射到一个新的顶点，且所有顶点经过同一操作后变成了原来排列的一个置换。
在这个情境中，我们讨论了两类对象：一类是“操作”，都被包含在群 $\mathbb D_n$ 中；一类是二面体的顶点，它们组成另一个集合。
抽象化这个情境：对于一个群 $(G, *)$ 和一个集合 $X$，我们将 $G$ 的每一个元素 $g$ 看成一个函数 $\sigma_g: X \to X$，所有的 $\sigma$ 构成群且该群的乘法正好对应函数的复合（构成同态）：
\[\sigma_g(\sigma_h(x)) = \sigma_{g * h}(x)\]即（此处 $\circ$ 表示函数复合）：
\[\sigma_g \circ \sigma_h = \sigma_{g * h}\]此处的映射 $g \mapsto \sigma_g$ 称为（左）作用，感性理解就是群中的抽象的元素是怎么被视为一个具体的变换的。
TODO: 例子
置换群
由于 $\sigma$ 可以求逆，$\sigma$ 必须是一个双射，由于 $\sigma: X \to X$ 中定义域和值域是同一个集合，$\sigma$ 是一个置换（Permuation）。
$X$ 的所有置换显然形成群（证明略去），称为 $X$ 的置换群（Permutation group），记作 $\operatorname{Sym}(X)$。群 $G$ 的作用将其所有元素映射到 $X$ 的置换群的一个子群。
Cayley 定理
若我们取 $X = G$ 和 $\sigma_g(h) = g * h$，我们就得到了 $G$ 同构于 $\operatorname{Sym}(G)$ 的一个子群。这一结论被称为 Cayley 定理。
想法：用群作用描述对称性
对于集合 $X$ 和群 $G$，如果有一个 $X$ 上的函数 $\Phi$ 使得
\[\forall x \in X, g \in G, \Phi(\sigma_g(x)) = \Phi(x)\]即任意群元素 $g$ 作用在任意元素 $x$ 上都不改变 $\Phi$ 的值，则称 $\Phi$ 为不变量，称 $G$ 为对称性。
例子
TODO: 先有不变量还是现有对称性？
例 1：令 $X = \mathbb R^2$，$G$ 为所有绕原点的旋转组成的群，则不变量是
\[\Phi((x,y)) = x^2 + y^2\]例 2：令 $X$ 为某个物理系统的状态，$G$ 为时间平移组成的群，则不变量 $\Phi$ 是系统的总能量。
例 3：令 $X = \mathbb R^2 \times \mathbb R^2$，$G$ 为平移、旋转、翻转组成的群（对于两个点作相同操作），则不变量为
\[\Phi((x_1, y_1), (x_2, y_2)) = (x_1 - x_2)^2 + (y_1 - y_2)^2\]稳定子 & 轨道
对于 $x \in X$，定义它的稳定子群（Stabilizer subgroup） 为使得 $x$ 不变的那些 $g$（稳定子）组成的集合：
\[\operatorname{Stab}(x) = \{g \mid \sigma_g(x) = x \}\]显然稳定子群是 $G$ 的子群（不然为什么叫 subgroup，证明略去）：
根据 Lagrange 定理，我们知道：
\[\lvert G \rvert = [G : \operatorname{Stab}(x)] \times \lvert \operatorname{Stab}(x) \rvert\]$[G : \operatorname{Stab}(x)]$ 有何意义？考虑 $\operatorname{Stab}(x)$ 的陪集 $h * \operatorname{Stab}(x)$ 中的任意一个元素 $h * g$：
\[\begin{aligned} & \sigma_{h*g}(x) \\ =& \sigma_h(\sigma_g(x)) \\ =& \sigma_h(x) \ne x \end{aligned}\]即这个陪集中的所有元素都会把 $x$ 送到 $\sigma_h(x)$。
反过来，不同元素是否对应不同陪集？不妨设有两个元素 $g_1, g_2 \in G$ 把 $x$ 映射到相同元素：
\[\begin{aligned} \sigma_{g_1}(x) &= \sigma_{g_2}(x) \\ \sigma_{g_1^{-1}}(\sigma_{g_1}(x)) &= \sigma_{g_1^{-1}}(\sigma_{g_2}(x)) \\ x &= \sigma_{g_1^{-1} * g_2}(x) \\ g_1^{-1} * g_2 & \in \operatorname{Stab}(x) \\ g_2 & \in g_1 * \operatorname{Stab}(x) \\ \end{aligned}\]则 $g_1, g_2$ 必然属于同一陪集，因此不同元素的确对应不同陪集。
因此，所有 $x$ 通过 $G$ 中元素能到达的所有元素与陪集构成双射，这些元素组成的集合称为轨道（Orbit）：
\[\operatorname{Orb}(x) = \{\sigma_g(x) \mid g \in G\}\]有
\[\lvert \operatorname{Orb}(x) \rvert = [G : \operatorname{Stab}(x)]\]代入 Lagrange 定理，得到轨道-稳定子定理（Orbit–stabilizer theorem）：
\[\boxed{ \lvert G \rvert = \lvert \operatorname{Orb}(x) \rvert \times \lvert \operatorname{Stab}(x) \rvert }\]所有轨道组成的集合称为轨道空间，记作 $G \backslash X$（注意不要和商群混淆，轨道空间不一定是群）。
Burnside 引理
接下来的核心问题是计算 $\lvert G \backslash X \rvert$。（本段所有内容都在有限集和有限群中进行。）
TODO: 润色，说明动机
\[\begin{aligned} & \lvert G \backslash X \rvert \\ =& \sum_{O \in G \backslash X} 1 \\ =& \sum_{O \in G \backslash X} \sum_{x \in O} \frac 1 {\lvert O \rvert} \\ =& \sum_{O \in G \backslash X} \sum_{x \in O} \frac {\lvert \operatorname{Stab}(x) \rvert} {\lvert G \rvert} \\ =& \frac 1 {\lvert G \rvert} \sum_{x \in X} \lvert \operatorname{Stab}(x) \rvert \\ \end{aligned}\]若定义
\[\mathcal F = \{(g,x) \mid \sigma_g(x) = x \}\]则
\[\begin{aligned} \lvert \mathcal F \rvert &= \sum_{x \in X} \lvert \{ g \mid \sigma_g(x) = x \} \rvert &&= \sum_{x \in X} \lvert \operatorname{Stab}(x) \rvert \\ &= \sum_{g \in G} \lvert \{ x \mid \sigma_g(x) = x \} \rvert &&= \sum_{g \in G} \lvert \operatorname{Fix}(g) \rvert \\ \end{aligned}\]其中
\[\operatorname{Fix}(g) = \{x \mid \sigma_g(x) = x \}\]于是得到
\[\boxed{ \lvert G \backslash X \rvert = \frac 1 {\lvert G \rvert} \sum_{x \in X} \lvert \operatorname{Stab}(x) \rvert = \frac 1 {\lvert G \rvert} \sum_{g \in G} \lvert \operatorname{Fix}(g) \rvert }\]例题：P4980 【模板】Pólya 定理
一个 $n$ 个点的环，给每个顶点染 $m$ 种颜色中的一种，求本质不同的染色方案数。
本质不同被定义为不能通过旋转和其它染色方案相同。
TODO: 润色
- $G = \mathbb Z_n$
- $X$ 为这个环的所有可能排列
根据 Möbius 反演的知识可进一步减小计算量，此处略去。