群同构测试：从 Abel 群标准形到循环扩张的作用矩阵

两个群可能使用完全不同的元素标签与生成元，却有相同乘法结构。群同构问题要求判断是否存在双射 \(\varphi:G\to H\) 满足 \(\varphi(xy)=\varphi(x)\varphi(y)\)。对一般黑盒群尚无统一的多对数时间量子算法；但 Abel 群可以由不变因子完全分类，一类“Abel 正规子群被循环群扩张”的非交换群也可把同构测试化为作用矩阵的幂共轭问题。

1. 为什么群阶远远不够

同构必保持群阶、元素阶分布、中心和交换性，但这些不变量通常不完备。例如

\[ \mathbb Z_6 \quad\text{与}\quad S_3 \]

都有 6 个元素，却一个 Abelian、一个非 Abelian。算法需要产生规范结构或直接构造同构，而不是只比较若干容易计算的统计量。

黑盒模型给每个元素任意唯一标签，只提供群乘法和生成元。若经典算法必须枚举 \(|G|\) 个元素，它对输入长度 \(\log|G|\) 就是指数时间。

2. Abel 群的规范直积分解

设生成元为 \(g_1,\ldots,g_k\)。先用阶查找得到 \(r_i=|g_i|\)，定义

\[ \Phi: D=\mathbb Z_{r_1}\times\cdots\times\mathbb Z_{r_k} \to G, \qquad a\mapsto\prod_i g_i^{a_i}. \]

函数 \(a\mapsto\Phi(a)\) 隐藏关系子群 \(K=\ker\Phi\)。Abelian HSP 求 \(K\) 后，群就是商

\[ G\cong D/K. \]

把 \(K\) 的生成元写成整数关系矩阵并求 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. \]

两个有限 Abel 群同构当且仅当序列 \((d_1,\ldots,d_t)\) 相同。Smith 变换还给出新基与旧生成元之间的坐标，因此不只判定 yes/no，也能构造同构映射。

3. 循环扩张类 \(\mathscr S\)

Le Gall 考虑满足

\[ G=\langle A,y\rangle, \]

的一类群，其中

\[ A\trianglelefteq G,\qquad A\ \text{Abelian},\qquad |y|=m,\qquad\gcd(|A|,m)=1. \]

这可写成半直积 \(A\rtimes\mathbb Z_m\)。共轭定义循环因子对 \(A\) 的作用

\[ \alpha(a)=yay^{-1}. \]

选择 \(A\) 的 Abel 基后，\(\alpha\) 在每个 Sylow 分量上表示为有限域上的可逆矩阵 \(M\)。因此群结构由三类数据控制：

  1. Abel 群 \(A\) 的不变因子；

  2. 循环补群的阶 \(m\)；

  3. 作用自同构 \(\alpha\) 在合适基下的共轭类。

同一个群可能有多种 \(A,y\) 表达，所以算法先计算具有最小规范循环阶的 standard decomposition。量子阶查找、Abel 群分解和 constructive membership 让这一步关于 \(\log|G|\) 为多项式。

4. 同构条件为何是“幂后共轭”

设

\[ G=A\rtimes_{\alpha}\langle y\rangle,\qquad H=B\rtimes_{\beta}\langle z\rangle \]

已有匹配的 standard decomposition，且 \(A\cong B\)、\(|y|=|z|=m\)。一个同构可把 \(y\) 送到某个 \(z^k\) 乘以 \(B\) 中元素，其中

\[ k\in\mathbb Z_m^*. \]

它还在 \(A,B\) 间诱导基变换 \(P\)。保持共轭作用要求

\[ P M_\alpha P^{-1}=M_\beta^k \]

（在各有限域分量上分别成立）。所以问题化为：是否存在 \(k\)，使一个矩阵与另一个矩阵的第 \(k\) 次幂相似？

矩阵相似当且仅当 rational canonical form 或 invariant factors 相同。把特征多项式在扩域中分解后，条件进一步化成多重集合离散对数：给定

\[ X=\{x_1,\ldots,x_v\},\qquad Y=\{y_1,\ldots,y_v\}, \]

寻找 \(k\) 使

\[ \{y_1^k,\ldots,y_v^k\}=X. \]

逐个猜配对会产生指数排列与模阶歧义。Le Gall 将 set discrete logarithm 分解为若干 Abelian HSP，同时处理所有配对约束，在 \(\operatorname{poly}(v,\log|\mathbb F|)\) 时间求 \(k\)。若存在，再从矩阵共轭变换和 Abel 基变换组装显式群同构。

5. 小例子：平凡作用与反演作用

取 \(A=\mathbb Z_3\)、\(m=2\)。若 \(y\) 对 \(A\) 的作用平凡，

\[ A\rtimes\mathbb Z_2\cong\mathbb Z_6. \]

若作用为反演

\[ \alpha(a)=-a\pmod3, \]

则得到

\[ \mathbb Z_3\rtimes_{-1}\mathbb Z_2\cong S_3. \]

两群的 \(A\) 与 \(m\) 完全相同，差别只在 \(1\times1\) 作用矩阵 \([1]\) 和 \([-1]=[2]\)。在 \(\mathbb F_3\) 中二者不可能通过基变换共轭，故不同构。

6. 群扩张等价与一般边界

一般扩张

\[ 1\to A\to G\to Q\to1 \]

还由 \(Q\) 对 \(A\) 的作用和一个满足 cocycle 方程的 \(2\)-cocycle 决定。改变截面会把 cocycle 加上 coboundary；扩张等价测试因此是“作用是否相容 + 两 cocycle 是否同一上同调类”。Zatloukal 对若干参数族用 Abelian HSP 加速这些线性与同调约束。

这些结果不等于一般群同构已解决，也不等于图同构已解决。Le Gall 算法依赖 Abel-by-cyclic、互素阶和 unique encoding；超出这些承诺时，standard decomposition 和幂共轭判据都可能失效。

7. 小结与习题

  • Abel 群同构由关系子群的 Smith 标准形完全决定。

  • Abel-by-cyclic 群还需记录循环补群对正规 Abel 子群的共轭作用。

  • 两个作用给出同构，当且仅当适当幂后在基变换下共轭。

  • set discrete logarithm 用多个 Abelian HSP 同时消除配对与模阶歧义。

  1. 求 \(\mathbb Z_4\times\mathbb Z_6\) 的不变因子分解。

  2. 证明若 \(y\) 换成 \(y^k\) 且 \(\gcd(k,m)=1\)，作用矩阵变为 \(M_\alpha^k\)。

  3. 比较 \(\mathbb Z_5\rtimes\mathbb Z_4\) 中作用 \(a\mapsto2a\) 与 \(a\mapsto3a\) 是否可能由补群生成元变换联系。

  4. 解释群同构、群扩张等价和图同构三者为何不能互换结论。

参考文献