Dehn 函数

有人递给你一个你知道等于单位元的字，并要你去证明它——办法是不断插入和消去定义关系的副本，直到该字坍缩。有些这样的证明很短；有些却长得令人痛苦。Dehn 函数度量最坏情形：给定一个长度至多为 n 且等于 1 的字，你可能被迫使用多少次关系？它就是『证明平凡性』所需的、以关系计的代价。

形式上，对有限表现 ⟨ S | R ⟩，群中满足 w = 1 的字 w 在自由群中可写成若干关系子的共轭的乘积；w 的面积是这种表达式中关系子（计重数）的最少个数。Dehn 函数为 δ(n) = max{ area(w) : |w| ≤ n, w = 1 }。在标准等价（与增长函数相同）意义下，δ 不依赖于有限表现，且是拟等距不变量。

Dehn 函数恰好支配字问题的难度：它是递归的当且仅当字问题可解，其大小则度量复杂度。线性 Dehn 函数刻画双曲群（Gromov）；CAT(0) 群与自动群有二次界；幂零群有多项式 Dehn 函数；而像鲍姆斯拉格–索利塔群 BS(1, 2) 这样的群有指数 Dehn 函数，并且存在一些群，其 Dehn 函数实现了丰富的『等周谱』指数。