MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

arXiv:1712.02484v2 [] 19 Feb 2018

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

Abstract. We introduce a notion of Ricci curvature for Cayley graphs that can be called
medium-scale because it is neither infinitesimal nor asymptotic, but based on a chosen finite
radius parameter. For this definition, abelian groups are identically flat, and in the other direction
we show that κ ≡ 0 implies the group is virtually abelian. In right-angled Artin groups, the
curvature is zero on central elements and negative otherwise. On the other hand, we find nilpotent,
CAT(0), and hyperbolic groups with points of positive curvature. We study dependence on
generators and behavior under embeddings.

Contents
1. Introduction
1.1. Definitions
1.2. Properties and examples
1.3. A Laplacian rephrasing
2. Virtually abelian groups
3. Nilpotent groups
4. Positively curved directions in CAT(0) and hyperbolic groups
4.1. A CAT(0) example
4.2. A hyperbolic example
5. Behavior under isometric embeddings
6. Curvature outside a ball
7. Questions for future study
References

1
2
3
5
5
7
9
9
10
11
12
13
14

1. Introduction
The emergence of a theory of large-scale negative curvature, or δ-hyperbolicity, has provided
an enormous breakthrough and a powerful tool for the theory of infinite groups. The existence
of any δ ≥ 0 for which a Cayley graph satisfies this family of metric conditions implies a host of
consequences for the geometry of the graph and the spaces acted on by the group. However, for large
finite graphs, this theory is not applicable—every bounded-diameter metric space is δ-hyperbolic
for δ ≥ diam, so hyperbolicity provides no information. In the analysis of large but finite graphs or
networks, we need another tool.
In the 2000s, Yann Ollivier defined a notion of metric Ricci curvature—at finite scales, not
asymptotic—suitable for graphs and other non-manifold geometries [7, 8, 9, 10]. To do this, he
offered a geometric interpretation of classical Ricci curvature as follows: curvature measures the
extent to which corresponding points on spheres are closer together or farther apart than the
centers of the spheres. (Negative Ricci curvature occurs when corresponding points are farther and
The authors gratefully acknowledge support from U.S. National Science Foundation grants DMS 1107452, 1107263,
1107367 “RNMS: GEometric structures And Representation varieties” (the GEAR Network). MD is supported by
NSF DMS-1255442. MD thanks Ruth Charney, Ilya Kapovich, and Jennifer Taback for very useful conversations.
1

2

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

positive curvature when they are closer.) The ability to define corresponding points on spheres in
the manifold setting relies on parallel transport, so Ollivier’s generalized definition replaces the
comparison distance with transportation distance, L1 Wasserstein distance to be precise.1 With
this definition, he can show that in the manifold setting his metric Ricci curvature agrees with
classical Ricci curvature on small scales, to first order.

Figure 1. (Left) For a geodesic in a manifold, points on spheres centered at the
endpoints may be put in correspondence by parallel transport. (Right) In the
Cayley graph for Z3 , corresponding neighbors of e and a4 bc are shown here marked
by color.
This paper is motivated by the observation that Cayley graphs of finitely generated groups,
because of the edge labelings, provide a setting in which transportation distance is not needed,
because any two points’ neighbors can be put in natural correspondence. Thus we arrive at a new
definition of Ricci curvature of Cayley graphs, which parallels manifold Ricci curvature even more
closely than the Ollivier adaptation. We explore its properties below.
1.1. Definitions. We will write (G, S) for a group G with generating set S, and e ∈ G for the
identity element. We will assume throughout that |S| < ∞, S = S −1 , and e ∈
/ S. We will use Γ for
graphs, in particular for the defining graph of a right-angled Artin group AΓ and for the Cayley
graph Γ(G, S) associated to (G, S). For x ∈ G, let |x| denote its length in the (G, S) word metric.
We write Br (x) = {g ∈ G : |x−1 g| ≤ r} and Sr (x) = {g ∈ G : |x−1 g| = r} for the ball and sphere
of radius r centered at x, respectively.
Let Tr (x, y) be the L1 transportation distance for the uniform measure on Br (x) and Br (y):
it is the “earth mover’s distance,” or the infimal distance for any plan of moving mass from
one probability distribution to the other. (See [8].) Then Ollivier defines what we will call the
r (x,y)
.
transportation curvature κTr (x, y) = d(x,y)−T
d(x,y)
In a Cayley graph Γ(G, S), note that there is a natural correspondence between neighbors of x
and neighbors of y given by matching xa with ya for a ∈ S; more generally we can compare xw
with yw for any word w ∈ G. Thus let Sr (x, y) be the radius-r spherical comparison distance in
the Cayley graph Γ(G, S):
1 X
Sr (x, y) :=
d(xw, yw),
|Sr |
w∈Sr

or similarly Br (x, y) on balls rather than spheres. Thus we can define a new Ricci curvature on
d(x,y)−Br (x,y)
r (x,y)
groups via κB
or κSr (x, y) = d(x,y)−S
. We call this comparison curvature
r (x, y) =
d(x,y)
d(x,y)
to distinguish it from Ollivier’s transportation curvature.
1We note that Ollivier’s was one of several proposed discretizations of Ricci curvature formulated in the same
time period; other quite different definitions can be found in sources such as [4, 5].

MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

3

B
−1
For comparison curvature, note that κB
y), so to study the curvature in a group
r (x, y) = κr (e, x
B
it suffices to fix one of the points at the identity. Thus we will write κB
r (g) to mean κr (e, g), and
similarly for the spherical comparison curvature S. For all three definitions, when the parameter r
is omitted, we are considering the case r = 1. In this note we will focus on the spherical comparison
curvature with r = 1, so we will simplify the notation even further, writing

κ(g) = κS1 (e, g).
Indeed, note that S1 (g) is the the average word length of a conjugate
of x by a generator, so we
P −1
1
|a ga| = S1 (e, g). In terms
will introduce the notation GenCon(g) = GenCon(G, S, g) := |S|
a∈S

of conjugation, then, we will study the notion of Ricci curvature on groups given by
κ(g) =

|g| − GenCon(g)
.
|g|

Negative Ricci curvature (with respect to spheres of radius one) occurs at a group element g
when its conjugates by generators are, on average, longer in word length than g itself. Respectively,
positive curvature occurs when conjugation shortens the length, and zero curvature when it is
unchanged.
1.2. Properties and examples.
Proposition 1 (Basic properties of comparison curvature).
(1) The curvature is zero at central elements, because g ∈ Z(G) =⇒ GenCon(g) = |g|. Indeed,
all comparison curvatures are identically zero on the center, for balls or spheres of any
radius. This is because d(xa, ya) = d(ax, ay) = d(x, y), so corresponding points have the
S
same distance as the centers, giving S = B = d and so κB
r = κr ≡ 0 for all r. In particular,
abelian groups with any generating sets have identically zero curvature.
(2) For finite groups, we can take all elements as generators (S = G r {e}) to make κ ≡ 0,
because the Cayley graph is a complete graph so all distances are 1.
(3) For r = 1, the value B is obtained as a weighted average of the value S with d, the distance
of the centers x and y. This means that the sign of the comparison curvature is the same
whether one considers balls or spheres of radius 1.
(4) Since T is an inf, and correspondence defines one of the competing transportation plans, we
have T ≤ B, so κT ≥ κB in general. This means that for abelian groups, the transportation
curvature is non-negative.
(5) |a−1 xa| is integer-valued and equals zero only for x = e, so GenCon(e) = 0 and GenCon(x) ≥
1 for non-identity elements. Generators a ∈ S satisfy κ(a) = 1 − GenCon(a), so κ(a) ≤ 0.
(6) Suppose that {e, w, w2 , w3 , . . .} is geodesic in a group G, meaning that |wk | = k|w| for
all k. It follows that κ(w) ≤ 0. Otherwise, there exists some generator a ∈ S for which
|a−1 wa| = d(a, wa) ≤ |w|−1. In that case we would have |wk | ≤ |a−1 wk a|+2 ≤ k|w|−k+2,
which for k ≥ 3 contradicts the assumption.
(7) For any x, y and any w ∈ Br , we have d(x, y) − 2r ≤ d(xw, yw) ≤ d(x, y) + 2r, and so the
average is also in that range, which means that the correspondence curvature is bounded:
S
−2r/d ≤ κB
r , κr ≤ 2r/d for d = d(x, y). In particular if you fix r and make d large, the
curvature becomes pinched near zero. When |w| ≤ 2, we get κ(w) ≤ 2/|w| ≤ 1. Putting
these together, we get κ ≤ 1 for every group element.
Proposition 2 (Damping out). If G is an infinite group and S is any generating set, then the
average curvature over the ball of radius n tends to zero as n → ∞.
Proof. The average curvature in the group G is the limit
P
g∈Bn κ(g)
lim
.
n→∞
|Bn |

4

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

Since |κ(g)| ≤

2
|g|

we see that for any k < n we have
P
|Bk | + k2 |Bn r Bk |
2
g∈Bn κ(g)
lim
≤ lim
≤ .
n→∞
n→∞
|Bn |
|Bn |
k

Since this holds for arbitrary k, the average curvature tends to 0.



Example 3 (Dependence on generators in the symmetric group). We will illustrate a simple
observation about the dependence on choice of generators by considering the case of the symmetric
group Symm(n). Recall from Proposition 1(2) that with respect to S = G r {e}, we get κ ≡ 0.
If we focus, for example, on the group element σ = (1 . . . n) ∈ Symm(n), then we will be able to
manipulate the sign of κ(σ) by building an appropriate generating set.
Proposition 4 (Manipulating the sign). Let σ = (1 . . . n) be the basic n-cycle in the symmetric group
Symm(n). Given any  > 0, for sufficiently large n there exist two generating sets Spos and Sneg
for Symm(n) such that
• with respect to Spos , we have |σ| = 2, GenCon(σ) < 1 + , and κ(σ) > 1−
; and
2
• with respect to Sneg , we have |σ| = 1, GenCon(σ) > 3 − , and κ(σ) < −2 + .
Proof. Let Spos (n) = Symm(n) r {e, σ}± , so that |Spos | = n! − 3. Consider the action of Symm(n)
on itself by conjugation. We must consider the length s−1 σs for s ∈ S. If s−1 σs ∈ {σ, σ −1 }, then
we can see |s−1 σs| = 2. This happens if s commutes with σ or conjugates it to σ −1 in the first case
there are n − 3 elements of S with this property. In the second case there are n elements of S. In
all other cases s−1 σs ∈ S and so has length 1. Thus we have
GenCon(σ) =

1
n! + 2n − 6
((n! − 3 − n − (n − 3)) + 2(n + n − 3)) =
−→ 1.
n! − 3
n! − 3

Let Sneg (n) = {(12), (23), . . . (n−1 n), σ ± }, so that |Sneg | = n + 1. Consider |s−1 σs| for s ∈ Sneg .
If s = σ ± , then |s−1 σs| = 1. Since σ is not fixed by any transposition we see that |s−1 σs| = 3
otherwise. Thus,
2 + 3(n − 1)
GenCon(σ) =
−→ 3. 
n+1
Example 5 (Free groups with standard generators). Let Fn be the free group with n standard
generators, and let w = a1 · · · am be a freely reduced word of length m, with ai not necessarily
distinct. If this spelling is not cyclically reduced, i.e., a1 = a−1
m = x, then GenCon(w) =
(2n−1)(m+2)+(m−2)
where the first term corresponds to conjugation by all generators other than x,
2n
and the last term corresponds to conjugation by x. If w is cyclically reduced, then GenCon(w) =
(2n−2)(m+2)+m+m
. In either case, GenCon(w) = m + 2 − n2 . Thus, κ(w) = 1 − GenCon(w)
=
2n
|w|
2
2
2−2n
mn − m = mn which is negative for n ≥ 2, and 0 for n = 1 (the case of the elementary free group
Z).
We have established that GenCon(w) and κ(w) both depend only on |w| and the rank of the
free group. We get negative curvature at all non-identity points in free groups of rank at least two.
Example 6 (F2 × Z). If G = F2 × Z = ha, b, z : [a, z] = [b, z] = ei, with S = {a, b, z}± , then a
straightforward calculation shows that GenCon(a) = GenCon(b) = 53 , so κ(a) = κ(b) = − 32 , as
follows. Conjugating a by a± or z ± doesn’t change its length, while conjugates by b± have length
3. Thus GenCon(a) = 1+1+1+1+3+3
= 53 . The case of b is similar. That means that κ = −2/3 on
6
the sphere, or −3/7 on the ball. Thus F2 × Z has some points of zero curvature and some points of
negative curvature (and no points of positive curvature) in its standard generators.
Example 7 (General RAAGs). Right-angled Artin groups, or RAAGs, are groups in which the
only relations are commuting relations between certain generators. This is encoded in a simple
undirected graph Γ for which the vertices represent generators and the edges appear between

MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

5

commuting pairs. For instance the free group Fn is a RAAG defined by a graph with no edges, and
the previous example F2 × Z is given by three vertices arranged in a path.
We will use the fact that RAAGs have a natural normal form: a string is geodesic iff it does not
contain a substring of the form x−1 (y1 y2 . . . yn )x where x, yi are generators and x, yi commute for
all i.
Proposition 8 (Curvature dichotomy for RAAGs). Let AΓ be the RAAG on the graph Γ with the
standard generating set S = V (Γ)±1 . Then κ(g) = 0 iff g is central; else, κ(g) < 0.
Proof. In light of Proposition 1(1), it suffices to show that if g is not central then κ(g) < 0. Fix
such a g. We will show that for all generators t ∈ S, |t−1 gt| + |tgt−1 | ≥ 2|g|, and there exists a
generator making this inequality strict.
Let Pref(g) = {v ∈ S | g = vh is a geodesic spelling of g} and Suff(g) = {v ∈ S | g = hv is a
geodesic spelling of g}. These are the letters that can be commuted to the front or the back of a
geodesic spelling for g, respectively. By the normal forms for RAAGs, these sets are well defined,
and neither Pref(g) nor Suff(g) can contain both v and v −1 . Note that all the letters in Pref(g)
(respectively Suff(g)) commute with one another, so the corresponding vertices form a clique in Γ.
These sets will prove useful in calculating word length.
For t ∈ S, note that |gt| = |g| ± 1, with |gt| = |g| − 1 if and only if t−1 ∈ Suff(g). Similarly,
−1
|t g| = |g| + 1 ⇐⇒ t ∈
/ Pref(g). Considering all the possibilities for whether t± are in Pref(g) or
−1
Suff(g) one sees that |t gt| + |tgt−1 | ≥ 2|g|. Finally, since g is not central, we can find a letter x
such that {x} ∪ Pref(g) is not a clique, and that means that both xg and x−1 g are geodesic. Since
both x and x−1 can’t be in Suff(g), this gives |x−1 gx| + |xgx−1 | > 2|g|.

1.3. A Laplacian rephrasing.
Definition 9. We define the automorphic Cayley graph ΓA (G, U ) for a group G and set of
automorphisms U ⊆ Aut(G) as follows: it has vertices for group elements g ∈ G and (directed)
edges g ∼ h if there exists φ ∈ U such that φ(g) = h.
Note that ΓA (G, U ) is often not connected. Note also that averaging over conjugates by generators
is the same thing as averaging over conjugates by neighbors:
1 X −1
1 X
1 X −1
|y xy| =
|(xa)−1 x(xa)| =
|a xa| = GenCon(x).
|S| y∼x
|S|
|S|
a∈S

a∈S

The automorphic Cayley graph of a group is related to κ in the following manner:
Proposition 10 (Curvature and the Laplacian). Let G be a group generated by S, and let S act
on G by conjugation. Fix x ∈ G and set fx (y) := |y −1 xy|. Then
1
κ(x) =
(∇fx ) (x),
fx (x)
where ∇f is the graph Laplacian on ΓA (G, S) pulled back by f . In particular, κ ≡ 0 on G if and
only if fx is harmonic.
2. Virtually abelian groups
We have seen that no group can have positive curvature at all nonidentity points, since Proposition 1(5) observes that κ(a) ≤ 0 for a ∈ S. Now we will consider the consequences of identically
zero curvature.
Theorem 11. Suppose κ(a) = 0 for all a ∈ S. Then G is virtually abelian.
Proof. Since κ(a) = 0 we have that GenCon(a) = 1 for all a ∈ S. In particular, this means that
the action of G by conjugation stabilizes S as a set. Consequently, since S is finite, it follows that
the stabilizer of a point a ∈ S is finite index in G. Since G is acting by conjugation, Fix(a) = Z(a).

6

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER
f.i.

Thus, for every a ∈ S, Z(a) ≤ G. Since S generates G, it follows that Z(G) = ∩a∈S Z(a), and this
group is finite index in G and abelian.

As a corollary, we get that groups of constant zero curvature are virtually abelian.
One might hope that there is a converse, namely that given a virtually abelian group we can find
a generating set where every point has κ = 0. We will see soon that this is not possible; however,
we do have the following.
∼ Zn is a finite-index normal free
Theorem 12. Let G be virtually abelian, so that H ≤ G, H =
abelian subgroup of G. Then there exists a generating set S of G such that κ(h) = 0 ∀h ∈ H.
Proof. There exists a finite group F such that G fits into the sequence
H ,→ G  F.
Since G acts on H by conjugation, there is a well defined map φ : F → Out(H) = GLn (Z). Let
U be a set containing a lift of each non-identity element of F and close it under inversion. Let T be
a finite generating set for H. Let V = {uvw | u, v, w ∈ U, uvw ∈ H} ∪ {uv | u, v ∈ U, uv ∈ H} ∪ T .
and let T 0 = {u−1 vu | t ∈ V, u ∈ hU i} be the set of conjugates of elements of T by elements of
hU i. This is a finite set since the orbits of hU i in H are finite. Let S = U ∪ T 0 ; by construction
S generates G. We will show that conjugating by s ∈ S does not change the word length of any
h ∈ H.
Let x1 . . . xl be a spelling for h that is geodesic with respect to S = U ∪ T 0 . Since T 0 is preserved
by the conjugation action of U we can assume that all but the first k letters are in T 0 . We will
show that k = 0.
Consider the word x1 . . . xk , note that since this represents an element of H we know that k 6= 1.
First we can see that no subword of the form xi xi+1 gives an element of H as we could replace this
with a generator from T 0 . Looking at the final subword xk−1 xk we can see there is an element y
such that yxk−1 xk is in H. We can then replace xk−1 xk by y −1 t for the element t = yxk−1 xk ∈ T 0 .
This allows us to reduce k by 1 without changing the length of our word. We can thus keep reducing
until we arrive at the case that k = 1 giving a contradiction.
Since H is a normal subgroup, T 0 is contained in H, which is abelian. Therefore generators in
0
T commute with h, so conjugation by T 0 generators does not change the word length.
Next consider conjugation by u ∈ U . Let xui = u−1 xi u, and note that this is in T 0 so its word
length is 1 with respect to S generators. We have a spelling for the group element u−1 hu, namely
−1
u−1
xu1 . . . xul , so |u−1 hu| ≤ |h|. Conversely, if y1 . . . ym is a word representing u−1 hu, then y1u . . . ym
is a word representing h, so |h| ≤ |u−1 hu|. Thus conjugation fixes the length of every word in H
and the curvature κ(h) = 0 for all h ∈ H.

In the case where the group is virtually Z we can remove the dependence on generating set;
however, in general, we must choose the generators carefully. This is established in the next two
results.
Proposition 13. Let G be a group with generating set S. Let N be a normal infinite cyclic
subgroup. Then κ(g) = 0 for all g ∈ N .
Proof. Take an element g ∈ Z and any generator s ∈ S. Since Z is normal we see that conjugation
by s gives an automorphism of Z which is either the identity or inversion. In either case this
preserves the length of the element g.

Proposition 14. There is a virtually abelian group G with a generating set S such that every
finite index free abelian subgroup has a point of positive curvature and a point of negative curvature.
Proof. Let G = ha, b, t | [a, b], t−1 at = ab, t−1 bt = a−1 , t6 i with generating set {a, b, t}±1 . This
group is isomorphic to Z2 o Z/6Z. The subgroup ha, bi = Z2 is a normal abelian subgroup and any
finite index free abelian subgroup is a subgroup of this.

MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

7

We will show that the element (ab)n has positive curvature and the element an has negative
curvature for all n ≥ 1.
The element w = (ab)n can be written as a geodesic using the spelling t−1 an t = w. So this
word has length n + 2. Since w = (ab)n ∈ Z2 , conjugating by the generators a, b does not change
the length. We must now consider the conjugates by t and t−1 . Firstly, twt−1 = tt−1 an tt−1 = an
and that has length n. Finally, t−1 wt = t−2 an t2 = t−1 (ab)n t = bn which also has length n. We
conclude that GenCon(w) = n + 43 < n + 2, thus κ(w) > 0.
The element v = an is a geodesic and so we work with this spelling. Conjugating by elements
of ha, bi will not change the length. Conjugating by t we get t−1 vt is a geodesic and has length
n + 2. Conjugating by t−1 we get tvt−1 = b−n , which is a geodesic and has length n. This gives
GenCon(v) = n + 31 > n, thus κ(v) < 0.

Finally, to see that it is not possible to have a complete converse to Theorem 11, we will look at
the infinite dihedral group.
Proposition 15. Let D∞ = Z2 ∗ Z2 , which is virtually Z. This group has no finite generating set
giving it constant zero curvature.
Proof. First consider D∞ = Z2 ∗ Z2 with the standard presentation ha, b | a2 , b2 i. Every element
of this group can be represented uniquely and geodesically as a positive word in a and b with no
occurrence of a2 or b2 . (The cyclic group generated by ab has index 2, with D∞ = habi t ahabi.)
If D∞ had a finite generating set S with zero curvature everywhere, then S would be preserved
by the conjugation action on itself, i.e., s−1 ts ∈ S for all s, t ∈ S. (As in the proof of Theorem 11,
this is because conjugation can’t carry a generator to the identity, so it can only lengthen the
generators, but if any of them strictly increases in length, then GenCon will go up and curvature
will be negative.)
If every element of S is a word which starts and ends in different letters, then S is contained in
the subgroup habi, because ba = (ab)−1 ∈ habi. Since habi is a proper subgroup, we conclude that
there is an element s ∈ S which starts and ends with the same letter, say a. There are two cases:
either s = a or s = awa for some nonempty w. We will deal with the case that s = a; the other
case works the same way.
There is at least one more element t =
6 s of S since D∞ has rank 2. Up to replacing t by t−1 ,
there are four cases to check: freely reduced spellings t = b, t = bvb, t = bva or t = ava for strings
v ∈ S∗.
Firstly, if t = b, then t−1 st = bab ∈ S and s−1 (t−1 st)s = ababa ∈ S. Repeatedly conjugating by
t and then s we find more elements that must belong to S, contradicting finiteness. The proof for
t = bvb is exactly the same.
If t = bva, then we can look at t−i sti = (av −1 b)i a(bva)i which is reduced and must be in S for
all i, showing again that S would be infinite.
Finally, if t = ava, then we can start by conjugating by a to see that v ∈ S. Since t was a reduced
word, we see that v starts and ends with b, which is a case that has already been treated.

3. Nilpotent groups
First, note that every nilpotent group has a nontrivial center (containing at least the last group
in its lower central series), which means that it has some points with κ = 0. In this section we
will establish that nilpotent groups can also have infinitely many points of positive and negative
curvature, by finding all three cases (κ = 0, > 0, < 0) with positive density in the Heisenberg group.
Let H(Z) = ha, b : [a, b] is centrali be the standard presentation of the Heisenberg group (the
free nilpotent group of step two and rank two). Blachère computed the exact formula for the word
metric in this distance in [1] in terms of matrix-entry coordinates. We will instead use Mal’cev
coordinates: every group element can be uniquely written in the form aA bB cC , where c = [a, b], for

8

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

integer exponents A, B, C. When it is convenient we can use Z3 coordinates (A, B, C) to denote
aA bB cC . Then the word metric obeys the following formula: if A > B > 0 and C > 0, then
(
2dC/Ae + A + B,
C ≤ A2 − AB;
A B C
√
(?)
|a b c | =
2d2 C + ABe − A − B, C ≥ A2 − AB.
Let us call the first case (C ≤ A2 −AB) the low-height case; then the high-height case is C ≥ A2 −AB.
Theorem 16. The Heisenberg group H(Z) with standard generators S = {a, b}± has a positive
proportion of points with positive, negative and zero curvature, respectively: there exists  > 0 such
that
#{g ∈ Bn : κ(g) = 0}
<
< 1 − ,
#Bn
and the same is true for κ > 0 and κ < 0.
Proof. First let us describe the ball Bn in terms of the coordinates (A, B, C) of its elements. For
each (A, B) satisfying |A| + |B| ≤ n, the point (A, B, C) belongs to Bn iff C satisfies a certain
quadratic polynomial inequality in A, B—this can be read off of the word-length formula with a
little bit of work (because of the square root appearing in the high-height case and the quadratic
bound for the low-height case), or is described directly in [3].
Now let w = aA bB cC ∈ Bn and note what happens when we conjugate by generators a, b. We
have
a−1 (aA bB cC )a = aA bB cC−B ; a(aA bB cC )a−1 = aA bB cC+B ;
b−1 (aA bB cC )b = aA bB cC+A ;

b(aA bB cC )b−1 = aA bB cC−A .

At low height, for A, B fixed, we will show that the sign of κ only depends on C mod A. To see
this, note that conjugating by b± changes C by adding ±A. By (?), each of these two conjugates
changes |w| by exactly 2 in opposite directions, which cancels out in the averaging. Thus only
conjugates by a± contribute to the sign of κ.
In particular if C is a multiple of A then C/A is a whole number, so dC/Ae is preserved by
C 7→ C − B and increased by C 7→ C + B, which means that the curvature is negative overall.
On the other hand, if C = kA + 1, then dC/Ae is preserved by C 7→ C + B and decreased by
C 7→ C − B, for positive curvature overall. Generally the sign of κ in this case (low height; A, B
fixed; C varying) only depends on C mod A. To be precise, suppose C = kA + r. Then
(
(
k + 2, r > A − B
k + 1, r > B
d(C + B)/Ae =
and d(C − B)/Ae =
k + 1, r ≤ A − B
k,
r ≤ B.
Within the conditions A > B > 0, C > 0, let us further restrict to the sector 15 A ≤ B < 25 A;
clearly a positive proportion of the points in the ball satisfy these inequalities. Then of the possible
remainders r for C, at least 1/5 satisfy 1 ≤ r ≤ B (Case 1), at least 1/5 satisfy A − B < r ≤ A − 1
(Case 2), and at least 1/5 satisfy B < r ≤ A − B (Case 3). In all three cases, dC/Ae = k + 1. In
Case 1, d(C ± B)/Ae = k + 1, k, so κ > 0. In Case 2, d(C ± B)/Ae = k + 2, k + 1, so κ < 0. And in
Case 3, d(C ± B)/Ae = k + 1, k + 1, so κ = 0.
We have established that the sign of the curvature repeats periodically (mod A) at low height.
To complete the proof, we must be sure that for most of the (A, B) in the ball of radius n, the
low-height values obtained by C complete at least one period with respect to A, and that the
low-height case has positive measure. First we check that A2 − AB ≥ A (the low-height inequality
is satisfied for a full period): this is true for A ≥ 5 because 15 A ≤ B < 52 A. Finally, note that
R n R n−A 2
4
(A − AB) dB dA = n24 , which has positive measure since |Bn | is bounded above and
0 0
below by multiples of n4 .


MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

9

Remark 17. At high height, for A, B fixed, there is a pattern of positive and negative curvature
points appearing in an interval of fixed length surrounding each value of C for which C + AB = k 2
is a perfect square. Outside of these intervals, κ = 0.
This means that in a fixed fiber (A, B, ∗), almost every point has zero curvature; on the other
hand, we’ve seen that over the ball of radius n, a positive proportion of points have κ 6= 0.
We note that this proof will carry over to the Heisenberg group with any generating set. We
sketch the general proof here. There will still be a low-height/high-height distinction in arbitrary
generators, with a positive proportion of the ball in low height. (See [3], where the low-height case
is called unstable and the proportion is the positive rational number Vuns /V .) Each generating set
has a defining polygon Q in the plane given by the convex hull of the projection of its generating set.
(For the standard generators, Q is the diamond |A| + |B| ≤ n.) It is still the case that conjugation
by generators induces a linear change in the C coordinate. We can restrict to a sector of the
defining polygon bounded away from its vertices, as we did here, so that there exists h > 0 for
which (A, B) ∈ nQ and C ∈ [0, hn2 ] implies (A, B, C) ∈ Bn . This guarantees that the fibers in this
sector over each (A, B) will see a full period with respect to A and B. The word length will still
be given in (A, B, C) by a linear function with rounding in the low-height case. Thus we will get
linear inequalities determining whether κ > 0, κ < 0, or κ = 0, with each one satisfied for a positive
proportion of points in Bn .
Remark 18. In the 1976 paper [6], John Milnor shows that for any left-invariant Riemannian metric
on a nonabelian nilpotent Lie group, there are directions of strictly positive Ricci curvature and
directions of strictly negative Ricci curvature. In particular, the central direction is positively
curved, and non-central directions orthogonal to the commutator subalgebra are negatively curved.
Note that the asymptotic cone of the word metric (H(Z), {a, b}± ) is the Lie group H(R) with the
(left-invariant) L1 Carnot-Carathéodory metric, which is not Riemannian but only sub-Finsler. The
work here shows that this metric on H(R) behaves quite differently from the Riemannian ones
studied by Milnor: the x-direction is still negatively curved, as in the Riemannian case (because
the conjugate of an by b± has length n + 2 for n ≥ 1), but now the z-direction (the center) has
zero Ricci curvature.
4. Positively curved directions in CAT(0) and hyperbolic groups
4.1. A CAT(0) example. We will build a family of CAT(0) groups which have points of positive
curvature. First we recall the following Proposition from [2].
Proposition 19 (Bridson-Haefliger pg. 353, Prop 11.13). Let X and A be non-positively curved
spaces. If A is compact and φ, ψ : A → X are local isometries, then the quotient of X t A by the
equivalence relation generated by [(a, 0) ∼ φ(a) and (a, 1) ∼ ψ(a)] is non-positively curved.
We can now prove the following.
Theorem 20. For n ≥ 3, k ≥ 2, the group
n
n−2
Gn,k = hx, y, a1 , . . . , ak | ai xn a−1
= y n−2 , a−1
i
i
i x ai = y

is CAT(0). In each such group, the string xn is geodesic (i.e., |xn | = n), and κ(xn ) > 0.
Proof. Take a rose R with 2 petals one of length n and one of length n − 2. Given a rose S with
two petals both of length n(n − 2) there are two local isometries φ, ψ : S → R wrapping the loops
around the loops in R the appropriate number of times. Doing this k times will give a non-positively
curved quotient by the above proposition. A simple application of Seifert-van Kampen shows that
the fundamental group of this space is Gn,k .
Suppose xn is not geodesic. Then there is a geodesic w such that w = xn in G and |w| < n. Using
HNN normal forms, w has normal form xn and so there must be a “pinch,” i.e., w decomposes as

10

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

w1 ai w2 a− w3 , where w2 ∈ hxn , y n−2 i. However, since |w| < n we have |w2 | < n − 2 which implies
w2 is the empty word, giving a contradiction.
n
n−2
Thus we have |xn | = n, and by construction, for all i, |a−1
| = n − 2, and similarly
i x ai | = |y
−1
−1 n
n −1
for ai . Additionally, |x x x| = n, |xx x | = n, and by the triangle inequality, |y −1 xn y| ≤ n + 2,
and similarly for |yxn y −1 | ≤ n + 2. All together, we get
GenCon(xn ) ≤

1
(2k(n − 2) + 2n + 2(n + 2)) ≤ n.
2k + 4

This gives κ(xn ) = 1 − n1 (GenCon(xn )) > 0, as desired.



4.2. A hyperbolic example. Before we look for a hyperbolic group with such a property we
start with the following useful computation for products. Let us adopt the notation that if S1 , S2
are generating sets for G1 , G2 , respectively, then S1  S2 will denote the split generating set
S = (S1 × {e}) ∪ ({e} × S2 ) for the product G1 × G2 .
Proposition 21 (Product formula). Let G1 and G2 be groups with generating sets S1 , S2 respectively. Let S = S1  S2 be the split generating set for G1 × G2 . Then
GenCon((x, y)) =

|S1 | GenCon(x) + |S1 ||y| + |S2 ||x| + |S2 | GenCon(y)
.
|S1 | + |S2 |

Proof. We will compute (|S1 | + |S2 |) GenCon((x, y)). This is just the sum of the lengths of all
conjugates of (x, y).
X
X
X
|s−1 (x, y)s| =
|(s−1
|(e, s−1
1 , e)(x, y)(s1 , e)| +
2 )(x, y)(e, s2 )|
s1 ∈S1

s∈S

=

X

s2 ∈S2

|(s−1
1 xs1 , y)|

s1 ∈S1

=

X

+

X

|(x, s−1
2 ys2 )|

s2 ∈S2

(|s−1
1 xs1 |

+ |y|) +

s1 ∈S1

X

(|s−1
2 ys2 | + |x|)

s2 ∈S2

= |S1 ||y| + S2 ||x| +

X

|s−1
1 xs1 | +

s1 ∈S1

X

|s−1
2 ys2 |

s2 ∈S2

= |S1 | GenCon(x) + |S1 ||y| + |S2 ||x| + |S2 | GenCon(y).



Theorem 22. There is a non-elementary hyperbolic group and a sequence of elements wi such
that κ(wi ) > 0.
Proof. Consider two random reduced spellings x, y ∈ F (a, b) = ha, b | ∅i of length l and let w1 = axa
and w2 = y. Then for any  > 0, the following properties hold with positive probability as l → ∞:
• They are cyclically and freely reduced,
• ha, b | w1 , w2 i is a C 0 () small cancellation group.
Fix some such w1 , w2 .
Consider the group G = ha, b, t | t−1 w1 t = w2 i, and let S = {a, b, t}± denote its generators. By
the above hypothesis, we can fix  = 1/6 and choose w1 , w2 as relators presenting a C 0 (1/6) small
cancellation group, which is necessarily a non-elementary hyperbolic group. By small cancellation
any trivial word contains at least half a relation, therefore w1 is a geodesic spelling in the group G.
We have |w1 | = l + 2 and |w2 | = l.
Consider the lengths of the 6 conjugates of w1 , recalling that w1 starts and ends with a.
|a−1 w1 a| = l + 2,

|t−1 w1 t| = l,

|b−1 w1 b| ≤ l + 4,

|aw1 a−1 | = l + 2,

|tw1 t−1 | ≤ |w1 | + 2 = l + 4,

|bw1 b−1 | ≤ l + 4.

Thus we have GenCon(w1 ) ≤

6l+16
6

= |w1 | + 23 .

MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

11

The hyperbolic group we are constructing to prove the theorem is the group G × Symm(4) with
generating set S  Spos , where Spos is the generating set from Proposition 4. Note that |σ| = 2 in
these generators. From the proof of Proposition 4, we know that GenCon(σ) = 26
21 . We can now
compute the curvature κ((w1 , σ)) using the formula from Proposition 21, obtaining
6l + 16 + 12 + 21(l + 2) + 26
27l + 96
32
=
=l+
<l+4
27
27
9
1
GenCon((w1 , σ)) > 0.
This gives us positive curvature: κ((w1 , σ)) = 1 − l+4
To get an infinite sequence of words, let vn = w1 t−1 w2n tw1 . This is a geodesic word of length
nl + 2 + 2(l + 2) in (G, S). Conjugating vn by a or a−1 preserves length, conjugating by t will
shorten it by 2 and the other three conjugations (by t−1 , b, b−1 ) will lengthen it by at most 2. Thus,
we get GenCon(vn ) ≤ |vn | + 23 . On the other hand, so we get
GenCon((w1 , σ)) ≤

GenCon((vn , σ)) ≤ |vn | +

38
< |vn | + 2.
27

Thus we can see that we have κ((vn , σ)) > 0.



5. Behavior under isometric embeddings
Recall the notation S1  S2 = (S1 × {e}) ∪ ({e} × S2 )
Theorem 23 (Positively curved embedding). Let G be any group with generating set S. For
sufficiently large n, there is an isometric embedding i : G → G × Symm(n) such that κ(i(g)) > 0
for all g ∈ G with respect to a generating set S  Spos . Moreover, i is boundedly far from a
homomorphism: d(i(gh), i(g)i(h)) ≤ 2.
Proof. Let σ = (1 . . . n) ∈ Symm(n) and let Spos = Symm(n) r {e, σ}± be the generating set for
Symm(n) designed to make κ(σ) > 0, as in Proposition 4.
Consider the map i : G → G × Symm(n) defined by i(g) = (g, σ). Then by Proposition 21 we
can write
 (|S| + |Spos |)|(g, σ)| + |S|(GenCon(g) − |g|) + |Spos |(GenCon(σ) − |σ|)
GenCon (g, σ) =
|S| + |Spos |
|S|(GenCon(g) − |g|) + |Spos |(GenCon(σ) − |σ|)
=|(g, σ)| +
.
|S| + |Spos |
To have positive curvature at the point (g, σ) we require |S|(GenCon(g) − |g|) + |Spos |(GenCon(σ) −
|σ|) to be negative. Since S is fixed and GenCon(g) − |g| ≤ 2, we must pick n large enough so
that |Spos |(GenCon(σ) − |σ|) < 2|S|. From Proposition 4, |Spos |(GenCon(σ) − |σ|) = n! + 2n − 6 −
2(n! − 3) = −n! + 2n. Taking n large we can ensure
 −n! + 2n + 2|S| < 0. Thus for sufficiently large
n we have GenCon((g, σ)) < |(g, σ)| and κ (g, σ) > 0.

In an exactly similar fashion, we get a corresponding statement for negative curvature.
Theorem 24 (Negatively curved embedding). Let G be a group with generating set S. For
sufficiently large n, there is an isometric embedding i : G → G × Symm(n) such that κ(i(g)) < 0
for all g ∈ G with respect to a generating set S  Sneg . Moreover, i is boundedly far from a
homomorphism: d(i(gh), i(g)i(h)) ≤ 1.
Proof. Let Sneg (n) = {(12), (23), . . . (n−1 n), σ ± } be the generating set for Symm(n) designed to
make κ(σ) < 0, as in Proposition 4. Take the embedding i : G → G × Symm(n) defined by i(g) =
|S|(GenCon(g)−|g|)+|Sneg |(GenCon(σ)−|σ|)
(g, σ), as above. To have negative curvature at the point (g, σ) we require
|S|+|Sneg |
to be greater than 0. Since S is fixed and GenCon(g) − |g| ≥ −2, we must pick n large enough
so that |Sneg |(GenCon(σ) − |σ|) > −2|S|. From Proposition 4, |Sneg |(GenCon(σ) − |σ|) = 2n − 2.
Taking n > |S|
 we get that 2n − 2 − 2|S| > 0. Thus for sufficiently large n GenCon (g, σ) > |(g, σ)|
and κ (g, σ) < 0.


12

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

In both examples above the embedding is quasi-dense. If we relax this, we can make the negative
curvature embedding a homomorphism.
Theorem 25 (Negatively curved homomorphic embedding). Let G be a group with generating set
T . There exists a group H and a homomorphism φ : G → H such that:
(1) φ is an isometry.
(2) κ(φ(g)) < 0 for all g ∈ G r {e}.
In fact, κ(h) < 0 for all h ∈ H r {e}.
Proof. Let Fn be the free group of rank n with the standard generating set U . We defer the choice
of n until later. Let H = G ∗ Fn with the generating set S = T ∪ U . Then φ(g) = g defines a
homomorphism which is an isometry onto its image.
We must now compute GenCon(g) for g ∈ G. Let u be a generator of Fn . The word u−1 gu is a
geodesic in the group G ∗ Fn and so this element has length |g| + 2. Thus,
GenCon(H, S, g) =

|T | GenCon(G, T, g) + 2n(|g| + 2)
.
|T | + 2n

Since GenCon(G, T, g) ≥ |g| − 2, taking n > |T2 | , we have GenCon(H, S, g) > |g|. Thus, κ(g) < 0.
Let h be an element of H. If one geodesic representative starts with an element of G, then all
geodesic representatives will start with a letter of G. Similarly, if any geodesic representative ends
with a letter of G, then all geodesic representatives end with a letter of G.
We now split into cases. Firstly, consider the case that both the first and last letters of h are in
G. In this case we see that every element of Fn lengthens this word. Thus taking n large enough
we can ensure such elements have negative curvature.
Secondly, for an element that has a geodesic representative where both the first and last letter
are in Fn we see that all elements of T will lengthen this element. From the calculation in Example
5 we see that for any n ≥ 1 these elements will have negative curvature.
Finally consider the case that a geodesic representative starts with a letter of T and ends with a
letter of U . Conjugating by elements of T will either preserve the length or make the word longer.
Conjugating by U will have a similar effect. Taking n ≥ 2 we see that there is an element of U
which lengthens the word and thus we get negative curvature.
This completes the proof that the group has negative curvature everywhere.

Recall the well-known fact that no hyperbolic group has a subgroup isomorphic to Z2 . So
using the above construction with G = Z2 , we’ve constructed a non-hyperbolic group with every
non-identity element negatively curved.

6. Curvature outside a ball
Since generators are always nonpostively curved (see Prop 1(5)), no nontrivial group can have
positive curvature at all points. What happens when we assume that κ(g) > 0 for all g outside a
ball of finite radius?
Theorem 26. Let G be a group generated by S and suppose for some R ∈ N we have κ(g) > 0 for
all g 6∈ BR . Then G is a finite group.
Proof. Define An = S2n ∪ S2n+1 to be an annulus in the Cayley graph. For all g ∈ G, sP
∈ S, let
wg,s .
wg,s = |g|−|s−1 gs| measure the amount that g is shortened by conjugation by s. Let cn =
Sn ×S

Noting that for g ∈ Sn we have |g| = n, the following chain of equalities relating cn to κ(g).

MEDIUM-SCALE CURVATURE FOR CAYLEY GRAPHS

cn =

X

X

wg,s =

(g,s)∈Sn ×S



13



X
X 
|S|·|g| −
|s−1 gs|
|g| − |s−1 gs| =
s∈S

g∈Sn

(g,s)∈Sn ×S


X
X 
X 
S1 (g) 
κ(g).
1−
= n|S|
|S|·|g| − |S|·S1 (g) = n|S|
=
n
g∈Sn

g∈Sn

g∈Sn

Thus for n > R we have cn > 0.
Define the following sets:
Kn = {(g, s) ∈ An × S | s−1 gs ∈ An−1 } ;

Jn = {(g, s) ∈ An × S | s−1 gs ∈ An+1 };

Ln = {(g, s) ∈ Sn × S | wg,s = 1} ;

Un = {(g, s) ∈ Sn × S | wg,s = −1}.
P
P
Let kn = Kn wg,s . The generating set S is closed under inversion so, Ln+1 wg,s = − Un wg,s
P
P
and Jn wg,s = − Kn+1 wg,s = −kn+1 .
For n  R we have
X
X
0 < c2n + c2n+1 =
wg,s +
wg,s
P

(g,s)∈S2n ×S

=

X

wg,s +

(g,s)∈Kn

=

X
X

X

wg,s +

(g,s)∈L2n+1

wg,s +

(g,s)∈Kn

=

(g,s)∈S2n+1 ×S

X

X

wg,s +

(g,s)∈U2n

X

wg,s

(g,s)∈Jn

wg,s

(g,s)∈Jn

wg,s −

(g,s)∈Kn

X

wg,s

(g,s)∈Kn+1

= kn − kn+1 .
We conclude that for indices bigger than R, the sequence (kn ) is strictly decreasing.
Positive curvature ensures that every element of S2n has at least one generator which conjugates
it into An−1 , so we have
|S2n | ≤ kn ≤ 2|Kn | ≤ 2|S|·|An |.
We are now ready to assemble these facts. If G has linear growth it is virtually Z and we can
appeal to Proposition 13. Thus assume G is a group with superlinear growth. Since |S2n | → ∞, we
see that for m  n  R we get
|S2m | ≤ km < kn ≤ 2|S|·|An | ≤ 4|S||S2n+1 |,
giving a contradiction.


7. Questions for future study

We have seen that only finite groups have positive curvature outside a ball. It seems natural to
conjecture that negative curvature outside a ball implies exponential growth, and to hope for a
similar argument.
Finally, one reasonable critique of this definition of curvature is that it is somehow too local,
since we based our comparisons on spheres of radius 1. Some of the anomalous behavior (such as
positive curvature in hyperbolic groups) might be better controlled by evaluating κB
r (x) where r
is “tuned”
as
a
function
of
|x|.
For
instance
it
would
be
interesting
to
study
the
r
= |x| case or
p
the r = |x| case, both for our comparison curvature and for Ollivier’s transportation curvature,
where these variants could give a promising way to evaluate the curvature of large but finite graphs.

14

ASSAF BAR-NATAN, MOON DUCHIN, AND ROBERT KROPHOLLER

References
[1] Sébastien Blachère, Word distance on the discrete Heisenberg group. Colloq. Math. 95 (2003), no. 1, 21–36.
[2] Martin R. Bridson and André Haefliger Metric spaces of nonpositive curvature. Grundlehren der Mathematischen
Wissenschaften [Fundamental Principles of Mathematical Sciences], 319. Springer-Verlag, Berlin, 1999.
[3] Moon Duchin and Christopher Mooney, Fine asymptotic geometry in the Heisenberg group. Indiana Univ. Math.
J. 63 (2014), no. 3, 885–916.
[4] Robin Forman, Bochner’s method for cell complexes and combinatorial Ricci curvature. Discrete Comput.
Geom., 29(3), 323–374, 2003.
[5] Yong Lin and Shing-Tung Yau, Ricci curvature and eigenvalue estimate on locally finite graphs. Math. Res.
Lett., 17(2): 343–356, 2010.
[6] John Milnor, Curvatures of left invariant metrics on Lie groups. Advances in Math. 21 (1976), no. 3, 293–329.
[7] Yann Ollivier, Ricci curvature of metric spaces. C. R. Math. Acad. Sci. Paris 345 (2007), no. 11, 643–646.
[8] Yann Ollivier, Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256 (2009), no. 3, 810–864.
[9] Yann Ollivier, A survey of Ricci curvature for metric spaces and Markov chains. Probabilistic approach to
geometry, 343–381, Adv. Stud. Pure Math., 57, Math. Soc. Japan, Tokyo, 2010.
[10] Yann Ollivier, A visual introduction to Riemannian curvatures and some discrete generalizations. Analysis and
geometry of metric measure spaces, 197–220, CRM Proc. Lecture Notes, 56, Amer. Math. Soc., Providence, RI,
2013.

