|
|
| Line 1: |
Line 1: |
| In the mathematical subject of [[geometric group theory]], a '''Dehn function''', named after [[Max Dehn]], is an optimal function associated to a [[finitely presented group|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 <ref name="Gersten"/>). The growth type of the Dehn function is a [[quasi-isometry| quasi-isometry invariant]] of a [[finitely presented group]]. The Dehn function of a finitely presented group is also closely connected with [[non-deterministic algorithm|non-deterministic]] algorithmic complexity of the [[Word problem for groups|word problem]] in groups. In particular, a [[finitely presented group]] has solvable [[Word problem for groups|word problem]] if and only if the Dehn function for a [[finitely presented group|finite presentation]] of this group is [[recursion#Recursion in mathematics|recursive]] (see Theorem 2.1 in <ref name="Gersten"/>). 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.
| | I’m Alberta from Villargiroud doing my final year engineering in Nursing. I did my schooling, secured 90% and hope to find someone with same interests in Auto audiophilia.<br><br>Have a look at my homepage; [http://instagramhackfollowers.wordpress.com/ free followers on instagram] |
| | |
| ==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 groups|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 [[Small cancellation theory|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 theory|small cancellation condition]].<ref>Martin Greendlinger, [http://www3.interscience.wiley.com/journal/113397463/abstract?CRETRY=1&SRETRY=0 ''Dehn's algorithm for the word problem.''] Communications in Pure and Applied Mathematics, vol. 13 (1960), pp. 67–83.</ref> 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]]s. In his 1987 monograph "Hyperbolic groups"<ref name="Gromov">M. Gromov, ''Hyperbolic Groups'' in: "Essays in Group Theory" (G. M. Gersten, ed.), MSRI Publ. 8, 1987, pp. 75–263. ISBN 0-387-96618-8.</ref> [[Mikhail Gromov (mathematician)|Gromov]] proved that a finitely presented group is [[word-hyperbolic group|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 [[isoperimetric inequality|filling area]] functions for compact [[Riemannian manifold]]s 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 [[Eliyahu Rips|Rips]] who showed<ref>M. Sapir, J.-C. Birget, E. Rips. ''Isoperimetric and isodiametric functions of groups''. [[Annals of Mathematics]] (2), vol 156 (2002), no. 2, pp. 345–466.</ref> that most "reasonable" time complexity functions of [[Turing machine]]s can be realized, up to natural equivalence, as Dehn functions of finitely presented groups.
| |
| | |
| ==Formal definition==
| |
| | |
| Let
| |
| :<math> G=\langle X|R\rangle\qquad (*)</math>
| |
| be a [[finitely presented group|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 is, ''w'' belongs to the [[Normal closure (group theory)|normal closure]] of ''R'' in ''F''(''X''), that is, there exists a representation of ''w'' as
| |
| | |
| :<math>w=u_1r_1u_1^{-1}\cdots u_m r_mu_{m}^{-1} \text{ in } F(X),</math> (♠)
| |
| | |
| where ''m'' ≥ 0 and where ''r<sub>i</sub>'' ∈ ''R''<sup>± 1</sup> 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''<sup>± 1</sup>.
| |
| | |
| 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
| |
| :<math>f: \mathbb N\to [0,\infty) </math>
| |
| 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
| |
| | |
| :<math>{\rm Dehn}(n)=\max\{{\rm Area}(w): w=1 \text{ in } G, |w|\le n, w \text{ freely reduced}.\} </math>
| |
| | |
| 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 Dehn functions are usually difficult to compute precisely, one usually studies their asymptotic growth types as ''n'' tends to infinity.
| |
| | |
| For two monotone-nondecreasing functions
| |
| :<math>f,g: \mathbb N\to [0,\infty) </math>
| |
| one says that ''f'' is ''dominated'' by ''g'' if there exists ''C'' ≥1 such that
| |
| :<math> f(n)\le Cg(Cn+C)+Cn+C</math>
| |
| 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''<sup>''n''</sup> ≈ ''b''<sup>''n''</sup>. 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''<sup>''d''</sup>. Also, 1 ≈ ''n''.
| |
| | |
| If a finite group presentation admits an isopeprimetric 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-isometry|quasi-isometric]] [[finitely presented group]]s and some finite presentation of ''G'' has an isoperimetric function ''f''(''n'') then for any finite presentation of ''H'' there is an isoperimentric 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-isometry|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 [[recursion#Recursion in mathematics|recursive]] Dehn function with respect to (∗)
| |
| **There exists a recursive isoperimetric function ''f''(''n'') for (∗).
| |
| **The group ''G'' has solvable [[Word problem for groups|word problem]].
| |
| ::In particular, this implies that solvability of the word problem is a quasi-isometry invariant for [[finitely presented group]]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''<sub>''i''</sub> as well. As a consequence, it is known<ref name="Gersten">S. M. Gersten, [http://books.google.com/books?hl=en&lr=&id=kLTKEymaDO0C&oi=fnd&pg=PA79&dq=Higher-dimensional+isoperimetric+(or+Dehn)+functions+of+groups&ots=Omqzh11OfQ&sig=yc9nY3mqsP6umdpz7MDMi6O7ojU ''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.</ref><ref>Juan M. Alonso, ''Inégalités isopérimétriques et quasi-isométries.'' Comptes Rendus de l'Académie des Sciences. Série I. Mathématique, vol. 311 (1990), no. 12, pp. 761–764.</ref> 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 algorithm|non-deterministic time complexity]] Dehn(''n'') and [[deterministic algorithm|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''.<ref name="brid">Martin R. Bridson. [http://books.google.com/books?id=VB_f6xnmvikC&pg=PA29&dq=The+geometry+of+the+word+problem.+Invitations+to+geometry+and+topology,&ei=KWcMSZrFHovCMqiWzLME&client=firefox-a ''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.</ref>
| |
| *For the closed oriented surface of genus 2, the standard presentation of its [[fundamental group]]
| |
| :<math>G=\langle a_1,a_2,b_1,b_n|[a_1,b_1][a_2,b_2]=1\rangle</math>
| |
| :satisfies Dehn(''n'') ≤ ''n'' and Dehn(''n'') ≈ ''n''.
| |
| *For every integer ''k'' ≥ 2 the [[free abelian group]] <math>\mathbb Z^k</math> has Dehn(''n'') ≈ ''n''<sup>2</sup>.<ref name="brid"/>
| |
| *The [[Baumslag-Solitar group]]
| |
| :<math>B(1,2)=\langle a,b| b^{-1}ab=a^2\rangle</math>
| |
| :has Dehn(''n'') ≈ 2<sup>''n''</sup> (see <ref>S. M. Gersten, ''Dehn functions and'' ''l''<sub>1</sub>''-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. ISBN 0-387-97685-X.</ref>).
| |
| *The 3-dimensional discrete [[Heisenberg group]]
| |
| :<math>H_3=\langle a,b, t| [a,t]=[b,t]=1, [a,b]=t^2 \rangle </math>
| |
| :satisfies a cubic but no quadratic isoperimetric inequality.<ref name="WP"/>
| |
| *Higher-dimensional Heisenberg groups
| |
| :<math>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\ne j\rangle</math>,
| |
| :where ''k'' ≥ 2, satisfy quadratic isoperimetric inequalities.<ref>D. Allcock, [http://www.springerlink.com/content/m1byvh8uee1lq2r6/ ''An isoperimetric inequality for the Heisenberg groups.''] [[Geometric and Functional Analysis]], vol. 8 (1998), no. 2, pp. 219–233.</ref>
| |
| *If ''G'' is a "Novikov-Boone group", that is, a finitely presented group with unsolvable [[Word problem for groups|word problem]], then the Dehn function of ''G'' growths faster than any [[recursion#Functional recursion|recursive function]].
| |
| *For the [[Thompson groups|Thompson group]] ''F'' the Dehn function is quadratic, that is, equivalent to ''n''<sup>2</sup> (see <ref>V. S. Guba, [http://www.springerlink.com/content/3537628l42rw2062/ ''The Dehn function of Richard Thompson's group F is quadratic''.] [[Inventiones Mathematicae]], vol. 163 (2006), no. 2, pp. 313–342.</ref>).
| |
| *The so-called Baumslag-Gersten group
| |
| ::<math>G=\langle a, t| (t^{-1}a^{-1} t) a (t^{-1} at)=a^2\rangle </math>
| |
| :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<sub>2</sub>(''n'') (see <ref name="Gersten"/><ref>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).</ref>).
| |
| | |
| ==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.<ref name="Gromov"/>
| |
| *'''Isoperimetric gap''': If a finitely presented group satisfies a subquadratic isoperimetric inequality then it is word-hyperbolic.<ref name="Gromov"/><ref>A. Yu. Olʹshanskii. [http://www.worldscinet.com/cgi-bin/details.cgi?id=jsname:ijac&type=all ''Hyperbolicity of groups with subquadratic isoperimetric inequality.''] International Journal of Algebra and Computation, vol. 1 (1991), no. 3, pp. 281–289.</ref><ref>[[Brian Bowditch|B. H. Bowditch]]. [http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.mmj/1029005156&page=record ''A short proof that a subquadratic isoperimetric inequality implies a linear one.'']
| |
| Michigan Mathematical Journal, vol. 42 (1995), no. 1, pp. 103–107.</ref> Thus there are no finitely presented groups with Dehn functions equivalent to ''n''<sup>''d''</sup> with ''d'' ∈ (1,2).
| |
| *[[Automatic group]]s and, more generally, [[combable group]]s satisfy quadratic isoperimetric inequalities.<ref name="WP">[[David Epstein|D. B. A. Epstein]], [[James W. Cannon|J. W. Cannon]], D. Holt, S. Levy, M. Paterson, [[William Thurston|W. Thurston.]] [http://books.google.com/books?id=DQ84QlTr-EgC&printsec=frontcover&dq=Word+processing+in+groups&ei=tsMLSavjOaX2MZCD7aME ''Word processing in groups.''] Jones and Bartlett Publishers, Boston, MA, 1992. ISBN 0-86720-244-0.</ref>
| |
| *A finitely generated [[nilpotent group]] has a Dehn function equivalent to ''n''<sup>''d''</sup> 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''.<ref>S. M. Gersten, D. F. Holt, T. R. Riley, [http://www.springerlink.com/content/klqyjdt4306ynuw7/ ''Isoperimetric inequalities for nilpotent groups.''] [[Geometric and Functional Analysis]], vol. 13 (2003), no. 4, pp. 795–814.</ref>
| |
| *The set of real numbers ''d'' ≥ 1, such that there exists a finitely presented group with Dehn function equivalent to ''n''<sup>''d''</sup>, is dense in the interval <math>[2,\infty)</math>.<ref>N. Brady and M. R. Bridson,
| |
| [http://www.springerlink.com/content/ua5bexw3vf02n2jp/ ''There is only one gap in the isoperimetric spectrum.'']
| |
| [[Geometric and Functional Analysis]], vol. 10 (2000), no. 5, pp. 1053–1070.</ref>
| |
| *If all [[ultralimit|asymptotic cones]] of a finitely presented group are [[simply connected space|simply connected]], then the group satisfies a polynomial isoperimetric inequality.<ref>M. Gromov, ''Asymptotic invariants of infinite groups'', in: "Geometric Group Theory", Vol. 2 (Sussex, 1991), London Mathematical Society Lecture Note Series, 182, Cambridge University Press, Cambridge, 1993, pp. 1–295.</ref>
| |
| *If a finitely presented group satisfies a quadratic isoperimetric inequality, then all asymptotic cones of this group are simply connected.<ref>P. Papasoglu. [http://intlpress.com/journals/JDG/archive/pdf/1996/44-4-789.pdf ''On the asymptotic cone of groups satisfying a quadratic isoperimetric inequality.''] [[Journal of Differential Geometry]], vol. 44 (1996), no. 4, pp. 789–806.</ref>
| |
| *If (''M'',''g'') is a closed [[Riemannian manifold]] and ''G'' = ''π''<sub>1</sub>(''M'') then the Dehn function of ''G'' is equivalent to the filling area function of the manifold.<ref>J. Burillo and J. Taback. [http://nyjm.albany.edu/j/2002/8-11.pdf ''Equivalence of geometric and combinatorial Dehn functions.''] New York Journal of Mathematics, vol. 8 (2002), pp. 169–179.</ref>
| |
| *If ''G'' is a group acting properly discontinuously and cocompactly by isometries on a [[CAT(0) space]], then ''G'' satisfies a quadratic isoperimetric inequality.<ref>M. R. Bridson and [[A. Haefliger]], [http://books.google.com/books?id=3DjaqB08AwAC&printsec=frontcover&dq=.+R.+Bridson+and+A.+Haefliger,+%22Metric+spaces+of+non-positive+curvature%22 ''Metric spaces of non-positive curvature.''] Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319. Springer-Verlag, Berlin, 1999. ISBN 3-540-64324-9; Remark 1.7, p. 444.</ref> 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.<ref>E. Leuzinger. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYY-4C2R48H-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_version=1&_urlVersion=0&_userid=10&md5=19f8c8331aea2b86850596d20368ef2b ''On polyhedral retracts and compactifications of locally symmetric spaces.''] Differential Geometry and its Applications, vol. 20 (2004), pp. 293–318.</ref> 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.<ref name="WP"/> The Dehn functions for SL(''m'','''Z'''), where ''m'' > 4 are quadratic.<ref>R. Young. ''The Dehn
| |
| function of SL(''n'';'''Z''').''</ref> The Dehn function of SL(4,'''Z'''), has been conjectured to be quadratic, by Thurston.
| |
| *[[Mapping class group]]s of surfaces of finite type are [[automatic group|automatic]] and satisfy quadratic isoperimetric inequalities.<ref>Lee Mosher, ''Mapping class groups are automatic.'' [[Annals of Mathematics]] (2), vol. 142 (1995), no. 2, pp. 303–384.</ref>
| |
| *Hatcher and Vogtmann proved that the groups Aut(''F''<sub>''k''</sub>) and Out(''F''<sub>''k''</sub>) satisfy exponential isoperimetric inequalities for every ''k'' ≥ 3.<ref>[[Allen Hatcher]] and [[Karen Vogtmann]],
| |
| [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pjm/1102365632 ''Isoperimetric inequalities for automorphism groups of free groups.''] [[Pacific Journal of Mathematics]], vol. 173 (1996), no. 2, 425–441.</ref> For ''k'' = 3 these bounds are known to be sharp by a result of Bridson and Vogtmann who proved that Aut(''F''<sub>3</sub>) and Out(''F''<sub>3</sub>) do not satisfy subexponential isoperimetric inequalities.<ref>Martin R. Bridson and Karen Vogtmann, [http://blms.oxfordjournals.org/cgi/content/abstract/27/6/544 ''On the geometry of the automorphism group of a free group.''] [[Bulletin of the London Mathematical Society]], vol. 27 (1995), no. 6, pp. 544–552.</ref>
| |
| *For every [[Group automorphism|automorphism]] ''φ'' of a finitely generated [[free group]] ''F''<sub>''k''</sub> the mapping torus group <math>F_k\rtimes_\phi \mathbb Z</math> of ''φ'' satisfies a quadratic isoperimetric inequality.<ref>Martin R. Bridson and Daniel Groves. [http://people.maths.ox.ac.uk/~bridson/papers/BG1/ ''The quadratic isoperimetric inequality for mapping tori of free-group automorphisms'']. Memoirs of the American Mathematical Society, to appear.</ref>
| |
| *Most "reasonable" computable functions that are ≥''n''<sup>4</sup>, can be realized, up to equivalence, as Dehn functions of finitely presented groups. In particular, if ''f''(''n'') ≥ ''n''<sup>4</sup> is a superadditive function whose binary representation is computable in time <math>O(\sqrt[4]{f(n)})</math> 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, [[Eliyahu Rips|Rips]] and Sapir obtained the following result,<ref>J.-C. Birget, A. Yu. Ol'shanskii, E. Rips, M. Sapir. ''Isoperimetric functions of groups and computational complexity of the word problem.'' [[Annals of Mathematics]] (2), vol 156 (2002), no. 2, pp. 467–518.</ref> 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''<sup>2</sup>T(''n''<sup>2</sup>)<sup>4</sup>.
| |
| | |
| ==Generalizations==
| |
| | |
| *There are several companion notions closely related to the notion of an isoperimetric function. Thus an [[isodiametric function]]<ref>S. M. Gersten, ''The double exponential theorem for isodiametric and isoperimetric functions''. International Journal of Algebra and Computation, vol. 1 (1991), no. 3, pp. 321–327.</ref> 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 mimimum, over all combinatorial null-homotopies of the diagram, of the maximal length of intermediate loops bounding intermediate diagrams along such null-homotopies.<ref>S. M. Gersten and T. Riley, [http://www.springerlink.com/content/n57038t5566430lt/ ''Filling length in finitely presentable groups''.] Dedicated to John Stallings on the occasion of his 65th birthday. [[Geometriae Dedicata]], vol. 92 (2002), pp. 41–58.</ref> 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.<ref>J. M. Alonso, X. Wang and S. J. Pride, [http://www.reference-global.com/doi/abs/10.1515/jgth.1999.008 ''Higher-dimensional isoperimetric (or Dehn) functions of groups''.] [[Journal of Group Theory]], vol. 2 (1999), no. 1, pp. 81–112.</ref> 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''<ref>M. Gromov, ''Asymptotic invariants of infinite groups'', in: "Geometric Group Theory", Vol. 2 (Sussex, 1991), London Mathematical Society Lecture Note Series, 182, [[Cambridge University Press]], Cambridge, 1993, pp. 1–295.</ref> [[Mikhail Gromov (mathematician)|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).<ref>O. Bogopolskii and E. Ventura. [http://www.reference-global.com/doi/abs/10.1515/JGT.2008.035 ''The mean Dehn functions of abelian groups''.]
| |
| [[Journal of Group Theory]], vol. 11 (2008), no. 4, pp. 569–586.</ref><ref>Robert Young. [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1J-4PT0Y41-1&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=dd941b487e4fbb13204cf66da8174aaa ''Averaged Dehn functions for nilpotent groups.''] [[Topology (journal)|Topology]], vol. 47 (2008), no. 5, pp. 351–367.</ref><ref>E. G. Kukina and V. A. Roman'kov. [http://www.springerlink.com/content/kt2668207lr01l26/ ''Subquadratic Growth of the Averaged Dehn Function for Free Abelian Groups.''] Siberian Mathematical Journal, vol. 44 (2003), no. 4, 1573–9260.</ref>
| |
| | |
| *A relative version of the notion of an isoperimetric function plays a central role in Osin' approach to [[relatively hyperbolic group]]s.<ref>Densi Osin. [http://books.google.com/books?hl=en&lr=&id=ZTqOG4KLNK4C&oi=fnd&pg=PA1&dq=osin+relatively+hyperbolic&ots=BP_lywhmY-&sig=Dx5gPWiqQoo4oKuhJ9ZSGuPGIfo ''Relatively Hyperbolic Groups: Intrinsic Geometry, Algebraic Properties, and Algorithmic Problems.''] Memoirs of the American Mathematical Society, vol. 179 (2006), no. 843. [[American Mathematical Society]]. ISBN 978-0-8218-3821-1.</ref>
| |
| | |
| *[[Rostislav Grigorchuk|Grigorchuk]] and Ivanov explored several natural generalizations of Dehn function for group presentations on finitely many generators but with infinitely many defining relations.<ref>[[Rostislav Grigorchuk|R. I. Grigorchuk]] and S. V. Ivanov, [http://www.springerlink.com/content/t093p170j66365u6/ On Dehn Functions of Infinite Presentations of Groups,] [[Geometric and Functional Analysis]], vol. 18 (2009), no. 6, pp. 1841–1874</ref>
| |
| | |
| ==See also==
| |
| *[[van Kampen diagram]]
| |
| *[[Word-hyperbolic group]]
| |
| *[[Automatic group]]
| |
| *[[Small cancellation theory]]
| |
| *[[Geometric group theory]]
| |
| | |
| ==Notes==
| |
| {{reflist|2}}
| |
| | |
| ==Further reading==
| |
| *Noel Brady, Tim Riley and Hamish Short. [http://www.springerlink.com/content/p8j80k/?sortorder=asc&v=expanded ''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. [http://books.google.com/books?id=VB_f6xnmvikC&pg=PA29&dq=The+geometry+of+the+word+problem.+Invitations+to+geometry+and+topology,&ei=KWcMSZrFHovCMqiWzLME&client=firefox-a ''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.
| |
| | |
| ==External links==
| |
| *[http://www.maths.bris.ac.uk/~matrr/SL(n,Z).html#14 ''The Isoperimetric Inequality for SL(n,Z).''] A September 2008 Workshop at the [[American Institute of Mathematics]].
| |
| *[http://www.maths.bris.ac.uk/~matrr/Art/diagrams.pdf A collection of diagrams by Tim Riley]
| |
| | |
| [[Category:Geometric group theory]]
| |
| [[Category:Geometric topology]]
| |
| [[Category:Combinatorics on words]]
| |