TY - JOUR

T1 - On Dehn functions of infinite presentations of groups

AU - Grigorchuk, Rostislav I.

AU - Ivanov, Sergei V.

N1 - Funding Information:
Keywords and phrases: Presentation of groups, word problem, Dehn functions, van Kampen diagrams, torsion groups, Burnside groups AMS Mathematics Subject Classification: Primary 20E08, 20F05, 20F06, 20F10, 20F50, 20F65, 20F69 The first named author is partially supported by NSF grants DMS 04-56185, DMS 06-00975 and by the Swiss National Science Foundation. The second named author is supported in part by NSF grant DMS 04-00746

PY - 2009/3

Y1 - 2009/3

N2 - We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups. In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining relators due to Lysenok, is bounded from above by C 1 x 2 log 2 x, where C 1 > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 248, where n is either odd or divisible by 2 9, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x 19/12.

AB - We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups. In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining relators due to Lysenok, is bounded from above by C 1 x 2 log 2 x, where C 1 > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 248, where n is either odd or divisible by 2 9, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x 19/12.

KW - Burnside groups

KW - Dehn functions

KW - Presentation of groups

KW - Torsion groups

KW - Van Kampen diagrams

KW - Word problem

UR - http://www.scopus.com/inward/record.url?scp=63949083335&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=63949083335&partnerID=8YFLogxK

U2 - 10.1007/s00039-009-0712-0

DO - 10.1007/s00039-009-0712-0

M3 - Article

AN - SCOPUS:63949083335

SN - 1016-443X

VL - 18

SP - 1841

EP - 1874

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 6

ER -