【基础定义】
-
笛卡尔积。
\(A\times B=\{(a,b)|a\in A,b\in B\}\)。\(A\) 和 \(B\) 各是一个集合。
-
运算。一般研究二元运算（加减乘除等）。
运算是一种映射。从两个集合 \(A,B\) 到一个集合 \(C\) 的映射，满足 \(A\times B=C\)（笛卡尔积）。
-
群。
群是集合 \(G\) 和运算 \(*\) 的二元组 \((G,*)\)。
群需要满足以下性质：
-
封闭性。\(*\) 为 \(G\times G\rightarrow G\) 的映射。
-
结合律。\((a*b)*c=a*(b*c)\)。
-
单位元。存在 \(e\in G\) 使得任意 \(a\in G\) 有 \(a*e=a\)、\(e*a=a\)。
注：\(e\) 唯一不是群的定义，而是群的性质。
-
逆元。对任意 \(a\in G\)，存在 \(a^{-1}\in G\)，使得 \(a*a^{-1}=e\)、\(a^{-1}*a=e\)。
注：\(a^{-1}\) 唯一、逆元都是相互的，不是群的定义，而是群的性质。
满足前两个的二元组叫半群；满足前三个的叫幺半群；如果在群的基础上还满足交换律，叫阿贝尔群。
注：一个简单的非阿贝尔群的群是二面体群。它由所有 "旋转 \(\alpha\) 度" 和 "旋转 \(\alpha\) 度并左右翻转" 的操作构成，且所有在它里面的操作对正 \(n\) 边形应用后，形状相同。
-
-
子群。
一个群 \((G,*)\) 的一个子群 \((G',*)\)，要满足 \(G'\subseteq G\) 且 \((G',*)\) 是群。
-
生成子群。
一个群 \((G,*)\)。对于一个集合 \(A\subseteq G\) 的生成子群，是 \(A\) 中元素通过 \(*\) 和取逆元能得到的所有元素，与 \(*\) 操作构成的子群。
单个元素只用 \(*\) 运算在有限群中的生成子群，记作 \(<a>\)。\(<a>\) 的元素个数称作 \(a\) 的阶。子群元素个数称作子群的阶。
如果考虑 \(*\) 定义为乘法，\(a*a=a^2\)。我们发现如果 \(a^x=a\)，那么 \(<a>=\{a,a^2,\dots,a^{x-1}\}\)。那 \(a\) 的阶就是 \(x-1\)。发现这和数论里的定义是一样的！（\(a^{x-1}=1\)）
-
循环群。
对于群 \((G,*)\)，如果 \(G\) 里存在元素 \(a\)，使得 \(<a>=(G,*)\)，则 \((G,*)\) 是循环群，称 \(a\) 是生成元。
-
陪集。
有一个群 \((G,*)\)。对任意元素 \(b\in G\) 与子群 \((N,*)\)，记 \(bN=\{b*a|a\in N\}\) 为 \(N\) 的左陪集。右陪集类似定义。
若任意 \(b\)，有 \(bN=Nb\)，称 \((N,0)\) 为 \((G,0)\) 的正规子群。
-
群同态与群同构。
两个群 \((A,\oplus),(B,\otimes)\) 是同态的，当且仅当存在一个从 \(A\) 到 \(B\) 的映射 \(f\)，使得任意 \(x,y\in A\) 有 \(f(x)\otimes f(y)=f(x\oplus y)\)。
两个群是同构的，当且仅当它们同态，且 \(f\) 是一一映射。在群论意义下，两个群同构，表示它们完全一样。
-
置换。对集合 \(S\)，一个双射 \(f:S\rightarrow S\) 是 \(S\) 的置换。
常用方括号内两行数表示：
\[f=\begin{bmatrix}1&2&3&4\\2&3&1&4\\\end{bmatrix} \] -
轮换。每个置换可以等效为若干个独立轮换的复合。
-
对换。即大小为 \(2\) 的轮换。
-
不动点。即大小为 \(1\) 的轮换。
-
对称群。集合 \(T\) 的所有置换构成对称群 \(S\)。注意 \(S\) 只和 \(|T|\) 有关。
对称群是非阿贝尔群。
-
置换群。置换群是对称群的子群。
-
群作用。
直观理解：一个群，常表示一些变换；一个集合，常作为被变换对象。一个变换群和一个被变换对象的集合，共同构成群作用。
形式化定义：
对于集合 \(X\)（元素为 \(x_1,x_2,\dots\)）与群 \(G=(F,*)\)（\(F\) 元素为 \(f_1,f_2,\dots\)）。
则左群作用为映射 \(F\times X\rightarrow X\)（\(F\) 和 \(X\) 的笛卡尔积映射到 \(X\)）。我们可以认为群作用是一种运算，类似 \(f\cdot x_1=x_2\)。
群作用还要符合：\(f_1\cdot (f_2\cdot x)=(f_1*f_2)\cdot x\)。
注：如果定义为 \(X\times F\)，称为右群作用。不过在 OI 里不区分这个，后面默认是左群作用。
注 2：下面在无歧义的情况下把 \(f\cdot x_1\) 写作 \(f(x_1)\)。群作用和线段树上的 val 和 tag 很像。val 对应 \(X\)，tag 对应 \(G\)。
但线段树还要求 val 有加法运算，且对 tag × 有分配律。
同时线段树只要求是半群，不要求是群。例如 "整数，赋值" 可以放到线段树上，但是不是群。 -
轨道。定义在群作用上。
直观理解：某元素在所有变换下能变成的所有元素构成的集合。
形式化：对 \(x\in X\)，\(O_x=\{f(x)|f\in F\}\)。
【性质】
【拉格朗日定理】
因为不正规子群太难了，所以我们下面默认是正规子群，也就把左右陪集统称为陪集。下面用 \(G\) 指代原群集合，\(N\) 指代子群的集合。同时认为讨论限于有限群。
-
陪集与 \(N\) 大小相同。
对于 \(a_i,a_j\in N\)（\(a_i\neq a_j\)），若 \(b*a_i=b*a_j\)，则 \(b^{-1}*b*a_i=a_i=b^{-1}*b*a_j=a_j\)，矛盾。
-
陪集要么等于 \(N\)，要么和 \(N\) 交为空。
当 \(b\in N\)，因为子群的封闭性，\(bN=N\)。
当 \(b\not\in N\)，反设存在 \(b*a_i=a_j\)。\(b*a_i=a_j\Rightarrow b*a_i*a_i^{-1}=a_j*a_i^{-1}\Rightarrow b=a_j*a_i^{-1}\)。根据子群的定义，\(b\in N\)，矛盾。
-
所有陪集和 \(N\)，构成 \(G\) 的划分。
假设原群集合有一个 \(k\) 不在所有陪集和 \(N\) 中。根据子群定义，\(N\) 包含单位元。所以陪集 \(kN\) 包含 \(k\)。因为 \(G\) 是有限的，所以这样的陪集不能永远找下去。根据第二条性质，陪集和 \(N\) 构成 \(G\) 的划分。
于是我们得到了拉格朗日定理：
对于有限群 \((G,*)\)，其子群 \((H,*)\) 满足 \(|H|\) 是 \(|G|\) 的因数。
【置换群性质】
凯莱定理：\(n\) 阶有限群与某个 \(n\) 元素对称群的 \(n\) 阶子群同构。
证明：
考虑 \(G=(S,*)\)，\(|S|=n\)。取 \(S_1*S_{1\sim n}\)，记为 \(S_{i_1}\sim S_{i_n}\)。则 \(i_1\sim i_n\) 恰好是 \(1\sim n\) 的排列。
（或认为 "\(S_1*\)" 是 \(S\rightarrow S\) 双射）
记 \(x\rightarrow i_x\) 这 \(n\) 个小映射关系组成一个大的映射 \(f_1\)。
取 \(S_2*\) 得来的 \(i_1\sim i_n\)，组成 \(f_2\)，同理取 \(f_3\sim f_n\)。
那么 \(\{f_1\sim f_n,\text{复合}\}\) 与 \(G\) 同构。