群论(Group Theory)

群的定义

设 GG 为非空集合，其上有二元运算⋅:G×G→G\cdot :G \times G \to G，如果它们满足以下性质，则称 (G,⋅)(G,\cdot )是一个群(group)，简称群 GG：

  1. 结合律：∀a,b,c∈G,a⋅(b⋅c)=(a⋅b)⋅c\forall a,b,c \in G,a \cdot (b \cdot c) = (a \cdot b) \cdot c.
  2. 有单位元：∃e∈G,∀a∈G,a⋅e=e⋅a=a\exists e \in G,\forall a \in G,a \cdot e = e \cdot a = a.这里ee被称为群GG的单位元，也可称作幺元.
  3. 有逆元：∀a∈G,∃b∈G,a⋅b=b⋅a=e\forall a \in G,\exists b \in G,a \cdot b=b \cdot a=e.这里bb被称为aa的逆元，也可以记作a−1a^{-1}.

额外地：
任何一个群还应满足封闭性条件：∀a,b∈G,a⋅b∈G\forall a,b \in G,a \cdot b \in G.上面定义的二元运算⋅\cdot已经隐含了封闭性条件.
4. 若群GG满足交换律：∀a,b∈G,a⋅b=b⋅a\forall a,b \in G,a\cdot b=b\cdot a，则称群GG为交换群或Abel 群.
若群GG仅满足 1，则称 (G,⋅)(G,\cdot ) 为半群.
若群GG仅满足 1,2，则称 (G,⋅)(G,\cdot ) 为幺半群.
若群GG仅满足 1,2,4，则称 (G,⋅)(G,\cdot ) 为交换幺半群或Abel 幺半群.

群的基本性质

对于群(G,⋅)(G,\cdot)，以下性质总是成立：

  1. 对于任何有限长的列 {gi}i=1k⊆G\{g_i\}^{k}_{i=1} \subseteq G，积 ∏i=1kgi=g1⋅g2⋅⋯⋅gk\prod_{i=1}^{k}g_i = g_1 \cdot g_2 \cdot \cdots \cdot g_k 的运算结果与加括号的方式无关.
  2. ∃!e∈G\exists!e\in G.
  3. ∀a∈G,∃!a−1\forall a \in G,\exists!a^{-1}.
  4. 消去律：∀a,b,c∈G,\forall a,b,c\in G,若a⋅c=b⋅ca \cdot c=b \cdot c或c⋅a=c⋅bc \cdot a=c \cdot b，则a=ba=b.一个可消去的元素是可逆的.

群的例子

  • 整数集Z\mathbb{Z}在加法++运算下构成 Abel 群(Z,+)(\mathbb{Z},+)，单位元为00，对于Z\mathbb{Z}中的任意元素，其逆元为它的相反数.
  • 对于任意正三角形的可重合旋转操作，可以构成空间对称群.对于任意几何图形，能够使其与自身重合的变换全体也在映射的复合下构成群.

想要验证以上群的例子，只要根据群的定义进行验证即可.
再给出两个数集中的反例：

  • 整数在乘法下并不构成群，因为其中不属于{−1,0,1}\{-1,0,1\}的元素在整数范围内没有乘法逆元.
  • 正整数在加法下不构成群，因为正整数没有加法单位元.

子群

子群的定义

对于群 (G,⋅)(G,\cdot) 和它的一个子集 H⊆GH\subseteq G，如果 (H,⋅)(H,\cdot) 也是一个群，则称子集 HH 是 GG 的一个子群.可记为H≤GH\le G.

子群的验证

要判断给定子集 H⊆GH\subseteq G 是不是 GG的子群，并不需要逐一验证群的定义：结合律一定成立，只要保证它对二元运算封闭、有单位元且对取逆封闭即可.即满足以下条件：

∀g,h∈H,g−1⋅h∈H\forall g,h\in H,g^{-1}\cdot h\in H

由子集生成的子群

一般地，对于群 (G,⋅)(G,\cdot)，给定子集 S∈GS\in G ，从 SS 中的元素出发，重复进行乘法和取逆运算有限次得到的所有结果组成的集合成为 群(G,⋅)(G,\cdot) 的一个子群，称为由子集 SS 生成的子群.

对于群 (G,⋅)(G,\cdot) 和 GG 的非空子集 S⊆GS\subseteq G，若 HH 是包含 SS 的 GG 的子群中按包含关系最小的，则子群 HH 为由子集 SS 生成的子群，并记作 ⟨S⟩\langle S\rangle.

特别地，若 card(S)=1card(S)=1，则 ⟨S⟩\langle S\rangle 也记作 ⟨x⟩\langle x\rangle，称为 xx 的幂的循环子群.

循环群

对于群 GG ，若 ∃x∈G,G=⟨x⟩\exists x\in G,G=\langle x\rangle，则称群GG是一个循环群.如果群 (G,⋅)(G,\cdot) 的子集 S⊆GS\subseteq G 满足 ⟨S⟩=G\langle S\rangle=G，则称 SS 是 GG 的 生成子集.生成子集 SS 中的元素称为生成元.

所有的循环群都是 Abel 群.但即使群的所有非平凡子群都是循环群，群本身也可能不是 Abel 群.

对称群

置换

若S={1,2,...,n}S=\{1,2,...,n\}，则从SS到自身的双射σ:S→S\sigma:S\to S被称为SS的一个置换.该映射是可逆的.

若card(S)=ncard(S)=n，那么，SS上的全体置换的数量就是 n!n!.

特别地，0!=10!=1，即空集合上有且仅有一个置换，即空置换.置换讨论的是元素间的对应关系，而并不关心元素具体是什么.当讨论大小为nn的集合时，通常假定讨论的集合就是{1,2,...,n}\{1,2,...,n\}.

对称群的定义

集合 SS 上的全体置换在映射的复合运算下构成群，称为 SS 的对称群，记作 Sym(S)\mathrm{Sym}(S).

当 S={1,2,...,n}S=\{1,2,...,n\} 时，对称群 Sym(S)\mathrm{Sym}(S) 也记作 SnS_n，称为 nn 次对称群.

对称群 SnS_n 的阶为 n!n!.

置换的表示

置换通常有两种表示方法：

  1. 双行表示法：将置换 σ\sigma 表示为 (12⋯nσ(1)σ(2)⋯σ(n))\begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}

  2. 轮换表示法：将置换表示为若干个不相交轮换的乘积.例如，(1 3 2)(1\ 3\ 2) 表示 1↦3↦2↦11 \mapsto 3 \mapsto 2 \mapsto 1 的轮换.

轮换和对换

一个长度为 kk 的轮换是指将 kk 个元素按环状排列的置换.长度为 22 的轮换称为对换.

任何置换都可以表示为若干个不相交轮换的乘积，也可以表示为对换的乘积.

阶

群的阶

群 GG 中元素的个数称为群 GG 的阶，记作 ∣G∣|G| 或 ord(G)\mathrm{ord}(G).

若群 GG 中元素个数有限，则称 GG 为有限群；否则称为无限群.

元素的阶

对于群 GG 中的元素 gg，使得 gk=eg^k = e（其中 ee 是单位元）成立的最小正整数 kk 称为元素 gg 的阶，记作 ord(g)\mathrm{ord}(g).

若不存在这样的正整数 kk，则称元素 gg 的阶为无穷.

拉格朗日定理

拉格朗日定理：设 GG 是有限群，HH 是 GG 的子群，则 ∣H∣|H| 整除 ∣G∣|G|.

推论：有限群中任意元素的阶整除群的阶.

群上离散对数

在循环群 G=⟨g⟩G = \langle g \rangle 中，对于任意元素 h∈Gh \in G，存在整数 xx 使得 gx=hg^x = h.

这个整数 xx 称为以 gg 为底的 hh 的离散对数，记作 x=log⁡ghx = \log_g h.

离散对数的性质

  1. log⁡g(h1h2)=log⁡gh1+log⁡gh2\log_g(h_1 h_2) = \log_g h_1 + \log_g h_2
  2. log⁡g(hk)=klog⁡gh\log_g(h^k) = k \log_g h
  3. 在有限循环群中，离散对数在模群的阶意义下是唯一的

离散对数问题

离散对数问题(DLP)：给定循环群 GG、生成元 gg 和元素 h∈Gh \in G，求解整数 xx 使得 gx=hg^x = h.

这个问题在某些群中被认为是困难的，是现代密码学的基础之一.

环论(Ring Theory)

环的定义

设 RR 为非空集合，其上有两个二元运算：加法 +:R×R→R+: R \times R \to R 和乘法 ⋅:R×R→R\cdot: R \times R \to R，如果它们满足以下性质，则称 (R,+,⋅)(R,+,\cdot) 是一个环(ring)：

  1. (R,+)(R,+) 是 Abel 群
  2. 乘法满足结合律：∀a,b,c∈R,a⋅(b⋅c)=(a⋅b)⋅c\forall a,b,c \in R, a \cdot (b \cdot c) = (a \cdot b) \cdot c
  3. 分配律：∀a,b,c∈R\forall a,b,c \in R，有
    • 左分配律：a⋅(b+c)=a⋅b+a⋅ca \cdot (b + c) = a \cdot b + a \cdot c
    • 右分配律：(a+b)⋅c=a⋅c+b⋅c(a + b) \cdot c = a \cdot c + b \cdot c

如果环 RR 的乘法运算还满足交换律，则称 RR 为交换环.

如果环 RR 有乘法单位元 11（即 ∀a∈R,1⋅a=a⋅1=a\forall a \in R, 1 \cdot a = a \cdot 1 = a），则称 RR 为有单位元的环或幺环.

环的例子

  • 整数集 Z\mathbb{Z} 在通常的加法和乘法下构成交换幺环
  • 有理数集 Q\mathbb{Q}、实数集 R\mathbb{R}、复数集 C\mathbb{C} 都是交换幺环
  • 模 nn 整数环 Z/nZ\mathbb{Z}/n\mathbb{Z} 是有限交换幺环
  • 对于环 RR，n×nn \times n 矩阵环 Mn(R)M_n(R) 是有单位元但不交换的环（当 n>1n > 1 时）
  • 多项式环 R[x]R[x]：若 RR 是环，则以 RR 为系数的多项式在通常的加法和乘法下构成环

理想

理想的定义

设 RR 是环，II 是 RR 的非空子集.如果 II 满足：

  1. ∀a,b∈I,a−b∈I\forall a,b \in I, a - b \in I（对减法封闭）
  2. ∀r∈R,a∈I,ra∈I\forall r \in R, a \in I, ra \in I 且 ar∈Iar \in I（吸收性质）

则称 II 是 RR 的一个理想.

理想的类型

  • 主理想：由单个元素 aa 生成的理想，记作 (a)={ra:r∈R}(a) = \{ra : r \in R\}
  • 极大理想：不等于 RR 的理想中按包含关系最大的理想
  • 素理想：理想 PP 满足：若 ab∈Pab \in P，则 a∈Pa \in P 或 b∈Pb \in P

商环

设 II 是环 RR 的理想，则商集 R/I={r+I:r∈R}R/I = \{r + I : r \in R\} 在运算
(r+I)+(s+I)=(r+s)+I(r + I) + (s + I) = (r + s) + I 和 (r+I)(s+I)=rs+I(r + I)(s + I) = rs + I
下构成环，称为商环.

零因子和整环

零因子

在环 RR 中，非零元素 aa 称为左零因子，如果存在非零元素 bb 使得 ab=0ab = 0.

类似地，非零元素 aa 称为右零因子，如果存在非零元素 bb 使得 ba=0ba = 0.

如果 aa 既是左零因子又是右零因子，则称 aa 为零因子.

整环

没有零因子的交换幺环称为整环或整数环.

整环的等价定义：交换幺环 RR 是整环当且仅当对于 a,b∈Ra,b \in R，若 ab=0ab = 0，则 a=0a = 0 或 b=0b = 0.

整环的性质

  1. 整环满足消去律：若 ac=bcac = bc 且 c≠0c \neq 0，则 a=ba = b
  2. 有限整环是域
  3. 整环可以嵌入到它的分式域中

多项式环

多项式环的定义

设 RR 是环，xx 是一个符号（不定元），则多项式环 R[x]R[x] 是所有形如

f(x)=a0+a1x+a2x2+⋯+anxnf(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n

的表达式的集合，其中 ai∈Ra_i \in R，在通常的多项式加法和乘法下构成环.

多项式的次数

非零多项式 f(x)=anxn+⋯+a1x+a0f(x) = a_n x^n + \cdots + a_1 x + a_0（其中 an≠0a_n \neq 0）的次数 deg⁡f=n\deg f = n.

零多项式的次数定义为 −∞-\infty 或不定义.

多项式环的性质

  1. 若 RR 是整环，则 R[x]R[x] 也是整环
  2. 若 RR 是唯一分解整环，则 R[x]R[x] 也是唯一分解整环
  3. 若 FF 是域，则 F[x]F[x] 是主理想整环

多项式的根

设 f(x)∈R[x]f(x) \in R[x]，a∈Ra \in R.如果 f(a)=0f(a) = 0，则称 aa 是多项式 f(x)f(x) 在 RR 中的一个根.

因式分解定理：(x−a)(x - a) 整除 f(x)f(x) 当且仅当 aa 是 f(x)f(x) 的根.

中国剩余定理

经典形式

设 m1,m2,…,mkm_1, m_2, \ldots, m_k 是两两互质的正整数，a1,a2,…,aka_1, a_2, \ldots, a_k 是任意整数.则同余方程组

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

在模 M=m1m2⋯mkM = m_1 m_2 \cdots m_k 意义下有唯一解.

环论形式

设 RR 是交换幺环，I1,I2,…,IkI_1, I_2, \ldots, I_k 是 RR 的理想.如果这些理想两两互质（即 Ii+Ij=RI_i + I_j = R 当 i≠ji \neq j），则存在环同构

R/(I1∩I2∩⋯∩Ik)≅R/I1×R/I2×⋯×R/IkR/(I_1 \cap I_2 \cap \cdots \cap I_k) \cong R/I_1 \times R/I_2 \times \cdots \times R/I_k

域论(Field Theory)

域的定义

域(field) 是一个交换幺环，其中每个非零元素都有乘法逆元.

等价地，域 FF 是满足以下条件的集合：

  1. (F,+)(F,+) 是 Abel 群，单位元记作 00
  2. (F∖{0},⋅)(F \setminus \{0\}, \cdot) 是 Abel 群，单位元记作 11
  3. 分配律：∀a,b,c∈F,a⋅(b+c)=a⋅b+a⋅c\forall a,b,c \in F, a \cdot (b + c) = a \cdot b + a \cdot c

域的基本性质

  1. 域没有零因子
  2. 域是整环
  3. 域的唯一理想是 (0)(0) 和域本身
  4. 每个有限整环都是域

域的例子

  • 有理数域 Q\mathbb{Q}：最小的特征为 00 的域
  • 实数域 R\mathbb{R}：实数集在通常的加法和乘法下构成域
  • 复数域 C\mathbb{C}：复数集是代数闭域
  • 有限域 Fp\mathbb{F}_p：当 pp 是素数时，Z/pZ\mathbb{Z}/p\mathbb{Z} 构成有 pp 个元素的域
  • 函数域：有理函数域 F(x)F(x)，其中 FF 是域

域的特征

域 FF 的特征 char(F)\mathrm{char}(F) 定义为最小的正整数 pp 使得 p⋅1F=0Fp \cdot 1_F = 0_F.

如果不存在这样的正整数，则 char(F)=0\mathrm{char}(F) = 0.

性质：域的特征要么是 00，要么是素数.

域的扩张

扩张的定义

设 FF 和 KK 是域，如果 F⊆KF \subseteq K，则称 KK 是 FF 的扩域或扩张，记作 K/FK/F.

扩张的度数

域扩张 K/FK/F 的度数 [K:F][K:F] 定义为 KK 作为 FF-向量空间的维数.

若 [K:F]<∞[K:F] < \infty，则称 K/FK/F 是有限扩张；否则称为无限扩张.

塔定理

若 L/KL/K 和 K/FK/F 都是有限扩张，则 L/FL/F 也是有限扩张，且

[L:F]=[L:K]⋅[K:F][L:F] = [L:K] \cdot [K:F]

代数元和超越元

设 K/FK/F 是域扩张，α∈K\alpha \in K.

  • 如果存在非零多项式 f(x)∈F[x]f(x) \in F[x] 使得 f(α)=0f(\alpha) = 0，则称 α\alpha 是 FF 的代数元
  • 否则称 α\alpha 是 FF 的超越元

代数扩张

如果域扩张 K/FK/F 中的每个元素都是 FF 的代数元，则称 K/FK/F 是代数扩张.

定理：有限扩张都是代数扩张.

有限域

有限域的存在性和唯一性

定理：对于素数 pp 和正整数 nn，存在唯一的（在同构意义下）有 pnp^n 个元素的有限域，记作 Fpn\mathbb{F}_{p^n} 或 GF(pn)\mathrm{GF}(p^n).

有限域的构造

  1. 素域：Fp=Z/pZ\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}，其中 pp 是素数
  2. 扩域：Fpn≅Fp[x]/(f(x))\mathbb{F}_{p^n} \cong \mathbb{F}_p[x]/(f(x))，其中 f(x)f(x) 是 Fp\mathbb{F}_p 上的 nn 次不可约多项式

有限域的性质

  1. Fpn\mathbb{F}_{p^n} 的特征是 pp
  2. Fpn\mathbb{F}_{p^n} 的乘法群 Fpn∗\mathbb{F}_{p^n}^* 是循环群，阶为 pn−1p^n - 1
  3. Frobenius 自同态：ϕ:x↦xp\phi: x \mapsto x^p 是 Fpn\mathbb{F}_{p^n} 的自同态
  4. Fpn\mathbb{F}_{p^n} 中每个元素都满足 xpn=xx^{p^n} = x

伽罗瓦域

伽罗瓦理论

伽罗瓦理论研究域扩张的自同态群与中间域之间的对应关系.

伽罗瓦扩张

域扩张 K/FK/F 称为伽罗瓦扩张，如果它是有限的、正规的且可分的.

伽罗瓦群

伽罗瓦扩张 K/FK/F 的伽罗瓦群 Gal(K/F)\mathrm{Gal}(K/F) 是 KK 的所有固定 FF 的自同态构成的群.

伽罗瓦基本定理

设 K/FK/F 是伽罗瓦扩张，G=Gal(K/F)G = \mathrm{Gal}(K/F).则存在一一对应：

{中间域 E:F⊆E⊆K}⟷{子群 H⊆G}\{\text{中间域 } E: F \subseteq E \subseteq K\} \longleftrightarrow \{\text{子群 } H \subseteq G\}

这个对应由 E↦Gal(K/E)E \mapsto \mathrm{Gal}(K/E) 和 H↦KHH \mapsto K^H（HH 的不动域）给出.