# Groups with finitely many Busemann points

Liran Ron-George  and  Ariel Yadin  Department of Mathematics, Ben-Gurion
University of the Negev  {lirar<EMAIL_ADDRESS>
###### Abstract.

We show that an infinite finitely generated group $G$ is virtually
$\mathbb{Z}$ if and only if every Cayley graph of $G$ contains only finitely
many Busemann points in its horofunction boundary. This complements a previous
result of the second named author and M. Tointon.

We thank Y. Glasner, Y. Hartman, A. Karlsson, T. Meyerovitch, and M. Tointon
for useful discussions. Research supported by Israel Science Foundation, grant
no. 954/21. The first author is also partially supported by the Israel Science
Foundation, grant no. 1175/18.

##  1\. Introduction

In a few important works it has been suggested to consider horofunctions as an
analogue to linear functionals, in (non-linear) general metric spaces, see
e.g. [3, 5, 6, 14] and references therein. The space of horofunctions (which
will be precisely defined below) has been fruitfully used in the study of the
geometry of metric spaces. Specifically in the case of hyperbolic spaces and
hyperbolic groups these have been used quite successfully. Less research has
been devoted to the study of horofunction boundaries in the case of “small”
groups. This is perhaps due to the fact that the space of horofunctions itself
is not invariant when switching between different Cayley graphs of the same
group. However, it seems to be true that some properties are shared by all
Cayley graphs of a given group, and it is very interesting to determine such
invariants.

Horofunctions are very well suited to finding virtual characters, that is
functions whose restriction to a finite index subgroup is a non-trivial
homomorphism into an Abelian group. In fact, as will be explained below, if a
horofunction has a finite orbit under the canonical group action, it is such a
virtual character (with the implicit finite index subgroup being the
stabilizer of the action). Finding such virtual characters is useful in many
situations, because it provides a way of splitting the group into two parts.
Specifically, if $\psi:G\to\mathbb{Z}$ is a surjective homomorphism, then
$G\cong\mathbb{Z}\ltimes K$ for $K=\mathsf{Ker}\psi$. Even though such a
decomposition is a semi-diect product, in many cases it is still useful in the
geometric or algebraic analysis. For example, the main part in the proof of
Gromov’s theorem regarding groups of polynomial growth [2] is to show that
every group of polynomial growth admits a virtual character. Most of the new
proofs of this theorem are actually proofs of this result, including Kleiner’s
proof [8] and Ozawa’s proof [9]. Even before these new proofs appeared it was
suggested by Karlsson [4] to use the horofunction boundary to provide the
required virtual character in the polynomial growth case.

####

###### Conjecture 1.1

Let $G$ be a finitely generated group of polynomial growth. Then, for any
Cayley graph of $G$ the horofunction boundary contains a finite orbit (for the
canonical group action).

See also Conjecture 1.3 in [11].

Grigorchuk has conjectured that there is a “gap” in the possible growth
functions of Cayley graphs, see [1]. Specifically, if the growth is small
enough it is conjectured that the group actually has polynomial growth. Since
horofunctions, and specifically Busemann points (see below) are related to
geodesics in the graph, these may very well be good tools to study the growth.
By Gromov’s theorem mentioned, every polynomial growth group is virtually
nilpotent and thus admits a virtual character. Walsh [12] has shown that the
action of nilpotent groups on their horofunction boundary has a finite orbit.
So we have the following (logically weaker) conjecture.

####

###### Conjecture 1.2

Let $\Gamma$ be a Cayley graph. Assume that the size of the ball of radius $r$
in $\Gamma$ is bounded by $C\exp(Cr^{\alpha})$ for some $C>0$,
$\alpha<\tfrac{1}{2}$ and all $r\in\mathbb{N}$.

Then, the horofunction boundary of $\Gamma$ contains a finite orbit for the
underlying group action.

Let us remark that even smaller growth functions in Conjecture 1.2 are of
interest. The state of the art follows from the work of Shalom & Tao [10]
proving that any group of growth bounded by $C\exp(C(\log r)(\log\log
r)^{\varepsilon})$ for some $\varepsilon>0$ is virtually nilpotent (and so
actually of polynomial growth). In forthcoming work by Szusterman and the
second named author it is shown that if every Cayley graph of small enough
growth has a finite orbit in its horofunction boundary, then the underlying
group is actually virtually nilpotent.

Part of the difficulty of understanding the horofunction boundary of a Cayley
graph, and especially connecting it to the underlying algebraic structure of
the group, is that the boundary changes when changing the specific choice of
Cayley graph. The properties of the boundary which are invariant to changing
Cayley graphs are still somewhat mysterious. As a first step in considering
such invariants, in [11] it was shown that any graph that has linear volume
growth must have finitely many Busemann points in its boundary (see below for
a precise definition of Busemann points). The other direction is not true for
general graphs, we provide an example of a graph with arbitrary growth and a
boundary consisting of just one point, see Example 4.2 below.

Our main result, Theorem 1.3, is a first step in understanding the
relationship between algebraic properties of a group and the horofunction
boundaries of its Cayley graphs. Theorem 1.3 states that an infinite finitely
generated group is virtually $\mathbb{Z}$ if and only if for every Cayley
graph there are finitely many Busemann points in its horofunction boundary. It
is also shown that these conditions are equivalent to every Cayley graph
having a finite horofunction boundary, and that when these equivalent
conditions hold, every horofunction is a Busemann point. See below for a
precise statement and definitions.

###  1.1. Notation and precise statement of results

Let $G$ be a finitely generated group. Fix a finite symmetric generating set
$S$ for $G$; that is, $S$ generates $G$ as a group, $|S|<\infty$, and
$S=S^{-1}=\\{x^{-1}\ :\ x\in S\\}$. The Cayley graph of $G$ with respect to
$S$, denoted $\Gamma(G,S)$ is the graph whose vertices are elements of $G$ and
edges are given by the relation: $\\{x,xs\\}$ is an edge for any $x\in G$ and
$s\in S$. The graph metric of $\Gamma(G,S)$ is denoted by $d_{S}$. It is easy
to check that $d_{S}$ is left-invariant in the sense that
$d_{S}(zx,zy)=d_{S}(x,y)$ for all $x,y,z\in G$. Thus it is useful to use the
notation $|x|_{S}=d_{S}(x,1)$ where $1=1_{G}$ denote the identity element in
the group $G$. When the metric is clear from the context we will omit the
subscript $d=d_{S}$ and $|x|=|x|_{S}$.

Fix some Cayley graph $\Gamma(G,S)$. Let $L(G,S)$ be the set of all functions
$h:G\to\mathbb{R}$ such that $h$ is $1$-Lipschitz (i.e. $|h(x)-h(y)|\leq
d(x,y)$ for all $x,y\in G$) and $h(1)=0$. Equip $L(G,S)$ with the topology of
pointwise convergence, and note that $L(G,S)$ is compact. The set $G$ embeds
into $L(G,S)$ by identifying $x\in G$ with the Busemann function
$b_{x}:G\to\mathbb{R}$ given by $b_{x}(y)=d(x,y)-d(x,1)$. We denote closure of
$\\{b_{x}\ :\ x\in G\\}$ in $L(G,S)$ by $\overline{\Gamma(G,S)}$ and define
the horofunction boundary, or horoboundary of $\Gamma(G,S)$ to be

$\partial\Gamma(G,S):=\overline{\Gamma(G,S)}\setminus\\{b_{x}\ :\ x\in G\\}.$

Elements of $\partial\Gamma(G,S)$ are called horofunctions. (The term metric-
functional is also used, with good reason, see [7].) One notes that all
horofunctions are integer valued (because the Busemann functions are, and we
are dealing with pointwise convergence).

A finite geodesic in $\Gamma(G,S)$ is a finite sequence
$(\gamma_{k})_{k=0}^{n}$ such that

(1) $\displaystyle\forall\ 0\leq m\leq k\leq n$ $\displaystyle\qquad
d(\gamma_{k},\gamma_{m})=k-m.$

An infinite geodesic in $\Gamma(G,S)$ is an infinite sequence
$(\gamma_{k})_{k=0}^{\infty}$ such that (1) holds for all $0\leq m\leq k$. For
simplicity, when we write geodesic we refer to an infinite geodesic, and if we
require finite geodesics we will explicitly state finite.

It is shown in Lemma 3.2 below that if $(\gamma_{n})_{n}$ is an infinite
geodesic, then $\gamma_{\infty}:=\lim_{n\to\infty}b_{\gamma_{n}}$ exists (as a
limit in $\overline{\Gamma(G,S)}$), and that
$\gamma_{\infty}\in\partial\Gamma(G,S)$. Such a horofunction
$\gamma_{\infty}\in\partial\Gamma(G,S)$ that is a limit of a geodesic is
called a Busemann point. We denote by $\partial_{b}\Gamma(G,S)$ the closure
(in $\overline{\Gamma(G,S)}$) of the set of all Busemann points. For a more in
depth discussion of Busemann points on Cayley graphs see [13] and references
therein.

The fact that any Cayley graph contains an infinite geodesic is classical, and
can be proven using König’s Lemma. (In fact, that proof shows the existence of
a bi-infinite geodesic, i.e. a sequence $(\gamma_{t})_{t\in\mathbb{Z}}$ such
that $\gamma_{0}=1$ and such that any finite subpath is a finite geodesic.
This implies that there are always at least two Busemann points in the
horoboundary. See also Karlsson’s proof (by another method) in [6] that the
horoboundary (there called metric boundary) of a finitely generated infinite
group contains at least $2$ elements.)

The horoboundary construction also provides an equivalence relation on
geodesics: two geodesics $\alpha,\beta$ are equivalent if
$\alpha_{\infty}=\beta_{\infty}$. Note that if $\alpha\cap\beta:=\\{x\ :\
\exists\ t,k\in\mathbb{N}\ ,\ \alpha_{t}=\beta_{k}=x\\}$ is infinite, then
$\alpha_{\infty}=\beta_{\infty}$. However, the opposite is not guarantied. One
may have equivalent geodesics which have an empty intersection. (It is however
true that geodesics $\alpha,\beta$ are equivalent if and only if there exists
some geodesic $\gamma$ such that
$|\gamma\cap\alpha|=|\gamma\cap\beta|=\infty$. See [12].)

Our main result is the following.

####

###### Theorem 1.3

Let $G$ be an infinite finitely generated group. The following are equivalent.

  1. (1)

$G$ is virtually $\mathbb{Z}$.

  2. (2)

For every Cayley graph of $G$ the Busemann boundary is finite.

  3. (3)

For every Cayley graph of $G$ the horofunction boundary is finite.

Moreover, when $G$ is virtually $\mathbb{Z}$ any horofunction is a Busemann
point.

Recall that for a group property $\mathcal{P}$, the property of being
virtually $\mathcal{P}$ is containing a finite index subgroup with the
property $\mathcal{P}$. Thus, virtually $\mathbb{Z}$ means containing a finite
index infinite cyclic subgroup.

###### Proof of Theorem 1.3.

$(1)\Rightarrow(2)$ was first shown in [11], and holds for general graphs of
linear growth. In Proposition 4.1 we provide a very elegant and short proof by
Sam Shepperd (communicated to us by M. Tointon).

Our main two new contributions are $(2)\Rightarrow(1)$ and the assertion that
if $G$ is virtually $\mathbb{Z}$ then every horofunction is a Busemann point.

The implication $(2)\Rightarrow(1)$ is shown in Lemma 3.1 below.

Theorem 4.3 below shows that when $G$ is virtually $\mathbb{Z}$ then in any
Cayley graph, every horofunction is a Busemann point. This gives
$(1)\Rightarrow(3)$ by combining the implication $(1)\Rightarrow(2)$ with
Theorem 4.3.

$(3)\Rightarrow(2)$ is trivial since the Busemann boundary is contained in the
horoboundary.  $\sqcap$$\sqcup$

Somewhat frustratingly, we have not proved the following.

####

###### Conjecture 1.4

Let $G$ be an infinite finitely generated group and assume that there exists
some Cayley graph of $G$ for which $\partial_{b}\Gamma(G,S)$ is finite.

Then, $G$ is virtually $\mathbb{Z}$.

##  2\. Group Action

There is a natural action of $G$ on $\overline{\Gamma(G,S)}$, given by
$x.h(y)=h(x^{-1}y)-h(x^{-1})$ for $x\in G$ and $h\in\overline{\Gamma(G,S)}$.
The following basic properties are very easy to verify, and we leave the proof
to the reader.

####

###### Proposition 2.1

The action of $G$ on $\overline{\Gamma(G,S)}$ has the following properties:

  1. (1)

The action is continuous, i.e. if $h_{n}\to h$ then $x.h_{n}\to x.h$.

  2. (2)

The map $x\mapsto b_{x}$ is equivariant, i.e. $x.b_{y}=b_{xy}$.

  3. (3)

The horoboundary $\partial\Gamma(G,S)$ and the Busemann boundary
$\partial_{b}\Gamma(G,S)$ are invariant subsets.

Two basic properties of horofunctions we require are the following. The proofs
are included for completeness.

####

###### Proposition 2.2

Let $\Gamma(G,S)$ be a Cayley graph.

If $b_{x_{n}}\to h$ and $h\in\partial\Gamma(G,S)$, then $|x_{n}|\to\infty$.

Also, if $b_{x_{n}}\to h$ and $|x_{n}|\to\infty$, then for every $r\geq 0$
there exists $x\in G$ with $h(x)=-|x|=-r$.

In particular, horofunctions are not bounded from below.

###### Proof.

Assume that $b_{x_{n}}\to h\in\overline{\Gamma(G,S)}$ and $|x_{n}|\leq r$ for
all $n$. Then, since the ball of radius $r$ is finite, it must be that there
exists some $|x|\leq r$ such that $x_{n}=x$ for infinitely many $n$. Thus,
$h=b_{x}\not\in\partial\Gamma(G,S)$. This shows that if $b_{x_{n}}\to
h\in\partial\Gamma(G,S)$ then $|x_{n}|\to\infty$.

Now, assume that $b_{x_{n}}\to h$ with $|x_{n}|\to\infty$. Fix some $r\geq 0$,
let $z=x_{n}\in G$ be such that $b_{z}(y)=h(y)$ for all $|y|\leq r$. Since
$|x_{n}|\to\infty$ we can choose $z$ so that $|z|>r$. Let
$\gamma=(1=\gamma_{0},\ldots,\gamma_{|z|}=z)$ be a finite geodesic and let
$x=\gamma_{r}$. Note that $|x|=r$ and that

$h(x)=d(\gamma_{|z|},\gamma_{r})-d(\gamma_{|z|},\gamma_{0})=-r=-|x|.$

$\sqcap$$\sqcup$

####

###### Proposition 2.3

Let $h\in\partial\Gamma(G,S)$ be a horofunction. Let
$K=\mathsf{stab}(h)=\\{x\in G\ :\ x.h=h\\}$ be the stabilizer of $h$.

Then, the restriction $h\big{|}_{K}$ is a homomorphism from $K$ into
$\mathbb{Z}$ (the additive group of integers).

###### Proof.

This follows immediately since for any $x\in K$ and any $y\in G$ we have

$h(xy)=x^{-1}.h(y)+h(x)=h(y)+h(x).$

$\sqcap$$\sqcup$

We have seen that restricting a horofunction to the stabilizer subgroup (for
the canonical group action) results in a homomorphism into $\mathbb{Z}$. One
naive approach to attempt to provide a simple proof that a finite horoboundary
implies that the group is virtually $\mathbb{Z}$ (similar to Conjecture 1.4)
would be as follows.

$G$ acts on $\partial\Gamma(G,S)$. Define:

$K=\\{x\in G\ :\ \forall\ h\in\partial\Gamma(G,S)\ ,\ x.h=h\\}$ $F=\\{x\in K\
:\ \forall\ h\in\partial\Gamma(G,S)\ ,\ h(x)=0\\}.$

One can show that $F$ is a subgroup. In fact it is possible to show that if
$x_{1},\ldots,x_{n}\in F$ then the group they generate, $\left\langle
x_{1},\ldots,x_{n}\right\rangle$, is contained in a ball of finite radius $r$,
which depends only on the generators $x_{1},\ldots,x_{n}$.

At the moment we do not know an answer to the following:

####

###### Question 2.4

Is the subgroup $F$ finitely generated when the horoboundary is finite? Is $F$
always finitely generated (in any Cayley graph)?

Because of the properties above, if $F$ is finitely generated, then it is
finite.

When the horoboundary is finite, we have that $[G:K]<\infty$ and we can also
write $\partial\Gamma(G,S)=\\{h_{1},\ldots,h_{d}\\}$. The map
$\Psi(x)=(h_{1}(x),\ldots,h_{d}(x))$ is then a map into $\mathbb{Z}^{d}$ whose
restriction to $K$ is a homomorphism. The kernel of $\Psi\big{|}_{K}$ is
exactly $F$. So if $F$ is finite, then one could show that $K$ is virtually
$\mathbb{Z}^{n}$ for some $n\leq d$, implying that also $G$ is. Since $G$ has
a finite horoboundary, one can then prove that actually $n=1$, along the lines
of our proof of Theorem 1.3.

##  3\. Finite Busemann boundaries

In this section we prove the main new part of Theorem 1.3, stated as the
following lemma.

####

###### Lemma 3.1

Let $G$ be a finitely generated infinite group. Assume that $S$ is a finite
symmetric generating set such that for any $x\in G$ we have that the Busemann
boundary $\partial_{b}\Gamma(G,U)$ is finite, where $U=S\cup\\{x,x^{-1}\\}$.

Then, $G$ is virtually $\mathbb{Z}$.

The proof of Lemma 3.1 is at the end of the section, and will use the
following lemmas.

####

###### Lemma 3.2

Let $\Gamma(G,S)$ be a Cayley graph. Let $(\gamma_{t})_{t}$ be a geodesic.

Then, the pointwise limit

$\gamma_{\infty}=\lim_{t\to\infty}b_{\gamma_{t}}$

exists, and $\gamma_{\infty}\in\partial\Gamma(G,S)$.

Then, there exists $t_{0}$ such that for all $t\geq t_{0}$ we have that
$\gamma_{\infty}(\gamma_{t})=-|\gamma_{t}|$.

If $\gamma_{0}=1$, then $\gamma_{\infty}(\gamma_{t})=-t$ for all
$t\in\mathbb{N}$.

###### Proof.

Let $(\gamma_{t})_{t}$ be a geodesic with $\gamma_{0}=1$. Set
$b_{t}=b_{\gamma_{t}}$. For any $x\in G$, by the triangle inequality
$b_{x}(y)=d(y,x)-|x|\geq-|y|$. Thus, for fixed $y\in G$ the sequence
$(b_{t}(y))_{t}$ is bounded below by $-|y|$. Because $\gamma$ is a geodesic
with $\gamma_{0}=1$, we have that
$|\gamma_{t+1}|-|\gamma_{t}|=d(\gamma_{t+1},\gamma_{t})$. So another use of
the triangle inequality gives,

$\displaystyle b_{t+1}(y)-b_{t}(y)$
$\displaystyle=d(\gamma_{t+1},y)-d(\gamma_{t},y)-d(\gamma_{t+1},\gamma_{t})\leq
0.$

We conclude that $(b_{t}(y))_{t}$ is a non-increasing sequence of integers,
bounded from below, and hence must converge to some integer which we denote by
$\gamma_{\infty}(y)$.

Also, for every $s\geq t$ we have that

$b_{s}(\gamma_{t})=d(\gamma_{t},\gamma_{s})-|\gamma_{s}|=-|\gamma_{t}|.$

Taking $s\to\infty$ we have that
$\gamma_{\infty}(\gamma_{t})=-|\gamma_{t}|=-t$ for all $t$.

Now, let $\beta$ be a geodesic, with $\beta_{0}=x$. Then,
$(\gamma_{t}=x^{-1}\beta_{t})_{t}$ is a geodesic with $\gamma_{0}=1$, so the
limit $\beta_{\infty}=x.\gamma_{\infty}$ exists.

Let $t_{0}$ be such that for all $t\geq t_{0}$ we have that
$\gamma_{\infty}(x^{-1})=d(\gamma_{t},x^{-1})-|\gamma_{t}|$. Then, for all
$s\geq t\geq t_{0}$ we have that

$d(\gamma_{s},\gamma_{t})-(d(\gamma_{s},x^{-1})-d(\gamma_{t},x^{-1}))=d(\gamma_{t},x^{-1})-|\gamma_{t}|-(d(\gamma_{s},x^{-1})-|\gamma_{s}|)=0,$

so that for all $t\geq t_{0}$ and all large enough $s$,

$\displaystyle\beta_{\infty}(\beta_{t})$
$\displaystyle=d(\beta_{s},\beta_{t})-|\beta_{s}|$
$\displaystyle=d(\gamma_{s},\gamma_{t})-(d(\gamma_{s},x^{-1})-d(\gamma_{t},x^{-1}))-|\beta_{t}|=-|\beta_{t}|.$

$\sqcap$$\sqcup$

####

###### Lemma 3.3

Let $\Gamma(G,S)$ be a Cayley graph. Let $K\leq G$ be a finite index subgroup
$[G:K]<\infty$.

Then, there exists $h\in\partial_{b}\Gamma(G,S)$ and $1\neq y\in K$ such that
$h(y)=-|y|$.

###### Proof.

Let $R\subset G$ be finite set of representatives for the cosets of $K$, i.e.
$G=\uplus_{r\in R}rK$, and suppose that $1\in R$. Let $(\gamma_{t})_{t}$ be
some geodesic in $\Gamma(G,S)$ such that $\gamma_{0}=1$ and let
$\gamma_{\infty}\in\partial_{b}\Gamma(G,S)$. By Lemma 3.2 we have that
$\gamma_{\infty}(\gamma_{t})=-t$ for every $t$. Since $R$ is finite, there
exists $r\in R$ such that $\gamma_{t}\in rK$ for infinitely many $t$. Denote
$\beta_{t}=r^{-1}\gamma_{t}$. Note that $\beta_{t}$ is a geodesic and
$\beta_{\infty}=r^{-1}.\gamma_{\infty}$. By Lemma 3.2 there exists $t_{0}$
such that for every $t\geq t_{0}$ we have
$\beta_{\infty}(\beta_{t})=-|\beta_{t}|$. Since by definition $\beta_{t}\in K$
for infinitely many $t$, there exists $t$ such that $\beta_{t}\in K$ and
$\beta_{\infty}(\beta_{t})=-|\beta_{t}|$. We are done by taking
$h=\beta_{\infty}$ and $y=\beta_{t}$.  $\sqcap$$\sqcup$

####

###### Lemma 3.4

Let $\Gamma(G,S)$ be a Cayley graph. Let $K\leq G$ be a subgroup.

Suppose there exists a $1$-Lipschitz map $h:G\to\mathbb{R}$ such that $h|_{K}$
is a group homomorphism, and suppose also that there is $1\neq x\in K$ such
that $h(x)=|x|_{S}$.

Then $|x^{t}|_{S}=t\cdot|x|_{S}$ for every $t\in\mathbb{N}$. If we denote
$U=S\cup\\{x,x^{-1}\\}$ then for any $g\in G$ we have that $(gx^{t})_{t}$ is a
geodesic in $\Gamma(G,U)$.

Moreover, there exists a geodesic $\gamma$ in $\Gamma(G,S)$ such that
$\gamma_{t|x|}=x^{t}$ for all $t\in\mathbb{N}$.

###### Proof.

By the triangle inequality $|x^{t}|_{S}\leq t|x|_{S}$. By our assumptions on
$h$, since $x\in K$ we have that

$t|x|_{S}=th(x)=h(x^{t})\leq|x^{t}|_{S},$

so $|x^{t}|_{S}=t|x|_{S}=h(x^{t})$ for all $t\in\mathbb{N}$.

Next we show that $|x^{t}|_{U}=t$ for every $t\in\mathbb{N}$. Write
$x^{t}=u_{1}\cdots u_{m}$ where $u_{j}\in U$ for all $1\leq j\leq
m=|x^{t}|_{U}$. Let $J=\\{j\ |\ u_{j}\in S\\}$, so that if $j\notin J$ then
$u_{j}\in\\{x,x^{-1}\\}$. Since $x\in U$, $m\leq t$. Also,

$t\cdot|x|_{S}=|x^{t}|_{S}=|u_{1}\cdots
u_{m}|_{S}\leq\sum_{j=1}^{m}|u_{j}|_{S}\leq|J|+(m-|J|)\cdot|x|_{S}\leq
m\cdot|x|_{S},$

where we have used that $|x|_{S}\geq 1$ because $x\neq 1$. Thus, $t\leq m$,
implying that $|x^{t}|_{U}=m=t$.

Now, let $g\in G$. Since $(x^{t})_{t}$ is a geodesic in $\Gamma(G,U)$ and the
graph metric is left invariant,
$d_{U}(gx^{n},gx^{m})=d_{U}(x^{n},x^{m})=|n-m|$, so $(gx^{t})_{t}$ is also a
geodesic in $\Gamma(G,U)$.

Finally, for the last assertion, we want to construct a geodesic $\gamma$ in
$\Gamma(G,S)$ such that $\gamma_{t|x|}=x^{t}$ for all $t\in\mathbb{N}$. To
this end, set $m=|x|$ and let $(1=x_{0},x_{1},\ldots,x_{m}=x)$ be a finite
geodesic in $\Gamma(G,S)$. Define $\gamma_{0}=1$ and for $0\leq j\leq m$
define $\gamma_{nm+j}=x^{n}x_{j}$.

We will show that $\gamma$ is a geodesic in $\Gamma(G,S)$. Indeed, since
$\gamma$ is a path in the graph $\Gamma(G,S)$, it is immediate that
$d(\gamma_{t},\gamma_{s})\leq s-t$ for all $s\geq t$, so we only need to prove
a matching lower bound.

Let $k\geq n$ and $0\leq i,j\leq m$ be such that $km+i\geq nm+j$. Then,

$\displaystyle d(\gamma_{nm+j},\gamma_{km+i})$
$\displaystyle=d(x^{n}x_{j},x^{k}x_{i})=d(x_{j},x^{k-n}x_{i}).$

If $k=n$ then $i\geq j$ and

$d(\gamma_{nm+j},\gamma_{km+i})=d(x_{j},x_{i})=i-j=km+i-(nm+j)$

because $(x_{0},\ldots,x_{m})$ is a finite geodesic. If $k>n$, then

$\displaystyle(k-n+1)|x|_{S}$ $\displaystyle=|x^{k-n+1}|_{S}\leq
d(x^{k-n+1},x^{k-n}x_{i})+d(x^{k-n}x_{i},x_{j})+d(x_{j},1)$
$\displaystyle=d(x_{m},x_{i})+d(\gamma_{nm+j},\gamma_{km+i})+d(x_{j},x_{0})$
$\displaystyle=d(\gamma_{nm+j},\gamma_{km+i})+|x|_{S}+j-i,$

where we have used again that $(x_{0},\ldots,x_{m})$ is a finite geodesic.
Thus, in all cases we get that

$d(\gamma_{nm+j},\gamma_{km+i})\geq km+i-(nm+j),$

providing a matching lower bound to the upper bound, and proving that $\gamma$
is indeed a geodesic in $\Gamma(G,S)$.  $\sqcap$$\sqcup$

####

###### Lemma 3.5

Let $\Gamma(G,S)$ be a Cayley graph. Let $K\leq G$ be a subgroup.

Suppose there exists a $1$-Lipschtiz map $h:G\to\mathbb{R}$ such that $h|_{K}$
is a group homomorphism, and suppose also that there is $1\neq x\in K$ such
that $h(x)=|x|_{S}$. Let $U=S\cup\\{x,x^{-1}\\}$.

Then,

$|\mathsf{Ker}{(h|_{K})}|\leq|\partial_{b}\Gamma(G,U)|.$

###### Proof.

Let $g\in\mathsf{Ker}(h|_{K})$. Let $\gamma_{t}=x^{t}$ and $\beta_{t}=gx^{t}$.
Note that both $(\gamma_{t})_{t}$ and $(\beta_{t})_{t}$ are geodesics in
$\Gamma(G,U)$ by Lemma 3.4.

Define $\psi(x)=\frac{1}{|x|_{S}}\cdot h(x)$. Notice that $\psi$ is a
$1$-Lipschitz map on $\Gamma(G,U)$, since $|\psi(s)|\leq 1$ for every $s\in S$
and $|\psi(x)|=|\psi(x^{-1})|=1$. Note also that $\psi|_{K}$ is a homomorphism
to $\mathbb{R}$, and satisfies $\psi(\gamma_{t})=\psi(\beta_{t})=t$ for every
$t$. Thus for every $t$,

$d_{U}(\gamma_{t},\gamma_{0})=t=|\psi(\gamma_{t})-\psi(\beta_{0})|\leq
d_{U}(\gamma_{t},\beta_{0})$
$d_{U}(\beta_{t},\beta_{0})=t=|\psi(\beta_{t})-\psi(\gamma_{0})|\leq
d_{U}(\beta_{t},\gamma_{0})$

Consider $\overline{\Gamma(G,U)}$. Note that,

$\displaystyle b_{\gamma_{t}}(\gamma_{0})-b_{\gamma_{t}}(\beta_{0})$
$\displaystyle=d_{U}(\gamma_{t},\gamma_{0})-d_{U}(\gamma_{t},\beta_{0})\leq 0$
(2) $\displaystyle\leq
d_{U}(\beta_{t},\gamma_{0})-d_{U}(\beta_{t},\beta_{0})=b_{\beta_{t}}(\gamma_{0})-b_{\beta_{t}}(\beta_{0}).$

If $\gamma_{\infty}=\beta_{\infty}$, there exists $t_{0}$ such that for every
$t\geq t_{0}$ we have that
$b_{\gamma_{t}}(\gamma_{0})-b_{\gamma_{t}}(\beta_{0})=b_{\beta_{t}}(\gamma_{0})-b_{\beta_{t}}(\beta_{0})$,
implying equality throughout (3). Thus,
$d_{U}(\gamma_{t},\beta_{0})=d(\gamma_{t},\gamma_{0})=t$ for every $t\geq
t_{0}$.

Now we shall prove that $g=1$. Since $h(g)=0$, $h(x^{n})=n\cdot|x|_{S}$ and
$h$ is $1$-Lipschitz, we have

$t\cdot|x|_{S}=h(\gamma_{t})=|h(\gamma_{t})-h(g)|\leq d_{S}(\gamma_{t},g),$

so that $t\cdot|x|_{S}\leq d_{S}(\gamma_{t},g)$ for every $t$.

Fix some $t\geq t_{0}$. Since $d_{U}(\gamma_{t},\beta_{0})=t$ there exist a
finite geodesic $(z_{j})_{j=0}^{t}$ in $\Gamma(G,U)$ such that
$z_{0}=\beta_{0}=g$ and $z_{t}=\gamma_{t}=x^{t}$. Let
$u_{j}=z_{j-1}^{-1}z_{j}$ for every $1\leq j\leq t$, and let
$J=\\{j~{}|~{}u_{j}\in S\\}$. We get:

$t\cdot|x|_{S}\leq
d_{S}(\gamma_{t},g)\leq\sum_{j=1}^{t}|u_{j}|_{S}=|J|+(t-|J|)\cdot|x|_{S}=t\cdot|x|_{S}-|J|\cdot(|x|_{S}-1).$

Because $x\neq 1$, it follows that $|J|=0$, so $u_{j}\in\\{x,x^{-1}\\}$ for
every $1\leq j\leq t$. Thus $x^{t}=z_{t}=gx^{m}$ for some $m\in\mathbb{Z}$.
But that means that $g=x^{t-m}$ and so $0=h(g)=h(x^{t-m})=(t-m)\cdot|x|_{S}$.
This implies that $t-m=0$, i.e. that $g=1$.

Thus we have shown that the only $g\in\mathsf{Ker}(h|_{K})$ such that
$\gamma_{\infty}=g.\gamma_{\infty}$ is $g=1$. So if
$g,g^{\prime}\in\mathsf{Ker}(h|_{K})$ are such that
$g.\gamma_{\infty}=g^{\prime}.\gamma_{\infty}$ then $g=g^{\prime}$. That is,
the map $g\mapsto g.\gamma_{\infty}$ from $\mathsf{Ker}(h|_{K})$ to
$\partial_{b}\Gamma(G,U)$ is injective, completing the proof.
$\sqcap$$\sqcup$

We now complete this section by proving Lemma 3.1.

###### Proof of Lemma 3.1.

Let $S$ be a finite symmetric generating set for an infinite group $G$ such
that for any $x\in G$, setting $U=S\cup\\{x,x^{-1}\\}$ gives a Cayley graph
$\Gamma(G,U)$ with a finite Busemann boundary. Specifically, taking $x\in S$
tells us that $|\partial_{b}\Gamma(G,S)|<\infty$. Let

$K=\\{x\in G\ :\ \forall\ h\in\partial_{b}\Gamma(G,S)\ ,\ x.h=h\\}$

be the kernel of the action. Since $\partial_{b}\Gamma(G,S)$ is finite,
$[G:K]<\infty$. By Lemma 3.3 there exists $h\in\partial_{b}\Gamma(G,S)$ and
$1\neq y\in K$ such that $h(y)=-|y|_{S}$. By Proposition 2.3, $h|_{K}$ is a
homomorphism into $\mathbb{R}$, so $h(x)=|x|_{S}$ for $x=y^{-1}$. By Lemma
3.5, we have that $|\mathsf{Ker}(h|_{K})|\leq|\partial_{b}\Gamma(G,U)|$, where
$U=S\cup\\{x,x^{-1}\\}$. This is finite by our assumptions on $S$.

Since $h$ is a non-trivial integer valued homomorphism on the infinite group
$K$, it must be that $h(K)\cong\mathbb{Z}$. Thus,
$K/\mathsf{Ker}(h|_{K})\cong\mathbb{Z}$, and as the kernel is finite, this
implies that $K$ is virtually $\mathbb{Z}$. As $[G:K]<\infty$, this completes
the proof.  $\sqcap$$\sqcup$

##  4\. Graphs of Linear Growth

The “only if” direction of Theorem 1.3 was originally proven in [11] (in that
paper horoboundary refers to what we call Busemann boundary). Sam Shepperd
gave the following short and elegant proof.

By a graph of linear growth we mean that the number of vertices in the ball of
radius $r$ in the graph grows at most linearly in the radius $r$.

####

###### Proposition 4.1

Let $\Gamma$ be a graph, with $d$ denoteing the graph distance. Let
$o\in\Gamma$ be some vertex, and consider the Busemann boundary
$\partial_{b}\Gamma$ with respect to this base point. Let
$S_{r}=\\{x\in\Gamma\ :\ d(x,o)=r\\}$ be the sphere of radius $r$ around $o$.

Then,

$|\partial_{b}\Gamma|\leq\liminf_{r\to\infty}|S_{r}|.$

Specifically, if $\Gamma$ has linear growth, then the Busemann boundary is
finite.

###### Proof.

For a geodesic $\gamma$ in $\Gamma$, denote

$S_{r}\cap\gamma=\\{x\in S_{r}\ :\ \exists\ t\ ,\ \gamma_{t}=x\\}.$

For any geodesic $\gamma$ there exists some $r(\gamma)$ such that for all
$r\geq r(\gamma)$ we have $|S_{r}\cap\gamma|=1$.

Now, let $\gamma^{(1)},\ldots,\gamma^{(n)}$ be $n$ geodesics, such that
$\gamma^{(1)}_{\infty},\ldots,\gamma^{(n)}_{\infty}$ are all distinct Busemann
points. Since these geodesics are all pairwise non-equivalent, no two of them
can intersect infinitely many times. Thus, there exists some $r_{0}$ such that
for all $r\geq r_{0}$, we have

$\forall\ i\neq j\ ,\
\big{(}S_{r}\cap\gamma^{(i)}\big{)}\cap\big{(}S_{r}\cap\gamma^{(j)}\big{)}=\emptyset.$

By making sure that
$r_{0}\geq\max\\{r(\gamma^{(1)}),\ldots,r(\gamma^{(n)})\\}$ we get that

$n=\big{|}\bigcup_{j=1}^{n}(S_{r}\cap\gamma^{(j)})\big{|}\leq|S_{r}|$

for all $r\geq r_{0}$. Taking $\liminf$ on the right-hand side completes the
proof of the first assertion.

Now, if $\Gamma$ has linear growth, then there exists a constant $C>0$ such
that for any $r\in\mathbb{N}$ we have

$\big{|}\\{x\in\Gamma\ :\ d(x,o)\leq r\\}\big{|}=\sum_{k=0}^{r}|S_{k}|\leq
C(r+1).$

This is easily seen to imply that $\liminf_{r\to\infty}|S_{r}|<\infty$,
implying the second assertion.  $\sqcap$$\sqcup$

Note also that one can replace the geodesics in the proof above with infinite
simple paths which have distinct limits in the horoboundary. It is not true,
however, that every horofunction is the limit of a sequence forming a simple
infinite path.

As mentioned, the converse statement to Proposition 4.1 for general graphs,
i.e. an analogue of Theorem 1.3, is not true in general. Consider the
following example with a graph of arbitrary growth, but only one point in the
horofunction boundary.

####

###### Example 4.2

Consider the following graph: Let $(\Gamma_{n})_{n\in\mathbb{N}}$ be a
sequence of finite graphs, and fix some vertex $x_{n}\in\Gamma_{n}$ in each
one.

The vertex set of our graph $\Gamma$ is then defined to be
$\mathbb{N}\cup\bigcup_{n}\Gamma_{n}$. Edges in $\Gamma$ are given by:

  * •

the original edges in $\mathbb{N}$ ($\\{x,y\\}$ is an edge if $|x-y|=1$ for
$x,y\in\mathbb{N}$),

  * •

the original edges in each $\Gamma_{n}$,

  * •

and additional edges $\\{n,x_{n}\\}$ for each $n\in\mathbb{N}$.

See Figure 1.

It is not difficult to compute that if $x\in\Gamma_{n}\cup\\{n\\}$ and if
$y\in\Gamma_{m}\cup\\{m\\}$ for $m>n$, then

$d(y,x)=d(y,m)+d(m,n)+d(n,x),$

so that the only possible horofunction in this graph is given by

$h(x)=\lim_{m\to\infty}(d(m,x)-m).$

$\bigtriangleup\bigtriangledown\bigtriangleup$

Figure 1. The graph $\Gamma$ from Example 4.2.

####

###### Theorem 4.3

Let $G$ be a group that is virtually $\mathbb{Z}$, and let $\Gamma(G,S)$ be
any Cayley graph of $G$.

Then, any horofunction in $\partial\Gamma(G,S)$ is a Busemann point; i.e.
$\partial\Gamma(G,S)=\partial_{b}\Gamma(G,S)$.

###### Proof.

Since $G$ is virtually $\mathbb{Z}$ it has linear growth, so by Proposition
4.1 we know that the Busemann boundary $\partial_{b}\Gamma(G,S)$ is finite.
$G$ acts on $\partial_{b}\Gamma(G,S)$. Let

$K=\\{x\in G\ :\ \forall\ h\in\partial_{b}\Gamma(G,S)\ ,\ x.h=h\\}$

be the kernel of the action. Since $\partial_{b}\Gamma(G,S)$ is finite,
$[G:K]<\infty$. By Lemma 3.3 there exists $\varphi\in\partial_{b}\Gamma(G,S)$
and $1\neq y\in K$ such that $\varphi(y)=-|y|_{S}$. By Proposition 2.3,
$\varphi|_{K}$ is a homomorphism into $\mathbb{R}$, so $\varphi(x)=|x|_{S}$
for $x=y^{-1}$. Since $\varphi$ is $1$-Lipschitz, by Lemma 3.4 there exists a
geodesic $\alpha$ in $\Gamma(G,S)$ such that $\alpha_{n|x|}=x^{n}$ for all
$n\in\mathbb{N}$. Applying the same logic to $y=x^{-1}$ but with the
$1$-Lipschitz function $-\varphi$, we can also define a geodesic $\beta$ so
that $\beta_{n|x|}=x^{-n}$ for all $n\in\mathbb{N}$.

Now, consider the subgroup $N=\left\langle x\right\rangle\cong\mathbb{Z}$.
Since $G$ is virtually $\mathbb{Z}$, it is impossible that $[G:N]=\infty$. Let
$R$ be a set of representatives for the cosets of $N$; i.e. $G=\biguplus_{r\in
R}rN$ with $|R|=[G:N]<\infty$. Assume that $1\in R$.

Let $h\in\partial\Gamma(G,S)$ be an arbitrary horofunction. Let $(y_{n})_{n}$
be a sequence in $G$ such that $h=\lim_{n\to\infty}b_{y_{n}}$. By Proposition
2.2, the set $\\{y_{n}\\}_{n}$ is infinite, and thus, there must exist some
$r\in R$ such that infinitely many $y_{n}$ are in the coset $rN$. Thus, one of
the two sets

$\\{y_{n}\ :\ \exists\ k\ ,\ y_{n}=r\alpha_{k}\\}\qquad\textrm{ or }\\{y_{n}\
:\ \exists\ k\ ,\ y_{n}=r\beta_{k}\\}$

is infinite. That is, the sequence $(y_{n})_{n}$ has infinitely many common
points with one of the geodesics $r\alpha$ or $r\beta$. This implies that

$h=\lim_{n\to\infty}b_{y_{n}}=\lim_{k\to\infty}b_{rx^{k}}\in\\{r.\alpha_{\infty},r.\beta_{\infty}\\}.$

As this was for an arbitrary horofunction $h\in\partial\Gamma(G,S)$, we have
that

$\partial\Gamma(G,S)\subset\\{r.\alpha_{\infty},r.\beta_{\infty}\ :\ r\in
R\\}\subset\partial_{b}\Gamma(G,S).$

$\sqcap$$\sqcup$

## References

  * [1] R. I. Grigorchuk.  On growth in group theory.  In Proceedings of the International Congress of Mathematicians, volume 1, pages 325–338, 1990.
  * [2] M. Gromov.  Groups of polynomial growth and expanding maps.  Publications Mathématiques de l’IHÉS, 53:53–78, 1981.
  * [3] A. Karlsson.  Nonexpanding maps, Busemann functions, and multiplicative ergodic theory.  Rigidity in Dynamics and Geometry: Contributions from the Programme Ergodic Theory, Geometric Rigidity and Number Theory, Isaac Newton Institute for the Mathematical Sciences Cambridge, United Kingdom, 5 January–7 July 2000, pages 283–294, 2002.
  * [4] A. Karlsson.  Ergodic theorems for noncommuting random products.  Lecture notes available on the author’s website, 2008.
  * [5] A. Karlsson.  From linear to metric functional analysis.  Proceedings of the National Academy of Sciences, 118(28), 2021.
  * [6] A. Karlsson.  Hahn-Banach for metric functionals and horofunctions.  Journal of Functional Analysis, 281(2):109030, 2021.
  * [7] A. Karlsson.  8\. elements of a metric spectral theory.  In Dynamics, Geometry, Number Theory, pages 276–300. University of Chicago Press, 2022.
  * [8] B. Kleiner.  A new proof of Gromov’s theorem on groups of polynomial growth.  Journal of the American Mathematical Society, 23(3):815–829, 2010\.
  * [9] N. Ozawa.  A functional analysis proof of Gromov’s polynomial growth theorem.  Ann. Sci. Éc. Norm. Supér.(4), 51(3):549–556, 2018.
  * [10] Y. Shalom and T. Tao.  A finitary version of Gromov’s polynomial growth theorem.  Geometric and Functional Analysis, 20(6):1502–1547, 2010.
  * [11] M. C. Tointon and A. Yadin.  Horofunctions on graphs of linear growth.  Comptes Rendus Mathematique, 354(12):1151–1154, 2016.
  * [12] C. Walsh.  The action of a nilpotent group on its horofunction boundary has finite orbits.  Groups, Geometry, and Dynamics, 5(1):189–206, 2011.
  * [13] C. Webster and A. Winchester.  Busemann points of infinite graphs.  Transactions of the American Mathematical Society, 358(9):4209–4224, 2006.
  * [14] S.-T. Yau.  Perspectives on geometric analysis.  arXiv preprint math/0602363, 2006.