浅谈群论

时间:2023-01-31 22:04:12

一些基础

子群

\(H\)\(G\)的子集且\(<H,op>\)为群,则\(<H,op>\)\(<G,op>\)的子群

\(H\)既满足封闭性且求逆封闭,\(\forall a,b\in H,ab\in H,a^{-1}\in H\)

等价于\(\forall a,b\in H,ab^{-1}\in H\)

一些特殊特殊的子群:

生成子群:\(a\in G\),则\(<\{a^i,i\in Z\},op>\)称为生成子群

正规化子:\(a\in G\),则\(<\{x|ax=xa,x\in G>\)称为正规化子,记为\(N(a)\)

共轭子群:\(a\in G,H\)\(G\)的子群,则\(xHx^{-1}\)称为\(H\)的共轭子群

等价类

等价关系:满足自反性\(a=a\),对称性\(a=b\Leftrightarrow b=a\),传递性\(a=b,b=c\Leftrightarrow a=c\)(\(=\)代表的是等价关系)

等价类:\(x\)的等价类\([x]_R=\{y|<x,y>\in R\}\),\(R\)是满足某种等价关系两个元素所有集合

可以认为是把等价关系看作边,\([x]_R\)\(x\)所在联通块的大小

商集:\([A/R]\)指在以\(R\)为等价关系时等价类的集合

陪集

陪集分为右陪集与左陪集,两个没区别

对于\(a\in G\),\(H\)\(G\)的子群,称\(Ha=\{ha|h\in H\}\)\(H\)的右陪集

如果\(H\)为有限集,则\(|Ha|=|H|\)(不会证)

Lagrange定理

\(H\)\(G\)的子群,则\(|G|\)\(|H|\)的倍数

考虑用陪集分解群

首先有个结论,\(\forall a,b\in G,H\)\(G\)的子群,\(a\in Hb\Leftrightarrow Ha=Hb\Leftrightarrow ab^{-1}\in H\)

若已知\(a\in Hb\),则\(a=h_1b,h_1\in H\),\(\forall h_2\in H\),\(h_2a=h_2h_1b\),且\(h_2h_1\in H\)

\(Ha\subseteq Hb\),反过来同理的\(Hb\subseteq Ha\),即\(Ha=Hb\)

若已知\(Ha=Hb\),则\(\exist h_1,h_2\in H,h_1a=h_2b\),\(ab^{-1}=h_1^{-1}h_2\in H\)

若已知\(ab^{-1}\in H\),则\(ab^{-1}=h\in H\),则\(a=hb\in Hb\)

如果将\(Ha=Hb\)视为一种等价关系,\(H\)一定单独是一个等价类

\(a\notin H\),则\(Ha\not=He\),即\(a\)一定不与\(e\)在同一等价类

\(|Ha|=|H|\),所以所有等价类大小相同

\(\dfrac{|G|}{|H|}=|[G/R]|,R=\{<a,b>,Ha=Hb\}\)

由此还可以得到共轭类分解

共轭关系也是一种等价关系,将\(a\in G\),所有与\(a\)共轭的\(b\)形成的集合称为共轭类

\(a\)所在的共轭类大小为\(\dfrac{|G|}{|N(a)|}\)

\(x,y\in G,xax^{-1}=yay^{-1}\)

\(xa=yay^{-1}x\Rightarrow y^{-1}xa=ay^{-1}x\Rightarrow y^{-1}x\in N(a)\Rightarrow xN(a)=yN(a)\)

如果沿用陪集分解的思路,因为\(xN(a)=yN(a)\)\(x,y\)属于同一个等价类

\(N(a)\)陪集分解,对于其中的一个等价类中所有的元素\(x\),\(xax^{-1}\)确定\(a\)的一个共轭

则共轭类的大小即为\(N(a)\)陪集分解后的等价类个数

置换群相关定理

置换群

置换群即为一个\(n\)元排列\(P\)组成的集合,定义运算\(PG=(G_{P_i})\)

可证满足封闭性与求逆封闭

如果将\(i\)\(P_i\)连有向边,则图为若干个不相交的环(\(n\)条边\(n\)个点)

当然,有时置换群不一定是一个排列的集合,但一定是置换的集合

轨道-稳定子群定理

定义一个集合\(A\),\(G\)为一个作用于\(A\)的置换群,\(a\in A\)

定义\(G^a=\{g|g(a)=a,g\in G \}\),称为稳定子群

\(G(a)=\{g(a),g\in G \}\),称为轨道

\(|G|=|G(a)|\times|G^a|\),证明如下

\(x,y\in G\),且\(x(a)=y(a)\),则\(\Leftrightarrow a=x^{-1}(y(a))\Leftrightarrow x^{-1}y\in G^a\Leftrightarrow xG^a=yG^a\)

\(G\)\(G^a\)陪集分解,则当\(x(a)=y(a)\)\(x,y\)属于同一等价类

考虑等价类的个数即为有多少个不同的\(x(a)\)即为\(|G(a)|\)

Burnside 引理

\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G}[A^g]\),\(A^g\)的定义与\(G^a\)类似,就是\(A^g=\{a|g(a)=a,a\in A \}\)

\(|G^a|=\dfrac{|G|}{|G(a)|}\),两边同时求和

\(\sum\limits_{a\in A}|G^a|=\sum\limits_{a\in A}\dfrac{|G|}{|G(a)|}=|G|\sum\limits_{a\in A}\dfrac{1}{|G(a)|}\)

观察\(\sum\limits_{a\in A}\dfrac{1}{|G(a)|}\),本质为轨道个数(每一个\(a\)所在的等价类大小分之\(1\)求和就是等价类的个数)=\([A/G]\)

\(\sum\limits_{a\in A}|G^a|=\sum\limits_{g\in G}[A^g]=|G|\times|[A/G]|\)

\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G}[A^g]\)

在这里我们给问题赋予一个实际意义

考虑\(A\)表示问题的所有方案,\(G\)为问题视为重复方案的置换

\([A/G]\)即为将\(G\)看作一个等价关系的集合后划分出的等价类集合

\(G^a\)即为满足对\(a\)置换作用后依旧不变的置换,\(A^g\)差不多

\(G(a)\)为与\(a\)一起视为一种方案的方案集合,也可一看作是\(a\)所在的等价类

再具体一点的例子就是环的着色问题

Pólya 定理

具体到染色问题,假设有\(m\)种颜色

\(A^g=m^{c(g)}\),\(c(g)\)\(g\)的不相交循环个数

【模板】Pólya 定理

给定一个 \(n\) 个点,\(n\) 条边的环,有 \(n\) 种颜色,给每个顶点染色,问有多少种本质不同的染色方案,答案对 \(10^9+7\) 取模

注意本题的本质不同,定义为:只需要不能通过旋转与别的染色方案相同

很明显\(G\)为一个轮换了\(i\)次的置换群

问题在于计算\(c(g)\),考虑\(g\)是轮换了\(i\)次的的置换,当前位置为\(p\)

\(p->(p+i)mod\ n->(p+2i)mod\ n.....p'mod\ n=p\)

\(p+(n/c(g))i=p+kn\),即\(c(g)=\dfrac{i}{k}\),则\(c(g)\)既为\(n\)的因数也为\(i\)的因数且最大

\(c(g)=gcd(i,n)\)

\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G} n^{c(g)}=\dfrac{1}{n}\sum\limits_{i=1}^nn^{gcd(i,n)}\)

\(f(x)=n^x\)

\([A/G]=\dfrac{1}{n}\sum\limits_{i=1}^nf(gcd(i,n))=\dfrac{1}{n}\sum\limits_{d|n}f(d)\sum\limits_{i=1}[gcd(i,n)=d]=\dfrac{1}{n}\sum\limits_{d|n}f(d)\phi(\dfrac{n}{d})\)

这里用\(dfs\)凑因子可以做到\(\Theta(\sqrt n)\)

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int t;
int n;
int Pow(int a,int b,int p)
{
	int res=1;
	int base=a;
	while(b)
	{
		if(b&1)
		{
			res=((long long)res*base)%p;
		}
		base=((long long)base*base)%p;
		b>>=1;
	} 
	return res;
}
vector<pair<int,int> >Rec;
int Phi[105][105];
int Pri[105][105];
int Used[105];
int Res=0;
void dfs(int x)
{
	if(x==Rec.size())
	{
		int d=1;
		int phi=1;
		for(int i=0;i<Rec.size();i++)
		{
			d=(d*Pri[i][Used[i]]);
			phi=(phi*Phi[i][Used[i]]);
		}
		Res=((long long)Res+((long long)phi*Pow(n,(n/d)-1,MOD))%MOD)%MOD;
		return;
	}
	int Lim=Rec[x].second;
	for(int i=0;i<=Lim;i++)
	{
		Used[x]=i;
		dfs(x+1);
	}
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		Rec.clear();
		scanf("%d",&n);
		Res=0;
		int now=n;
		for(int d=2;d*d<=now;d++)
		{
			if(now%d==0)
			{
				int Tot=0;
				while(now%d==0)
				{
					now/=d;
					Tot++; 
				}
				Rec.push_back(make_pair(d,Tot));
			}
		}
		if(now>1)
		{
			Rec.push_back(make_pair(now,1));
		}
		for(int i=0;i<Rec.size();i++)
		{
			int Lim=Rec[i].second;
			int p=Rec[i].first;
			Phi[i][0]=1;
			Pri[i][0]=1;
			for(int j=1;j<=Lim;j++)
			{
				Pri[i][j]=Pri[i][j-1]*p;
				Phi[i][j]=Pri[i][j]-Pri[i][j-1];
			}
		}
		dfs(0);
		printf("%d\n",Res);
	}
} 

Magic Bracelet

金妮的生日快到了。哈利波特正在为他的新女友准备生日礼物。礼物是一个由\(n\)颗魔法珠组成的魔法手镯。有\(m\)种不同的魔珠。每种珠子都有其独特的特征。将许多珠子串在一起,将制作一个漂亮的圆形魔法手镯。正如哈利波特的朋友赫敏所指出的那样,某些种类的珠子会相互作用并爆炸,哈利波特必须非常小心地确保这些对的珠子不会并排串在一起,有无数种珠子。如果忽略围绕手镯中心旋转产生的重复,哈利能制作多少种不同的手镯?找到取模 \(9973\) 的答案。

同样定义\(G\)为轮换\(i\)次的置换群,但由于不能随便染色,所以不能用\(Pólya\)定理

\([A/G]=\dfrac{1}{|G|}\sum\limits_{g\in G}|A^g|\)

瓶颈在于计算\(|A^g|\)

我们将\(g\)拆分成不同的循环,这些循环的内部的点颜色是相同的且每个循环大小相同,问题是不同循环之间的关系

如果我们把一个循环看成一个点,再将和他有关系的连边,最后连出还是一个环

我们可以考虑只在这个环上计算答案

\(f(x)\)为长度为\(x\)的环时的答案

\([A/G]=\dfrac{1}{n}\sum\limits_{g\in G}|A^g|=\dfrac{1}{n}\sum\limits_{d|n}f(d)\phi(\dfrac{n}{d})\)

现在问题在与如何计算\(f(x)\)

构造一个邻接矩阵\(T\),矛盾为\(0\),否则为\(1\),则\(T^x\)时的对角线之和即为\(f(x)\)

#include<cstdio>
#include<vector>
#include<utility>
#include<cstring>
using namespace std;
const int MOD=9973;

int t;
int m;
int x,y;
int k;
int Pow(int a,int b,int p)
{
	int res=1;
	int base=(a%p);
	while(b)
	{
		if(b&1)
		{
			res=(res*base)%p;
		}
		base=(base*base)%p;
		b>>=1;
	} 
	return res;
}
struct Martix{
    int n, m;
    int val[10][10];
    void clear() { memset(val, 0, sizeof(val)); }
    void init() {
        clear();
        for (int i = 0; i < n; i++) {
            val[i][i] = 1;
        }
    }
    Martix operator*(const Martix x) const {
        Martix Res;
        Res.n = n;
        Res.m = x.m;
        Res.clear();
        for (int k = 0; k <m; k++) {
            for (int i = 0; i < Res.n; i++) {
                for (int j = 0; j < Res.m; j++) {
                    Res.val[i][j]=(Res.val[i][j]+val[i][k]*x.val[k][j])%MOD;
                }
            }
        }
        return Res;
    }
}A;
Martix ppow(Martix Ad, int b) {
    Martix Res;
    Res=Ad;
    Res.init();
    Martix Base = Ad;
    while (b) {
        if (b & 1) {
            Res = Res * Base;
        }
        Base = (Base * Base);
        b >>= 1;
    }
    return Res;
}
int F(int x)
{
	Martix IDSY=ppow(A,x);
	int Res=0;
	for(int i=0;i<m;i++)
	{
		Res=(Res+IDSY.val[i][i])%MOD;
	}
	return Res;
}
vector<pair<int,int> >Rec;
int Phi[205][205];
int Pri[205][205];
int Used[205];
int Res=0;
int n;
void dfs(int x)
{
	if(x==Rec.size())
	{
		int d=1;
		int phi=1;
		for(int i=0;i<Rec.size();i++)
		{
			d=(d*Pri[i][Used[i]]);
			phi=(phi*Phi[i][Used[i]])%MOD;
		}
		Res=(Res+((phi)%MOD*F((n/d)))%MOD)%MOD;
		return;
	}
	int Lim=Rec[x].second;
	for(int i=0;i<=Lim;i++)
	{
		Used[x]=i;
		dfs(x+1);
	}
}

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		Rec.clear();
		scanf("%d %d %d",&n,&m,&k);
		A.clear();
		A.n=m;
		A.m=m;
		for(int i=1;i<=A.n;i++)
		{
			for(int j=1;j<=A.n;j++)
			{
				A.val[i-1][j-1]=1;
			}
		}
		for(int i=1;i<=k;i++)
		{
			scanf("%d %d",&x,&y);
			A.val[x-1][y-1]=0;
			A.val[y-1][x-1]=0;
		}
		Res=0;
		int now=n;
		for(int d=2;d*d<=now;d++)
		{
			if(now%d==0)
			{
				int Tot=0;
				while(now%d==0)
				{
					now/=d;
					Tot++; 
				}
				Rec.push_back(make_pair(d,Tot));
			}
		}
		if(now>1)
		{
			Rec.push_back(make_pair(now,1));
		}
		for(int i=0;i<Rec.size();i++)
		{
			int Lim=Rec[i].second;
			int p=Rec[i].first;
			Phi[i][0]=1;
			Pri[i][0]=1;
			for(int j=1;j<=Lim;j++)
			{
				Pri[i][j]=Pri[i][j-1]*p;
				Phi[i][j]=Pri[i][j]-Pri[i][j-1];
			}
		}
		dfs(0);
		Res=(Res*Pow(n,MOD-2,MOD))%MOD;
		printf("%d\n",Res);
	}
	return 0;
}