IV Topics in Geometric Group Theory - Cayley graphs and the word metric

1Cayley graphs and the word metric

IV Topics in Geometric Group Theory

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.