Groups with Word Problem in NP, and Higman Embeddings

The well known Higman embedding 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 [7])   Let G be a finitely generated group with word problem solvable by a non-deterministic Turing machine with time function $\le T(n)$ such that T(n)⁴ is superadditive. Then G can be quasi-isometrically embedded into a finitely presented group H with isoperimetric function equivalent to n²T(n²)⁴. 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 ${\bf Q}$. 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 ${\bf Q}$ or ${\bf Z}/p{\bf Z}$ is solvable in polynomial time,
• Polycyclic groups because they are representable by matrices over fields [39], [36].
• Arbitrary finitely generated metabelian groups because they are representable by matrices over finite direct products of fields [36], [24], [40].
• Automatic groups (in particular, hyperbolic groups) [11],
• Groups of piecewise linear transformations of a line with finitely many rational singularities (including the R. Thompson group F) [9],
• Every finitely generated subgroup of a diagram group [20],
• Every free Burnside group B(m,n) for sufficiently large odd exponent n (see, for example, Storozhev's argument in Section 28 of [28]).

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 finitely generated free group in the variety of all solvable groups of a given class has word problem in P.

Gromov proved in [19] that every finitely presented group with a simply connected asymptotic cone has polynomial Dehn function, so it has word problem in NP. Papasoglu proved in [35] [35] that every group with quadratic Dehn function has simply connected asymptotic cone. Nevertheless not every finitely presented group with polynomial Dehn function has a simply connected asymptotic cone because if the cone is symply connected then the group has a linear isodiametric function, and Theorem 3 allows one to construct lots of groups with polynomial Dehn functions which cannot have linear isodiametric functions. It is an open question whether polynomial Dehn function and linear isodiametric function imply that the cone is simply connected.

It is an interesting question whether the class of groups with word problem in NP 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 [38] 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.

The class of finitely presented groups with polynomial Dehn functions is, by Theorem 14, the ``universal" subclass of the class of all groups with word problem in NP.

An example of an embedding of one group into another where lengths are not distorted but areas are distorted can be found in Gersten [15]. Some examples of groups with big Dehn functions embeddable into groups with small Dehn functions can be found in Madlener, Otto [26] and Baumslag, Bridson, Miller and Short [4]. Our results show that any recursively presented finitely generated group can be embedded into a finitely presented group with linear 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 Gcannot be smaller than the non-deterministic 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²T(n²)⁴ (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+\epsilon}$ for every $\epsilon>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 [6].

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

In 1976, D. Collins asked (see [10] or [22] Problem 5.22) if there exists a version of the Higman embedding theorem which preserves the degree of unsolvability of the conjugacy problem. He proved in [10] that the original Higman embedding and several later modifications of it do not preserve solvability of the conjugacy problem. For example, if a finitely group C has undecidable power problem (given two elements $a,b \in C$, decide whether a is a power of b) then the finitely presented group obtained by using the Higman construction will automatically have undecidable conjugacy problem, and it is relatively easy to find a finitely generated group with decidable conjugacy problem and undecidable power problem. At the end of his paper, Collins wrote that new ideas should be found to construct a variant of the Higman embedding preserving solvability of the conjugacy problem, and that ``For the present the most that can be hoped for is isolation of the conditions on C that are necessary and sufficient for the preservation of the solvability of the conjugacy problem in the Higman embedding."

We managed to show that the answer to Collins' questionis is ``yes".

Theorem 15 (Olshanskii, Sapir [34])   Every finitely generated group with solvable conjugacy problem is embeddable into a finitely presented group with solvable conjugacy problem. Moreover, every finitely generated recursively presented group G can be embedded into a finitely presented group H in such a way that the degree of unsolvability of the conjugacy problem in H coinsides with the degree of undecidability of the conjugacy problem in G.  

The construction in the proof of this theorem is complicated and employs ideas of three previous papers [38], [31], [7]. This theorem has the following interesting corollary. It gives a partial answer to another Collins' problem (see [22], Problem 5.21) which asked whether every torsion-free group with solvable word problem is embeddable into a group with solvable conjugacy problem. Recall that for every group the order problem asks what is the order of a given element in this group.

Theorem 16   Every countable group with solvable power and order problems is embeddable into a finitely presented group with solvable power, order and conjugacy problems.

So far we are unable to replace the power problem by the word problem in Theorem 16. It is clear that the power problem is stronger than the word problem (an element is a power of the identity element if and only if it is equal to the identity element). On the other hand, the order problem is clearly solvable in very torsion-free problem. So in the torsion-free case one can drop the condition that the order problem is solvable. Thus Theorem 16 implies that any torsion-free group with solvable power problem can be embedded into a finitely presented group with solvable power and conjugacy problem (the larger group will be also torsion-free in this case). In the case when the initial group might have torsion, the solvability of the order problem is essential because it is easy to costruct a finitely generated group with solvable power problem but unsolvable order problem, which is not embeddable into any group with solvable conjugacy problem (hint: conjugated elements must have the same order).

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,...,a_m\}$ and exponent n. This group is very complicated and in particular not finitely presented if $m\ge 2$ and n is odd and $\ge 665$ (Adian, [2]). 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ⁿ=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ⁿ=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₁uq₂uq₃)=k₁(uq₁uq₂uq₃)k₂(uq₁uq₂uq₃)'k₃....k_N(uq₁uq₂uq₃)^(N)

for every word u in the alphabet $\{a_1,...,a_m\}$. Here N is a sufficiently large number (28 is enough), k₁,...,k_N, q₁,q₂, q₃ are new letters, and the words between consecutive k's are copies of uq₁uq₂uq₃ 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₁uq₂uq₃).

Fig. 3.

On the boundary of this diagram we have the word K(uq₁uq₂uq₃). The words on each of the concentric circles is labeled by K(u_iq₁u_iq₂u_iq₃)where u_i is a prefix of u of length i-1. The word written on the innermost circle is K(q₁q₂q₃). This word will be called the hub. The edges connecting the circles are labeled by letters r₁,...,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,...,m.
• ar=ra, $a\in \{a_1,...,a_m\}$, $r\in \{r_1,...,r_m\}$
• kr=rk, $k\in\{k_1,...,k_N\}$, $r\in \{r_1,...,r_m\}$.

plus N copies of each of these relations written in N disjoint alphabets. These relations plus the hub relation K(q₁q₂q₃) 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,...,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:

in

Fig. 4.

This is an annular diagram. The hole of it has label u_bⁿ (u_b is the word u rewritten in the alphabet $\{b_1,...,b_m\}$). The boundary label of the disc is K(uq₁uq₂uq₃), the label of the external boundary of the diagram is also K(uq₁uq₂uq₃). 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\in\{k_1,...,k_N\}$.
• $\rho q= q\rho$ for every $q\in \{q_1,q_2,q_3,...,q_3^{(N)}\}$.
• $\rho a=a\rho$ for every a from the N copies of $\{a_1,...,a_m\}$.
• $a^\rho=ab$ for every $a\in \{a_1,...,a_m\}$.
• ab=ba for every $a\in \{a_1,...,a_m\}$ and $b\in \{b_1,...,b_m\}$.
• q_ib=bq_i for every $b\in \{b_1,...,b_m\}$, i=1,2,3.

Since the label of the external boundary is K(uq₁uq₂uq₃), we can glue in a disc with this label, and make our annular diagram into an ordinary diagram with boundary label u_bⁿ. 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 17 (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+\epsilon}$ provided n is odd and $\ge 10^{10}$; $\lim_{n\to \infty} \epsilon=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 Ghas polynomial verbal isoperimetric function. This function is defined as follows:

Let v(x₁,...,x_n) be a word. Suppose that w is in the verbal subgroup vsg(v). Then $w=\prod_i v(X_{1,i},...,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+\epsilon}$ ( $\lim_{n\to \infty} \epsilon=0$). This can be proven by modifying Storozhev's argument from [28] (Storozhev's argument gives estimate n⁴ 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¹⁰.