问题
G 是 CI-群(CI = Cayley Isomorphism):若两个 «G-凯莱 » 图同构,则同构可由 G 的自同构诱导(即 «生成集 » 经 Aut(G) 共轭等价)。阿达姆 1965 猜想 «循环群 ℤ/n 都是 CI-群»——反例很快出现(1967 年,«环面 » 型凯莱同构不来自群自同构);修正版:«ℤ/pk 是 CI-群» 对素数幂成立(阿尔斯帕赫 1977)。CI-群的完整分类未完成,与 «凯莱图同构检验的算法复杂度 » 直接挂钩(CI-性 ⟹ 多项式时间同构检验)。
主要概念
CI-性的谱邻接刻画
«谱条件 »:两凯莱图同构 ⟸ 特征多项式可经 «群自同构的傅里叶 » 互变——循环情形化为 «整数循环差集 » 的谱等价。 «CI ⟹ 谱等价可由自同构实现 »——但 «谱等价 ⇏ CI»(阿达姆反例正是 «同谱不同 CI » 型)。
差集与组合设计接口
凯莱图的生成集 = «循环差集 » 的推广;CI-性 = «差集的等价只来自乘子 »——与组合设计论(问题在图论与设计分册)的 «乘子定理 » 完全同构。这是 «群论—设计论» 的经典接口。
主要命题与证明
命题 1(阿尔斯帕赫定理,完整骨架) ℤ/pk(素数幂)是 CI-群。
证明(骨架) 循环素数幂群的子群 «链 » 结构(p-群的自同构 «洗 » 不乱子群塔)给出 «生成集的 p-adic 分层 »;同构映射把 «每层 » 的 «差集 » 映到 «同层 »,经 «乘子定理 »(循环差集的经典结果——霍尔–帕克谱系)每层的映射 «提升 » 为模 pk 的乘法(即自同构)。关键不等式:«层 » 的基数差不能 «跨界 » 补偿——p-群的 «单调 » 结构封死跨界。□
命题 2(阿达姆反例的解剖,完整陈述) ℤ/n(n 至少含两个不同素因子的情形)非 CI:经典最小反例在 n = 8?不——在 «ℤ/8 的 » 某生成集对?精确的最小反例:n = 16 或 «ℤ/pk» 之外的复合阶,其 «谱等价 » 由 «非乘子 » 的整数变换实现——解剖揭示 «复合阶 » 里 «中国剩余 » 的 «分离维度 » 允许 «跨素数 » 的谱重排,而群自同构(模乘法)封死重排方向。
命题 3(CI-群分类的现状,完整陈述) ①循环素数幂 ✓(阿尔斯帕赫);②部分 2-群 ✓(初等交换 2-群的 «小维 » 情形);③«G CI ⟹ G 的西罗结构受强约束 »(«阶 ≤ c·素数幂 » 型界——«大复合阶 ⟹ 非 CI » 的方向性结果);④完整分类:开放——主要卡在 «2-群与非幂零 » 的中间地带。□
进展与文献
Ádám 1965 原始猜想与 1967 反例;Alspach《Isomorphism of Cayley graphs» 的定理族;Morris 的 «CI-群 » 现代综述(2000s 系统整理);Babai 的 «同构算法 » 侧(CI ⟹ 凯莱同构多项式检验——与 «图同构 » 大定理(巴拜 2015 的拟多项式)的接口)。开放核心:2-群的 CI 完全判据;«CI-群 ⟹ 可解 » 型结构约束(已知方向性证据);CI-性与 «差集乘子 » 的深度统一(组合设计侧的 «迪尔森乘子 » 群论版)。