IV Topics in Geometric Group Theory (Full)

Part IV — Topics in Geometric Group Theory

Based on lectures by H. Wilton

Notes taken by Dexter Chua

Michaelmas 2017

These notes are not endorsed by the lecturers, and I have modified them (often

significantly) after lectures. They are nowhere near accurate representations of what

was actually lectured, and in particular, all errors are almost surely mine.

The subject of geometric group theory is founded on the observation that the algebraic

and algorithmic properties of a discrete group are closely related to the geometric

features of the spaces on which the group acts. This graduate course will provide an

introduction to the basic ideas of the subject.

Suppose Γ is a discrete group of isometries of a metric space

. We focus on the

theorems we can prove about Γ by imposing geometric conditions on

. These

conditions are motivated by curvature conditions in differential geometry, but apply

to general metric spaces and are much easier to state. First we study the case when

is Gromov-hyperbolic, which corresponds to negative curvature. Then we study

the case when

is CAT(0), which corresponds to non-positive curvature. In order

for this theory to be useful, we need a rich supply of negatively and non-positively

curved spaces. We develop the theory of non-positively curved cube complexes, which

provide many examples of CAT(0) spaces and have been the source of some dramatic

developments in low-dimensional topology over the last twenty years.

Part 1.

We will introduce the basic notions of geometric group theory: Cayley graphs,

quasiisometries, the Schwarz–Milnor Lemma, and the connection with algebraic

topology via presentation complexes. We will discuss the word problem, which

is quantified using the Dehn functions of a group.

Part 2.

We will cover the basic theory of word-hyperbolic groups, including the Morse

lemma, local characterization of quasigeodesics, linear isoperimetric inequality,

finitely presentedness, quasiconvex subgroups etc.

Part 3.

We will cover the basic theory of CAT(0) spaces, working up to the Cartan–

Hadamard theorem and Gromov’s Link Condition. These two results together

enable us to check whether the universal cover of a complex admits a CAT(1)

metric.

Part 4.

We will introduce cube complexes, in which Gromov’s link condition becomes

purely combinatorial. If there is time, we will discuss Haglund–Wise’s special

cube complexes, which combine the good geometric properties of CAT(0) spaces

with some strong algebraic and topological properties.

Pre-requisites

Part IB Geometry and Part II Algebraic topology are required.

Contents

1 Cayley graphs and the word metric

1.1 The word metric

1.2 Free groups

1.3 Finitely-presented groups

1.4 The word problem

2 Van Kampen diagrams

3 Bass–Serre theory

3.1 Graphs of spaces

3.2 The Bass–Serre tree

4 Hyperbolic groups

4.1 Definitions and examples

4.2 Quasi-geodesics and hyperbolicity

4.3 Dehn functions of hyperbolic groups

5 CAT(0) spaces and groups

5.1 Some basic motivations

5.2 CAT(κ) spaces

5.3 Length metrics

5.4 Alexandrov’s lemma

5.5 Cartan–Hadamard theorem

5.6 Gromov’s link condition

5.7 Cube complexes

5.8 Special cube complexes

1 Cayley graphs and the word metric

1.1 The word metric

There is an unfortunate tendency for people to think of groups as being part

of algebra. Which is, perhaps, reasonable. There are elements and there are

operations on them. These operations satisfy some algebraic laws. But there is

also geometry involved. For example, one of the simplest non-abelian groups

we know is

, the group of symmetries of a triangle. This is fundamentally a

geometric idea, and often this geometric interpretation can let us prove a lot of

things about D

In general, the way we find groups in nature is that we have some object,

and we look at its symmetry. In geometric group theory, what we do is that we

want to remember the object the group acts on, and often these objects have

some geometric structure. In fact, we shall see that all groups are symmetries of

some geometric object.

Let Γ be a group, and

a generating set for Γ. For the purposes of this

course,

will be finite. So in this course, we are mostly going to think about

finitely-generated groups. Of course, there are non-finitely-generated groups out

there in the wild, but we will have to put in some more effort to make our ideas

work.

The simplest geometric idea we can think of is that of distance, i.e. a metric.

So we want to use our generating set S to make Γ into a metric space.

Definition

(Word length)

Let Γ be a group and

a finite generating set. If

γ ∈ Γ, the word length of γ is



(γ) = min{n : γ = s

±1

· · · s

±1

for some s

∈ S}.

Definition

(Word metric)

Let Γ be a group and

a finite generating set. The

word metric on Γ is given by

(γ

, γ

) = 

(γ

−1

If we stare at the definition, we see that the word metric is left-invariant, i.e.

for any g, γ

, γ

∈ Γ, we have

(gγ

, gγ

) = d

(γ

, γ

However, it is usually not the case that the metric is right invariant, i.e.

(

g, γ

) is not equal to

(

, γ

). This is one of the prices we have to

pay for wanting to do geometry.

If we tried to draw our metric space out, it looks pretty unhelpful — it’s just

a bunch of dots. It is not path connected. We can’t really think about it well.

To fix this, we talk about Cayley graphs.

Definition (Cayley graph). The Cayley graph Cay

(Γ) is defined as follows:

– V (Cay

(Γ)) = Γ

– For each γ ∈ Γ and s ∈ S, we draw an edge from γ to γs.

If we want it to be a directed and labelled graph, we can label each edge by the

generator s.

There is, of course, an embedding of Γ into

Cay

(Γ). Moreover, if we

metrize

Cay

(Γ) such that each edge has length [0

1], then this is an isometric

embedding.

It will be useful for future purposes to note that there is a left action of Γ

Cay

(Γ) which extends the left action of Γ on itself. This works precisely

because the edges are defined by multiplication on the right, and left and right

multiplication commute.

Example.

Take Γ =

, and take

{

}

. Then the Cayley graph

looks like

0 1

Example. Take Γ = S

and S = {(1 2), (1 2 3)}. The Cayley graph is

Example. Take Γ = Z, and S = {1}. Then the Cayley graph looks like

−4 −3 −2 −1 0 1 2 3 4

Example. Take Γ = Z and S = {2, 3}. Then the Cayley graph looks like

Now this seems quite complicated. It’s still the same group Γ =

, but with

a different choice of generating set, it looks very different. It seems like what we

do depends heavily on the choice of the generating set.

Example. If Γ = Z

and S = {(1, 0), (0, 1)}, then the Cayley graph is a grid

Example. If Γ = F

= ha, bi, S = {a, b}, then the Cayley graph looks like

If one has done algebraic topology, then one might recognize this as the

universal cover of a space. This is not a coincidence, and we will talk about this

later.

Let’s now thing a bit more about the choice of generating set. As one would

expect, the Cayley graph depends a lot on the generating set chosen, but often we

only care about the group itself, and not a group-with-a-choice-of-generating-set.

The key observation is that while the two Cayley graphs of

we drew seem

quite different, if we looked at them from 100 meters away, they look quite

similar — they both look like a long, thin line.

Definition

(Quasi-isometry)

Let

λ ≥

1 and

c ≥

0. A function between metric

spaces f : X → Y is a (λ, c)-quasi-isometric embedding if for all x

, x

∈ X

, x

) − c ≤ d

(f(x

), f(x

)) ≤ λd

(x,

, x

) + c

If, in addition, there is a

such that for all

y ∈ Y

, there exists

x ∈ X

such that

(

y, f

(

))

≤ C

, we say

is a quasi-isometry, and

is quasi-isometric to

We write X '

Y .

We can think of the first condition as saying we are quasi-injective, and the

second as saying we are quasi-surjective.

The right way to think about the definition is that the

says we don’t care

about what happens at scales less than

, and the

is saying we allow ourselves

to stretch distances. Note that if we take

= 0, then this is just the notion of

a bi-Lipschitz map. But in general, we don’t even require

to be continuous,

since continuity is a rather fine-grained property.

Exercise. Check that X '

Y is an equivalence relation.

This is not immediately obvious, because there is no inverse to

. In fact, we

need the axiom of choice to prove this result.

Example.

Any bounded metric spaces is quasi-isometric to a point. In particu-

lar, if Γ is finite, then (Γ, d

) '

For this reason, this is not a great point of view for studying finite groups.

On the other hand, for infinite groups, this is really useful.

Example.

For any Γ and

, the inclusion (Γ

, d

)

→

(

Cay

(Γ)

, d

) is a quasi-

isometry (take λ = 1, c = 0, C =

Of course, the important result is that any two word metrics on the same

group are quasi-isomorphic.

Theorem.

For any two finite generating sets

S, S

of a group Γ, the identity

map (Γ, d

) → (Γ, d

) is a quasi-isometry.

Proof. Pick

λ = max

s∈S



(s), λ

= max

s∈S



(s),

We then see



(γ) ≤ λ



(γ), 

(γ) ≤ λ

(γ).

for all γ ∈ Γ. Then the claim follows.

So as long as we are willing to work up to quasi-isometry, we have a canonically

defined geometric object associated to each finitely-generated group.

Our next objective is to be able to state and prove the Schwarz–Milnor

lemma. This is an important theorem in geometric group theory, saying that if

a group Γ acts “nicely” on a metric space

, then Γ must be finitely generated,

and in fact (Γ

, d

) is quasi-isomorphic to

. This allows us to produce some

rather concrete geometric realizations of (Γ, d

), as we will see in examples.

In order to do that, we must write down a bunch of definitions.

Definition

(Geodesic)

Let

be a metric space. A geodesic in

is an isometric

embedding of a closed interval γ : [a, b] → X.

This is not exactly the same as the notion in differential geometry. For

example, if we have a sphere and two non-antipodal points on the sphere, then

there are many geodesics connecting them in the differential geometry sense,

but only the shortest one is a geodesic in our sense. To recover the differential

geometry notion, we need to insert the words “locally” somewhere, but we shall

not need that.

Definition

(Geodesic metric space)

A metric space

is called geodesic if every

pair of points x, y ∈ X is joined by a geodesic denoted by [x, y].

Note that the notation [

x, y

] is not entirely honest, since there may be

many geodesics joining two points. However, this notation turns out to work

surprisingly well.

Definition

(Proper metric space)

A metric space is proper if closed balls in

are compact.

For example, infinite-dimensional Hilbert spaces are not proper, but finite-

dimensional ones are.

Example.

If Γ =

hSi

, then

Cay

(Γ) is geodesic. If

is finite, then

Cay

(Γ) is

proper.

Example.

Let

be a connected Riemannian manifold. Then there is a metric

on M defined by

d(x, y) = inf

α:x→y

length(α),

where we take the infimum over all smooth paths from x to y.

The Hopf–Rinow theorem says if

is complete (as a metric space), then the

metric is proper and geodesic. This is great, because completeness is in some

sense a local property, but “proper” and “geodesic” are global properties.

We need two more definitions, before we can state the Schwarz–Milnor lemma.

Definition

(Proper discontinuous action)

An action Γ on a topological space

X is proper discontinuous if for every compact set K, the set

{g ∈ Γ : gK ∩ K 6= ∅}

is finite.

Definition

(Cocompact action)

An action Γ on a topological space

cocompact if the quotient Γ \ X is compact.

Lemma

(Schwarz–Milnor lemma)

Let

be a proper geodesic metric space,

and let Γ act properly discontinuously, cocompactly on X by isometries. Then

(i) Γ is finitely-generated.

(ii) For any x

∈ X, the orbit map

Γ → X

γ 7→ γx

is a quasi-isometry (Γ, d

) '

(X, d).

An easy application is that Γ acting on its Caylay graph satisfies these

conditions. So this reproduces our previous observation that a group is quasi-

isometric to its Cayley graph. More interesting examples involve manifolds.

Example.

Let

be a closed (i.e. compact without boundary), connected

Riemannian manifold. Then the universal cover

is also a complete, connected,

Riemannian manifold. By the Hopf–Rinow theorem, this is proper and geodesic.

Since the metric of

is pulled back from

, we know

(

) acts on

isometries. Therefore by the Schwarz–Milnor lemma, we know

(M) '

Example.

The universal cover of the torus

× S

, and the fundamental

group is Z

. So we know Z

, which is not surprising.

Example. Let M = Σ

, the surface of genus 2.

We then have

∼

, b

, a

, b

| [a

, b

][a

, b

]i.

On the other hand, the universal cover can be thought of as the hyperbolic plane

, as we saw in IB Geometry.

So it follows that

This gives us some concrete hold on what the group

is like, since people

have been thinking about the hyperbolic plane for centuries.

Proof of Schwarz–Milnor lemma.

Let

(

x, R

) be such that Γ

. This

is possible since the quotient is compact.

Let S = {γ ∈ Γ : γ

B ∩

B 6= ∅}. By proper discontinuity, this set is finite.

We let

r = inf

6∈S

B, γ

B).

If we think about it, we see that in fact

is the minimum of this set, and in

particular r > 0.

Finally, let

λ = max

s∈S

d(x

, sx

We will show that

generates Γ, and use the word metric given by

to show

that Γ is quasi-isometric to X.

We first show that Γ =

hSi

. We let

γ ∈

Γ be arbitrary. Let [

, γx

] be a

geodesic from x

to γx

. Let  be such that

( − 1)r ≤ d(x

, γx

) < r.

Then we can divide the geodesic into



pieces of length about

. We can choose

, . . . x

`−1

, x

= γx

such that d(x

i−1

, x

) < r.

By assumption, we can pick

∈

Γ such that

∈ γ

, and further we pick

= γ, γ

= e. Now for each i, we know

B, γ

−1

i−1

B) = d(γ

i−1

B, γ

B) ≤ d(x

i−1

, x

) < r.

So it follows that γ

−1

i−1

∈ S. So we have

γ = γ

= (γ

−1

)(γ

−1

) · · · (γ

−1

`−1

) ∈ hSi.

This proves Γ = hSi.

To prove the second part, we simply note that

r − r ≤ d(x

γx

We also saw that



is an upper bound for the word length of

under

. So we

have

r

(γ) − r ≤ d(x

, γx

On the other hand, by definition of λ, we have

d(x

, γx

) ≤ λ

(γ).

So the orbit map is an orbit-embedding, and quasi-surjectivity follows from

cocompactness.

1.2 Free groups

If we want to understand a group, then a reasonable strategy now would be to

come up with a well-understood (proper geodesic) space for Γ to act (proper

discontinuously, cocompactly) on, and see what we can tell from this quasi-

isometry. There is no general algorithm for doing so, but it turns out for certain

groups, there are some “obvious” good choices to make.

Let’s begin by understanding the free group. In some sense, they are the

“simplest” groups, but they also contain some rich structure. Roughly speaking,

a free group on a set

is a group that is “freely” generated by

. This freeness

is made precise by the following universal property.

Definition

(Free group)

Let

be a (usually finite) set. A group

(

) with a

map

S → F

(

) is called the free group on

if it satisfies the following universal

property: for any set map

S → G

, there is a unique group homomorphism

F (S) → G such that the following diagram commutes:

S F (S)

Usually, if |S| = r, we just write F (S) = F

In fancy category-theoretic language, this says the functor

Sets → Grps

is left adjoint to the forgetful functor U : Grps → Sets.

This definition is good for some things, but not good for others. One thing it

does well is it makes it clear that

(

) is unique up to isomorphism if it exists.

However, it is not immediately clear that

(

) exists! (unless one applies the

adjoint functor theorem)

Thus, we must concretely construct a group satisfying this property. Apart

from telling us that

(

) actually exists, a concrete construction lets us actually

do things with the group.

For concreteness, suppose

, . . . , a

}

is a finite set. We consider a

graph

where there are r “petals”. This is known as the rose with r petals.

We claim that its fundamental group is

(

). To see this, we have to

understand the universal cover

. We know

is a simply connected

graph, so it is a tree. Moreover, since it is a covering space of

, it is regular

with degree 2r on each vertex.

If r = 2, then this is our good old picture

∗

We can use this to understand the fundamental group

(

). The elements

(

) are homotopy classes [

] of based loops in

. Using the homotopy

lifting lemma, this map can be lifted to a path

˜γ

in the universal cover starting

at ∗.

∗

In general, there are many paths that represent the same element. However, there

is a “canonical” such path. Indeed, we can eliminate all backtracks in the path

to obtain an embedded path from

∗

to the end point of

˜γ

. We may reparametrize

so that it spends equal time on each edge, but that is not important.

Algebraically, how do we understand this? Each loop in

represents an

element

(

). If we look at the “canonical” form of the path above, then

we see that we are writing γ in the form

γ = a

±1

· · · a

±1

The fact that we have eliminated all backtracks says this expression is reduced,

i.e. we don’t see anything looking like

−1

, or

−1

. Importantly, there is a

unique way to write

as a reduced word, corresponding to the unique embedded

path from

∗

to the end point of

˜γ

in the universal cover. Thus, if we somehow

expressed

as a non-reduced word in the

, . . . , a

, then we can reduce it by

removing instances of

−1

, and keep doing so until we don’t see any.

This terminates since the length of the word is finite, and the result does not

depend on the order we performed the reduction in, by uniqueness.

Example. Take the case π

= ha, bi. We might be given a word

−2

−3

−1

We can reduce this to

aba

−1

In particular, since this is not the identity, we know the original path was not

null-homotopic.

This gives us a very concrete understanding of

(

) — it is generated

, . . . , a

, and each element is represented uniquely by a reduced word. To

multiply words together, write them one after another, and then reduce the

result.

From this description, it is clear that

Corollary. π

(

) has the universal property of

(

), with

, . . . , a

}

So π

)

∼

Proof. Given any map f : S → G, define

f : F (S) → G by

f(a

±1

· · · a

±1

) =

f(a

)

±1

· · ·

f(a

)

±1

for any reduced word

±1

· · · a

±1

. This is easily seen to be well-defined and is

the unique map making the diagram commute.

1.3 Finitely-presented groups

Let’s try to consider groups that are slightly more complex than free groups. If a

group Γ is generated by

, then we have a surjective homomorphism

(

)

→

Γ.

Let K = ker η. Then the first isomorphism theorem tells us

∼

F (S)

Since we understand

(

) quite explicitly, it would be nice if we have a solid

gasp on

as well. If

normally generates

, so that

hhRii

, then we say

that hS | Ri is a presentation for Γ. We will often write that

∼

hS | Ri.

Example.

= ha, b | aba

−1

Definition

(Finitely-presented group)

A finitely-presentable group is a group

Γ such that there are finite S and R such that Γ

∼

hS | Ri.

A finitely-presented group is a group Γ equipped

and

such that Γ

∼

hS |

Ri.

Presentations give us ways to geometrically understand a group. Given a

presentation

hS | Ri

, we can construct space

such that

∼

hS | Ri

To do so, we first construct a rose with

|S|

many petals, each labeled by an

element of

. For each

r ∈ R

, glue a disk onto the rose along the path specified

by r. The Seifert–van Kampen theorem then tells us π

∼

Γ.

Example.

We take the presentation

∼

ha, b | aba

−1

. If we think hard

enough (or a bit), we see this construction gives the torus.

Conversely, if we are given a connected cell complex

, we can obtain a

presentation of the fundamental group. This is easy if the cell complex has a

single 0-cell. If it has multiple 0-cells, then we choose a maximal tree in

(1)

and the edges

}

not in the maximal tree define a generating set for

(1)

. The attaching maps of the 2-cells in

define elements

}

(1)

, and these data define a presentation P

= hS | Ri for π

This is not canonical, since we have to pick a maximal tree, but let’s not

worry too much about that. The point of maximal trees is to get around the

problem that we might have more than one vertex.

Exercise. If X has one vertex, then Cay

X =

(1)

1.4 The word problem

Long time ago, Poincar´e was interested in characterizing the 3-sphere. His

first conjecture was that if a closed 3-manifold

had

∗

(

)

∼

∗

(

), then

∼

. Poincar´e thought very hard about the problem, and came up with a

counterexample. The counterexample is known as the Poincar´e homology sphere.

This is a manifold P

with

∗

(P )

∼

∗

but it turns out there is a surjection

(

)

→ A

. In particular,

is not

homeomorphic to a sphere.

So he made a second conjecture, that if

is a compact manifold with

∼

1, then

∼

. Note that the condition already implies

∗

(

)

∼

∗

(

)

by Hurewicz theorem and Poincar´e duality. This is known as the Poincar´e

conjecture, which was proved in 2002 by Perelman.

But there is more to say about Poincar´e’s initial conjecture. Some time later,

Max Dehn constructed an infinite family of 3d homology spheres. In order to

prove that he genuinely had infinitely many distinct homology spheres, he had

to show that his homology spheres had different fundamental groups. He did

manage to write down the presentations of the fundamental groups, and so what

was left to do is to distinguish whether the presentations actually presented the

same group.

To make sense of this statement, we must have some way to distinguish

between the homology spheres. To do so, he managed to write down the

presentation of the fundamental group of his homology spheres, and he had to

figure out if those groups are genuinely the same.

For our purposes, perhaps we should be slightly less ambitious. Suppose we

are given a presentation

hS | Ri

of a finitely-presented group Γ. Define the set

of alphabets

= S q S

−1

= {s, s

−1

: s ∈ S},

and let

∗

be the set of all finite words in

. Then the fundamental question is,

given a word

w ∈ S

∗

, when does it represent the identity element 1

∈

Γ? Ideally,

we would want an algorithm that determines whether this is the case.

Example.

Recall that in the free group

(

) =

hS | ∅i

, we had a normal form

theorem, namely that every element in Γ can be written uniquely as a product

of generator (and inverses) such that there aren’t any occurrences of

−1

. This gives a way of determining whether a given word

w ∈ S

∗

represents

the identity. We perform elementary reductions, removing every occurrence of

−1

. Since each such procedure reduces the length of the word, this

eventually stops, and we would end up with a reduced word. If this reduced

word is empty, then w represents the identity. If it is non-empty, w does not.

Thus, we have a complete solution to the word problem for free groups, and

moreover the algorithm is something we can practically implement.

For a general finitely-presented group, this is more difficult. We can first

reformulate our problem. The presentation Γ =

hS | Ri

gives us a map

(

)

→

Γ,

sending

. Each word gives us an element in

(

), and thus we can

reformulate our problem as identifying the elements in the kernel of this map.

Lemma.

Let Γ =

hS | Ri

. Then the elements of

ker

(

)

→

Γ) are precisely

those of the form

i=1

±1

−1

where g

∈ F (S) and r

∈ R.

Proof.

We know that

ker

(

)

→

Γ) =

hhRii

, and the set described above is

exactly hhRii, noting that gxyg

−1

= (gxg

−1

)(gyg

−1

This tells us the set of elements in

∗

that represent the identity is recursively

enumerable, i.e. there is an algorithm that lists out all words that represent the

identity. However, this is not very helpful when we want to identify whether a

word represents the identity. If it does, then our algorithm will eventually tell

us it is (maybe after 3 trillion years), but if it doesn’t, the program will just run

forever, and we will never know that it doesn’t represent the identity.

Example. Let Γ = Z

∼

ha, b | [a, b]i. Consider the word

w = a

−n

We see that this represents our identity element. But how long would it take for

our algorithm to figure this fact out? Equivalently, what

do we need to pick

so that w is of the form

i=1

±1

−1

We can draw a picture. Our element [a, b] looks like

If, say, n = 2, then w is given by

If we think about it hard, then we see that what we need to do is to find out how

to fill in this big square with the small squares, and we need 4 squares. Indeed,

we can read off the sequence

w = [a, b] · (b[a, b]b

−1

) · (b

−1

[a, b]ba

−1

−2

) · (b

−1

[a, b]baba

−2

which corresponds to filling in the square one by one as follows:

Of course, this is fine if we know very well what the Cayley graph of the

group looks like, but in general it is quite hard. Indeed, solving the word problem

is part of what you do if you want to draw the Cayley graph, since you need to

know when two words give the same element!

So how do we solve the word problem? Our previous partial algorithm would

make a good, full solution if we knew how far we had to search. If we know that

we will only need at most

= 10

100

, then if we searched for all expressions of

the form

i=1

−1

for

d <

100

, and didn’t find

, then we know

does

not represent the identity element (we will later argue that we don’t have to

worry about there being infinitely many g

’s to look through).

Definition (Null-homotopic). We say w ∈ S

∗

is null-homotopic if w = 1 in Γ.

Definition

(Algebraic area)

Let

w ∈ S

∗

be mull-homotopic. Its algebraic area

Area

a,P

(w) = min

(

d : w =

i=1

±1

−1

)

We write the subscript

to emphasize this is the algebraic area. We will

later define the geometric area, and we will write it as

Area

. Afterwards, we

will show that they are the same, and we will stop writing the subscript.

Let us use

| · |

to denote word length in

(

), while



continues to denote

the word length in Γ.

Definition

(Dehn function)

Then Dehn function is the function

N → N

mapping

n 7→ max {Area

a,P

(w) | |w|

≤ n, w is null-homotopic} .

This Dehn function measures the difficulty of the word problem in P.

Proposition.

The word problem for

is solvable iff

is a computable function.

We will postpone the proof. The hard part of the proof is that we don’t have

to worry about the infinitely many possible g

that may be used to conjugate.

It would be really nice if the Dehn function can be viewed as a property of

the group, and not the presentation. This requires us to come up with a notion

of equivalence relation on functions N → [0, ∞) (or [0, ∞) → [0, ∞)).

Definition (4). We write f 4 g iff for some C > 0, we have

f(x) ≤ Cg(Cx + C) + Cx + C.

for all x.

We write f ≈ g if f 4 g and g 4 f .

This captures the (super-linear) asymptotic behaviour of f.

Example. For α, β ≥ 1, n

4 n

iff α ≤ β.

Proposition. If P and Q are two finite presentations for Γ, then δ

≈ δ

We start with two special cases, and then show that we can reduce everything

else to these two special cases.

Lemma. If R

⊆ hhRii is a finite set, and

P = hS | Ri, Q = hS | R ∪ R

then δ

' δ

Proof. Clearly, δ

≤ δ

. Let

m = max

∈R

Area

It is then easy to see that

Area

(w) ≤ m Area

(w).

Lemma. Let P = hS | Ri, and let

Q = hS q T | R q R

where

= {tw

−1

: t ∈ T, w

∈ F (S)}.

Then δ

≈ δ

Proof. We first show δ

4 δ

. Define

ρ : F (S q T ) → F (s)

s 7→ s

t 7→ w

In particular, ρ(r) = r for all r ∈ R and ρ(r

) = 1 for all r

∈ R

Given w ∈ F (S), we need to show that

Area

(w) ≤ Area

(w).

Let d = Area

(w). Then

w =

i=1

±1

−1

where

∈ F

(

)

, r

∈ R ∪ R

. We now apply

. Since

is a retraction,

ρ(w) = w. Thus,

w =

i=1

ρ(g

)ρ(r

)

±1

ρ(g

)

−1

Now

(

) is either

or 1. In the first case, nothing happens, and in the second

case, we can just forget the ith term. So we get

w =

i=1,r

∈R

ρ(g

±1

ρ(g

)

−1

Since this is a valid proof in P that w = 1, we know that

Area

(w) ≤ d = Area

(w).

We next prove that

4 δ

. It is unsurprising that some constants will appear

this time, instead of just inequality on the nose. We let

C = max

t∈T

Consider a null-homotopic word w ∈ F (S q T ). This word looks like

w = s

· · · t

· · · s · · · t · · · ∈ F (S q T ).

We want to turn these t’s into s’s, and we need to use the relators to do so.

We apply relations from R

to write this as

= s

· · · w

· · · s · · · w

· · · ∈ F (S).

We certainly have |w

≤ C|w|

SqT

. With a bit of thought, we see that

Area

(w) ≤ Area

) + |w|

SqT

≤ δ

(C|w|

SqT

) + |w|

SqT

So it follows that

(n) ≤ δ

(Cn) + n.

Proof of proposition.

Let

hS | Ri

and

| R

. If

P, Q

present

isomorphic groups, then we can write

s = u

∈ F (S

) for all s ∈ S

Similarly, we have

= v

∈ F (S) for all s

∈ S

We let

T = {su

−1

| s ∈ S}

= {s

−1

| s

∈ S

}

We then let

M = hS q S

| R ∪ R

∪ T ∪ T

We can then apply our lemmas several times to show that δ

≈ δ

Now we can talk about

, the Dehn function of Γ, as long as we know we

are only talking up to ≈. In fact, it is true that

Fact. If Γ

, then δ

≈ δ

The proof is rather delicate, and we shall not attempt to reproduce it.

2 Van Kampen diagrams

Recall we previously tried to understand the Dehn function of

in terms of

filling in squares on a grid. In this chapter, we pursue this idea further, and

come up with an actual theorem.

To make this more precise, recall that in the case of

, we could embed a

null-homotopic word into the plane of the form

We saw, at least heuristically, the algebraic area of

is just the geometric area

of this figure. Of course, sometimes it is slightly more complicated. For example,

if we have the word w = [a, b]

, then we have to use the cell [a, b] twice.

Definition

(Singular disc diagram)

A (singular) disc diagram is a compact,

contractible subcomplex of R

, e.g.

We usually endow the disc diagram D with a base point p, and define

Area

(D) = number of 2-cells of D

and

Diam

(D) = length of the longest embedded path in D

(1)

, starting at p.

If we orient

, then

has a well-defined boundary cycle. A disc diagram is

labelled if each (oriented) edge is labelled by an element

s ∈ S

. The set of face

labels is the set of boundary cycles of the 2-cells.

If all the face labels are elements of

, then we say

is a diagram over

hS | Ri.

Definition

(van Kampen diagram)

w ∈ hhRii

, and

is the boundary cycle

of a singular disc diagram

over the presentation

hS | Ri

, we say that

is a

van Kampen diagram for w.

Example. The diagram

is a van Kampen diagram for abababa

−2

−1

Note that in this case, the map

→ X

that represents

factors through

a map D → X

Lemma

(van Kampen’s lemma)

Let

hS | Ri

be a presentation and

w ∈ S

∗

Then the following are equivalent:

(i) w = 1 in Γ presented by P (i.e. w is null-homotopic)

(ii) There is a van Kampen diagram for w given P.

If so, then

Area

(w) = min{Area

(D) : D is a van Kampen diagram for w over P}.

Proof. In one direction, given

w =

i=1

−1

∈ F (S)

such that w = 1 ∈ Γ, we start by writing down a “lollipop diagram”

This defines a diagram for the word

i=1

−1

which is equal in

(

) to

, but is not exactly

. However, note that performing elementary reductions

(or their inverses) correspond to operations on the van Kampen diagram that

does not increase the area. We will be careful and not say that the area doesn’t

change, since we may have to collapse paths that look like

In the other direction, given a diagram

for

, we need to produce an

expression

w =

i=1

−1

such that d ≤ Area(D).

We let

be the first 2-cell that the boundary curve arrives at, reading

anticlockwise around

∂D

. Let

be the path from

, and let

be the relator

read anti-clockwise around e. Let

= D − e,

and let w

= ∂D

. Note that

w = gr

±1

−1

Since Area(D

) = Area(D) − 1, we see by induction that

w =

i=1

±1

−1

with d = Area(D).

We observe that in our algorithm about, the

’s produced have length

≤ Diam(D). So we see that

Corollary. If w is null-homotopic, then we can write w in the form

w =

i=1

−1

where

≤ Diam D

with D a minimal van Kampen diagram for w. We can further bound this by

(max |r

) Area(D) + |w|

≤ constant · δ

(|w|

) + |w|

So in particular, if we know

(

|w|

), then we can bound the maximum

length of g

needed.

It is now easy to prove that

Proposition.

The word problem for a presentation

is solvable iff

computable.

Proof.

(⇐)

By the corollary, the maximum length of a conjugator

that we need to

consider is computable. Therefore we know how long the partial algorithm

needs to run for.

(⇒)

To compute

(

), we use the word problem solving ability to find all

null-homotopic words in

(

) of length

≤ n

. Then for each

, go out and

look for expressions

w =

i=1

±1

−1

A naive search would find the smallest area expression, and this gives us

the Dehn function.

It is a hard theorem that

Theorem

(Novikov–Boone theorem)

There exists a finitely-presented group

with an unsolvable word problem.

Corollary. δ

is sometimes non-computable.

Let’s look at some applications to geometry. In geometry, people wanted to

classify manifolds. Classifying (orientable) 2-dimensional manifolds is easy. They

are completely labeled by the genus. This classification can in fact be performed

by a computer. If we manage to triangulate our manifold, then we can feed the

information of the triangulation into a computer, and then the computer can

compute the Euler characteristic.

Is it possible to do this in higher dimensions? It turns out the word problem

gives a severe hindrance to doing so.

Theorem.

Let

n ≥

4 and Γ =

hS | Ri

be a finitely-presented group. Then we

can construct a closed, smooth, orientable manifold M

such that π

∼

Γ.

This is a nice, little surgery argument.

Proof. Let S = {a

, . . . , a

} and R = {r

, . . . , r

}. We start with

= #

i=0

× S

n−1

Note that when we perform this construction, as n ≥ 3, we have

∼

by Seifert–van Kampen theorem. We now construct M

from M

k−1

such that

∼

, . . . , a

| r

, . . . , r

We realize

as a loop in

k−1

. Because

n ≥

3, we may assume (after a small

homotopy) that this is represented by a smooth embedded map

→ M

k−1

We take

to be a smooth tubular neighbourhood of

. Then

∼

× D

n−1

⊆ M

k−1

. Note that ∂N

∼

× S

n−2

Let

× S

n−2

. Notice that

∂U

∼

∂N

. Since

n ≥

4, we know

simply connected. So we let

k−1

= M

a manifold with boundary

× S

n−2

. Choose an orientation-reversing diffeo-

morphism ϕ

: ∂U

→ ∂M

k−1

. Let

= M

k−1

∪

Then by applying Seifert van Kampen repeatedly, we see that

= π

k−1

/hhr

ii,

as desired.

Thus, if we have an algorithm that can distinguish between the fundamental

groups of manifolds, then that would solve (some variant of) the word problem

for us, which is impossible.

Finally, we provide some (even more) geometric interpretation of the Dehn

function.

Definition

(Filling disc)

Let (

M, g

) be a closed Riemannian manifold. Let

→ M

be a smooth null-homotopic loop. A filling disk for

is a

smooth map f : D

→ M such that the diagram

Since there is a metric

, we can pull it back to a (possibly degenerate)

metric

∗

, and hence measure quantities like the length



(

) of

and

the area Area(f) of D

A classic result is

Theorem

(Douglas, Rad´u, Murray)

is embedded, then there is a least-area

filling disc.

So we can define

Definition (FArea).

FArea(γ) = inf{Area(f) | f : D

→ M is a filling disc for γ}.

Definition (Isoperimetric function). The isoperimetric function of (M, g) is

F iU

: [0, ∞) → [0, ∞)

 7→ sup{FArea(γ) : γ : S

→ M is a smooth null-homotopic loop, (γ) ≤ }

Theorem

(Filling theorem)

let

be a closed Riemannian manifold. Then

F iU

' δ

By our previous construction, we know this applies to every finitely-presented

group.

3 Bass–Serre theory

3.1 Graphs of spaces

Bass–Serre theory is a way of building spaces by gluing old spaces together, in a

way that allows us to understand the fundamental group of the resulting space.

In this section, we will give a brief (and sketchy) introduction to Bass-Serre

theory, which generalizes some of the ideas we have previously seen, but they

will not be used in the rest of the course.

Suppose we have two spaces

X, Y

, and we want to glue them along some

subspace. For concreteness, suppose we have another space

, and maps

∂

−

Z → X

and

∂

Z → Y

. We want to glue

and

by identifying

∂

−

(

)

∼ ∂

(

)

for all z ∈ Z.

If we simply take the disjoint union of

and

and then take the quotient,

then this is a pretty poorly-behaved construction. Crucially, if we want to

understand the fundamental group of the resulting space via Seifert–van Kampen,

then the maps

∂

must be very well-behaved for the theorem to be applicable.

The homotopy pushout corrects this problem by gluing like this:

∂

−

∂

X Y

Definition

(Homotopy pushout)

Let

X, Y, Z

be spaces, and

∂

−

Z → X

and

∂

: Z → Y be maps. We define

X q

Y = (X q Y q Z × [−1, 1])/ ∼,

where we identify ∂

(z) ∼ (z, ±1) for all z ∈ Z.

By Seifert–van Kampen, we know π

(X q

Y ) is the pushout

Z π

(X)

Y π

(X q

Y )

∂

∗

∂

−

∗

In other words, we have

(X q

Y )

∼

X ∗

In general, this is more well-behaved if the maps

∂

∗

are in fact injective, and we

shall focus on this case.

With this construction in mind, we can try to glue together something more

complicated:

Definition

(Graph of spaces)

A graph of spaces

consists of the following

data

– A connected graph Ξ.

– For each vertex v ∈ V (Ξ), a path-connected space X

– For each edge e ∈ E(Ξ), a path-connected space X

–

For each edge

e ∈ E

(Ξ) attached to

∈ V

(Ξ), we have

-injective maps

∂

: X

→ X

The realization of X is

|X | = X =

v∈V (Ξ)

e∈E(Ξ)

× [−1, 1])

(∀e ∈ E(Ξ), ∀x ∈ X

, (x, ±1) ∼ ∂

(x))

These conditions are not too restrictive. If our vertex or edge space were

not path-connected, then we can just treat each path component as a separate

vertex/edge. If our maps are not

injective, as long as we are careful enough,

we can attach 2-cells to kill the relevant loops.

Example.

A homotopy pushout is a special case of a realization of a graph of

spaces.

Example. Suppose that the underlying graph looks like this:

The corresponding gluing diagram looks like

Fix a basepoint

∗ ∈ X

. Pick a path from

∂

−

(

∗

) to

∂

(

∗

). This then gives a

loop

that “goes around”

[

−

1] by first starting at

∂

−

(

∗

), move along

∗ × [−1, 1], then returning using the path we chose.

Since every loop inside

can be pushed down along the “tube” to a loop

in X

, it should not be surprising that the group π

(X) is in fact generated by

) and t.

In fact, we can explicitly write

X =

∗ hti

hh(∂

)

∗

(g) = t(∂

−

)

∗

(g)t

−1

∀g ∈ π

This is known as an HNN extension. The way to think about this is as follows

— we have a group

, and we have two subgroups that are isomorphic to each

other. Then the HNN extension is the “free-est” way to modify the group so

that these two subgroups are conjugate.

How about for a general graph of spaces? If Ξ is a graph of spaces, then its

fundamental group has the structure of a graph of groups G.

Definition (Graph of groups). A graph of groups G consists of

– A graph Γ

– Groups G

for all v ∈ V (Γ)

– Groups G

for all e ∈ E(Γ)

– For each edge e with vertices v

(e), injective group homomorphisms

∂

: G

→ G

(e)

In the case of a graph of spaces, it was easy to define a realization. One way

to do so is that we have already see how to do so in the two above simple cases,

and we can build the general case up inductively from the simple cases, but that

is not so canonical. However, this has a whole lot of choices involved. Instead,

we are just going to do is to associate to a graph of groups

a graph of spaces

which “inverts” the natural map from graphs of spaces to graphs of groups,

given by taking π

of everything.

This can be done by taking Eilenberg–Maclane spaces.

Definition

(Aspherical space)

A space

is aspherical if

is contractible. By

Whitehead’s theorem and the lifting criterion, this is true iff

(

) = 0 for all

n ≥ 2.

Proposition.

For all groups

there exists an aspherical space

(

such that

(

1))

∼

. Moreover, for any two choices of

(

1) and

(

1), and for every homomorphism

G → H

, there is a unique map (up to

homotopy)

(

→ K

(

1) that induces this homomorphism on

. In

particular, K(G, 1) is well-defined up to homotopy equivalence.

Moreover, we can choose

(

1) functorially, namely there are choices of

(

1) for each

and choices of

such that

◦ f

◦

and

K(G,1)

for all f, G, H.

These K(G, 1) are known as Eilenberg–MacLane spaces.

When we talked about presentations, we saw that this is true if we don’t

have the word “aspherical”. But the aspherical requirement makes the space

unique (up to homotopy).

Using Eilenberg–MacLane spaces, given any graph of groups

, we can

construct a graph of spaces Ξ such that when we apply

to all the spaces in

X , we recover G.

We can now set

G = π

|X |.

Note that if Γ is finite, and all the G

’s are finitely-generated, then π

G is also

finitely-generated, which one can see by looking into the construction of

(

1).

If Γ is finite, all

’s are finitely-presented and all

’s are finitely-generated,

then π

G is finitely-presented.

For more details, read Trees by Serre, or Topological methods in group theory

by Scott and Wall.

3.2 The Bass–Serre tree

Given a graph of groups

, we want to analyze

, and we do this by

the natural action of G on

X by deck transformations.

Recall that to understand the free group, we looked at the universal cover of

the rose with r petals. Since the rose was a graph, the universal cover is also a

graph, and because it is simply connected, it must be a tree, and this gives us a

normal form theorem. The key result was that the covering space of a graph is

a graph.

Lemma.

is a graph of spaces and

X → X

is a covering map, then

naturally has the structure of a graph of spaces

, and

respects that structure.

Note that the underlying graph of

is not necessarily a covering space of

the underlying graph of X .

Proof sketch. Consider

[

v∈V (Ξ)

⊆ X.

Let

−1





[

v∈V (Ξ)





ˆv∈V (

Ξ)

ˆv

This defines the vertices of

, the underlying graph of

. The path components

ˆv

are going to be the vertex spaces of

. Note that for each

ˆv

, there exists a

unique v ∈ V (Ξ) such that p :

ˆv

→ X

is a covering map.

Likewise, the path components of

−1





[

e∈E(Ξ)

× {0}





form the edge spaces

e∈E(Ξ)

ˆe

, which again are covering spaces of the

edge space of X.

Now let’s define the edge maps

∂

ˆe

for each

ˆe ∈ E

(

)

7→ e ∈ E

(Ξ). To do so,

we consider the diagram

ˆe

× [−1, 1]

× [−1, 1] X

∼

By the lifting criterion, for the dashed map to exist, t