The Rips Construction I

Given a finitely presented group {Q}, Rips constructed a hyperbolic group {G} and a surjection {p:G\twoheadrightarrow Q} with finitely generated kernel {N}. In this post and the next we will see how the Rips construction has been used to produce draconic subgroups of hyperbolic groups.

Besides the Rips construction, our main tool will be Higman’s Embedding Theorem: any recursively presented group embeds in some finitely presented group. (A recursive presentation is a presentation with a finte set of generators and a recursively enumerable set of defining relations.) Pathological behavior is embedded in a finitely presented group {Q} via this theorem, and pulled back to some hyperbolic group {G} via the Rips construction. As Bridson points out, Bieri has shown {N} is not finitely presented unless {Q} is finite, so that the Rips construction does not directly produce pathological finitely presented subgroups of nice groups. The 1-2-3 Theorem of Baumslag, Bridson, Miller, Short produces (under some conditions) finitely presented subgroups of {G\times G} as the pullback {\{(g_1,g_2)\in G\times G:p(g_1)=p(g_2)\}}. (Compare with the Mihailova construction in an upcoming blog post.)

1. Small Cancellation Groups

In his original paper, Rips constructed {G} as a small cancellation group. We will give a brief overview of the motivation for studying these groups. The theory of small cancellation groups is developed in Combinatorial Group Theory (Lyndon and Schupp) chapter 5. See also chapter 4 for a proof of the Higman Embedding Theorem.

Dehn exhibited an algorithm solving the word problem for fundamental groups of closed surfaces. Given a presentation {\langle\mathcal{A}|\mathcal{R}\rangle} of a group, the word problem asks if two words in {\mathcal{A}^\pm} represent the same group element, or equivalently it asks if a given word represents the trivial element. We will always assume that {\mathcal{R}} has been closed under the operations of inverses and cyclic conjugations. One can solve this problem for fundamental groups of closed hyperbolic surfaces by studying the geometry of the universal cover.

The universal cover of the standard presentation {\langle a,b|[a,b]\rangle} of the fundamental group of a torus is the plane tesselated by squares. Observe that any closed curve {\gamma} in the 1-skeleton encloses a square that has two consecutive edges (half its boundary) on {\gamma}. The universal cover of the standard presentation {\langle a_1,\ldots,a_g,b_1,\ldots,b_g|[a_1,b_1]\cdots[a_g,b_g]\rangle} of the fundamental group of a genus {g} surface, {g\geq 2}, is the hyperbolic plane tessellated by {4g}-gons. Since the circumference of a hyperbolic circle is an exponential function of its radius, the fundamental domains bubble out exponentially as we move outwards from a fixed domain. One may therefore expect (and it is true) that any closed curve {\gamma} in the 1-skeleton encloses a {4g}-gon for which more than half its boundary lies on {\gamma}. (In the picture below, imagine the boundary loop of the union of octagons sharing a vertex with the central octagon.)

This geometric observation suggests an algorithm for solving the word problem in hyperbolic surface groups. Dehn’s algorithm works as follows. Given a word {w}, search for a substring, {\gamma}, of {w} that is a prefix of a relator {r=\gamma\gamma'\in\mathcal{R}} with {|\gamma|>|r|/2}. (Remember, {\mathcal{R}} is closed under inverses and cyclic conjugation.) If no such substring exists, then {w} does not represent the identity element of {\langle\mathcal{A}|\mathcal{R}\rangle}. If we find such {\gamma}, replace it by {(\gamma')^{-1}} inside {w} to obtain a new shorter word representing the same element as {w}. Repeat.

Under the standard presentation, we have seen that fundamental domains of hyperbolic surface groups are polygons that intersect each other in at most a single edge. Small cancellation groups are groups with presentations satisfying certain combinatorial conditions that generalize this situation. Some of these small cancellation conditions force Dehn’s algorithm to work. The role of the region enclosed by a curve in the 1-skeleton of a hyperbolic tessellation is now played by van Kampen diagrams. A van Kampen diagram for a reduced word {w} representing 1 in {\langle\mathcal{A}|\mathcal{R}\rangle} is a finite planar graph {M} with vertices of valence at least 3, together with a distinguished vertex {P} on the boundary and with edges labelled by words in {\mathcal{A}^\pm} such that:

  • no edge word represents {1\in\langle\mathcal{A}|\mathcal{R}\rangle},
  • reading around each bounded region gives a relator (without cancellation)
  • reading around the boundary of {M} starting at {P} gives {w} (without cancellation)

Observe that an edge common to two bounded regions (or traversed twice along the periphery of a bounded region) must be labelled by a piece: a common prefix of two distinct elements of {\mathcal{R}}. A presentation is said to satisfy the small cancellation condition {C'(\lambda)} for some {\lambda>0\in\mathbb{R}} if every piece {\gamma} that is a prefix of a relator {r} has length less than {\lambda|r|}. If the pieces are small fractions of the relators for which they are prefixes, one can expect to see the same exponential bubbling of regions towards the boundary of {M} as with the hyperbolic surfaces. Indeed, Greendlinger’s Lemma, proved by studying the combinatorics of van Kampen diagrams and their duals, is stronger than the statement that every word representing a trivial element in a {C'(1/6)} presentation {\langle\mathcal{A}|\mathcal{R}\rangle} contains a substring that is more than half of a relator.

Therefore Dehn’s algorithm solves the word problem in {C'(1/6)} groups. The Dehn function {\delta(n)} in such a group consequently satisfies {\delta(n)\leq n}, so {C'(1/6)} groups are {\delta}-hyperbolic.

2. The Rips Construction

Theorem 1 Given any finitely presented group {Q=\langle a_1,\ldots,a_n|r_1,\ldots,r_m\rangle} and any real number {\lambda>0}, there is a {C'(\lambda)} group {G} and a short exact sequence

\displaystyle 1\rightarrow N\rightarrow G\stackrel{p}{\rightarrow}Q\rightarrow1

with {N} finitely generated.

The idea of the proof is to add two new generators {x,y} to the presentation of {Q} and suitable noise (words in {x,y}) to the desired relators so that the noise precludes much cancellation in the new presentation but disappears when {x,y} are mapped to {1}. Let

\displaystyle G=\langle a_1,\ldots,a_n,x,y|r_1*,\cdots,r_m*,a_i^{\pm1}xa_i^{\mp1}*,a_i^{\pm1}ya_i^{\mp1}*\rangle

where * represents a different long noise word every time it occurs. For example, the following words have little overlap:

  • {xyxy^2xy^3\cdots xy^{17}}
  • {xy^{18}xy^{19}xy^{20}\cdots xy^{34}}
  • {xy^{35}xy^{36}xy^{37}\cdots xy^{51}}
  • {\cdots}

It’s not too hard to generate algorithmically suitable noise words as a function of {\lambda} and the presentation.

The kernel {N} is normally generated by {x,y}. The conjugation relations make {\langle x,y\rangle} a normal subgroup of {G}, so that {N} is actually 2-generated.

3. First Applications

Rips produced the first applications of his construction to show that subgroups of small cancellation groups do not behave like subgroups of free groups:

Theorem 2 (Rips) There is a small cancellation group {G} such that:

  1. {G} has finitely generated subgroups whose intersection is not finitely generated.
  2. {G} has a finitely generated but not finitely presented subgroup
  3. The subgroup membership problem in {G} is not solvable. Indeed, there is a subgroup ({N}) for which there is no algorithm deciding whether a word in the generating set for {G} represents an element of the subgroup.
  4. {G} contains an infinite ascending chain of {r}-generated groups. ({r\geq3} fixed.)

The proof works by embedding recursively presented groups exhibiting the relevant behavior in a finitely presented group and applying the Rips construction. Using covering space theory, one shows that {\{b^iab^{-i}\}} is a free basis for the subgroup of the free group {F_2=\langle a,b\rangle} it generates. Therefore the amalgamated free product

\displaystyle \langle a,b,c,d|b^iab^{-i}=d^icd^{-i}, i\in\mathbb{Z}\rangle

of two copies of {F_2} along this subgroup has two finitely generated free subgroups {\langle a,b\rangle} and {\langle c, d\rangle} with infinitely generated intersection. Applying the Rips construction to a finitely presented group {Q} into which this recursively presented group embeds, one sees that {p^{-1}(\langle a,b\rangle)=\langle a,b,x,y\rangle} and {p^{-1}(\langle c,d\rangle)} are 4-generated, but {p^{-1}(\langle a,b\rangle\cap\langle c,d\rangle)} is not finitely generated.

Parts (2)-(4) are proved similarly. (2) uses a finitely generated, recursively presented but not finitely presented group, such as the Lamplighter group. (3) uses a recursively presented group with unsolvable word problem (for instance

\displaystyle \langle a,b,c,d|b^iab^{-i}=d^icd^{-i}, i\in S\rangle,

where {S} is recursively enumerable but not recursive). (4) uses a finitely presented group with an ascending chain of 1-generated subgroups, such as the Baumslag-Solitar group {BS(1,2)=\langle t,a|ta^2t^{-1}=a\rangle}.

Observe that one can obtain a group {G} exhibiting all these pathologies simultaneously by simply taking {Q} to be the direct product presentation of various finite presentations that would produce the various pathologies individually.

4. Isomorphism problem for hyperbolic groups

The isomorphism problem seeks an algorithm to decide whether two presentations from among some class of groups represent isomorphic groups. Until recently, the isomorphism problem for hyperbolic groups was open. Baumslag, Miller, and Short used the Rips construction to suggest that the isomorphism problem is difficult.

Recall that the rank of a group is the minimum number of elements needed to generate it. Grushko’s Theorem says that the rank of a free product of groups is the sum of the ranks of the free factors. Baumslag, Miller and Short proved that for any {k\geq 3}, there is no algorithm that given any presentation for a hyperbolic group known to have rank either 2 or {\geq k} can determine which is the case. If rank is impossible to detect, they argue, then it should be difficult to tell if two groups are isomorphic.

One proves their theorem as follows. Given a finitely presented group {Q}, apply the Rips construction to a free product of {k} copies of {Q}. If {Q} does not represent the trivial group, Grushko’s Theorem implies that the resulting group {G} has rank at least {k}. On the other hand, if {Q} represents the trivial group, then {G=N} is 2-generated. If one could solve the isomorphism problem for the stated class of groups, then one could determine if any given finite presentation represents the trivial group, which is impossible.

Advertisements

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:

WordPress.com Logo

You are commenting using your WordPress.com 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