浅谈 Pólya 定理

yanzihe · 2025-04-18 17:00:55 · 算法·理论

首先推荐一下我的博客，本文所有内容同步发表于这个博客中。

第一章

群的定义

群是满足如下条件的二元组 (G, \times)，其中 G 是一个集合，\times 是一个二元运算。

• 封闭性：\forall a, b\in G, a\times b \in G

• 结合律：\forall a, b, c\in G, (a\times b)\times c=a\times(b\times c)

• 单位元存在性：\exists e\in G\ \text{s.t.} \forall a\in G, a\times e=e\times a=a（称这样的 e 是 G 的单位元）

• 逆元存在性：\forall a \in G, \exists b \in G\ \text{s.t.} a\times b=b\times a=e（称这样的 b 为 a^{-1}）

可以证明，一个群满足如下两个推论：

• 推论 1：群的单位元唯一
  证明：假设 e_1, e_2\in G 且 e_1, e_2 都是 G 的单位元。
  那么因为 e_2 是单位元，e_1\times e_2=e_1。同理，e_1\times e_2=e_2，所以 e_1=e_2。因此群的单位元唯一。

• 推论 2：群中任意元素 a，它的逆元唯一 证明：假设 b_1, b_2\in G 都是 a 的逆元，则根据结合律，有：

  (b_1\times a)\times b_2=b_1\times(a\times b_2)

  所以有 e\times b_2=b_1\times e 即 b_1=b_2 因此逆元唯一。

如果一个群 (G, \times) 满足 \forall a, b\in G, a\times b=b\times a，则称这个群是阿贝尔群。

如果一个群 (G, \times) 满足 G 是有限集，则称这个群是有限群，称 G 是这个有限群的阶，记作|(G, \times)|。

子群的定义

如果 H\subseteq G，并且 (H, \times) 和 (G, \times) 都是群，则称 (H, \times) 是 (G, \times) 的子群，记作:

如果 H={e} 或者 H=G，则称(H, \times) 是 (G, \times) 的平凡子群，反之，则是非平凡子群。

习题

一.判断如下二元组是否是群：

1. (\mathbb{R}^*, \times)
2. ((-\infty, 4)\cup(4, +\infty), +)
3. (\mathbb{N}, +)
4. (\mathbb{Z}^*, +)
5. (\mathbb{Q}^*, \div)
6. (\varnothing, \times)
7. (\{1\}, \times)
8. (\text{定义域和值域均是全体实数的所有严格增函数}, \text{映射复合})

二.对于下列集合，分别构造运算 \times，使得它们和 \times 构成的二元组是群：

1. (-\infty, 4)\cup(4, +\infty)
2. \{3, 4, 5, 6\}
3. \{\sin(1), \pi, \sqrt 2\}

三.是否所有群 G,都有 H 是 G 的子群并且 H\ne G？如果是，请证明，如果否，请构造反例。

四.判断该命题是否正确：如果 g\in G，并且其逆元为 g^{-1}，那么 \forall H\leq G 且 g\in H，都有 g^{-1}\in H。

五.判断该命题是否正确：如果 e 是 G 的单位元，则 \forall H\leq G，都有 e\in H。

四.找出下列群的一个非平凡子群或者证明其没有非平凡子群：

1.(\{0, 1, 2, 3, 4, 5\}, \triangle)（定义 a\triangle b=(a+b)\mod 6）

2.(\text{全体多项式函数}, \text{多项式乘法})

3.(\text{定义域和值域均是全体实数的所有严格增函数}, \text{函数复合})

第二章

陪集的定义

对于两个群 H, G，如果 H\leq G, g\in G，则定义左陪集：

定义右陪集：

陪集的性质

如果 H\leq G, g\in G，则有：

• g\in gH
• gH=H\iff g\in H
• g_1H=g_2H\iff g_1^{-1}\times g_2\in H
• Hg_1=Hg_2\iff g_1\times g_2^{-1}\in H
• g_1H\cap g_2H\ne\varnothing \iff g_1H=g_2H
• \bigcup_{g\in G}gH=G

习题

一.证明上述陪集的性质。

二.证明如果 H\leq G, g\in G，那么 (gH, \times) 是群当且仅当 g\in H。

三.证明如果 b\in G, H\leq G, h\in H，那么 H(hb)=Hb。

三.定义G/H=\{gH|g\in G\}， H\setminus G=\{Hg|g\in G\}，求证 |G/H|=|H\setminus G|

证明

考虑引理：

aH=bH \iff Ha^{-1}=Hb^{-1}

证明：aH=bH \iff a^{-1}b\in H \iff Ha^{-1}=Hb^{-1}

考虑映射 f:G/H\to H\setminus G，满足 f(aH)=Ha^{-1}。

设 aH\ne bH，根据引理有 Ha^{-1}\ne Hb^{-1}，所以 f 是单射。

所以有 |G/H|\leq|H\setminus G|。同理有 |G/H|\geq|H\setminus G|，所以 |G/H|=|H\setminus G|

拉格朗日定理

若 H\leq G，定义 G/H=\{gH|g\in G\}，定义 |G:H|=|G/H|。

对于有限群 G 和 H\leq G，有 |H|\times|G:H|=|G|（注意这里的乘法是正整数乘法，而非 G 中的运算）

习题

一.利用陪集的性质，证明拉格朗日定理。

二.证明 9 阶群不存在 4 阶子群。

二.设 G_1, G_2, ..., G_n 是有限群且满足 G_1\geq G_2 \geq ... \geq G_n，求证 [G_1:G_n]=\prod_{i=1}^{n-1}[G_i:G_{i+1}]。

第三章

对称群

对于集合 A，定义对称群是由全体 A\rightarrow A 的双射构成的群（运算是映射的复合），记做 \text{Sym}(A)。

当 A 是有限集时，设 n=|A|，则称 \text{Sym}(A) 为 n 次对称群，记作 S_n。

定义对称群的子群是变换群，如果这个对称群是有限群，那么还称它的子群为置换群。（置换群也是一种变换群）

习题

一.证明 |S_n|=n! 二.验证对称群满足群的性质。 三.证明若 n\geq 3，则 S_n 不是阿贝尔群。

轮换

定义置换 \sigma:A\rightarrow A 是一个轮换当且仅当存在 (a_0, a_2, ......, a_{k-1})，满足 \forall i, \sigma(a_i)=a_{i+1\mod k}，且对于所有 x\ne a_i, \sigma(x)=x。

一个置换可以用 (a_0, a_1, ......, a_{k-1}) 的形式表示，其中 k 被称为这个轮换的长度。

置换唯一分解定理

一个置换可以被分解为若干个不相交轮换的复合，并且如果不考虑这些轮换的顺序，这样的分解方式唯一。

证明比较显然，考虑若 \sigma(a)=b，则连接 a 和 b，最终必然得到若干个环，每一个环都恰好对应一个轮换。

习题

一.证明两个不相交轮换的复合满足交换律。

二.证明任何置换都可以被分解为若干个长度为 2 的轮换的复合。

三.设 \sigma=\prod_{i=1}^{k}A_i(A_1, A_2, ..., A_k) 是不相交的轮换，设 p=\text{lcm}_{i=1}^{k}(A_i\text{的长度})，求证 \sigma^p=e(\text{单位元})。

第四章

群作用

考虑群 G 和集合 X，如果有二元运算 g*x(g\in G, x\in X) 满足如下性质，则称群 G 作用于 X。

• g*x\in X
• g1\times (g2*x)=(g1\times g2)*x
• e*x=x

为了书写简便，有时候 * 会省略。

考虑如下几个例子：

• 使用满足 g*x=x 的二元运算，任意群 G 都作用于 X。（此时称这个作用是平凡的）

• 使用加法做为二元运算，则 (\mathbb{Z}, +) 作用于 \mathbb{Z} 和 \mathbb{R}，但是 (\mathbb{R}, +) 不作用于 \mathbb{Z}。

• 考虑二元运算 f*x=f(x)，则 S_A 作用于 A。

习题

一.设 g\in G，G 作用于 X，证明映射 f:x\rightarrow g*x 是双射。

二.证明若 G 作用于 X，那么存在映射 f:G\rightarrow S_X，满足 \forall g_1, g_2\in G, f(g_1g_2)=f(g1)\circ f(g2)。

一些定义

定义 x 的轨道 O_x=\{gx|g\in G\}，定义 x 的稳定化子 F_x=\{g|gx=x\}。 可以证明 F_x\leq G。(只需验证群的四条性质是否满足)

考虑如下例子：

• 在平凡作用中，\forall x\in X, O_x=\{x\}, F_x=G
• 考虑以加法为二元运算，(\mathbb{Z}, +) 作用于 \mathbb{Q}，并且 \forall x\in \mathbb{Q}，O_x=\{x+k|k\in\mathbb{Z}\}, F_x=\{0\}

习题

一.完成 F_x\leq G 的证明。 二.证明 \forall y\in O_x, O_y=O_x。

轨道-稳定子定理

证明：|\{O_x|x\in X\}|=\sum_{x\in X}\dfrac{1}{|O_x|}=\sum_{x\in X}\dfrac{|F_x|}{|G|}=\dfrac{1}{|G|}\sum_{x\in X}|F_x|=\dfrac{1}{|G|}\sum_{g\in G}|X_g|。

最后一步是因为两个和式都会每一对满足 gx=x 的 x 和 g 统计恰好一次。

习题：

P4980 【模板】Pólya 定理

求对 n 个点的环使用 n 种颜色染色的方案数。两个方案数不同当且仅当一个环无法通过旋转和另一个环重合。

解法

考虑群 G=(\{\text{顺时针旋转零个节点}, \text{顺时针旋转一个节点},...... \text{顺时针旋转} n-1 \text{个节点}\}, \text{操作的复合})，容易验证它是一个群。（事实上还是阿贝尔群）

考虑集合 X=\text{所有的染色方案}，定义二元运算 g*x= 对 x 执行 g 操作后得到的染色方案，容易验证 G 作用于 X 上。

发现和 x 本质相同的染色方案构成的集合是 O_x，所以题目求的就是 |\{O_x|x\in X\}|，可以利用 Burnside 引理计算，但问题是如何计算 X_g。

考虑哪些染色方案满足顺时针旋转 k 个节点后不变，发现它的充分必要条件是 \forall i, a_i=a_{i+\gcd(n, k)\mod n)}。（具体证明需要用到裴蜀等式）所以方案数是 n^{\gcd(n, k)}。

根据 Burnside 引理，答案是 \frac{1}{n}\sum_{i=1}^nn^{\gcd(i, n)}。

根据莫比乌斯反演相关理论，得出答案是 \sum_{g|n}n^{g-1}\phi(\frac{n}{g})，直接计算即可。

第五章

在上一章的最后，我们使用 Burnside 引理解决了 【模板】Pólya 定理。但是，这类题其实可以被 Pólya 定理更好的解决。

Pólya 定理

设 G, X 均有限且 G 作用在 X 上，Y 是一个有限集（你可以认为其中的每一个元素都是一种颜色），定义 X^Y 是全体映射 X\rightarrow Y 构成的集合。（你可以认为 X^Y 中的每一个元素都是一个染色方案）

考虑二元运算 g*f=h(g\in G, f, h\in X^Y)，满足 \forall x\in X, h(x)=f(g^{-1}x)。容易验证 G 通过二元运算 * 作用于 X^Y。（你可以认为如果 g*f=h，则 f 和 h 这两个染色方案本质相同）

定义双射（置换）\sigma_g:X\rightarrow X，满足 \sigma_g(x)=gx，定义 c(g)=\sigma_g 分解成的不相交轮换数量。

那么著名的 Pólya 定理断言：|\{O_x|x\in X^Y\}|=\frac{1}{|G|}\sum_{g\in G}|Y|^{c(g)}。

例子

求 n 个颜色给 n 个点的环染色，认为两种染色方案相同当且仅当能够通过旋转使得一种方案和另一种方案重合，求本质不同的染色方案数。

定义 Y=\{\text{颜色1}, \text{颜色2}, ......, \text{颜色n}\}, X 是环上 n 个节点构成的集合，G=(\{\text{顺时针旋转零个节点}, \text{顺时针旋转一个节点},...... \text{顺时针旋转} n-1 \text{个节点}\}, \text{操作的复合})。

根据定义 X^Y 是所有给点染色的方案构成的集合。

根据定义， g*f 就是染色方案 f 经过 g 操作得到的染色方案（你应该自己验证这一点），|\{O_x|x\in X^Y\}| 就是本质不同的染色方案，利用 Pólya 定理可知答案是 \frac{1}{n}\sum_{g\in G}n^{c(g)}。

考虑计算 c(\text{顺时针旋转k个节点})，它的意义如果把两个点能通过若干次旋转 k 个节点而重合，则成这两个点本质相同的情况下，本质不同的点的数量。我们有 c(\text{顺时针旋转k个节点})=\gcd(n, k)

你会发现，转化到这里 Pólya 定理的结论和 Burnside 推出的结论完全相同。所以使用 Burnside 引理能够容易地证明出 Pólya 定理。

习题

一.考虑一个正方形，给它的顶点染色为红色，绿色或者蓝色，认为旋转后相同的染色方案相同，求本质不同的染色方案。（答案：\frac{1}{4}(3^4+3+3^2+3)=24）

二.考虑一个三角形，给它的顶点染色为红色，绿色或者蓝色，如果一种染色方案通过若干次旋转和翻着后和另一种染色方案相同，则认为它们本质相同，求本质不同的染色方案。（答案 \frac{1}{6}(3^3+3^2+3^2+3^1+3^2+3^1)=10）

三.求证 \forall n, m\in \mathbb{Z}^+，n|\sum_{k=1}^n m^{\gcd(n, k)}。