In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group (that is a freely reduced word in the generators representing the identity element of the group) in terms of the length of that relation (see pp. 79–80 in ). The growth type of the Dehn function is a quasi-isometry invariant of a finitely presented group. The Dehn function of a finitely presented group is also closely connected with non-deterministic algorithmic complexity of the word problem in groups. In particular, a finitely presented group has solvable word problem if and only if the Dehn function for a finite presentation of this group is recursive (see Theorem 2.1 in ). The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic isoperimetric inequality for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a minimal surface in a Riemannian manifold in terms of the length of the boundary curve of that surface.
History
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.Martin Greendlinger, Communications on Pure and Applied Mathematics, vol. 13 (1960), pp. 67–83. 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"M. Gromov, Hyperbolic Groups in: "Essays in Group Theory" (G. M. Gersten, ed.), MSRI Publ. 8, 1987, pp. 75–263. . 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 showedM. Sapir, J.-C. Birget, E. Rips. Isoperimetric and isodiametric functions of groups. Annals of Mathematics (2), vol 156 (2002), no. 2, pp. 345–466. that most "reasonable" time complexity functions of Turing machines can be realized, up to natural equivalence, as Dehn functions of finitely presented groups.
Formal definition
Let
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.
Area of a relation
Let w ∈ F(X) be a relation in G, that is, a freely reduced word such that w = 1 in G. Note that this is equivalent to saying that w belongs to the normal closure of R in F(X), that is, there exists a representation of w as
(♠)
where m ≥ 0 and where ri ∈ R± 1 for i = 1, ..., m.
For w ∈ F(X) satisfying w = 1 in G, the area of w with respect to (∗), denoted Area(w), is the smallest m ≥ 0 such that there exists a representation (♠) for w as the product in F(X) of m conjugates of elements of R± 1.
A freely reduced word w ∈ F(X) satisfies w = 1 in G if and only if the loop labeled by w in the presentation complex for G corresponding to (∗) is null-homotopic. This fact can be used to show that Area(w) is the smallest number of 2-cells in a van Kampen diagram over (∗) with boundary cycle labelled by w.
Isoperimetric function
An isoperimetric function for a finite presentation (∗) is a monotone non-decreasing function
such that whenever w ∈ F(X) is a freely reduced word satisfying w = 1 in G, then Area(w) ≤ f(|w|), where |w| is the length of the word w.
Dehn function Then the Dehn function of a finite presentation (∗) is defined as
Equivalently, Dehn(n) is the smallest isoperimetric function for (∗), that is, Dehn(n) is an isoperimetric function for (∗) and for any other isoperimetric function f(n) we have Dehn(n) ≤ f(n) for every n ≥ 0.
Growth types of functions
Because the exact Dehn function usually depends on the presentation, one usually studies its asymptotic growth type as n tends to infinity, which only depends on the group.
For two monotone-nondecreasing functions
one says that f is dominated by g if there exists C ≥1 such that
for every integer n ≥ 0. Say that f ≈ g if f is dominated by g and g is dominated by f. Then ≈ is an equivalence relation and Dehn functions and isoperimetric functions are usually studied up to this equivalence relation. Thus for any a,b > 1 we have an ≈ bn. Similarly, if f(n) is a polynomial of degree d (where d ≥ 1 is a real number) with non-negative coefficients, then f(n) ≈ nd. Also, 1 ≈ n.
If a finite group presentation admits an isoperimetric function f(n) that is equivalent to a linear (respectively, quadratic, cubic, polynomial, exponential, etc.) function in n, the presentation is said to satisfy a linear (respectively, quadratic, cubic, polynomial, exponential, etc.) isoperimetric inequality.
Basic properties 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 ui as well. As a consequence, it is knownS. M. Gersten, Isoperimetric and isodiametric functions of finite presentations. Geometric group theory, Vol. 1 (Sussex, 1991), pp. 79–96, London Math. Soc. Lecture Note Ser., 181, Cambridge University Press, Cambridge, 1993.Juan M. Alonso, Inégalités isopérimétriques et quasi-isométries. Comptes Rendus de l'Académie des Sciences, Série I, vol. 311 (1990), no. 12, pp. 761–764. 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.
Examples
For any finite presentation of a finite group G we have Dehn(n) ≈ n.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. . For the closed oriented surface of genus 2, the standard presentation of its fundamental group
satisfies Dehn(n) ≤ n and Dehn(n) ≈ n. For every integer k ≥ 2 the free abelian group has Dehn(n) ≈ n2. The Baumslag-Solitar group
has Dehn(n) ≈ 2n (see S. M. Gersten, Dehn functions and l1-norms of finite presentations. Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), pp. 195–224, Math. Sci. Res. Inst. Publ., 23, Springer, New York, 1992. .). The 3-dimensional discrete Heisenberg group
satisfies a cubic but no quadratic isoperimetric inequality. Higher-dimensional Heisenberg groups , where k ≥ 2, satisfy quadratic isoperimetric inequalities.D. Allcock, An isoperimetric inequality for the Heisenberg groups. Geometric and Functional Analysis, vol. 8 (1998), no. 2, pp. 219–233. 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 n2 (see V. S. Guba, The Dehn function of Richard Thompson's group F is quadratic. Inventiones Mathematicae, vol. 163 (2006), no. 2, pp. 313–342.). The so-called Baumslag-Gersten group
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 log2(n) (see A. N. Platonov, An isoparametric function of the Baumslag-Gersten group. (in Russian.) Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, no. 3, pp. 12–17; translation in: Moscow University Mathematics Bulletin, vol. 59 (2004), no. 3, pp. 12–17 (2005).).
Known results
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. Isoperimetric gap: If a finitely presented group satisfies a subquadratic isoperimetric inequality then it is word-hyperbolic.A. Yu. Olʹshanskii. Hyperbolicity of groups with subquadratic isoperimetric inequality. International Journal of Algebra and Computation, vol. 1 (1991), no. 3, pp. 281–289. B. H. Bowditch. A short proof that a subquadratic isoperimetric inequality implies a linear one. Michigan Mathematical Journal, vol. 42 (1995), no. 1, pp. 103–107. Thus there are no finitely presented groups with Dehn functions equivalent to nd with d ∈ (1,2). Automatic groups and, more generally, combable groups satisfy quadratic isoperimetric inequalities.D. B. A. Epstein, J. W. Cannon, D. Holt, S. Levy, M. Paterson, W. Thurston. Word Processing in Groups. Jones and Bartlett Publishers, Boston, MA, 1992. A finitely generated nilpotent group has a Dehn function equivalent to nd 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.S. M. Gersten, D. F. Holt, T. R. Riley, Isoperimetric inequalities for nilpotent groups. Geometric and Functional Analysis, vol. 13 (2003), no. 4, pp. 795–814. The set of real numbers d ≥ 1, such that there exists a finitely presented group with Dehn function equivalent to nd, is dense in the interval .N. Brady and M. R. Bridson, There is only one gap in the isoperimetric spectrum. Geometric and Functional Analysis, vol. 10 (2000), no. 5, pp. 1053–1070.