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 函數實現了豐富的『等周譜』指數。