1. 7.11 TODD-COXETER算法

这段话是本节的引言，开宗明义地介绍了 Todd-Coxeter算法 的核心功能。

1. 什么是Todd-Coxeter算法？
   • 它是一个具体的、可执行的计算方法，就像你在小学学过的长除法一样，是一套按部就班的步骤。
   • 它的名字来源于两位数学家 J. A. Todd 和 H. S. M. Coxeter。
2. 这个算法用来做什么？
   • 核心目标是“确定一个群在某个集合上的操作”。这是一个群论中的核心概念。
   • 这里的群是有限群 $G$。有限群意味着群中的元素个数是有限的。
   • 这里的集合不是任意集合，而是一个非常特殊的集合：子群 $H$ 的所有陪集组成的集合。
   • 群操作可以理解为群的元素如何像置换（重新排列）一样作用于一个集合中的元素。想象一下，一个正方形的对称操作（旋转、翻转）就是它的对称群作用在它的四个顶点集合上。
3. “令人惊叹的方法”是什么意思？
   • 作者使用“令人惊叹”（amazing）这个词，暗示了这个算法的巧妙和强大。它能从非常抽象的群的定义（生成元和关系）出发，通过纯粹的符号操作和表格构建，最终得出一个具体的、可视化的置换结果。它就像一座桥梁，连接了抽象的代数定义和具体的组合结构。

这段话详细说明了运行 Todd-Coxeter算法 所需的输入信息。

1. “明确给出” (explicitly given) 的含义：
   • 这意味着我们不能只是抽象地说“存在一个群 $G$”，而是必须具体地描述出这个群的结构。在代数中，“明确给出”通常指用生成元和关系来定义。
2. 群的表示 (Presentation of a group)：
   • Todd-Coxeter算法的输入是群的一个表示。这个表示法在上一节（7.10节）已经介绍过。
   • 生成元 (Generators)：$x_1, \ldots, x_m$ 是一些群的元素，通过它们的组合可以得到群中所有的元素。它们就像一个向量空间的基向量，任何向量都可以由基向量的线性组合表示。在群里，任何元素都可以由生成元和它们的逆的乘积（称为“字”）表示。
   • 关系 (Relations)：$r_1, \ldots, r_k$ 是一些由生成元构成的字，这些字在群 $G$ 中都等于单位元 $e$。它们是生成元之间必须遵守的规则或约束。例如，如果 $x$ 是一个生成元，而 $x^3=e$ 是一个关系，那么任何时候我们看到 $x^3$ 都可以将其视作单位元。
3. 公式的含义：
   • 符号 $\langle \ldots \mid \ldots \rangle$ 是群的表示的标准记法。
   • 竖线 | 左边是生成元的集合 $\{x_1, \ldots, x_m\}$。
   • 竖线 | 右边是关系的集合 $\{r_1, \ldots, r_k\}$。
   • 这个表示定义的群 $G$ 是由生成元 $x_1, \ldots, x_m$ 生成的“最自由”的群，但要满足关系 $r_1=e, \ldots, r_k=e$。

这段话说明了 Todd-Coxeter算法 所需的第二个输入：子群 $H$ 的描述。

1. 子群H的定义方式：
   • 和群 $G$ 一样，子群 $H$ 也必须被“明确给出”。
   • $H$ 是 $G$ 的一个子集，并且它自身也构成一个群。
   • 我们通过给出 $H$ 的生成元集合来定义它。
2. 子群的生成元：
   • $h_1, \ldots, h_s$ 是 $H$ 的生成元。这意味着 $H$ 中所有的元素都可以由这些 $h_i$ 和它们的逆的乘积得到。
   • 重要的是，这些 $h_i$ 本身是什么？它们是定义 $G$ 的生成元 $x_1, \ldots, x_m$ 构成的“字”（words）。
3. 自由群 F 和 像 (image)：
   • 这里的自由群 $\mathcal{F}$ 是一个理论上的辅助工具。它是由生成元 $\{x_1, \ldots, x_m\}$ 生成的，但没有任何关系的群。在 $\mathcal{F}$ 中，$x_1x_2$ 和 $x_2x_1$ 是两个不同的元素。
   • 群 $G$ 可以看作是自由群 $\mathcal{F}$ 的一个商群。存在一个自然的满射同态 $\pi: \mathcal{F} \rightarrow G$。
   • 一个在 $\mathcal{F}$ 中的字 $w$（比如 $x_1 x_2^{-1} x_1$）在 $G$ 中的“像”就是 $\pi(w)$，也就是在 $G$ 中这个字所代表的那个元素。
   • 所以，$\{h_1, \ldots, h_s\}$ 是一组在自由群 $\mathcal{F}$ 中写出的字。这些字在 $G$ 中对应的元素（它们的像）共同生成了子群 $H$。

这段话解释了算法的具体执行方式和一些重要的约定。

1. 算法的核心机制：
   • 算法不是通过代数推导，而是通过“构造一些表格”来进行的。这表明它是一个组合的、枚举式的过程。
2. 右陪集 vs. 左陪集：
   • 一个子群 $H$ 可以将群 $G$ 分割成不同的“块”，这些块就是陪集。
   • 右陪集 (Right Cosets) 的形式是 $Hg = \{hg \mid h \in H\}$，其中 $g$ 是 $G$ 中的一个元素。
   • 左陪集 (Left Cosets) 的形式是 $gH = \{gh \mid h \in H\}$。
   • 本文选择使用右陪集，原因是作者认为这样“更容易阅读”表格。这是一个习惯和便利性的选择，算法的本质也可以用左陪集来叙述。
3. 群在右陪集上的操作：
   • 群 $G$ 可以作用于其右陪集的集合 $\mathcal{C}_R = \{Hg \mid g \in G\}$。
   • 这个操作是通过右乘法定义的：对于 $\mathcal{C}_R$ 中的一个陪集 $Hg$ 和 $G$ 中的一个元素 $x$，操作结果是 $(Hg) \cdot x = H(gx)$。
   • 这意味着，一个元素 $x$ 将陪集 $Hg$ “移动”到了陪集 $H(gx)$。
4. 运算的组合顺序 (Composition Order)：
   • 这是一个非常关键且容易混淆的点。在标准的函数复合中，$(f \circ g)(x) = f(g(x))$ 意味着“先应用 $g$，再应用 $f$”。
   • 但是，当群通过右乘法作用于一个集合时，元素的乘积顺序与操作的顺序是一致的。
   • 如果一个元素 $g_1$ 将 $s$ 变为 $s \cdot g_1$，然后一个元素 $g_2$ 作用于结果，得到 $(s \cdot g_1) \cdot g_2 = s \cdot (g_1g_2)$。
   • 所以，乘积 $g_1g_2$ 的作用就等同于“先作用 $g_1$，然后作用 $g_2$”。这与我们从左到右的阅读习惯一致。

这一小节通过一个具体的置换乘法例子，来强调上一段提出的“操作顺序”约定。

1. 这个标题的含义：
   • “先做这个然后做那个” (First this and then that) 是对操作复合顺序的一种非常直观的描述。它强调操作的执行顺序与书写顺序（从左到右）一致。
2. 置换乘法的两种约定：
   • 标准约定 (从右到左)：在大多数本科抽象代数教材中，置换被看作是函数，作用在集合 $\{1, 2, 3, 4, \ldots\}$ 上。置换的乘积 $\sigma \tau$ 被定义为函数复合 $\sigma \circ \tau$，即“先应用 $\tau$，再应用 $\sigma$”。
   • 按照这个标准约定，计算 $(234) \circ (123)$：
   • $1 \xrightarrow{(123)} 2 \xrightarrow{(234)} 3$
   • $2 \xrightarrow{(123)} 3 \xrightarrow{(234)} 4$
   • $3 \xrightarrow{(123)} 1 \xrightarrow{(234)} 1$
   • $4 \xrightarrow{(123)} 4 \xrightarrow{(234)} 2$
   • 结果是 $1 \to 3 \to 1$ 和 $2 \to 4 \to 2$，即 $(13)(24)$。
   • 本书约定 (从左到右)：为了配合右陪集上的右乘操作，本书在这里采用了一种不同的约定。$\sigma \circ \tau$ 意味着“先应用 $\sigma$，再应用 $\tau$”。
   • 按照这个新约定，我们来计算 $(234) \circ (123)$：
   • $1 \xrightarrow{(234)} 1 \xrightarrow{(123)} 2$
   • $2 \xrightarrow{(234)} 3 \xrightarrow{(123)} 1$
   • $3 \xrightarrow{(234)} 4 \xrightarrow{(123)} 4$
   • $4 \xrightarrow{(234)} 2 \xrightarrow{(123)} 3$
   • 结果是 $1 \to 2 \to 1$ 和 $3 \to 4 \to 3$，即 $(12)(34)$。
3. 结论：
   • 书中给出的结果 $(12)(34)$ 明确地告诉我们，它采用的是“从左到右”的操作顺序约定。

这部分是 Todd-Coxeter算法 的核心逻辑，列出了构建陪集表时必须遵守的四条基本公理。算法的整个过程就是不断应用这四条规则来填充和化简表格，直到得到一个完整和一致的结果。

• 规则 1: 每个生成元的操作是一个置换。
• 置换的定义：一个集合到其自身的双射（既是单射又是满射）。
• 为什么是置换：在群中，每个元素 $g$ 都有一个逆元 $g^{-1}$。生成元 $x$ 也是群的元素，所以它有逆元 $x^{-1}$。
• 操作 $s \mapsto s \cdot x$ 的可逆性：如果 $x$ 把陪集 $C_1$ 映到 $C_2$ (即 $C_2 = C_1 \cdot x$)，那么 $x^{-1}$ 必然把 $C_2$ 映回到 $C_1$ (即 $C_1 = C_2 \cdot x^{-1}$)。
• 这意味着 $x$ 的操作是一对一的（单射），并且作用在有限集合上时，也必然是“映上”的（满射）。因此，每个生成元在所有陪集构成的集合上的操作，必须是一个置换。
• 在算法中的体现：这意味着在表示生成元 $x$ 作用的表格列中，每个陪集（索引）必须出现且仅出现一次作为起点，也必须出现且仅出现一次作为终点。

• 规则 2: 关系操作平凡：它们固定每个陪集。
• 关系的定义：一个关系 $r$ 是一个在群 $G$ 中等于单位元 $e$ 的字。
• 单位元的操作：单位元 $e$ 的操作是恒等操作，它不改变任何东西。对于任何陪集 $C$，有 $C \cdot e = C$。
• 引申：因为关系 $r$ 在 $G$ 中就是 $e$，所以 $r$ 的操作也必须是恒等操作。它必须固定每一个陪集。
• 在算法中的体现：如果一个关系 $r = x_1 x_2 \ldots x_k$，那么从任何一个陪集（索引）$i$ 开始，依次应用 $x_1, x_2, \ldots, x_k$ 的操作，最终必须回到索引 $i$。这为我们提供了强大的约束来填充表格。

• 规则 3: $H$ 的生成元固定陪集 $[H]$。
• 陪集 $[H]$：这是子群 $H$ 本身，它可以被写作右陪集 $He$。它是我们整个陪集枚举过程的“原点”或“基准点”。
• H 的元素如何作用于 [H]：根据右陪集的定义，对于任何 $h \in H$，有 $[H] \cdot h = (He) \cdot h = H(eh) = Hh$。
• 陪集的性质：一个右陪集 $Ha$ 等于 $H$ 当且仅当 $a \in H$。
• 结论：因为 $h \in H$，所以 $Hh = H$。这意味着 $H$ 中任何元素（包括它的生成元）通过右乘都固定（stabilize）陪集 $[H]$。
• 在算法中的体现：我们将用索引 $\mathbf{1}$ 来代表陪集 $[H]$。那么对于 $H$ 的任何一个生成元 $h_j$，我们都有一个初始条件：$\mathbf{1} \xrightarrow{h_j} \mathbf{1}$。

• 规则 4: 操作是传递的。
• 传递操作 (Transitive Action) 的定义：一个群 $G$ 在集合 $S$ 上的操作是传递的，如果对于 $S$ 中任意两个元素 $s_1, s_2$，都存在一个群元素 $g \in G$ 使得 $s_1 \cdot g = s_2$。
• 直观理解：从集合中的任何一个点出发，你都可以通过群操作到达集合中的任何其他点。整个集合是“连通”的，形成一个单一的“轨道”（orbit）。
• 为什么在陪集上是传递的：对于任意两个右陪集 $Hg_1$ 和 $Hg_2$，我们可以找到一个元素 $g = g_1^{-1}g_2 \in G$。那么 $(Hg_1) \cdot g = H(g_1(g_1^{-1}g_2)) = H( (g_1g_1^{-1})g_2) = H(eg_2) = Hg_2$。所以，总能从一个陪集到达另一个。
• 在算法中的体现：这条规则是隐含的。它告诉我们，我们创建的所有陪集（索引）最终都必须属于同一个连通的部分。我们从索引 $\mathbf{1}$ 开始，通过生成元不断探索新的索引，这条规则保证了我们最终能枚举出所有的陪集，而不会产生孤立的、无法到达的陪集。

这段话是对前面四条规则来源的简要说明，将其与更基本的群论概念联系起来。

1. 对规则1的解释: “第一个规则源于群元素是可逆的这一事实”
   • 如前所述，生成元 $x$ 在陪集集合上的操作记为 $\rho_x$。即 $\rho_x(C) = C \cdot x$。
   • 因为 $x$ 是群 $G$ 的元素，所以它有逆元 $x^{-1}$。$x^{-1}$ 对应的操作是 $\rho_{x^{-1}}(C) = C \cdot x^{-1}$。
   • 我们来验证 $\rho_x$ 和 $\rho_{x^{-1}}$ 是互为逆函数的：
   • $(\rho_{x^{-1}} \circ \rho_x)(C) = \rho_{x^{-1}}(\rho_x(C)) = \rho_{x^{-1}}(C \cdot x) = (C \cdot x) \cdot x^{-1} = C \cdot (xx^{-1}) = C \cdot e = C$。
   • $(\rho_x \circ \rho_{x^{-1}})(C) = \rho_x(\rho_{x^{-1}}(C)) = \rho_x(C \cdot x^{-1}) = (C \cdot x^{-1}) \cdot x = C \cdot (x^{-1}x) = C \cdot e = C$。
   • 由于 $\rho_x$ 存在一个逆函数 $\rho_{x^{-1}}$，所以 $\rho_x$ 是一个双射，即置换。
2. 对规则2的解释: “第二个规则反映了关系代表 $G$ 的单位元素”
   • 一个关系 $r$ 被定义为在群 $G$ 中等于单位元 $e$。
   • 单位元 $e$ 的操作是恒等操作，即 $\rho_e(C) = C \cdot e = C$ 对所有陪集 $C$ 成立。
   • 如果一个关系 $r$ 是由生成元组成的字 $r = x_1 x_2 \ldots x_k$，那么它对应的操作是 $\rho_r = \rho_{x_k} \circ \ldots \circ \rho_{x_2} \circ \rho_{x_1}$ (注意，这里如果用标准函数复合，顺序是反的，但根据本书约定，操作顺序和书写顺序一致，所以是 $\rho_{x_1}$ 然后 $\rho_{x_2}$...)
   • 因为在群中 $r=e$，所以对应的操作也必须相等：$\rho_r = \rho_e$。
   • 因此，$\rho_r$ 必须是恒等操作，即它固定每个陪集。
3. 对规则3和4的解释: “规则 3 和 4 是陪集上操作的特殊性质”
   • 这句话的意思是，规则1和2适用于任何群操作（只要操作是忠实的，即 $g \neq e \implies \rho_g$ 不是恒等），而规则3和4是专门针对“$G$ 作用于其子群 $H$ 的陪集”这一特定场景的。
   • 规则3 ($H$ 的生成元固定 $[H]$) 来自陪集 $Ha=H \iff a \in H$ 的基本定义。
   • 规则4 (操作是传递的) 来自于我们可以通过右乘 $g_1^{-1}g_2$ 从任意陪集 $Hg_1$ 到达 $Hg_2$。
   • 如果 $G$ 作用在另一个不相关的集合 $S$ 上，这个操作不一定是传递的（可能会有多个轨道），也不一定有哪个元素会被某个子群 固定。

这段话引入了算法执行过程中的核心记号——索引。

1. 为什么需要索引？
   • 陪集本身（如 $H(x_1x_2)$）写起来很繁琐。
   • 在算法开始时，我们根本不知道有哪些陪集，更不用说它们的具体形式了。
   • 使用简单的数字索引 $1, 2, 3, \ldots$ 作为陪集的临时占位符或“代号”，可以大大简化表格和计算过程。
2. 索引的分配规则：
   • 索引 1 的特殊地位：我们规定，索引 $\mathbf{1}$ 永远代表起始的陪集，即子群 $H$ 本身。在右陪集的记法中，这就是 $[H]$ 或 $He$。
   • 动态添加索引：算法是一个探索性的过程。当我们从一个已知的索引（代表一个已知的陪集）出发，应用一个生成元 $x$ 的操作，而结果是未知的陪集时，我们就引入一个新的索引来代表这个新发现的陪集。
   • 不知道需要多少索引：在算法结束之前，我们无法预知总共会发现多少个不同的陪集。陪集的数量（即子群 $H$ 在 $G$ 中的索引 $[G:H]$）是算法的输出之一，而不是输入。如果 $[G:H]$ 是无限的，算法可能永远不会终止。

这段是 Todd-Coxeter 算法 第一个完整示例的开场白，它设定了问题，并执行了算法的第一步。

1. 问题的设定：
   • 群 G: $G = \langle x, y, z \mid x^3, y^2, z^2, xyz \rangle$。
   • 生成元：$x, y, z$。
   • 关系：
   • $x^3=e$（$x$ 的阶是1或3）
   • $y^2=e$（$y$ 的阶是1或2）
   • $z^2=e$（$z$ 的阶是1或2）
   • $xyz=e$ (这是一个混合关系，等价于 $z = y^{-1}x^{-1}$ 或 $xy=z^{-1}$。由于 $z^2=e$, $z=z^{-1}$, 所以 $xy=z$)。
   • 子群 H: $H = \langle z \rangle$。
   • $H$ 是由生成元 $z$ 生成的循环子群。
   • 由于关系 $z^2=e$，我们知道 $H$ 最多有两个元素 $\{e, z\}$。我们尚不确定 $z$ 是否等于 $e$。如果 $z \neq e$，则 $H$ 的阶为2。
2. 算法的启动：应用规则3
   • 算法的第一步总是从索引 1 和子群 $H$ 的生成元开始。
   • 规则3说：$H$ 的生成元固定陪集 $[H]$。
   • 在我们的记法中，$[H]$ 用索引 1 表示。
   • $H$ 的生成元是 $z$。
   • 因此，规则3告诉我们：$z$ 的操作固定了索引 1。
   • 写作 $\mathbf{1} \xrightarrow{z} \mathbf{1}$。
   • 这意味着，当我们在为生成元 $z$ 构建操作表时，我们已经有了一条信息：$z$ 作用在1上，结果还是1。
3. 后续策略：
   • “这用尽了规则 3 中的信息”：因为 $H$ 只有一个生成元 $z$，所以关于 $H$ 的生成元如何作用于索引 1 的信息已经全部用完。
   • “规则 1 和 2 接管”：接下来，我们就要靠规则1（生成元是置换）和规则2（关系是恒等）来继续填充表格和发现新的信息。
   • “规则 4 只会隐含地出现”：我们不会直接说“因为操作是传递的，所以...”，而是通过从索引 1 不断探索新索引的方式来自然地满足传递性要求。

这段描述了算法的核心“探索”步骤：当没有规则可以直接推导出下一步时，我们就创造一个新的索引来表示这个未知的结果。

1. 处理生成元 x：
   • 我们已经知道 $\mathbf{1} \xrightarrow{z} \mathbf{1}$。现在轮到处理其他生成元，比如 $x$。
   • “$x$ 对索引 $\mathbf{1}$ 做了什么？” 意思是 $\mathbf{1} \cdot x$ 对应哪个陪集（索引）？
   • 现有的规则（特别是规则3）没有提供任何关于 $x$ 的信息。
2. 分配新索引（步骤ii）:
   • 当信息不足时，算法采取“定义新变量”的策略。我们引入一个新的索引 $\mathbf{2}$，并定义 $\mathbf{1} \xrightarrow{x} \mathbf{2}$。
   • 这个定义是暂时的。在后续计算中，我们可能会发现 $\mathbf{2}$ 其实和某个已存在的索引（比如 $\mathbf{1}$）是同一个，届时再进行合并。但在当前，我们只能假设它是一个全新的陪集。
   • 括号里的内容是对这个新索引的解释：既然 $\mathbf{1}$ 代表陪集 $[H]$，那么 $\mathbf{1} \cdot x$ 就代表陪集 $[H]x$。因此，$\mathbf{2}$ 就是 $[H]x$ 的代号。作者建议“最好忽略这一点”，是为了让学习者专注于算法的符号操作，而不要过早地被背后复杂的陪集理论所困扰。
3. 继续探索:
   • 现在我们有了一个新的索引 $\mathbf{2}$，我们自然要问：$x$ 对 $\mathbf{2}$ 作用是什么？即 $\mathbf{2} \xrightarrow{x} ?$
   • 同样，没有任何规则能告诉我们结果。
   • 所以我们再次分配一个新的索引 $\mathbf{3}$，并定义 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • 索引 3 现在代表陪集 $([H]x)x = [H]x^2$。
4. 复合操作的推论:
   • 我们有了 $\mathbf{1} \xrightarrow{x} \mathbf{2}$ 和 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • 将这两个操作复合起来，我们就得到了 $x^2$ 对 $\mathbf{1}$ 的作用：$\mathbf{1} \xrightarrow{x^2} \mathbf{3}$。

这段引入了一种记录当前进度的有用工具：部分置换表示法。

1. 部分操作 (Partial Action)：
   • 在算法的任何中间阶段，我们通常只知道一部分生成元对一部分索引的作用。这就是所谓的“部分操作”。
   • 例如，我们知道 $\mathbf{1} \xrightarrow{x} \mathbf{2}$，但可能还不知道 $\mathbf{1} \xrightarrow{y} ?$。
2. 用循环表示法跟踪进度：
   • 为了方便地记录和查看我们已经知道了什么，可以使用置换的循环表示法。
   • 一个完整的置换，如 $(123)$，意味着 $1 \to 2 \to 3 \to 1$。
   • 一个部分操作可以用一个“未闭合”的循环来表示。
3. 解读部分置换：
   • $z = (\mathbf{1}) \cdots$:
   • 这表示我们知道 $z$ 的操作形成了一个包含 1 的循环。因为 $\mathbf{1} \xrightarrow{z} \mathbf{1}$，所以这个循环是 $(\mathbf{1})$。
   • 省略号 ... 表示 $z$ 在其他索引（如 $\mathbf{2}, \mathbf{3}$）上的作用我们还完全不知道。
   • $x = (\mathbf{123} \cdots$:
   • 这表示我们知道 $\mathbf{1} \xrightarrow{x} \mathbf{2}$ 和 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • 这是一个从 $\mathbf{1}$ 开始的循环的一部分。
   • 省略号 ... 在括号内，且没有闭合括号，这强调了我们还不知道 $\mathbf{3} \xrightarrow{x} ?$。这个循环链还没有“闭合”。

这是算法中第一个关键的“推导”步骤，它利用关系来发现新的信息，而不是定义新的索引。

1. 应用规则2：
   • 规则2说关系操作平凡，即固定每个陪集。
   • 我们有一个关系 $x^3=e$。
   • 这意味着，从任何索引 $i$ 开始，连续应用三次 $x$ 的操作，必须回到 $i$。即 $i \xrightarrow{x^3} i$。
2. 结合已知信息进行推导：
   • 我们从索引 1 开始应用这个关系：$\mathbf{1} \xrightarrow{x^3} \mathbf{1}$。
   • 我们已经知道：$\mathbf{1} \xrightarrow{x} \mathbf{2}$ 和 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • 把这两个合起来，我们知道 $\mathbf{1} \xrightarrow{x^2} \mathbf{3}$。
   • 现在看 $x^3$ 的操作：$\mathbf{1} \xrightarrow{x^3} \mathbf{1}$ 可以分解为 $(\mathbf{1} \xrightarrow{x^2}) \xrightarrow{x} \mathbf{1}$。
   • 代入已知信息，就变成了 $\mathbf{3} \xrightarrow{x} \mathbf{1}$。
   • 这是一个全新的信息！我们之前不知道 $\mathbf{3} \xrightarrow{x} ?$，现在通过关系 $x^3=e$ 推导出了结果。我们不需要再引入新的索引 $\mathbf{4}$ 了。
3. 关系表 (Relation Table)：
   • 文中引入了一种表格来系统地记录和应用关系。
   • 表格的第一行写下关系的字，例如 $x, x, x$。
   • 表格的第二行记录操作路径。
   • 我们从索引 1 开始，把它写在第二行的最左边。
   • 因为关系必须闭合，所以我们把索引 1 也写在第二行的最右边。
   • 然后从左到右填充：$\mathbf{1} \xrightarrow{x} \mathbf{2}$，所以在第一个 $x$ 下面写 $\mathbf{2}$。
   • $\mathbf{2} \xrightarrow{x} \mathbf{3}$，所以在第二个 $x$ 下面写 $\mathbf{3}$。
   • 现在表格是 1 2 3 1。这清晰地显示出，第三个 $x$ 必须把 $\mathbf{3}$ 映射到 $\mathbf{1}$。
4. 更新部分操作：
   • 我们现在知道了 $\mathbf{1} \xrightarrow{x} \mathbf{2}$，$\mathbf{2} \xrightarrow{x} \mathbf{3}$，以及 $\mathbf{3} \xrightarrow{x} \mathbf{1}$。
   • 这正好构成了一个完整的3-循环。
   • 所以，关于 $x$ 在索引 $\{1,2,3\}$ 上的操作，我们已经完全清楚了。
   • 我们可以更新部分操作的记录为 $x=(123)$。
   • 后面的 ... 表示我们不知道 $x$ 在其他可能的索引（比如将来可能出现的4, 5...）上如何作用，但至少在 $\{1,2,3\}$ 这个子集上，它的作用是完整的。
5. 一个重要的提醒：
   • “只是我们还不知道索引 $\mathbf{1}, \mathbf{2}, \mathbf{3}$ 是否代表不同的陪集。”
   • 我们虽然知道了 $x$ 的操作模式，但这并不排除在后续的计算中，我们可能会发现 $\mathbf{2}=\mathbf{3}$ 或者 $\mathbf{1}=\mathbf{2}$ 的可能性。如果发生了这种“坍缩”，那么这个3-循环也会相应地坍缩。但在没有证据之前，我们假设它们是不同的。

这段描述了对另一个生成元 $y$ 进行类似的处理过程：先探索，再用关系约束。

1. 处理生成元 y：
   • 我们已经对 $x$ 和 $z$ 在某些索引上的操作有了一些了解。现在轮到生成元 $y$。
   • 我们从最基本的问题开始：“$y$ 对索引 $\mathbf{1}$ 做了什么？” 即 $\mathbf{1} \xrightarrow{y} ?$
   • 目前没有任何规则能告诉我们答案。$H=\langle z \rangle$ 的定义只约束了 $z$，没有约束 $y$。
2. 分配新索引:
   • 和之前处理 $x$ 时一样，我们引入一个新的索引 $\mathbf{4}$，并定义 $\mathbf{1} \xrightarrow{y} \mathbf{4}$。
   • 此时，我们有索引集合 $\{\mathbf{1}, \mathbf{2}, \mathbf{3}, \mathbf{4}\}$。
3. 应用关系 $y^2=e$：
   • 规则2告诉我们，关系 $y^2=e$ 意味着从任何索引出发，连续应用两次 $y$ 的操作，必须回到起点。
   • 我们将此规则应用于我们刚刚探索的路径，从索引 1 开始：$\mathbf{1} \xrightarrow{y^2} \mathbf{1}$。
   • 这个操作可以分解为 $(\mathbf{1} \xrightarrow{y}) \xrightarrow{y} \mathbf{1}$。
   • 代入我们的新定义 $\mathbf{1} \xrightarrow{y} \mathbf{4}$，我们得到 $\mathbf{4} \xrightarrow{y} \mathbf{1}$。
   • 又一次，我们通过关系得到了一个新的操作信息，而无需引入更多的索引。
4. 关系表和部分操作：
   • 文中用一种更紧凑的记法 y y / 1 4 1 来表示 $y^2$ 的关系表。这等同于：
   • 这个推导告诉我们，在索引 $\{1, 4\}$ 上，$y$ 的操作是 $\mathbf{1} \xrightarrow{y} \mathbf{4}$ 和 $\mathbf{4} \xrightarrow{y} \mathbf{1}$。
   • 这构成了一个2-循环（即一个对换）。
   • 因此，我们可以将 $y$ 的部分操作记为 $y=(14)\cdots$。省略号表示我们还不知道 $y$ 对 $\mathbf{2}$ 和 $\mathbf{3}$ 的作用。

这是整个示例中最关键的一步，它演示了算法如何通过不同关系的相互作用来发现索引之间的相等关系，从而导致陪集信息的“坍缩”。

1. 汇总已知信息：
   • 作者用一个大表格汇总了所有关系在索引 1 上的应用情况。
   • $x^3$ 表: 1 2 3 1 (如前所述，原文的 1 2 3 应为 1 2 3 1)
   • $y^2$ 表: 1 4 1
   • $z^2$ 表: 1 1 1
   • $xyz$ 表: 1 2 ? ? 1。我们知道 $\mathbf{1} \xrightarrow{x} \mathbf{2}$，并且最终必须回到 $\mathbf{1}$。中间两步是未知的。
2. 利用 $xyz$ 关系表进行推导：
   • 我们来看 $xyz=e$ 这条关系在索引 1 上的应用。
   • 从左到右推: 我们知道 $\mathbf{1} \xrightarrow{x} \mathbf{2}$。所以表格变成：
   • 从右到左推: 这一步是关键！我们可以利用逆元从右边往左边推。路径 $\mathbf{?} \xrightarrow{z} \mathbf{1}$ 等价于 $\mathbf{1} \xrightarrow{z^{-1}} \mathbf{?}$。
   • 由于 $z^2=e$，我们有 $z=z^{-1}$。
   • 而已知信息 $\mathbf{1} \xrightarrow{z} \mathbf{1}$，所以 $\mathbf{1} \xrightarrow{z^{-1}} \mathbf{1}$。
   • 这意味着 ? 必须是 $\mathbf{1}$。
   • 现在 $xyz$ 表格被填充为：
   • 这个完整的表格 1 2 1 1 包含了新的信息！
3. 发现矛盾/等价关系：
   • 从填充好的 $xyz$ 表 1 2 1 1 中，我们可以读出：$\mathbf{2} \xrightarrow{y} \mathbf{1}$。
   • 但是，我们回顾一下之前对 $y$ 的分析，我们有 $\mathbf{1} \xrightarrow{y} \mathbf{4}$ 和 $\mathbf{4} \xrightarrow{y} \mathbf{1}$。
   • 我们现在有了两个关于 $y$ 的操作，都导致结果为 $\mathbf{1}$：
4. $\mathbf{2} \xrightarrow{y} \mathbf{1}$
5. $\mathbf{4} \xrightarrow{y} \mathbf{1}$
   • 规则1说，$y$ 的操作必须是一个置换。置换是一对一的。如果两个不同的输入 $\mathbf{2}$ 和 $\mathbf{4}$ 经过 $y$ 的操作后得到了相同的输出 $\mathbf{1}$，那么唯一的可能性就是这两个输入本身就是相同的！
   • 因此，我们得出结论：$\mathbf{4} = \mathbf{2}$。
6. 执行索引合并 (“坍缩”):
   • 一旦我们发现了 $\mathbf{4} = \mathbf{2}$，我们就必须更新我们所有的记录。这个过程叫做“合并陪集”或“坍缩”。
   • 我们通常用较小的索引替换较大的索引。所以，在所有出现 $\mathbf{4}$ 的地方，我们都用 $\mathbf{2}$ 来替换。
   • 之前的 $y$ 的部分操作是 $y=(14)\cdots$。替换后，它变成了 $y=(12)\cdots$。
   • 这意味着，$\mathbf{1} \xrightarrow{y} \mathbf{2}$ 并且 $\mathbf{2} \xrightarrow{y} \mathbf{1}$。

这段描述了在索引 $\mathbf{4}$ 坍缩为 $\mathbf{2}$ 之后，如何利用这个新信息继续填充表格，直到所有信息都完整和一致。

1. 更新后的状态：
   • 索引集：$\{\mathbf{1}, \mathbf{2}, \mathbf{3}\}$
   • $x$ 的操作：$x=(123)$。这个是完整的。
   • $y$ 的操作：之前是 $y=(14)\cdots$，因为 $\mathbf{4}=\mathbf{2}$，现在是 $y=(12)\cdots$。我们知道 $\mathbf{1} \leftrightarrow \mathbf{2}$，但还不知道 $y$ 对 $\mathbf{3}$ 的作用。
   • $z$ 的操作：我们只知道 $\mathbf{1} \xrightarrow{z} \mathbf{1}$，即 $z=(1)\cdots$。
2. 重新审视和填充关系表：
   • $x^3$ 表:
   • $x=(123)$ 已经满足了在 $\{\mathbf{1},\mathbf{2},\mathbf{3}\}$ 上任意一点出发，三次 $x$ 操作后回到原点。例如，从 $\mathbf{2}$ 开始：$\mathbf{2} \xrightarrow{x} \mathbf{3} \xrightarrow{x} \mathbf{1} \xrightarrow{x} \mathbf{2}$。这个表是完全一致的。
   • $y^2$ 表:
   • $\mathbf{1} \xrightarrow{y} \mathbf{2} \xrightarrow{y} \mathbf{1}$。第一行 1 2 1 成立。
   • 我们还不知道 $\mathbf{3} \xrightarrow{y} ?$。所以第三行 3 ? 3 还是空的。
   • $z^2$ 表:
   • $\mathbf{1} \xrightarrow{z} \mathbf{1} \xrightarrow{z} \mathbf{1}$。第一行 1 1 1 成立。
   • 我们不知道 $\mathbf{2} \xrightarrow{z} ?$ 和 $\mathbf{3} \xrightarrow{z} ?$。
   • $xyz$ 表:
   • 第一行 1 2 1 1 已经完整。
   • 第二行，从 $\mathbf{2}$ 开始：$\mathbf{2} \xrightarrow{x} \mathbf{3}$。表格为 2 3 ? ? 2。
   • 第三行，从 $\mathbf{3}$ 开始：$\mathbf{3} \xrightarrow{x} \mathbf{1}$。表格为 3 1 ? ? 3。
3. 再次利用 $xyz$ 表推导：
   • 看第三行 3 1 ? ? 3。
   • 我们知道 $\mathbf{3} \xrightarrow{x} \mathbf{1}$。
   • 我们也知道 $\mathbf{1} \xrightarrow{y} \mathbf{2}$ (因为 $y=(12)\cdots$)。
   • 所以表格被填充为 3 1 2 ? 3。
   • 这告诉我们：$\mathbf{2} \xrightarrow{z} \mathbf{3}$。
   • 这是一个关于 $z$ 的全新信息！
4. 连锁反应：
   • 我们推导出了 $\mathbf{2} \xrightarrow{z} \mathbf{3}$。
   • 规则1要求 $z$ 是置换。$z$ 的逆 $z^{-1}$ 必须把 $\mathbf{3}$ 带回 $\mathbf{2}$。
   • 因为 $z^2=e$，所以 $z=z^{-1}$。
   • 因此，我们同时得到 $\mathbf{3} \xrightarrow{z} \mathbf{2}$。
   • 现在 $z$ 的操作是：$z=(1)(23)$。
   • 再来看 $y$ 的操作。我们还不知道 $\mathbf{3} \xrightarrow{y} ?$。
   • 回到 $xyz$ 表的第二行 2 3 ? ? 2。
   • $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • $\mathbf{2}$ 必须通过 $z^{-1}y^{-1}x^{-1}$ 回到 $\mathbf{2}$。
   • 或者更容易地，我们有 $\mathbf{2} \xrightarrow{xyz} \mathbf{2}$。
   • $\mathbf{2} \xrightarrow{x} \mathbf{3} \xrightarrow{y} \mathbf{?} \xrightarrow{z} \mathbf{2}$。
   • 因为我们刚知道 $\mathbf{3} \xrightarrow{z} \mathbf{2}$，所以 $\mathbf{?} \xrightarrow{z} \mathbf{2}$ 意味着 $\mathbf{?}$ 必须是 $\mathbf{3}$。
   • 因此，中间那一步 $\mathbf{3} \xrightarrow{y} \mathbf{?}$ 必须是 $\mathbf{3} \xrightarrow{y} \mathbf{3}$。
   • 这意味着 $y$ 固定了索引 3。
   • 现在所有部分操作都完整了。
5. 最终结果：
   • 索引集: $\{\mathbf{1}, \mathbf{2}, \mathbf{3}\}$
   • $x$ 的操作: $x=(123)$
   • $y$ 的操作: $y=(12)(3)$，通常写作 $y=(12)$
   • $z$ 的操作: $z=(1)(23)$，通常写作 $z=(23)$
   • 所有的表格现在都应该是一致的，算法终止。

这段话解释了如何从 Todd-Coxeter 算法 的输出（即最终的置换表示）中提取关于群 $G$ 和子群 $H$ 的宝贵信息。

1. 算法输出的普遍信息：
   • 陪集的数量: 算法得到的最终索引的数量，就是子群 $H$ 在 $G$ 中的索引（index），记作 $[G:H]$。
   • 在我们的例子中，我们得到了3个索引 {1, 2, 3}，所以 $[G:H]=3$。这意味着 $H$ 在 $G$ 中有3个不同的右陪集。
2. 关于生成元阶的信息：
   • 输入的关系为我们提供了生成元阶的上限。例如，$z^2=e$ 意味着 $z$ 的阶整除2，所以阶只能是1或2。
   • 算法的输出（置换表示）可以帮助我们确定阶的下限。
   • 在我们的例子中，生成元 $z$ 对应的置换是 $(23)$。
   • 置换 $(23)$ 的阶是2（因为 $(23)^2 = e$，但 $(23)^1 \neq e$）。
   • 一个群元素的阶必须能被它在任何置换表示中对应置换的阶整除。所以 $z$ 的阶必须能被2整除。
   • 结合上限（1或2）和下限（能被2整除），我们唯一地确定了 $z$ 的阶就是2。
   • 这意味着在群 $G$ 中，$z$ 不是单位元 $e$。
3. 推断子群 H 的阶：
   • $H$ 是由 $z$ 生成的循环子群，$H = \langle z \rangle$。
   • 因为我们刚刚证明了 $z$ 的阶是2，所以 $H = \{e, z\}$，其阶 $|H|=2$。
4. 推断群 G 的阶：
   • 拉格朗日定理的推论（计数公式）告诉我们：$|G| = |H| \cdot [G:H]$。
   • 我们已经推导出 $|H|=2$ 和 $[G:H]=3$。
   • 因此，群 $G$ 的阶 $|G| = 2 \cdot 3 = 6$。
5. 识别群 G 的结构：
   • 我们得到了一个从 $G$ 到对称群 $S_3$ 的置换表示（因为操作在3个元素上）的同态 $\phi: G \to S_3$。
   • 这个同态将生成元映射为：$\phi(x)=(123)$, $\phi(y)=(12)$, $\phi(z)=(23)$。
   • 置换 $(123)$ 和 $(12)$ 可以生成整个对称群 $S_3$。因此，这个同态 $\phi$ 是满射的。
   • 一个从阶为6的群 $G$ 到阶为6的群 $S_3$ 的满射同态，必然是同构。
   • 因此，我们最终识别出我们研究的群 $G = \langle x, y, z \mid x^3, y^2, z^2, xyz \rangle$ 同构于对称群 $S_3$。

这段话讨论了 Todd-Coxeter 算法 的一个重要特例和一般情况下的局限性。

1. 特例：$H = \{e\}$ (平凡子群)
   • 如果我们选择的子群 $H$ 只包含单位元 $e$ (在文中用 $\{1\}$ 表示)，会发生什么？
   • 陪集的形式：右陪集 $Hg$ 变成了 $\{e\}g = \{g\}$。这意味着每个陪集只包含一个元素。
   • 陪集与群元素的对应：不同的群元素 $g_1, g_2$ 对应不同的陪集 $\{g_1\}, \{g_2\}$。因此，陪集的集合与群 $G$ 的元素集合之间存在一个自然的双射。
   • 操作的含义：$G$ 在右陪集集合上的操作 $(Hg_1) \cdot g_2 = H(g_1g_2)$，现在变成了 $(\{g_1\}) \cdot g_2 = \{g_1g_2\}$。这正好就是 $G$ 在自身元素集合上的右乘操作。这被称为右正则表示 (right regular representation)。
   • 置换表示完全确定G：根据凯莱定理 (Cayley's Theorem)，任何群都同构于其自身的置换群（通过左乘或右乘）。因此，在这种情况下，算法输出的置换表示将与 $G$ 同构。我们能完全还原出 $G$ 的乘法表。
   • 代价：陪集的数量 $[G:H] = |G|/|H| = |G|/1 = |G|$。算法需要处理的索引数量等于群 $G$ 的阶。如果 $G$ 是一个大群，这将导致非常繁重的计算（“许多索引”）。
2. 一般情况：$H$ 是非平凡子群
   • 当我们选择一个更大的子群 $H$ 时，陪集的数量 $[G:H]$ 会变小，计算量也随之减小。
   • 信息的损失：然而，这样做是有代价的。我们得到的置换表示 $\phi: G \to S_n$ (其中 $n=[G:H]$) 可能不再是单射。
   • 同态的核 (Kernel)：$\phi$ 的核 $K = \ker(\phi)$ 是 $G$ 中所有被映射到恒等置换的元素构成的正规子群。根据第一同构定理，$G/K \cong \text{Im}(\phi) \subseteq S_n$。
   • 表示不足以确定G的阶：我们只能确定商群 $G/K$ 的阶。我们不知道核 $K$ 的大小。群 $G$ 的真实阶是 $|G| = |K| \cdot |G/K|$。如果 $|K|>1$，那么 $|G|$ 就会比我们从置换表示中看到的要大。

这是第二个例子的准备阶段，其目标是证明一组给定的关系足以完整定义四面体群 $T$。在运行 Todd-Coxeter 算法 之前，作者先对群的表示做了一些代数上的简化。

1. 目标：证明关系 (7.10.9) 是四面体群 $T$ 的一个完整表示。
   • 四面体群 T 是正四面体的旋转对称群，我们知道它的阶是12。
   • 关系 (7.10.9)（在上一节中给出）是：$x^3=1, y^3=1, z^2=1, xyz=1$。
   • “完整关系集合”意味着由这些生成元和关系定义的抽象群 $G = \langle x,y,z \mid x^3, y^3, z^2, xyz \rangle$ 恰好同构于四面体群 $T$。
2. 简化策略：消除生成元
   • 一个常用的简化技巧是，如果一个关系可以用来把一个生成元表示成其他生成元的表达式，那么我们就可以消除这个生成元和那个关系。
   • 我们有关系 $xyz=1$ (这里作者假设 $xyz=1$ 而不是 $e$)。
   • 从 $xyz=1$ 可以解出 $z = (xy)^{-1} = y^{-1}x^{-1}$。
   • 但是，作者做了一个更直接的推导：从 $xyz=1$ 得到 $xy = z^{-1}$。
   • 同时，我们有另一个关系 $z^2=1$，这意味着 $z=z^{-1}$。
   • 所以，我们可以把 $xy=z^{-1}$ 和 $z=z^{-1}$ 合并，得到 $xy=z$。
3. 代入和替换
   • 现在我们有了 $z=xy$，这意味着生成元 $z$ 是冗余的，可以用 $x$ 和 $y$ 的乘积代替。
   • 群现在可以只由 $x, y$ 生成。
   • 我们需要把 $z=xy$ 代入到所有其他的关系中去，以得到只含 $x,y$ 的新关系。
   • $x^3=1$ 和 $y^3=1$ 不含 $z$，保持不变。
   • $z^2=1$：将 $z=xy$ 代入，得到 $(xy)^2=1$，即 $xyxy=1$。
   • $xyz=1$：这个关系已经被我们用来消除 $z$ 了，所以它被消耗掉了。
   • 这样，原来的四个关系和三个生成元就被简化成了三个关系和两个生成元。
4. 新的群表示
   • 经过简化，我们得到了一个新的群表示：$G = \langle x, y \mid x^3=1, y^3=1, xyxy=1 \rangle$。
   • 作者断言，这个新表示与旧表示定义的是同一个群，并且这些关系在真实的四面体群 $T$ 中也是成立的。

这段话清晰地阐述了证明的逻辑和策略。

1. 定义抽象群 G:
   • 我们现在关注的是由简化的表示定义的抽象群 $G = \langle x, y \mid x^3, y^3, xyxy \rangle$。
   • 我们的最终目标是证明这个抽象群 $G$ 和我们熟知的具体群——四面体群 $T$——是同一个东西（同构）。
2. 利用冯·戴克定理 (von Dyck's Theorem)：
   • 推论 (7.10.14)，即冯·戴克定理，是一个基本结论。它说：如果有一个群 $G = \langle S \mid R \rangle$，而另一个群 $T$ 里的某些元素（我们不妨也叫它们 $S$）满足 $R$ 中的所有关系，那么就存在一个从 $G$ 到 $T$ 的满射群同态 $\psi$。
   • 在我们的例子中，$G = \langle x,y \mid x^3,y^3,xyxy\rangle$。真实的四面体群 $T$ 确实可以由两个元素 $x, y$（比如两个不同的旋转）生成，并且这些关系在 $T$ 中也成立。
   • 因此，冯·戴克定理保证了存在一个满射同态 $\psi: G \to T$。
   • 满射（surjective）意味着 $T$ 中的每个元素都是 $G$ 中某个元素的像。
3. 证明同构的策略:
   • 我们想证明 $\psi$ 是同构（isomorphism），即双射（bijective）。
   • 一个双射既是满射又是单射。
   • 我们已经知道 $\psi$ 是满射了。
   • 对于有限群之间的同态，有一个捷径：如果两个有限群的阶相等，那么它们之间的一个满射同态必然也是单射的，因此是同构。
   • 所以，我们的任务被简化为：证明 $|G| = |T|$。
4. 最终目标:
   • 我们知道四面体群的阶 $|T| = 12$。
   • 因此，我们只需要证明我们定义的抽象群 $G = \langle x, y \mid x^3, y^3, xyxy \rangle$ 的阶也是12。
   • 这就是我们要使用 Todd-Coxeter 算法 来解决的问题。

这段话设定了 Todd-Coxeter 算法 的具体输入（子群 H），并提出了一个更具体的计算目标。

1. 选择子群 H:
   • 为了运行算法，我们必须选择一个子群 $H$。
   • 作者在这里选择了一个由生成元 $x$ 生成的循环子群，$H = \langle x \rangle$。
   • 这是一个明智的选择，因为 $x$ 的行为被关系 $x^3=1$ 所约束，这使得 $H$ 的结构比较简单。
2. 对 H 的阶的初步分析:
   • 由于关系 $x^3=1$，我们知道在群 $G$ 中，$x$ 的阶整除3。所以 $x$ 的阶可能是1或3。
   • 如果 $x$ 的阶是1，那么 $x=e$，则 $H = \{e\}$，$|H|=1$。
   • 如果 $x$ 的阶是3，那么 $H = \{e, x, x^2\}$，则 $|H|=3$。
   • 在算法开始前，我们无法确定是哪种情况。
3. 重新定义成功标准:
   • 我们的总目标是证明 $|G|=12$。
   • 利用计数公式 $|G| = |H| \cdot [G:H]$，我们可以把目标分解：
   • 证明 $|H|=3$。
   • 证明 $[G:H]=4$。
   • 如果这两点都能通过 Todd-Coxeter 的结果得到证明，那么 $|G|=3 \cdot 4 = 12$，证明就完成了。
   • 如何证明？
   • 证明 $[G:H]=4$: 算法最终产生了4个不同的索引。
   • 证明 $|H|=3$: 算法产生的 $x$ 的置换表示的阶是3，这就证明了在 $G$ 中 $x$ 的阶不可能是1，因此必须是3。
4. 填表提示:
   • “要填充它，请从关系的两端操作。” 这是一个给计算者的关键提示，强调了之前在第一个例子中学到的技巧：同时从左到右和从右到左填充关系表，以便在中间“相遇”并推导出新信息。

这部分直接给出了 Todd-Coxeter 算法 运行完成后的最终关系表。原文省略了中间的推导步骤，我们在这里需要脑补这个过程。

启动:

• 群: $G = \langle x, y \mid x^3, y^3, xyxy \rangle$
• 子群: $H = \langle x \rangle$
• 规则3: $H$ 的生成元 $x$ 固定索引 1。所以 $\mathbf{1} \xrightarrow{x} \mathbf{1}$。
• $x^3$ 表: 第一行 1 1 1 1 立刻完成。

探索:

1. 处理 y: $\mathbf{1} \xrightarrow{y} ?$ 是未知的。定义新索引 $\mathbf{2}$。$\mathbf{1} \xrightarrow{y} \mathbf{2}$。
2. $y^3$ 表: 在索引 1 上应用。1 2 ? ? 1。我们不知道 $\mathbf{2} \xrightarrow{y} ?$。定义新索引 $\mathbf{3}$。$\mathbf{2} \xrightarrow{y} \mathbf{3}$。表格变为 1 2 3 ? 1。于是推导出 $\mathbf{3} \xrightarrow{y} \mathbf{1}$。
   • 现在我们有 $y$ 的部分操作 $y = (123)\cdots$。
3. $xyxy$ 表: 在索引 1 上应用。1 ? ? ? 1。
   • $\mathbf{1} \xrightarrow{x} \mathbf{1}$ (来自规则3)。表格 1 1 ? ? 1。
   • $\mathbf{1} \xrightarrow{y} \mathbf{2}$。表格 1 1 2 ? 1。
   • $\mathbf{2} \xrightarrow{x} ?$ 未知。
   • 从右边推: $\mathbf{1} \xrightarrow{y^{-1}} \mathbf{3}$ (因为 $\mathbf{3} \xrightarrow{y} \mathbf{1}$)。表格 1 1 2 3 1。
   • 新信息: 中间步骤告诉我们 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
4. 继续探索: 我们有了 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。那 $\mathbf{3} \xrightarrow{x} ?$ 呢？未知。定义新索引 $\mathbf{4}$。$\mathbf{3} \xrightarrow{x} \mathbf{4}$。
5. $x^3$ 表: 在索引 2 上应用。2 3 4 ? 2。这推导出 $\mathbf{4} \xrightarrow{x} \mathbf{2}$。
   • 现在 $x$ 的操作在 $\{2,3,4\}$ 上形成一个闭环: $x = (1)(234)\cdots$。
6. 再次检查 $xyxy$ 表:
   • 我们看索引 2 上的行: 2 3 ? ? 2
   • $\mathbf{2} \xrightarrow{x} \mathbf{3}$。
   • $\mathbf{3} \xrightarrow{y} \mathbf{1}$。
   • 表格变为 2 3 1 ? 2。
   • $\mathbf{1} \xrightarrow{x} \mathbf{1}$。
   • 表格变为 2 3 1 1 2。
   • 这告诉我们 $\mathbf{1} \xrightarrow{y} \mathbf{2}$。这与我们最初的定义一致，没有新信息。
   • 我们看索引 3 上的行: 3 4 ? ? 3
   • $\mathbf{3} \xrightarrow{x} \mathbf{4}$。
   • $\mathbf{4} \xrightarrow{y} ?$ 未知。
   • 从右边推: $\mathbf{3} \xrightarrow{y^{-1}} \mathbf{2}$。$\mathbf{2} \xrightarrow{x^{-1}} \mathbf{4}$。
   • 我们有 $\mathbf{4} \xrightarrow{x} \mathbf{2}$，所以 $\mathbf{2} \xrightarrow{x^{-1}} \mathbf{4}$ 正确。
   • 表格 3 4 ? 2 3。
   • 新信息: $\mathbf{4} \xrightarrow{y} \mathbf{2}$。
7. 再次检查 $y^3$ 表:
   • 我们有了 $\mathbf{4} \xrightarrow{y} \mathbf{2}$。
   • 在索引 4 上应用 $y^3=1$。4 2 ? ? 4
   • $\mathbf{4} \xrightarrow{y} \mathbf{2}$。
   • $\mathbf{2} \xrightarrow{y} \mathbf{3}$。
   • 表格 4 2 3 ? 4。
   • 推导出 $\mathbf{3} \xrightarrow{y} \mathbf{4}$。
   • 矛盾/坍缩! 我们之前有 $\mathbf{3} \xrightarrow{y} \mathbf{1}$。现在又有了 $\mathbf{3} \xrightarrow{y} \mathbf{4}$。由于 $y$ 是置换，这必然意味着 $\mathbf{4}=\mathbf{1}$。
8. 执行坍缩 $\mathbf{4}=\mathbf{1}$:
   • 用 $\mathbf{1}$ 替换所有 $\mathbf{4}$。
   • $x$ 的操作 $(1)(234)$ 变为: 4 被 1 替换，所以变成 $(231)$，即 $(123)$。
   • $y$ 的操作 $(123)$ 和 $\mathbf{4} \xrightarrow{y} \mathbf{2}$ (变为 $\mathbf{1} \xrightarrow{y} \mathbf{2}$), $\mathbf{3} \xrightarrow{y} \mathbf{4}$ (变为 $\mathbf{3} \xrightarrow{y} \mathbf{1}$)。这些都与 $y=(123)$ 吻合。
   • 哦，我的手动推导出了问题，让我们严格按照最终的表格反推。最终表格显示有4个索引，没有坍缩。这意味着我的推导过程在某处出错了。让我们直接分析最终表格的正确性。

分析最终表格:

• 索引: {1, 2, 3, 4}。这意味着 $[G:H]=4$。
• $x$ 的操作:
• 从第一张表读出: $\mathbf{1} \xrightarrow{x} \mathbf{1}$。$\mathbf{2} \xrightarrow{x} \mathbf{3} \xrightarrow{x} \mathbf{4} \xrightarrow{x} \mathbf{2}$。
• 所以 $x = (1)(234)$。这是一个置换。
• 它的阶是3。这证明了在 $G$ 中 $x$ 的阶不为1，必为3。因此 $|H|=|\langle x \rangle| = 3$。
• $x^3=1$ 关系满足：$(1)^3=e$, $(234)^3=e$。
• $y$ 的操作:
• 从第二张表读出: $\mathbf{1} \xrightarrow{y} \mathbf{2} \xrightarrow{y} \mathbf{3} \xrightarrow{y} \mathbf{1}$。$\mathbf{4} \xrightarrow{y} \mathbf{4}$。
• 所以 $y = (123)(4)$。这是一个置换。
• 它的阶是3。
• $y^3=1$ 关系满足：$(123)^3=e$, $(4)^3=e$。
• $xyxy=1$ 操作:
• 我们逐行验证。
• 行 1: $\mathbf{1} \xrightarrow{x} \mathbf{1} \xrightarrow{y} \mathbf{2} \xrightarrow{x} \mathbf{3} \xrightarrow{y} \mathbf{1}$。闭合，正确。
• 行 2: $\mathbf{2} \xrightarrow{x} \mathbf{3} \xrightarrow{y} \mathbf{1} \xrightarrow{x} \mathbf{1} \xrightarrow{y} \mathbf{2}$。闭合，正确。
• 行 3: $\mathbf{3} \xrightarrow{x} \mathbf{4} \xrightarrow{y} \mathbf{4} \xrightarrow{x} \mathbf{2} \xrightarrow{y} \mathbf{3}$。闭合，正确。
• 行 4: $\mathbf{4} \xrightarrow{x} \mathbf{2} \xrightarrow{y} \mathbf{3} \xrightarrow{x} \mathbf{4} \xrightarrow{y} \mathbf{4}$。闭合，正确。

结论:

• 所有表格都是一致和完整的。
• 索引数为4，所以 $[G:H]=4$。
• $x$ 对应的置换是 $(234)$，其阶为3，所以 $|H|=|\langle x \rangle| = 3$。
• 因此 $|G| = |H| \cdot [G:H] = 3 \cdot 4 = 12$。
• 证明完成。

这是对第二个例子计算结果的总结和进一步解读。

1. 提取置换表示:
   • 从上一部分分析的表格中，我们总结出每个生成元对应的置换。
   • $x$ 的操作是 $\mathbf{1} \to \mathbf{1}$ 和 $\mathbf{2} \to \mathbf{3} \to \mathbf{4} \to \mathbf{2}$。这对应的置换是 $(1)(234)$，通常简写为 $(234)$。
   • $y$ 的操作是 $\mathbf{1} \to \mathbf{2} \to \mathbf{3} \to \mathbf{1}$ 和 $\mathbf{4} \to \mathbf{4}$。这对应的置换是 $(123)(4)$，通常简写为 $(123)$。
   • 这就得到了公式 (7.11.7)。
2. 重申证明逻辑:
   • 索引数: 最终有4个索引，所以子群 $H=\langle x \rangle$ 在 $G$ 中的索引 $[G:H]=4$。
   • $x$ 的阶: 生成元 $x$ 对应的置换是 $(234)$，这个置换的阶是3。因为置换的阶必须整除原群元素的阶，所以 $|x|$ 必须是3的倍数。又因为我们有关系 $x^3=1$，所以 $|x|$ 必须整除3。唯一的可能是 $|x|=3$。
   • $H$ 的阶: 因为 $H=\langle x \rangle$ 且 $|x|=3$，所以 $|H|=3$。
   • $G$ 的阶: 使用计数公式 $|G| = |H| \cdot [G:H] = 3 \cdot 4 = 12$。
   • 这与四面体群 $T$ 的阶相等，所以我们证明了 $G \cong T$。
3. 进一步的洞察：识别群的结构
   • “顺便说一句...” 这部分提供了一个额外的结论。
   • 我们得到的置换 $x'=(234)$ 和 $y'=(123)$ 都是作用在4个元素 $\{1,2,3,4\}$ 上的置换。它们属于对称群 $S_4$。
   • $x'=(234)$ 是一个3-循环，是偶置换。
   • $y'=(123)$ 是一个3-循环，是偶置换。
   • 两个偶置换的乘积仍然是偶置换，所以它们生成的子群必然是 $S_4$ 的子群，且包含于交错群 $A_4$ (所有偶置换构成的群)。
   • $A_4$ 的阶是 $|S_4|/2 = 24/2 = 12$。
   • 我们得到的置换表示 $\phi: G \to S_4$ 的像 $\text{Im}(\phi)$ 是由 $(234)$ 和 $(123)$ 生成的群。
   • 可以验证这两个置换可以生成整个 $A_4$。例如，$(123)(234)=(12)(34)$，我们得到了 $A_4$ 中所有的3-循环和 $V_4$ 型元素。
   • 因此 $\text{Im}(\phi) = A_4$。
   • 由于 $|G|=12$ 并且 $|\text{Im}(\phi)|=|A_4|=12$，这个同态 $\phi: G \to A_4$ 是同构。
   • 结论：$G \cong A_4$。
   • 因为我们已经证明 $G \cong T$，所以我们实际上也证明了四面体群 $T$ 同构于交错群 $A_4$。

这个例子展示了算法的另一种可能性：关系过于强大，导致群的结构变得非常简单，甚至平凡。

1. 问题设定：
   • 群 G: $G = \langle x, y \mid x^3, y^3, yxyxy \rangle$。注意，和四面体群相比，一个关系被换掉了。
   • 子群 H: $H = \langle y \rangle$。
   • 目标: 分析这个群的结构。
2. 算法启动和初步推导 (脑补过程):
   • 规则3: $H=\langle y \rangle$ 的生成元是 $y$，所以 $y$ 固定索引 1。$\mathbf{1} \xrightarrow{y} \mathbf{1}$。
   • $y^3$ 表: 在索引 1 上 1 1 1 1，满足。
   • 处理 x: $\mathbf{1} \xrightarrow{x} ?$ 未知。定义 $\mathbf{1} \xrightarrow{x} \mathbf{2}$。
   • $x^3$ 表: 1 2 ? ? 1。定义 $\mathbf{2} \xrightarrow{x} \mathbf{3}$。1 2 3 ? 1。推导出 $\mathbf{3} \xrightarrow{x} \mathbf{1}$。得到 $x=(123)$。
   • 到目前为止，部分操作是 $y=(1)\cdots$，$x=(123)$。
3. 分析 $yxyxy$ 关系表 (关键步骤):
   • 作者给出的表格是最终填写了一部分的快照。我们来分析它是如何得到的。
   • 第一行 (从索引 1 开始): 1 ? ? ? ? 1
   • 从左推:
   • $\mathbf{1} \xrightarrow{y} \mathbf{1}$。表格 1 1 ? ? ? 1。
   • $\mathbf{1} \xrightarrow{x} \mathbf{2}$。表格 1 1 2 ? ? 1。
   • $\mathbf{2} \xrightarrow{y} ?$ 未知。
   • 从右推 (用逆元):
   • $\mathbf{1} \xrightarrow{y^{-1}} \mathbf{1}$ (因为 $y^3=1, y^{-1}=y^2$, 且 $\mathbf{1} \xrightarrow{y^2} \mathbf{1}$)。表格 1 ? ? ? 1 1。
   • $\mathbf{1} \xrightarrow{x^{-1}} \mathbf{3}$ (因为 $\mathbf{3} \xrightarrow{x} \mathbf{1}$)。表格 1 ? ? ? 3 1 1。
   • $\mathbf{3} \xrightarrow{y^{-1}} \mathbf{?}$ 未知。
   • 这里我的推导和书中的 1 2 1 3 1 不一致。让我们严格按照书上给的提示来理解。
   • 书本提示：“第一行的前三个条目通过从左侧操作确定，后三个条目通过从右侧操作确定”。
   • 左侧三个 y x y: $\mathbf{1} \xrightarrow{y} \mathbf{1} \xrightarrow{x} \mathbf{2} \xrightarrow{y} ?$ 得到 1 1 2 ?。
   • 右侧三个 y x y: $\mathbf{?} \xrightarrow{y} \mathbf{?} \xrightarrow{x} \mathbf{?} \xrightarrow{y} \mathbf{1}$。
   • 书中的 1 2 1 3 1 似乎有误或基于我们未知的中间步骤。但我们接受它的结论：该行显示 2 ->y 3。这可能是笔误，原文想表达的是 $\mathbf{2} \xrightarrow{y} \mathbf{1}$ 和 $\mathbf{1} \xrightarrow{x} \mathbf{3}$? 让我们直接接受书中给出的两个推论并向下进行。
   • 推论A (来自第一行): $\mathbf{2} \xrightarrow{y} \mathbf{3}$
   • 推论B (来自第二行): $\mathbf{2} \xrightarrow{y} \mathbf{2}$
4. 发现坍缩:
   • 我们现在有两条关于“$\mathbf{2} \xrightarrow{y} ?$”的信息。
5. $\mathbf{2} \xrightarrow{y} \mathbf{3}$
6. $\mathbf{2} \xrightarrow{y} \mathbf{2}$
   • 由于 $y$ 的操作是函数，一个输入只能有一个输出。因此，必然有 $\mathbf{3} = \mathbf{2}$。第一次坍缩！
7. 连锁坍缩:
   • 我们将 $\mathbf{3}$ 替换为 $\mathbf{2}$。
   • 我们之前有 $x$ 的操作是 $x=(123)$。
   • 替换 $\mathbf{3}$ 为 $\mathbf{2}$ 后，变成 $x=(122)$。这是什么意思？
   • $1 \to 2$
   • $2 \to 2$
   • $3(\text{即}2) \to 1$
   • 所以 $\mathbf{1} \xrightarrow{x} \mathbf{2}$ 和 $\mathbf{2} \xrightarrow{x} \mathbf{1}$。
   • 这与 $\mathbf{2} \xrightarrow{x} \mathbf{2}$ 矛盾。
   • 让我们再看一下书中的推导：“查看 $x x x$ 的表，我们看到 $\mathbf{2}=\mathbf{1}$”。
   • $x^3$ 在索引 1 上的关系表是 1 2 3 1。
   • 当我们发现 $\mathbf{3}=\mathbf{2}$ 时，这个表变成了 1 2 2 1。
   • 1 2 2 1 读作：$\mathbf{1} \xrightarrow{x} \mathbf{2}$, $\mathbf{2} \xrightarrow{x} \mathbf{2}$, $\mathbf{2} \xrightarrow{x} \mathbf{1}$。
   • $\mathbf{1} \xrightarrow{x} \mathbf{2}$ 和 $\mathbf{2} \xrightarrow{x} \mathbf{1}$ 意味着 $x$ 在 $\{1,2\}$ 上是 $(12)$。那么 $x^2$ 就是恒等。
   • $\mathbf{1} \xrightarrow{x^2} \mathbf{1}$。
   • 而 1 2 2 1 表中的 $\mathbf{1} \xrightarrow{x^2} \mathbf{2}$。
   • 所以我们得到 $\mathbf{2}=\mathbf{1}$。第二次坍缩！
8. 最终结论:
   • 我们先发现 $\mathbf{3}=\mathbf{2}$，然后又发现 $\mathbf{2}=\mathbf{1}$。
   • 这意味着所有索引 $\{\mathbf{1}, \mathbf{2}, \mathbf{3}\}$ 都坍缩成了索引 1。
   • 只剩下一个索引，这意味着陪集只有一个。
   • 只有一个陪集意味着子群 $H$ 等于整个群 $G$。即 $[G:H]=1 \implies G=H$。
   • 因为 $H = \langle y \rangle$，所以 $G = \langle y \rangle$。
   • 我们还有关系 $y^3=1$。
   • 因此，$G$ 是一个由 $y$ 生成的循环群，其阶最多为3。
   • 算法本身不告诉我们 $y$ 的阶是不是1。但如果阶是1，则 $G$ 是平凡群。如果阶是3，则 $G \cong C_3$。通常在这种情况下，我们得到的结论是 $G$ 是 $C_3$ 的一个商群。但由于 $G$ 本身就是循环的，它只能是 $C_3$ 或平凡群。

这部分首先给出了一个重要的警告，然后介绍了一个处理更复杂子群 $H$ 的技巧。

1. 警告：
   • “任何错误都会导致操作坍缩。”
   • 这是一个实践中的经验之谈。Todd-Coxeter 算法 对错误非常敏感。如果在推导过程中犯了一个小错误（比如错误地合并了两个不该合并的索引，或者算错了一个操作），这个错误很可能会像病毒一样传播，引发错误的连锁坍缩。
   • 最终，你可能会得出一个比真实情况简单得多的群（比如得到一个平凡群），并错误地认为原始群就是平凡的。
   • 因此，执行算法时必须极度细心和系统。
2. 处理复杂子群H的技巧：
   • 到目前为止，我们选择的子群 $H$ 都非常简单，都是由单个生成元（如 $\langle z \rangle, \langle x \rangle, \langle y \rangle$）生成的。
   • 如果 $H$ 是由一个更复杂的“字” (word) $h$ 生成的呢？比如，在 $G=\langle x,y \mid \ldots \rangle$ 中， $H=\langle xyx^{-1} \rangle$。
   • 规则3要求我们知道 $H$ 的生成元如何作用于索引 1。这意味着我们需要计算 $\mathbf{1} \xrightarrow{xyx^{-1}} \mathbf{1}$。这会涉及到一连串的操作，在算法初期，我们可能不知道 $\mathbf{1} \xrightarrow{x}$ 是什么，计算会很困难。
   • 技巧：Tietze变换。作者介绍的方法是一种叫做Tietze变换的技巧。其思想是，通过引入新的生成元和新的关系来简化子群的定义，同时不改变原始群的结构。
   • 步骤：
3. 引入一个新的生成元符号，比如 $u$。
4. 增加一个新的关系 $u=h$，或者等价地 $u^{-1}h=1$。这个关系将新生成元 $u$ 的意义“绑定”为我们想要的字 $h$。
5. 原来的群 $G$ 同构于这个增加了生成元和关系的新群 $G'$。
6. 现在，在新的表示下，子群 $H=\langle h \rangle$ 就变成了 $H=\langle u \rangle$。
7. 这样，我们又回到了简单的情况：$H$ 是由单个生成元 $u$ 生成的。应用规则3就变得非常简单：$\mathbf{1} \xrightarrow{u} \mathbf{1}$。
   • 多个生成元: 如果 $H = \langle h_1, h_2, \ldots, h_s \rangle$，我们就引入 $s$ 个新生成元 $u_1, \ldots, u_s$ 和 $s$ 个新关系 $u_1=h_1, \ldots, u_s=h_s$。那么 $H$ 就变成了 $\langle u_1, \ldots, u_s \rangle$，应用规则3同样很简单：$\mathbf{1} \xrightarrow{u_i} \mathbf{1}$ 对所有 $i$ 成立。

这部分开始进入对算法正确性的非正式讨论。作者首先对算法的中间状态给出了一个更形式化的描述。

1. 讨论的性质：
   • 这是一个非正式的讨论，而不是一个严格的数学证明。
   • 严格的证明需要对算法的每一步骤进行形式化定义，而本文省略了这一步。
   • 目的是让读者对算法为什么有效建立一个直观的理解。
2. 算法的中间状态描述：
   • 在任何时候，算法的状态可以由以下几部分定义：
   • 一个索引集合 $\mathbf{I}$：这是我们到目前为止发现的所有陪集的代号集合。
   • 一个在 $\mathbf{I}$ 上的部分操作：这是一个描述，说明了我们已经知道了哪些生成元对哪些索引的作用。
   • 例子：在第一个例子的早期，状态是 $\mathbf{I} = \{1,2,3,4\}$，部分操作包括 $\mathbf{1} \xrightarrow{x} \mathbf{2}$, $\mathbf{2} \xrightarrow{x} \mathbf{3}$, $\mathbf{3} \xrightarrow{x} \mathbf{1}$ 和 $\mathbf{1} \xrightarrow{y} \mathbf{4}$, $\mathbf{4} \xrightarrow{y} \mathbf{1}$ 等。
3. 对中间状态的澄清：
   • “部分操作不必与规则 1、2 和 3 一致”：这是一个关键的、微妙的观点。在中间过程中，我们的表格可能是不完整的，甚至是“矛盾”的。例如，一个关系表可能还没有闭合，或者我们可能有两个索引后来被证明是相等的。算法的目标正是要去发现和解决这些不一致之处，最终达到一个完全一致的状态。
   • “但它应该是传递的”：这里的传递性是指，我们引入的所有索引都必须能从索引 1 通过已知的部分操作路径到达。我们不会凭空引入一个与现有索引网络完全不相连的索引。这正是规则4（操作是传递的）的体现。我们只在需要时（即从一个已知索引出发探索未知时）才添加新索引。
4. 起始状态：
   • 算法开始时，状态是最简单的：
   • 索引集合 $\mathbf{I} = \{\mathbf{1}\}$。
   • 部分操作是空的，没有任何已定义的操作。

这段话将算法的核心动力机制归结为两种基本步骤，并提出了关于算法正确性和终止性的两个核心问题。

1. 算法的两种基本步骤:
   • 步骤 (i) - 合并/坍缩 (Deduction/Consequence):
   • 这是算法的“验证”和“求解”步骤。
   • 当我们通过应用规则（主要是规则1和规则2）发现，两个不同的索引代号 $\mathbf{i}$ 和 $\mathbf{j}$ 实际上必须代表同一个陪集时，我们就执行“等同”操作。
   • 例如，在第一个例子中，我们发现 $\mathbf{2} \xrightarrow{y} \mathbf{1}$ 和 $\mathbf{4} \xrightarrow{y} \mathbf{1}$，这迫使我们得出 $\mathbf{2}=\mathbf{4}$。
   • “除非规则暗示索引相等，否则我们绝不会等同索引。” 这句话强调了合并操作必须是有理有据的，不能随意进行。
   • 步骤 (ii) - 定义/探索 (Definition/Extension):
   • 这是算法的“探索”和“假设”步骤。
   • 当我们想知道 $\mathbf{i} \xrightarrow{x} ?$ 但没有任何规则能告诉我们答案时，我们就引入一个全新的索引 $\mathbf{j}$（它不在当前的索引集合中），并定义 $\mathbf{i} \xrightarrow{x} \mathbf{j}$。
   • 例如，在第一个例子的开始，我们定义了 $\mathbf{1} \xrightarrow{x} \mathbf{2}$。
2. 算法的终止条件:
   • 算法在什么时候停止？当它达到一个“稳定状态”时。
   • 这个稳定状态是指：我们有了一个完整的操作表（对于所有生成元在所有索引上的操作都已定义），并且这个操作表与所有规则（特别是所有关系表都正确闭合）完全一致。
   • 此时，步骤(i) 和 步骤(ii) 都无法再进行：没有更多的索引可以合并，也没有更多的未知操作需要定义。
3. 两个核心问题及其答案:
   • 问题1：过程会终止吗？ (Termination)
   • 答案是：对于有限群（或更一般地，有限索引 $[G:H]$ 的情况），是的。
   • 作者给出了一个条件：“并且优先选择类型 (i) 的步骤”。这在实践中很重要，意味着我们应该尽可能地先利用现有信息进行推导和合并，而不是盲目地引入新索引。这会让算法更快地收敛。
   • 作者“不予证明”，因为证明比较复杂，涉及到为算法状态定义一个序，并证明每一步都会使这个序减小。
   • 问题2：如果它终止了，操作是否正确？ (Correctness)
   • 答案是：是的。这是对算法应用者来说更重要的一个保证。
   • 只要算法给出了一个终止的、一致的表格，那么这个表格所描述的置换表示就确实是 $G$ 在 $H$ 的陪集上的正确操作（在重新编号后）。
   • 接下来的定理 7.11.10 将会对这个问题给出一个证明的梗概。

这是关于算法正确性的核心定理。它精确地陈述了算法输出的意义。

1. 定理的假设 (Hypothesis)：
   • “假设步骤 (i) 和 (ii) 的有限次重复...”：这里假设算法已经终止了。
   • “...产生了一个与规则 (7.11.3) 兼容的一致表。”：这里假设算法的最终输出是一个稳定的状态。
   • 一致 (consistent)：没有矛盾。
   • 与规则(7.11.3)兼容 (compatible)：
2. 每个生成元的操作都定义成了一个完整的置换。
3. 所有关系在任何索引上操作都是恒等的（所有关系表都闭合）。
4. $H$ 的生成元固定索引 1。
5. 整个操作是传递的（所有索引都是从 1 可达的）。
6. 定理的结论 (Conclusion)：
   • “那么该表定义了一个置换表示...”：最终的表格为每个生成元 $x_i$ 都给出了一个置换 $\pi_i$。这些置换 $\pi_i$ 生成了一个置换群 $P \subseteq S_n$（其中 $n$ 是索引数）。由于关系在置换下也成立，这定义了一个从 $G$ 到 $P$ 的群同态 $\phi: G \to P$。
   • “...通过适当的编号，它就是 $G$ 中 $H$ 的右陪集上的表示。”：这是最关键的结论。它说，我们用抽象索引 $\{1, 2, \ldots, n\}$ 得到的这个置换群 $P$，和群 $G$ 作用在真实的右陪集集合 $\mathcal{C} = \{Hg_1, Hg_2, \ldots, Hg_n\}$ 上产生的那个置换群，是“一样”的。
   • “一样”的严格意思是：存在一个双射（一个“重新编号”的方案）$\varphi^*: \{\mathbf{1}, \ldots, \mathbf{n}\} \to \mathcal{C}$，它是一个G-同构，即它保持群 $G$ 的操作：$\varphi^*(\mathbf{i} \cdot g) = \varphi^*(\mathbf{i}) \cdot g$。

这是定理证明的第一部分，它建立了从抽象群 $G$ 到我们计算出的索引集合 $\mathbf{I}^*$ 上的操作的同态。

1. 建立 G 在 I* 上的操作:
   • 输入: 群 $G$ 的表示 $\langle x_i \mid r_j \rangle$ 和算法终止得到的一致的表格。
   • 表格的作用: 对于每个生成元 $x_i$，表格都给出了它在索引集合 $\mathbf{I}^*$ 上的一个置换，我们记这个置换为 $\pi_i$。
   • 验证同态: 冯·戴克定理（推论 7.10.14）说，要建立一个从 $G$ 出发的同态，我们只需要验证 $G$ 的所有关系在目标群（这里是置换群）中是否成立。
   • 算法的终止条件保证了“关系操作平凡”，即如果 $r_j$ 是一个关系，那么它对应的置换 $\pi(r_j)$ 就是恒等置换。
   • 因此，确实存在一个群同态 $\phi: G \to S_{|\mathbf{I}^*|}$，它将每个生成元 $x_i$ 映射到置换 $\pi_i$。
   • 这个同态 $\phi$ 就定义了 $G$ 在索引集合 $\mathbf{I}^*$ 上的一个右操作：对于 $g \in G$ 和 $\mathbf{i} \in \mathbf{I}^*$，操作为 $\mathbf{i} \cdot g = \phi(g)(\mathbf{i})$。
2. 验证操作的性质:
   • 传递性: 算法的构造过程（规则4的隐含应用）保证了所有索引都是从索引 1 通过一系列生成元的操作得到的。这意味着对于任意索引 $\mathbf{i} \in \mathbf{I}^*$，都存在一个由生成元构成的字 $w$（它代表 $G$ 中某个元素 $g$），使得 $\mathbf{1} \cdot g = \mathbf{i}$。由此可以进一步证明，任意两个索引之间都是可以通过群操作相互到达的。所以 $G$ 在 $\mathbf{I}^*$ 上的操作是传递的。
   • 稳定性: 规则3 被直接建立在算法中，所以我们知道 $H$ 的生成元固定索引 1。因为 $H$ 是由这些生成元生成的，所以整个子群 $H$ 都固定索引 1。即对于所有 $h \in H$，有 $\mathbf{1} \cdot h = \mathbf{1}$。

这是证明的核心，它提出了构造一个连接“计算世界”和“理论世界”的桥梁（映射 $\varphi$）的策略。

1. 证明策略:
   • 我们的目标是证明算法得到的操作（$G$ on $\mathbf{I}^*$）和理论上的操作（$G$ on $\mathcal{C}$）是“一样”的。
   • 证明“一样”的标准方法是找到一个保持操作的双射（G-同构）。
   • 所以，我们需要构造一个映射 $\varphi^*: \mathbf{I}^* \to \mathcal{C}$，并证明它是双射且操作兼容（即 $\varphi^*(\mathbf{i} \cdot g) = \varphi^*(\mathbf{i}) \cdot g$）。
2. 构造方法：归纳法/过程模拟
   • 我们不是在算法结束后才去寻找 $\varphi^*$，而是在算法的每一步都同步地构造和维护这样一个映射。
   • 我们将这个在算法中间阶段 $\mathbf{I}$ 上定义的映射称为 $\varphi: \mathbf{I} \to \mathcal{C}$。
   • 这个映射必须始终保持“与部分操作兼容”，即如果我们在算法中定义了 $\mathbf{i} \xrightarrow{x} \mathbf{j}$，那么在理论世界中，必须有 $\varphi(\mathbf{i}) \xrightarrow{x} \varphi(\mathbf{j})$。
3. 归纳法的起始步骤 (Base Case):
   • 在算法开始时，索引集合是 $\mathbf{I}_0 = \{\mathbf{1}\}$。
   • 我们定义初始映射 $\varphi_0: \{\mathbf{1}\} \to \mathcal{C}$。
   • 最自然的选择就是将算法的起点（索引 1）映射到理论世界的起点（陪集 $[H]$）。
   • 所以，$\varphi_0(\mathbf{1}) = [H]$。
4. 归纳法的递推步骤 (Inductive Step):
   • 假设在某个阶段，我们已经有了一个“好”的映射 $\varphi: \mathbf{I} \to \mathcal{C}$。
   • 现在算法执行下一步（步骤 (i) 或 (ii)），得到了新的索引集合 $\mathbf{I}'$ 和新的部分操作。
   • 我们需要证明，我们可以将 $\varphi$ 扩展或修改为一个新的“好”的映射 $\varphi': \mathbf{I}' \to \mathcal{C}$。
   • 接下来的段落将分别讨论如何处理步骤 (i) 和 (ii) 的情况。

这是对归纳证明中处理步骤 (ii) - 定义/探索情况的详细说明。

1. 回顾步骤 (ii)：
   • 当 $\mathbf{i} \xrightarrow{x} ?$ 未知时，我们引入一个全新的索引 $\mathbf{j}$，并定义 $\mathbf{i} \cdot x = \mathbf{j}$。
   • 此时，索引集合从 $\mathbf{I}$ 扩展为 $\mathbf{I}' = \mathbf{I} \cup \{\mathbf{j}\}$。
2. 归纳假设:
   • 我们已经有了一个“好”的映射 $\varphi: \mathbf{I} \to \mathcal{C}$，它是操作兼容的。
   • 这意味着对于我们已知的操作，比如 $\mathbf{a} \xrightarrow{y} \mathbf{b}$，都有 $\varphi(\mathbf{a}) \cdot y = \varphi(\mathbf{b})$。
   • 特别地，我们知道索引 $\mathbf{i}$ 对应的真实陪集是 $\varphi(\mathbf{i})$。为了方便，我们给它起个名字，叫 $[Hg]$。
3. 扩展映射:
   • 我们需要定义一个新的映射 $\varphi': \mathbf{I}' \to \mathcal{C}$。
   • 对于所有已经在 $\mathbf{I}$ 中的老索引 $\mathbf{k}$，我们保持定义不变：$\varphi'(\mathbf{k}) = \varphi(\mathbf{k})$。
   • 对于新引入的索引 $\mathbf{j}$，我们需要给它分配一个真实世界中的陪集。
   • 如何分配才能保持“操作兼容”？
   • 我们在计算世界中的定义是 $\mathbf{i} \cdot x = \mathbf{j}$。
   • 为了兼容，我们在理论世界中也必须有 $\varphi'(\mathbf{i}) \cdot x = \varphi'(\mathbf{j})$。
   • 代入已知信息：$\varphi(\mathbf{i}) \cdot x = \varphi'(\mathbf{j})$。
   • 即 $[Hg] \cdot x = \varphi'(\mathbf{j})$。
   • 根据陪集上的右操作定义，$[Hg] \cdot x = H(gx)$。
   • 所以，我们必须定义 $\varphi'(\mathbf{j}) = [H(gx)]$。
4. 结论:
   • 这个定义是唯一能保持操作兼容性的选择。
   • 因为 $\mathbf{j}$ 是一个全新的索引，将它映射到一个新的陪集不会与已有的映射产生冲突。
   • 因此，当算法执行“探索”步骤时，我们可以自然地、无矛盾地扩展我们的对应映射 $\varphi$。

这部分处理归纳证明中更复杂的情况：步骤 (i) - 合并/坍缩。

1. 回顾步骤 (i)：
   • 算法通过应用规则，发现两个之前被认为是不同的索引 $\mathbf{i}$ 和 $\mathbf{j}$，实际上必须是同一个。
   • 例如，因为 $\mathbf{i} \xrightarrow{x} \mathbf{k}$ 和 $\mathbf{j} \xrightarrow{x} \mathbf{k}$，而 $x$ 的操作是置换（单射），所以 $\mathbf{i}=\mathbf{j}$。
   • 或者因为关系表要求 $\mathbf{i} \xrightarrow{r} \mathbf{i}$，但实际计算出的路径是 $\mathbf{i} \to \ldots \to \mathbf{j}$，所以也强制 $\mathbf{i}=\mathbf{j}$。
   • 执行这个步骤后，索引集合 $\mathbf{I}$ 会坍缩成一个新的、更小的集合 $\mathbf{I}'$（例如，所有 $\mathbf{j}$ 都被替换为 $\mathbf{i}$）。
2. 证明的挑战:
   • 在坍缩之前，我们的映射 $\varphi$ 将 $\mathbf{i}$ 和 $\mathbf{j}$ 映射到理论世界中的两个陪集：$\varphi(\mathbf{i})$ 和 $\varphi(\mathbf{j})$。
   • 在坍缩之后，$\mathbf{i}$ 和 $\mathbf{j}$ 在计算世界中变成了同一个东西。
   • 为了定义一个新的、一致的映射 $\varphi': \mathbf{I}' \to \mathcal{C}$，我们必须保证它们在理论世界中的像也是同一个东西，即 $\varphi(\mathbf{i}) = \varphi(\mathbf{j})$。
   • 如果 $\varphi(\mathbf{i}) \neq \varphi(\mathbf{j})$，那么我们的映射就无法定义了，整个证明框架就崩溃了。
3. 引理 7.11.11 的作用:
   • 这个引理正是为了解决这个挑战。它保证了这种情况不会发生。
   • 引理的陈述: 如果算法的规则（在计算世界中）迫使我们得出 $\mathbf{i}=\mathbf{j}$，那么这两个索引在理论世界中的对应物 $\varphi(\mathbf{i})$ 和 $\varphi(\mathbf{j})$ 也必然是相等的。
   • 为什么引理成立（证明在下一段）？简而言之，因为理论世界（$G$ 在陪集上的操作）本身就是完美遵守所有规则的。如果一个逻辑推导在计算世界的模型中成立，那么这个推导在理论世界这个“完美模型”中也必然成立。
4. 如何定义新映射 $\varphi'$:
   • 有了这个引理的保证，定义 $\varphi'$ 就变得简单了。
   • 对于坍缩后集合 $\mathbf{I}'$ 中的任何一个索引（我们不妨称之为 $[\mathbf{i}]$，代表与 $\mathbf{i}$ 等价的所有旧索引），我们定义 $\varphi'([\mathbf{i}]) = \varphi(\mathbf{i})$。
   • 这个定义是良定义的 (well-defined)，因为如果 $\mathbf{j}$ 也在 $[\mathbf{i}]$ 这个等价类中，引理保证了 $\varphi(\mathbf{j}) = \varphi(\mathbf{i})$，所以我们选择哪个代表元（$\mathbf{i}$ 或 $\mathbf{j}$）来定义 $\varphi'$ 的值，结果都是一样的。

这是对引理 7.11.11 的证明。虽然非常简短，但抓住了核心思想。

1. 证明的核心逻辑:
   • 引理要证明的是：如果算法规则能从部分操作 $\varphi$ 推导出 $\mathbf{i}=\mathbf{j}$，那么必然有 $\varphi(\mathbf{i})=\varphi(\mathbf{j})$。
   • 证明思路是反证法或直接论证: 假设 $\varphi(\mathbf{i}) \neq \varphi(\mathbf{j})$，但算法规则却能推导出 $\mathbf{i}=\mathbf{j}$。这意味着算法规则在“真实世界” $\mathcal{C}$ 中不成立，但这将与群论的基本事实相矛盾。
2. “陪集上的操作确实满足规则”的含义:
   • 让我们逐条检查算法的规则在真实的陪集集合 $\mathcal{C}$ 上是否成立。
   • 规则1 (置换性): $G$ 在 $\mathcal{C}$ 上的操作 $C \mapsto C \cdot g$ 是由可逆的群元素 $g$ 定义的，因此它确实是一个置换。
   • 规则2 (关系平凡性): 如果 $r$ 是一个关系，那么在 $G$ 中 $r=e$。因此，它在 $\mathcal{C}$ 上的操作是 $C \mapsto C \cdot r = C \cdot e = C$，是恒等操作。
   • 规则3 (H固定[H]): 对于 $h \in H$，在 $\mathcal{C}$ 上的操作是 $[H] \mapsto [H] \cdot h = Hh$。根据陪集的性质，$Hh=H=[H]$。所以该规则成立。
   • 规则4 (传递性): 我们已经证明了 $G$ 在其右陪集集合上的操作是传递的。
3. 串联逻辑:
   • 算法得出 $\mathbf{i}=\mathbf{j}$ 的过程，是一个纯粹的逻辑推导，其公理就是规则 1-4 以及已知的部分操作 $\varphi$。
   • 我们的归纳假设是 $\varphi$ 是“操作兼容”的，这意味着计算世界中所有已知的操作关系在理论世界中都有对应的真实陪集操作关系。
   • 既然算法的公理（规则 1-4）和前提（已知的部分操作）在理论世界 $\mathcal{C}$ 中都是成立的，那么由这些公理和前提推导出的任何结论（例如 $\mathbf{i}=\mathbf{j}$），在理论世界中也必须成立。
   • 在理论世界中，"$\mathbf{i}=\mathbf{j}$" 这个结论的对应物就是 "$\varphi(\mathbf{i})=\varphi(\mathbf{j})$"。
   • 因此，如果算法推导出 $\mathbf{i}=\mathbf{j}$，那么必然有 $\varphi(\mathbf{i})=\varphi(\mathbf{j})$。引理得证。

这是定理证明的最后一部分，它完成了对映射 $\varphi^*$ 是双射的证明。

1. 证明满射性 (Surjectivity):
   • 我们需要证明，对于理论世界中任何一个陪集 $C \in \mathcal{C}$，都存在一个计算世界中的索引 $\mathbf{i} \in \mathbf{I}^*$，使得 $\varphi^*(\mathbf{i})=C$。
   • 证明思路:
   • $G$ 在 $\mathcal{C}$ 上的操作是传递的。这意味着任何陪集 $C$ 都可以从起始陪集 $[H]$ 通过某个群操作得到，即 $C = [H] \cdot g$ for some $g \in G$。
   • 算法的构造过程也是传递的（规则4），这意味着所有索引 $\mathbf{i}$ 都是从索引 1 通过群操作得到的，即 $\mathbf{i} = \mathbf{1} \cdot g$。
   • 由于算法会持续探索，直到无法定义新的陪集为止，它会探索出由 $\mathbf{1}$ 出发能到达的所有地方。
   • 因为 $\varphi^*(\mathbf{1})=[H]$，并且映射是操作兼容的 ($\varphi^*(\mathbf{1} \cdot g) = \varphi^*(\mathbf{1}) \cdot g = [H]g$)，所以算法探索到的索引集合 $\mathbf{I}^*$ 将会恰好映射到由 $[H]$ 出发能到达的所有陪集——也就是整个 $\mathcal{C}$。
   • 因此，$\varphi^*$ 是满射。
2. 证明单射性 (Injectivity):
   • 我们需要证明，如果 $\varphi^*(\mathbf{i}) = \varphi^*(\mathbf{j})$，那么必然有 $\mathbf{i}=\mathbf{j}$。
   • 证明思路:
   • 步骤1: 用群元素表示索引和陪集
   • 由于 $G$ 在 $\mathbf{I}^*$ 上的操作是传递的，所以对于任意索引 $\mathbf{i}$，都存在一个群元素 $a \in G$ 使得 $\mathbf{i} = \mathbf{1} \cdot a$。
   • 由于 $\varphi^*$ 是操作兼容的，所以 $\varphi^*(\mathbf{i}) = \varphi^*(\mathbf{1} \cdot a) = \varphi^*(\mathbf{1}) \cdot a = [H]a$。
   • 同理，对于索引 $\mathbf{j}$，存在 $b \in G$ 使得 $\mathbf{j}=\mathbf{1}\cdot b$ 且 $\varphi^*(\mathbf{j}) = [H]b$。
   • 步骤2: 利用单射的假设
   • 假设 $\varphi^*(\mathbf{i}) = \varphi^*(\mathbf{j})$。
   • 代入上面的表达式，我们得到 $[H]a = [H]b$。
   • 步骤3: 使用陪集理论
   • $[H]a = [H]b$ 当且仅当 $ab^{-1} \in H$。
   • (原文用的是 $H=Hba^{-1}$，然后 $ba^{-1} \in H$，是等价的)。
   • 步骤4: 将陪集理论的结论转换回索引世界
   • 我们知道 $ba^{-1}$ 是子群 $H$ 的一个元素。
   • 我们还知道，算法的构造保证了子群 $H$ 稳定索引 1。这意味着，对于任何 $h \in H$，都有 $\mathbf{1} \cdot h = \mathbf{1}$。
   • 因为 $ba^{-1} \in H$，所以 $\mathbf{1} \cdot (ba^{-1}) = \mathbf{1}$。
   • 两边同时右乘 $a$：$(\mathbf{1} \cdot b a^{-1}) \cdot a = \mathbf{1} \cdot a$。
   • 利用操作的结合律：$\mathbf{1} \cdot (ba^{-1}a) = \mathbf{1} \cdot a$。
   • $\mathbf{1} \cdot b = \mathbf{1} \cdot a$。
   • 步骤5: 得出结论
   • 我们已经知道 $\mathbf{j} = \mathbf{1} \cdot b$ 和 $\mathbf{i} = \mathbf{1} \cdot a$。
   • 因此，我们证明了 $\mathbf{j} = \mathbf{i}$。
   • 单射性得证。
3. 最终结论:
   • 因为 $\varphi^*$ 既是满射又是单射，所以它是双射。
   • 又因为它的构造保证了操作兼容性，所以它是一个G-同构。
   • 这完成了整个定理的证明。

这句话是英国哲学家、数学家伯特兰·罗素的一句名言，被作者引用在此，用以评论一种特定的思维方式。

1. 引言的字面意思:
   • “我们想要什么就假定什么的方法”（The method of postulating what we want）指的是一种不经过证明或推导，直接把期望的结论作为前提来使用的做法。
   • 罗素将这种方法的“优点”与“盗窃相对于诚实劳动的优点”相提并论。
   • 盗窃的“优点”是什么？快速、省力、直接得到结果。
   • 诚实劳动的特点是什么？辛苦、耗时、一步一个脚印。
2. 引言的寓意:
   • 罗素以一种讽刺的口吻批评了这种“直接假定结论”的思维方式。它虽然能让人很快地“得到”想要的结论，但这是一种智力上的不诚实，绕过了严谨论证的艰苦过程。
   • 就像盗窃一样，这种方法得到的“财富”（结论）是没有合法性基础的，是虚假的、不可靠的。
   • 真正的知识和理解，必须通过“诚实劳动”——即严谨的逻辑推导和证明——来获得。
3. 在本章上下文中的含义:
   • 作者将这句话放在 Todd-Coxeter 算法 的正确性证明之后，其用意可能是多重的：
   • 自我肯定: 暗示本章所做的艰苦工作（详细解释算法步骤、并证明其正确性）是“诚实劳动”。我们没有直接假定“算法是正确的”，而是通过一步步的论证来建立它的可靠性。
   • 对比: 与那些可能在不理解其原理的情况下就随意使用算法，或者满足于“它似乎能用”的模糊认识的做法形成对比。
   • 对数学精神的颂扬: 强调了数学的核心精神——严谨性。在数学中，一个结论的价值不在于它看起来多么美好，而在于它能否被无可辩驳地证明。
   • 幽默感: 在一段高度技术性的、枯燥的证明之后，引用罗素的这句俏皮话，可以调节气氛，让读者会心一笑，同时加深对严谨性重要性的印象。

这部分是本章的课后练习题，旨在帮助读者巩固本章（第七章 群操作）学习到的概念和方法。练习题覆盖了从凯莱定理、类方程、p-群、Sylow定理到本节的生成元与关系和 Todd-Coxeter 算法 的所有内容。

对每个小节的练习题进行简要分析：

• 第1节 Cayley 定理:
• 1.1: 这是一个基础的群操作定义验证题。需要验证两个公理：1) $e * x = x$ (单位元操作)；2) $(g_1g_2)*x = g_1*(g_2*x)$ (结合律)。让我们来验证一下：
• $e*x = xe^{-1} = xe = x$。公理1成立。
• $(g_1g_2)*x = x(g_1g_2)^{-1} = xg_2^{-1}g_1^{-1}$。
• $g_1*(g_2*x) = g_1*(xg_2^{-1}) = (xg_2^{-1})g_1^{-1} = xg_2^{-1}g_1^{-1}$。
• 公理2也成立。所以，它确实定义了一个操作。这种操作有时被称为右反操作。
• 1.2: 考察对轨道概念的理解。$H$ 在 $G$ 上的左乘操作，一个元素 $g \in G$ 的轨道是 $\{h g \mid h \in H\}$，这正是 $g$ 所在的右陪集 $Hg$。所以，轨道就是 $G$ 的右陪集。

• 第2节 类方程: 练习计算中心化子、共轭类的大小，以及利用类方程推断群的结构。这是群操作理论的核心应用。

• 第3节 p-群: 练习应用p-群的性质，特别是其非平凡的中心，来分析群的结构。

• 第4节 二十面体群: 针对具体的对称群，练习计算类方程和分析其正规子群。

• 第5节 对称群中的共轭: 练习置换群的计算，包括生成元、中心化子、共轭类（由循环结构决定）等。

• 第6节 正规化子: 练习正规化子和共轭子群的概念。

• 第7节 Sylow 定理: 练习应用强大的Sylow定理来分析有限群的子群结构，特别是用于证明某些阶的群不是单群或对其进行分类。

• 第8节 阶为12的群: 这是一个综合应用前面所有知识对特定阶的群进行分类的练习。

• 第9节 自由群: 考察对自由群这个最基本构造的理解。

• 第10节 生成元与关系: 练习如何使用和理解群的表示，包括映射性质、交换子子群等。

• 第11节 Todd-Coxeter 算法:
• 11.1-11.3: 这些是核心的计算练习，要求读者亲手执行 Todd-Coxeter 算法 来分析给定的群表示，确定其阶和结构。这是对本节内容的直接应用。
• 11.4: 这是一个概念题，考察对算法输出表格的解读能力。如果一个子群 $H$ 是正规的，那么它所有的陪集构成的商群 $G/H$ 是一个群。这会如何体现在表格中？（提示：陪集的乘法会是良定义的）。
• 11.5-11.8: 更复杂的应用，有些涉及到证明群的平凡性或与著名群（如二面体群、多面体群、$A_5$）的同构关系。

• 杂项问题: 提供了一些更具挑战性或综合性的问题，融合了本章的多个概念。