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

共轭问题的可判定谱

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

题面哪些群的共轭问题可判定?双曲群、广义双曲群的情形如何?

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

问题

群 G(有限表现)的共轭问题:判定任意两给定字是否共轭。德恩 1911 年提出三大判定问题(字、共轭、同构),共轭居中且最深:字问题可解的群共轭问题可不解(米勒构造:字问题可解、共轭问题不可解的有限表现群存在)。本问:共轭可判定性的群类谱——双曲群(可,命题 2)、广义双曲、一关系群、自动机群——与不可解的边界。

主要概念

德恩算法与双曲性

双曲群的定义性等价之一:存在 Dehn 表现——任何非平凡既约字含 «超过某关系一半» 的子段,可用该关系的补段替换(字长严格缩短)。这给出字问题的线性时间算法;共轭问题则需要 «短共轭子» 定理:共轭的两元素之间存在长度受控的共轭子。

扭转与共轭增长

双曲群中元素的共轭类有 «扭转不变量»:翻译长度 ‖g‖ = lim ‖gnx−1x‖/n 是共轭不变量, «扭转»(沿双曲元素的轴滑动)是共轭类的参数化骨架——双曲群的共轭类由 «短代表 + 扭转» 双重结构组织,这正是算法的几何基础。

主要命题与证明

命题 1(双曲群的德恩算法,完整骨架) 双曲群有 Dehn 表现,从而字问题可解。

骨架 ①双曲 ⟹ 线性等周:面积 ≤ C·周长(薄三角形拼装)。②零伦圆盘的面积由 «面片» 计数:每个面片边界 = 关系(的循环),周长 C·面积 ⟹ 面片数 ≤ C·ℓ,由鸽笼原理必有 «周长比面积小» 的面片——其边界大部分贴着外周:给出 «长超过关系一半的子段»。③取有限多个 such 面片(长 ≤ 某常数的关系有限截断)作 Dehn 表现;替换算法每步字长严格缩短,必终止于平凡字 ⟺ 原字平凡。□

命题 2(双曲群共轭问题可解,完整骨架) 双曲群的共轭问题可解(格罗莫夫;德赞的定量版)。

骨架 核心=短共轭子定理:若 g, h 共轭(g = xhx−1)且 g, h 是循环既约的,则存在共轭子 x 满足 |x| ≤ 2|g| + 2|h| + C 或 g(从而 h)与 «扭转» 结构相关。机制:x 极短化后,路径 [1, x] 与 [x, xh] 拼出 «从 g 的轨道到自身» 的四边形;双曲性(薄四边形)使其对角线受控 ⟹ x 或 «绕轴滑动» 的短补偿。算法:用德恩算法先化 g, h 为循环既约形,再穷举 |x| ≤ 2|g|+2|h|+C 的候选共轭子逐个验算——有限搜索必终止。□

命题 3(不可解谱系与广义双曲,完整陈述) ①存在有限表现群共轭问题不可解(米勒 1971;甚至字问题可解者亦有——米勒构造、柯林斯–米勒精化);②广义双曲(相对双曲)群在 «适当形式 » 下共轭问题可解:字问题可解 + 抛物结构可计算的类(法里陪集可控)逐一建立;③剩余有限群共轭问题不可解的例子亦存在(经米勒型构造与剩余有限化的联合)。

梗概 ①的机制=从图灵机到群的编码:把停机问题的实例编码为 «两元素是否共轭»,德恩–米勒–博里温路线的模块化拼装。②的关键:相对双曲群里共轭可 «沿抛物子群分解»:非抛物部分的双曲机制(命题 2)+ 抛物部分的 «法里算术»(可判定情形逐一验证);卡在 «抛物融合不可计算» 的例子给出可判定性恰好的失效点。□

进展与文献

Dehn 1911(三问题);Gromov《Hyperbolic Groups》§8(算法章节);Delzant 1996(短共轭子的定量骨架);Miller 1971(不可解谱系的开山);Collins–Miller(判定问题的度谱);Farb(相对双曲的定义与算法框架);Osin(广义双曲的代数机器)。一关系群的共轭问题(与本册问题 04 联动):字问题已解(马格努斯),共轭问题 开放——它是本问谱系上最亮的一格空位;自动机群的共轭问题(格里戈丘克群)已知可解但 «统一算法» 缺。共轭增长、扭转不变量与 «共轭可分离性 »(虚方向,见问题 38)是活跃的接口。

← 返回问题 32