程序员的基本群论

本文提供了一些代数群的例子，以便你能够建立对它们的直觉。

群是一个包含以下元素的集合：

• 一个封闭的二元运算
• 二元运算也是结合的
• 存在单位元
• 每个元素都有逆元

我们还讨论了阿贝尔群。阿贝尔群有一个额外的要求，即二元运算是可交换的。

现在是时候讨论群作为数学结构了。

使用整数的加法作为群的例子有一个令人困惑的地方，就是学生们常常会回应说：“但你不能也对整数进行乘法吗？”

诚然，这可能会让人感到困惑。还有其他代数结构，比如环和域，它们涉及两个二元运算。然而，暂时将群视为只有一个固定且不变的二元运算，从群的角度来看，任何其他可能的二元运算要么不存在，要么不是什么问题。

事情更复杂的是，有时二元运算会伪装成其他的二元运算。

例如，在处理只具有加法的群时，有时作者会随意提到乘法，尽管该群并没有这个二元运算。在这个上下文中，乘法实际上是对某个加法操作重复进行若干次的简写。

群的例子

最好通过查看许多群来感受群的特点。让我们开始吧。

1. 平凡群

让我们的群是一个包含数字 $\set{0}$ 的集合，二元运算为加法。很明显，二元运算是闭合和结合的。

$$ (0 + 0) + 0 = (0 + 0) + 0 $$

每个元素都有一个单位元和逆元。

这不是一个有趣的群，但确实是你可以创建的最小有效群。

注意，一个群不能是空的，因为根据定义它必须包含一个单位元。

作为读者的练习，证明集合 $\set{1}$ 在二元运算 $\times$ 下是一个群。

2. 实数在乘法下不是群

尽管实数 ($\mathbb{R}$) 在乘法下有一个单位元（数字 $1$），并且是封闭和结合的，但并不是所有元素都有逆元。

实数是可逆的，方法是取它们的乘法逆元 $(1 / n)$，但零虽然是一个实数，却不能被逆转，因为 $1/0$ 是未定义的而且不是一个实数。

严格来说， $a$ 的逆元是 $b$，使得 $ab = 1$。在这里我们说，如果 $a = 0$，则在集合中没有 $b$ 使得 $ab = 1$。

然而，正的实数（不包括零）在乘法下确实是一个群。每个元素都有一个逆元 ($1/n$)，单位元是 1。

练习： 整数（正数和负数）在乘法下不是一个群。展示四个要求（封闭、结合、存在单位元、所有元素都有逆元）中哪些要求未得到满足。

3. $n \times m$ 的实数矩阵在加法下是一个群

让我们来研究一下：

矩阵加法是闭合且结合的。如果你将一个 $n × m$ 的实数矩阵与另一个 $n × m$ 的实数矩阵相加，你将得到一个 $n × m$ 的实数矩阵。单位矩阵是一个所有元素为零的 $n × m$ 矩阵，矩阵的逆元是该矩阵乘以 -1。等等，我们不允许乘以 -1，对吗？

一个群并不要求逆元必须“可通过群的二元运算计算”，只要求逆元存在。也就是说，我们将掩码计算逆元的方式视为将每个元素乘以 $-1$，尽管乘以 $-1$ 并不是一个群运算。

如果我们将 $n \times m$ 矩阵的操作定义为哈达马乘积（逐元素乘法），那么此群则不可能是群，原因与上述讨论相同。具体来说，逆元通过矩阵中每个元素的倒数进行计算，如果其中一个元素为零，那么逆元就无法计算。

如果我们将操作定义为方阵的传统矩阵乘法，是否仍然是群取决于集合的定义，正如我们将在示例5中看到的那样。

4. 欧几里得平面上 2D 点的集合在逐元素加法下是一个群

这实际上是先前示例的特殊情况，但让我们从不同的角度来看待它。

考虑标准二维平面上所有实值点 $(x, y)$ 的集合。

我们的二元运算是点之间的相加，例如 $(1,1) + (2,2) = (3,3)$。

我们的单位元是原点，因为与此相加将保持其他点的相同位置。

一个点的逆元就是关于原点的“镜像”（$x$ 和 $y$ 坐标取负），因为当你将一个点与其逆元相加时，将结果为原点。

5. $n \times n$ 的非零行列式矩阵在乘法下是一个群

回顾一下，若一个矩阵的行列式非零，则该矩阵可逆。当一个行列式非零的矩阵与另一个行列式非零的矩阵相乘时，乘积的行列式也将非零。实际上，我们可以说得更具体，如果 $A$、$B$ 和 $C$ 是方阵，且 $AB = C$，那么 $\det(A) \times \det(B) = \det(C)$。

让我们来逐条检查定义：

• 非零行列式矩阵的乘法是封闭的，因为你无法“离开群”，乘积将始终具有非零行列式。矩阵乘法是结合的。
• 单位元是单位矩阵（除了主对角线为 1 以外的所有元素均为零）。
• 逆元就是矩阵的逆，且行列式非零的矩阵是可逆的。

6. $n \times n$ 的零行列式矩阵在乘法下不是一个群

记住，行列式为零的矩阵不能被逆，因此这个集合不能具有逆元。在这种情况下，我们没有单位元，因为单位矩阵的行列式为 1。由于我们没有单位元，因此这个集合和二元运算甚至不是一个单一体，而是半群。

7. 固定上边界度的所有多项式在加法下是一个群

如果我们说“所有最高度为 7 的实系数多项式在加法下”，这是一个有效的群。

• 多项式加法是封闭且结合的
• 单位元是多项式 $0$（或者更确切地说是 $0x^0$）
• 逆元是系数乘以 $-1$
• 我们不能说度数是“恰好 7”，因为单位元的度数是 0，而它不会是群的一部分。

度数有上边界的多项式在乘法下不是群，因为一般来说，当你乘以多项式时，度数会变大，因此这个运算将不再封闭。

8. 模一个质数的加法是一个群

我们取质数 $7$。

在这里，单位元仍然是 $0$，因为你与 $0$ 相加会得到相同的数字。

在这种情况下，$5$ 的逆元会是什么？

它将是 $2$，因为 $7 - 5 = 2$，或 $5 + 2 \mod 7$ 为零（单位元）。

9. 模一个质数的乘法不是一个群

在此例中，零没有逆元。

如果我们省略数字 $0$，那么我们将有一个群。单位元是 1，元素 $a$ 的逆元是其模逆元 $a^{-1}$。

10. 固定基数的整数指数乘法是一个群

如果两个整数指数的 $b$ 被相乘，结果是基数乘积的整数指数。例如， $2^3 \times 2^4 = 2^{3 + 4} = 2^7$。对于任意基数均适用：

$$ b^x \times b^y = b^{x + y} $$

单位元是 $b^0$，也就是 $1$，而 $b^x$ 的逆元是 $b^{-x}$。

有限群

顾名思义，有限群包含有限数量的元素。所有整数在加法下的集合不是有限的，但模一个质数的整数加法是一个有限群。

在零知识证明中，我们只使用有限群。

群的阶

群的阶是其包含的元素数量。

循环群

循环群是指有一个元素，使得群中的每个元素都可以通过对该元素反复应用二元运算生成。

循环群的例子

例 1：在加法下只由 0 组成的群是一个循环群

这是显然成立的，因为 $0 + 0 = 0$ 生成了群中的每个元素。

例 2：模 7 的加法是一个循环群

如果我们从 $1$ 开始，将 $1$ 不断相加，我们将生成群中的每个元素。例如：

$$ \begin{align} &1 + 1 &= 2 \\ &1 + 1 + 1 &= 3 \\ &1 + 1 + 1 + 1 &= 4 \\ &1 + 1 + 1 + 1 + 1 &= 5 \\ &1 + 1 + 1 + 1 + 1 + 1 &= 6 \\ &1 + 1 + 1 + 1 + 1 + 1 + 1 &= 0 \\ &1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 &= 1 \\ \end{align} $$

例 3：在模 $7$ 的乘法下是一个循环群，...