群论

集合论

集合论是群论的基础,群论是建立在集合论上的。

集合的基本操作

集合的交

\[ A \cap B = \lbrace x \vert x \in A \wedge x \in B \rbrace \]

集合的并

\[ A \cup B = \lbrace x\vert x \in A \vee x \in B \rbrace \]

集合的笛卡尔积

注意到笛卡尔积是一个二元组。 \[ A \times B = \lbrace (x,y) \vert x \in A \wedge y \in B \rbrace \]

集合的映射

我们定义一个映射\(f\)满足 $f(x) = y $, 其中 \(x\in A\)\(y\in B\), 即映射可以把一个集合A中的元素映射到集合B中的一个元素。

可以称映射\(f\)作用于集合A,映射到集合B

群论

二元运算

给定集合\(A\),不难发现\(A\times A=\lbrace(x,y)\vert x\in A \vee y\in A\rbrace\)

给定映射\(f\)作用于集合\(A\times A\), 如果他依然映射到集合\(A\), 即 \[ \exists x\in A,\exists y\in A 满足f((x,y)) \in A \]\(f\)实现了二元运算,为了简化这种表示,我们常常使用符号\(x\circ y\)表示\(f((x,y))\)

半群

给定非空集合\(A\), 给定二元运算\(\circ\), 如果满足

  • 封闭性: \(\forall x \in A, \forall y \in A\), 都有\(x\circ y \in A\)

  • 结合律: \(\forall x \in A, \forall y \in A, \forall z \in A\),都有\((x\circ y)\circ z = x\circ( y \circ z)\)

则非空集合A和二元运算共同构成半群,也称\(\lbrace A:\circ\rbrace\)是一个半群。

幺半群

给定\(\lbrace A:\circ\rbrace\)是一个半群, 如果\(\exists e_1 \in A\)\(\forall x \in A\)都有\(e_1\circ x = x\), 则称\(e_1\)为左幺元,也称为左单位元。

给定\(\lbrace A:\circ\rbrace\)是一个半群, 如果\(\exists e_2 \in A\)\(\forall x \in A\)都有\(x\circ e_2 = x\), 则称\(e_2\)为右幺元,也称为右单位元。

给定\(\lbrace A:\circ\rbrace\)是一个半群, 如果左单位元与右单位元均存在,则\(\lbrace A:\circ\rbrace\)是一个幺半群。不难证明这时\(e_1=e_2\)(考虑\(e_1\circ e_2\)),所以我们常常称幺半群的单位元为\(e\)

需要注意的是如果右幺元不存在,左幺元存在,则左幺元不一定唯一,参考如下半群, 其中所有元素都是左单位元,且不存在右单位元。 \[ A=\lbrace a_1,a_2,a_3,a_4\rbrace, \\ f((x,y)) = y \]

给定\(\lbrace A:\circ\rbrace\)是一个幺半群,\(e\)为其单位元,如果\(\forall x \in A\),都\(\exists r_1 \in A\) 使得\(r_1\circ x=e\), 则称\(e_1\)为左逆元。

给定\(\lbrace A:\circ\rbrace\)是一个幺半群,\(e\)为其单位元,如果\(\forall x \in A\),都\(\exists r_2 \in A\) 使得\(x\circ r_2 =e\), 则称\(e_2\)为右逆元。

给定\(\lbrace A:\circ\rbrace\)是一个幺半群,如果\(\forall x \in A\),其左逆元和右逆元均存在,则\(\lbrace A:\circ\rbrace\)是一个群。不难证明此时\(r_1=r_2\)(考虑\(r_1\circ x\circ r_2\)), 所以我们常常称群的逆元为\(r\)

交换群

给定\(\lbrace A:\circ\rbrace\)是一个群,如果\(\forall x \in A , \forall y \in A\) 都有\(x\circ y = y\circ x\), 则称\(\lbrace A:\circ\rbrace\)是一个交换群。

整数模群

pass

素数模群

pass

置换群

给定一个排列\(P=\lbrace p_1,p_2,p_3...p_n\rbrace\), 定义映射规则 \[ \begin{aligned} 1 \to p_1\\ 2 \to p_2\\ 3 \to p_3\\ ...\\ n \to p_n \end{aligned} \] 于是我们得到了一个映射h,不妨把这个映射写做 \[ h=\begin{pmatrix} 1 & 2 & 3 &... &n\\\\ p_1 & p_2 & p_3 &... &p_n \end{pmatrix} \]

考虑排列的数量,我们一共有\(n!\)个映射,把这些映射构成的集合称为集合\(A\)

考虑映射的复合运算\(h(x)\)复合\(g(x)\)得到了\(h(g(x))\),我们也可写作\((h\circ g)(x)\), 我们把映射的复合运算称为\(f\),则\(f((h,g)) = (h \circ g)\)

不难证明\(\lbrace A:f\rbrace\)是一个群。我们常常称这个群为\(n\)元置换群。

当然大部分置换群不定是交换群。

循环乘积

循环乘积只是置换的另一种表示方法。

考虑一个置换,如果按照他的的映射规则把其中的整数连接起来,如下 \[ \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 3 & 1 & 6 &2 &4 &5 \end{pmatrix} \]

graph LR
1-->3-->6-->5-->4-->2-->1

他可以按照环的形式写作\((1\space3\space6\space5\space4 \space2)\)

如果连接以后,有些一多余的点 \[ \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 3 & 1 & 6 &4 &2 &5 \end{pmatrix} \]

graph LR
1-->3-->6-->5-->2-->1
4-->4

则可以写作\((1\space3\space6\space5\space2)\circ(4)\), 而其中长度为1的循环置换可以省略,故而也可写作\((1\space3\space6\space5\space2)\)

如果某些置换有多个环,比如下面这个置换。 \[ \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 2 & 1 & 3 &6 &4 &5 \end{pmatrix} \]

graph LR
3-->3
1-->2-->1
4-->6-->5-->4

对于这个置换,实际上他是两个置换的积,即 \[ \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 2 & 1 & 3 &6 &4 &5 \end{pmatrix}= \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 2 & 1 & 3 &4 &5 &6 \end{pmatrix}\circ \begin{pmatrix} 1 & 2 & 3 &4 &5 &6\\\\ 1 & 2 & 3 &6 &4 &5 \end{pmatrix} \] 而右边的两个置换可以分别写作\((2\space 1)\)\((4\space6\space5)\), 于是左边的置换理所当然的写成了\((2\space 1)\circ (4\space6\space5)\)

所以一个置换一定可以写成多个循环乘积的复合。

置换群的交换律

当两个置换的循环乘积表示法中,不存在相同的数字的时候,满足交换律。例如\((1\space2\space3)\circ(4\space5\space6)=(4\space5\space6)\circ (1\space2\space3)\), 以及\((1\space2\space3)\circ(1\space5\space6)\ne(1\space5\space6)\circ (1\space2\space3)\)

置换群的单位元

\((1)\circ(2)\circ(3)...(n)\)

置换群的逆元

对于置换 \[ h=\begin{pmatrix} 1 & 2 & 3 &... &n\\\\ p_1 & p_2 & p_3 &... &p_n \end{pmatrix} \] 其逆元为 \[ h=\begin{pmatrix} p_1 & p_2 & p_3 &... &p_n\\\\ 1 & 2 & 3 &... &n \end{pmatrix} \]

置换群的整数幂

考虑一个n元置换\(g\), 考虑\(g\circ g\), 不妨写作\(g^2\), 再考虑\(g\circ g\circ g\), 不妨写作\(g^3\), 如何快速计算\(g^k\)

解法1: 由于置换群满足结合律,所以可以直接使用快速幂算法,时间复杂度\(O(n\cdot log(k))\)

解法2: 对置换做幂,可将置换分解为不相交的循环乘积,然后分别做幂,最后合并,即如果\(g=g_1\circ g_2\), 则\(g^k=(g_1\circ g_2)^k=g_1^k\circ g_2^k\), 由于对循环乘积做幂,只需要在其对应的环上跳跃相同的长度即可,所以可以\(O(n)\)模拟,最终分解复杂度\(O(n)\),对循环乘积做幂复杂度\(O(n)\), 合并复杂度\(O(n)\),总复杂度\(O(n)\)

置换群的分数幂

考虑计算\(g^\frac{a}{b}\)

化简: \(g^\frac{a}{b}=(g^\frac{1}{b})^a\) 证明过程这里不做展开。

于是只需要计算\(g^\frac{1}{b}\)然后对其做整数幂即可。我们计算\((1\space2\space...n)^b\), 假设得到了\((a_1\space a_2\space ... a_n)\),由于循环乘积与数值无关,我们强制假设\((a_1\space a_2\space ... a_n)=g\),则可直接还原\(g^\frac{1}{b}\)