# Length and Area Functions on Groups and Quasi-Isometric Higman Embeddings

## 1 Results

### 1.1 Definitions

Recall that isoperimetric functions of a finitely presented group $`G=X|R`$ measure areas of van Kampen diagrams over the presentation of this group. Figure 1 shows what a van Kampen diagram may look like.

Fig. 1.

It is a directed planar labeled graph where every edge is labeled by a generator from $`X`$, and the contour of every 2-cell (face) is labeled by a relator from $`R`$. By van Kampen lemma  a word $`wXX^1`$ is equal to 1 in the group $`G`$ if and only if there exists a van Kampen diagram $`\mathrm{\Delta }`$ over the presentation of $`G`$ with boundary label $`w`$. The number of cells in $`\mathrm{\Delta }`$ is equal to the number of factors in a representation of $`w`$ as a product of conjugates of relators from $`R`$:

$$w=r_i^{u_i}.$$
(1)   
We are going to establish a more precise relation between equation (1) and the van Kampen diagram $`\mathrm{\Delta }`$ later (see Lemma 1 below).

If a van Kampen diagram has minimal number of cells, $`m`$, among all diagrams with the same boundary label $`w`$ then we say that $`w`$ has area $`m`$. A function $`f(m)`$ is called an isoperimetric function of the presentation $`X|R`$ of the group $`G`$ if every word of length at most $`m`$ which is equal to 1 in the group has area at most $`f(m)`$. On the set of functions $`𝐍𝐍`$, one can define a quasi-order saying that $`fg`$ if

$$f(m)Cg(Cm)+Cm$$

for all $`m`$ and some constant $`C`$. Any minimal (with respect to $``$) isoperimetric function is called the Dehn function of the presentation $`X|R`$. The article “the” is appropriate here because it is well known , ,  that Dehn functions of different presentations of the same group are equivalent that is they satisfy inequalities

$$f_1f_2,\text{ }f_2f_1$$

.

We can also define isodiametric functions introduced by Gersten . These functions measure the diameter of a van Kampen diagram with given perimeter<sup>1</sup><sup>1</sup>1Recall that the diameter of a graph is the maximal distance between two vertices of the graph.. More precisely, with every word $`w`$ which is equal to 1 in $`G`$, we associate its diameter, that is the smallest diameter of a van Kampen diagram with boundary label $`w`$. Then if $`d(n)`$ is an isodiametric function of $`G=X|R`$, $`d(n)`$ must exceed the diameter every word $`w=1`$ (mod $`G`$) of length $`n`$. The equivalence of isodiametric functions is defined as before. Isodiametric functions of different presentations of the same group are always equivalent .

Both isoperimetric and isodiametric functions reflect the decidability of the word problem in the group. In particular, , the word problem is decidable if and only if the Dehn function (the smallest isodiametric function) is recursive. Nevertheless, the word problem in a group with huge Dehn function may be easy. For example the word problem in the Baumslag-Solitar group $`a,b|a^b=a^2`$ can be solved in quadratic time (since this group is representable by $`2\times 2`$ integer matrices) while the Dehn function is exponential . One of our main goals is to show that still there exists a very close connection between the Dehn functions and the computational complexity of the word problem.

If $`G=X`$ and $`H=XY`$ are finitely presented, one can also define the area function of $`G`$. This function is defined on the set $`W`$ of all words in the alphabet $`X`$ which are equal to 1 in $`G`$. It takes every word from $`W`$ to the area of this word in $`H`$.

Other important concepts are the one of a distortion function and the one of a length function. Let $`G=X`$ be a finitely generated subgroup of a finitely generated group $`H=Y`$. Then the distortion function $`d_{G,H}(n):𝐍𝐍`$ takes every natural number $`n`$ to $`\mathrm{max}\{|u|_X|uG,|u|_Yn\}`$. In other words, in order to compute $`d_{G,H}(n)`$ we consider all (finitely many) elements of $`G`$ whose lengths in $`H`$ are at most $`n`$, for each of these elements we compute its length in the alphabet $`X`$, and then take the maximum of these lengths.

The corresponding length function of $`G`$ inside $`H`$ is the function $`\mathrm{}:G𝐍`$ which takes every element $`g`$ of $`G`$ to $`|g|_Y`$, the length of $`g`$ in $`H`$.

Two functions $`f_1,f_2:G𝐍`$ are called $`O`$-equivalent if $`f_1(g)cf_2(g),f_2(g)cf_1(g)`$ for some constant $`c`$ and every $`gG`$. Different choices of generating sets in $`G`$ and $`H`$ lead to $`O`$-equivalent length functions $`\mathrm{}_H:G𝐍`$ and equivalent distortion functions associated with this embedding.

If $`|g|_X=O(|g|_Y)`$ for every $`gG`$, or, equivalently, if the distortion function is at most linear we say that $`G`$ is quasi-isometrically embedded into $`H`$ or that $`G`$ has bounded distortion in $`H`$. Otherwise we say that $`G`$ is has unbounded distortion.

For example, every subgroup of the free group has (obviously) bounded distortion, but the (cyclic) center $`C=c`$ of the 3-dimensional Heisenberg group $`H^3=a,b,c[a,b]=c,ca=ac,cb=bc`$ has quadratic distortion. Indeed $`c^{n^2}=[a^n,b^n]`$ for every $`n`$, the length of $`c^{n^2}`$ in $`C`$ is $`n^2`$ and the length of this element in $`H^3`$ is $`4n`$.

Just as Dehn functions and isodiametric functions reflect the decidability of the word problem, the distortion function reflects the decidability of the membership problem for subgroups: if $`G`$ is a finitely generated subgroup of a finitely generated group $`H`$ which has solvable word problem, then the membership in $`G`$ for elements of $`H`$ is decidable if and only if the distortion function of $`G`$ in $`H`$ is recursive .

In this paper, we survey recent results about isoperimetric, isodiametric, length and area functions of groups obtained by the authors in collaboration with J.-C. Birget, V. Guba and E. Rips.

There are several important connections between Dehn functions and length functions. We present two easy statements without proofs here.

###### Theorem 1

(Bridson, ) Let $`G`$ be a finitely presented group and $`HG`$ be a finitely generated subgroup of $`G`$ with distortion function $`d(n)`$. Then the Dehn function of the HNN extension $`H=G,t|h^t=h,hH`$ is at least $`d(n)`$.

###### Theorem 2

(Olshanskii, Sapir 1998) The set of distortion functions of finitely generated subgroups of the direct product of two free groups $`F_2\times F_2`$ coincides (up to equivalence) with the set of all Dehn function of finitely presented groups.

Theorem 2 is new although a remark in  hints to a possibility of some connection between distortion of subgroups in $`F_2\times F_2`$ and Dehn functions. Here is a proof of this theorem. It uses the well known Mikhailova’s trick (see ) and a result from Baumslag and Roseblade .

It is proved in  that every finitely generated subgroup $`E`$ of $`F_2\times F_2`$ is the equalizer (in  it is called the free corner pullback) of two homomorphisms $`\varphi :E^{}G`$ and $`\psi :E^{\prime \prime }G`$ of two finitely generated subgroups $`E^{},E^{\prime \prime }`$ of $`F_2`$ onto a finitely presented group $`G`$, that is $`E=\{(u,v)E^{}\times E^{\prime \prime }|\varphi (u)=\psi (v)\}`$. Since every finitely generated subgroup of $`F_2`$ has bounded distortion, $`E^{}\times E^{\prime \prime }`$ is quasi-isometrically embedded into $`F_2\times F_2`$. So it is enough to show that the distortion function of the equalizer of two homomorphisms $`\varphi :F_mG`$ and $`\psi :F_nG`$ of two free groups onto a finitely presented group $`G`$ in $`F_m\times F_n`$ is equivalent to the Dehn function of $`G`$.

Let $`d(k)`$ be the Dehn function of $`G`$. Let $`F_m=x_1,\mathrm{},x_m`$, $`F_n=y_1,\mathrm{},y_n`$ (we assume that these generating sets are closed under taking inversese). As a generating set for $`H=F_m\times F_n`$ we take the set of all pairs $`(x_i,1)`$, $`(1,y_j)`$. Let $`E`$ be the equalizer of $`\varphi `$ and $`\psi `$ in $`H`$.

Let $`r_1,\mathrm{},r_{\mathrm{}}`$ be generators of the kernel of $`\psi `$ (as a normal subgroup of $`F_n`$). Without loss of generality we assume that the set $`\{r_1,\mathrm{},r_{\mathrm{}}\}`$ is closed under cyclic shifts and inverses.

For every $`i=1,\mathrm{},m`$ pick one word $`t_iF_n`$ such that $`\varphi (x_i)=\psi (t_i)`$. For every $`j=1,\mathrm{},n`$ pick one word $`s_j`$ such that $`\varphi (s_j)=\psi (y_j)`$. Then the equalizer $`E`$ is generated by the pairs $`(x_i,t_i),(s_j,y_j),(1,r_k)`$, $`i=1,\mathrm{},m`$, $`j=1,\mathrm{},n`$, $`k=1,\mathrm{},\mathrm{}`$. Indeed, if $`(u,v)E`$, that is $`\varphi (u)=\psi (v)`$ and $`u=x_{i_1}x_{i_2}\mathrm{}x_{i_p}`$ then

$$(u,v)=(x_{i_1},t_{i_1})\mathrm{}(x_{i_p},t_{i_p})(1,a)$$

where $`\psi (a)=1`$. Since $`a`$ belongs to the kernel of $`\psi `$, we have that $`a`$ is a product of conjugates of $`r_k`$:

$$a=\underset{i=1}{\overset{d}{}}r_{k_i}^{w_i}.$$

Therefore

$$(u,v)=(x_{i_1},t_{i_1})\mathrm{}(x_{i_p},t_{i_p})\underset{i=1}{\overset{d}{}}(1,r_{k_i})^{(w_i(\stackrel{}{s}),w_i)}.$$
(2)   
Here $`w(\stackrel{}{s})`$ denotes the word $`w`$ where each $`y_j`$ is substituted by the corresponding $`s_j`$.

We shall prove that the distortion function of $`E`$ in $`H`$ is equivalent to $`d(k)`$. In order to do that we need the following general statement.

###### Lemma 1

Let $`\mathrm{\Delta }`$ be a van Kampen diagram over a presentation $`X|R`$ where $`X=X^1`$, $`R`$ is closed under cyclic shifts and inverses. Let $`w`$ be the boundary label of $`\mathrm{\Delta }`$. Then $`w`$ is equal in the free group to a word of the form $`u_1r_1u_2r_2\mathrm{}u_dr_du_{d+1}`$ where:

1. $`r_iR`$;
2. $`u_1u_2\mathrm{}u_{d+1}=1`$ in the free group;
3. $`_{i=1}^{d+1}|u_i|4e`$ where $`e`$ is the number of edges of $`\mathrm{\Delta }`$.

Proof. If $`\mathrm{\Delta }`$ has an internal edge (i.e. an edge which belongs to the contours of two cells) then it has an internal edge $`f`$ one of whose vertices belongs to the boundary. Let us cut $`\mathrm{\Delta }`$ along $`f`$ leaving the second vertex of $`f`$ untouched. We can repeat this operation until we get a diagram $`\mathrm{\Delta }_1`$ which does not have internal edges. It is easy to see that the boundary label of $`\mathrm{\Delta }_1`$ is equal to $`w`$ in the free group. The number of edges of $`\mathrm{\Delta }_1`$ which do not belong to contours of cells (let us call them edges of type 1 is the same as the number of such edges in $`\mathrm{\Delta }`$ and the number of edges which belong to contours of cells in $`\mathrm{\Delta }_1`$ (edges of type 2) is at most twice the number of such edges of $`\mathrm{\Delta }`$ (we cut each edge from a contour of a cell at most once, after the cut we get two external edges instead of one internal edge).

Suppose that a cell $`\mathrm{\Pi }`$ in $`\mathrm{\Delta }_1`$ has more than one edge which has a common vertex with $`\mathrm{\Pi }`$ but does not belong to the contour of $`\mathrm{\Pi }`$ . Take any point $`O`$ on $`(\mathrm{\Pi })`$. Let $`p`$ be the boundary path of $`\mathrm{\Delta }_1`$ starting at $`O`$ and let $`q`$ be the boundary path of $`\mathrm{\Pi }`$ starting at $`O`$. Consider the path $`qq^1p`$. The subpath $`q^1p`$ bounds a subdiagram of $`\mathrm{\Delta }_1`$ containing all cells but $`\mathrm{\Pi }`$. Replace the path $`q`$ in $`qq^1p`$ by a loop $`q^{}`$ with the same label starting at $`O`$ and lying inside the cell $`\mathrm{\Pi }`$. Let the region inside $`q^{}`$ be a new cell $`\mathrm{\Pi }^{}`$. Then the path $`q^{}q^1p`$ bounds a diagram whose boundary label free is freely equal to $`w`$. Notice that $`\mathrm{\Pi }^{}`$ has exactly one edge having a common vertex with $`\mathrm{\Pi }^{}`$ and not belonging to the contour of $`\mathrm{\Pi }`$. Thus this operation reduces the number of cells which have more than one edge which has a common vertex the cell but does not belong to the contour of it.

After a number of such transsformations we shall have a diagram $`\mathrm{\Delta }_2`$ which has the form of a tree $`T`$ with cells hanging like leaves (each has exactly one common vertex with the tree).

The number of edges of type 1 in $`\mathrm{\Delta }_2`$ cannot be bigger than the number of all edges in $`\mathrm{\Delta }_1`$, so it cannot be more than two times bigger than the total number of edges in $`\mathrm{\Delta }`$.

The boundary label of $`\mathrm{\Delta }_2`$ is freely equal to $`w`$, and it has the form $`u_1r_{i_1}u_2r_{i_2}\mathrm{}u_dr_{i_d}u_{d+1}`$ where $`d`$ is the number of cells in $`\mathrm{\Delta }`$, $`u_1u_2\mathrm{}u_{d+1}`$ is the label of a tree, so $`u_1u_2\mathrm{}u_{d+1}=1`$ in the free group. The sum of lengths of $`u_i`$ is at most four times the number of edges in $`\mathrm{\Delta }`$ because the word $`u_1u_2\mathrm{}u_{d+1}`$ is written on the tree $`T`$, and when we travel along the tree, we pass through each edge twice.

The lemma is proved.

Let us consider the distortion function of $`E`$ in $`H`$. Without loss of generality we can assume that $`d(k)`$ is the Dehn function of the presentation $`y_1,\mathrm{},y_n|r_1,\mathrm{},r_{\mathrm{}}`$ (recall that Dehn functions of different finite presentations of the same group are equivalent).

Let $`(u,v)`$ be any element in $`E`$ whose length in $`H`$, $`|u|+|v|`$, is $`k1`$. Then as before

$$(u,v)=(x_{i_1},t_{i_1})\mathrm{}(x_{i_p},t_{i_p})(1,a)$$

where $`u=x_{i_1}\mathrm{}x_{i_p}`$, $`\psi (a)=1`$.

Notice that the length of the word $`a`$ does not exceed

$$|v|+c_1|u|c_1(|u|+|v|)=c_1k$$

where $`c_1`$ is the maximal length of $`|t_i|`$, $`i=1,\mathrm{},m`$.

Let $`\mathrm{\Delta }`$ be the minimal area van Kampen diagram over the presentation

$$y_1,\mathrm{},y_n|r_1,\mathrm{},r_{\mathrm{}}$$

of $`G`$ with the boundary label $`a`$. Then the area of $`\mathrm{\Delta }`$ does not exceed $`d(c_1k)`$. Since $`\mathrm{\Delta }`$ is a planar graph, its number of edges $`e`$ does not exceed a constant times the area plus the length of the boundary of $`\mathrm{\Delta }`$.

By Lemma 1,

$$a=u_1r_{i_1}u_2\mathrm{}r_{i_q}u_{q+1}$$

where $`u_1\mathrm{}u_{q+1}=1`$ in the free group, and $`|u_i|4e`$. Then

$$\begin{array}{c}(1,a)=(u_1(\stackrel{}{s})1u_2(\stackrel{}{s})1\mathrm{}1u_{q+1}(\stackrel{}{s}),u_1r_{i_1}u_2\mathrm{}r_{i_q}u_{q+1})\hfill \\ =u_1^{}(1,r_{i_1})u_2^{}(1,r_{i_2})\mathrm{}(1,r_{i_q})u_{q+1}^{}\hfill \end{array}$$

where $`u_i^{}`$ denotes the word $`u_i`$ with letters $`y_j`$ substituted by $`(s_j,y_j)`$. Therefore the length in $`E`$ of the element $`(1,a)`$ does not exceed $`c_2d(c_1k)+c_1k`$ for some constant $`c_2`$. Hence the length in $`E`$ of the element $`(u,v)`$ does not exceed $`k(1+c_1)+c_2d(c_1k)`$.

This implies that the distortion function of $`E`$ in $`H`$ does not exceed a function equivalent to the Dehn function $`d`$.

To prove that the Dehn function $`d`$ does not exceed a function equivalent to the distortion function of $`E`$ in $`H`$, it is enough, for every number $`p1`$, to take a word $`aF_n`$, from the kernel of $`\psi `$, $`|a|p`$, of area $`d(p)`$. Then it is easy to see that any representation of $`(1,a)`$ as a product of generators of $`E`$ must contain at least $`d(p)`$ factors of the form $`(1,r_k)`$ (because it corresponds to a representation of $`a`$ in the form $`u_1r_{i_1}u_2r_{i_2}\mathrm{}r_{i_d}u_{d+1}`$ where $`u_1\mathrm{}u_{d+1}=1`$ in the free group). $`\mathrm{}`$

### 1.2 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  proved that every Dehn function is the time function of a nondeterministic Turing machine.

###### Theorem 3

(Birget, Sapir, ) 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^2`$ 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)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)f(m)+f(n)`$ for some constant $`c`$ and all $`m,n`$ (since we identify equivalent functions). Now, if the word $`w`$ of length $`m`$ has area $`f(m)`$ and the word $`w^{}`$ of length $`n`$ has area $`f(n)`$ and there are no cancellations in the product $`w^gw^{}`$ where $`g`$ is a word of small length ($`c/2`$), then this product “cannot” have area smaller than $`f(m)+f(m)`$. Since the length of $`w^gw^{}`$ is $`m+n+c`$, we have $`f(m+n+c)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 property does not exist at that time, Guba and Sapir were able to prove the following partial result.

###### Theorem 4

(Guba, Sapir, ) 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 property 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𝐙`$.

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

###### Theorem 5

(Sapir, Birget, Rips, ) Let $`M`$ be a not necessarrily deterministic Turing machine with time function $`T(n)`$ for which $`T(n)^4`$ is superadditive. Then there exists a finitely presented group $`G(M)=A`$ with Dehn function equivalent to $`T(n)^4`$, and the smallest isodiametric function equivalent to $`T(n)^3`$.

Moreover, $`G(M)`$ simulates $`M`$, that is there exists an injective map $`K`$ from the set of input words of $`M`$ to $`(AA^1)^+`$ such that

1. $`1/C|u|<|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,\mathrm{})`$, 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 $`T(m)`$ for some function $`T(m)`$ if there exists a deterministic Turing machine which for every number $`m`$ written in binary computes the first $`m`$ digits of $`\alpha `$ in time at most $`T(m)`$.

###### Theorem 6

(Sapir, ) For every real number $`\alpha 4`$ computable in time $`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/4\alpha }`$. On the other hand if $`n^\alpha `$ is the Dehn function of a finitely presented group then $`\alpha `$ is computable in time $`2^{2^{2^m}}`$.

Of course all well known numbers $`>4`$ (say, rational numbers, $`e+2,e\pi ,2\mathrm{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 4`$, Brady and Bridson proved that the spectrum contains all numbers of the form $`2\mathrm{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 $`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 [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 }(\mathrm{log}n)^{\mathrm{log}n}\mathrm{log}\mathrm{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)^4`$ there exists a subgroup of $`F_2\times F_2`$ with distortion function $`T(n)^4`$. In particular for every real number $`\alpha 4`$ computable in time $`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 has (obviously) bounded distortion.

### 1.3 Length Functions of a Finitely Generated Group

Theorems 2 and 7 gives information about the set of distortion functions of subgroups of one particular group, $`F_2\times F_2`$. In this section, we shall fix an arbitrary finitely generated group $`G`$ and describe all possible length functions (and hence distortion functions) of $`G`$ inside other groups.

A complete description of all length functions of a finitely generated group is given by the following theorem.

###### Theorem 8

(Olshanskii, ) Let $`\mathrm{}:G𝐍`$ be a length function on a group $`G`$. Then the following conditions hold:

1. $`\mathrm{}(g)=\mathrm{}(g^1)`$ for every $`gG`$; $`\mathrm{}(g)=0`$ if and only if $`g=1`$.
2. $`\mathrm{}(gh)\mathrm{}(g)+\mathrm{}(h)`$ for every $`g,hG`$.
3. There exists a positive number $`c`$ such that the cardinality of the set $`\{gG|\mathrm{}(g)r\}`$ does not exceed $`c^r`$ for every $`r𝐍`$.

Conversely for every group $`G`$ and every function $`\mathrm{}:G𝐍`$ satisfying (D1) - (D3), there exists an embedding of $`G`$ into a 2-generated group $`H`$ with generating set $`B=\{b_1,b_2\}`$ such that the length function $`g|g|_B`$ is equivalent to $`f`$.

In the particular case when $`G`$ is a cyclic group, Theorem 8 implies that for any number $`\alpha (0,1]`$, there exists a group $`H_\alpha >G`$ and an element $`gH_\alpha `$ such that the length of $`g^i`$ in $`H_\alpha `$ grows as $`i^\alpha `$. This gives an answer to Gromov’s question .

Another problem by Gromov  asked for a description of length functions of cyclic groups in finitely presented groups. It is clear that not every function satisfying (D1)–(D3) can be a length function of the cyclic group in a finitely presented group: the cardinality of the set of $`O`$-equivalence classes of functions satisfying (D1)-(D3) is continuum, and the set of embeddings of the infinite cyclic group into finitely presented groups is countable. Nevertheless the following theorem shows that all “reasonable” functions are length functions of a given finitely generated group $`G`$ in a finitely presented group.

Let $`G`$ be a group with a finite generating set $`A=\{a_1,\mathrm{},a_m\}`$. Let $`F_m`$ be the free group generated by $`AA^1`$. Every function $`\mathrm{}:G𝐍`$ can be naturally extended to a function $`\mathrm{}^{}:F_mN`$. We say that $`\mathrm{}`$ is computable if $`\mathrm{}^{}`$ is computable in the natural sense.

###### Theorem 9

(Olshanskii, ) Let $`\mathrm{}`$ be a computable function $`G𝐍`$ satisfying (D1)-(D3). Then $`G`$ can be embedded into a finitely presented group $`H`$ in such a way that the corresponding length function is equivalent to $`\mathrm{}`$.

This theorem immediately follows from Theorem 8 and the following result.

###### Theorem 10

(Olshanskii,) Every finitely generated and recursively presented group $`G`$ can be quasi-isometrically embedded into a finitely presented group.

Although Theorem 9 shows that all “reasonable” functions are length functions of a given finitely generated recursively presented group inside finitely presented groups, it does not give a characterization of these functions. Such a characterization has been found recently by Olshanskii. This answers questions asked by P. Papasoglu and R. Gilman. It also gives a complete solution of Gromov’s problem from . It turned out that such a characterization can be easily deduced from  and .

We say that a function $`\mathrm{}:G𝐍`$ satisfies condition (D4) if there exists a natural number $`n`$ and a recursively enumerable set $`SF_m\times F_n`$ such that

(a) if $`(v_1,u),(v_2,u)S`$ for some words $`v_1,v_2,u`$ then $`v_1`$ and $`v_2`$ represent the same element in $`G`$;

(b) $`\mathrm{}^{}(v)=\mathrm{min}(\{|u||(v,u)S\})`$ for every $`vF_m`$.

Clearly it does not depend on the choice of generators of $`G`$ whether $`\mathrm{}`$ satisfies condition (D4) or not because of the obvious rewriting.

Notice that in (D4), we can always assume $`n=2`$. Indeed, if condition (D4) holds for a function $`\mathrm{}`$ and some $`n`$, it also holds for $`\mathrm{}`$ and any natural number $`n^{}2`$ since there is an isomorphic embedding of $`F_n`$ into $`F_n^{}`$.

###### Theorem 11

(Olshanskii, ) Let $`G`$ be a finitely generated subgroup of a finitely presented group $`H`$. Then the corresponding length function on $`G`$ satisfies conditions (D1)–(D4). Conversely, for every finitely generated group $`G`$ and every function $`\mathrm{}:G𝐍`$ satisfying conditions (D1)–(D4), there exists an embedding of $`G`$ into a finitely presented group $`H`$ such that the length function $`g|g|_H`$ is $`O`$-equivalent to $`\mathrm{}`$.

Condition (D4) is relatively complicated. We do not know if it is possible to simplify it in general. But in the case when the group $`G`$ has solvable word problem, including the important case when $`G`$ is cyclic, condition (D4) can be replaced by a much simpler condition.

As usual, the graph of a function $`\mathrm{}^{}:F_m𝐍`$ is the set $`(w,\mathrm{}^{}(w))F_m\times N`$. A pair $`(w,k)`$ is said to lie above the graph of $`\mathrm{}^{}`$ if $`\mathrm{}^{}(w)k`$.

###### Theorem 12

(Sapir, ) Let $`G`$ be a finitely generated group with decidable word problem. Then the function $`\mathrm{}:g|g|_H`$ given by an embedding of $`G`$ into a finitely presented group $`H`$ satisfies condtions (D1)–(D3) and the following condition

(D4’) The set of pairs above the graph of $`\mathrm{}^{}`$ is recursively enumerable.

Conversely, for every function $`\mathrm{}:G𝐍`$ satisfying conditions (D1), (D2), (D3), and (D4’), there exists an embedding of $`G`$ into a finitely presented group $`H`$ such that the corresponding length function on $`G`$ is $`O`$-equivalent to $`\mathrm{}`$.

It is again clear that whether condition (D4’) holds or not does not depend of the choice of generators of $`G`$.

In the important particular case when $`G`$ is the infinite cyclic group we have

###### Corollary 1

(1)Let $`g`$ be an element of infinite order in a finitely presented group $`H`$ with a generating set $`=\{b_1,\mathrm{},b_k\}`$. Denote $`\mathrm{}(i)=|g^i|_{}=|g^i|`$ for $`i𝐙`$. Then

* $`\mathrm{}(i)=\mathrm{}(i)`$ for $`i𝐙`$ ($`l`$ is symmetric), and $`\mathrm{}(i)=0`$ iff $`i=0`$;
* $`\mathrm{}(i+j)\mathrm{}(i)+\mathrm{}(j)`$ for $`i,j𝐙`$ ($`l`$ is subadditive);
* there is a positive number $`c`$ such that $`card\{i𝐙|\mathrm{}(i)r\}c^r`$ for any $`r𝐍`$.
* the set of integer pairs above the graph of $`\mathrm{}`$ is recursively enumerable.

(2) Conversely, for any function $`\mathrm{}:𝐙𝐍`$, satisfying the conditions (C1)–(C4), there is a finitely presented group $`H`$ and an element $`gH`$ such that $`|g^i|_H`$ is $`O`$-equivalent to $`\mathrm{}(i)`$.

It is easy to prove that (D4) implies (D4’). Indeed, suppose that (D4) holds. Consider a Turing machine $`M`$ listing elements of the recursively enumerable set $`E`$. Let us change the machine $`M`$ in such a way that (1) instead of pairs $`(w,u)`$ from $`F_m\times F_n`$ it produces pairs $`(w,|u|)`$ from $`F_m\times 𝐍`$ and (2) after every, say, 10, steps of calculation, it goes through all pairs listed so far and for each of these pairs $`(w_i,k_i)`$ adds a pair $`(w_i,k_i+1)`$ to the list, then it does the next 10 steps of calculations, etc. Clearly, this new machine will list all pairs which are above the graph of $`\mathrm{}^{}`$ and only these pairs. Thus the set of pairs above the graph of $`\mathrm{}^{}`$ is recursively enumerable and condition (D4’) holds.

By the proper choice of a universal group $`H`$ it is not difficult to sharpen the formulation of Theorems 9 and 11. One can select the group $`H`$ in these theorems (independently of $`G`$) as the receptacle of all possible “computable distortions” of finitely generated recursively presented groups. The next theorem follows from Theorem 4 from .

###### Theorem 13

(Olshanskii, 1998) There exists a finitely presented group $`H`$, having the following property. For an arbitrary finitely generated recursively presented group $`G`$ and an arbitrary function $`\mathrm{}:R𝐍`$ satisfying conditions (D1)-(D4) there exists an embedding of $`G`$ into $`H`$ such that the length function of $`G`$ corresponding to this embedding is $`O`$-equivalent to $`\mathrm{}`$.

### 1.4 Groups with Word Problem in NP

The well known Higman theorem says that a group has a recursive presentation if and only if this group is embeddable into a finitely presented group. Theorem 10 strengthens this result. The next Theorem strengthens it even further.

###### Theorem 14

(Birget, Olshanskii, Rips, Sapir ) Let $`G`$ be a finitely generated group with word problem solvable by a non-deterministic Turing machine with time function $`T(n)`$ such that $`T(n)^4`$ is superadditive. Then $`G`$ can be quasi-isometrically embedded into a finitely presented group $`H`$ with isoperimetric function equivalent to $`n^2T(n^2)^4`$. In particular, the word problem of a finitely generated group is in NP if and only if this group is a (quasi-isometric) subgroup of a finitely presented group with polynomial isoperimetric function.

In particular, this theorem gives a Higman-like description of groups with word problem in NP.

The class of finitely generated groups with word problem in NP is very large. It clearly includes all matrix groups over $`𝐐`$. It also includes

* All finitely generated matrix groups over arbitrary fields: this follows from the fact that every finitely generated field is a finite extension of a purely transcendental extension of its simple subfield, and the fact that the word problem in the ring of polynomials over $`𝐐`$ or $`𝐙/p𝐙`$ is solvable in polynomial time,
* Polycyclic and finitely generated metabelian groups because they are representable by matrices ,
* Automatic groups (in particular, hyperbolic groups) ,
* Groups of piecewise linear transformations of a line with finitely many rational singularities (including the R. Thompson group $`F`$) ,
* Every finitely generated subgroup of a diagram group ,
* Every free Burnside group $`B(m,n)`$ for sufficiently large odd exponent $`n`$ (see, for example, Storozhev’s argument in Section 28 of ).

This class is closed under free and direct products. It is easy to see using Magnus’ embedding that for every normal subgroup $`N`$ of a free finitely generated group $`F`$ if $`F/N`$ has word problem in NP (resp. P) then $`F/N^{}`$ has word problem in NP (resp. P). Therefore every free group in the variety of all solvable groups of a given class has word problem in P.

It is an interesting question whether this class also contains all one-relator groups. There are of course finitely generated groups with word problem not in NP, for example groups with undecidable word problem. Moreover the construction from  allows one to construct groups with decidable but arbitrary hard word problem. But these groups are in some sense “artificial”. So perhaps the class of groups with word problem in NP (which by Theorem 14 is the class of all subgroups of finitely presented groups with polynomial Dehn functions) can be considered as the class of “tame” groups.

An example of an embedding of one group into another where lengths are not distorted but areas are distorted can be found in Gersten . Some examples of groups with big Dehn functions embeddable into groups with small Dehn functions can be found in Madlener, Otto  and Baumslag, Bridson, Miller and Short . Our results show that any recursively presented finitely generated group can be embedded into a finitely presented group with bounded length distortion but with close to maximal possible area distortion. Indeed, Theorem 3 shows that an isoperimetric function of a group $`H`$ containing a given group $`G`$ cannot be smaller than the time complexity $`T(n)`$ of the word problem for $`G`$, and Theorem 14 shows that $`G`$ can be embedded into a finitely presented group with Dehn function at most $`n^2T(n^2)^4`$ (which is polynomially equivalent to $`T(n)`$ ).

For matrix groups our theorem implies that every such group is embedded quasi-isometrically into a finitely presented group with Dehn function at most $`n^{10+ϵ}`$ for every $`ϵ>0`$. It is interesting to know the smallest Dehn function of a finitely generated group containing, for example, the Baumslag-Solitar group $`BS_{2,1}`$.

Notice that a semigroup analog of Theorem 14 was obtained in Birget .

As it usually happens, solution of one problem leads to solutions of other problems.

In 1976, D. Collins asked  if there exists a version of the Higman embedding theorem which preserves the degree of unsolvability of the conjugacy problem. The answer is “yes” as the following theorem shows.

###### Theorem 15

(Olshanskii, Sapir, 1998) The embedding described in the proof of Theorem 14 preserves the degree of unsolvability of the conjugacy problem. In particular, the conjugacy problem is decidable in $`G`$ if and only if it is decidable in $`H`$.

Using the proof of Theorem 14, in order to embed a finitely generated group $`G`$ with word problem in NP into a finitely presented group with polynomial isoperimetric function, one needs first construct a Turing machine which solves the word problem in $`G`$, then convert it into a so called $`S`$-machine (see below), then convert the $`S`$-machine into a group. As a result the group we construct will have a relatively complicated set of relations. In some important cases like the Baumslag-Solitar group $`G_{2,1}`$, the free Burnside groups $`B(m,n)`$, where $`n`$ is odd and $`>>1`$, and others, we can modify our construction and get simple presentations of groups with polynomial isoperimetric functions where these groups embed.

Consider, for example, the free Burnside group $`B(m,n)`$ with $`m`$ generators $`\{a_1,\mathrm{},a_m\}`$ and exponent $`n`$. This group is very complicated and in particular not finitely presented if $`m2`$ and $`n`$ is odd and $`665`$ (Adian, ). Now we are going to give a presentation of a finitely presented group $`H`$ with a polynomial isoperimetric function, containing $`B(m,n)`$ as a quasi-isometric subgroup.

The relations of $`B(m,n)`$ have the form $`u^n=1`$ where $`u`$ is an arbitrary word in the alphabet of generators. So our goal is to find a finite set of relations of a bigger group which will imply all the relations $`u^n=1`$ (and no extra relations between generators of $`B(m,n)`$).

Instead of first writing relations of $`H`$, and then drawing van Kampen diagrams we shall first draw diagrams, and then write relations.

For simplicity take $`n=3`$. The construction really does not depend much on $`n`$, so we shall sometimes write $`n`$ instead of $`3`$. First of all, we shall find a finite set of relations which imply relations of the form

$$K(uq_1uq_2uq_3)=k_1(uq_1uq_2uq_3)k_2(uq_1uq_2uq_3)^{}k_3\mathrm{}.k_N(uq_1uq_2uq_3)^{(N)}$$

for every word $`u`$ in the alphabet $`\{a_1,\mathrm{},a_m\}`$. Here $`N`$ is a sufficiently large number (28 is enough), $`k_1,\mathrm{},k_N,q_1,q_2,q_3`$ are new letters, and the words between consecutive $`k^{}s`$ are copies of $`uq_1uq_2uq_3`$ written in disjoint alphabets. The group given by these relations will be denoted by $`G_{m,n}`$. Figure 3 shows the van Kampen diagram (below it will be called a disc) with boundary label $`K(uq_1uq_2uq_3)`$.

Fig. 3.

On the boundary of this diagram we have the word $`K(uq_1uq_2uq_3)`$. The words on each of the concentric circles is labeled by $`K(u_iq_1u_iq_2u_iq_3)`$ where $`u_i`$ is a prefix of $`u`$ of length $`i1`$. The word written on the innermost circle is $`K(q_1q_2q_3)`$. This word will be called the hub. The edges connecting the circles are labeled by letters $`r_1,\mathrm{},r_m`$. The cells tessellating the space between the circles have labels

* $`q_i^{r_j}=a_jq_i`$, $`i=1,2,3`$, $`j=1,\mathrm{},m`$.
* $`ar=ra`$, $`a\{a_1,\mathrm{},a_m\}`$, $`r\{r_1,\mathrm{},r_m\}`$
* $`kr=rk`$, $`k\{k_1,\mathrm{},k_N\}`$, $`r\{r_1,\mathrm{},r_m\}`$.

plus $`N`$ copies of each of these relations written in $`N`$ disjoint alphabets. These relations plus the hub relation $`K(q_1q_2q_3)`$ form the presentation of $`G_{m,n}`$.

Now we construct $`H=H_{m,n}`$. Take a copy of $`B(m,n)`$ generated by $`\{b_1,\mathrm{},b_m\}`$. The group $`H`$ will be an HNN-extension of the direct product $`B(m,n)\times G_{m,n}`$. Here is the van Kampen diagram:

Fig. 4.

This is an annular diagram. The hole of it has label $`u_b^n`$ ($`u_b`$ is the word $`u`$ rewritten in the alphabet $`\{b_1,\mathrm{},b_m\}`$). The boundary label of the disc is $`K(uq_1uq_2uq_3)`$, the label of the external boundary of the diagram is also $`K(uq_1uq_2uq_3)`$. In order to fill this diagram as shown on the picture, one needs a new (stable) letter $`\rho `$ and the following relations:

* $`\rho k=k\rho `$ for $`k\{k_1,\mathrm{},k_N\}`$.
* $`\rho q=q\rho `$ for every $`q\{q_1,q_2,q_3,\mathrm{},q_3^{(N)}\}`$.
* $`\rho a=a\rho `$ for every $`a`$ from the $`N`$ copies of $`\{a_1,\mathrm{},a_m\}`$.
* $`a^\rho =ab`$ for every $`a\{a_1,\mathrm{},a_m\}`$.
* $`ab=ba`$ for every $`a\{a_1,\mathrm{},a_m\}`$ and $`b\{b_1,\mathrm{},b_m\}`$.
* $`q_ib=bq_i`$ for every $`b\{b_1,\mathrm{},b_m\}`$, $`i=1,2,3`$.

Since the label of the external boundary is $`K(uq_1uq_2uq_3)`$, we can glue in a disc with this label, and make our annular diagram into an ordinary diagram with boundary label $`u_b^n`$. Since the discs are filled with cells corresponding to the relations of $`G_{m,n}`$, and the rest is filled with cells corresponding to the new relations, we get that all defining relations of $`B(m,n)`$ follow from the (finitely many) relations that we got. The group $`H`$ that we just created is what we need.

###### Theorem 16

(Olshanskii, Sapir, 1998) The natural homomorphism of $`B(m,n)`$ into $`H`$ is a quasi-isometric embedding. The group $`H`$ has isoperimetric function $`n^{8+ϵ}`$ provided $`n`$ is odd and $`10^{10}`$; $`lim_n\mathrm{}ϵ=0`$.

Similarly we can quasi-isometrically embed a relatively free group $`G`$ of any finitely based group variety into a finitely presented group. The resulting group will have a polynomial isoperimetric function provided $`G`$ has polynomial verbal isoperimetric function. This function is defined as follows:

> Let $`v(x_1,\mathrm{},x_n)`$ be a word. Suppose that $`w`$ is in the verbal subgroup vsg$`(v)`$. Then $`w=_iv(X_{1,i},\mathrm{},X_{n,i})`$. Fix such a representation of $`w`$ with minimal sum of lengths of all $`|X_{j,i}|`$ involved in this representation. The verbal isoperimetric function gives an upper bound for this sum in terms of $`|w|`$.

This function does not depend (up to “big O”) on the identity defining the variety, so one can speak about verbal isoperimetric functions of varieties.

For example, the variety of solvable groups has polynomial verbal isoperimetric function, so our construction embeds it into a group with polynomial Dehn function.

The variety of Burnside groups of odd exponent $`n>>1`$ has verbal isoperimetric function $`n^{1+ϵ}`$ ($`lim_n\mathrm{}ϵ=0`$). This can be proven by modifying Storozhev’s argument from  (Storozhev’s argument gives estimate $`n^4`$ for the verbal isoperimetric function).

We can also embed in a similar way the Baumslag-Solitar groups $`G_{1,n}`$ into finitely presented groups with isoperimetric function $`n^{10}`$.

## 2 Methods

### 2.1 $`S`$-machines

First of all let us present some ideas how to find a group with an “arbitrary” Dehn function. Consider again the main diagram called a disc on the Figure 3 for the group $`G_{m,n}`$.

The disc is divided by the $`k`$-bands into $`N`$ sectors. The words written on the circles between consecutive $`k`$’s have the form

$$uq_1uq_2uq_3$$

and to pass from one level to another level we replace $`q_i`$ by $`aq_i`$. So we can imagine these words written on a tape of a Turing machine, $`q_i`$ mark the places where the heads are, and we have a rule of the form

$$[q_1aq_1,q_2aq_2,q_3aq_3]$$

for every $`a`$.

What we get is a simple example of a so called $`S`$-machine.

Roughly speaking, the difference between $`S`$-machines and ordinary Turing machines is that $`S`$-machines are almost “blind”. They “see” letters written on the tape only when these letters are between two heads of the machine and the heads are very close to each other. If the heads are far apart, the machine does not see any letters on the tape, in this case a command executed by the machine depends only on the state of the heads.

In contrast, ordinary Turing machines can see letters on the tape near the position where the head is. The command executed by the machine always depends not only on the state of the head but (which is very important!) also on the letter(s) observed by the head. Notice that even for moving the head a Turing machine one square to the left, one needs to know the content of the square to the left of the head.

Let us give a precise definition of $`S`$-machines. Let $`k`$ be a natural number. Consider now a language of admissible words. It consists of words of the form

$$q_1u_1q_2\mathrm{}u_kq_{k+1}$$

where $`q_i`$ are letters from disjoint sets $`Q_i`$, $`i=1,\mathrm{},k+1`$, $`u_i`$ are reduced group words in an alphabet $`Y_i`$ ($`Y_i`$ are not necessarily disjoint), the sets $`\overline{Y}=Y_i`$ and $`\overline{Q}=Q_i`$ are disjoint.

Notice that in every admissible word, there is exactly one representative of each $`Q_i`$ and these representatives appear in this word in the order of the indices of $`Q_i`$.

If $`0ijk`$ and $`W=q_1u_1q_2\mathrm{}u_kq_{k+1}`$ is an admissible word then the subword $`q_iu_i\mathrm{}q_j`$ of $`W`$ is called the $`(Q_i,Q_j)`$-subword of $`W`$ ($`i<j`$).

An $`S`$-machine is a rewriting system . The objects of this rewriting system are all admissible words.

The rewriting rules, or $`S`$-rules, have the following form:

$$[U_1V_1,\mathrm{},U_mV_m]$$

where the following conditions hold:

Each $`U_i`$ is a subword of an admissible word starting with a $`Q_{\mathrm{}}`$-letter and ending with a $`Q_r`$-letter (where $`\mathrm{}=\mathrm{}(i)`$ must not exceed $`r=r(i)`$, of course).

If $`i<j`$ then $`r(i)<\mathrm{}(j)`$.

Each $`V_i`$ is also a subword of an admissible word whose $`Q`$-letters belong to $`Q_{\mathrm{}(i)}\mathrm{}Q_{r(i)}`$ and which contains a $`Q_{\mathrm{}}`$-letter and a $`Q_r`$-letter.

If $`\mathrm{}(1)=1`$ then $`V_1`$ must start with a $`Q_1`$-letter and if $`r(m)=k+1`$ then $`V_n`$ must end with a $`Q_{k+1}`$-letter (so tape letters are not inserted to the left of $`Q_1`$-letters and to the right of $`Q_{k+1}`$-letters).

To apply an $`S`$-rule to a word $`W`$ means to replace simultaneously subwords $`U_i`$ by subwords $`V_i`$, $`i=1,\mathrm{},m`$. In particular, this means that our rule is not applicable if one of the $`U_i`$’s is not a subword of $`W`$. The following convention is important:

After every application of a rewriting rule, the word is automatically reduced. We do not consider reducing of an admissible word a separate step of an $`S`$-machine.

We also always assume that an $`S`$-machine is symmetric, that is for every rule of the $`S`$-machine the inverse rule (defined in the natural way) is also a rule of this $`S`$-machine. This reflects the fact that the $`r`$-edges in the disc on Figure 3 can point away from the hub or toward the hub.

Notice that virtually any $`S`$-machine is highly nondeterministic.

Among all admissible words of an $`S`$-machine we fix one word $`W_0`$. If an $`S`$-machine $`𝒮`$ can take an admissible word $`W`$ to $`W_0`$ then we say that $`𝒮`$ accepts $`W`$. We can define a time and space function of an $`S`$-machine as usual. If $`UU_1\mathrm{}U_n=W_0`$ is an accepting computation of the $`𝒮`$-machine $`𝒮`$ then $`|U|+|U_1|+\mathrm{}+|U_n|`$ is called the area of this computation. This allows us to define the area function of an $`S`$-machine.

###### Theorem 17

(Sapir, ) $`S`$-machines are polynomially equivalent to Turing machines. More precisely for every Turing machine $`M`$ with time function $`T(n)`$ there exists an $`S`$-machine with area function $`T(n)^4`$ which is equivalent to $`M`$ (this means that there exists a correspondence $`\varphi `$ between configurations of $`M`$ and admissible words of $`𝒮`$, given a configuration $`c`$, the word $`\varphi (c)`$ is computable in linear time, and the machine $`M`$ accepts $`c`$ if and only if $`𝒮`$ accepts $`\varphi (c)`$).

In fact a stronger theorem can be deduced from the main results of . It was recently proved by Sapir.

###### Theorem 18

(Sapir, 1998) For every Turing machine $`M`$ with time function $`T(n)`$ such that $`T(n)^4`$ is superadditive, there exists an $`S`$-machine $`𝒮`$ with one head and only one internal state which is equivalent to $`M`$ and has time function $`T(n)^4`$.

Notice that an $`S`$-machine with one head and one state letter is completely blind (in the sense explained above). The rules of such an $`S`$-machine have the following very simple form:

$$[quqv]$$

where $`q`$ is the internal state, $`u`$ and $`v`$ are words in the tape alphabet.

The amazing fact is that the proof of a completely Computer Science statement, Theorem 18, involves some heavy geometric group theory. We first convert $`M`$ into an $`S`$-machine $`𝒮_1`$ with many heads, then convert $`𝒮_1`$ into the group from  with Dehn function $`T(n)^4`$, then convert the group into an $`S`$-machine $`𝒮`$ with one head and one internal state, having time function $`T(n)^4`$ (in the last step we use an idea from Miller ).

The group $`G_N(𝒮)`$ associated with an $`S`$-machine $`𝒮`$ is constructed in the same way as the group $`G_{m,n}`$ presented above. We add all rules of $`𝒮`$ to the set of generators and for every rule $`r`$ of the form $`[U_1V_1,\mathrm{},U_pV_p]`$ we have $`p`$ relations $`U_1^r=V_1,\mathrm{},U_p^r=V_p`$. These relations replace the relations $`q_i^r=aq_i`$ in the presentation of $`G_{m,n}`$. Other relations are the same.

Although this construction slightly differs from the construction in  it is possible to prove the following statement.

###### Theorem 19

(Sapir, ) Every Turing machine $`M`$ with time function $`T(n)`$ can be converted into an $`S`$-machine $`𝒮`$ in such a way that the Dehn function of the group $`G_N(𝒮)`$ is $`T(n)^4`$ provided $`T(n)^4`$ is superadditive.

Now in order to embed a finitely generated group $`G`$ into a finitely presented group we take a Turing machine $`M`$ recognizing words which are equal to 1 in $`G`$, convert it into an $`S`$-machine $`𝒮`$, and then basically repeat the construction of the group $`H_{m,n}`$ replacing $`B(m,n)`$ by $`G`$ and $`G_{m,n}`$ by $`G_N(𝒮)`$. The resulting group is denoted by $`H_N(𝒮)`$. It plays the role of group $`H`$ in Theorem 14.

### 2.2 Why $`S`$-machines?

Here we will explain why we need to convert Turing machines into $`S`$-machines.

Consider any Turing machine $`M`$. For simplicity assume that $`M`$ has one tape, which is always finite, but we can add squares at the right end of the tape, the alphabet $`A`$ of tape letters, the set $`Q`$ of states, and the set $`R`$ of transitions. As usual we assume that the head is always placed between two squares of the tape, and observes both squares. So the transitions have the form $`uqvu^{}q^{}v^{}`$ where $`u,v,u^{},v^{}`$ are words in the tape alphabet, $`q,q^{}Q`$ (see  for details). Then using the same idea as in the construction of $`G_{m,n}`$ we can replace the relations $`q_i^r=aq_i`$ by $`(uqv)^r=u^{}q^{}v^{}`$ (here $`r`$ is a letter associated with the transition of $`M`$). As in  we assume that $`M`$ has only one accept configuration $`W_0`$.

Thus we have the following presentation of the group $`G(M)`$ associated with $`M`$.

* $`(uqv)^r=u^{}q^{}v^{}`$, for every transition $`r=[uqvu^{}q^{}v^{}]`$ of the machine $`M`$,
* $`ar=ra`$, for every $`aA`$ and every transition $`r`$
* $`kr=rk`$, for every $`k\{k_1,\mathrm{},k_N\}`$ and every transition $`r`$.

As before, we need $`N`$ copies of each of these relations written in disjoint alphabets. The hub relation will have the form $`K(W_0)`$ where $`W_0`$ is the accept configuration.

Now it is easy to see that for every accepted word $`U`$ we can tessellate the disc with boundary label $`K(U)`$ into cells labeled by these relations. Let $`U=U_1U_2\mathrm{}U_p=W_0`$ be an accepting computation. As before we will have a sequence of concentric circles, each labeled by $`K(U_i)`$, the innermost oval will be labeled by $`K(W_0)`$.

So it is easy to see that the word $`K(U)`$ is equal to 1 in $`G(M)`$ if the configuration $`U`$ is accepted by $`M`$.

Unfortunately the converse statement is wrong in most cases and this is precisely why we need $`S`$-machines. Let us demonstrate this on a simple example. Consider the following Turing machine $`M`$. It has two states $`q,q_0`$ and one tape letter $`a`$. The only transitions are the following:

* $`aqq_0`$,
* $`aq_0q_0`$.

The stop configuration is $`q_0`$ (the tape is empty). It is clear that the set of configurations accepted by this machine consists of configurations $`a^nq_0`$ and $`a^mq`$ where $`n0,m>0`$, and does not include, for example, the configuration $`q`$. Thus we would like $`K(q)`$ to be not equal to 1 in $`G(M)`$. The diagram on Figure 5 shows that $`K(q)`$ is equal to 1 in this group.

Fig. 5.

This picture shows the tessellation of only one of the sectors. The other sectors are tessellated in the same way.

One can easily see the difference between this picture and the standard picture of a disc. Here we have pairs of cells which have two common edges, and in the standard disc cells could have at most one common edge.

The diagram on Figure 6 is a subdiagram of the diagram on Fig. 5. It consists of two cells corresponding to the relations $`r_2a=ar_2`$ and $`(aq_0)^{r_2}=q_0`$ and has boundary label corresponding to the relation $`(q_0)^{r_2}=a^1q_0`$ which is the relation corresponding to the rule $`[q_0a^1q_0]`$, the inverse rule for $`[q_0aq_0]`$.

Fig. 6.

It is possible to prove that the group $`G(M)`$ actually simulates the $`S`$-machine with the set of admissible words $`a^nq`$, $`a^nq_0`$ and the set of rules

* $`qa^1q_0`$,
* $`q_0a^1q_0`$.

plus the inverse rules. This $`S`$-machine is “stronger” than $`M`$, it accepts more configurations, including the configuration $`q`$.

In general if we take any Turing machine $`M`$ and repeat this construction we will get a group simulating the $`S`$-machine obtained by replacing every transition $`uqvu^{}q^{}v^{}`$ by the $`S`$-rule $`[qu^1u^{}q^{}v^{}v^1]`$. This $`S`$-machine will almost always be much stronger than the original Turing machine.

One way around this problem was invented by Boone and Novikov . This is why they used the Baumslag-Solitar type relations $`x^a=x^2`$. These relations prevent appearance of negative letters on the “tape” (the concentric circles in the disc). But we could not use these relations because they make the Dehn function exponential.

Thus we had to prove instead that $`S`$-machines are polynomially equivalent to ordinary Turing machines (Theorem 17).

### 2.3 Geometry of van Kampen Diagrams

In order to analyze an arbitrary diagram over $`H=H_{m,n}`$, and $`H_N(𝒮)`$ in general we change the presentation of $`H`$. We add all words $`K(u)`$ (discs) and all relations of $`G=B`$ to the presentation. The presentation becomes infinite. After that we order the relations, saying that the discs have the highest rank, $`r`$-relations have smaller ranks, and the $`b`$-commutativity relations have the lowest rank. With every diagram we associate its type, a vector, the first coordinate of which is the number of discs, and the last coordinate is the number of $`b`$-commutativity cells (we omit the ranking of other relations). It turns out that diagrams of minimal type have nice geometric properties.

The main and easy concept which helps us analyze these diagrams is the concept of a band <sup>2</sup><sup>2</sup>2Other people call them corridors and strips.. If $`S`$ is a set of letters then an $`S`$-band is a sequence of cells $`\pi _1,\mathrm{},\pi _n`$ in a van Kampen diagram such that each two consecutive cells in this sequence have a common edge labeled by a letter from $`S`$. Figure 7 illustrates this concept.

Fig. 7.

The broken line formed of the intervals $`\mathrm{}(\pi _i,e_i)`$, $`\mathrm{}(\pi _i,e_{i1})`$ is called the median of this band.

We say that two bands cross if their medians cross. We say that a band is an annulus if its median is a closed curve. In this case the first and the last cells of the band coincide (see Figure 8)

Fig. 8.

Let $`S`$ and $`T`$ be two disjoint sets of letters, let ($`\pi `$, $`\pi _1`$, …, $`\pi _n`$, $`\pi ^{}`$) be an $`S`$-band and let ($`\pi `$, $`\gamma _1`$, …, $`\gamma _m`$, $`\pi ^{}`$) is a $`T`$-band. Suppose that:

* the medians of these bands form a simple closed curve,
* on the boundary of $`\pi `$ and on the boundary of $`\pi ^{}`$ the pairs of $`S`$-edges separate the pairs of $`T`$-edges,
* the start and end edges of these bands are not contained in the region bounded by the medians of the bands.

Then we say that these bands form an $`(S,T)`$-annulus and the curve formed by the medians of these bands is the median of this annulus.

For example, the diagram on Figure 3 contains $`k`$-bands, $`q_i`$-bands, $`A`$-bands crossing the circles transversally, and $`r`$-annuli filling the space between consecutive circles. In the diagram on Figure 4 we also have a $`\rho `$-annulus going around the disc, and many $`b`$-bands consisting of the $`b`$-commutativity cells.

The main idea is the following. In most relations of the presentation of $`H`$ one can choose two pairs of letters which belong to disjoint sets of letters. For example, the relation $`aba^1b^1=1`$ has a pair of $`a`$-letters and a pair of $`B`$-letters. The cells corresponding to these relations must form $`a`$-bands and $`b`$-bands in a van Kampen diagram. Each cell is an intersection of an $`a`$-band and a $`b`$-band. Thus if we prove that the number of $`a`$-bands is “small” and the number of $`b`$-bands is “small”, and that an $`a`$-band and a $`b`$-band can have at most one common cell, we show that the number of $`(a,b)`$-commutativity cells is “small”.

In order to bound the number of bands we use the following idea. Suppose that we have ruled out annuli. Then every band starts (ends) either on the boundary of the diagram (the number of such bands is linear in terms on the perimeter), or on the boundary of a cells (for example, an $`a`$-band can end on a disc). This gives us the direction in which to proceed.

First we assume that a diagram contains no discs and prove the absence of certain types of annuli: $`r`$-annuli, $`\rho `$-annuli, $`a`$-annuli, $`(r,a)`$-annuli, etc. (22 different kinds altogether). One way to prove it is to use a simultaneous induction: assume that one of these annuli exists, take the innermost annulus of one of these kinds. Then the subdiagram bounded by this annulus does not contain annuli of any of the 22 kinds. This makes the subdiagram look nice and eventually leads to existence of a pair of cells that cancel (thus the diagram is not reduced which contradicts its minimality).

Then we assume that the diagram contains discs and we bound the number of discs (see below) and their perimeters. Then we bound the number of $`r`$-bands by proving that there are no $`r`$-annuli, so each of the $`r`$-bands must start and end on the boundary of the diagram. Similarly we bound the number of $`\rho `$-bands. Then we bound the number of $`q`$-bands (they can start on the discs, and the perimeters of the discs are already bounded). Since every $`q`$-cell is an intersection of an $`r`$-band or a $`\rho `$-band and a $`q`$-band, we bound the number of $`q`$-cells. This leads to a bound of the number of $`A`$-bands (they can end on $`q`$-cells and on discs), and so on.

Of course we always need the absence of multiple intersections of bands. Although the next Figure 9 shows that a multiple intersection of an $`S`$-band and a $`T`$-band does not necessarily produce an $`(S,T)`$-annulus, it turns out to be enough to rule out $`(S,T)`$-annuli.

Fig. 9.

In order to bound the number of discs (and their perimeters) in a van Kampen diagram, we use the following idea.

The generic diagram over the presentation of $`H`$ looks like this:

Fig. 10.

Discs in the diagram are connected by $`k`$-bands.

So with every van Kampen diagram we can associate a graph of discs. The vertices of this graph are the discs plus one external vertex. Vertices are connected by the $`k`$-bands. If a $`k`$-band starts on a disc and ends on the boundary of the diagram, we assume that this band terminates in the external vertex. The degree of each internal vertex of this graph is $`N>>1`$. We prove that this graph cannot have bigons: two discs connected by a pair of $`k`$-bands. This implies that the graph of discs is hyperbolic, and a standard small cancellation theory applies . In particular there exists a disc with $`N3`$ external edges. This also implies that the number of discs and $`k`$-bands in the diagram is linear in terms of the perimeter.

In order to rule out $`r`$-annuli, $`\rho `$-annuli and other types of annuli, we use several type reducing surgeries on a diagram. One of them is illustrated by the following picture.

Moving $`r`$-bands. Suppose that in a minimal diagram $`\mathrm{\Delta }`$ an $`r`$-band $``$ touches a disc $`\mathrm{\Pi }`$ as in Figure 11 (that is one of the sides of $``$ has two common $`k`$-edges with the contour of the disc). Then it can be proved that the bottom path of $``$ has a common subpath with the contour of $`\mathrm{\Pi }`$ starting and ending with $`k`$-edges. Let $`p`$ be the maximal common subpath with this property, so that $`\mathrm{𝐛𝐨𝐭}(R)=qpq^{}`$, $`(\mathrm{\Pi })=pp_1`$. Without loss of generality we can assume that the label $`\mathrm{Lab}(p)`$ of the path $`p`$ has the form $`k_iwk_{i+1}w^{}k_{i+2}\mathrm{}k_j`$ where $`w=uq_1uq_2uq_3`$ Then for some word $`V`$ we have that $`\mathrm{Lab}(p)V`$ is a cyclic shift of $`K(w)=\mathrm{Lab}((\mathrm{\Pi }))`$. One can construct an $`r`$-band $`^{}`$ with the bottom path labeled by the word $`V`$ and the $`r`$-edges having the same labels as in $``$. Let $`^{\prime \prime }`$ be the subband of $``$ with bottom path $`p`$, so $`=_1^{\prime \prime }_2`$. Let $`e`$ be the start edge of $`^{\prime \prime }`$ and let $`e^{}`$ be the end edge of $`^{\prime \prime }`$. Cut the diagram $`\mathrm{\Delta }`$ along the path $`e^1p_1e^{}`$. We can fill the resulting hole by gluing in the $`r`$-band $`^{}`$ and the mirror image $`\overline{}^{}`$ of $`^{}`$. The new diagram $`\mathrm{\Delta }^{}`$ that we obtain this way will have two $`r`$-bands instead of the old $`r`$-band $``$. The first is $`_1(\overline{}^{})^1_2`$ (the inverse band $`(\overline{}^{})^1`$ differs from $`\overline{}^{}`$ by the order of cells) and the second one is $`^{\prime \prime }^{}`$. The second $`r`$-band is an annulus which touches $`\mathrm{\Pi }`$ along its inner boundary. If we replace the disc $`\mathrm{\Pi }`$ by the corresponding van Kampen diagram over the presentation of $`G_N(𝒮)`$, we see that the subdiagram $`\mathrm{\Pi }^{}`$ bounded by the outer boundary of the annulus $`^{\prime \prime }^{}`$ is a diagram over the presentation of $`G_N(𝒮)`$ with exactly one hub and no $`r`$-edges on the boundary. Then one can prove that $`\mathrm{\Pi }^{}`$ is a disc (corresponding to some computation). We replace it by one cell of the infinite presentation of $`H`$. Then we reduce the resulting diagram.

Fig. 11.

This construction amounts to changing the disc $`\mathrm{\Pi }`$, moving the band $``$ through the disc and then reducing the resulting diagram.

Now suppose that there exists an $`r`$-annulus in our van Kampen diagram as in Figure 12.

Fig. 12.

Suppose that there are discs inside the region bounded by this annulus. Then these discs form a hyperbolic graph, and so the $`r`$-band will intersect more than 1/2 of the $`k`$-bands going out of one of these discs. Then the $`r`$-band moving construction reduces the type of the diagram. Thus the region bounded by the $`r`$-annulus cannot contain discs. But we have ruled out the case when a diagram without discs contains an $`r`$-annulus, a contradiction.

In order to bound the perimeters of discs and $`B`$-cells we use the following idea. The contour of a disc contains a constant number of non $`A`$-edges. Thus in order to bound the perimeter of a disc, we need to bound the number of $`A`$-edges on the contour of it. Every $`A`$-edge on the contour of a discs is the start edge of an $`a`$-band. An $`a`$-band consists of $`a`$-commutativity cells corresponding to relations of the form $`ab=ba`$, $`ar=ra`$ or $`a\rho =\rho a`$ or to the relations of the form $`a^\rho =ab`$. Thus an $`a`$-band can end either on a disc or on the boundary of a $`(a,q,r)`$-cell. The latter belongs to an $`r`$-band and we already know that the diagram contains only “small number” of $`r`$-bands. Thus if the a disc has a very big perimeter and many of the $`a`$-bands starting on the contour of this disc end on boundaries of $`(a,q,r)`$-cells, then many of these $`a`$-bands must end on the contour of the same $`r`$-band. The following lemma shows that it is impossible.

###### Lemma 2

Let $`_1`$,…,$`_n`$ be maximal $`a`$-bands starting on a path $`p`$ where $`p`$ is an $`A`$-subpath of the boundary of a disc $`\mathrm{\Pi }`$. Suppose that the end edges of all $`_i`$ are on the contours of $`r`$-cells belonging to the same $`r`$-band $`𝒯`$. Then $`n2`$.

Sketch of the Proof. Indeed, if $`n>2`$ then there are three $`a`$-bands, say, $`_1`$, $`_2`$, $`_3`$ starting on $`p`$ and ending on three different cells $`\pi _1`$, $`\pi _2`$ and $`\pi _3`$ of $`𝒯`$. We can assume that $`\pi _2`$ is between $`\pi _1`$ and $`\pi _3`$ (see Figure 13). Consider the minimal subdiagram $`\mathrm{\Delta }_1`$ of our diagram containing $`a`$-bands $`_1,_2,_3`$, the minimal subpath of the path $`p`$ containing the starting edges of $`_1`$, $`_2`$, $`_3`$, and the part of the band $`𝒯`$ between $`\pi _1`$ and $`\pi _3`$ Then $`\mathrm{\Delta }_1`$ has no $`k`$-edges on its contour. Therefore $`\mathrm{\Delta }_1`$ does not contain discs. Therefore the maximal $`q`$-band $`𝒬`$ in $`\mathrm{\Delta }_1`$ containing $`\pi _2`$ divides $`\mathrm{\Delta }_2`$ into two parts (that is if we delete the $`q`$-edges from $`𝒬`$, the diagram $`\mathrm{\Delta }_2`$ will fall into two pieces). The subpath of the path $`p`$ containing the start edges of $`_1,_2,_3`$ is contained in one of these parts since it does not contain $`\overline{Q}`$-edges. The cells $`\pi _1`$ and $`\pi _3`$ belong to different parts because $`𝒬`$ cannot intersect $`𝒯`$ twice. Since the $`\pi _1`$ and $`\pi _3`$ are connected with the cells on $`p`$ by $`a`$-bands, one of these bands must intersect $`𝒬`$ which is impossible (a $`q`$-band cannot cross an $`a`$-band). $`\mathrm{}`$

Fig. 13.

Finally we need to estimate the number and perimeters of $`B`$-cells (i.e. cells corresponding to relations of the group $`B`$). Here we use the following trick. Suppose that two $`B`$-cells are connected by a $`b`$-band consisting of $`(a,b)`$-commutativity cell. Then we can cut the two $`B`$-cells together with the $`b`$-band from the diagram, and replace it by one $`B`$-cell and a number of $`(a,b)`$-commutativity relations. This reduces the type of the diagram because the commutativity relations have smaller rank than $`B`$-relations. Figure 14 shows how this surgery proceeds.

Fig. 14.

This implies that every $`b`$-band starting on the contour of a $`B`$-cell must end either on the boundary of the diagram or on the contour of a $`(a,\rho ,b)`$-cell. The number of maximal $`a`$-bands in the diagram is bounded (because the total perimeter of the discs is bounded, and the number of $`q`$-cells is bounded too), and a lemma similar to Lemma 2 shows that the number of $`b`$-bands starting on the contour of the same $`B`$-cell and ending on the contour of the same $`a`$-band is at most 2. This leads to the bound of the number of $`B`$-cells and the total perimeter of $`B`$-cells.

Finally we can estimate the areas of words in $`H`$ relative to the finite presentation of $`H`$. Take any word $`w`$ which is equal to 1 in $`H`$. Then there exists a diagram over the infinite presentation of $`H`$ (with discs and $`B`$-cells) with boundary label $`w`$. The total perimeter of discs and $`B`$-cells is bounded by a polynomial in $`|w|`$. Now replace every disc by the van Kampen diagram over the finite presentation of $`H`$ (as in Fig. 3), and replace each $`B`$-cell by the diagram on Fig. 4 consisting of two discs and a relatively small number of other cells. The resulting diagram will be a van Kampen diagram over the finite presentation of $`H`$. It is easy to see that if the perimeter of a disc is $`p`$ then the area is $`O(T(p)^2)`$ where $`T`$ is the time function of the $`S`$-machine. This gives an estimate of the area of $`w`$ which is polynomially equivalent to $`T(|w|)`$.

### 2.4 Why Is There No Distortion?

The proof that the embedding of $`B(m,n)`$ into $`H_{m,n}`$ and in general any recursively presented group $`G`$ into $`H_N(𝒮)`$ is undistorted also uses bands and annuli, and the structure of diagrams over the infinite presentation of $`H`$ described in the previous section.

Here we present the main points of the proof of bounded distortion in Theorems 10, 14 and 16.

For simplicity consider the case of the group $`H=H_{m,n}`$ from Theorem 16. The general case of $`H_N(𝒮)`$ is similar. By definition of bounded distortion, we have to find a constant $`c>0`$ such that for any element $`gB(m,n)`$ represented by a geodesic (in $`B(m,n)`$) word $`U=U(b_1,\mathrm{},b_m)`$ in the alphabet $`B=\{b_1,\mathrm{},b_m\}`$ and for any word $`Z`$ in the generators of $`H`$, that represents the same element, we have $`|Z|c|U|`$.

In order to achieve this goal, consider the minimal diagram $`\mathrm{\Delta }`$ over the infinite presentation of $`H`$ considered in the previous section, with boundary label $`UZ^1`$. Then the boundary of $`\mathrm{\Delta }`$ has the form $`p^1p^{}`$ where $`\mathrm{Lab}(p)U`$, $`\mathrm{Lab}(p^{})Z`$. We need to show that $`|p|c|p^{}|`$ for some constant $`c`$. It suffices to make a correspondence between $`b`$-edges of $`p`$ and edges of $`p^{}`$, such that any edge of $`p^{}`$ corresponds to at most $`c^1`$ edges of $`p`$.

First of all notice that we can assume that no $`B`$-cell in $`\mathrm{\Delta }`$ has a common edge with $`p`$. Indeed, if such a $`B`$-cell exists, we can cut it off reducing the type of the diagram and replacing the path $`p`$ with a not shorter path $`p_1`$ (recall that $`U`$ was a geodesic word representing $`g`$).

Therefore for every edge $`e`$ on $`p`$, there is a maximal $`b`$-band $`𝒯`$ in $`\mathrm{\Delta }`$, starting at $`e`$. It can end neither on $`p`$ nor on the boundary of a $`G_b`$-cell (both cases are ruled out in the same manner as it was done in the previous section: we can do a type reducing surgery again).

If $`𝒯`$ ends on the path $`p^{}`$, we associate the terminal edge of $`𝒯`$ with $`e`$. Another possibility is that $`𝒯`$ terminates on the boundary of some maximal $`a`$-band (at the cell labeled by a relator $`\rho ^1a_i\rho b_i^1a_i^1`$). A lemma similar to Lemma 2 shows that at most 2 maximal $`b`$-bands starting on $`p`$ can end on the boundary of the same $`a`$-band. This means that we can consider the set $`𝒜`$ of $`a`$-bands where these $`b`$-bands end.

The most pleasant (for us) among these $`a`$-bands are those which start or end on $`p^{}`$ (they cannot end on $`p`$ because $`p`$ does not have $`A`$-edges). Other $`a`$-bands can terminate either on contours of $`r`$-bands or on disks.

We need to consider two cases. In the first case the number of those $`r`$-bands is large (proportional to the number of $`a`$-bands in $`𝒜`$). Since there are no $`r`$-annuli in $`\mathrm{\Delta }`$ (see the previous section), each of these $`r`$-bands starts and ends on $`p^{}`$, and we obtain a desired inequality $`|p^{}|c|p|`$.

In the second case we have to assume that the number of $`r`$-bands where $`a`$-bands terminate is “small”. Since by a variation of Lemma 2 the number of $`a`$-bands terminating on the same $`r`$-band is bounded by a constant, in this case most $`a`$-bands in $`𝒜`$ terminate on discs.

In this situation we use the so called ovals and their shadows (see  and ).

An oval is a simple closed path $`h`$ in the disk graph of the diagram $`\mathrm{\Delta }`$. It divides the plane into two regions. One of them, denoted by $`O(h)`$, must possess the following property. For every disk $`\mathrm{\Pi }`$ on $`h`$, the number $`n_1`$ of maximal $`k`$-bands going from $`\mathrm{\Pi }`$ into $`O(h)`$ and the number $`n_2`$ of the maximal $`k`$-bands going from $`\mathrm{\Pi }`$ into the exterior of $`O(h)`$ satisfy the following inequalities:

$$n_1n_2+8,n_22n_1.$$

The hyperbolicity of the disk graph and high degrees of its interior vertices make possible drawing an oval $`h`$ passing via any interior edge of the disc graph of $`\mathrm{\Delta }`$.

One of the main properties of ovals is that if an $`r`$-band starts outside the subdiagram $`O(h)`$ bounded by the oval and then intersects the oval, it cannot leave $`O(h)`$. Indeed otherwise the hyperbolicity of the disk graph would imply the existence of either a $`(k,r)`$-annulus (which is impossible, see the previous section) or an $`r`$-band intersecting too many maximal $`k`$-bands starting on the same disk (again it is impossible because of the Moving $`r`$-bands construction from the previous section).

Thus any maximal $`r`$-band crossing an oval $`h`$, must intersect its shadow, i.e. the boundary subpath of the diagram lying in $`O(h)`$. This allows us to prove that the shadow of any oval $`h`$ is sufficiently long comparing to the perimeter of any disk $`\mathrm{\Pi }`$ crossed by $`h`$. We can also choose $`h`$ in such a way that the shadow of $`h`$ is inside $`p^{}`$ (because $`p`$ does not contain $`k`$-edges). Therefore the number of $`a`$-bands ending on the contour of a disc does not exceed the length of the shadow of any oval passing through the disc. If the bands $`𝒜`$ end on different discs $`\mathrm{\Pi }_1`$,…,$`\mathrm{\Pi }_k`$ then the hyperbolicity of the disc graph allows us to find ovals passing through these discs which have disjoint shadows, all inside $`p^{}`$. Thus the length of $`p^{}`$ cannot be smaller than the number of $`a`$-bands in $`𝒜`$, which in turn, as we know, cannot be much smaller than the length of $`p`$.

The proof of the result that the shadow of an oval $`h`$ is sufficiently long comparing to the perimeter of a disc $`\mathrm{\Pi }`$ in $`h`$ consists of two cases. In the first case the number of maximal $`r`$-band in $`O(h)`$ is sufficiently large (greater than, say, $`\frac{1}{20}`$ of the number of all $`a`$-edges between successive $`k`$-edges of $`\mathrm{\Pi }`$). This case is clear since all the $`r`$-bands must terminate on the shadow.

The second case is complementary to the first one. Since the number of the $`r`$-bands is small, the quantity of the $`a`$-bands going from $`\mathrm{\Pi }`$ into $`O(p)`$ and terminating on $`r`$-bands, is small too (Lemma 2 works again). Therefore a majority of them terminates either in the shadow of $`\mathrm{\Pi }`$ (this is the best alternative for us) or on some disks $`\mathrm{\Pi }^{},\mathrm{\Pi }^{\prime \prime },\mathrm{}\mathrm{\Pi }^{(k)}`$ inside of $`O(h)`$.

This situation can be analyzed by induction: as before we can draw ovals $`h_1,\mathrm{},h_k`$ passing through $`\mathrm{\Pi }^{},\mathrm{},\mathrm{\Pi }^{(k)}`$ respectively, whose shadows are disjoint and are inside the shadow of $`h`$.

### 2.5 Embeddings With Given Length Functions

Here we present the main ideas of the proofs of results from  (see Section 1.3).

If $`G`$ is a subgroup of a group $`H`$ with a finite set of generators $`B=\{b_1,\mathrm{},b_n\}`$ then the function $`\mathrm{}(g)=|g|_B`$ on $`G`$ evidently satisfies conditions (D1)-(D3) from Theorem 8. For instance condition (D3) holds because the number of all words of length at most $`k`$ in the alphabet $`B`$ grows exponentially as $`k\mathrm{}`$.

To prove that every function $`G𝐍`$ satisfying conditions (D1)-(D3) can be realized as the length function of $`G`$ inside a finitely generated group $`H`$, we start with a presentation $`G=F_G/N`$, where $`F_G`$ is a free group with the basis $`\{x_g\}_{gG\backslash \{1\}}`$ and $`N`$ is the kernel of homomorphism $`ϵ:x_gg`$.

Then we construct an embedding $`\beta :x_gX_g`$ of $`F_G`$ into the 2-generated free group $`F=F_2=F(b_1,b_2)`$, such that the image $`\beta (F_G)`$ is freely generated by $`X_g`$, $`gG\backslash \{1\}`$ and the words $`X_g`$ are very “independent” in the sense described below.

The group $`H`$ is equal to the quotient $`F/L`$, where $`L`$ is the normal closure of $`\beta (N)`$ in $`F`$.

Notice that whatever homomorphism $`\beta `$ we choose, it induces a homomorphism $`\gamma :GH`$. To make this homomorphism injective, we need the following property:

$$L\beta (F_G)=\beta (N).$$

In fact $`\beta (F_G)`$ satisfies the following much stronger property:

(\*) For any normal subgroup $`U\beta (F_G)`$ there is a normal subgroup $`VF`$ such that $`U=V\beta (F_G)`$.

The fact that free groups and more generally every non-elementary hyperbolic group has plenty of infinitely generated free subgroups with property (\*) is interesting in its own right, it was the key ingredient in Olshanskii’s proof from  of the fact that every non-elementary hyperbolic group is SQ-universal.

It turns out that we can make $`\beta `$ satisfy condition (\*) by choosing reduced words $`X_g`$ with the following small cancellation condition:

(\**) If $`Y`$ is a subword of a word $`X_g`$ and $`|Y|\frac{1}{50}|X_g|`$ then $`Y`$ occurs in $`X_g`$ as a subword only once, and $`Y`$ occurs neither in $`X_g^1`$ nor in $`X_h^{\pm 1}`$ for $`hg`$.

It is relatively easy to construct an infinite set of words $`X_g`$ in the alphabet $`\{b_1,b_2\}`$ which satisfies the (\**)-condition and has exponential growth, that is the number of different words $`X_g`$ of length $`k`$ grows exponentially as $`k\mathrm{}`$.

Since by condition (D3) the number of elements $`gG`$ with $`\mathrm{}(g)k`$ does not exceed $`c^k`$ for some constant $`c`$, we can choose the set $`\{X_g\}`$ in such a way that

$$\mathrm{}(g)|X_g|<d\mathrm{}(g)$$

for some positive constant $`d`$ and every $`gG\backslash \{1\}`$.

We need to show that the embedding $`\gamma :GH`$ has bounded distortion. For this we take any element $`X_g`$ of $`\gamma (G)`$ and consider the shortest word $`W`$ in the alphabet $`\{b_1,b_2\}`$ representing $`X_g`$ in $`H`$. The group $`H`$ is given by the presentation consisting of all relations of the form $`X_{g_1}X_{g_2}\mathrm{}X_{g_n}=1`$ where $`g_1g_2\mathrm{}g_n=1`$ in $`G`$.

Since $`X_g=W`$ modulo this presentation, we can consider the corresponding van Kampen diagram $`\mathrm{\Delta }`$ with boundary label $`X_gW^1`$. We can assume that the number of cells in $`\mathrm{\Delta }`$ is minimal among all such diagrams.

The condition (\**) implies the following property of van Kampen diagrams over the presentation of $`H`$. Let $`\mathrm{\Pi }_1`$ and $`\mathrm{\Pi }_2`$ be cells in a diagram $`\mathrm{\Delta }`$ having a common edge. Then either any common arc $`p`$ of the boundaries $`\mathrm{\Pi }_1`$ and $`\mathrm{\Pi }_2`$ is short comparing to the perimeters $`P_1,P_2`$ of the cells (say, $`|p|\frac{1}{10}\mathrm{min}(P_1,P_2)`$), or a subdiagram consisting of $`\mathrm{\Pi }_1`$ and $`\mathrm{\Pi }_2`$, has also a boundary label of the form $`w=w(X_{g_1},\mathrm{},X_{g_n})`$, i.e. the subdiagram can be replaced by one cell. The latter option cannot occur in $`\mathrm{\Delta }`$ because of the minimality of the diagram $`\mathrm{\Delta }`$. Thus $`\mathrm{\Delta }`$ satisfies a small cancellation condition .

This in turn allows us to prove that the word $`W`$ is freely equal to a product $`X_{g_1}^{\pm 1}\mathrm{}X_{g_s}^{\pm 1}`$ for some $`g_jG`$ with $`g=g_1^{\pm 1}\mathrm{}g_s^{\pm 1}`$ (see  for details). Further, since the cancellations in such a product are small,

$$|\gamma (g)|_H(1\frac{2}{50})\underset{j=1}{\overset{s}{}}|X_{g_1}|.$$

By conditions (D1), (D2), and by the choice of $`X_g`$, we have:

$$|\gamma (g)|_H0.96\mathrm{}(g_j)=0.96\mathrm{}(g_j^{\pm 1})0.96\mathrm{}(g).$$

Hence $`0.96\mathrm{}(g)|\gamma (g)|_Hd\mathrm{}(g)`$, so $`\mathrm{}`$ is $`O`$-equivalent to the length function of $`G`$ in $`H`$.

Alexander Yu. Olshanskii   
Department of Higher Algebra   
MEHMAT. Moscow State University   
olsh@nw.math.msu.su   

Mark V. Sapir   
Department of Mathematics   
Vanderbilt University   
http://www.math.vanderbilt.edu/$``$msapir