Dehn function

The idea of an isoperimetric function for a finitely presented group goes back to the work of Max Dehn in 1910s. Dehn proved that the word problem for the standard presentation of the fundamental group of a closed oriented surface of genus at least two is solvable by what is now called Dehn's algorithm. A direct consequence of this fact is that for this presentation the Dehn function satisfies Dehn(n) ≤ n. This result was extended in 1960s by Martin Greendlinger to finitely presented groups satisfying the C'(1/6) small cancellation condition.[2] The formal notion of an isoperimetric function and a Dehn function as it is used today appeared in late 1980s – early 1990s together with the introduction and development of the theory of word-hyperbolic groups. In his 1987 monograph "Hyperbolic groups"[3] Gromov proved that a finitely presented group is word-hyperbolic if and only if it satisfies a linear isoperimetric inequality, that is, if and only if the Dehn function of this group is equivalent to the function f(n) = n. Gromov's proof was in large part informed by analogy with filling area functions for compact Riemannian manifolds where the area of a minimal surface bounding a null-homotopic closed curve is bounded in terms of the length of that curve.

The study of isoperimetric and Dehn functions quickly developed into a separate major theme in geometric group theory, especially since the growth types of these functions are natural quasi-isometry invariants of finitely presented groups. One of the major results in the subject was obtained by Sapir, Birget and Rips who showed[4] that most "reasonable" time complexity functions of Turing machines can be realized, up to natural equivalence, as Dehn functions of finitely presented groups.

Let

${\displaystyle G=\langle X|R\rangle \qquad (*)}$

be a finite group presentation where the X is a finite alphabet and where R ⊆ F(X) is a finite set of cyclically reduced words.

• If G and H are quasi-isometric finitely presented groups and some finite presentation of G has an isoperimetric function f(n) then for any finite presentation of H there is an isoperimetric function equivalent to f(n). In particular, this fact holds for G = H, where the same group is given by two different finite presentations.
• Consequently, for a finitely presented group the growth type of its Dehn function, in the sense of the above definition, does not depend on the choice of a finite presentation for that group. More generally, if two finitely presented groups are quasi-isometric then their Dehn functions are equivalent.
• For a finitely presented group G given by a finite presentation (∗) the following conditions are equivalent:
  • G has a recursive Dehn function with respect to (∗).
  • There exists a recursive isoperimetric function f(n) for (∗).
  • The group G has solvable word problem.

In particular, this implies that solvability of the word problem is a quasi-isometry invariant for finitely presented groups.

• Knowing the area Area(w) of a relation w allows to bound, in terms of |w|, not only the number of conjugates of the defining relations in (♠) but the lengths of the conjugating elements u_i as well. As a consequence, it is known[1][5] that if a finitely presented group G given by a finite presentation (∗) has computable Dehn function Dehn(n), then the word problem for G is solvable with non-deterministic time complexity Dehn(n) and deterministic time complexity Exp(Dehn(n)). However, in general there is no reasonable bound on the Dehn function of a finitely presented group in terms of the deterministic time complexity of the word problem and the gap between the two functions can be quite large.

• For any finite presentation of a finite group G we have Dehn(n) ≈ n.[6]
• For the closed oriented surface of genus 2, the standard presentation of its fundamental group

${\displaystyle G=\langle a_{1},a_{2},b_{1},b_{2}|[a_{1},b_{1}][a_{2},b_{2}]=1\rangle }$

satisfies Dehn(n) ≤ n and Dehn(n) ≈ n.

• For every integer k ≥ 2 the free abelian group ${\displaystyle \mathbb {Z} ^{k}}$ has Dehn(n) ≈ n².[6]
• The Baumslag-Solitar group

${\displaystyle B(1,2)=\langle a,b|b^{-1}ab=a^{2}\rangle }$

has Dehn(n) ≈ 2ⁿ (see [7]).

• The 3-dimensional discrete Heisenberg group

${\displaystyle H_{3}=\langle a,b,t|[a,t]=[b,t]=1,[a,b]=t^{2}\rangle }$

satisfies a cubic but no quadratic isoperimetric inequality.[8]

• Higher-dimensional Heisenberg groups

${\displaystyle H_{2k+1}=\langle a_{1},b_{1},\dots ,a_{k},b_{k},t|[a_{i},b_{i}]=t,[a_{i},t]=[b_{i},t]=1,i=1,\dots ,k,[a_{i},b_{j}]=1,i\neq j\rangle }$,

where k ≥ 2, satisfy quadratic isoperimetric inequalities.[9]

• If G is a "Novikov-Boone group", that is, a finitely presented group with unsolvable word problem, then the Dehn function of G growths faster than any recursive function.
• For the Thompson group F the Dehn function is quadratic, that is, equivalent to n² (see [10]).
• The so-called Baumslag-Gersten group

${\displaystyle G=\langle a,t|(t^{-1}a^{-1}t)a(t^{-1}at)=a^{2}\rangle }$

has a Dehn function growing faster than any fixed iterated tower of exponentials. Specifically, for this group

Dehn(n) ≈ exp(exp(exp(...(exp(1))...)))

where the number of exponentials is equal to the integral part of log₂(n) (see [1][11]).

• A finitely presented group is word-hyperbolic group if and only if its Dehn function is equivalent to n, that is, if and only if every finite presentation of this group satisfies a linear isoperimetric inequality.[3]
• Isoperimetric gap: If a finitely presented group satisfies a subquadratic isoperimetric inequality then it is word-hyperbolic.[3][12][13] Thus there are no finitely presented groups with Dehn functions equivalent to n^d with d ∈ (1,2).
• Automatic groups and, more generally, combable groups satisfy quadratic isoperimetric inequalities.[8]
• A finitely generated nilpotent group has a Dehn function equivalent to n^d where d ≥ 1 and all positive integers d are realized in this way. Moreover, every finitely generated nilpotent group G admits a polynomial isoperimetric inequality of degree c + 1, where c is the nilpotency class of G.[14]
• The set of real numbers d ≥ 1, such that there exists a finitely presented group with Dehn function equivalent to n^d, is dense in the interval ${\displaystyle [2,\infty )}$.[15]
• If all asymptotic cones of a finitely presented group are simply connected, then the group satisfies a polynomial isoperimetric inequality.[16]
• If a finitely presented group satisfies a quadratic isoperimetric inequality, then all asymptotic cones of this group are simply connected.[17]
• If (M,g) is a closed Riemannian manifold and G = π₁(M) then the Dehn function of G is equivalent to the filling area function of the manifold.[18]
• If G is a group acting properly discontinuously and cocompactly by isometries on a CAT(0) space, then G satisfies a quadratic isoperimetric inequality.[19] In particular, this applies to the case where G is the fundamental group of a closed Riemannian manifold of non-positive sectional curvature (not necessarily constant).
• The Dehn function of SL(m, Z) is at most exponential for any m ≥ 3.[20] For SL(3,Z) this bound is sharp and it is known in that case that the Dehn function does not admit a subexponential upper bound.[8] The Dehn functions for SL(m,Z), where m > 4 are quadratic.[21] The Dehn function of SL(4,Z), has been conjectured to be quadratic, by Thurston. This and, more generally, Gromov's conjecture that lattices in higher rank Lie groups have a quadratic Dehn function has been proved by Leuzinger and Young.[22]
• Mapping class groups of surfaces of finite type are automatic and satisfy quadratic isoperimetric inequalities.[23]
• The Dehn functions for the groups Aut(F_k) and Out(F_k) are exponential for every k ≥ 3. Exponential isoperimetric inequalities for Aut(F_k) and Out(F_k) when k ≥ 3 were found by Hatcher and Vogtmann.[24] These bounds are sharp, and the groups Aut(F_k) and Out(F_k) do not satisfy subexponential isoperimetric inequalities, as shown for k = 3 by Bridson and Vogtmann,[25] and for k ≥ 4 by Handel and Mosher. [26]
• For every automorphism φ of a finitely generated free group F_k the mapping torus group ${\displaystyle F_{k}\rtimes _{\phi }\mathbb {Z} }$ of φ satisfies a quadratic isoperimetric inequality.[27]
• Most "reasonable" computable functions that are ≥n⁴, can be realized, up to equivalence, as Dehn functions of finitely presented groups. In particular, if f(n) ≥ n⁴ is a superadditive function whose binary representation is computable in time ${\displaystyle O\left({\sqrt[{4}]{f(n)}}\right)}$ by a Turing machine then f(n) is equivalent to the Dehn function of a finitely presented group.
• Although one cannot reasonably bound the Dehn function of a group in terms of the complexity of its word problem, Birget, Olʹshanskii, Rips and Sapir obtained the following result,[28] providing a far-reaching generalization of Higman's embedding theorem: The word problem of a finitely generated group is decidable in nondeterministic polynomial time if and only if this group can be embedded into a finitely presented group with a polynomial isoperimetric function. Moreover, every group with the word problem solvable in time T(n) can be embedded into a group with isoperimetric function equivalent to n²T(n²)⁴.

• There are several companion notions closely related to the notion of an isoperimetric function. Thus an isodiametric function[29] bounds the smallest diameter (with respect to the simplicial metric where every edge has length one) of a van Kampen diagram for a particular relation w in terms of the length of w. A filling length function the smallest filling length of a van Kampen diagram for a particular relation w in terms of the length of w. Here the filling length of a diagram is the minimum, over all combinatorial null-homotopies of the diagram, of the maximal length of intermediate loops bounding intermediate diagrams along such null-homotopies.[30] The filling length function is closely related to the non-deterministic space complexity of the word problem for finitely presented groups. There are several general inequalities connecting the Dehn function, the optimal isodiametric function and the optimal filling length function, but the precise relationship between them is not yet understood.
• There are also higher-dimensional generalizations of isoperimetric and Dehn functions.[31] For k ≥ 1 the k-dimensional isoperimetric function of a group bounds the minimal combinatorial volume of (k + 1)-dimensional ball-fillings of k-spheres mapped into a k-connected space on which the group acts properly and cocompactly; the bound is given as a function of the combinatorial volume of the k-sphere. The standard notion of an isoperimetric function corresponds to the case k = 1. Compared to the classical case only little is known about these higher dimensional filling functions. One chief result is that lattices in higher rank semisimple Lie groups are undistorted in dimensions below the rank, i.e. they satisfy the same filling functions as their associated symmetric space.[32]

• In his monograph Asymptotic invariants of infinite groups[33] Gromov proposed a probabilistic or averaged version of Dehn function and suggested that for many groups averaged Dehn functions should have strictly slower asymptotics than the standard Dehn functions. More precise treatments of the notion of an averaged Dehn function or mean Dehn function were given later by other researchers who also proved that indeed averaged Dehn functions are subasymptotic to standard Dehn functions in a number of cases (such as nilpotent and abelian groups).[34][35][36]

• A relative version of the notion of an isoperimetric function plays a central role in Osin' approach to relatively hyperbolic groups.[37]
• Grigorchuk and Ivanov explored several natural generalizations of Dehn function for group presentations on finitely many generators but with infinitely many defining relations.[38]

• van Kampen diagram
• Word-hyperbolic group
• Automatic group
• Small cancellation theory
• Geometric group theory

• Noel Brady, Tim Riley and Hamish Short. The Geometry of the Word Problem for Finitely Generated Groups. Advanced Courses in Mathematics CRM Barcelona, Birkhäuser, Basel, 2007. ISBN 3-7643-7949-9.
• Martin R. Bridson. The geometry of the word problem. Invitations to geometry and topology, pp. 29–91, Oxford Graduate Texts in Mathematics, 7, Oxford University Press, Oxford, 2002. ISBN 0-19-850772-0.

• The Isoperimetric Inequality for SL(n,Z). A September 2008 Workshop at the American Institute of Mathematics.
• PDF of Bridson's article The geometry of the word problem.