Read an Excerpt
Computers, Rigidity, and Moduli
The Large-Scale Fractal Geometry of Riemannian Moduli Space
By Shmuel Weinberger Princeton University Press
Copyright © 2004 Princeton University Press
All right reserved. ISBN: 978-0-691-11889-5
Chapter One
Group Theory
It is not surprising, given the syntactical nature of arguments in logic and in combinatorial group theory, that one of the earliest examples of a natural, widely studied, mathematical problem to be shown algorithmically unsolvable lies in group theory. Our unsolvability (and dichotomy) results in topology and geometry will come about by encoding group theory into these subjects, which will be done in chapter 2. The goal of this chapter is to provide the necessary background in group theory.
This subject contains a number of deep theorems. Some of the highlights of this part are:
the unsolvability of the word problem by Novikov and Boone, and the triviality problem by Adian and Rabin (section 1.2);
Higman's embedding theorem (section 1.2);
the recent work of Sapir with Birget and Rips on Dehn functions (section 1.3);
the results of Borel-Wallach and of Clozel on the cohomology of arithmetic groups (section 1.5);
the theorems of Baumslag and Dyer with Heller and Miller on the group homology of finitely presented groups (section 1.6).
1.1 PRESENTATIONS OF GROUPS
Let G be a group. G is said to be finitely generated if there are finitely many elements [g.sub.1], [g.sub.2, ..., [g.sub.k] such that every element of G is a product of these elements (many times) and their inverses. All finitely generated groups are countable, but the rational numbers give an example of a nonfinitely generated countable group.
Note that saying that G is finitely generated is exactly the same thing as saying that there is a surjection from a free group [F.sub.k] [right arrow] G for some k. We say that a subgroup H of G is finitely normally generated if there is a finite set S such that H is the smallest normal subgroup of G containing S. Alternatively, the elements of H are products of things of the form [gsg.sup.-1], where s is from S, and g lies in G.
The group G is finitely presented if there is a surjection [F.sub.k] [right arrow] G whose kernel is finitely normally generated. A set R which normally generates the kernel is called a set of relations for G. One uses the notation
G = <[g.sub.1], [g.sub.2], ..., [g.sub.k] | [r.sub.1], [r.sub.2], ..., [r.sub.s]>,
where the r's are a list of the elements of R. The r's should be thought of as being words in the g-letters. One can easily show that the kernel of one surjection of a free group to G is finitely normally generated iff it is for any other surjection. Using this, one can show, for instance, that the following group is not finitely presented:
<x, y | [x, [x.sup.a] [yx.sup.-a]] where a = 0, 1, 2, 3, ...> = [??] [??] [??],
where [g, h] = [ghg.sup.-1][h.sup.-1] is the commutator of g and h, and [??] denotes the wreath product (for those familiar with this concept; we will never have any use for it).
One thinks of the finite presentation as giving the group defined by these generators, subject to the given set of relations (like an axiomatic system). The word problem asks one to give an algorithm for deciding whether a combination of generators represents the trivial element of G; in other words, whether a certain potential relation is a consequence of the relations that are already part of the set R. (Again, this is a property of a group, not of the way the group is presented.) We will discuss the word problem in the next section.
Remark. It is not at all easy to tell if two finite presentations define the same group. The Tietze theorem asserts that two presentations define the same group iff there is a sequence of elementary moves (and their inverses) that relate the two presentations. The first move adds a new generator and a new relation that defines the generator in terms of the old ones, for example,
<x, y |> = <x, y, z | z = [xyx.sup.-215] [y.sup.12]x>.
(We use the convention that a relation of the form r = s is just a user friendly way of writing [rs.sup.-1].) The second move allows one to add a relation that is a "consequence" (i.e., that lies in the normal closure) of the others. So
<x, y | yx = xy> = <x, y | yx = xy, xyxy = yxyx>.
These moves always increase the complexity of presentations, but that means that their inverses can decrease complexity. We will see that relating two "simple presentations" by Tietze moves could involve going through very complicated intermediate presentations. (We will never really need the Tietze theorem, but it will sometimes be useful for illustration purposes.)
Besides their natural logical interest, finitely presented groups occur extremely naturally throughout mathematics. Probably the simplest, general sources of these are fundamental groups of compact manifolds and arithmetic groups (or more general lattices in real Lie groups).
The reason that compact smooth manifolds have finitely presented fundamental groups is because they are all homeomorphic to finite polyhedra (= finite simplicial complex) by a relatively difficult theorem of Cairns and Whitehead (CW), or by Morse theory, which, at least, shows that they are homotopy equivalent to finite CW complexes.
Given a finite CW complex or simplicial complex one can very simply write down a presentation of the fundamental group. The 1-skeleton is always homotopy equivalent to a wedge of circles; the 2-cells of the 2-skeleton then give the relations. The proof of this description goes by way of van Kampen's theorem, which describes the fundamental group of the union of two spaces that intersect "nicely." To describe the answer, we shall need the constructions of "amalgamated free product" and "HNN extension."
Definition. Let A, B, and ITLITL be groups, and let ITLITL be a subgroup of both A and B. A [*.sub.C] B is the group defined to have the universal property that A and B both map to A [*.sub.C] B, and if f : A [right arrow] D and g : B [right arrow] D are homomorphisms that agree on ITLITL, then there is a unique extension of f and g to a map A [*.sub.C] B [right arrow] D.
General nonsense implies that A [*.sub.C] B is unique (up to canonical isomorphism) if it exists. To construct it, we can give a formula. Suppose A = <[a.sub.1], [a.sub.2], ... | [r.sub.1], [r.sub.2], ...>, B = < [b.sub.1], [b.sub.2], ... | [s.sub.1], [s.sub.2], ...>, and ITLITL is generated by [c.sub.1], [c.sub.2], ... As ITLITL is a subgroup of both A and B, we can write [c.sub.1] = [c.sub.1] (a's) and [c.sub.1] = [c.sub.1] (b's), [c.sub.2] = [c.sub.2] (a's) and [c.sub.2] = [c.sub.2] (b's), etc. Now
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(Note that actually one needs only a homomorphism from ITLITL into both A and B for the definition and universal property to make sense. The universal property is helpful for a conceptual understanding of why the amalgamated free product is independent of all the choices involved.) With this preparation, we can state van Kampen's theorem.
Van Kampen's theorem
If two spaces with fundamental groups A and B intersect along a connected space with a fundamental group ITLITL, then their union has the fundamental group A [*.sub.C] B.
The HNN extension is a natural analogue of the amalgamated free product, and comes up in determining the fundamental group of a union when the intersection is not connected.
Definition. Let A be a group and [B.sub.j], j = 1, 2, isomorphic subgroups (let [empty set] be the isomorphism). Then the HNN extension [A.sup.*.sub.B] is defined by the universal property that, if f : A [right arrow] D is a homomorphism which restricts to conjugate maps on the two copies of B, then it extends uniquely to [A.sup.*.sub.B]. In terms of generators and relations, the formula is
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
with the obvious notation.
If one glues a cylinder Y x I whose fundamental group is B along both of its ends to a space with fundamental group A, then one gets into a situation where the HNN extension is defined. Indeed, the fundamental group of this union is the HNN extension.
Exercise
Show that van Kampen's theorem together with the above addendum for cylinders together suffice to deal with all unions of polyhedra along subpolyhedra.
It is worth noting that these constructions can behave quite oddly when the "subgroups" are really groups with homomorphisms with nontrivial kernels. For instance, if we consider [[??].sub.2] and [[??].sub.3] amalgamated "along" [??] which maps surjectively to both groups, one obtains the trivial group.
On the other hand, if all of the "inclusions" are really injections, then A automatically injects into A [*.sub.C] B and into [A.sup.*.sub.B]. In fact, there is quite a natural normal form for elements in the amalgamated free product and HNN extension, given a choice of coset representatives for the subgroup. In the next section we will make extensive use of these constructions, and, in particular, this injectivity statement.
The proof of this and several of the other basic theorems of combinatorial group theory can be written down in a completely opaque combinatorial fashion, but are actually quite transparent from a geometric point of view.
Definition. A graph of groups is a graph [GAMMA] such that each vertex v is associated a group [G.sub.v] and each edge is assigned [G.sub.e]. For each of the two inclusions of endpoints u, v in an edge e, there are given injections [G.sub.e] [right arrow] [G.sub.u] and [G.sub.e] [right arrow] [G.sub.v].
Notice that an edge can have both endpoints being the same vertex, in which case one has a group with two isomorphic subgroups. Thus, the data for an edge are exactly the data necessary for defining amalgamated free products or HNN extensions. For any connected graph, one can then inductively define, using amalgamated free products or HNN extensions on individual vertices, the fundamental group of the graph of groups. If all the vertex and edge groups are trivial, this is just the fundamental group of the graph.
One could define this notion in a less ad hoc way by an appropriate universal property; we leave this for the reader. One can also see that it is the fundamental group of a union of spaces, which overlap only in pairs, and that "fit together" according to the pattern of the graph (vertices corresponding to spaces, and edges to overlaps) and with the fundamental groups of every piece determined by the labels on the graph.
The following proposition gives a connection between group actions on trees and graphs of groups.
Proposition If a groupGacts simplicially on a tree T without inversions (i.e., invariant edges are fixed), then the quotient T/G is a graph of groups, with fundamental group G, wherewith each vertex or edge is associated its stabilizer. Conversely, every graph of groups comes from an action of its fundamental group.
The proof is little more than covering space theory. Note that, as a consequence, A injects into A [*.sub.C] B, since the latter group acts on a tree, with A and B as vertex groups and ITLITL as the edge group. Similarly, A injects into the HNN extension [A.sup.*.sub.B] because the latter also acts on a tree with A as a stabilizer subgroup for a vertex. Here are some other corollaries:
1. Subgroups of free groups are free. (Freeness is equivalent to having a free action on a tree; free actions restricted to subgroups remain free.)
2. Exercise: Show that any subgroup of finite index in a nonabelian free group is a free group of higher rank. Show that the commutator subgroup of a nonabelian free group is a free group of infinite rank. What are its generators?
3. Generalized Kurosh subgroup theorem: Any subgroup of a graph of groups is a graph of groups where the edge and vertex groups are subgroups of the original vertex and edge groups.
The usual Kurosh theorem corresponds to free products, that is, where edge groups are trivial, so for the subgroup all edge groups are also trivial, so that the fundamental group is a free product of subgroups of the free factors and free groups.
Exercise
Supposing that G and H are nontrivial groups, not both [[??].sub.2], show that G * H contains a free group of rank 2.
1.2 PROBLEMS ABOUT GROUPS
Now let us return to the theory of group presentations. Recall that the word problem for a finitely presented group is to determine when a word represents the trivial element.
Example 1 Finite groups have a solvable word problem. (Use their multiplication tables.)
So do finitely presented residually finite groups, that is, groups G with enough homomorphisms to finite groups to catch any nontrivial element. (In other words, each nontrivial element g of G is mapped nontrivially by some homomorphism of G into a finite group.) The proof of this goes as follows. Start two machines going. The first lists elements of the normal closure of R systematically (i.e., going though the elements of G to get many conjugates of the elements of R, and taking many products of these) and checks to see if the given word occurs. If this happens, the machine yells "w is trivial." The second machine lists all homomorphisms from G into any finite group (why is this algorithmic?) and then checks if the word is mapped trivially. If it is not, this machine yells "w is nontrivial." Clearly only one of these will happen, and if G is residually finite, one of them will.
One could want to know a bound on how long it would take an algorithm to determine if w is trivial. In general, it could be quite bad.
Another example is the free group, where the algorithm is quite simple; one just looks for appearances of symbols like [xx.sup.-1] within the word, and removes these. When one is done, one has a reduced word, and every group element has only one expression as a reduced word. This is an extremely fast algorithm. (It is linear in the length of the word.) There is a large and rich class of groups with a linear time solution to the word problem (subgroups of products of hyperbolic groups in the sense of Gromov; see the references), but I do not know of many general theorems for them.
Nowadays, there are even examples of finitely presented solvable groups with unsolvable word problems! But this is running ahead in our story. The wonderful theorem of Boone and (P. S.) Novikov is simply the following:
Theorem There are finitely presented groups with an unsolvable word problem.
We will not even sketch the proof here. The overall idea is to encode a Turing machine into a finite presentation (using a series of amalgamated free products and HNN extensions) so "the normal form theorem" (for elements of an amalgamated free product or HNN extension) implies that the only way that a word will be trivialized is via the appropriate computation of the Turing machine. That, the construction, and the proof that it works, will give you the theorem. A number of refinements and extensions will be of importance to us later. We will get to these.
(Continues...)
Excerpted from Computers, Rigidity, and Moduli by Shmuel Weinberger Copyright © 2004 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
