Isoperimetric and isodiametric functions of groups

Abstract

This is the first of two papers devoted to connections between asymptotic functions of groups and computational complexity. In particular, we show how to construct a finitely presented group with NP-complete word problem. One of the main results of this paper states that if a real number $\alpha \ge 4$ is computable in time $\le 2^{2^{Cm}}$ for some constant $C>0$ then $n^\alpha$ is equivalent to (“big O”) to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is $n^{3\alpha/4}$. On the other hand, if $n^\alpha$ is equivalent to the Dehn function of a finitely presented group then $\alpha$ is computable in time $\le 2^{2^{2^{Cm}}}$ for some constant $C$. Being computer in time $T(n0$ means that there exists a Turing machine which, given $n$, computes a binary rational approximation of $\alpha$ with error at most $1/2^{n+1}$ in time at most $T(n)$. This implies that, say, functions $n^{\pi+1}$, $n^{e^2}$ and $n^\alpha$ for all rational numbers $\alpha \ge 4$ are equivalent to Dehn functions of some finitely presented groups and that $n^\pi$ and $n^\alpha$ for all rational numbers $\alpha \ge 3$ are equivalent to the smallest isodiametric functions of finitely presented groups.

Moreover, we describe all Dehn functions of finitely presented groups $\succ n^4$ as time functions of Turing machines modulo two conjectures:

1. Every Dehn function is equivalent to a superadditive function.

2. The square root of the time function of a Turing machine is equivalent to the time function of a Turing machine.

DOI: 10.2307/3597195

Authors

Mark V. Sapir

Jean-Camille Birget

Eliyahu Rips