跳转至

2.【理论】群与对称

\[ \rm{Define\ \LaTeX \ Macros\ Here} \newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}} \newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}} \newcommand\ul[1]{\underline{#1}} \newcommand\dis{\operatorname{dis}} \newcommand\edp{\operatorname{edp}} \newcommand\Endpos{\operatorname{Endpos}} \newcommand\Startpos{\operatorname{Startpos}} \newcommand\height{\operatorname{height}} \newcommand\SA{\operatorname{SA}} \newcommand\len{\operatorname{len}} \newcommand\chkmax{\operatorname{chkmax}} \newcommand\chkmin{\operatorname{chkmin}} \newcommand\siz{\operatorname{siz}} \newcommand\fa{\operatorname{fa}} \newcommand\LCP{\operatorname{LCP}} \newcommand\EGF{\operatorname{EGF}} \newcommand\OGF{\operatorname{OGF}} \newcommand\bd{\operatorname{Border}} \newcommand\mbd{\operatorname{MaxBorder}} \]

本节内容是下一节部分内容的基础，但不会本节的内容也不影响你阅读下一节的大部分内容。

群的引入

假设我们有一个对称的操作的集合 \(G\)，组合对象的全集记为 \(X\)，一个组合对象 \(x\) 能够通过 \(G\) 中的操作生成其他的组合对象。我们说这些组合对象等价，需要计数所有等价类的个数。

例子

  1. 给一个 \(n\) 元环节点标号，两个环同构（事实上环上就是能通过旋转重合），则视为同一个环。
  2. 给一个立方体的 \(6\) 个面涂上颜色，如果两个立方体能够通过旋转重合，则视为同一个立方体。
  3. ……

为了给这些计数问题一个通用的解决方法，我们就必须研究这些对称操作组成的结构。

若 \(x,y\) 两个对象本质属性相同，则我们说 \(x\sim y\)。我们说 \(f\) 是一个对称操作，其作用在 \(x\) 上的结果记作 \(f(x)\)，那么有 \(\forall x\in X,x\sim f(x)\)，也就是任意一个对象 \(x\) 在 \(f\) 的作用下本质属性都不改变。

  1. 若 \(f,g\) 都是对称操作，那么 \(x\sim g(x)\)，自然有 \(g(x)\sim f(g(x))\)。也就是说先执行 \(f\)，再执行 \(g\)，这两步合在一起的变换也是一个对称操作。我们把这个操作记作 \(f\circ g\)，那么就是说 \(\forall f,g\in G,f\circ g\in G\)。
  2. 对于离散的对象来说，对称总是一种保持结构不变的重标号方式。也就是说 \(f\) 是一个函数 \([n]\rightarrow [n]\)，函数复合必然有结合律，即 \(\forall f,g,h\in G,(f\circ g)\circ h=f\circ (g\circ h)\)。
  3. 必然存在 \(e\in G\)，\(e(x)=x\)，因为什么都不做同样不会改变其本质属性。
  4. 由于 \(x\sim f(x)\)，那么就必然有 \(f(x)\sim x\)，如果将 \(x\) 看作是 \(f(x)\) 施加操作才得到的，那么就必然 \(\exists f^{-1} \in G\)，\(f(x)\sim (f^{-1}\circ f)(x)\)，也就是说 \(\forall f\in G,\exists f^{-1}\in G,f^{-1}\circ f=e\)。

通过上面的讨论，我们可以说：对称操作集合 \(G\) 在操作复合运算 \(\circ\) 下构成一个群。对称变换是群 \(G\) 对组合对象集合 \(X\) 的群作用。我们要计数的东西就是等价类集合 \(X/G\) 的大小 \(|X/G|\)。

轨道-稳定子群定理

有几个结构是值得我们注意的

  1. 对象 \(x\) 的轨道 \(O_x=\{f(x):f\in G\}\)，也就是 \(x\) 的等价类集合。
  2. 稳定子群 \(G_x=\{f\in G:f(x)=x\}\)，也就是作用在 \(x\) 不变的那些变换组成的集合。它是 \(G\) 的子群是易证的。
  3. 不动点 \(X^g=\{x\in X:g(x)=x\}\)，在 \(g\) 作用下不变的结构。

对于前两个结构，我们有轨道-稳定子群定理

\[ \forall x\in X,|O_x|\cdot |G_x|=|G| \]

这个形式一看就像拉格朗日定理啊！事实上一种证明方法就是在轨道与 \(G_x\) 在 \(G\) 中的左陪集建立双射，不过我们这里不这么干。我们用更简单的另一种理解方式。

我们知道

\[ |G|=\sum_{y\in O_x}|G_{x\rightarrow y}| \]

引理

若 \(f(x)=y\)，则 \(\{f\circ g: g\in G_x\}=G_{x\rightarrow y}\)，\(|G_x|=|G_{x\rightarrow y}|\)。

人话就是，无论是哪个 \(f\in G_{x\rightarrow y}\)，通过右复合上所有 \(g\in G_x\)，都能生成整个 \(G_{x\rightarrow y}\)。

让我们来证明这个引理

  1. 首先，我们证明 \(\{f\circ g:g\in G_x\}\subseteq G_{x\rightarrow y}\)。

    这是显然的，因为 \(f(g(x))=f(x)=y\)。

  2. 下一步，我们证明 \(\{f\circ g:G_x\}=|G_x|\)。

    这也是显然的，即证明 \(\forall g_1,g_2\in G_x,g_1\neq g_2\Longrightarrow f\circ g_1\neq f\circ g_2\)。反证，假设成立，右消去律告诉我们 \(g_1=g_2\)，矛盾。

    结合 1，这告诉我们 \(|G_x|\le |G_{x\rightarrow y}|\)。

  3. 接下来，我们证明 \(|G_{x\rightarrow y}|\le |G_x|\)，故技重施即可，对于 \(\forall f\in G_{x\rightarrow y},\exists g\in G_{y\rightarrow x}\)。那么对于同一个 \(g\)，所有的 \(f\circ g\) 必定两两不同，所以 \(|\{f\circ g:f\in G_{x\rightarrow y}\}|=|G_{x\rightarrow y}|\)，又有 \(\{f\circ g:f\in G_{x\rightarrow y}\}\subseteq G_x\)，故 \(|G_{x\rightarrow y}|\le |G_x|\)。Q.E.D！

有了 \(|G_{x\rightarrow y}|=|G_x|\) 这个引理，一切就变得容易了。

\[ |G|=\sum_{y\in O_x}|G_{x\rightarrow y}|=|O_x|\cdot |G_x| \]

Burnside's Lemma

又叫 Not Burnside's Lemma。

我们再考察上面的第三个结构：不动点。

\[ \sum_{x\in X,g\in G}[g(x)=x]=\sum_{g\in G}X^g=\sum_{x\in X}G_x \]

然后想想我们怎么表示轨道数 \(|X/G|\)。对每个轨道，我们要让所有 \(y\in O_x\) 加起来恰好是 \(1\)，立即有：

\[ |X/G|=\sum_{x\in X}\frac{1}{|O_x|}=\sum_{x\in X}\frac{|G_x|}{|G|}=\frac{1}{|G|}\sum_{g\in G}X^g \]

这就是 Burnside's Lemma：轨道数=所有变换不动点个数的平均值。