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
D
6
, 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
6
.
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
S
a generating set for Γ. For the purposes of this
course,
S
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
S
a finite generating set. If
γ Γ, the word length of γ is
S
(γ) = min{n : γ = s
±1
1
· · · s
±1
n
for some s
i
S}.
Definition
(Word metric)
.
Let Γ be a group and
S
a finite generating set. The
word metric on Γ is given by
d
S
(γ
1
, γ
2
) =
s
(γ
1
1
γ
2
).
If we stare at the definition, we see that the word metric is left-invariant, i.e.
for any g, γ
1
, γ
2
Γ, we have
d
S
(gγ
1
, gγ
2
) = d
S
(γ
1
, γ
2
).
However, it is usually not the case that the metric is right invariant, i.e.
d
S
(
γ
1
g, γ
2
g
) is not equal to
d
S
(
γ
1
, γ
2
). 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
S
(Γ) is defined as follows:
V (Cay
S
(Γ)) = Γ
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
S
(Γ). Moreover, if we
metrize
Cay
S
(Γ) 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 Γ
on
Cay
S
(Γ) 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 Γ =
C
2
=
Z/
2
Z
, and take
S
=
{
1
}
. Then the Cayley graph
looks like
0 1
Example. Take Γ = S
3
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 Γ =
Z
, 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
2
and S = {(1, 0), (0, 1)}, then the Cayley graph is a grid
Example. If Γ = F
2
= ha, bi, S = {a, b}, then the Cayley graph looks like
If one has done algebraic topology, then one might recognize this as the
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
Z
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
1
, x
2
X
1
λ
d
X
(x
1
, x
2
) c d
Y
(f(x
1
), f(x
2
)) λd
X
(x,
1
, x
2
) + c
If, in addition, there is a
C
such that for all
y Y
, there exists
x X
such that
d
Y
(
y, f
(
x
))
C
, we say
f
is a quasi-isometry, and
X
is quasi-isometric to
Y
.
We write X '
qi
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
c
says we don’t care
about what happens at scales less than
c
, and the
λ
is saying we allow ourselves
to stretch distances. Note that if we take
c
= 0, then this is just the notion of
a bi-Lipschitz map. But in general, we don’t even require
f
to be continuous,
since continuity is a rather fine-grained property.
Exercise. Check that X '
qi
Y is an equivalence relation.
This is not immediately obvious, because there is no inverse to
f
. 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
S
) '
qi
1.
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
S
, the inclusion
, d
S
)
(
Cay
S
(Γ)
, d
S
) is a quasi-
isometry (take λ = 1, c = 0, C =
1
2
).
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
0
of a group Γ, the identity
map , d
S
) , d
S
0
) is a quasi-isometry.
Proof. Pick
λ = max
sS
S
0
(s), λ
0
= max
sS
0
S
(s),
We then see
S
(γ) λ
0
S
0
(γ),
S
0
(γ) λ
s
(γ).
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
X
, then Γ must be finitely generated,
and in fact
, d
s
) is quasi-isomorphic to
X
. This allows us to produce some
rather concrete geometric realizations of , d
s
), as we will see in examples.
In order to do that, we must write down a bunch of definitions.
Definition
(Geodesic)
.
Let
X
be a metric space. A geodesic in
X
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
X
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
X
are compact.
For example, infinite-dimensional Hilbert spaces are not proper, but finite-
dimensional ones are.
Example.
If Γ =
hSi
, then
Cay
S
(Γ) is geodesic. If
S
is finite, then
Cay
S
(Γ) is
proper.
Example.
Let
M
be a connected Riemannian manifold. Then there is a metric
on M defined by
d(x, y) = inf
α:xy
length(α),
where we take the infimum over all smooth paths from x to y.
The Hopf–Rinow theorem says if
M
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
X
is
cocompact if the quotient Γ \ X is compact.
Lemma
(Schwarz–Milnor lemma)
.
Let
X
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
0
X, the orbit map
Γ X
γ 7→ γx
0
is a quasi-isometry , d
s
) '
qi
(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
M
be a closed (i.e. compact without boundary), connected
Riemannian manifold. Then the universal cover
˜
M
is also a complete, connected,
Riemannian manifold. By the Hopf–Rinow theorem, this is proper and geodesic.
Since the metric of
˜
M
is pulled back from
M
, we know
π
1
(
M
) acts on
˜
M
by
isometries. Therefore by the Schwarz–Milnor lemma, we know
π
1
(M) '
qi
˜
M.
Example.
The universal cover of the torus
S
1
× S
1
is
R
2
, and the fundamental
group is Z
2
. So we know Z
2
'
qi
R
2
, which is not surprising.
Example. Let M = Σ
2
, the surface of genus 2.
We then have
π
1
Σ
2
=
ha
1
, b
1
, a
2
, b
2
| [a
1
, b
1
][a
2
, b
2
]i.
On the other hand, the universal cover can be thought of as the hyperbolic plane
H
2
, as we saw in IB Geometry.
So it follows that
π
1
Σ
2
'
qi
H
2
.
This gives us some concrete hold on what the group
π
1
Σ
2
is like, since people
have been thinking about the hyperbolic plane for centuries.
Proof of Schwarz–Milnor lemma.
Let
¯
B
=
¯
B
(
x, R
) be such that Γ
¯
B
=
X
. This
is possible since the quotient is compact.
Let S = {γ Γ : γ
¯
B
¯
B 6= ∅}. By proper discontinuity, this set is finite.
We let
r = inf
γ
0
6∈S
d(
¯
B, γ
0
¯
B).
If we think about it, we see that in fact
r
is the minimum of this set, and in
particular r > 0.
Finally, let
λ = max
sS
d(x
0
, sx
0
).
We will show that
S
generates Γ, and use the word metric given by
S
to show
that Γ is quasi-isometric to X.
We first show that Γ =
hSi
. We let
γ
Γ be arbitrary. Let [
x
0
, γx
0
] be a
geodesic from x
0
to γx
0
. Let be such that
( 1)r d(x
0
, γx
0
) < r.
Then we can divide the geodesic into
r
. We can choose
x
1
, . . . x
`1
, x
`
= γx
0
such that d(x
i1
, x
i
) < r.
By assumption, we can pick
γ
i
Γ such that
x
i
γ
i
¯
B
, and further we pick
γ
`
= γ, γ
0
= e. Now for each i, we know
d(
¯
B, γ
1
i1
γ
i
¯
B) = d(γ
i1
¯
B, γ
i
¯
B) d(x
i1
, x
i
) < r.
So it follows that γ
1
i1
γ
i
S. So we have
γ = γ
`
= (γ
1
0
γ
1
)(γ
1
1
γ
2
) · · · (γ
1
`1
γ
`
) hSi.
This proves Γ = hSi.
To prove the second part, we simply note that
r r d(x
0
γx
0
).
We also saw that
is an upper bound for the word length of
γ
under
S
. So we
have
r
s
(γ) r d(x
0
, γx
0
).
On the other hand, by definition of λ, we have
d(x
0
, γx
0
) λ
s
(γ).
So the orbit map is an orbit-embedding, and quasi-surjectivity follows from
cocompactness.