Length Functions of a Finitely Generated Group

Theorems 2 and 7 give 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, [30]) Let $\ell: G\to {\bf N}$ be a length function on a finitely generated group G. Then the following conditions hold:

(D1): $\ell(g)=\ell(g^{-1})$ for every $g\in G$ ; $\ell(g)=0$ if and only if g=1.
(D2): $\ell(gh)\le \ell(g)+\ell(h)$ for every $g,h\in G$ .
(D3): There exists a positive number c such that the cardinality of the set $\{g\in G\ \vert \ \ell(g)\le r\}$ does not exceed c^r for every $r\in {\bf N}$ .

Conversely for every group G and every function $\ell: G\to {\bf N}$ 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\to \vert g\vert _B$ is equivalent to $\ell$ .

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

Another problem by Gromov [19] 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 the 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,\dots,a_m\}$ . Let F_m be the free group generated by $A\cup A^{-1}$ . Every function $\ell: G\to {\bf N}$ can be naturally extended to a function $\ell^*: F_m\to N$ : for a word $w \in (A \cup A^{-1})^*$ , $\ell^*(w) = \ell( r(w) ) \in {\bf N}$ (where r(w) is the natural map from the free group onto G).

We say that $\ell$ is computable if $\ell^*$ is computable in the natural sense.

Theorem 9 (Olshanskii, [31]) Let $\ell$ be a computable function $G\to {\bf N}$ 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 $\ell$ .

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 one of the Gromov's problems from [19]. It turned out that such a characterization can be easily deduced from [30] and [31].

We say that a function $\ell: G\to {\bf N}$ satisfies condition (D4) if there exists a natural number n and a recursively enumerable set $S\subset F_m\times F_n$ such that

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

(b) $\ell^*(v)=\min(\{\vert u\vert\; \vert\ (v,u)\in S\})$ for every $v\in F_m$ .

Clearly it does not depend on the choice of generators of G whether $\ell$ 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 $\ell$ and some n, it also holds for $\ell$ and any natural number $n'\ge 2$ since there is an isomorphic embedding of F_ninto F_n'.

Theorem 11 (Olshanskii, [33]) Let G be a finitely generated subgroup of a finitely presented group H. Then the corresponding length function of G inside H satisfies conditions (D1)-(D4). Conversely, for every finitely generated group Gand every function $\ell: G\to {\bf N}$ satisfying conditions (D1)-(D4), there exists an embedding of G into a finitely presented group H such that the length function $g\mapsto \vert g\vert _H$ is O-equivalent to $\ell$ .

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 $\ell^*: F_m\to {\bf N}$ is the set $(w, \ell^*(w))\subseteq F_m\times N$ . A pair (w,k) is said to lie above the graph of $\ell^*$ if $\ell^*(w)\le k$ .

Theorem 12 (Sapir, [33]) Let G be a finitely generated group with decidable word problem. Then the function $\ell: g\mapsto \vert g\vert _H$ given by an embedding of G into a finitely presented group H satisfies conditions (D1)-(D3) and the following condition

(D4') The set of pairs above the graph of $\ell^*$ is recursively enumerable.

Conversely, for every function $\ell: G\to {\bf N}$ 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 $\ell$ .

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

Corollary 1 (1) Let g be an element of infinite order in a finitely presented group H with a generating set ${\cal B} = \{b_1,\dots,b_k\}$ . Denote $\ell(i)=\vert g^i\vert _{\cal B} =\vert g^i\vert$ for $i\in {\bf Z}$ . Then

(C1): $\ell(i)=\ell(-i)$ for $i\in {\bf Z}$ (l is symmetric), and $\ell(i)=0$ iff i=0;
(C2): $\ell(i+j)\le \ell(i)+\ell(j)$ for $i,j\in {\bf Z}$ (l is subadditive);
(C3): there is a positive number c such that $\,card\{i\in {\bf Z}\vert \ell(i)\le r\}\le c^r$ for any $r\in {\bf N}$ .
(C4): the set of integer pairs above the graph of $\ell$ is recursively enumerable.

(2) Conversely, for any function $\ell:\,{\bf Z}\rightarrow{\bf N}$ , satisfying the conditions (C1)-(C4), there is a finitely presented group H and an element $g\in H$ such that |gⁱ|_H is O-equivalent to $\ell(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 S. 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 {\bf N}$ 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 $\ell^*$ and only these pairs. Thus the set of pairs above the graph of $\ell^*$ 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 [31].

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 $\ell: G\to {\bf N}$ 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 $\ell$ .