Definitions

Recall that isoperimetric functions of a finitely presented group $G=\langle X\ \vert \ R\rangle$ 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 [25] a word $w\in X\cup X^{-1}$ is equal to 1 in the group G if and only if there exists a van Kampen diagram $\Delta$ over the presentation of G with boundary label w. The number of cells in $\Delta$is equal to the number of factors in a representation of w as a product of conjugates of relators from R:

$$w=\prod r_i^{u_i}.$$ (1)

We are going to establish a more precise relation between equation (1) and the van Kampen diagram $\Delta$ later (see Lemma 1 below).

If a van Kampen diagram has minimal number of cells, n, among all diagrams with the same boundary label w then we say that w has area n. A function f(m) is called an isoperimetric function of the presentation $\langle X \ \vert \ R\rangle$ 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 ${\bf N}\to {\bf N}$, one can define a quasi-order saying that $f\prec g$if

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

for all m and some constant C. Any minimal (with respect to $\prec$) isoperimetric function is called the Dehn function of the presentation $\langle X \ \vert \ R\rangle$. The article ``the" is appropriate here because it is well known [3], [13], [19] that Dehn functions of different finite presentations of the same group are equivalent, i.e., they satisfy inequalities

$$f_1\prec f_2, \hbox{\quad} f_2\prec f_1$$

.

We can also define isodiametric functions introduced by Gersten [16]. These functions measure the diameter of a van Kampen diagram with given perimeter². 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=\langle X\ \vert \ R\rangle$, d(n) must exceed the diameter of every word w= 1 (mod G) of length $\le n$. The equivalence of isodiametric functions is defined as before. Isodiametric functions of different finite presentations of the same group are always equivalent [19].

Both isoperimetric and isodiametric functions reflect the decidability of the word problem in the group. In particular it is well known (see, for example, [26]) that 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 $\langle a,b \ \vert\ a^b=a^2\rangle$ can be solved in quadratic time (since this group is representable by $2\times 2$ integer matrices) while the Dehn function is exponential [11]. 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=\langle X\rangle$ and $H=\langle X\cup Y\rangle$ are finitely presented, one can also define the area function of G in H. 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 distortion function and the length function. Let $G=\langle X\rangle$ be a finitely generated subgroup of a finitely generated group $H=\langle Y\rangle$. Then the distortion function $d_{G,H}(n): {\bf N}\to {\bf N}$ takes every natural number n to $\max\{\vert u\vert _{X}\ \vert\ u\in G, \vert u\vert _Y\le n\}$. 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 $\ell: G\to {\bf N}$ which takes every element g of G to |g|_Y, the length of g in H.

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

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

For example, every subgroup of the free group is (obviously) quasi-isometrically embedded, but the (cyclic) center $C=\langle c\rangle$ of the 3-dimensional Heisenberg group $H^3=\langle a,b,c\Vert \ [a,b]=c, ca=ac, cb=bc\rangle$ has quadratic distortion. Indeed cⁿ²=[aⁿ,bⁿ] for every n, the length of cⁿ² in C is n² and the length of this element in H³ is $\le 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 [12].

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 connections here. The first of them plays an important role in several papers by Bridson and others on isoperimetric functions. The second connection is new.

Theorem 1 (Bridson, [8])   Let G be a finitely presented group and $H\le G$ be a finitely generated subgroup of G with distortion function d(n). Then the Dehn function of the HNN extension $H = \langle G, t\ \vert h^t=h, h\in H\rangle$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 functions of finitely presented groups.  

Theorem 2 is new although a remark in [19] 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 [25]) and a result from Baumslag and Roseblade [5].

It is proved in [5] that every finitely generated subgroup E of $F_2\times F_2$is the equalizer (in [5] it is called the free corner pullback) of two homomorphisms $\phi: E'\to G$ and $\psi: E''\to G$ of two finitely generated subgroups E', E'' of F₂onto a finitely presented group G, that is $E=\{(u,v)\in E'\times E'' \ \vert \ \phi(u)=\psi(v)\}$. Since every finitely generated subgroup of F₂ is quasi-isometrically embedded in F₂, $E'\times E''$ 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 $\phi: F_m\to G$ and $\psi: F_n\to G$ 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=\langle x_1, ..., x_m\rangle$, $F_n=\langle y_1,...,y_n\rangle$ (we assume that these generating sets are closed under taking inverses). 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 $\phi$ and $\psi$ in H.

Let $r_1,...,r_\ell$ 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,...,r_\ell\}$ is closed under cyclic shifts and inverses.

For every i=1,...,m pick one word $t_i\in F_n$such that $\phi(x_i)=\psi(t_i)$. For every j=1,...,n pick one word s_j such that $\phi(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,...,m, j=1,...,n, $k=1,...,\ell$. Indeed, if $(u,v)\in E$, that is $\phi(u)=\psi(v)$and u=x_i1x_i2...x_ip then

(u,v)=(x_i1,t_i1)...(x_ip, t_ip)(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=\prod_{i=1}^d r_{k_i}^{w_i}.$$

Therefore

$$(u,v)=(x_{i_1},t_{i_1})...(x_{i_p}, t_{i_p}) \prod_{i=1}^d (1,r_{k_i})^{(w_i({\vec s}),w_i)}.$$ (2)

Here $w({\vec 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 $\Delta$ be a van Kampen diagram over a presentation $\langle X \ \vert \ R\rangle$ where X=X^-1, R is closed under cyclic shifts and inverses. Let w be the boundary label of $\Delta$. Then w is equal in the free group to a word of the form u₁r₁u₂r₂...u_dr_du_d+1 where:

1.

$r_i\in R$;

2.

u₁u₂...u_d+1=1 in the free group;

3.

$\sum_{i=1}^{d+1}\vert u_i\vert\le 4e$ where e is the number of edges of $\Delta$.

 

Proof. If $\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 $\Delta$ along f leaving the second vertex of f untouched. We can repeat this operation until we get a diagram $\Delta_1$ which does not have internal edges. It is easy to see that the boundary label of $\Delta_1$ is equal to w in the free group. The number of edges of $\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 $\Delta$ and the number of edges which belong to contours of cells in $\Delta_1$ (edges of type 2) is at most twice the number of such edges of $\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 $\Pi$ in $\Delta_1$ has more than one edge which has a common vertex with $\Pi$ but does not belong to the contour of $\Pi$ . Take any point O on $\partial(\Pi)$. Let p be the boundary path of $\Delta_1$starting at O and let q be the boundary path of $\Pi$ starting at O. Consider the path qq^-1p. The subpath q^-1p bounds a subdiagram of $\Delta_1$ containing all cells but $\Pi$. Replace the path q in qq^-1pby a loop q' with the same label starting at O and lying inside the cell $\Pi$. Let the region inside q' be a new cell $\Pi'$. Then the path q'q^-1p bounds a diagram whose boundary label is freely equal to w. Notice that $\Pi'$ has exactly one edge having a common vertex with $\Pi'$and not belonging to the contour of $\Pi$. Thus this operation reduces the number of cells which have more than one edge which has a common vertex with the cell but does not belong to the contour of it.

After a number of such transformations we shall have a diagram $\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 $\Delta_2$ cannot be bigger than the number of all edges in $\Delta_1$, so it cannot be more than two times bigger than the total number of edges in $\Delta$.

The boundary label of $\Delta_2$ is freely equal to w, and it has the form u₁r_i1u₂r_i2...u_dr_idu_d+1 where d is the number of cells in $\Delta$, u₁u₂...u_d+1 is the label of a tree, so u₁u₂...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 $\Delta$ because the word u₁u₂...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 $\langle y_1,...,y_n\ \vert \ r_1,...,r_\ell\rangle$ (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 $k\ge 1$. Then as before

(u,v)=(x_i1,t_i1)...(x_ip, t_ip)(1,a)

where u=x_i1...x_ip, $\psi(a)=1$.

Notice that the length of the word adoes not exceed

$$\vert v\vert+c_1\vert u\vert\le c_1(\vert u\vert+\vert v\vert)=c_1k$$

where c₁is the maximal length of t_i, i=1,...,m.

Let $\Delta$ be the minimal area van Kampen diagram over the presentation

$$\langle y_1,...,y_n\ \vert\ r_1,..., r_\ell\rangle$$

of Gwith the boundary label a. Then the area of $\Delta$ does not exceed d(c₁k). Since $\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 $\Delta$.

By Lemma 1,

a=u₁r_i1u₂...r_iqu_q+1

where u₁...u_q+1=1 in the free group, and $\sum \vert u_i\vert\le 4e$. Then

$$\begin{array}{l} (1,a)=(u_1({\vec s})\cdot 1\cdot u_2({\vec s... ...'(1,r_{i_2})\cdot...\cdot (1,r_{i_q})\cdot u_{q+1}' \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₂d(c₁k)+c₁k for some constant c₂. Hence the length in E of the element (u,v) does not exceed k(1+c₁)+c₂d(c₁k).

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 ddoes not exceed a function equivalent to the distortion function of E in H, it is enough, for every number $p\ge 1$, to take a word $a\in F_n$, from the kernel of $\psi$, $\vert a\vert\le 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₁r_i1u₂r_i2...r_idu_d+1 where u₁...u_d+1=1 in the free group). $\Box$