算法基础 - Burnside 引理
Kobral
·
·
个人记录
介紹
给定一个有限群 G 和一个集合 X，定义一个操作 \rho: G \times X \rightarrow X，满足以下条件：
- 对于任意的 g \in G 和 x \in X，有 \rho(e,x) = x，其中 e 是 G 的单位元。
- 对于任意的 g,h \in G 和 x \in X，有 \rho(g, \rho(h,x)) = \rho(gh, x)。
设 X/G 表示 X 的所有 G 的轨道组成的集合，即 X/G = \{Gx | x \in X\}。则对于任意的 g \in G，轨道 Gx 的元素个数为 |\{y \in X | \rho(g,y) = y\}|。Burnside 引理给出了计算 X/G 中轨道个数的方法， X^g=\{y\in X|\rho(g,y)=y\}：
|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|
证明
在Burnside引理的证明中，第一步是将对群元素 g \in G 的求和重新表达为对元素 x \in X 的等价求和：
\sum_{g \in G}|X^g| = \#\{(g,x) \in G \times X \mid g \cdot x = x\} = \sum_{x \in X}|G_x|.
这里 X^g = \{x \in X \mid g \cdot x = x\} 是由 g \in G 固定的 X 中的点集，而 G_x = \{g \in G \mid g \cdot x = x\} 是 G 的稳定子群，即保持点 x \in X 的对称。
轨道-稳定子定理表明对于每个 x \in X，轨道 G \cdot x = \{g \cdot x \mid g \in G\} 和左陪集 G/G_x 之间存在一种自然的双射。拉格朗日定理暗示：
|G \cdot x| = [G : G_x] = \frac{|G|}{|G_x|}
因此，求和可以重写为：
\sum_{x \in X}|G_x| = \sum_{x \in X}\frac{|G|}{|G \cdot x|}
将 X 表示为 X/G 中的轨道的不交并：
\sum_{x \in X}\frac{|G|}{|G \cdot x|} = |G|\sum_{A \in X/G}\sum_{x \in A}\frac{1}{|A|} = |G|\sum_{A \in X/G}1 = |G|\cdot|X/G|.
将所有内容综合在一起得到所需的结果：
\sum_{g \in G}|X^g| = |G|\cdot|X/G|.
这类似于共轭类方程的证明，该证明考虑了 G 在自身上的共轭作用：X = G 且 g \cdot x = gxg^{-1}，这样 x 的稳定子就是中心化子：G_x = ZG(x)。
应用
我们来看一个使用 Burnside 引理解决的问题。假设有一个正方形，我们想要用三种不同颜色进行染色，求共有多少种不同的染色方案，其中只考虑旋转对称性，忽略翻转对称性。
设正方形的顶点集合为 X，每个顶点可以染成三种不同颜色之一。我们将操作 \rho 定义为正方形的旋转操作，即对于任意 g \in G和x \in X，\rho(g,x) 表示将顶点 x 按照 g 的旋转方式旋转。
根据 Burnside 引理，我们只需要计算满足 \rho(g,x) = x 的元素个数，其中 g 为正方形的旋转操作，x 为染色方案。对于正方形的旋转操作，共有 4 种情况：不动，顺时针旋转 90 度，旋转 180 度和逆时针旋转 90 度。
计算结果留给读者练习。
作者：李耀升