In the mathematical subject of
geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
, a Dehn function, named after
Max Dehn
Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Born to a Jewish family in Germany, Dehn's early life and career took place in Germany. ...
, 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
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
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
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
. 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
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
has solvable
word problem if and only if the Dehn function for a
finite presentation of this group is
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
(see Theorem 2.1 in
). The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic
isoperimetric inequality
In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In n-dimensional space \R^n the inequality lower bounds the surface area or perimeter \operatorname(S) of a set S\subset\R^n ...
for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a
minimal surface
In mathematics, a minimal surface is a surface that locally minimizes its area. This is equivalent to having zero mean curvature (see definitions below).
The term "minimal surface" is used because these surfaces originally arose as surfaces that ...
in a
Riemannian manifold
In differential geometry, a Riemannian manifold or Riemannian space , so called after the German mathematician Bernhard Riemann, is a real manifold, real, smooth manifold ''M'' equipped with a positive-definite Inner product space, inner product ...
in terms of the length of the boundary curve of that surface.
History
The idea of an isoperimetric function for a
finitely presented group
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
goes back to the work of
Max Dehn
Max Wilhelm Dehn (November 13, 1878 – June 27, 1952) was a German mathematician most famous for his work in geometry, topology and geometric group theory. Born to a Jewish family in Germany, Dehn's early life and career took place in Germany. ...
in 1910s. Dehn proved that the
word problem for the standard presentation of the
fundamental group
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...
of a closed oriented surface of genus at least two is solvable by what is now called
Dehn's algorithm In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have "small overlaps" with each other. Small cancellation ...
. 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. 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 group
In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a ''word hyperbolic group'' or ''Gromov hyperbolic group'', is a finitely generated group equipped with a word metric satisfying certain properties abstra ...
s. 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
Gromov (russian: Громов) is a Russian male surname, its feminine counterpart is Gromova (Громова).
Gromov may refer to:
* Alexander Georgiyevich Gromov (born 1947), Russian politician and KGB officer
* Alexander Gromov (born 1959), R ...
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 manifold
In differential geometry, a Riemannian manifold or Riemannian space , so called after the German mathematician Bernhard Riemann, is a real manifold, real, smooth manifold ''M'' equipped with a positive-definite Inner product space, inner product ...
s where the area of a
minimal surface
In mathematics, a minimal surface is a surface that locally minimizes its area. This is equivalent to having zero mean curvature (see definitions below).
The term "minimal surface" is used because these surfaces originally arose as surfaces that ...
bounding a
null-homotopic
In topology, a branch of mathematics, two continuous function (topology), continuous functions from one topological space to another are called homotopic (from grc, ὁμός "same, similar" and "place") if one can be "continuously deformed ...
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
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
, especially since the growth types of these functions are natural
quasi-isometry In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. T ...
invariants of finitely presented groups. One of the major results in the subject was obtained by Sapir, Birget and
Rips who showed that most "reasonable" time complexity functions of
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
s 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 ''r
i'' ∈ ''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 In geometric group theory, a presentation complex is a 2-dimensional cell complex associated to any presentation of a group, presentation of a group (mathematics), group ''G''. The complex has a single vertex, and one loop at the vertex for each ge ...
for ''G'' corresponding to (∗) is
null-homotopic
In topology, a branch of mathematics, two continuous function (topology), continuous functions from one topological space to another are called homotopic (from grc, ὁμός "same, similar" and "place") if one can be "continuously deformed ...
. This fact can be used to show that Area(''w'') is the smallest number of 2-cells in a
van Kampen diagram In the mathematical area of geometric group theory, a Van Kampen diagram (sometimes also called a Lyndon–Van Kampen diagram ) is a planar diagram used to represent the fact that a particular word in the generators of a group given by a group pr ...
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 ''a''
''n'' ≈ ''b''
''n''. Similarly, if ''f''(''n'') is a polynomial of degree ''d'' (where ''d'' ≥ 1 is a real number) with non-negative coefficients, then ''f''(''n'') ≈ ''n''
''d''. 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 group
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
s 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
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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 group
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
s.
*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
[S. 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 University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press
A university press is an academic publishing hou ...
, Cambridge, 1993. 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 University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books ...
, Oxford, 2002. .
*For the closed oriented surface of genus 2, the standard presentation of its
fundamental group
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...
:
:satisfies Dehn(''n'') ≤ ''n'' and Dehn(''n'') ≈ ''n''.
*For every integer ''k'' ≥ 2 the
free abelian group
In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subse ...
has Dehn(''n'') ≈ ''n''
2.
*The
Baumslag-Solitar group
:
:has Dehn(''n'') ≈ 2
''n'' (see ).
*The 3-dimensional discrete
Heisenberg group
In mathematics, the Heisenberg group H, named after Werner Heisenberg, is the group of 3×3 upper triangular matrices of the form
::\begin
1 & a & c\\
0 & 1 & b\\
0 & 0 & 1\\
\end
under the operation of matrix multiplication. Elements ' ...
:
:satisfies a cubic but no quadratic isoperimetric inequality.
*Higher-dimensional Heisenberg groups
:
,
:where ''k'' ≥ 2, satisfy quadratic isoperimetric inequalities.
*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''
2 (see ).
*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 log
2(''n'') (see
).
Known results
*A finitely presented group is
word-hyperbolic group
In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a ''word hyperbolic group'' or ''Gromov hyperbolic group'', is a finitely generated group equipped with a word metric satisfying certain properties abstra ...
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.
Thus there are no finitely presented groups with Dehn functions equivalent to ''n''
''d'' with ''d'' ∈ (1,2).
*
Automatic group In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata represent the Cayley graph of the group. That is, they can tell if a given word representation of a group element is in a " ...
s 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
In mathematics, specifically group theory, a nilpotent group ''G'' is a group that has an upper central series that terminates with ''G''. Equivalently, its central series is of finite length or its lower central series terminates with .
Intuiti ...
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''.
*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
.
*If all ultralimit">asymptotic cones of a finitely presented group are simply connected space">simply connected
In topology, a topological space is called simply connected (or 1-connected, or 1-simply connected) if it is path-connected and every path between two points can be continuously transformed (intuitively for embedded spaces, staying within the spac ...
, then the group satisfies a polynomial isoperimetric inequality.
*If a finitely presented group satisfies a quadratic isoperimetric inequality, then all asymptotic cones of this group are simply connected.
*If (''M'',''g'') is a closed
(''M'') then the Dehn function of ''G'' is equivalent to the filling area function of the manifold.
*If ''G'' is a group acting properly discontinuously and cocompactly by isometries on a CAT(0) space, then ''G'' satisfies a quadratic isoperimetric inequality. In particular, this applies to the case where ''G'' is the
(not necessarily constant).
*The Dehn function of SL(''m'', Z) is at most exponential for any ''m'' ≥ 3. 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.
The Dehn functions for SL(''m'',Z), where ''m'' > 4 are quadratic. The Dehn function of SL(4,Z), has been conjectured to be quadratic, by Thurston.
*
and satisfy quadratic isoperimetric inequalities.
*The Dehn functions for the groups Aut(''F''
) are exponential for every ''k'' ≥ 3. Exponential isoperimetric inequalities for Aut(''F''
) when ''k'' ≥ 3 were found by Hatcher and Vogtmann. These bounds are sharp, and the groups Aut(''F''
) do not satisfy subexponential isoperimetric inequalities, as shown for ''k'' = 3 by Bridson and Vogtmann, and for ''k'' ≥ 4 by Handel and Mosher.
*For every
of ''φ'' satisfies a quadratic isoperimetric inequality.
*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''
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,
and Sapir obtained the following result, providing a far-reaching generalization of
: 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''
.
*There are several companion notions closely related to the notion of an isoperimetric function. Thus an
bounds the smallest ''diameter'' (with respect to the simplicial metric where every edge has length one) of a
for a particular relation ''w'' in terms of the length of ''w''. A
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. The filling length function is closely related to the non-deterministic
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. 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. Unlike the case of standard Dehn functions, little is known about possible growth types of ''k''-dimensional isoperimetric functions of finitely presented groups for ''k'' ≥ 2.
*In his monograph ''Asymptotic invariants of infinite groups''
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).
*A relative version of the notion of an isoperimetric function plays a central role in Osin' approach to
and Ivanov explored several natural generalizations of Dehn function for group presentations on finitely many generators but with infinitely many defining relations.
Advanced Courses in Mathematics CRM Barcelona, Birkhäuser, Basel, 2007. .
*Martin R. Bridson
Invitations to geometry and topology, pp. 29–91, Oxford Graduate Texts in Mathematics, 7,
, Oxford, 2002. {{ISBN, 0-19-850772-0.
.