# 群同构测试：从 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. 解释群同构、群扩张等价和图同构三者为何不能互换结论。

## 参考文献

- 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).