Revision | 抽象代数小常识

Posted on Edited on In

Abstract. 本文实际上是离散数学与结构上半学期的笔记整理。本课实际上包含了其他内容，比如朴素集合论中的势理论，命题逻辑，一阶逻辑及（不）完备定理，在合集 category: Discrete Math 中有所收录，不再重复。本文只写抽象代数的内容。

本文最后一节有许多定理的证明有待补充，包括后两条 Sylow 定理的证明，分裂域相关理论，和最后因子分解算法中关于 $\pm 1$ 出现概率均等的断言。

群论

群同态

定理 1.1.1（同态基本定理）. 对于 $G$ 到 $H$ 的同态 $f$，有

$$
G / \ker f \cong \mathrm{im~}f
$$

只需验证如下几个断言确实成立即可：

  1. $\ker f$ 是 $G$ 的正规子群。
  2. $\overline{f} : g\ker f \mapsto f(g)$ 是良定义的单射。

命题 1.1.2（对应定理）. $f$ 是 $G\rightarrow H$ 的满同态，那么对于 $f$ 给出了 $G$ 中包含 $\ker f$ 的全体子群到 $H$ 的全体子群间的双射，并且保持正规子群关系（i.e. $\ker f \subset G_1 \trianglelefteq G_2 \subset H \Rightarrow f(G_1)\trianglelefteq f(G_2)$）。

对于双射的断言，回忆双射的等价定义是左可逆并且右可逆。而我们知道 $G\mapsto f(G)$（求值域）有一个自然的逆就是求原像（记为 $f^-1$），只需要验证 $f^{-1}f(G’) = G’, f(f^{-1}(H’)) = H’$ 即可。关于保持正规子群关系的断言只需要对着定义验证即可。

此时对于 $G$ 的子群 $K$，考虑映射 $\eta : H \rightarrow H/f(K)$ 为到商群的自然映射。那么有

$$
\ker\eta f = K, \mathrm{im~}f = H/f(K)
$$

根据同态基本定理

$$
\color{red} G / K \cong H / f(K)
$$

定理 1.1.3（第一同构定理）. 设 $H, N$ 是 $G$ 的正规子群且 $H\subset N$，则有

$$
G/N \cong G/H {\Big/} N/H
$$

考虑 $G$ 到 $G/H$ 的自然映射 $\eta$。在 $(3)$ 中带入 $K\leftarrow N$ 立即得到结论。

定理 1.1.4（第二同构定理）. $N\trianglelefteq G, H\subset G$，则

  • $NH\subset G$；
  • $N\cap H \trianglelefteq H$；
  • $$
    NH / N \cong H / N\cap H
    $$

前两个断言只需要一些琐碎的验证。定义 $f : H \rightarrow NH / N$，其中 $f(k) = kH$，可知 $\ker f = N \cap H$。由于 $N$ 是正规子群，$nhN = hn’N = hN$，因此 $\mathrm{im~}f = NH / N$。

群对集合的作用

考虑群对自身的共轭作用 $a * x := axa^{-1}$。则轨道-稳定子定理指出：

$$
|G| = \sum_{x\in C} |Gx| = \sum_{x\in C} [G : \mathrm{Stab}(x)]
$$

其中 $C$ 是诸轨道（即共轭类）的代表元构成的集合。现在考察 $\mathrm{Stab}(x)$ 是什么。

$$
\mathrm{Stab}(x) = \{g\in G : gxg^{-1} = x\} = \{g\in G : gx = xg\}
$$

因此实际上 $\mathrm{Stab}(x)$ 就是 $x$ 的中心化子 $C(x)$。现在考察所有 $G$ 的中心中的元素的中心化子，容易发现是整个群。因此对于 $x\in C_G$ 有 $C(x) = G$, $[G : \mathrm{Stab}(x)] = 1$。于是我们得到了一个群的共轭类方程：

$$
|G| = |C| + \sum_{i} [G : C(y_i)]
$$

其中 $y_i$ 枚举所有大小非 $1$ 的共轭类的代表元。

命题 1.2.1. 任意 $p^k$ 阶群必然有 $>1$ 个元素，此处 $p$ 为素数。

考虑将共轭类方程两边同时模 $p$，立即得到 $p | |C|$。

命题 1.2.2. 任意 $p^2$ 阶群为 Abel 群。

证明.

考虑 $C \ne G$，取 $a\not\in C$，则有 $C \in C(a)$，并且 $a\in C(a)$，因此有 $1 < |C| < |C(a)|$，只能是 $|C(a)| = p^2$，这表明 $a\in C$，矛盾。于是不存在这样的元素，$C = G$。

Sylow 定理

定义 1.3.1 $G$ 是有限群，$p$ 是素数，若存在 $m > 0$，$p^m \mid |G| \wedge p^{m + 1} \nmid |G|$，则 $G$ 的 $p^m$ 阶子群称为 $G$ 的 $p$-Sylow 子群。

引理 1.3.2（Cauchy 引理）. $G$ 是有限 Abel 群，$p$ 是素数，$p \mid |G|$，则 $G$ 中存在 $p$ 阶元。

证明. 在 $G$ 中任取 $a\ne 0$（$0$ 是该阿贝尔群的单位元），现在考虑 $\mathrm{ord}(a)$。若 $p | \mathrm{ord}(a)$，那么 $\mathrm{ord}(a^{\mathrm{ord}(a) / p}) = p$。

否则 $G / \langle a\rangle$ 仍然满足上述条件，递归下去可以找到 $\mathrm{ord}(b\langle a\rangle) = p$，那么必然有 $p | \mathrm{ord}(b)$，有 $\mathrm{ord}(b^{\mathrm{ord}(b) / p}) = p$。

Sylow 第一定理指出 $p$-Sylow 子群的存在性。

定理 1.3.3（Sylow 第一定理）. 设 $G$ 是有限群，$p$ 是素数，若 $p^k \mid |G|$，则 $G$ 包含至少一个 $p^k$ 阶子群。

证明. 首先考虑 $G$ 的共轭类方程

$$
|G| = |C| + \sum [G : C(y_i)]
$$

若 $p \nmid |C|$，那么将等式两边模掉 $p$ 得到 $\sum [G : C(y_i)]\ne 0$，换言之存在 $y_i$，$p^k | C(y_i)$，递归到此子群中可以找到 $p^k$ 阶子群。

否则 $p \mid |C|$，根据 Cauchy 引理存在一个 $p$ 阶元 $a$。于是 $p^{k-1} \mid |G / \langle a\rangle|$，递归到其中可以找到一个 $p^{k-1}$ 阶子群 $H/\langle a\rangle$。此 $H$ 的大小正是 $|H| = |H/\langle a\rangle| \cdot |\langle a\rangle| = p^k$。

Sylow 第一定理的结论可以把 Cauchy 引理加强至任何群。首先说明存在 $p^k$ 阶群，然后群中自然有 $p$ 阶元。

定理 1.3.4（Sylow 第二定理）. $G$ 是有限群，素数 $p\mid |G|$。则

  1. $G$ 的任意两个 $p$-Sylow 子群都共轭。
  2. $G$ 的任意 $p^k$ 阶群均包含在某个 $p$-Sylow 子群中。

定理 1.3.5（Sylow 第三定理） 设 $|G| = p^k m$，$\gcd(p, m) = 1$。$G$ 的 $p$-Sylow 子群的个数 $n_p$ 满足

  1. $n_p | m$。
  2. $n_p \equiv 1\pmod p$。

证明没看。这两个定理有一个显然的推论：若 $G$ 只有一个 $p$-Sylow 子群，则该群必为正规子群。（似乎实际上某阶群只有一个则该群必然正规？）

上述结论可以用来推导一些神秘的低阶有限群相关结论：

Example 1. $20449=11^2 \cdot13^2$ 阶群是阿贝尔群。

证明.

用 Sylow 第三定理算出 $11^2$ 阶群和 $13^2$ 阶群都只有一个，因此这两个群是正规子群。这两个子群都是 $p^2$ 阶群，从而内部是交换的。因为这两个群阶数互质，所以是平凡交的，从而他们之间是交换的。

上面的推到中用到的经典结论：$N, H$ 是正规子群，且 $N\cap H = \{e\}$，那么 $\forall x\in N, y\in H, xy = yx$。

只需要证明 $xyx^{-1}y^{-1} = e$，这是因为 $(xyx^{-1})y\in H, x(yx^{-1}y^{-1})\in N$，从而 $xyx^{-1}y^{-1} \in H\cap N = \{e\}$。

Example 2. $15$ 阶群都是循环群。

证明.

用 Sylow 第三定理算出 $3$ 阶子群和 $5$ 阶子群恰好只有一个，从而其中 $3$ 阶元有 $2$ 个，$5$ 阶元有 $4$ 个，加上单位元，还有 $8$ 个元素的阶只能是 $15$，故其确实是循环群。

Example 3. $56$ 阶群都不是单群。

Example 4. $108$ 阶群都不是单群。

这两个例子都是用 Sylow 第三定理算每个 $p$-Sylow 子群的个数，必要时计算诸阶元的个数。

有限生成 Abel 群

定理 1.4.1（有限生成 Abel 群基本定理）. $G$ 是一个有限生成 Abel 群，那么 $G$ 可以分解成有限个循环群 $C_i$ 的直和：

$$
G = C_1 \oplus \cdots \oplus C_k
$$

证明. 假设 $G$ 可以由最少 $k$ 个元素生成，记为 $a_1, …, a_k$。考虑两种情况。

  • 不存在一个生成元集合，能够非平凡地表示 $0$ ，即对于整数 $x_1, …, x_k$，$\sum x_ia_i = 0$ 当且仅当 $x_1 = \cdots = x_k = 0$。这自然表明 $G$ 是 $\langle x_1\rangle\oplus \cdots\oplus \langle x_k\rangle$ 的内直和。

  • 存在生成元集合，能够非平凡地表示 $0$ ，设 $m_1$ 是考虑所有的生成元组、所有 $0$ 的表示中最小的正整数，不失一般性地假设 $m_1$ 在对应的 $0$ 的表示的 $a_1$ 的系数上，有

    $$
    m_1a_1 + \sum_{i=2}^k x_ia_i = 0
    $$

    对后面的元素做带余除法得到

    $$
    m_1a_1 + \sum_{i=2}^k (q_i m_1 + r_i) a_i = 0 \Rightarrow m_1 b_1 + \sum_{i=2}^k r_ia_i = 0
    $$

    其中 $b_1 = \sum_{i=2}^k q_ia_i + a_1$。现在 $b_1, …, b_k$ 可以生成 $G$，这是因为 $a_1$ 可以从 $b_1$ 反推。由于 $m_1$ 是所有生成元组中 $0$ 的坐标中的最小正整数，必然有 $r_2 = \cdots = r_k = 0$。于是 $m_1b_1 = 0$，且 $m_1$ 是可能的系数中最小的，因此 $|\langle x_1\rangle| = m_1$。我们证明 $\langle x_1\rangle \cap \langle x_2, …, x_k\rangle = \{0\}$。交集中的元素必然满足

    $$
    y_1 b_1 = \sum_{i=2}^{k}y_i a_1
    $$

    其中 $0 \leq y_1 < m_1$。若 $y_1$ 非零，则 $y_1b_1 - \sum_{i=2}^k y_ia_i$ 表示了 $0$，与 $m_1$ 的最小性矛盾，因此只能是 $y_1 = 0$，交集中的元素只有 $0$。递归下去分解 $\langle x_2, …, x_k\rangle$ 即得到 $G$ 的直和分解。

Remark. 在上述证明中，可以发现“最小性”处处发挥关键作用。

进一步可以证明这种分解在置换和同构的意义下是唯一的。

环论

环 $(R, +, \cdot)$ 可能具有的性质：

  • 交换环 $\forall a, b\in R, ab = ba$。
  • 含幺环 $\exists 1\ne 0, \forall a, a\cdot 1 = 1\cdot a = a$。
  • 除环 $\forall a\ne 0, \exists a^{-1}， aa^{-1} = a^{-1}a = 1$。
  • 无零因子 不包含非平凡零因子（参见定义 $2.1$）。
  • 整环 含幺无零因子交换环。

可以简单地推导如下命题：整环有消去律。这是因为若 $a\ne 0 \wedge ab = ac$，那么 $a(b - c) = 0$。因为环中没有零因子，$a\ne 0$，所以只能是 $b - c = 0$，即 $b = c$。

域系指交换的除环。事实上存在非交换的除环，比如实四元数环。

定义 2.1（零因子）. 若存在 $ab = 0$ 且 $a, b\ne 0$，则称 $a, b$ 为非平凡零因子，$a$ 称为左零因子，$b$ 称为右零因子。

注意环定义时只要求 $\cdot$ 是半群，所以不一定有逆元。对于一些元素，可能有左逆元或者右逆元，且有左逆元不一定有右逆元。若 $a$ 的左逆元等于右逆元，则称 $a$ 是群中的一个单位，此时可以证明其逆元唯一。

在加法和乘法意义下均封闭的子集称为子环。

我们希望环也可以像群一样做商，于是需要找到一类最弱的性质使得在加法群中商掉一个子集，能够保持乘法运算。因此定义

定义 2.2（理想）. $I$ 是 $(R, +)$ 的子群，满足 $\forall r\in R, a\in I$ 都有 $ar\in I, ra\in I$，则称 $I$ 是 $R$ 的理想。

不难验证定义 $R/I$ 上的加法 $(a+I) + (b + I) = (a + b) + I$，乘法 $(a + I)\otimes (b + I) = ab + I$ 之后，$(R/I, +, \cdot)$ 构成环。称为商环。

环同态

环同态的定义是常规的。容易验证

命题 2.1.1. 对于环同态 $\varphi: R_1\rightarrow R_2$，有 $\mathrm{im~}\varphi$ 是 $R_2$ 的子环，$\ker\varphi$ 是 $R_1$ 的理想。

可以证明下面几个同态相关的定理，一切仿造群同态基本定理、对应定理和第一及第二同构定理的证明。

定理 2.1.2.

  1. $R / \ker\varphi \cong \mathrm{im~}\varphi$
  2. $A$ 是 $R$ 的子环，$B$ 是 $R$ 的理想，则 $A + B$ 是一个子环，$A\cap B$ 是 $A$ 的理想，并且 $(A + B) / B \cong A / A\cap B$
  3. $I$ 是 $R$ 的理想，存在 $R$ 中包含 $I$ 的子环到 $R/I$ 中的子环的双射（此双射正是自然映射 $\eta$）
  4. $I, J$ 都是 $R$ 的理想，$I\subset J$，则 $J/I$ 是 $R/I$ 的理想，且 $R/J \cong (R/I) / (J/I)$

定义一个集合 $S$ 生成的理想为：$(S) = \bigcap\limits_{S\subset I, I\text{ an ideal}} I$。

若一个理想可以有单元素集合生成，则称为主理想。

Gauss 整环，主理想整环，欧几里得整环

本节讨论几个性质介于整环和域之间的特殊环。

第一类环上可以做唯一分解。需要注意的是环的元素没有定义大小关系，所以我们需要仔细考虑如何定义“真因子”的概念。可以发现环中存在一类元素是所有数的因子，这类元素无非是可逆元（$u | 1$ 表明 $u$ 可逆，而 $au^{-1}u = a$ 表明 $u | a$）。这类元素对因数分解而言没有意义（比如 $\mathbb{Z}$ 中的 $\pm 1$，和 $\mathbb{R}[x]$ 中的非零实数）

若 $a | b$ 且 $b | a$，则 $a = br, b = as$，于是 $a = ars$，消去 $a$ 得到 $rs=1$，因此 $r, s$ 是单位。这表明互相整除的数必然只相差单位。若 $a=ub$，其中 $u$ 是单位，则称 $a, b$ 是相伴元，记作 $a\sim b$。非相伴元的整除关系都是真整除关系。

若 $a$ 非单位且不能分解成两个真因子的乘积，则称 $a$ 为不可约元。若非单位元 $p$ 满足 $p \mid ab$ 则 $p\mid a$ 或 $p\mid b$，则称 $p$ 是素元。

定义 2.2.1（Gauss 整环 / UFD） $R$ 是整环，$r$ 中的非单位元素都可以写成有限个非单位不可约元素的乘积：$r = p_1p_2\cdots p_s$，且若 $r = p_1\cdots p_s=q_1\cdots q_r$，则 $r=s$ 且存在置换 $\Pi$ 使得 $p_i \sim q_{\Pi_i}$，则称 $R$ 是唯一分解整环（UFD）或者高斯整环。

存在不是 UFD 的整环。

Example. 在 $\mathbb{Z}[\sqrt{-5}]$ 中有 $9 = 3\cdot 3 = (2 + \sqrt{-5})(2-\sqrt{-5})$。但是 $3, 2 + \sqrt{-5}, 2-\sqrt{-5}$ 均不可约。

此处不可约性的证明采用一种常见的手法：对环中的元素定义“范数”为 $|a + b\sqrt{-5}|^2 = a^2 + 5b^2$，可以发现两元素相乘范数也相乘，且范数是正整数，于是只需要枚举所有范数不超过 $9$ 的元素，发现乘起来均不是上述三元之一。

这同时也表明在通常的环中素元和不可约元不是等价的概念。$3$ 是不可约的，但 $3$ 不是素元：$3 | (2 + \sqrt{-5})(2-\sqrt{-5})$。

引理 2.2.2. $R$ 是 UFD，当且仅当 $R$ 满足

  • 因子链条件 不存在 $d_1, d_2, …$ 使得 $d_{i + 1} \mid d_i$ 且 $d_i\nmid d_{i + 1}$。
  • 素性条件 $R$ 中的不可约元都是素元。

证明. 必要性是平凡的，我们只证明充分性。

任意元素的有限因子分解是存在的，因为我们可以给出算法。

而分解实际上也是唯一的。施归纳于 $a$ 的分解中最短的一个的长度。若长度为 $0$ 即元素不可约，结论显然成立。考虑 $a = p_1\cdots p_s = q_1\cdots q_r$。则有 $p_1 | q_1\cdots q_r$，用素性条件可以递归找到某个 $p_1 | q_i$，而 $q_i$ 不可约，所以 $p_1\sim q_i$。不失一般性假设 $p_1\sim q_1$，消去 $p_1$ 得到 $p_2\cdots p_s = uq_2\cdots q_r$，用归纳假设即得后面的分解是等价的，因此所有的分解都是等价的。

两元素 $g$ 是 $a, b$ 的最大公因数若 $\forall d, (d \mid a \wedge d \mid b)\rightarrow d \mid g$。从所有最大公因子中任取一个，构造二元函数 $\gcd(a, b)$。

现在 UFD 中的任意两元素均能求最大公因数，只需求因子分解然后将指标取 $\mid$ 即可，因为容易将整除关系转化成指标的偏序关系。实际上环中任意两元素都有 $\gcd$ 强于素性条件：

引理 2.2.3. 若环中任意两元素都能求 $\gcd$，则对于不可约元素 $p$，$p\mid ab\Rightarrow p\mid a\vee p\mid b$。

证明. 首先验证几个简单的等式，思路基本上都是简单粗暴的。

  1. $\gcd(\gcd(a, b), c)\sim\gcd(a, \gcd(b, c))$
  2. $c\gcd(a, b)\sim \gcd(ca, cb)$
  3. $\gcd(a, b)\sim 1\wedge \gcd(a, c)\sim 1\Rightarrow \gcd(a, bc)\sim 1$

然后用第三条反证即可。

综上所述，因子链条件 + 素性条件 等价于 因子链条件 + $\gcd$ 条件，这两个组合形成两种等价的 UFD 判定定理。

关注 $(a)$ 本身，实际上 $(a) = \{ca : c\in R\}$，即 $a$ 的倍数的全体。这表明整除关系自然地转化成两个元素生成的理想的判定关系。从这个层面上考察上面的 UFD 的判定定理（使用 $\gcd$ 条件），这似乎是在说若干个元素生成的理想都可以被他们的 $\gcd$ 生成。这启发我们定义一个更强的环

定义 2.2.5（主理想整环）. 若整环 $R$ 满足其所有理想都是主理想，则称 $R$ 是主理想整环（PID，Principle Ideal Ring）。

上课给的证明路线有点奇怪，我们先给出一个比较自然的证明。

定理 2.2.6. PID 都是 UFD。

证明. 只需要证明 PID 也满足因子链条件和 $\gcd$ 条件。

  • 假设存在 $d_1, d_2, …$ 使得 $d_{i + 1} \mid d_{i}\wedge d_i \nmid d_{i + 1}$，等价的表达是存在 $d_1, d_2, …$ 满足其所有理想都是主理想

    $$
    (d_1)\subsetneq (d_2) \subsetneq \cdots
    $$

    那么假设

    $$
    \bigcap_{i = 1}^{\infty} (d_i) = (a)
    $$

    这是因为理想的可数并必然也是理想，那么必然有某个 $N$ 使得 $a\in (d_N)$，于是对于任意的 $i > N$ 都有

    $$
    (a) \subseteq (d_N) \subsetneq (d_i) \subset (a)
    $$

    矛盾，此链并不存在。

  • 只需证明 $(\{a, b\})$ 是由 $g$ 生成的理想，此 $g$ 正是 $\gcd(a, b)$。只需要对着定义验证即可。

上课的奇怪证明出发点是证明素性条件。$p$ 是不可约元素表明 $(p)$ 是极大理想，考察考察环模掉极大理想的性质

引理 2.2.7. 对于交换环 $R, F$ 有

  1. $F$ 是一个域当且仅当它只有平凡的理想。
  2. $I$ 是 $R$ 的极大理想当且仅当 $R / I$ 是域。

证明.

  1. 必要性：考虑理想 $I$，若其中含有非零元，则 $1 = a^{-1}\cdot a\in I$，于是 $a = a\cdot 1\in I$，$I$ 必平凡。

    充分性：若元素 $a$ 不可逆，那么 $(a)$ 不包含 $1$，这是一个非平凡理想，矛盾。

  2. 两个方向可以简单地从断言 1 推出。

利用这个结论，我们知道 $R / (p)$ 必然是域，因此 $p | ab$ 推出 $ab \in (p)$，这表明 $ab + (p) = (a + (p))(b + (p))$，但是域中没有非平凡零因子，只能是 $a\in (p)$ 或者 $b\in (p)$，这样也证明了结论。

回忆求 $\gcd$ 的常用方法是辗转相除，于是我们考察一类环：

定义 2.2.7（欧几里得整环）. 若环 $R$ 上可以定义一个赋值 $\delta : R \setminus \{0\}\rightarrow \mathbb{N}$，满足如下条件：

  • 对于任意的 $a$，$\delta(a)\leq \delta(ab)$。
  • 对于任意的 $a$ 和非零元 $b$，都存在 $r$ 满足 $r=0$ 或者 $\delta(r) < \delta(b)$，且 $a = bq + r$。

则称 $R$ 为欧几里得整环。

整数环的 $\delta$ 定义为常函数，多项式环的 $\delta$ 定义为 $\deg$，都是欧几里得整环。

定理 2.2.8 欧几里得整环都是 PID。

证明. 考虑一个非零理想 $I$，取其中 $\delta$ 最小的元素 $b$，那么对于任意的元素 $a$ 都有 $a = bq$（因为 $\delta(r)$ 不可能小于 $\delta(b)$，只能取 $0$），因此 $I = (b)$。

域自然都是欧几里得整环，因为所有非零元都可逆。

综上所述我们有如下一条链：

$$
\text{Integer domain} \leftarrow \text{UFD} \leftarrow \text{PID} \leftarrow \text{Euclidean Ring} \leftarrow \text{Field}
$$

域论

基本概念

定义 3.1.1（环的特征）. 对于无零因子环 $R$，若其中存在至少一个周期元，则存在素数 $p$ 使得 $\forall r\in R, pr = 0$。$p$ 称为 $R$ 的特征。若 $R$ 中无周期元，则称 $R$ 的特征为 $0$。

域是特殊的环。因此特征也可以定义在域上。

定理 3.1.2. 无零因子环 $R$ 的特征要么是 $0$，要么是素数。

证明. 我们先断言若对于 $a\ne 0$，若 $ma = 0$ 则 $\forall b\in R, mb = 0$。这是因为根据分配律，$(ma)b = a(mb) = 0$，环中没有非平凡零因子，所以 $mb = 0$。

接下来我们证明最小的 $m$ 一定是素数。我们取 $m$ 为使得 $ma = 0$ 的正整数中的最小者，若 $m = pq$（非平凡分解）则 $q(pa) = 0$，$m$ 的最小性导出 $p > m$，同理 $q > m$，矛盾。

上述推导同时表明域的特征是使得 $m\overline{1} = 0$ 成立的最小正整数，若不存在则为 $0$。其中 $\overline{1}$ 是域的单位元。

对于整环 $R$，可以定义其“分式域”为 $F = (R\times R) / \sim$，其中 $(a, b)\sim (c, d) := ad = bc$，运算性质类似于分数运算，因为非常常规所以不赘述。一个域到其分式域有一个自然的同态：$r \mapsto (r, 1)$，称为标准嵌入。

关于分式域，我们只强调如下泛性质

定理 3.1.3. 设 $R$ 是整环，$F$ 是其分式域，$F’$ 是域，$f$ 是 $R$ 到 $F$ 的标准嵌入，$g$ 是 $R\rightarrow F’$ 的单同态，且 $g(1) = 1$，则存在唯一的 $F$ 到 $F’$ 的同态使得 $g = hf$。

证明. 令 $h(a / b) = g(a)g(b)^{-1}$，接下来只需要一些平凡的验证工作即可说明其是良定义的同态，并且唯一。

若一个域 $F$ 的特征为 $0$，则由单位元 $\overline{1}$ 用加法生成了一个同构于 $\mathbb{Z}$ 的整环，那么上述结论表明存在 $\mathbb{Z}$ 的分式域即 $\mathbb{Q}$ 到 $F$ 的同态，你可以验证这个同态是单的，特征为 $0$ 的域中必存在同构于有理数域的子域。

本课程中我们重点讨论有限域，下面是一个特殊的有限域：

$\mathbb{F}_p$ 是域 $\mathbb{Z} / p\mathbb{Z}$，$f$ 是 $\mathbb{F}_p[x]$ 上的不可约多项式，因此 $(f)$ 是极大理想，从而 $\mathbb{F}_p[x] / (f)$ 是域。不难看出其大小为 $p^{\deg f}$，正是某素数的幂。我们将证明任意有限域的幂都是素数的幂、并且相同大小的有限域都是同构的，并讲一些有限域上的多项式相关的内容（包括一个多项式分解算法）。

域的扩张

定义 3.2.1（域的扩张）. 设 $F, L$ 是两个域。若 $F\subset L$，我们称

  • $F$ 是 $L$ 的子域。
  • $L$ 是 $F$ 的扩域。

记作 $L / F$。可以验证 $L$ 是 $F$ 上的线性空间。定义 $[L : F]$ 表示其维数。

若 $[E : F]$ 有限，则称 $E$ 是 $F$ 的有限扩张。对于有限扩张，我们有如下结论，经常用于研究两个域之间是否存在其他的子域。

定理 3.2.2. 设 $K/E$，$E/F$ 都是有限扩张，那么

$$
[K : F] = [K : E][E : F]
$$

证明. 取 $K/E$ 的一组基 $u_1, …, u_n$，$E/F$ 的一组基 $v_1, …, v_m$。那么对于 $K$ 中的元素 $k$，有

$$
\begin{aligned}
k &= \sum_{i=1}^n e_i u_i \\
&= \sum_{i=1}^n\sum_{j=1}^n f_{ij} u_iv_j
\end{aligned}
$$

而 $k = 0$ 推出所有 $e_i = 0$，$e_i = 0$ 推出所有 $f_{ij} = 0$，因此 $\{u_iv_j\}$ 是 $K$ 的一组基。

记 $F(S)$ 表示包含域 $F$ 和集合 $S$ 的最小域。则 $F(S) / F$。若 $S$ 中只有一个元素 $s$，可以简单地记为 $F(s)$。此时 $F(s)$ 称为一个单扩张。

对于 $u$，定义映射 $\varphi : F[x] \rightarrow F[u]$，仅仅将 $x$ 替换为 $u$。若 $\varphi$ 是单射，称 $u$ 为 $F$ 的超越元，否则称为代数元。若 $E / F$，$E$ 中所有元素都是 $F$ 的代数元，则称 $E$ 为代数扩张，反之称为超越扩张。对于代数元，取 $\ker \varphi$ 中 $\deg$ 最小的多项式，得到该元的最小多项式。最小多项式的度数即指出线性空间 $\langle 1, u, u^2, …\rangle$ 的维数，因此有限扩张都是代数扩张，反过来，关于代数元的单扩张一定是有限扩张。

有限域

上节的引理 2.2.7 指出域有限域 $\mathbb{F}_p$ 上的不可约多项式 $f$ 生成极大理想，因此 $\mathbb{F}_p[x] / (f)$ 是一个域，这个域的大小无非是 $p^{\deg f}$，称为 $GF(p^k)$。我们定义这个记号的原因是下面的一系列结论：我们将证明任意有限域的幂都是素数的幂，且大小相同的有限域彼此同构。

定理 3.3.1. 有限域的维数必然是某个素数的幂 $p^k$。

证明. 有限域的特征 $\mathrm{char~} F = p$，因此单位元 $\overline{1}$ 生成一个同构于 $\mathbb{Z}_p$ 的子域，于是 $F / \mathbb{Z}_p$。若 $[F : \mathbb{Z}_p] = k$，则 $|F| = p^k$。

在群中，我们有 Fermat 小定理，而域的乘法在非单位元上构成群，这启发我们：

引理 3.3.2. 若 $|F| = p^k$，那么 $\forall x\in F, (x^{p^{k} - 1} - 1)x = 0$。

重复关于多项式的分解和根的关系的论证，我们得到

引理 3.3.3. 若 $|F| = p^k$，那么

$$
x^{p^k} - x = \prod_{a\in F} (x - a)
$$

证明. 将每个元素带入验证得到 $(x - a) \mid x^{p^k} - x$，$(x - a)$ 均是 $F[x]$ 中的不可约元，对比两边的度数立即知道上式成立

引理 3.3.4. 若 $f\in F[x]$ 是度数为 $d$ 的不可约多项式，那么 $f \mid x^{|F|^d} - x$。

证明. 令 $L = F[x] / (f)$，则 $L$ 是 $F$ 的扩域，$|L| = {|F|^d}$。我们知道

$$
x^{|L|} - x = \prod_{a\in L} (x - a)
$$

因为 $\overline{x}\in L$，所以 $x - \overline{x} \mid x^{|L|} - x$。同时 $f(\overline{x}) = 0$，因此 $x - \overline{x} | f$。

这表明 $\deg \gcd(f, x^{|L|}- x) > 0$，经典结论指出扩域不会改变 $\gcd$，因此 $\gcd(f, x^{|L|} - x)$ 只能是 $f$（因为 $f$ 在 $F[x]$ 中不可约）。

定理 3.3.5. 设 $F$ 是有限域，其中 $|F| = q$，令 $L = F[x] / (f)$，$f$ 是度数为 $d$ 的不可约多项式。则对于任意的 $K$ 满足 $K/F$ 且 $[K : F] = d$，都有 $L\cong K$。

证明. 首先知道 $|K| = p^d$，进而

$$
x^{p^d} - x = \prod_{a\in K} (x - a)
$$

由引理 3.3.4，$f | x^{p^d} - x$。这表明 $f = \prod_{a_i\in K}(x - a_i)$，我们得到了 $f(a_1) = 0$。

定义映射 $\varphi : F[x]\rightarrow K$ 为 $h \mapsto h(a_i)$。则

$$
\begin{align}
g \in \ker \varphi &\Leftrightarrow g(a_1) = 0 \\
&\Leftrightarrow (x - a_1) | g \\
&\Leftrightarrow \gcd(g, f)\ne 1 \\
&\Leftrightarrow \gcd(f, g) = f \\
&\Leftrightarrow g \in (f)
\end{align}
$$

于是 $\ker \varphi = (f)$，因此 $F[x] / (f) \cong \mathrm{im~} \varphi\subset K$，然而 $|\mathrm{im~}\varphi| = |F[x] / (f)| = p^d = |K|$，所以 $\mathrm{im~}\varphi = K$。

现在一切归结为对于任意的 $k$ 都存在度为 $k$ 的不可约多项式。我们之前已经证明了对于任意的不可约的 $f$ 都有 $f \mid x^{|F|^d} - x$。我们仍然考虑这个重要的多项式。

引理 3.3.6. 对于不可约多项式 $f$，若 $\deg f\mid k$，则 $f \mid x^{p^k} - x$。

证明. 我们知道 $f\mid x^{p^{\deg f}} - x$。现在要证明 $x^{p^{\deg f}} - x | x^{p^k} - x$，我们容易证明 $a^{p^{\deg f}} - a = 0 \Rightarrow a^{p^k} - a = 0$。如果 $x^{p^{\deg f}} - x$ 能在某个域下被分解成一次多项式的乘积，那么就做完了。事实上确实是这样的，此扩域称为 $x^{p^{\deg f}} - x$ 的分裂域。考试前我们暂时放弃考察分裂域的相关理论。

至此已经可以知道所有的 $k$ 阶不可约多项式都存在：可以在 $x^{p^k} - x$ 中找到。于是我们可以结合定理 3.3.5 下断言：所有的大小为 $p^k$ 的域都同构，桥梁是某个不可约多项式给出的 $F[x] / (f)$。但实际上 $x^{p^k}$ 的性质非常好，我们还有：

引理 3.3.7. 对于不可约多项式 $f$，若 $f \mid x^{p^k} - x$，则 $\deg f \mid k$。

证明. $\color{red} \text{Admit.}$

引理 3.3.8. $x^{p^k} - x$ 没有平方因子。

证明. 考虑 $\gcd(x^{p^k} - x, (x^{p^k} - x)’) = 1$。若 $x^{p^k} - x = f^2g$，则 $(f^2g)’ = f(2g + fg’)$，故至少平方因子 $f$ 整除该 $\gcd$，但 $\gcd$ 是 $1$。

综上得到了

$$
x^{p^k} - x = \prod_{\text{$f$ is irreducible and monic, and $\deg f\mid k$}} f(x)
$$

这个反复出现的多项式连同其性质在解决许多问题中发挥了至关重要的作用。

有限域上多项式的因子分解算法

我们的任务是在多项式时间内高概率给出多项式环 $F[x]$ 上的多项式 $f$ 的一个非平凡因子。此处 $F$ 是有限域。我们的算法分为三种情况：

$f$ 含有平方因子 此时输出 $\gcd(f, f’)$ 即可。

$f$ 的因子度数不同 假设存在 $f_1, f_2 \mid f$，且 $\deg f_1 < \deg f_2$。那么 $f_1 | \gcd(f, x^{p^{\deg f_1}} - x)$，但 $28$ 式表明这个 $\gcd$ 并非 $f$。

$f$ 的因子度数均相同 设 $f = f_1\cdot f_k$，$\deg f_i = d$。则根据中国剩余定理，$F[x] / (f)\cong F[x] / (f_1)\times\cdots\times F[x] / (f_k)$。那么我们在 $F[x] / (f)$ 中随机采样多项式 $r$。则

$$
f_i | r^{p^d - 1} - 1 \quad \text{s.t.} \quad r^{p^d - 1} \equiv 1\pmod {f_i}
$$

于是

$$
r^{\frac{p^d - 1}{2}} \equiv \pm 1 \pmod {f_i}
$$

并且可以证明结果是 $1$ 和 $-1$ 的概率是均等的。这是我们求 $\gcd(r^{\frac{p^d - 1}{2}}, f)$，只有下面两种情况我们得不到$f$ 的非平凡因子：

  • 所有的 $r^{\frac{p^d - 1}{2}} \bmod f_i$ 都是 $1$。
  • $r^{\frac{p^d - 1}{2}}\bmod f = -1$。

因此成功概率为 $1 - 2^{1-\deg f / d}$，高概率成功。