Dehn Functions of Groups

Our first goal is to give an almost complete description of Dehn functions of finitely presented groups in terms of time functions of Turing machines. First of all Birget and Sapir [38] proved that every Dehn function is the time function of a nondeterministic Turing machine.

Theorem 3 (Birget, Sapir, [38])   Every Dehn function of a finitely presented group G is equivalent to the time function of some (not necessarily deterministic) Turing machine solving the word problem in G.  

This result restricts the class of functions which can be Dehn functions of groups. Indeed, time functions of non-deterministic machines are functions f(n) which can be computed deterministically in time at most 2^f(n). It is easy to construct a recursive number $\alpha>2$ such that the function $[n^\alpha]$ is not computable even in double exponential time by a Turing machine, so $n^\alpha$ is not equivalent to the Dehn function of any finitely presented group. This answers a question by Gersten (he asked if every increasing recursive function >n² is equivalent to the Dehn function of a finitely presented group).

The set of Dehn functions ``must" satisfy a yet another restriction: every Dehn function ``must" be superadditive (more precisely, it ``must" be equivalent to a superadditive function), that is $f(m+n)\ge f(m)+f(n)$ for every m,n. We put the word ``must" in quotation marks because the proof of this restriction is yet to exist. Here is a quasi-proof. Notice that it is enough to show that $f(m+n+c)\ge f(m)+f(n)$ for some constant c and all m,n (since we identify equivalent functions). Now, if the word w of length $\le m$ has area f(m) and the word w' of length $\le n$ has area f(n) and there are no cancellations in the product w^gw' where g is a word of small length ($\le c/2$), then this product ``cannot" have area smaller than f(m)+f(m). Since the length of w^gw' is $\le m+n+c$, we have $f(m+n+c)\ge f(m)+f(n)$. Figure 2 shows a diagram with boundary label w^gw'.

Fig. 2.

Of course the problem is that we can probably tessellate the disk with the boundary label w^gw' in a different, more economical, way. Still there are so many ways to choose g, and to connect two van Kampen diagrams that it seems unlikely that we cannot find a product w^gw' with area f(m)+f(n).

Although, as we have said the proof of superadditivity conjecture does not exist at that time, Guba and Sapir were able to prove the following partial result.

Theorem 4 (Guba, Sapir, [21])   The Dehn function of every group which is a free product of two non-trivial groups, is superadditive.  

The proof of this theorem basically shows that the idea presented above works in the case of free products.

In view of Theorem 4, the superadditivity conjecture is equivalent to the following property:

The Dehn function of any finitely presented group G is equivalent to the Dehn function of the free product $G * {\bf Z}$.

The next theorem gives a description of Dehn functions. It shows that the class of functions f(n) > n⁴ satisfying the restrictions mentioned above virtually coincides with the class of Dehn functions >n⁴ of finitely presented groups.

Theorem 5 (Sapir, Birget, Rips, [38])    Let M be a not necessarily deterministic Turing machine with time function T(n) for which T(n)⁴ is superadditive. Then there exists a finitely presented group $G(M) = \langle A \rangle$ with Dehn function equivalent to T(n)⁴, and the smallest isodiametric function equivalent to T(n)³.

Moreover, G(M) simulates M, that is there exists an injective map K from the set of input words of M to $(A \cup A^{-1})^+$ such that

1.

|u|/C< |K(u)|<C|u| for some constant C>1 and for every input word u;

2.

An input word u is accepted by M if and only if K(u)=1 in G;

This theorem implies the following description of the ``isoperimetric spectrum" in $[4,\infty)$, that is the numbers $\alpha>4$ such that $n^\alpha$ is equivalent to a Dehn function of a finitely presented group.

We say that a real number $\alpha$ is computable in time $\le T(m)$for some function T(m) if there exists a deterministic Turing machine which for every number m, written in binary, computes a binary fraction approximating $\alpha$ with error not exceeding $\frac{1}{2^m}$time at most T(m).

Theorem 6 (Sapir, [38])     For every real number $\alpha\ge 4$ computable in time $\preceq 2^{2^m}$ the function $n^\alpha$ is equivalent to the Dehn function of a finitely presented group and the smallest isodiametric function of this group is $n^{3\alpha/4}$. On the other hand if $n^\alpha$ is the Dehn function of a finitely presented group then $\alpha$ is computable in time $\preceq 2^{2^{2^m}}$.

Of course all well known numbers >4 (say, rational numbers, $e+2, e\pi, 2\log_2\frac{a}{b}$ for integers a, b, a>4b), are computable in polynomial time, so for these numbers $\alpha$, $n^\alpha$ is the Dehn function of a finitely presented group. For $\alpha\le 4$, Brady and Bridson proved that the spectrum contains all numbers of the form $2\log_2 \frac{2a}{b}$ where a > b are integers, so the spectrum is dense in the set of all real numbers, but a description similar to Theorem 6 is not known for numbers $\le 4$. Even for non-integer rational numbers between 2 and 4 we do not yet know if they belong to the isoperimetric spectrum. We expect the result for $\alpha \in [2, 4)$ to be similar to Theorem 6.

Of course Theorem 5 provides examples of Dehn functions which are much more complicated than $n^\alpha$. For example, functions like $n^{2\pi}(\log n)^{\log n}\log\log n$ are clearly equivalent to fourth powers of time functions of Turing machines (hint: take the Turing machines which calculates the fourth root of such a function in the unary notation), and by Theorem 5 they are equivalent to Dehn functions of finitely presented groups.

Theorem 2 allows us to formulate the following corollary of Theorem 5 which gives examples of subgroups of the direct product of two free groups with ``arbitrary weird" distortion.

Theorem 7 (Sapir)   For every time function T(n) of a non-deterministic Turing machine with superadditive T(n)⁴ there exists a subgroup of $F_2\times F_2$ with distortion function T(n)⁴. In particular for every real number $\alpha\ge 4$ computable in time $\le 2^{2^m}$ there exists a subgroup of $F_2\times F_2$ with distortion function equivalent to $n^\alpha$.  

Recall that $F_2\times F_2$ is automatic. Notice that every cyclic subgroup of it is (obviously) quasi-isometrically embedded.