群论入门

Part 0 声明

本文若无特殊说明，所有集合皆为有限集合。

Part 1 群定义

1.1 群

称一个集合 $G$ 和某种二元运算 $\cdot$ 构成群当且仅当：

• 存在单位元：$\exists e\in G$ 满足 $\forall g\in G$ 有 $e\cdot g=g\cdot e=g$；
• 满足结合律：$\forall g_1,g_2,g_3\in G$，有 $g_1\cdot(g_2\cdot g_3)=(g_1\cdot g_2)\cdot g_3$；
• 封闭：$\forall g_1,g_2\in G$，满足 $g_1\cdot g_2\in G$；
• 存在逆元：$\forall g\in G$，有 $g^{-1}\in G$ 满足 $g\cdot g^{-1}=g^{-1}\cdot g=e$；

注意 $G$ 不一定满足交换律，满足交换律的群叫交换群或阿贝尔群。

集合 $G$ 和运算 $\cdot$ 构成的群记为 $(G,\cdot)$，本文为了方便省略了运算 $\cdot$，统一记作群 $G$。

1.2 子群

对于一个群 $G$，称群 $H$ 为 $G$ 的子群当且仅当 $H\subseteq G$。

例如模 $3$ 意义下的乘法群 $\{1\}$ 是模 $3$ 意义下的乘法群 $\{1,2\}$ 的子群。

1.3 左陪集和右陪集

对于一个群 $G$、它的子群 $H$ 和一个 $g\in G$：

• 定义 $g\cdot H=\{g\cdot h|h\in H\}$ 为 $H$ 的左陪集；

• 定义 $H\cdot g=\{h\cdot g|h\in H\}$ 为 $H$ 的右陪集；

例如 $\{2\}$ 是模 $3$ 意义下的乘法群 $\{1,2\}$ 的子群 $\{1\}$ 的左陪集，也是它的右陪集。

Part 2 群性质

2.1 群皆可逆矩阵群

考虑一个大小为 $n$ 的群 $G$，$\forall g\in G$，显然可以把 $g$ 写成一个 $n\times n$ 的 01 矩阵且保证写出的矩阵集仍是一个群。

所以任意群都和全体可逆矩阵群的一个子群同构。

2.2 陪集的性质和 Lagrange 定理

2.2.1 陪集的性质

考虑群 $G$ 的任意子群 $H$ 和任意 $a,b\in G$：（这里考虑右陪集，左陪集同理）

1. $H\cdot a\in G$：由于 $G$ 是群所以封闭；

2. $a\in H\cdot a$：因为 $e\in H$；

3. $a\in H\Leftrightarrow H\cdot a=H$：由于 $H$ 是群所以封闭；

4. $b\in H\cdot a\Leftrightarrow H\cdot a=H\cdot b$；

   证明

   右到左显然，左到右：

   $\exist h\in H,h\cdot a=b$，所以 $H\cdot b=H\cdot(h\cdot a)=(H\cdot h)\cdot a=H\cdot a$。（根据 2）

   Q.E.D.

5. $H\cdot a$ 与 $H\cdot b$ 要么相等要么不交；

   证明

   若有交则 $\exist c\in H\cdot a,c\in H\cdot b$，根据 3，$H\cdot a=H\cdot c=H\cdot b$。

   Q.E.D.

6. $|H\cdot a|=|H|$；

   证明

   若 $|H\cdot a|\not=|H|$，则一定有 $|H\cdot a|<|H|$，则有 $h_1,h_2\in H$ 满足 $h_1\not=h_2$ 且 $h_1\cdot a=h_2\cdot a$。

   由于 $a\in G$，所以 $a^{-1}\in G$，所以 $h_1\cdot a\cdot a^{-1}=h_2\cdot a\cdot a^{-1}$，$h_1=h_2$，矛盾。

   所以 $|H\cdot a|=|H|$，Q.E.D.

2.2.2 Lagrange 定理

对于群 $G$ 的任意子群 $S$，均有 $|G|$ 是 $|S|$ 的因子。

证明是显然的，根据 2.2.1 中的 1、5、6 立得。

推论：$\forall \gcd(x,p)=1,x^{\varphi(p)}\equiv 1\pmod p$

考虑模 $m$ 的乘法群 $S_p=\{x|1\le x<p,\gcd(x,p)=1\}$，显然有 $|S_p|=\varphi(p)$。

对于 $S_p$ 的幂子群 $H_x=\{x^y\text{ mod } p|y\in \mathbb{N}\}(x\in S_p)$，均有 $|H_x|$ 是 $|S_p|$ 即 $\varphi(p)$ 的因数。

因为 $x^{|H_x|}\equiv 1\pmod p$，所以 $x^{\varphi(p)}\equiv (x^{|H_x|})^{\frac{\varphi(p)}{|H_x|}}\equiv 1\pmod p$。

Part 3 群作用

考虑一个置换群 $G$ 和一个集合 $X$，满足 $\forall x\in X,g\in G$ 都有 $x\cdot g\in X$。

这时称 $G$ 是 $X$ 上的作用，例如 $n$ 阶置换群就是 $n$ 阶排列集上的作用。

3.1 轨道和定点

$\forall x\in X$，定义 $G$ 作用在 $X$ 上的轨道 $O_x$ 和定作用集（其实是群） $G_x$：

$O_x=\{x\cdot g|g\in G\}\\ G_x=\{g|g\in G,x\cdot g=x\}\\$

$O_x$ 实际上是在 $G$ 作用下 $X$ 中与 $x$ 等价元素的集合。

考察 $G_x$ 的性质：

• $G_x\subseteq G$；
• 存在单位元：$e\in G_x$，这很显然；
• 满足结合律：$\forall g_1,g_2,g_3\in G_x$，有 $g_1\cdot(g_2\cdot g_3)=(g_1\cdot g_2)\cdot g_3$，这也很显然；
• 封闭：$\forall g_1,g_2\in G_x$ 有 $g_1\cdot g_2\in G_x$，因为 $x\cdot g_1\cdot g_2=(x\cdot g_1)\cdot g_2=x\cdot g_2=x$；
• 存在逆元：$\forall g\in G_x$ 有 $g^{-1}\in G_x$，因为 $x\cdot g=x\Leftrightarrow x=x\cdot g^{-1}$；

所以 $G_x$ 是 $G$ 的子群。

3.2 Burnside 引理和 Polya 定理

3.2.1 轨道-不动点引理（Orbit-stabilizer 引理）

$|O_x|\times |G_x|=|G|$

3.2.2 Burnside 引理

设 $X^g=\{x|x\in X,x\cdot g=x\}$，$X/G=\{O_x|x\in X\}$ 即 $X$ 在 $G$ 作用下的轨道集合（$|X/G|$ 即为 $X$ 在 $G$ 作用下本质不同元素个数），则：

$|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|$

3.2.3 Polya 定理

考虑给所有满足 $x\in X$ 的 $x$ 中元素染上 $m$ 种不同颜色（相同颜色元素本质相同）。$\forall g\in G$，设 $c(g)$ 为 $g$ 中轮换个数（置换中环的个数），则在 $G$ 作用下本质不同染色方案数为：

$\frac{1}{|G|}\sum\limits_{g\in G}m^{c(g)}$

Tips：

观察 Ploya 定理的证明过程，不难发现对于置换作用 $g$，满足 $x\cdot g=x$ 的 $x\in X$ 必定满足位于同一个轮换的元素本质相同。

这方便了 Burnside 引理的应用。

Part 4 群例题

• P4980 【模板】Pólya 定理

  查看题解

  考虑 $n$ 阶顺时针旋转置换构成的集合 $G$：

  • 存在单位元：置换 $p_i=i$ 在 $G$ 中；
  • 满足结合律：显然；
  • 封闭：显然；
  • 存在逆元：显然，可以绕一大圈再回来；

  所以 $G$ 是一个群。

  考虑 Polya 定理：

  $|X[m]/G|=\frac{1}{|G|}\sum\limits_{g\in G}m^{c(g)}$

  注意到 $\forall g\in G$，若 $p\cdot g$ 后 $p_1\to p_x$，则 $g$ 中置换环有 $\gcd(x,n)$ 个，即 $c(g)=\gcd(x,n)$。证明考虑从 $i$ 向 $i+x-1\text{ mod }n+1$ 即旋转后的点连边。

  所以答案即为：

  $\frac{1}{n}\sum\limits_{d|n}n^d\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]=\frac{1}{n}\sum\limits_{d|n} n^d\varphi(\frac{n}{d})$

  有一个神奇的结论，$\sum\limits_{d|n}O(\sqrt d)=O(n^{\frac{3}{4}})$，所以暴力计算 $\varphi(\frac{n}{d})$ 能过。

  考虑时间复杂度更正确的做法，实际上可以把 $n$ 质因数分解，求 $\varphi(\frac{n}{d})$ 时再 $O(\log n)$ 分解质因数根据 $\varphi$ 的积性算出 $\varphi(\frac{n}{d})$。单次时间复杂度 $O(\sqrt n\log n)$。

  代码如下：（$O(T\sqrt n\log n)$ 做法）

  #include <iostream>
  #include <cstdio>
  #include <vector>
  
  using namespace std;
  
  const int S=100005,BS=35,p=1000000007;
  
  int n;
  bool nop[S];
  int tot,prime[S];
  int cp,ps[S],pi[S][BS];
  
  inline int qpow(int x,int y)
  {
  	int res=1;
  	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
  	return res;
  }
  
  inline void init()
  {
  	nop[0]=nop[1]=true;
  	for(int i=2;i<=S-3;i++)
  	{
  		if(!nop[i]) prime[++tot]=i;
  		for(int j=1;j<=tot;j++)
  		{
  			if(1ll*i*prime[j]>S-3) break;
  			nop[i*prime[j]]=true;
  			if(i%prime[j]==0) break;
  		}
  	}
  }
  
  inline void slove()
  {
  	scanf("%d",&n);
  	cp=0;
  	int tn=n;
  	for(int i=1;1ll*prime[i]*prime[i]<=tn;i++)
  	{
  		if(tn%prime[i]==0)
  		{
  			++cp;
  			int tt=1;
  			ps[cp]=prime[i],pi[cp][0]=1,pi[cp][1]=ps[cp]-1;
  			while(tn%ps[cp]==0) tn/=ps[cp],pi[cp][tt+1]=pi[cp][tt]*ps[cp],tt++;
  		}
  	}
  	if(tn>1) cp++,ps[cp]=tn,pi[cp][0]=1,pi[cp][1]=tn-1;
  	int sum=0;
  	for(int i=1;1ll*i*i<=n;i++)
  	{
  		if(n%i==0)
  		{
  			int d=i,pid=1;
  			for(int j=1;j<=cp;j++)
  			{
  				int ct=0;
  				while(d%ps[j]==0) ct++,d/=ps[j];
  				pid*=pi[j][ct];
  			}
  			sum=(sum+1ll*qpow(n,n/i)*pid%p)%p;
  			if(i*i!=n)
  			{
  				d=n/i,pid=1;
  				for(int j=1;j<=cp;j++)
  				{
  					int ct=0;
  					while(d%ps[j]==0) ct++,d/=ps[j];
  					pid*=pi[j][ct];
  				}
  				sum=(sum+1ll*qpow(n,i)*pid%p)%p;
  			}
  		}
  	}
  	sum=1ll*sum*qpow(n,p-2)%p;
  	printf("%d\n",sum);
  }
  
  int main()
  {
  	init();
  	int T;
  	scanf("%d",&T);
  	while(T-->0) slove();
  	return 0;
  }
  

• 【2023NOI模拟赛27】美术作业

• 洛谷题目列表&tag=Polya 定理