A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

arXiv:1612.06638v2 [math.MG] 6 Jan 2017

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG
Abstract. We give a characterization for asymptotic dimension growth. We
apply it to CAT(0) cube complexes of finite dimension, giving an alternative proof
of N. Wright’s result on their finite asymptotic dimension. We also apply our new
characterization to geodesic coarse median spaces of finite rank and establish
that they have subexponential asymptotic dimension growth. This strengthens a
recent result of J. S̆pakula and N. Wright.

1. Introduction
The concept of asymptotic dimension was first introduced by Gromov [15]
in 1992 as a coarse analogue of the classical topological covering dimension.
It started to attract much attention in 1998 when Yu proved that the Novikov
higher signature conjecture holds for groups with finite asymptotic dimension
(FAD) [30]. A lot of groups and spaces are known to have finite asymptotic
dimension. Among those are, for instance, finitely generated abelian groups, free
groups of finite rank, Gromov hyperbolic groups [14, 24], mapping class groups
[5], CAT(0) cube complexes of finite dimension [29], see [3] for an excellent survey
of these and other results. Recently Behrstock, Hagen and Sisto introduced the
powerful new notion of hierarchically hyperbolic spaces and showed that these
have finite asymptotic dimension [1], recovering a number of the above results,
including notably mapping class groups and a number of CAT(0) cube complexes.
On the other hand, there are many groups and spaces with infinite asymptotic
dimension. Examples are the wreath product Z≀Z, the Grigorchuk group [27], the
Thompson groups, etc. Generalizing FAD, Dranishnikov defined the asymptotic
dimension growth for a space [13]; if the asymptotic dimension growth function
is eventually constant then the space has FAD. Dranishnikov showed that the
wreath product of a finitely generated nilpotent group with a finitely generated
FAD group has polynomial asymptotic dimension growth. He also showed that
polynomial asymptotic dimension growth implies Yu’s Property A, and, hence,
the coarse Baum-Connes Conjecture, provided the space has bounded geometry
[31]. Later, Ozawa [22] extended this result to spaces with subexponential growth;
see also [21]. Bell analyzed how the asymptotic dimension function is affected by
various group-theoretical constructions [4].
2010 Mathematics Subject Classification. 20F65, 20F67, 20F69, 51F99.
Key words and phrases. Asymptotic dimension growth, CAT(0) cube complex, coarse median
space, mapping class group.
Partially supported by the European Research Council (ERC) grant of Goulnara ARZHANTSEVA, no. 259527 and the Sino-British Fellowship Trust by Royal Society.
1

2

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

In this paper, we give an alternative characterization for the asymptotic dimension growth function which is inspired by Brown and Ozawa’s proof of Property A
for Gromov’s hyperbolic groups, [9, Theorem 5.3.15], which is in turn inspired by
[17]. We use this to study two notable examples: CAT(0) cube complexes of finite
dimension and coarse median spaces of finite rank.
The techniques used to study these examples are developments of those used
by S̆pakula and Wright [28] to establish Property A for uniformly locally finite
coarse median spaces of finite rank. As a byproduct, we obtain a new proof
of finite asymptotic dimension for CAT(0) cube complexes which allows one to
explicitly construct the required controlled covers. This compares with Wright’s
original proof, [29], which is discussed below.
CAT(0) cube complexes are a nice class of non-positively curved spaces, first
studied by Gromov who gave a purely combinatorial condition for recognizing
the non-positive curvature of cube complexes [14]. Many well-known groups
act properly on CAT(0) cube complexes. For instance, right-angled Artin groups,
many small cancellation groups, and Thompson’s groups admit such actions. This
makes it possible to deduce properties of these groups from the corresponding
properties of the CAT(0) cube complexes.
In 2010, Wright [29] proved that the asymptotic dimension of a CAT(0) cube
complex X is bounded by its dimension. He proved this by constructing a family
of ε−Lipschitz cobounded maps to CAT(0) cube complexes of (at most) the same
dimension indexed by ε > 0. We use our characterization for finite asymptotic
dimension to give a direct proof of this result. Namely, we construct uniformly
bounded covers with suitable properties. Being more explicit, this proof loses,
however, the sharp bound on the asymptotic dimension. Thus, we give an alternative proof of the following non-quantitative variant of Wright’s theorem:
Theorem 1.1. Let X be a CAT(0) cube complex of finite dimension, then X has finite
asymptotic dimension.
The key point in our approach is to analyse the normal cube path distance on
the cube complex, introduced by Niblo and Reeves [18]. We consider the ball
with respect to the normal cube path distance rather than to the ordinary edgepath distance. We decompose such a ball into intervals and use induction on
the dimension in order to construct some “separated” net satisfying a suitable
consistency property. In the process, we give a detailed analysis of normal balls
and normal spheres (i.e. balls and spheres with respect to the normal cube path
distance). See Section 4 for all details.
Our second application is to coarse median spaces. They were introduced
by Bowditch as a coarse variant of classical median spaces [6]. The notion of a
coarse median group leads to a unified viewpoint on several interesting classes
of groups, including Gromov’s hyperbolic groups, mapping class groups, and
CAT(0) cubical groups. Bowditch showed that hyperbolic spaces are exactly
coarse median spaces of rank 1, and mapping class groups are examples of coarse

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

3

median spaces of finite rank [6]. He also established interesting properties for
coarse median spaces such as Rapid Decay, the property of having quadratic
Dehn function, etc.
Intuitively, a coarse median space is a metric space equipped with a ternary
operator (called the coarse median), in which every finite subset can be approximated by a finite median algebra. In these approximations the coarse median
is approximated by an actual median with the distortion being controlled by the
metric. This extends Gromov’s observation that in a δ-hyperbolic space finite
subsets can be well approximated by finite trees.
Recently, S̆pakula and Wright proved that a coarse median space with finite
rank and at most exponential volume growth has Property A [28]. Following
their proof and using our characterization for asymptotic dimension growth, we
obtain the following result:
Theorem 1.2. Let X be a geodesic coarse median space with finite rank and at most
exponential volume growth, then X has subexponential asymptotic dimension growth.
Hierarchically hyperbolic spaces are examples of coarse median spaces, see [2],
hence our theorem is broader in scope, though with a weaker conclusion, than the
finite asymptotic dimension result proven in [1]. We expect the following general
result.
Conjecture 1.3. Every geodesic coarse median space with finite rank has finite asymptotic
dimension.
By a result of Ozawa [22], subexponential asymptotic dimension growth implies
Property A, thus, our theorem strengthens the result of [28].
The paper is organized as follows. In Section 2, we give some preliminaries
on asymptotic dimension growth, CAT(0) cube complexes, and coarse median
spaces. In Section 3, we provide a characterization of the asymptotic dimension
growth function, and, as a special case, give a characterization of finite asymptotic
dimension. Sections 4 and 5 deal with CAT(0) cube complexes: in Section 4, we
study normal balls and spheres which are essential in our approach to prove
Theorem 1.1 in Section 5. Section 6 deals with the coarse median case, and we
prove Theorem 1.2 there.
2. Preliminaries
2.1. Asymptotic Dimension. The notion of asymptotic dimension was first introduced by Gromov in 1993 [15] as a coarse analogue of the classical Lebesgue
topological covering dimension. See also [3].
Let (X, d) be a metric space and r > 0. We call a family U = {Ui } of subsets in X
r−disjoint, if for any U , U′ in U, d(U, U′) > r, where d(U, U′) = inf {d(x, x′) : x ∈
U, x′ ∈ U′ }. We write
G
Ui
r−dis joint

4

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

for the union of {Ui }. A family V is said to be uniformly bounded, if mesh(V) =
sup {diam(V) : V ∈ V} is finite. Let U = {Ui } be a cover of X and r > 0. We define
the r−multiplicity of U, denoted by mr (U), to be the minimal integer n such that
for any x ∈ X, the ball B(x, r) intersects at most n elements of U. As usual, m(U)
denotes the multiplicity of a cover U, that is the maximal number of elements of
U with a non-empty intersection. A number λ > 0 is called a Lebesgue number of
U, if for every subset A ⊆ X with diameter 6 λ, there exists an element U ∈ U
such that A ⊆ U. The Lebesgue number L(U) of the cover U is defined to be the
infimum of all Lebesgue numbers of U.
Definition 2.1 ([15]). We say that the asymptotic dimension of a metric space X does
not exceed n and we write asdim X 6 n, if for every r > 0, the space X can be
covered by n + 1 subspaces X0 , X1 , . . . , Xn , and each Xi can be further decomposed
into some r−disjoint uniformly bounded subspaces:
X=

n
[

Xi ,

i=0

Xi =

G
r − disjoint
j∈N

Xij , and sup diam Xij < ∞.
i, j

We say asdim X = n, if asdim X 6 n and asdim X is not less than n.
Here are basic examples of spaces and groups with finite asymptotic dimension.
Example 2.2 ([20], [24]).
1) asdim Zn = n for all n ∈ N, where Z is the group of integers;
2) Gromov’s δ-hyperbolic spaces, e.g., word hyperbolic groups, have finite asymptotic
dimension.
From the definition, it is easy to see that the asymptotic dimension of a subspace
is at most that of the ambient space. There are other equivalent definitions of
asymptotic dimension. We list one here for a later use, and guide the reader to [3]
for others.
Proposition 2.3 ([3]). Let X be a metric space, then asdim X 6 n if and only if for any
r > 0, there exists a uniformly bounded cover U of X, such that mr (U) 6 n + 1.
2.2. Asymptotic Dimension Growth.
LLet us consider the direct sum of infinitely
many copies of the integers: G =
Z. Since for any n ∈ N, the group Zn
∞

is contained in G, by the above mentioned results, G has infinite asymptotic
dimension. In order to deal with such groups/spaces, Dranishnikov studied the
following concept as a generalization of the property of having a finite asymptotic
dimension.
Definition 2.4 ([13]). Let (X, d) be a metric space. Define a function
adX (λ) = min{m(U) : U is a cover of X, L(U) > λ} − 1,
which is called the asymptotic dimension function of X.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

5

Note that adX is monotonic and
lim adX (λ) = asdim (X).

λ→∞

Like in the case of the volume function, the growth type of the asymptotic
dimension function is more essential than the function itself. Recall that for
f, g : R+ → R+ , we write f  g, if there exists k ∈ N, such that for any x > k,
f (x) 6 kg(kx + k) + k. We write f ≈ g if both f  g and g  f . It is clear that “ ≈ ” is
an equivalence relation. We define the growth type of f to be the ≈-equivalence
class of f . Define the asymptotic dimension growth of X to be the growth type of
adX .
By a result of Bell and Dranishnikov, the growth type of the asymptotic dimension function is a quasi-isometric invariant.
Proposition 2.5 ([4, 13]). Let X and Y be two discrete metric spaces with bounded
geometry. If X and Y are quasi-isometric, then adX ≈ adY . In particular, the asymptotic
dimension growth is well-defined for finitely generated groups.
We give an alternative (equivalent) definition of the asymptotic dimension
growth that is used in our characterization.
Lemma 2.6. Let X be a metric space, and define
f X ≈ adX .
Then ad

f X (λ) = min{ mλ (U) : U is a cover of X} − 1.
ad

Proof. Given λ > 0, suppose U is a cover of X with L(U) > λ. For any U ∈ U,
define the inner λ−neighborhood of U to be
N−λ (U) = X \ Nλ (X \ U),
where Nλ denotes the usual λ-neighborhood of the set, and we define
N−λ (U) = {N−λ (U) : U ∈ U}.
Since L(U) > λ, N−λ (U) is still a cover of X. By definition, it is obvious that
f X  adX .
mλ(N−λ (U)) 6 m(U), which yields ad
Conversely suppose U is a cover of X. Consider Nλ (U), which has Lebesgue
number not less than λ. It is easy to show m(Nλ(U)) 6 mλ(U), which implies
fX .
adX  ad

f X as the definition for the
By the preceding lemma, we can use either adX or ad
asymptotic dimension function. Recall that if there exists a polynomial (subexponential) function f such that adX  f , then X is said to have polynomial
(subexponential) asymptotic dimension growth.
Dranishnikov has shown that polynomial asymptotic dimension growth implies Yu’s Property A, and he gave a class of groups having such property.

Proposition 2.7 ([13]). Let N be a finitely generated nilpotent group and G be a finitely
generated group with finite asymptotic dimension. Then the wreath product N ≀ G has

6

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

polynomial asymptotic dimension growth. In particular, Z ≀ Z has polynomial asymptotic
dimension growth.
2.3. CAT(0) Cube Complexes. We recall basic notions and results on the structure
of CAT(0) cube complexes. We omit some details and most of the proofs but direct
the readers to [8, 12, 14, 18, 26] for more information.
A cube complex is a polyhedral complex in which each cell is isometric to a Euclidean cube and the gluing maps are isometries. The dimension of the complex is
the maximum of the dimensions of the cubes. For a cube complex X, we can associate it with the intrinsic pseudo-metric dint , which is the minimal pseudo-metric
on X such that each cube embeds isometrically. When X has finite dimension, dint
is a complete geodesic metric on X. See [8] for a general discussion on polyhedral
complex and the associated intrinsic metric.
There is also another metric associated with X. Let X(1) be the 1-skeleton of X,
that is a graph with the vertex set V = X(0) . We equip V with the edge-path metric
d, which is the minimal number of edges in a path connecting two given vertices.
Clearly, when X(1) is connected, d is a geodesic metric on V. For x, y ∈ V, the
interval is defined by [x, y] = {z ∈ V : d(x, y) = d(x, z) + d(x, y)}, that is it consists of
all points on any geodesic between x and y.
A geodesic metric space (X, d) is CAT(0) if all geodesic triangles in X are slimmer
than the comparative triangle in the Euclidean space. For a cube complex (X, dint ),
Gromov has given a combinatorial characterization of the CAT(0) condition [14]:
X is CAT(0) if and only if it is simply connected and the link of each vertex is a
flag complex (see also [8]).
Another characterization of the CAT(0) condition was obtained by Chepoi [12]
(see also [25]): a cube complex X is CAT(0) if and only if for any x, y, z ∈ V,
the intersection [x, y] ∩ [y, z] ∩ [z, x] consists of a single point µ(x, y, z), which is
called the median of x, y, z. In this case, we call the graph X(1) a median graph;
and V equipped with the ternary operator m is indeed a median algebra [16]. In
particular, the following equations hold: ∀x, y, z, u, v ∈ V,
M1. µ(x, x, y) = x;
M2. µ(σ(x), σ(y), σ(z)) = µ(x, y, z), where σ is any permutation of {x, y, z};
M3. µ(µ(x, y, z), u, v) = µ(µ(x, u, v), µ(y, u, v), z).
Obviously, µ(x, y, z) ∈ [x, y], and [x, y] = {z ∈ V : µ(x, y, z) = z}.
Lemma 2.8. Let x, y, z, w ∈ V such that z, w ∈ [x, y]. Then z ∈ [x, w] implies w ∈ [z, y].
Proof. Since z ∈ [x, w] and w ∈ [x, y], we have µ(z, x, w) = z and µ(x, w, y) = w. So,
µ(z, w, y) = µ(µ(z, x, w), w, y) = µ(µ(z, w, y), µ(x, w, y), w) = µ(µ(z, w, y), w, w) = w,
which implies w ∈ [z, y].

Lemma 2.9. For x, y, z ∈ V and d(z, y) = 1, [x, z] ⊆ [x, y] or [x, y] ⊆ [x, z].
Proof. By Chepoi’s result [12], X(1) is a median graph, hence it is weakly modular
(see [12]). So d(x, y) , d(x, z), which implies d(x, y) = d(x, z)+1 or d(x, z) = d(x, y)+1,
i.e. [x, z] ⊆ [x, y] or [x, y] ⊆ [x, z].


A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

7

A CAT(0) cubical complex X can be equipped with a set of hyperplanes [11,
18, 19, 26]. Each hyperplane does not intersect itself, and divides the space into
two halfspaces. Given two hyperplanes h, k, if the four possible intersections of
halfspaces are all nonempty, then we say h crosses k, denoted by h ⋔ k. This
occurs if and only if h and k cross a common cube C (also denoted by h ⋔ C). Furthermore [26], given a maximal collection of pairwise intersecting hyperplanes,
there exists a unique cube which all of them cross. Thus, the dimension of X is
the maximal number of pairwise intersecting hyperplanes. We can also define
intervals in the language of hyperplanes: [x, y] consists of points which lie in all
halfspaces containing x and y.
We call a subset Y ⊆ V convex, if for any x, y ∈ Y, [x, y] ⊆ Y. Obviously,
halfspaces are convex since any geodesic crosses a hyperplane at most once [18,
26]. This also implies
d(x, y) = ♯{ hyperplane h : h separates x from y}.
2.4. Coarse Median Spaces. According to Gromov, hyperbolic spaces can be
considered locally as a coarse version of trees, in the sense that every finite subset
can be approximated by a finite tree in a controlled way [14]. If one wants to
approximate a space locally by finite median algebras (graphs), this would turn
to the definition of coarse median spaces introduced by Bowditch. See [6, 7, 32]
for details.
Definition 2.10 ([6]). Let (X, ρ) be a metric space, and µ : X3 → X be a ternary
operation. We say that (X, ρ, µ) is a coarse median space and µ is a coarse median on
X, if the following conditions hold:
C1. There exist constants K, H(0) > 0 such that ∀a, b, c, a′, b′ , c′ ∈ X,
ρ(µ(a, b, c), µ(a′ , b′ , c′ )) 6 K(ρ(a, a′ ) + ρ(b, b′ ) + ρ(c, c′)) + H(0).
C2. There exists a function H : N → [0, +∞) with the following property. For
a finite subset A ⊆ X with 1 6 |A| 6 p, there exists a finite median algebra
(Π, ρΠ , µΠ ), and maps π : A → Π, λ : Π → X such that ∀x, y, z ∈ Π, a ∈ A,
ρ(λµΠ (x, y, z), µ(λx, λy, λz)) 6 h(p),
and
ρ(a, λπa) 6 h(p).
We refer to K, H as the parameters of (X, ρ, µ). Furthermore, if there exists d ∈ N,
such that we can always choose the median algebra Π in condition (C2) above of
rank at most η, then we say X has (coarse) rank at most η.
A finitely generated group is said to be coarse median if some Cayley graph has
a coarse median.
Note that, by definition, a coarse median on a group is not required to be
equivariant under the group action.
Remark 2.11. According to Bowditch, without loss of generality, we may always
assume that µ satisfies the median axioms M1 and M2: for all a, b, c ∈ X,

8

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

M1. µ(a, a, b) = a;
M2. µ(a, b, c) = µ(b, c, a) = µ(b, a, c).
A large class of groups and spaces have been shown to be coarse median,
including Gromov’s hyperbolic groups, right-angled Artin groups, mapping class
groups, CAT(0) cube complexes, etc. [6]. Bowditch has proved that coarse median
groups have Property of Rapid Decay [7], quadratic Dehn’s function [6], etc.
This yielded a unified way to prove these properties for the above-listed groups.
Recently, S̆pakula and Wright have proved that coarse median spaces of finite
rank and of at most exponential volume growth have Yu’s Property A [28].
3. Characterization for asymptotic dimension growth
In this section, we establish a characterization for asymptotic dimension growth
and obtain several interesting consequences of this main result. For instance, we
get a characterization for a group to have finite asymptotic dimension.
Theorem 3.1. Let (X, d) be a discrete metric space, and f : R+ → R+ be a function. Then
the following are equivalent.
(1) adX  f ;
(2) There exists a function g : R+ → R+ which has the same growth type as f , such
that ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we can assign a subset S(x, k, l) ⊆ X,
satisfying:
i) ∀l ∈ N, ∃Sl > 0, such that S(x, k, l) ⊆ B(x, Sl ) for all k = 1, . . . , 3l;
ii) ∀l ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3l, ∀x ∈ X, we have S(x, k, l) ⊆ S(x, k′ , l);
iii) ∀x, y ∈ X with d(x, y) 6 l, we have:
• S(x, k − d(x, y), l) ⊂ S(x, k, l) ∩ S(y, k, l), for k = d(x, y) + 1, . . . , 3l;
• S(x, k + d(x, y), l) ⊃ S(x, k, l) ∩ S(y, k, l), for k = 1, . . . , 3l − d(x, y);
iv) ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we have ♯S(x, k, l) 6 g(l).
Proof.
• 1 ⇒ 2: By Lemma 2.6, we can assume that there exists a function g : R+ →
R+ with g ≈ f such that ∀l ∈ N, there exists a uniformly bounded cover U
of X with m3l (U) 6 g(l). Suppose U = {Ui : i ∈ I}, and choose xi ∈ Ui . For
k = 1, 2, . . . , 3l and x ∈ X, we define
S(x, k, l) = {xi : B(x, k) ∩ Ui , ∅}.
Now let us check the four properties in Condition 2.
i) If B(x, k) ∩ Ui , ∅, we can assume y ∈ B(x, k) ∩ Ui . Now d(y, xi ) 6
mesh(U), so d(x, xi) 6 k + mesh(U) 6 3l + mesh(U). In other words,
S(x, k, l) ⊆ B(x, 3l + mesh(U)).
ii) It is immediate, by our definition of sets S(x, k, l).
iii) ∀x, y ∈ X with d(x, y) 6 l, ∀k = d(x, y) + 1, . . . , 3l, we have:
S(x, k − d(x, y), l) = {xi : B(x, k − d(x, y)) ∩ Ui , ∅}.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

9

Now if B(x, k − d(x, y)) ∩ Ui , ∅, we can assume z ∈ B(x, k − d(x, y)) ∩ Ui,
i.e. z ∈ Ui and d(z, x) 6 k − d(x, y). So d(z, y) 6 k, i.e. z ∈ B(y, k) ∩ Ui . So
B(y, k) ∩ Ui , ∅, which implies
S(x, k − d(x, y), l) ⊂ S(x, k, l) ∩ S(y, k, l).
On the other hand, ∀k′ = 1, . . . , 3l − d(x, y), suppose x j ∈ S(x, k′ , l) ∪
S(y, k′ , l). We can assume that x j ∈ S(y, k′ , l), i.e. B(y, k′ ) ∩ U j , ∅, which
implies B(x, k′ + d(x, y)) ∩ U j , ∅. So we have:
S(x, k′ + d(x, y), l) ⊃ S(x, k′ , l) ∩ S(y, k′ , l).
iv) ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we have
♯S(x, k, l) = ♯{xi : B(x, k) ∩ Ui , ∅} 6 m3l (U) 6 g(l).
S
S(x, l, l). Also, ∀h ∈ H, we define Ah = {y : h ∈
• 2 ⇒ 1: ∀l ∈ N, let H =
x∈X

S(y, l, l)}. We define Ul = {Ah : h ∈ H}. Since ∀x ∈ X, if we take h ∈ S(x, l, l),
then x ∈ Ah . So Ul is a cover of X. Since ∃Sl > 0 such that S(x, l, l) ⊆ B(x, Sl ),
we know that d(h, y) 6 Sl for all y ∈ Ah , which implies mesh(Ul ) 6 Sl .
Finally, let us analyse ml (Ul ). ∀x ∈ X, consider h ∈ H with B(x, l) ∩ Ah , ∅.
Take y ∈ B(x, l) ∩ Ah , i.e. d(y, x) 6 l and h ∈ S(y, l, l). Now by assumptions
in Condition 2, we have
S(y, l, l) ⊆ S(x, l + d(x, y), l) ⊆ S(x, 2l, l).
So ml (Ul ) 6 ♯S(x, 2l, l) 6 g(l). Finally by Lemma 2.6, we have
f X 6 g ≈ f.
adX ≈ ad



Taking in the preceding theorem a constant function f , we obtain a characterization for finite asymptotic dimension.
Corollary 3.2. Let (X, d) be a discrete metric space, n ∈ N. Then the following are
equivalent:
(1) asdim X 6 n;
(2) ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we can assign a subset S(x, k, l) ⊆ X, satisfying:
i) ∀l ∈ N, ∃Sl > 0, such that S(x, k, l) ⊆ B(x, Sl ) for all k = 1, . . . , 3l;
ii) ∀l ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3l, ∀x ∈ X, we have S(x, k, l) ⊆ S(x, k′ , l);
iii) ∀x, y ∈ X with d(x, y) 6 l, we have:
• S(x, k − d(x, y), l) ⊂ S(x, k, l) ∩ S(y, k, l), for k = d(x, y) + 1, . . . , 3l;
• S(x, k + d(x, y), l) ⊃ S(x, k, l) ∩ S(y, k, l), for k = 1, . . . , 3l − d(x, y);
iv) ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we have ♯S(x, k, l) 6 n + 1.
Now we turn to the case when X is a graph, and obtain a characterization for
finite asymptotic dimension which is easier to check.
Corollary 3.3. Given a graph X = (V, E) with vertices V and edges E, and equipped with
the edge-path length metric d, then the following are equivalent:
(1) asdim X 6 n;

10

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

(2) ∀l ∈ N, ∀k = 1, 2, . . . , 3l, ∀x ∈ X, we can assign a subset S(x, k, l) ⊆ X, satisfying:
i) ∀l ∈ N, ∃Sl > 0, such that S(x, k, l) ⊆ B(x, Sl ) for all k = 1, . . . , 3l;
ii) ∀l ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3l, ∀x ∈ X, we have S(x, k, l) ⊆ S(x, k′ , l);
iii) ∀x, y ∈ X with d(x, y) = 1 (i.e. with x and y connected by an edge), we have:
S(y, k, l) ⊆ S(x, k + 1, l) for all k = 1, 2, . . . , 3l − 1;
iv) ∀l ∈ N, ♯S(x, 2l, l) 6 n + 1.
Remark 3.4. The only distinction between the above two corollaries is that in Corollary 3.3, assumption 2/iii) is required only for endpoints of an edge rather than
for an arbitrary pair of points as in Corollary 3.2. We point out that the preceding corollaries can be generalized to the case of arbitrary asymptotic dimension
growth. We will not use such a generalization, so we omit it.
Proof of Corollary 3.3.
1 ⇒ 2 is implied directly by Corollary 3.2, so we focus on 2 ⇒ 1.
S
S(x, l, l).
Following the proof of 2 ⇒ 3 in Proposition 3.1, ∀l ∈ N, let H =
x∈X

And ∀h ∈ H, define Ah = {y : h ∈ S(y, l, l)}. Define Ul = {Ah : h ∈ H}. Since
∀x ∈ X, if we take h ∈ S(x, l, l), then x ∈ Ah . So Ul is a cover of X. Since ∃Sl > 0
such that S(x, l, l) ⊆ B(x, Sl ), we know d(h, y) 6 Sl for all y ∈ Ah , which implies
mesh(Ul ) 6 Sl . Finally, let us analyse ml (Ul ). ∀x ∈ X, consider h ∈ H with
B(x, l) ∩ Ah , ∅. Take y ∈ B(x, l) ∩ Ah , i.e. d(y, x) 6 l and h ∈ S(y, l, l). By the
definition of the edge-path length metric d, we know that there exists a sequence
of vertices y = y0 , y1 , . . . , yk = x such that yi ∈ V for all i = 0, 1, . . . , k, d(yi , yi+1 ) = 1
for all i = 0, 1, . . . , k − 1, and k 6 l. Now by the hypothesis, we know:
S(y, l, l) ⊆ S(y1 , l + 1, l) ⊆ S(y2 , l + 2, l) ⊆ . . . ⊆ S(yk , l + k, l) = S(x, k + l, l) ⊆ S(x, 2l, l).
So {h ∈ H : B(x, l) ∩ Ah , ∅} ⊆ S(x, 2l, l), which implies ml (Ul ) 6 ♯S(x, 2l, l) 6
n + 1.

4. Normal cube path and normal distance
In the next two sections, we focus on CAT(0) cube complexes, and prove Theorem 1.1. We prove it by constructing a uniformly bounded cover with suitable
properties. Such a construction relies deeply on the analysis of normal balls and
spheres, which we give in this section.
Normal cube paths, which were introduced by Niblo and Reeves in [18] play
a key role in the construction of the cover. They determine a distance function
on the vertices and the balls and spheres defined in terms of this distance are
essential in our proof of Theorem 1.1.
Throughout this section we fix a CAT(0) cube complex X with a fixed vertex
x0 . The 1-skeleton X(1) of X is a graph with vertex set V = X(0) , and edge set E,
which give us the edge metric d on V. This is the restriction of the ℓ1 metric to the
0-skeleton.
4.1. Normal cube paths. Given a cube C ∈ X, we denote by St(C) the union of all
cubes which contain C as a subface.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

11

Definition 4.1 ([18]). Let {Ci }ni=0 be a sequence of cubes such that each cube has
dimension at least 1, and Ci−1 ∩ Ci consists of a single point, denoted by vi .
• Call {Ci }ni=0 a cube path, if Ci is the (unique) cube of minimal dimension
containing vi and vi+1 , i.e. vi and vi+1 are diagonally opposite vertices of Ci .
Define v0 to be the vertex of C0 diagonally opposite to v1 , and vn+1 to be the
vertex of Cn diagonally opposite to vn . The so-defined vertices {vi }n+1
are
i=0
called the vertices of the cube path, and we say the cube path is from v0 to
vn+1 .
• The length of a cube path is the number of the cubes in the sequence.
• A cube path is called normal if Ci ∩ St(Ci−1 ) = vi .
Normal cube paths in CAT(0) cube complexes behave like geodesics in trees.
More precisely, in [18], the existence and uniqueness of normal cube paths connecting any pair of vertices is established. See also [23].
Proposition 4.2 ([18]). For any two vertices x, y ∈ V, there exists a unique normal cube
path from x to y. (Note that the order is important here since in general normal cube
paths are not reversible).
Proposition 4.3 ([18]). The intersection of a normal cube path and a hyperplane is
connected. In other words, a normal cube path crosses a hyperplane at most once.
Proposition 4.4 ([18], [10]). Let {Ci }ni=0 and {D j }mj=0 be two normal cube paths in X, and
let {vi }n+1
and {w j }m+1
be the vertices of these normal cube paths. If d(v0 , w0 ) 6 1 and
i=0
j=0
d(vn+1 , wm+1 ) 6 1, then for all k, we have d(vk , wk ) 6 1.
We omit the proofs for the above three propositions, the readers can find them
in the original paper. However, let us recall the construction of the normal cube
path from x to y as follows: consider all the hyperplanes separating x from y
and adjacent to x. The key fact is that these hyperplanes all cross a unique cube
adjacent to x lying in the interval from x to y. This cube is defined to be the first
cube on the normal cube path; then one proceeds inductively to construct the
required normal cube path.
We will also need the following lemma, abstracted from [18].
Lemma 4.5. Let {Ci }ni=0 be the normal cube path, and h be a hyperplane. If h ⋔ Ci , then
∃ a hyperplane k, such that k ⋔ Ci−1 and h does not intersect with k.
Proof. Otherwise, ∀k ⋔ Ci−1 , we have h ⋔ k. Now by Lemma 2.15 in [18], we know
that there exists a cube C ∈ X, such that all such k ⋔ C and h ⋔ C, and Ci−1 is a face
of C. Moreover, C contains an edge e of Ci since h ⋔ C. So St(Ci−1 ) ∩ Ci contains e,
which is a contradiction to the definition of normal cube path.

Now for any two vertices of X, we consider all the hyperplanes separating them,
with a partial order by inclusion. More explicitly, for any x, y ∈ V, let H(x, y) be
the set of hyperplanes separating x and y. For any h ∈ H(x, y), let h− be the
halfspace containing x. Define h 6 k if h− ⊆ k− . Note that the definition depends

12

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

on the vertices we choose, and we may change them under some circumstances,
but still write h− for abbreviation. To avoid ambiguity, we point out the vertices
if necessary. We write h < k to mean a strict containment h− ( k− .
Lemma 4.6. For any h, k ∈ H(x, y), h and k do not intersect if and only if h 6 k or k 6 h.
Proof. We only need to show the necessity. Let {Ci }ni=0 be the normal cube path
from x to y, and assume h ⋔ Ci , k ⋔ C j . Since h and k do not intersect, i , j.
Assume i < j. Obviously, x ∈ h− ∩ k− , and y ∈ h+ ∩ k+ . Since h ⋔ Ci and k ⋔ C j ,
by Proposition 4.3, vi+1 ∈ h+ ∩ k− . Since h does not intersect with k, we have
h− ∩ k+ = ∅, which implies h− ⊆ k− .

Combining the above two lemmas, we have the following result on the existence
of chains in H(x, y).
Proposition 4.7. Let {Ci }ni=0 be the normal cube path from x to y, and h be a hyperplane
such that h ⋔ Cl . Then there exists a chain of hyperplanes h0 < h1 < · · · < hl−1 , hl = h
such that hi ⋔ Ci .
Proof. By Lemma 4.5, there exists a hyperplane k, such that k ⋔ Cl−1 and h does
not intersect with k. Define hl−1 = k. Inductively, we can define a sequence of
hyperplanes as required. Then the conclusion follows by Lemma 4.6.

Finally, we give a lemma used in the proof of the consistency part of our main
theorem.
Lemma 4.8. Let x0 , x, y ∈ V with [x0 , y] ⊆ [x0 , x], and let x′ , y′ be the n−th vertex on
the normal cube path from x0 to x, and to y. If x′ , y′ , then x′ < [x0 , y].
Proof. Otherwise, x′ ∈ [x0 , y]. By the construction of the normal cube path, we
know x′ is also the n−th vertex on the normal cube path from x0 to y, since
y ∈ [x0 , x]. In other words, x′ = y′ , which is a contradiction to the assumption. 
4.2. Normal metric. We define a new metric on V = X(0) using normal cube
paths [18, 23].
Definition 4.9. For any x, y ∈ V, define dnor (x, y) to be the length of the normal
cube path from x to y. We call dnor the normal metric on V.
One needs to verify that dnor is indeed a metric. It is easy to see that dnor (x, y) > 0,
and dnor (x, y) = 0 if and only if x = y. Note that the normal cube path from x to y
is not the one from y to x in general, so the symmetric relation is not that obvious.
In order to show the symmetric relation and the triangle inequality, we give the
following characterization.
Lemma 4.10. For x, y ∈ V, let < be the relation defined as above. Then
dnor (x, y) = sup{m + 1 : h0 < h1 < · · · < hm , hi ∈ H(x, y)}.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

13

Proof. Suppose {Ci }ni=0 is the normal cube path from x to y, so dnor (x, y) = n + 1.
Denote the right hand side of the equality in the lemma by n′ . Now for any chain
h0 < h1 < · · · < hm in H(x, y), by Proposition 4.3, hi intersects with just one cube,
denoted by Ck(i) . Obviously, if h, k ⋔ Ci , then h ⋔ k. So k(i) , k(j) if i , j, which
implies m 6 n, so n′ 6 n.
On the other hand, for any h ⋔ Cn , by Proposition 4.7, we have a chain of
hyperplanes h0 < h1 < · · · < hn−1 < hn = h, such that hi ⋔ Ci , which implies
n 6 n′ .

Proposition 4.11. dnor is indeed a metric on V.
Proof. By Lemma 4.10, H(x, y) = H(y, x), and as posets they carry opposite orders.
One can thus deduce dnor (x, y) = dnor (y, x). For x, y, z ∈ V, H(x, y)△H(y, z) =
H(x, z), where △ is the symmetric difference operation. The inclusions of H(x, y) ∩
H(x, z) into H(x, y) and H(y, z) ∩ H(x, z) into H(y, z) are both order preserving, and
therefore, by Lemma 4.10, we have dnor (x, z) 6 dnor (x, y) + dnor (y, z).

4.3. Normal balls and normal spheres. Recall that for any two points x, y in
V = X(0) , the interval between them is
[x, y] = {z ∈ V : d(x, y) = d(x, z) + d(z, y)}.
In other words, [x, y] is the set of vertices on the union of all the edge geodesics
from x to y. A subset Y ⊆ V is called convex, if for any x, y ∈ Y, [x, y] ⊆ Y.
Now let B(x, n) be the closed ball in the edge metric with centre x ∈ V and
radius n. Generally, B(x, n) is not convex (for example, take X = Z2 ). However, as
we will see, for the normal metric balls are convex. More precisely, we define the
normal ball with centre x ∈ V and radius n to be
Bnor (x, n) = {y ∈ V : dnor (x, y) 6 n}
and the normal sphere with centre x ∈ V and radius n to be
Snor (x, n) = {y ∈ V : dnor (x, y) = n}.
Lemma 4.12. Bnor (x, n) is convex for all x ∈ V and n ∈ N.
Proof. Given z, w ∈ Bnor (x, n), and a geodesic γ from z to w, if γ * Bnor (x, n), we
can assume u is the first vertex on γ which is not in Bnor (x, n), which implies
dnor (x0 , u) = n + 1. Let z′ be the vertex preceding u on γ, so dnor (x0 , z′ ) = n (since
dnor (z′ , u) = 1). Since d(z′ , u) = 1, there exists a unique hyperplane h separating z′
from u, so H(x0 , u) = H(x0 , z′ ) ⊔ {h}. Now according to Lemma 4.10, there exists
a chain h0 < · · · < hn−1 < h in H(x0 , u) with hi ∈ H(x0 , z′ ). Since every geodesic
intersects with any hyperplane at most once (see for example [26]), w ∈ h+ , which
implies h0 < · · · < hn−1 < h is also a chain in H(x0 , w). This is a contradiction to
dnor (x0 , w) 6 n, by Lemma 4.10.

Since the intersection of two convex sets is still convex, we have the following
corollary.
Corollary 4.13. For any x ∈ V and n ∈ N, the set [x0 , x] ∩ Bnor (x0 , n) is convex.

14

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

It is well known that for a convex subset Y in a CAT(0) cube complex and a
point v < Y, there is a unique point in Y which is closest to v (see, for example, [8]).
This statement is true both for the intrinsic CAT(0) metric on the cube complex
and the edge metric on the vertex set, and we have a similar statement for the
normal distance:
Proposition 4.14. There exists a unique point v ∈ [x0 , x] ∩ Bnor (x0 , n) such that
[x0 , x] ∩ Bnor (x0 , n) ⊆ [x0 , v].
The point v is characterized by:
d(x0 , v) = max{d(x0 , v′) : v′ ∈ [x0 , x] ∩ Bnor (x0 , n)}.
Furthermore, if dnor (x0 , x) > n, then v ∈ [x0 , x] ∩ Snor (x0 , n), which implies that v is
also the unique point in [x0 , x] ∩ Snor (x0 , n) such that
d(x0 , v) = max{d(x0 , v′ ) : v′ ∈ [x0 , x] ∩ Snor (x0 , n)}.
Proof. If there exist z , w ∈ [x0 , x] ∩ Bnor (x0 , n) such that d(x0 , z) = d(x0 , w) attains
the maximum, consider the median m = µ(z, w, x). By Corollary 4.13, m ∈ [z, w] ⊆
[x0 , x] ∩ Bnor (x0 , n), so d(m, x0) = d(z, x0 ) = d(w, x0). While m ∈ [z, x] ∩ [w, x], so
m = z = w, which is a contradiction.
By Corollary 4.13 [x0 , v] ⊆ [x0 , x] ∩ Bnor (x0 , n). Conversely, for any u ∈ [x0 , x] ∩
Bnor (x0 , n), let m = µ(u, v, x) ∈ [u, v]. By Corollary 4.13, m ∈ [x0 , x] ∩ Bnor (x0 , n).
While m ∈ [v, x], so d(m, x0) > d(v, x0), which implies m = v by the choice of v, i.e.
µ(u, v, x) = v, so v ∈ [u, x]. Now by Lemma 2.8, u ∈ [x0 , v].
Now for x, n satisfying dnor (x0 , x) > n, if v ∈ [x0 , x] ∩ Bnor (x0 , n − 1), take a geodesic
γ from v to x, and let v = y0 , y1 , . . . , yk = x be the vertices on γ. Since dnor (x0 , x) > n,
x , v, which implies k > 0. Now for y1 , since y1 ∈ [v, x], d(x0 , v) < d(x0 , y1). By the
definition of v, we know y1 < [x0 , x] ∩ Bnor(x0 , n), so y1 < Bnor (x0 , n). However, since
d(v, y1) = dnor (v, y1) = 1, we have
dnor (x0 , y1 ) 6 dnor (x0 , v) + dnor (v, y1 ) 6 n,
which is a contradiction.



To use the above proposition more flexibly, we give another characterization of
v, which can also be viewed as an alternative definition of v. In the rest of this
subsection, we fix x ∈ V and n ∈ N with dnor (x0 , x) > n.
be the normal cube path from x0 to x, and ṽ = vn be the
Proposition 4.15. Let {Ci }N
i=0
n-th vertex on this normal cube path. Then ṽ = v, which is provided by Proposition 4.14.
To prove this result, let us focus on subsets in H(x0 , x). Recall that H(x0 , x) is
endowed with the relation 6, as defined prior to Lemma 4.6.
Definition 4.16. A subset A ⊆ H(x0 , x) is called closed (under <), if ∀h ∈ A and
k < h, k ∈ A.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

15

Lemma 4.17. Let ṽ be the n-th vertex on the normal cube path from x0 to x, then H(x0 , ṽ)
is maximal in the following sense: for any closed A ⊆ H(x0 , x) which contains chains only
with lengths at most n, A ⊆ H(x0 , ṽ).
Proof. We proceed by induction on n. Suppose that the lemma holds for n − 1,
and let v′ be the (n − 1)−th vertex on the normal cube path from x0 to x. Given a
closed A ⊆ H(x0 , x) containing chains only with lengths at most n, and a maximal
chain h0 < h1 < · · · < hm in A. If m 6 n − 2, then the closed set {h ∈ A : h 6 hm }
contains chains only with lengths at most n − 1; by induction, it is contained in
H(x0 , v′) ⊆ H(x0 , ṽ). Now for m = n − 1: similarly, {h ∈ A : h 6 hn−2 } ⊆ H(x0 , v′ ),
which implies hi ⋔ Ci for i = 0, 1, . . . , n − 2. So hn−1 ⋔ Ck for some k > n − 1. If
k , n− 1, by Proposition 4.7 and the closeness of A, we get a chain in A with length
greater than n, which is a contradiction. So hn−1 ⋔ Cn−1 , i.e. hn−1 ∈ H(x0 , ṽ).

Proof of Proposition 4.15. By Proposition 4.14, ṽ ∈ [x0 , x] ∩ Bnor (x0 , n) ⊆ [x0 , v], which
implies H(x0 , ṽ) ⊆ H(x0 , v). However, H(x0 , v) is closed and contains chains
only with lengths at most n according to Lemma 4.10, so H(x0 , v) ⊆ H(x0 , ṽ) by
Lemma 4.17, which implies H(x0 , v) = H(x0 , ṽ). So H(v, ṽ) = H(x0 , v)△H(x0 , ṽ) = ∅,
which implies v = ṽ.

Finally, we characterize those points in [x0 , x] which lie in the intersection [x0 , x]∩
Snor (x0 , n). This will be used in the next subsection to decompose [x0 , x] ∩ Snor (x0 , n)
into a union of intervals.
Let Cn−1 be the n-th cube on the normal cube path from x0 to x, and v = ṽ is
the n-th vertex on the cube path as above. Let Hn be the set of all hyperplanes
intersecting with Cn−1 .
Proposition 4.18. For w ∈ [x0 , x], the following are equivalent:
1) w ∈ [x0 , x] ∩ Snor (x0 , n);
2) ∃h ∈ Hn , such that h crosses the last cube on the normal cube path from x0 to w;
3) ∃h ∈ Hn , such that h separates w from x0 and w ∈ [x0 , v].
Proof.
• 1) ⇒ 3): By Proposition 4.14, w ∈ [x0 , v]. Since dnor (x0 , w) = n, by
Lemma 4.10, the maximum length of chains in H(x0 , w) is n. Take such
a chain h0 < h1 < · · · < hn−1 in H(x0 , w) ⊆ H(x0 , v). Obviously, hi intersects
with different cubes, which implies hi ⋔ Ci . So hn−1 ∈ Hn , and it separates
w from x0 .
• 3) ⇒ 2): Since h separates w from x0 , h must cross some cube C on the
normal cube path from x0 to w. Since h ∈ Hn , we know there is a chain
h0 < h1 < · · · < hn−1 = h in H(x0 , v), which is also a chain in H(x0 , w).
So h cannot cross the first n − 1 cubes of the normal cube path from x0
to w. If h does not cross the last cube, then dnor (x0 , w) > n. However,
w ∈ [x0 , v] implies H(x0 , w) ⊆ H(x0 , v), by Lemma 4.10, dnor (x0 , v) > n, which
is a contradiction.
• 2) ⇒ 1): This is immediate, by Lemma 4.10.

16

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG


We have another description for Hn , which is implied by Proposition 4.7 directly.
Lemma 4.19. For h ∈ H(x0 , x), h ∈ Hn if and only if the maximal length of chains in
{k ∈ H(x0 , x) : k 6 h} is n.
4.4. Decomposition of [x0 , x] ∩ Snor (x0 , n). We want to decompose the set [x0 , x] ∩
Snor (x0 , n) so that we can proceed by the induction on dimension in the proof of
Theorem 1.1.
Throughout this subsection, we fix x ∈ V and n ∈ N with dnor (x0 , x) > n, and let
v be as defined in Proposition 4.14. At the end of the preceding subsection, we
have defined Hn to be the set of all hyperplanes intersecting with Cn−1 , where {Ci }
is the normal cube path from x0 to x.
Now we decompose [x0 , x]∩Snor (x0 , n) into a union of intervals with dimensions
lower than [x0 , x], and the number of these intervals can be controlled by the
dimension of [x0 , x]. This will make it possible to do induction on the dimension.
Definition 4.20. For h ∈ Hn , we define
Fh = {w ∈ [x0 , x] ∩ Snor (x0 , n) : h separates w from x0 }.
By Proposition 4.18, we immediately obtain the following two lemmas.
Lemma 4.21.
Fh = {w ∈ [x0 , x] : h crosses the last cube on the normal cube path from x0 to w}
= {w ∈ [x0 , v] : h separates w from x0 }.
S
Lemma 4.22. [x0 , x] ∩ Snor (x0 , n) = h∈Hn Fh .
By definition, we know
Fh = [x0 , x] ∩ Bnor (x0 , n) ∩ {v′ : h separates v′ from x0 },
which implies that Fh is convex. Moreover, we will show that Fh is actually an
interval.
Lemma 4.23. Let xh ∈ Fh be the point minimising d(x0 , xh ). Then Fh = [xh , v].
Proof. Since Fh is convex and xh , v ∈ Fh , so [xh , v] ⊆ Fh . On the other hand, ∀z ∈ Fh ,
let m = µ(x0 , z, xh ). So, m ∈ Fh and d(x0 , m) 6 d(x0 , xh ). By the choice of xh , we know
that d(x0 , m) = d(x0 , xh ), which implies m = xh , so xh ∈ [x0 , z]. By Proposition 4.14,
xh , z ∈ [x0 , v]. Thus, by Lemma 2.8, z ∈ [xh , v].

S
Proposition 4.24. [x0 , x] ∩ Snor (x0 , n) = h∈Hn [xh , v], and dim[xh , v] < dim[x0 , x].
Proof. We only need to show dim[xh , v] < dim[x0 , x]. For any hyperplane k crossing
[xh , v], by Proposition 4.18, k ⋔ h. So dim[xh , v] < dim[x0 , x].

Now we give another characterization for xh , which is useful in the proof of the
consistency condition of Theorem 1.1.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

17

Lemma 4.25. Let xh be the closest point to x0 on Fh , then xh is the unique point in
Bnor (x0 , n) such that h separates x0 from xh , and for any hyperplane k ⋔ h, k does not
separate xh from x0 .
Proof. Since xh ∈ Fh , we have xh ∈ [x0 , x] ∩ Bnor (x0 , n) and h separates x0 from xh .
Now for any hyperplane k ⋔ h, if k separates xh from x0 , we have xh ∈ h+ ∩ k+ and
x0 ∈ h− ∩ k− . Choose x̃h ∈ [x0 , xh ] such that x̃h ∈ h+ ∩ k− . Since k does not separate
x̃h from x0 , so d(x0 , x̃h) < d(x0 , xh). However, by Lemma 4.21, x̃h ∈ Fh , which is a
contradiction.
It remains to show that xh is the unique point satisfying these conditions. Otherwise, let x̂h be another point satisfying the hypothesis in the lemma and x̂h , xh .
Let k be a hyperplane separating x̂h from xh , and assume xh ∈ k− . Obviously,
k , h. If k ⋔ h, by hypothesis, k does not separate xh from x0 , as well as x̂h from
x0 , which is a contradiction since k separates x̂h from xh . So k does not cross h,
which implies h− ( k− by Lemma 4.6. However, x̂h ∈ k+ , so by Lemma 4.10,
dnor (x0 , xh ) < dnor (x0 , x̂h ). This is a contradiction since dnor (x0 , xh ) > n as h separates
x0 from xh .

4.5. S̆pakula and Wright’s Construction. We conclude this section with a recent application of normal cube paths, which were invoked by S̆pakula and
Wright, [28], in order to provide a new proof that finite dimensional CAT(0) cube
complexes have Yu’s Property A. The key to their proof was the construction of a
family of maps hl with the property that for any interval and any neighbourhood
of an endpoint of the interval the maps push that neighbourhood into the interval
itself. These maps were defined in terms of the normal cube paths as follows:
Definition 4.26 (The h maps). Given l ∈ N, we define hl : X → X as follows.
For x ∈ X, let hl (x) be the 3l−th vertex on the normal cube path from x to x0 if
dnor (x, x0 ) > 3l; and let it be x0 if dnor (x, x0 ) < 3l.
Lemma 4.27 ([28]). Let hl be defined as above and y ∈ B(x, 3l). Then hl (y) ∈ [x0 , x].
Proof. We only need to show that every halfspace containing x and x0 contains
also z = hl (y). For any hyperplane h such that one of the associated halfspaces,
say h+ , contains x and x0 , either y ∈ h+ or y ∈ h− . In the former case, z ∈ h+ , so we
only need to check the case that h separates x, x0 from y.
Denote by C0 , C1 , . . . , Cm the normal cube path from y to x0 , and denote by
y = v0 , v1, . . . , vm = x0 the vertices on this cube path. We shall argue that any
hyperplane separating y from x, x0 is “used” within the first d(x, y) steps on the
cube path. Suppose that the cube Ci does not cross any hyperplane h with h
separating y from x, x0. Hence every hyperplane k ⋔ Ci separates y, x from x0 , vi+1 .
If there was a hyperplane l separating y from x, x0 before Ci , then necessarily l
separates y, vi+1 from x, x0 , hence l crosses all the hyperplanes k crossing Ci . This
contradicts the maximality of this step on the normal cube path. Thus, there is no
such l, and so all the hyperplanes h separating y from x, x0 must be crossed within
the first d(x, y) steps.

18

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

Since z is the 3l−th vertex on the cube path and d(x, y) 6 3l, all the hyperplanes h
separating y from x, x0 must have been crossed before z. Thus, any such h actually
also separates y from x, x0, z.

We will use the remarkable properties of the h maps to construct the S sets
defined in our characterization of finite asymptotic dimension in the next section.
5. Finite dimensional CAT(0) cube complexes
Throughout this section, we fix a CAT(0) cube complex X of finite dimension η
and equipped with a basepoint x0 ∈ X. We will make use of the characterization
obtained in Corollary 3.3 in order to prove Theorem 1.1.
5.1. Constructing the sets S(x, k, l). By Corollary 3.3, in order to prove X has
finite asymptotic dimension, we need to find a constant N ∈ N such that ∀l ∈ N,
∀k = 1, 2, . . . , 3l, ∀x ∈ X, we can assign a subset S(x, k, l) ⊆ X, satisfying:
i)
ii)
iii)
iv)

∀l ∈ N, ∃Sl > 0, such that S(x, k, l) ⊆ B(x, Sl ) for all k = 1, . . . , 3l;
∀l ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3l, ∀x ∈ X, S(x, k, l) ⊆ S(x, k′ , l);
∀x, y ∈ X with d(x, y) = 1, S(y, k, l) ⊆ S(x, k + 1, l) for all k = 1, 2, . . . , 3l − 1;
∀l ∈ N, ♯S(x, 2l, l) 6 N + 1.

Now for l ∈ N, k = 1, 2, . . . , 3l, and x ∈ X, we define
e
S(x, k, l) = hl (B(x, k)).

It is easy to show that {e
S(x, k, l)} satisfies i) to iii), but it does not satisfy iv) above,
so we need some modification. Intuitively, we construct S(x, k, l) as a uniformly
separated net in e
S(x, k, l). To be more precise, we require the following lemma.
Lemma 5.1. There exist two constants N, K only depending on the dimension η, such
that ∀l ∈ N, ∀x ∈ V, there are subsets Cx ⊆ [x0 , x], and maps px : [x0 , x] → P(Cx ), where
P(Cx ) denotes the power set of Cx , satisfying:
• If d(x, y) = 1 and y ∈ [x0 , x], then Cx ∩ [x0 , y] = Cy , and px |[x0 ,y] = p y ;
• For z ∈ [x0 , x]and w ∈ px (z), we have d(z, w) 6 Kl;
• ∀z ∈ [x0 , x], ♯ B(z, Ml) ∩ Cx 6 N, where M = 3η + 3 + K.
We postpone the proof of the above lemma and first show how to use it to
construct S(x, k, l) (and, hence, to conclude the proof of Theorem 1.1).
Proof of Theorem 1.1. Let N, K be the constants in Lemma 5.1. ∀l ∈ N, ∀k =
1, 2, . . . , 3l, ∀x ∈ X, let e
S(x, k, l) = hl (B(x, k)) be as above, and by Lemma 4.27,
e
we know S(x, k, l) ⊆ [x0 , x]. Now we define
[
S(x, k, l) =
px (e
S(x, k, l)),
and the only thing left to complete the proof is to verify the conditions in Corollary
3.3.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

19

i) By the definition of hl , we know ∀y ∈ B(x, k), d(y, hl (y)) 6 3ηl. So for any
z∈e
S(x, k, l), d(z, x) 6 (3η + 3)l. For such z and any w ∈ px (z), by Lemma 5.1,
we know d(z, w) 6 Kl, which implies:
S(x, k, l) ⊆ B(x, (3η + 3 + K)l) = B(x, Ml).
ii) ∀l ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3l, ∀x ∈ X, we have e
S(x, k, l) ⊆ e
S(x, k′ , l). Now
immediately by the definition, S(x, k, l) ⊆ S(x, k′ , l).
iii) ∀x, y ∈ X with d(x, y) = 1, by Lemma 2.9, y ∈ [x0 , x] or x ∈ [x0 , y]. Assume the
former. Let k = 1, 2, . . . , 3l − 1. Obviously, e
S(y, k, l) ⊆ e
S(x, k + 1, l), so we have
[
[
[
e
e
S(y, k, l) =
p y (S(y, k, l)) =
px |[x0 ,y] (S(y, k, l)) =
px (e
S(y, k, l))
[
⊆
px (e
S(x, k + 1, l)) = S(x, k + 1, l).
Here we use the first part of Lemma 5.1 in the second equation. On the other
hand, e
S(x, k, l) ⊆ e
S(y, k + 1, l), so we have
[
[
S(x, k, l) =
px (e
S(x, k, l)) ⊆
px (e
S(y, k + 1, l))
[
[
e
=
px |[x0 ,y] (S(y, k + 1, l)) =
p y (e
S(y, k + 1, l)) = S(y, k + 1, l).

Here we use the first part of Lemma 5.1 in the fourth equality.
iv) By i), we know that S(x, k, l) ⊆ B(x, Ml) for all k = 1, 2, . . . , 3l. Hence, by
definition, S(x, k, l) ⊆ B(x, Ml) ∩ Cx . Now by the third part of Lemma 5.1, we
have ♯S(x, k, l) 6 N.

The last thing is to prove Lemma 5.1. We use the analysis in Section 4 to
construct Cx and px inductively. Recall that in Section 4 (Proposition 4.24), for any
l, n ∈ N, and any x ∈ X, we have
[
[x0 , x] ∩ Snor (x0 , nl) =
[xh , v],
h∈Hnl

with ♯Hnl 6 η and dim[xh , v] < dim[x0 , x]. In order to carry out induction on the
dimension of [x0 , x], we require a stronger version of Lemma 5.1, which is more
flexible on the choice of endpoints of intervals. More explicitly, we have
Lemma 5.2. There exist two constants N, K only depending on the dimension η, such
that ∀l ∈ N, ∀x̄, x ∈ V, ∃Cx̄,x ⊆ [x̄, x], and a map px̄,x : [x̄, x] → P(Cx̄,x ) satisfying:
• If d(x, y) = 1 and y ∈ [x̄, x], then Cx̄,x ∩ [x̄, y] = Cx̄,y , and px̄,x |[x̄,y] = px̄,y ;
• For z ∈ [x̄, x]and w ∈ px̄,x (z), we have d(z, w) 6 Kl;
• ∀z ∈ [x̄, x], ♯ B(z, Ml) ∩ Cx̄,x 6 N, where M = 3η + 3 + K.
It is obvious that Lemma 5.1 is implied by Lemma 5.2 (one just needs to take
x̄ = x0 ). Now we prove Lemma 5.2.
Proof of Lemma 5.2. Fix an l ∈ N. We will carry out induction on dim[x̄, x].
Given any x̄, x ∈ V with dim[x̄, x] = 1, we define
Cx̄,x = {y ∈ [x̄, x] : dnor (x̄, y) ∈ lN},

20

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

where lN = {0, l, 2l, 3l, . . .}. Since dim[x̄, x] = 1, [x̄, x] is indeed isometric to an
interval in R. We define px̄,x : [x̄, x] → P(Cx̄,x ) as follows: for any y ∈ [x̄, x], px̄,x (y)
consists of a single point which is at distance l⌊dnor (x̄, y)/l⌋ from x̄ in [x̄, y], where
⌊·⌋ is the function of taking integer part. Now it is obvious that
• If d(x, y) = 1 and y ∈ [x̄, x], then Cx̄,x ∩ [x̄, y] = Cx̄,y , and px̄,x |[x̄,y] = px̄,y ;
• For any z ∈ [x̄, x] and w ∈ px̄,x (z), we have d(z, w) 6 l;
• ∀z ∈ [x̄, x], ♯ B(z, Ml) ∩ Cx̄,x 6 3M.
Suppose for any x̄, x ∈ V with dim[x̄, x] 6 η − 1, we have defined Cx̄,x ⊆ [x̄, x]
and a map px̄,x : [x̄, x] → P(Cx̄,x ) satisfying:
• If d(x, y) = 1 and y ∈ [x̄, x], then Cx̄,x ∩ [x̄, y] = Cx̄,y , and px̄,x |[x̄,y] = px̄,y ;
(η−1)η
• For z ∈ [x̄, x] and w ∈ px̄,x (z),
 we have d(z, w) 6 2 l;
• ∀z ∈ [x̄, x], ♯ B(z, Ml) ∩ Cx̄,x 6 (3M)η−1 (η − 1)!.
Now we focus on x̄, x ∈ V with dim[x̄, x] = η. For any n ∈ N with nl 6 dnor (x̄, x),
by Proposition 4.24,
[
[
[xh , vxnl ],
Fxh =
[x̄, x] ∩ Snor (x̄, nl) =
x
h∈Hnl

x
h∈Hnl

x
where vxnl is the farthest point from x̄ in [x̄, x]∩Snor (x̄, nl), Hnl
is the set of hyperplanes
crossing the nl-th cube of the normal cube path from x̄ to x, and we also have
dim[xh , vxnl ] < dim[x̄, x]. By induction, Cxh ,vxnl and pxh ,vxnl have already been defined.
Now we define
[
Cnx̄,x =
Cxh ,vxnl ,
x
h∈Hnl

and
Cx̄,x =

⌊dnor[
(x̄,x)/l⌋

Cnx̄,x .

n=0

For any z ∈ [x̄, x], let z̃ be the nl-th vertex on the normal cube path from x̄ to z,
where n = ⌊dnor (x̄, z)/l⌋, so dnor (z̃, z) 6 l, which implies d(z̃, z) 6 ηl, and
[
[xh , vxnl ].
z̃ ∈ [x̄, x] ∩ Snor (x̄, nl) =
x
h∈Hnl

Now define

[n
o
x
px̄,x (z) =
pxh ,vxnl (z̃) : h ∈ Hnl
and z̃ ∈ [xh , vxnl] ,

and we need to verify the requirements hold for Cx̄,x and px̄,x .
First, suppose d(x, y) = 1 and y ∈ [x̄, x], and let h′ be the hyperplane separating
x from y. Given n ∈ N such that [x̄, y] ∩ Snor (x̄, nl) , ∅, by Proposition 4.15,
y
vxnl is the nl-th vertex on the normal cube path from x̄ to x, and vnl is the nl-th
vertex on the normal cube path from x̄ to y. Due to the fellow-traveller property,
y
Proposition 4.4, d(vxnl , vnl ) 6 1. By Proposition 4.14, we have
y

vnl ∈ Snor (x̄, nl) ∩ [x̄, y] ⊆ Snor (x̄, nl) ∩ [x̄, x] ⊆ [x̄, vxnl ].

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

21

Recall that H(z, w) denotes the set of all hyperplanes separating z from w. Obviously,
H(x̄, x) = H(x̄, y) ∪ {h′ },
y

y

x
which implies Hnl ⊆ Hnl
⊆ Hnl ∪ {h′ }, by Lemma 4.10 and Lemma 4.19.
y
x
If h′ ∈ Hnl
then Fxh′ ∩ [x̄, y] = ∅ by Proposition 4.18. On the other hand, ∀h ∈ Hnl
by Lemma 4.25, yh is the unique point in Bnor (x̄, nl) such that h separates x̄ from yh ,
and for any hyperplane k ⋔ h, k does not separate y from x̄. This implies yh = xh
y
x
since Hnl ⊆ Hnl
, so we can do induction for the new “base” point yh = xh and
y
y
y
x
vnl , vnl , since d(vxnl , vnl ) 6 1 and vnl ∈ [xh , vxnl ]. This implies
y

Cxh ,vxnl ∩ [xh , vnl ] = Cxh ,vy .
nl

Since Cxh ,vxnl ⊆

[xh , vxnl],

we have

Cxh ,vxnl ∩ [x̄, y] = Cxh ,vxnl ∩ [xh , vxnl ] ∩ [x̄, y] = Cxh ,vxnl ∩ [xh , µ(xh , vxnl, y)].
y

y

y

Claim: µ(xh , vxnl , y) = vnl . Indeed, if vxnl = vnl , then it holds naturally; If vxnl , vnl ,
y
y
y
then by Lemma 4.8, vxnl < [x̄, y]. Since d(vxnl , vnl ) = 1, so vxnl ∈ [vnl , y] or vnl ∈ [vxnl , y].
y
y
While the former cannot hold since [vnl , y] ⊆ [x̄, y], so vnl ∈ [vxnl , y], which implies
y

vnl ∈ [xh , y] ∩ [xh , vxnl ] ∩ [vxnl , y],
y

i.e. vnl = µ(xh , vxnl, y).
By the claim,
y

Cxh ,vxnl ∩ [x̄, y] = Cxh ,vxnl ∩ [xh , vnl ] = Cxh ,vy .
nl

Now for the above n, we have
[
 [

Cxh ,vxnl ∩ [x̄, y] =
Cnx̄,x ∩ [x̄, y] =
Cxh ,vxnl ∩ [x̄, y]
y

x
h∈Hnl

[

=

Cxh ,vy =

y

nl

[

h∈Hnl

Cyh ,vy = Cnx̄,y .
nl

y

h∈Hnl

h∈Hnl

Since Cnx̄,x ⊆ [x̄, x] ∩ Snor (x̄, nl), we have
Cx̄,x ∩ [x̄, y] =

⌊dnor[
(x̄,x)/l⌋
n=0

=

[

Cnx̄,x ∩ [x̄, y] =

[

Cnx̄,x ∩ [x̄, y]

n:[x̄,x]∩Snor (x̄,nl),∅

Cnx̄,x ∩ [x̄, y] =

n:[x̄,y]∩Snor (x̄,nl),∅

[

Cnx̄,y = Cx̄,y .

n:[x̄,y]∩Snor (x̄,nl),∅

∀z ∈ [x̄, y], one need to show that px̄,x (z) = px̄,y (z). Let z̃ be the nl-th vertex on
the normal cube path from x̄ to z, where n = ⌊dnor (x̄, z)/l⌋. By the analysis above,
we know
y

y

y

y

x
⊆ Hnl ∪ {h′ }.
d(vxnl , vnl ) 6 1, vnl ∈ [vxnl , y], xh = yh , Hnl ⊆ Hnl
y

x
For h ∈ Hnl
with z̃ ∈ [xh , vxnl ], then h ∈ Hnl , i.e. h , h′ since z̃ ∈ [x̄, y]. Now for such
h,
y

y

z̃ ∈ [x̄, y] ∩ [xh , vxnl ] = [xh , vnl ] = [yh , vnl ],

22

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

where the first equation comes from the claim above. Inductively, we know for
such h,
pxh ,vxnl (z̃) = p yh ,vy (z̃).
nl

Now by definition,

[n
o
x
pxh ,vxnl (z̃) : h ∈ Hnl
and z̃ ∈ [xh , vxnl ]
[n
o
y
=
pxh ,vxnl (z̃) : h ∈ Hnl and z̃ ∈ [xh , vxnl ]
[n
o
y
y
=
p yh ,vy (z̃) : h ∈ Hnl and z̃ ∈ [yh , vnl ]

px̄,x (z) =

nl

= px̄,y (z).
Second, for any z ∈ [x̄, x] and w ∈ px̄,x (z), assume that w ∈ pxh ,vxnl (z̃) for some
x
h ∈ Hnl
and z̃ ∈ [xh , vxnl ] as in the definition. By induction, we know d(z̃, w) 6
since dim[xh , vxnl ] 6 η − 1. So

(η−1)η
l
2

(η − 1)η
η(η + 1)
l=
l.
2
2
Third, for any z ∈ [x̄, x], consider B(z, Ml) ∩ Cx̄,x . Suppose
 n ∈ N satisfying
S
x
B(z, Ml) ∩ Cx̄,x ∩ Snor (x̄, nl) , ∅, so B(z, Ml) ∩
x [xh , v ]
, ∅, which means
h∈Hnl
nl
x
x
there exists some h ∈ Hnl such that B(z, Ml) ∩ [xh , vnl ] , ∅. For such n and h, let
z′ = µ(z, xh , vxnl ) ∈ [xh , vxnl ]. Obviously,
d(z, w) 6 d(z, z̃) + d(z̃, w) 6 ηl +

B(z, Ml) ∩ [xh , vxnl] ⊆ B(z′ , Ml) ∩ [xh , vxnl ].
By induction, we have




♯ B(z, Ml) ∩ Cxh ,vxnl 6 ♯ B(z′ , Ml) ∩ Cxh ,vxnl 6 (3M)η−1 (η − 1)!.
Now for the above z, there exist at most 3M values of n such that B(z, Ml) ∩ [x̄, x] ∩
x
Snor (x̄, nl) , ∅; and for such n, since ♯Hnl
6 η, there exist at most η hyperplanes h
x
such that B(z, Ml) ∩ [x̄, x] ∩ [xh , vnl ] , ∅. So we have
X




♯ B(z, Ml) ∩ Cx̄,x 6
♯ B(z, Ml) ∩ Cnx̄,x
n:B(z,Ml)∩[x̄,x]∩Snor (x̄,nl),∅

6

X

X 

♯ B(z, Ml) ∩ Cxh ,vxnl

x
n:as above h∈Hnl

6 3M · η · (3M)η−1 (η − 1)! = (3M)η η!.
(η−1)η

Now we take K = 2 , and N = (3M)η η! = (3K + 9η + 9)η η!, then the lemma
holds for these constants.

6. Coarse median spaces
In this section, we discuss the coarse median case, and prove Theorem 1.2. We
fix a coarse median space X with geodesic metric ρ and coarse median µ with
parameters K, H and finite rank η. The definitions and notations are the same as
in Section 2.4. According to Remark 2.11, we also assume that the coarse median
µ satisfies M1 and M2. We recall:

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

23

Theorem 6.1 ([28]). Any geodesic uniformly locally finite coarse median space of finite
rank and at most exponential growth has Property A.
Our result, Theorem 1.2, says that any coarse median space as above has subexponential asymptotic dimension growth. Thus, combining with Ozawa’s result [22], our theorem yields a strengthening of Theorem 6.1.
To prove Theorem 1.2, we use several notations and lemmas from [28]. We use
the notation x ∼s y for ρ(x, y) 6 s. Given r > 0 and a, b ∈ X, the coarse interval
[a, b]r is defined to be:
[a, b]r = {z ∈ X : µ(a, b, z) ∼r z}.
By a result of Bowditch [7], there exists a constant λ > 0 depending only on the
parameter K, H, such that for all x, y, z ∈ X, µ(x, y, z) ∈ [x, y]λ .
Also recall that the median axiom M3 holds in the coarse median case up to a
constant γ > 0 depending only on the parameters K, H: for all x, y, z, u, v ∈ X, we
have
µ(µ(x, y, z), u, v) ∼γ µ(µ(x, u, v), µ(y, u, v), z).
Actually we can take γ = 3K(3K + 2)H(5) + (3K + 2)H(0).
Given r, t, κ > 0, denote
L1 (r) = (K + 1)r + Kλ + γ + 2H(0),
L2 (r, κ) = (K + 1)r + κ + H(0), and
L3 (r, t) = 3η Kη rt + r.
We need the following lemmas from [28].
Lemma 6.2 ([28]). Let X be a coarse median space, r > 0, and let a, b ∈ X, x ∈ [a, b]λ .
Then [a, x]r ⊂ [a, b]L1 (r) .
Lemma 6.3 ([28]). Let X be a geodesic coarse median space of rank at most η. For every
κ > 0 and t > 0, there exists rt > 0, such that for all r > rt , a, b ∈ X, there exists
h ∈ [a, b]L1 (r) , such that
• ρ(a, h) 6 L3 (r, t), and
• B(a, rt) ∩ [a, b]κ ⊂ [a, h]L2 (r,κ) .
Lemma 6.4 ([28]). Let X be a coarse median space. Fix κ > 0. There exist constants
α, β > 0 depending only on the parameters of the coarse median structure and κ, such
that the following holds: let a, b, h, m ∈ X and r > 0 satisfy m ∈ [a, h]L2 (r,κ) , h ∈ [a, b]L1 (r) .
Then p = µ(m, b, h) satisfies ρ(h, p) 6 αr + β.
Proof of Theorem 1.2. The proof is based on the construction used in [28] to prove
property A, and for the readers’ convenience, we give a sketch of their proof.
In fact we will verify the stronger conditions on the S sets required to apply
Theorem 3.1. Fix a base point x0 ∈ X, and let α, β be the constants from Lemma
6.4. First apply Lemma 6.3 for κ = λ and all t ∈ N to obtain a sequence rt ∈ N,
such that the conclusion of the lemma holds. Furthermore, we can choose the rt
tr −H(0)
inductively to arrange the sequence N ∋ t 7→ lt = t 3K is increasing.

24

GOULNARA ARZHANTSEVA, GRAHAM A. NIBLO, NICK WRIGHT, AND JIAWEN ZHANG

Now fix x ∈ X, t ∈ N, and k ∈ {1, 2, . . . , 3lt}. For any y ∈ B(x, k), Lemma 6.3
applied for a = y, b = x0 and r = rt , produces a point h y ∈ [y, x0 ]L1 (rt ) . We define
S(x, k, lt ) = {h y ∈ X : y ∈ B(x, k)}.
We need to verify these sets satisfy Condition 2 in the statement of Proposition 3.1,
i.e. we need to show there exists a subexponential function f : R → R, satisfying:
i) ∀t ∈ N, ∃St > 0, such that S(x, k, lt ) ⊆ B(x, St ) for all k = 1, . . . , 3lt;
ii) ∀t ∈ N, ∀k, k′ with 1 6 k 6 k′ 6 3lt, ∀x ∈ X, we have S(x, k, lt ) ⊆ S(x, k′ , lt);
iii) ∀x, y ∈ X with ρ(x, y) 6 lt , we have:
• S(x, k − ρ(x, y), lt) ⊂ S(x, k, lt ) ∩ S(y, k, lt ), for k = ρ(x, y) + 1, . . . , 3lt;
• S(x, k + ρ(x, y), lt) ⊃ S(x, k, lt ) ∩ S(y, k, lt ), for k = 1, . . . , 3lt − ρ(x, y);
iv) ∀t ∈ N, ∀k = 1, 2, . . . , 3lt, ∀x ∈ X, we have ♯S(x, k, lt ) 6 f (lt ).
By the construction, ii) and iii) hold naturally. For i), by Lemma 6.3, we know
S(x, k, lt ) ⊆ B(x, lt + L3 (rt , t)). The only thing left is to find a subexponential function
f such that condition iv) holds. The following argument follows totally from the
proof in [28], and we omit some calculation. The readers can turn to their original
paper for more details.
Take y ∈ B(x, k), with the notation as above. Denote m y = µ(x, y, x0). Then by
Lemma 6.3, one can deduce that m y ∈ [y, h y ]L2 (rt ,λ) . Now since h y ∈ [y, x0 ]L1 (rt ) ,
Lemma 6.4 implies the point p y = µ(m y , x0 , h y ) ∈ [m y , x0 ]λ satisfies ρ(h y , p y ) 6
αrt + β. As m y = µ(x, y, x0) ∈ [x, x0 ]λ , Lemma 6.2 now implies p y ∈ [x, x0]L1 (λ) .
Consequently, we have ρ(x, p y ) 6 3lt + 3η Kη trt + rt + αrt + β, which depends linearly
on lt . Now by Proposition 9.8 in [7], the number of possible points p y is bounded by
P(lt ) for some polynomial P depending only on H, K, η and uniform local finiteness
of X. Since X has at most exponential growth, it follows that ♯S(x, k, lt ) is at most
P(lt )c′ crt for some constants c, c′ > 1. Take f (lt ) = P(lt )c′ crt and recall that in the limit
rt /lt → 0. We extend f to a function on R+ by setting f (r) := f (lt ) for r ∈ (lt−1 , lt ].
This completes the proof.


References
[1] J. Behrstock, M.F. Hagen, and A. Sisto. Asymptotic dimension and small-cancellation for
hierarchically hyperbolic spaces and groups. arXiv:1512.06071, 2015.
[2] J. Behrstock, M.F. Hagen, and A. Sisto. Hierarchically hyperbolic spaces ii: combination
theorems and the distance formula. arXiv:1509.00632, 2015.
[3] G. Bell and A. N. Dranishnikov. Asymptotic dimension in Bȩdlewo. Topology Proc, 38:209–236,
2011.
[4] G. C. Bell. Growth of the asymptotic dimension function for groups. arXiv:math/0504577,
2005.
[5] M. Bestvina, K. Bromberg, and K. Fujiwara. The asymptotic dimension of mapping class
groups is finite. arXiv:1006.1939, 2010.
[6] B. H. Bowditch. Coarse median spaces and groups. Pacific Journal of Mathematics, 261(1):53–93,
2013.
[7] B. H. Bowditch. Embedding median algebras in products of trees. Geometriae Dedicata,
170(1):157–176, 2014.

A CHARACTERIZATION FOR ASYMPTOTIC DIMENSION GROWTH

25

[8] M. R. Bridson and A. Häfliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren
der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. SpringerVerlag, Berlin, 1999.
[9] N. P. Brown and N. Ozawa. C∗ -algebras and finite-dimensional approximations, volume 88 of
Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2008.
[10] S. Campbell and G. A. Niblo. Hilbert space compression and exactness of discrete groups.
Journal of functional analysis, 222(2):292–305, 2005.
[11] I. Chatterji and G. A. Niblo. From wall spaces to CAT(0) cube complexes. International Journal
of Algebra and Computation, 15(05n06):875–885, 2005.
[12] V. Chepoi. Graphs of some CAT(0) complexes. Advances in Applied Mathematics, 24(2):125–179,
2000.
[13] A. N. Dranishnikov. Groups with a polynomial dimension growth. Geometriae Dedicata,
119(1):1–15, 2006.
[14] M. Gromov. Hyperbolic groups. In Essays in group theory, pages 75–263. Springer, 1987.
[15] M. Gromov. Asymptotic invariants of infinite groups. Geometric group theory, Vol.2, volume
182 of London Math. Soc. Lecture Note Ser., pages 1–295, 1993.
[16] J. R. Isbell. Median algebra. Transactions of the American Mathematical Society, 260(2):319–362,
1980.
[17] V. A. Kaimanovich. Boundary amenability of hyperbolic spaces. In Discrete geometric analysis,
volume 347 of Contemp. Math., pages 83–111. Amer. Math. Soc., Providence, RI, 2004.
[18] G. A. Niblo and L. D. Reeves. The geometry of cube complexes and the complexity of their
fundamental groups. Topology, 37(3):621–633, 1998.
[19] B. Nica. Cubulating spaces with walls. Algebr. Geom. Topol, 4:297–309, 2004.
[20] P. W. Nowak and G. Yu. Large scale geometry. 2012.
[21] I. Oppenheim. An intermediate quasi-isometric invariant between subexponential asymptotic dimension growth and Yu’s property A. Internat. J. Algebra Comput., 24(6):909–922, 2014.
[22] N. Ozawa. Metric spaces with subexponential asymptotic dimension growth. International
Journal of Algebra and Computation, 22(02):1250011, 2012.
[23] L. D. Reeves. Biautomatic structures and combinatorics for cube complexes. PhD thesis, University
of Melbourne, 1995.
[24] J. Roe. Hyperbolic groups have finite asymptotic dimension. Proceedings of the American
Mathematical Society, 133(9):2489–2490, 2005.
[25] M. Roller. Poc sets, median algebras and group actions. an extended study of Dunwoody’s
construction and Sageev’s theorem. Southampton Preprint Archive, 1998.
[26] M. Sageev. Ends of group pairs and non-positively curved cube complexes. Proceedings of the
London Mathematical Society, 3(3):585–617, 1995.
[27] J. Smith. The asymptotic dimension of the first Grigorchuk group is infinity. Revista Matemática
Complutense, 20(1):119–121, 2007.
[28] J. S̆pakula and N. J. Wright. Coarse medians and property A. arXiv:1602.06084, 2016.
[29] N. J. Wright. Finite asymptotic dimension for CAT(0) cube complexes. Geometry & Topology,
16(1):527–554, 2012.
[30] G. Yu. The Novikov conjecture for groups with finite asymptotic dimension. The Annals of
Mathematics, 147(2):325–355, 1998.
[31] G. Yu. The coarse Baum-Connes conjecture for spaces which admit a uniform embedding
into Hilbert space. Inventiones Mathematicae, 139(1):201–240, 2000.
[32] R. Zeidler. Coarse median structures on groups. Master’s thesis, University of Vienna, Vienna,
Austria, 2013.
Universität Wien, Fakultät für Mathematik, Oskar-Morgenstern-Platz 1, 1090 Wien, Austria.
E-mail address: goulnara.arzhantseva@univie.ac.at

School of Mathematics, University of Southampton, Highfield, SO17 1BJ, United Kingdom.
E-mail address: g.a.niblo@soton.ac.uk,wright@soton.ac.uk,jiawen.zhang@soton.ac.uk

