# 群同构测试：从 Abel 群标准形到循环扩张的作用矩阵 两个群可以使用完全不同的元素标签、不同的生成元、不同的乘法表写法，却具有完全相同的乘法结构——就像同一篇文章的两种不同语言的译本。群同构问题（group isomorphism problem）要求判断两个给定的群之间是否存在**同构**，即双射 $\varphi:G\to H$ 满足 $$ \varphi(xy)=\varphi(x)\varphi(y)\qquad(\forall x,y\in G). $$ 这个问题是著名的图同构问题的"近亲"，其精确复杂度至今悬而未决：对一般黑盒群，既无已知的多对数时间经典算法，也尚无统一的多对数时间量子算法。但是，一旦对群的结构加以限制，局面就完全不同。本文讲清两个正结果的来龙去脉： 1. **Abel 群**（Cheung–Mosca，Zoo 127）：有限 Abel 群可以由不变因子序列完全分类，而分解可以归结为 Abel 隐藏子群问题，因此量子算法在 $\operatorname{poly}(\log|G|)$ 时间内不仅能判定同构，还能把同构映射显式构造出来； 2. **Abel 正规子群被循环群扩张**的一类非交换群（Le Gall，Zoo 128）：同构测试被进一步化为"作用矩阵的幂后共轭"问题，再化为可由 Abel HSP 求解的多重集合离散对数。 阅读本文需要 Abel 隐藏子群问题（见[Abel 隐藏子群问题](abelian-hidden-subgroup.md)）和 Shor 阶查找（见 [Shor 算法](../ch04-classic-algorithms/shors-algorithm-tutorial.md)）作为前提；本文不再重新推导它们，只引用结论。 :::{admonition} 本课知识点 :class: tip 1. **[同构与结构不变量](#iso-and-invariants)**——能写出群同构的定义并验证 $\varphi(a)=i^{\,a}$ 这类具体映射是同构，举出群阶相同却不同构的例子，并解释为什么算法必须计算规范结构而不是比较统计量。 2. **[黑盒群模型与经典瓶颈](#black-box-model-bottleneck)**——能列出黑盒群模型的输入与接口，说明输入长度只有 $O(\log|G|)$，并解释枚举全部群元素的算法为何对输入长度是指数时间。 3. **[关系子群与 Abel HSP 分解](#relation-subgroup-hsp)**——能由生成元构造同态 $\Phi$ 与关系子群 $K=\ker\Phi$，验证 $\Phi$ 满足 Abel HSP 的两个条件，并由同构定理得出 $G\cong D/K$。 4. **[Smith 标准形与不变因子判定](#smith-invariant-factors)**——能用幺模行列变换把关系矩阵化为 Smith 标准形，写出"不变因子序列相同当且仅当同构"的判定准则，并手算小例子核对。 5. **[Abel-by-cyclic 群与作用矩阵](#abel-by-cyclic-action)**——能写出半直积 $G\cong A\rtimes_\alpha\mathbb Z_m$ 的乘法公式，解释非交换性为何全部来自共轭作用 $\alpha$，并把 $\alpha$ 表示为各 Sylow 分量上的矩阵。 6. **[幂后共轭判据](#power-conjugacy-criterion)**——能推导 $PM_\alpha P^{-1}=M_\beta^{\,k}$（$k\in\mathbb Z_m^*$），并指出推导中"$B$ 可交换"与"$k$ 为单位"两个不可省略的依据。 7. **[多重集合离散对数](#set-discrete-log)**——能把"幂后相似"化为特征值多重集合的离散对数问题，并解释朴素配对做法的两个指数障碍及 Le Gall 如何用 Abel HSP 消除它们。 8. **[最小例子与适用边界](#minimal-example-boundary)**——能在 $\mathbb Z_3\rtimes\mathbb Z_2$ 的最小例子上运用判据区分 $\mathbb Z_6$ 与 $S_3$，并列出结果依赖的结构承诺与模型承诺。 ::: ## 1. 问题从哪里来：标签与结构 (iso-and-invariants)= ### 1.1 同构是"换一套标签" 先建立一个具体直觉。考虑两个群：一个是模 $4$ 加法群 $$ \mathbb Z_4=\{0,1,2,3\},\qquad x*y=(x+y)\bmod 4, $$ 另一个是复数乘法群 $\{1,i,-1,-i\}$。它们的元素名字、运算符号完全不同，但映射 $$ \varphi:\mathbb Z_4\to\{1,i,-1,-i\},\qquad \varphi(a)=i^{\,a} $$ 满足 $\varphi(a*b)=i^{a+b\bmod 4}=i^a i^b=\varphi(a)\varphi(b)$（这里用了 $i^4=1$，所以指数可以模 $4$ 计算）。因此两个群同构：**群的本质是乘法表的结构，而不是元素的名字**。 同构测试的困难恰恰在于：算法拿到的只有"名字"（标签），而需要回答"结构"问题。两个群可能标签体系毫无相似之处，结构却相同；也可能许多容易计算的统计量全部吻合，结构却不同。 ### 1.2 为什么群阶远远不够 同构必保持一切"结构不变量"：群阶、每个元素的阶、中心、交换性等等。反过来，比较不变量是否足够？不够——这些不变量通常不完备。例如 $$ \mathbb Z_6 \quad\text{与}\quad S_3 $$ 都有 $6$ 个元素，但一个是 Abel 群、一个不是（$S_3$ 中两个对换不交换），因此不同构。这个例子里"交换性"一个不变量就足够区分；但加上更多统计量之后，仍然存在所有常见不变量都吻合却不同构的群对。结论：**算法必须产生规范结构（canonical form），或者直接构造出同构映射**，而不是只比较若干容易计算的统计量。这是全文的指导思想。 (black-box-model-bottleneck)= ### 1.3 黑盒群模型与经典瓶颈 本文采用**黑盒群（black-box group）模型**，这是讨论群算法查询复杂度的标准设定： - 群 $G$ 的每个元素被编码为一个唯一的长度 $n=O(\log|G|)$ 的比特串（unique encoding：一个元素只有一个合法标签）； - 算法只能通过群运算预言机做乘法、求逆、判断相等； - 输入还包括一小组生成元 $g_1,\ldots,g_k$。 注意输入长度只有 $O(\log|G|)$：几个生成元加上预言机接口。因此，**任何需要枚举全部 $|G|$ 个元素的算法，对输入长度而言都是指数时间的**。经典算法面对的正是这个瓶颈：如果群以完整乘法表给出（输入长度约 $|G|^2\log|G|$），经典算法可以穷举生成元的像，在约 $|G|^{\log|G|+O(1)}$ 时间内判定同构；对图同构，已有拟多项式时间的经典算法。但在黑盒模型下输入只有 $O(\log|G|)$ 长，这些"指数级枚举"办法全部失效，经典算法对一般黑盒群是指数时间的。量子算法的机会在于：Shor 式的周期/隐藏子群机制恰好能在 $\operatorname{poly}(\log|G|)$ 时间内提取群的"关系结构"，这正是同构测试所需要的信息。 ### 1.4 历史脉络 - **Zoo 127（Cheung–Mosca, 2001）**：给出分解有限 Abel 黑盒群的量子算法——求出一组生成元及完整关系，把 Abel 群写成循环群直积。Abel 群同构测试是它的直接推论。 - **Zoo 128（Le Gall, 2010）**：把同构测试推进到一类非交换群——含 Abel 正规子群 $A$、且商群为与 $|A|$ 互素的循环群的群（"Abel-by-cyclic"）。算法把问题化为有限域上矩阵的"幂后共轭"与多重集合离散对数，仍由 Abel HSP 求解。 - **Zoo 202（Zatloukal, 2013）**：研究更一般的群扩张等价测试，用 Abel HSP 加速作用相容性与上同调类的检查。 需要在一开始就强调：这些结果**都没有**解决一般群同构问题，也**没有**直接解决图同构问题。它们依赖明确的结构承诺（Abel、Abel-by-cyclic、互素阶、唯一编码），本文第 7 节会回到这个边界。 ## 2. 工具箱回顾 本文反复使用四件工具，这里只陈述结论并注明出处，不重新推导。 **阶查找（order finding）**。给定黑盒群中元素 $g$，求最小正整数 $r$ 使 $g^r=e$。量子算法（Shor 阶查找，即相位估计作用于模乘酉算子的群论版本）在 $\operatorname{poly}(\log|G|)$ 时间完成。 **Abel 隐藏子群问题（Abelian HSP）**。设 $D$ 为已知结构的有限 Abel 群，函数 $f:D\to S$ 满足：存在子群 $K\le D$，使得 $f$ 在 $K$ 的每个陪集上取常值、在不同陪集上取不同值。这样的 $f$ 称为**隐藏（hide）子群 $K$**。量子算法（Simon/Shor 框架对一般 Abel 群的推广）用 $\operatorname{poly}(\log|D|)$ 次查询求出 $K$ 的一组生成元。详见[Abel 隐藏子群问题](abelian-hidden-subgroup.md)。 **构造性成员测试（constructive membership）**。给定生成元 $g_1,\ldots,g_k$ 和元素 $h\in G$（$G$ Abel），求指数向量 $a$ 使 $h=\prod_i g_i^{a_i}$。做法是对函数 $(a,t)\mapsto \Phi(a)\cdot h^{-t}$（其中 $\Phi$ 见下节）做 Abel HSP：隐藏子群由关系与 $h$ 的表示共同生成，求出后即读出 $a$。复杂度同为 $\operatorname{poly}(\log|G|)$。 **Smith 标准形（Smith normal form）**。对任意整数矩阵 $R$，存在行列式为 $\pm1$ 的整数方阵（幺模矩阵）$U,V$，使 $$ URV=\operatorname{diag}(d_1,d_2,\ldots,d_t,0,\ldots,0), \qquad d_1\mid d_2\mid\cdots\mid d_t,\quad d_i\ge1. $$ 对角元 $d_i$（不变因子）由 $R$ 唯一确定；$U,V$ 与对角化过程可以在多项式时间内算出（经典算法，只需要整数行列运算）。 ## 3. Abel 群：关系子群与 Smith 标准形 本节把 Cheung–Mosca 分解完整走一遍。核心思想一句话：**Abel 群与"循环群直积"之间的差别，全部藏在生成元满足的关系里；而关系构成一个格子（$\mathbb Z^k$ 的子群），量子算法擅长的正是找格子。** (relation-subgroup-hsp)= ### 3.1 从生成元到关系子群 设 Abel 黑盒群 $G$ 的生成元为 $g_1,\ldots,g_k$。第一步，用量子阶查找求出每个生成元的阶 $$ r_i=|g_i|,\qquad i=1,\ldots,k, $$ 即最小正整数使 $g_i^{r_i}=e$。第二步，定义"自由"直积群到 $G$ 的映射 $$ \Phi: D=\mathbb Z_{r_1}\times\cdots\times\mathbb Z_{r_k} \longrightarrow G, \qquad a=(a_1,\ldots,a_k)\mapsto\prod_{i=1}^k g_i^{a_i}. $$ 先验证 $\Phi$ 是群同态。这一步**必须用到 $G$ 是 Abel 群**： $$ \Phi(a+b)=\prod_i g_i^{a_i+b_i} =\prod_i g_i^{a_i}\,g_i^{b_i} =\left(\prod_i g_i^{a_i}\right)\left(\prod_i g_i^{b_i}\right) =\Phi(a)\Phi(b), $$ 其中第三个等号把 $g_i^{b_i}$ 逐个移到对应位置，只有两两可交换时才合法。由于 $g_1,\ldots,g_k$ 生成 $G$，每个群元素都能写成 $\prod_i g_i^{a_i}$，即 $\Phi$ 是**满射**。 定义关系子群 $$ K=\ker\Phi=\{a\in D:\ g_1^{a_1}\cdots g_k^{a_k}=e\}. $$ $K$ 正是"生成元之间全部乘法关系"的集合：每个 $a\in K$ 是一条关系 $g_1^{a_1}\cdots g_k^{a_k}=e$。例如若 $g_1g_2=g_2g_1$ 之外的唯一关系是 $g_1^2=g_2^3$，那么 $(2,-3)\in K$。 ### 3.2 用 Abel HSP 求关系子群 把 $\Phi$ 看成函数 $f:D\to G$（输出用元素的标签表示）。它满足 Abel HSP 的全部条件： - $f$ 在 $K$ 的每个陪集上取常值：若 $b=a+k$、$k\in K$，则 $$ f(b)=\Phi(a+k)=\Phi(a)\Phi(k)=\Phi(a)\cdot e=f(a), $$ 用了同态性质与 $k\in\ker\Phi$； - $f$ 在不同陪集上取不同值：若 $f(a)=f(b)$，则 $\Phi(a-b)=\Phi(a)\Phi(b)^{-1}=e$，即 $a-b\in K$，二者属于同一陪集。 （这正是群同态基本定理证明里"纤维即陪集"的那一步。）因此运行 Abel HSP 算法，用 $\operatorname{poly}(\log|D|)$ 次查询得到 $K$ 的一组生成元 $k^{(1)},\ldots,k^{(s)}\in D$——每个生成元是一个 $k$ 维整数向量（分量按模 $r_i$ 理解）。 再由群同态基本定理（第一同构定理）：满同态 $\Phi:D\to G$ 诱导同构 $$ G\cong D/K. $$ 到此，$G$ 的结构完全被"数据化"：$D$ 是已知的循环直积，$K$ 是已知生成元的子群。 (smith-invariant-factors)= ### 3.3 Smith 标准形：从关系到不变因子 $D/K$ 仍不是一个"规范"的答案——同一个群可以由不同的 $D,K$ 给出。规范化的工具是 Smith 标准形。 把 $K$ 的生成元写成行向量，添上各分量的模 $r_i$ 关系，排成一个整数矩阵 $R$（**关系矩阵**，relation matrix）：每一行是 $\mathbb Z^k$ 中一个把生成元组合映到 $e$ 的关系。于是 $$ G\cong \mathbb Z^k/\langle R\text{ 的行}\rangle. $$ 对这个商群做 Smith 标准形的代数含义是： - **行变换**（左乘幺模阵 $U$）= 更换关系集合的基，不改变它们生成的子群； - **列变换**（右乘幺模阵 $V$）= 更换 $\mathbb Z^k$ 的基，也就是把 $g_1,\ldots,g_k$ 换成一组新生成元 $h_j=\prod_i g_i^{V_{ij}}$（整数可逆组合仍生成同一个群）。 由于行列变换不改变商群的同构型，Smith 标准形给出 $$ G\cong \mathbb Z_{d_1}\times\cdots\times\mathbb Z_{d_t}, \qquad d_1\mid d_2\mid\cdots\mid d_t, $$ 其中删去了 $d_i=1$ 的平凡因子。**不变因子序列 $(d_1,\ldots,d_t)$ 由 $G$ 唯一确定**（Smith 标准形的唯一性），因此： > **判定准则**：两个有限 Abel 群同构，当且仅当它们的不变因子序列 $(d_1,\ldots,d_t)$ 完全相同。 这就是第 1.2 节所说的"规范结构"：同构测试被归结为计算并比较一个整数序列。而且 Smith 变换的矩阵 $V$ 记录了新基与旧生成元之间的坐标，所以算法不只是回答 yes/no——把两边的规范基对齐，就能**构造**出显式同构映射（constructive membership 负责把任意元素换算到规范基坐标）。 ### 3.4 小例子：手算一次 Smith 标准形 设 Abel 群 $G$ 由 $g_1,g_2$ 生成，阶查找给出 $r_1=r_2=6$，即 $D=\mathbb Z_6\times\mathbb Z_6$。运行 Abel HSP 后，设返回的关系子群 $K$ 由 $$ k^{(1)}=(2,2),\qquad k^{(2)}=(0,3) $$ 生成（即关系 $g_1^2g_2^2=e$ 与 $g_2^3=e$）。关系矩阵为 $$ R=\begin{pmatrix}2&2\\0&3\end{pmatrix}. $$ 下面只做整数幺模行列运算，把 $R$ 对角化。每一步都标注依据： 第一步，第 2 列减去第 1 列（列变换，合法）： $$ \begin{pmatrix}2&0\\0&3\end{pmatrix}. $$ 第二步，把第 2 列加到第 1 列，再把第 1 行从第 2 行中减去，目的是用 $\gcd(2,3)=1$ 造出角上的 $1$： $$ \begin{pmatrix}2&0\\0&3\end{pmatrix} \xrightarrow{C_1\leftarrow C_1+C_2} \begin{pmatrix}2&0\\3&3\end{pmatrix} \xrightarrow{R_2\leftarrow R_2-R_1} \begin{pmatrix}2&0\\1&3\end{pmatrix}. $$ 第三步，交换两行把 $1$ 换到左上角，再消去同行的 $3$ 与同列的 $2$： $$ \begin{pmatrix}2&0\\1&3\end{pmatrix} \xrightarrow{R_1\leftrightarrow R_2} \begin{pmatrix}1&3\\2&0\end{pmatrix} \xrightarrow{C_2\leftarrow C_2-3C_1} \begin{pmatrix}1&0\\2&-6\end{pmatrix} \xrightarrow{R_2\leftarrow R_2-2R_1} \begin{pmatrix}1&0\\0&-6\end{pmatrix}. $$ 最后把第二行乘以 $-1$（幺模），得到 Smith 标准形 $$ \operatorname{diag}(1,6). $$ 验证：对角元整除关系 $1\mid6$ 成立；行列式绝对值 $=6=|K|$ 在变换下不变（幺模变换行列式为 $\pm1$）。因此 $$ G\cong\mathbb Z_1\times\mathbb Z_6=\mathbb Z_6. $$ 虽然 $G$ 由两个 $6$ 阶元素生成、表面上"像" $\mathbb Z_6\times\mathbb Z_6$，关系 $g_1^2g_2^2=e$、$g_2^3=e$ 实际上把它"压缩"成了一个 $6$ 阶循环群。不变因子序列 $(6)$ 就是这个群在同构意义下的"指纹"。 ### 3.5 复杂度逐项分析 整条流水线关于输入长度 $\log|G|$ 是多项式的，逐项看每个因子： 1. **阶查找**：对 $k$ 个生成元各做一次 Shor 阶查找。生成元个数 $k\le\log_2|G|$（每个生成元至少使群阶翻倍，严格说是群有一个长度 $\le\log_2|G|$ 的生成元链），单次代价 $\operatorname{poly}(\log|G|)$，合计 $\operatorname{poly}(\log|G|)$。 2. **Abel HSP**：作用在 $D=\prod_i\mathbb Z_{r_i}$ 上，$\log|D|=\sum_i\log r_i=O(k\log|G|)$，故查询与后处理都是 $\operatorname{poly}(\log|G|)$。 3. **Smith 标准形**：经典多项式时间算法，矩阵规模 $O(k)$、表值 $O(\log|G|)$ 比特，代价 $\operatorname{poly}(k,\log|G|)$。 4. **构造性成员测试**（组装同构时用到）：每次 $\operatorname{poly}(\log|G|)$。 每一项都是 $\operatorname{poly}(\log|G|)$，复合仍是 $\operatorname{poly}(\log|G|)$。这就是"Abel 群同构测试有多对数时间量子算法"的完整含义——注意它不是单一的量子加速点，而是阶查找与 HSP 两个量子子程序嵌在多项式时间的经典框架里。 ## 4. 循环扩张类 $\mathscr S$ Abel 群的情形解决后，自然的下一步是"离 Abel 群最近"的非交换群。Le Gall（Zoo 128）考虑满足 $$ G=\langle A,y\rangle $$ 的一类群，其中 $$ A\trianglelefteq G,\qquad A\ \text{Abelian},\qquad |y|=m,\qquad\gcd(|A|,m)=1. $$ 也就是说：$G$ 由一个 Abel 正规子群 $A$ 和一个循环补 $\langle y\rangle\cong\mathbb Z_m$ 生成，并且两部分阶互素。这类群称为 **Abel-by-cyclic** 群。 ### 4.1 直觉：非交换性只有一个来源 先看这个结构"长什么样"。由于 $A\trianglelefteq G$ 且 $G/A=\langle yA\rangle\cong\mathbb Z_m$，每个元素都能唯一写成 $$ g=a\,y^j,\qquad a\in A,\ j\in\mathbb Z_m. $$ 两个元素相乘时，麻烦出在把 $y^j$"穿过"$b$： $$ (a y^i)(b y^j)=a\,y^i b\,y^{-i}\,y^{i+j} =a\,\alpha^i(b)\,y^{i+j}, $$ 其中 $$ \alpha(a)=yay^{-1} $$ 是 $y$ 对 $A$ 的**共轭作用**。因为 $A$ 正规，$yay^{-1}\in A$，所以 $\alpha$ 是 $A$ 的一个自同构；因为 $|y|=m$，$\alpha^m(a)=y^may^{-m}=a$，即 $\alpha^m=\mathrm{id}$。 这个乘法公式说明：**$G$ 的全部非交换性都来自 $\alpha$**。若 $\alpha=\mathrm{id}$，则 $G=A\times\mathbb Z_m$ 是 Abel 群；$\alpha$ 越"不平凡"，群越非交换。结构上这是一个半直积 $$ G\cong A\rtimes_{\alpha}\mathbb Z_m. $$ 这里需要交代 $\gcd(|A|,m)=1$ 这个条件的作用：群论中的 Schur–Zassenhaus 定理保证，当正规子群与商群的阶互素时，扩张一定**分裂**——$G$ 一定是半直积（而不是更一般的、由 $2$-cocycle 扭结的扩张，后者见第 7 节），并且补群存在且在共轭意义下唯一。本文不证明这个定理，但要记住结论：**互素阶保证了"$A$ 加循环补"这个描述是完备且良定义的**，这是整个算法能成立的前提之一。 (abel-by-cyclic-action)= ### 4.2 作用矩阵：把 $\alpha$ 变成线性代数 要让算法处理 $\alpha$，需要把它写成矩阵。分三步： 第一步，用第 3 节的方法把 $A$ 分解为不变因子直积，并按素数归并为 Sylow 分量： $$ A=A_{p_1}\times A_{p_2}\times\cdots, \qquad A_p=\mathbb Z_{p^{e_1}}\times\cdots\times\mathbb Z_{p^{e_s}}. $$ 第二步，注意 Abel 群的每个 Sylow $p$-子群是唯一的（所有 $p$ 幂阶元素的集合），因此被任何自同构保持。所以 $\alpha$ 分解为各 Sylow 分量上的自同构 $\alpha_p$，不存在分量之间的交叉项。 第三步，在每个 Sylow 分量上取定 Abel 基后，$\alpha_p$ 就是一个可逆的整数线性变换；在分量的底（即 $p$-挠部分）上，它表示为有限域 $\mathbb F_p$ 上的可逆矩阵 $M$。于是 > 群结构由三类数据完全控制： > > 1. Abel 群 $A$ 的不变因子（第 3 节已解决）； > 2. 循环补群的阶 $m$； > 3. 作用自同构 $\alpha$ 在合适基下的矩阵（的共轭类）。 第 3 点是新东西，也是同构测试的难点所在：基可以任意换，$M$ 本身不是不变量，$M$ 的**共轭类**（相似类）才是。 ### 4.3 标准分解：消除表达的任意性 还有一个更隐蔽的任意性：同一个群 $G$ 可能有多种 $(A,y)$ 表达。例如 $G=A\rtimes\mathbb Z_m$ 中把 $y$ 换成 $y^k$（$\gcd(k,m)=1$）仍是合法补群生成元；$A$ 也可能有多个"最大的"候选。如果两个待测群各自给出不同的表达，直接比较矩阵毫无意义。 Le Gall 的解决办法是定义**标准分解（standard decomposition）**：在所有合法分解中取**循环阶最小**（因而最规范）的那个，把它作为群的规范描述。计算标准分解只需要： - 量子阶查找（测候选 $y$ 的阶）； - Abel 群分解（第 3 节，刻画候选 $A$）； - 构造性成员测试（检验元素属于哪个子群、换算坐标）。 每件工具都是 $\operatorname{poly}(\log|G|)$，候选的数量也有多项式界，所以这一步整体关于 $\log|G|$ 为多项式。此后，同构测试只需在两边标准分解之间进行。 ## 5. 同构判据：幂后共轭 ### 5.1 设定与目标 设两个待测群已经算出匹配的标准分解 $$ G=A\rtimes_{\alpha}\langle y\rangle,\qquad H=B\rtimes_{\beta}\langle z\rangle, $$ 并且前置检查已通过：$A\cong B$（用第 3 节的 Abel 判定准则）、$|y|=|z|=m$。记 $\alpha,\beta$ 在各自 Abel 基下的作用矩阵为 $M_\alpha,M_\beta$（在各有限域分量上分别讨论）。本节推导： > **同构判据**：$G\cong H$ 当且仅当存在 $k\in\mathbb Z_m^*$ 与基变换 $P$，使 > > $$P\,M_\alpha\,P^{-1}=M_\beta^{\,k}.$$ > > 即：**一个矩阵与另一个矩阵的第 $k$ 次幂相似**——"幂后共轭"。 ### 5.2 同构在补群上能做什么 设 $\varphi:G\to H$ 是同构。先看 $\varphi(y)$。把 $\varphi$ 复合上商映射 $H\to H/B\cong\mathbb Z_m$，得到满同态 $G\to\mathbb Z_m$，其核包含 $A$；标准分解的匹配性保证它诱导的正是商群之间的同构 $G/A\to H/B$。而 $\mathbb Z_m$ 的自同构恰为乘以单位 $k\in\mathbb Z_m^*$（生成元必须映到生成元，阶为 $m$ 的元素恰为 $z^k$、$\gcd(k,m)=1$）。因此 $$ \varphi(y)=b\,z^k,\qquad b\in B,\ k\in\mathbb Z_m^*. $$ 同时，标准分解的规范性保证 $\varphi$ 把 $A$ 映到 $B$；在两边 Abel 基下，这个 Abel 群同构就是一个可逆的基变换矩阵 $P$： $$ \varphi(a)\ \longleftrightarrow\ P\,\mathbf a, $$ 其中 $\mathbf a$ 是 $a$ 的坐标列向量。 (power-conjugacy-criterion)= ### 5.3 逐步推导幂后共轭方程 同构必须保持共轭作用，即对一切 $a\in A$： $$ \varphi\bigl(y\,a\,y^{-1}\bigr)=\varphi(y)\,\varphi(a)\,\varphi(y)^{-1}. $$ **左边**：由 $\alpha$ 的定义，$yay^{-1}=\alpha(a)$，所以左边 $=\varphi(\alpha(a))$，坐标为 $$ P\,M_\alpha\,\mathbf a. $$ **右边**：代入 $\varphi(y)=bz^k$： $$ (bz^k)\,\varphi(a)\,(bz^k)^{-1} =b\,z^k\,\varphi(a)\,z^{-k}\,b^{-1}. $$ 关键一步：$\varphi(a)\in B$ 且 $B$ 是 **Abel 群**，所以 $b$ 与 $z^k\varphi(a)z^{-k}\in B$ 可交换，$b\cdots b^{-1}$ 消去： $$ b\,z^k\,\varphi(a)\,z^{-k}\,b^{-1} =z^k\,\varphi(a)\,z^{-k} =\beta^{\,k}\bigl(\varphi(a)\bigr), $$ 最后一步用了 $\beta$ 的定义迭代 $k$ 次（$\beta^k(c)=z^k c z^{-k}$）。右边坐标为 $$ M_\beta^{\,k}\,P\,\mathbf a. $$ 左右相等且对一切 $\mathbf a$ 成立，因此 $$ P\,M_\alpha\,\mathbf a=M_\beta^{\,k}P\,\mathbf a \ \Longrightarrow\ P\,M_\alpha\,P^{-1}=M_\beta^{\,k}. $$ 这就是判据的必要性。充分性也成立：给定满足方程的 $k,P$，定义 $\varphi(ay^j)=\bigl(P\text{ 对应的元素}\bigr)z^{kj}$，直接验证它保持第 4.1 节的乘法公式，从而是同构。推导中两处不可省略的依据再强调一次：**$B$ 可交换**（消去 $b$）和 **$k$ 必须是单位**（商群同构）。 (set-discrete-log)= ### 5.4 从矩阵相似到多重集合离散对数 剩下的问题是纯线性代数：给定 $M_\alpha,M_\beta$，是否存在 $k\in\mathbb Z_m^*$ 使 $M_\alpha\sim M_\beta^k$（相似）？ 矩阵相似当且仅当有理标准形（rational canonical form）相同，等价地不变因子/初等因子组相同。若逐个枚举 $k\in\mathbb Z_m^*$ 再比较有理标准形，$k$ 有 $\varphi(m)$ 种取法，而 $m$ 可以到 $|G|$ 量级——这是指数搜索，必须避免。 换个角度看相似条件。把特征多项式在扩域中完全分解，设 $M_\alpha$ 的特征值多重集合为 $$ X=\{x_1,\ldots,x_v\},\qquad M_\beta\ \text{的特征值多重集合为}\ Y=\{y_1,\ldots,y_v\}. $$ 相似矩阵有相同的特征值多重集合；而 $M_\beta^k$ 的特征值恰为 $\{y_1^k,\ldots,y_v^k\}$（特征值随矩阵幂次取幂，这是 Jordan 块或直接对角化的直接推论）。于是必要条件——并且在配合有理标准形逐块核对后也是充分条件——是： > **多重集合离散对数（set discrete logarithm）**：给定有限域（扩域）中的两个多重集合 $X,Y$，寻找 $k$ 使 > > $$\{y_1^k,\ldots,y_v^k\}=X\quad(\text{作为多重集合相等}).$$ ### 5.5 为什么朴素做法失败，Le Gall 如何解决 朴素思路是"逐个猜配对"：猜 $x_1=y_{\pi(1)}^k$，解普通离散对数得 $k$，再验证其余元素。它有两个指数障碍： 1. **配对组合爆炸**：$v$ 个元素的配对有 $v!$ 种，逐一枚举是指数的。 2. **模阶歧义**：由单个方程 $x_i=y_{\pi(i)}^k$ 解出的 $k$ 只确定到模 $\operatorname{ord}(y_{\pi(i)})$；不同配对给出不同模数的剩余类，中国剩余定理不一定能把它们拼成一个公共的 $k$（各 $\operatorname{ord}(y_j)$ 未必互素，同余式组可能不相容，需要回溯）。 Le Gall 的观察是：这两个障碍本质上是"带有多重配对约束的周期查找"，而 Abel HSP 恰好擅长同时处理耦合的周期约束。他把整个 set discrete logarithm 编码为**若干个 Abel HSP 实例**：隐藏子群的结构同时记录"哪个 $x$ 对应哪个 $y$ 的幂"与"$k$ 在各模数下的剩余"，一次 HSP 求出隐藏子群即同时消除配对歧义与模阶歧义，而不必枚举。每个 HSP 实例的规模是 $\operatorname{poly}(v,\log|\mathbb F|)$，实例个数也是多项式，因此总的求解时间为 $$ \operatorname{poly}\bigl(v,\ \log|\mathbb F|\bigr), $$ 其中 $v$ 是矩阵维数（$v\le\log_2|A|$，因为每个不变因子分量至少贡献一个因子 $2$），$\log|\mathbb F|$ 是扩域的表值长度（扩域次数不超过矩阵维数，故也是 $\operatorname{poly}(\log|G|)$)。逐项看：因子 $v$ 来自矩阵维数与多重集合大小；因子 $\log|\mathbb F|$ 来自域中元素的比特长度与域运算代价；HSP 框架本身贡献关于这两个量的多项式开销。 最后，若找到合法的 $k$，回溯整条推导链：离散对数给出 $k$，矩阵共轭给出 $P$，$P$ 与 Abel 基变换（第 3 节的 Smith 坐标）合成 $A\to B$ 的显式映射，再配上 $y\mapsto z^k$（适当补上 $B$ 中的校正项），即组装出**显式群同构**。判定与构造是同一个算法的两个输出。 ## 6. 小例子：平凡作用与反演作用 取 $A=\mathbb Z_3$、$m=2$，把第 4–5 节的全部机制在最小尺度上演算一遍。 (minimal-example-boundary)= ### 6.1 平凡作用给出 $\mathbb Z_6$ 若 $y$ 对 $A$ 的作用平凡，即 $\alpha(a)=a$，作用矩阵是 $1\times1$ 矩阵 $[1]$。此时乘法公式退化为 $$ (a,y^i)(b,y^j)=(a+b,\ y^{i+j}), $$ 即直积 $\mathbb Z_3\times\mathbb Z_2$。由中国剩余定理（$\gcd(2,3)=1$）， $$ A\rtimes\mathbb Z_2\cong\mathbb Z_3\times\mathbb Z_2\cong\mathbb Z_6. $$ ### 6.2 反演作用给出 $S_3$ 若作用为反演 $$ \alpha(a)=-a\pmod 3, $$ 作用矩阵是 $[-1]=[2]$（$\mathbb F_3$ 中 $-1\equiv2$）。注意 $[2]^2=[4]=[1]$，确有 $\alpha^2=\mathrm{id}$，与 $m=2$ 自洽。此时 $$ \mathbb Z_3\rtimes_{-1}\mathbb Z_2\cong S_3: $$ 把 $A=\mathbb Z_3$ 的生成元对应到 $3$-循环 $(123)$，把 $y$ 对应到对换 $(12)$，则对换共轭 $3$-循环确实把它取逆：$(12)(123)(12)=(132)=(123)^{-1}$，这正是 $\alpha(a)=-a$。两个生成元满足 $S_3$ 的定义关系，故同构。 ### 6.3 用判据验证二者不同构 两群的 $A$（不变因子都是 $(3)$）与 $m=2$ 完全相同，唯一差别在 $1\times1$ 作用矩阵 $[1]$ 与 $[2]$。套用幂后共轭判据： - 可取的幂次：$k\in\mathbb Z_2^*=\{1\}$，只有 $k=1$； - $1\times1$ 可逆矩阵的共轭：$P[p]P^{-1}=[p]$，因为 $\mathbb F_3^*$ 可交换，**一维情形共轭不改变任何东西**； - 因此判据要求 $[1]=[2]^1=[2]$，在 $\mathbb F_3$ 中不成立。 故两群不同构。这与直接观察一致：$\mathbb Z_6$ 可交换而 $S_3$ 不可交换。注意判据里"$k$ 只允许取单位"这一点在本例中是决定性的——如果允许 $k=0$，$[2]^0=[1]$ 会错误地判为同构，但 $z^0=e$ 根本不生成商群，对应的"映射"不是双射。 这个例子还说明判据中 $\mathbb Z_m^*$ 的"幂次自由度"何时真正起作用：$m=2$ 时 $\mathbb Z_2^*$ 只有一个元素，幂自由度消失；$m\ge3$ 时才会出现"矩阵不共轭但幂后共轭"的非平凡同构（见练习 6 第 3 题）。 ## 7. 群扩张等价与一般边界 ### 7.1 比 Abel-by-cyclic 更一般的扩张 一般群扩张写作短正合列 $$ 1\to A\to G\to Q\to1, $$ 含义是 $A\trianglelefteq G$ 且 $G/A\cong Q$，但 $Q$ 不一定能嵌入 $G$ 作为子群（扩张不一定分裂）。此时结构由两部分数据决定： 1. **作用**：$Q$ 对 $A$ 的共轭作用（在 $A$ Abel 时，这使 $A$ 成为 $Q$-模）； 2. **$2$-cocycle**：取截面 $s:Q\to G$（每个陪集选一个代表），乘法亏量 $$ s(q)s(q')=f(q,q')\,s(qq') $$ 定义函数 $f:Q\times Q\to A$。群乘法结合律迫使 $f$ 满足 cocycle 方程（对 $A$ Abel、作用记为 $q\cdot a$ 的加法记号）： $$ q\cdot f(q',q'')+f(q,q'q'')=f(q,q')+f(qq',q''), $$ 即**$2$-cocycle 条件**——它正是"结合律在代表元层面的表达"。 截面本身有任意性：把 $s(q)$ 换成 $c(q)s(q)$（$c:Q\to A$ 任意），$f$ 会加上一个由 $c$ 决定的**coboundary**。因此扩张的等价类不是由单个 cocycle、而是由它的**上同调类**（$H^2(Q,A)$ 中的元素）决定。于是扩张等价测试 = "作用是否相容 + 两个 cocycle 是否属于同一上同调类"，两者都是线性代数/同调性质的约束。Zatloukal（Zoo 202）对若干参数族用 Abel HSP 加速这些线性与同调约束的求解。 ### 7.2 边界：这些结果没有解决什么 必须如实说明适用范围，三类保留条款： - **不等于一般群同构已解决**：Le Gall 算法依赖 Abel-by-cyclic 结构承诺（存在 Abel 正规子群与互素阶循环补）。对没有这种结构的群（例如幂零类更高的群、单群的直积等），标准分解与幂后共轭判据都可能失效或不再完备。 - **不等于图同构已解决**：图同构可自然地化为置换群相关的问题，但置换群一般不是 Abel-by-cyclic 群，本文算法不直接适用。 - **依赖模型承诺**：互素阶 $\gcd(|A|,m)=1$ 保证了 Schur–Zassenhaus 分裂与补群的共轭唯一性；unique encoding（每个元素唯一标签）保证了 HSP 中"函数在不同陪集取不同值"的良定义性。超出这些承诺时，standard decomposition 和幂后共轭判据都可能失效。 ## 8. 小结 本文的链条可以概括为四句话： - Abel 群同构由关系子群的 Smith 标准形完全决定：生成元的阶给出自由直积 $D$，Abel HSP 求出关系子群 $K$，Smith 标准形给出唯一不变因子序列，比较序列即判定同构，而且构造性； - Abel-by-cyclic 群还需额外记录循环补群对正规 Abel 子群的共轭作用；互素阶条件（Schur–Zassenhaus）保证半直积描述完备，标准分解消除表达任意性； - 两个作用给出同构，当且仅当适当幂次（$k\in\mathbb Z_m^*$）之后两个作用矩阵在基变换下共轭：$PM_\alpha P^{-1}=M_\beta^k$；推导的关键两步是商群同构迫使 $k$ 为单位、$B$ 可交换使补群校正项 $b$ 消去； - 幂后共轭经特征多项式化为多重集合离散对数；Le Gall 将其分解为若干 Abel HSP，同时消除配对组合与模阶歧义，在 $\operatorname{poly}(v,\log|\mathbb F|)$ 时间求 $k$。 ## 练习题 **练习 1【同构与结构不变量】**（→ [1.1 节](#iso-and-invariants)） 1. 基础：写出群同构的定义（保持运算的双射），并对正文的 $\varphi:\mathbb Z_4\to\{1,i,-1,-i\}$、$\varphi(a)=i^{\,a}$ 取 $a=2$、$b=3$ 验证 $\varphi(a*b)=\varphi(a)\varphi(b)$。 2. 基础：$\mathbb Z_6$ 与 $S_3$ 都有 $6$ 个元素，说明它们为什么不同构，并指出你用到了哪个结构不变量。 3. 进阶：设 $\varphi:G\to H$ 是保持运算的双射。证明 $\varphi(e_G)=e_H$ 与 $\varphi(x^{-1})=\varphi(x)^{-1}$，并由此说明同构保持一切由乘法表决定的性质。 > 提示：对 $\varphi(e_Ge_G)=\varphi(e_G)\varphi(e_G)$ 两边消去 $\varphi(e_G)$。 **练习 2【黑盒群模型与经典瓶颈】**（→ [1.3 节](#black-box-model-bottleneck)） 1. 基础：列出黑盒群模型给算法的输入与接口（唯一编码、群运算预言机、生成元组），并说明输入长度为什么只有 $O(\log|G|)$。 2. 进阶：乘法表输入下经典穷举判定同构约需 $|G|^{\log|G|+O(1)}$ 时间。把它改写成黑盒模型输入长度 $n=\log|G|$ 的函数，解释为什么这一时间是指数的。 > 提示：$|G|^{\log|G|}=2^{(\log|G|)^2}$。 **练习 3【关系子群与 Abel HSP 分解】**（→ [3.1 节](#relation-subgroup-hsp)） 1. 基础：设 Abel 群 $G=\langle g_1,g_2\rangle$，$|g_1|=4$、$|g_2|=6$。写出 $D$ 与 $\Phi$ 的定义，说明 $\Phi$ 为什么是满射，并验证 $(4,0),(0,6)\in K$。 2. 进阶：在 $S_3$ 中取 $g_1=(12)$、$g_2=(123)$（阶分别为 $2,3$）。计算 $\Phi\bigl((1,1)+(1,1)\bigr)$ 与 $\Phi(1,1)\,\Phi(1,1)$，说明二者不相等，并指出正文推导的哪一步对非交换群失效。 > 提示：$(12)(123)=(23)$，而 $(23)^2=e$、$(123)^2=(132)$。 **练习 4【Smith 标准形与不变因子判定】**（→ [3.3 节](#smith-invariant-factors)） 1. 基础：写出有限 Abel 群同构的判定准则。$\mathbb Z_{12}$ 与 $\mathbb Z_2\times\mathbb Z_6$ 群阶相同，分别求出它们的不变因子序列并判断是否同构。 2. 基础：在正文 3.4 节的例子中，用 $|G|=|D|/|K|=36/6$ 复核 $G\cong\mathbb Z_6$ 的结论。 3. 进阶：求 $\mathbb Z_4\times\mathbb Z_6$ 的不变因子分解。 > 提示：先按素数拆成初等因子 $\mathbb Z_4\times\mathbb Z_2\times\mathbb Z_3$，再用中国剩余定理按"每个素数取一列"的方式重新组装成整除链。 **练习 5【Abel-by-cyclic 群与作用矩阵】**（→ [4.2 节](#abel-by-cyclic-action)） 1. 基础：在 $G=A\rtimes_\alpha\langle y\rangle$ 中推导乘法公式 $(ay^i)(by^j)=a\,\alpha^i(b)\,y^{i+j}$，并说明 $\alpha=\mathrm{id}$ 时 $G$ 为什么退化为 Abel 直积。 2. 基础：解释为什么 $A$ 的每个 Sylow 子群都被 $\alpha$ 保持，从而作用矩阵可以按素数分量分块、没有交叉项。 3. 进阶：证明在 $A\rtimes_\alpha\langle y\rangle$ 中若把补群生成元 $y$ 换成 $y^k$ 且 $\gcd(k,m)=1$，则新生成元对应的作用矩阵变为 $M_\alpha^{\,k}$。 > 提示：直接计算 $y^k a y^{-k}$，并说明 $\gcd$ 条件用在哪里。 **练习 6【幂后共轭判据】**（→ [5.3 节](#power-conjugacy-criterion)） 1. 基础：完整陈述幂后共轭判据，并解释 $k$ 为什么必须取自 $\mathbb Z_m^*$ 而不是整个 $\mathbb Z_m$。 2. 进阶：第 5.2 节断言 $\mathbb Z_m$ 的自同构恰为"乘以 $k\in\mathbb Z_m^*$"。证明它，并举例说明 $k$ 非单位时映射 $z\mapsto z^k$ 为何不是同构。 3. 进阶：在 $\mathbb Z_5\rtimes\mathbb Z_4$ 中比较两个作用 $\alpha:a\mapsto2a$ 与 $\beta:a\mapsto3a$：它们给出的两个群是否同构？ > 提示：$\mathbb Z_4^*=\{1,3\}$，检查是否存在 $k\in\mathbb Z_4^*$ 使 $[3]=[2]^k$ 在 $\mathbb F_5$ 中成立；并说明为什么 $k$ 不能取 $2$。 **练习 7【多重集合离散对数】**（→ [5.4 节](#set-discrete-log)） 1. 基础：陈述多重集合离散对数问题的定义，并说明为什么 $M_\beta^{\,k}$ 的特征值恰为 $M_\beta$ 各特征值的 $k$ 次幂。 2. 基础：列出"逐个猜配对、解普通离散对数"做法的两个指数障碍，并说明 Le Gall 的 Abel HSP 编码如何同时消除它们。 3. 进阶：在 $\mathbb F_7$ 中求所有 $k$ 使多重集合 $\{2^k,3^k\}=\{4,5\}$，并指出单个方程 $2^k=4$ 的解为什么不足以确定答案（模阶歧义的具体体现）。 > 提示：$\operatorname{ord}(2)=3$、$\operatorname{ord}(3)=6$，把条件拆成两个同余方程。 **练习 8【最小例子与适用边界】**（→ [6.1 节](#minimal-example-boundary)） 1. 基础：取 $A=\mathbb Z_3$、$m=2$：写出平凡作用与反演作用在 $\mathbb F_3$ 上的作用矩阵，并用判据说明两群不同构（注意 $\mathbb Z_2^*=\{1\}$，一维矩阵共轭不改变任何东西）。 2. 基础：验证 $(12)(123)(12)=(132)=(123)^{-1}$，说明"对换共轭 $3$-循环等于取逆"正是反演作用 $\alpha(a)=-a$。 3. 进阶：解释群同构、群扩张等价和图同构三者为何不能互换结论：每个问题的输入承诺分别是什么，本文算法依赖其中哪些？ > 提示：对照第 7.2 节的三条保留条款。 ## 参考文献 - Zoo 编号 127：Kevin Cheung 与 Michele Mosca, [Decomposing Finite Abelian Groups](https://arxiv.org/abs/cs/0101004). - Zoo 编号 128：François Le Gall, [An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem](https://arxiv.org/abs/1001.0608). - Zoo 编号 202：Kevin Zatloukal, [Classical and Quantum Algorithms for Testing Equivalence of Group Extensions](https://arxiv.org/abs/1305.1327).