九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

Whitehead 算法与自同构等价

《群论中的 50 个公开问题》 · 问题 46 专题综述

题面自由群中两元素自同构等价的判定能否多项式化?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

给定 Fm 中两个字 u, v(长度 ≤ n),判定是否存在 α ∈ Aut(Fm) 使 α(u) = v。Whitehead 1936 的峰化算法给出可判定性;但复杂度上界是指数级。问题:①Whitehead 算法是否最优;②多项式算法(或至少 n, m 的双多项式)是否存在。

主要概念

Whitehead 峰化

关键观测:若 α(u) 是 «最短» 元素(在 Aut 轨道中长度最小),则任何 «峰化» 白头移动(对每个生成元 a:⟨a⟩ 或 ⟨a⁻¹⟩ 的 «乘积替换»)不会降低长度。峰化移动有限多种(≤ (2m)(2m−1) 型),故 «局部峰化 + 全局最短» 的搜索收敛。

Whitehead 图

顶点 = 轨道中的最短元素,边 = Whitehead 移动。图的连通性给出 «所有最短元素» 的遍历;图的几何(几步跳跃、对称性)决定算法效率。Myasnikov–Osin 等给出图的 «直径与分支» 分析,产生指数上界的精确化。

主要命题与证明

命题 1(Whitehead 峰化引理,完整骨架) 若 u 是 Aut-轨道最短元,则任何峰化移动都不缩短它。骨架:反设某峰化移动 φ 使 |φ(u)| < |u|;用 «Circular factorization»(沿 φ 的 «反向» 把 u 分解为 «峰化因子» 的乘积)——u 在 Fm/[F,F] 的像与 «峰化曲率» 的不等式给出矛盾。□

命题 2(可判定性,完整骨架) 算法:①对 u 跑峰化归约到最短元 u′(≤ 多项式次移动);②同对 v;③枚举 Whitehead 图中从 u′ 出发的所有最短元,查 v′ 是否在内(图的规模 ≤ (2m)|u′|,指数)。正确性由命题 1(最短元集合恰是峰化移动的轨道闭包)。□

命题 3(复杂度现状,诚实清单) ①m 固定时:算法 O(nm+…) 型(m 的多项式、n 的指数)——实际上 Whitehead 图的直径对固定 m 有多项式界(经 «峰化曲率» 分析),算法实际表现近似多项式;②m 变动时:已知下界(«某些输入需要指数步» 的构造)由 Myasnikov–Ushakov 给出;③多项式算法的候选路线:Whitehead 图的 «快速遍历»(经 Out(Fm) 的 Culler–Vogtmann Outer space 几何)、Aut 的 Nielsen 移动的 «自动结构» 化。□

进展与文献

Whitehead 1936 原始论文;Lyndon–Schupp《Combinatorial Group Theory》第 I 章的教科书处理;Myasnikov–Nikolov–Shpilrain 的复杂度分析;Myasnikov–Ushakov 的指数下界;Kapovich–Myasnikov–Schupp–Shpilrain 的 «generic case complexity»(Whitehead 在 «一般输入» 上是多项式快—— «平均情形快» 与 «最坏情形指数» 的现代分工)。开放核心:一般情形的多项式化,以及 «排除性证据» 是否指向 GI 型难度。

← 返回问题 46