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

收敛呈现的存在性判定

《半群中的 50 个公开问题》 · 问题 47 专题综述

题面给定独异点的呈现,判定它是否有有限收敛(完备项重写)呈现——可判定吗?

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

问题

独异点 M 的收敛呈现:呈现 ⟨A | R⟩ 使重写关系 →R 终止(noetherian)且局部合流(Newman 引理下即合流)——每个元素有唯一正规形。完备化问题:给定呈现,判定是否存在有限收敛呈现(不限于给定 R)?Knuth–Bendix 补全是半算法(收敛时成功、不收敛时不定);「是否存在可判定判据」「收敛呈现存在 ⇔ 什么代数性质」均开。它与格罗布纳基理论(交换多项式环的情形完备——Buchberger 算法可判定)的非交换推广直接相关。

主要概念

合流性:→* 与 →* 的菱形性质(Newman:终止 + 局部合流 ⟹ 合流)。Knuth–Bendix 补全:对临界对 ⟨ℓ₁u, uℓ₂⟩ 的正规形差异不断加规则,直到闭合。呈现与重写:⟨A | ui = vi⟩ 的重写系统取单向规则 ui → vi(定向的选择决定收敛性)。Dehornoy 阶:群/独异点的自 distributivity 结构给出的 «好序»,为某些独异点(Artin 辫独异点型,如 ⟨a, b | aba = bab⟩)保证收敛呈现。

主要命题与证明

命题 1(Newman 引理;完整证明) 终止的抽象重写关系中,局部合流 ⟹ 合流。

证明 对 x 的 «合并秩» μ(x)(x 所能开始的 y 满足一切 →* 合流的最大初段长——超限归纳基础)作良基归纳。设 x → y、x → z 两步(局部合流给公共 w:〈y →* w、z →* w)。须证 〈y, z 的任意后续合流——用对 μ 的归纳:μ(y), μ(z) < μ(x)(终止性下后继秩严格降)。任取 y → y′、z → z′;由归纳假设 〈y′ 与 y 合流、z′ 与 z 合流〉得 y′ →* w′ ←* z′ 的公共归约(路径拼接:y′ ← y →* w,对 μ(y) 归纳合并;同 z 侧),完成菱形。∎

命题 2(交换情形的完备可判定;完整证明框架) 交换独异点(有限表现)的收敛呈现存在性可判定——经格罗布纳基:交换等式理论中 Buchberger 算法总能补全(项序的终止性 + 临界对有限)。

证明框架 交换独异点的呈现可翻译为多项式半环上的理想成员问题;Buchberger 的 S-对约化在单项序下终止(理想升链条件),给出完备 Gröbner 基 ⟹ 收敛重写呈现存在且可计算。对照:非交换情形的临界对可无限增生(KB 补全不停机),且 «存在完备基» 与 «KB 可算出» 分离——这正是问题核心。□

命题 3(不可判定性的已知谱;陈述) «给定呈现 → 是否合流»(固定 R)在一般情形不可判定(半图埃归约,经典);«存在收敛呈现» 的可判定性更强约束,已知对 «群嵌入型» 独异点类可传递不可判定性(Kapur–Narendran 的部分结果),一般情形开放。

进展与文献

Knuth–Bendix《Simple word problems in universal algebras》(1970);Newman 引理(1942);Kapur–Narendran 的完备化不可判定系列;Dehornoy《Braids and Self-Distributivity》的好序方法;Squier 的同调阻碍(«收敛呈现 ⟹ 有限 K(π,1)» 型限制——呈现复杂度的同调下界)。开放核心:收敛呈现存在的可判定判据;代数刻画(Dehornoy 类性质?同调条件?);与 48 号自动性的耦合(自动 ⟹ 某种 «几何收敛»)。

← 返回问题 47