Fibre products and the membership problem

Baumslag, Bridson, Miller and Short (BBMS) provide criteria for what they call the fibre products to be finitely presented. They then leverage these results to show that, amongst other things, there exists a torsion-free hyperbolic group {G} with a fibre product subgroup {P}, such that the membership problem for {P} in {G} is undecidable. To connect this to our pursuit of the distortion functions of finitely generated subgroups, we recall that a finitely generated subgroup {H} of a finitely generated group {G} (with solvable word problem) has a solvable membership problem if and only if the distortion function of {H} in {G} is bounded above by a recursive function.

Theorem 1. There exists a torsion free word hyperbolic group {\Gamma} and a finitely presented subgroup {P< \Gamma\times\Gamma} such that there is no algorithm to decide membership of {P} and the conjugacy problem of {P} is unsolvable. Additionally, {\Gamma} can be chosen to be the fundamental group of a compact negatively curved 2-complex.

The group {\Gamma\times\Gamma} has a solvable conjugacy problem (Gersten-Short).

1. Fibre products

The central construction of BBMS is similar to the Mihailova construction we’ve covered before. To any short exact sequence

\displaystyle  1 \rightarrow N \rightarrow \Gamma \stackrel{p}{\rightarrow} Q \rightarrow 1. \ \ \ \ \ (1)

we have the associated fibre product {P<\Gamma\times\Gamma} where

\displaystyle  P=\{(g_1,g_2)\ |\ p(g_1)=p(g_2)\}. \ \ \ \ \ (2)

If {Q} is finitely presented and {\Gamma} is finitely generated then {P} is finitely generated. We can think of {P} as the graph of the relation {=_Q}, and so questions about equality in {Q} are questions about membership of {P}.

When {\Gamma} is free and {Q} is finitely presented with undecidable word problem, {P} has many undecidable properties (Miller), but {P} will generally not be finitely presented in this case (see the Mihailova construction). Using a refined version of the Rips construction, encapsulated by the following theorem, allows one to get finitely presented {P}.

1-2-3 Theorem. Suppose

\displaystyle  1 \rightarrow N \rightarrow \Gamma \stackrel{}{\rightarrow} Q \rightarrow 1. \ \ \ \ \ (3)

is exact, and let {P} be the associated fibre product. If {N} is finitely generated (type {F_1}), {\Gamma} is finitely presented ( type {F_2}), and {Q} is of type {F_3}, then {P} is finitely presented.

1.1. Type {F_3} and {\pi_2}

The major conceptual underpinning of Theorem 1 is a connection between type {F_3} and {\pi_2}. Let {X} be an Eilenberg-Maclane space for {Q} with finite 3-skeleton. We will assume that {X} has a single vertex. This means that its 2-skeleton, {X^{(2)}}, can be identified with to a finite presentation {\mathcal{P}_X} of {Q} whose generators are given by the 1-cells and whose relations are given by the attaching maps of 2-cells in {X^{(2)}}. Since {\pi_2\mathcal{P}_X:=\pi_2X^{(2)}} is finitely generated as a {Q}-module, {X^{(3)}} is finite. This can be seen by taking the attaching maps of the 3-cells as the generators of the module. This identification allows one to find a nice presentation for {\Gamma} and thus a nice presentation for {P}.

Obtaining this presentation is rather technical and takes a major portion of BBMS, and we omit the details. However, we will sketch their approach. Let {\mathcal{P}=\langle \mathcal{X}\ |\ \mathcal{R}\rangle} be a presentation for a group {G}. Let {\sigma=(c_1,..,c_m)} be a sequence of words of the form {c_i=w_ir_iw_i^{-1}} where {r_i\in \mathcal{R}^{\pm1}} and {w_i} is some word over {\mathcal{X}}. We call such a sequence an identity sequence if {\mathcal{P}rod c_i} is freely equal to the empty word in {F(\mathcal{X})}. An equivalence relation is given on identity sequences, and we consider the action of {F(\mathcal{X})} on these sequences given by {w\cdot(c_1,..,c_m)=(wc_1 w^{-1},...,wc_m w^{-1})}. This action naturally induces a {G}-action on the equivalence classes of identity sequences. We can view the identity sequences equipped with this action as a {G}-module is isomorphic to {\pi_2\mathcal{P}}. Thus {\pi_2\mathcal{P}} being finitely generated as a {G} module means that there is a finite set of identity sequences such that any identity sequence can be reduced under the equivalence relation to finitely many of these sequences in this set. This identification can then be used to determine a presentation for {\Gamma} entirely from the presentations of {N} and {Q}.

2. Proof of Theorem 1

Theorem 1 relies on an extension of the enhanced Rips construction.

Theorem 3 (Modified Rips Construction). There is an algorithm that associates to any finite group presentation {\mathcal{Q}}, a compact, negatively curved, piecewise hyperbolic 2-dimensional complex {K} and a short exact sequence

\displaystyle  1 \rightarrow N \rightarrow \Gamma \rightarrow Q \rightarrow 1, \ \ \ \ \ (4)

such that

  1. {\mathcal{Q}} presents the group {Q},
  2. {K} has a single vertex {x_0},
  3. the 2-cells of {K} are right angled hyperbolic pentagons (each side of which crosses several 1-cells),
  4. {\Gamma=\pi_1(K,x_0)},
  5. {N} has a finite generating set {A} of cardinality at least 2,
  6. each of the 1-cells in {K} is the unique closed geodesic in its homotopy class,
  7. the homotopy class of each {a\in A} is represented by one of the 1-cells of {K},
  8. {G} is torsion-free,
  9. and each {a\in A} generates its centralizer.

The first seven items follow from a construction in Bridson-Haefliger and Wise. Item (8) comes from the fact that the fundamental group of any compact non-positively curved space is torsion free. Item (9) follows from (7). {\Gamma} is hyperbolic and torsion free, so the centralizer of every non-trivial element in {\Gamma} is cyclic. Thus, if {a} were a proper power, its homotopy class would not correspond to a simple closed geodesic.

Theorem {1} follows from the next result.

Theorem 4. There exists a compact negatively curved 2-complex {K} and a finitely presented subgroup {P<\pi_1(K\times K)=\Gamma\times\Gamma} such that

  1. the membership problem for {P} is unsolvable, and
  2. {P} has unsolvable conjugacy problem.

This theorem utilizes the existence of groups of type {F_3} with unsolvable word problems. Collins and Miller constructed a group {Q} with a finite 2-dimensional {K(Q,1)} and unsolvable word problem. The enhanced Rips construction is applied to to {Q} for {\Gamma=\pi_1K}, where {K} is a compact negatively curved 2-complex.

Following the notation of the Rips construction, take {\{x_1,..,x_n,a_1,..,a_m\}} where {a_i\in A} and the {x_i} are lifts of generators of {Q}. We take {\{(x_i,1),(1,x_i),(a_j,1),(1,a_j)\}} for a generating set for {\Gamma}. The 1-2-3 Theorem implies that the fibre product {P} is finitely presented.

To see that the membership problem for {P} is unsolvable we restrict to specific words. A word on the generators {(x_i,1)} is in {P} if and only if the same word in the {x_i} is equivalent to the identity in {Q}. Thus the unsolvability of the word problem for {Q} implies the unsolvability of the membership problem for {P}.

The unsolvability of the conjugacy problem follows from the next lemma.

Lemma 5 Let {H<P<G} be finitely generated groups. Suppose {H\lhd G} and there exists {a\in H} such that {C_G(a)<P}. If there is no algorithm to decide membership of {P}, then {P} has an unsolvable conjugacy problem.

The thrust of the lemma is that, given a word in {G}, we consider {waw^{-1}} where {a} is a generator of {H}, and this word being conjugate to {a} in {P} is equivalent to {w} being in {P}. This lemma is applied with {H=N\times N}, as item (9) of Theorem 3 tells us that the centralizer of {(a_i,a_i)} is {\langle (a_i,1),(1,a_i)\rangle}, and thereby gives us unsolvability of the conjugacy problem.

3. Isomorphism problem

BBMS also addressees the isomorphism problem for subgroups of fundamental groups of non-positively curved spaces. These results take us away from subgroup distortion, but are worth noting for their own sake.

Corollary of Modified Rips construction. Let {K,\ \Gamma} and {A} be as above. Let {a\in A}. Then {\hat\Gamma=\langle\Gamma,t\ |\ t^{-1}at=a\rangle} is the fundamental group of a compact non=-positively curved squared complex, and is thus biautomatic (Niblo-Reeves).

Proof: Re-metrize {K} by subdividing each pentagonal face by introducing a new vertex in the middle of each face and side and using these to break the pentagons into hyperbolic quadrilaterals. These quadrilaterals are replaced by Euclidean squares without changing side length. The resulting space is still non-positively curved and the original 1-cells are still geodesics. We refine these squares until their side lengths are half that of the original 1-cells in {K}. We attach an annulus (union of two Euclidean squares) by gluing the boundary circles to the loop representing {a} by an isometry. \Box

Theorem 7. There exists a non-positively curved 4-dimensional complex {K} with biautomatic fundamental group {G}, and a (countable) recursive class of finitely presented subgroups {H_n<G} such that there is no algorithm to determine whether or not {H_n} is isomorphic to {H_1}.

The group in this theorem is a direct product {\hat\Gamma \times \Gamma} where {\Gamma} is a torsion free word hyperbolic group and {\hat\Gamma} is an HNN-extension of {\Gamma} given by {\langle \Gamma,\tau\ |\ \tau^{-1}a_1\tau=a_1\rangle} where {a_1\in\Gamma} generates a maximal cyclic subgroup.

Corollary 8. There exists a non-positively curved manifold of dimension 9 and a recursive class of finitely presented subgroups of {\pi_1M} such that there is no algorithm to determine homotopy equivalence between covering spaces corresponding to these subgroups.


About berstein

berstein is the name under which participants in the Berstein Seminar - a mathematics seminar at Cornell - are blogging.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s