Is there a simple proof that a group of linear growth is quasi-isometric to Z?

Question

I proposed to a master's student to work, from the exercise in Ghys-de la Harpe's book, on the proof that a finitely generated group $G$ that is quasi-isometric to $\mathbb{Z}$ is virtually $\mathbb{Z}$. However I initially had in mind the result that gives the same conclusion from the hypothesis that $G$ has linear growth.

Do you know of any simple (and elementary, in particular without assuming Gromov's theorem on polynomial growth groups) proof that a group of linear growth is quasi-isometric to $\mathbb{Z}$?

Answer 1

Here are two papers dealing with this question: Wilkie, A. J.(4-MANC); van den Dries, L.(1-IA-S) An effective bound for groups of linear growth. Arch. Math. (Basel) 42 (1984), no. 5, 391--396. 20F05

and

Imrich, Wilfried(A-MNT); Seifter, Norbert(A-MNT) A bound for groups of linear growth. Arch. Math. (Basel) 48 (1987), no. 2, 100--104.

the second one using ends of groups, as indicated by Sam.

Answer 2

I believe the substance of the question has been answered, but since it's a question of what can be done without modern machinery, this may help: I was thinking about the problem of deducing structure of a group from the growth rate in the '70's, when Gromov was still in Russia. When we first met, soon after he arrived, we had much in common that we'd been thinking about, but he had not yet proven the theorem concerning groups of polynomial growth. I was stuck on trying to analyze groups of quadratic growth; I recall that strictly linear growth seemed fairly straightforward using the technology of the time: in particular, Stalling's idea of a minimizing cocyle (from his work analying ends of groups). ( I believe when Gromov and I first met we both knew that groups of linear growth are virtually $\mathbb Z$, and we focused on other things.) I'm pretty sure there's a fairly elementary complete proof based on Stallings' idea, just thinking of components of the sphere of radius R as defining a cocycle. I could supply details on demand.

Added in response to Sam Nead's request:

This isn't very different from what Sam Nead and others outlined, but I'll give some variations of a proof. These are all related:

1. Consider a Cayley graph for the group. Between any two vertices $v$ and $w$, ask what is the maximal graph-flow between $v$ and $w$ (Each edge carries a flow of at most 1. A graph flow, in other language, is expressing the maximum possible multiple of the 0-chain w-v a the boundary of a 1-chain of $L^\infty$ norm 1). The well-known min-flow / max-cut principle says that the maximal flow equals the minimal cut, that is, the minimum $L^1$ norm of a collection of edges that separates $V$ from $W$, which in other language is the minimum $L^1$ norm of the coboundary of a 0-cochain that is 0 on $v$ and 1 on $w$.

   Linear growth implies there is a uniform upper bound for the graph flow, no matter how distant $v$ and $w$ are, because there are balls with bounded size of boundary about $v$ that don't contain $w$.

   Since there are spheres of arbitarily large radius of bounded size, if v and w are far enough apart, there must be a graph flow that is isomorphic in a neighborhood of two such spheres $S_r(v)$ and $S_s(v)$ where $0 < r, s< d(v,w)$. Take the annulus between them, and identify the spheres. A connected component of the resulting graph defines a subgroup of finite index in the group, and it comes equipped with a cyle (the flow) paired non-trivially with the cocycle (the identified spheres of radius $r$ and $s$).

2. Similarly to (1), you can look at the combinatorial derivative of the distance function from a vertex $v$, that a 1-cocycle on a 2-complex for the group that takes values $\pm 1$ and $0$. The derivative of the distance function has to repeat on spheres of radius R. Cut and glue, as before, and get a subgroup of finite index with a non-trivial 1-cocycle, giving a homomorphism to $\mathbb Z$.

3. Another variation, same general idea, technically harder but perhaps giving a clearer mental image: you can take a Riemannian manifold with fundamental group $G$, and in its universal cover, do volume-constrained minimization of hypersurfaces: what is the least area $A(V)$ for a hypersurface that bounds a volume $V$? Such surfaces have constant mean curvature. There has been a reasonably good existence theorem for solutions for a long time --- the solutions may not be smooth hypersurfaces, although in low dimensions they are, but they still have nice geometric descriptions. At a local minimum for $A(V)$, the hypersurface is a minimal surface. Even if there are no local minima, one could take limits as $V \to \infty$ to get minimal hypersurfaces. The images of minimizing hypersurfaces by deck transformations are either disjoint or they coincide, by familiar arguments (cutting and paste to get smaller surfaces doing the job). Use the separation properties of these to get a map to the infinite dihedral group, a la Stallings.

4. Automatic group theory. This theory is subsequent to Gromov's proof, but it had incipient forms before -- a number of people, including me and Gromov, had thought about growth patterns for groups. I think there's a nice pathway linear growth => automatic =(with polynomial growth)=> virtually Z^n => virtually Z. I've written enough, so I won't unroll this now.

Answer 3

If a group is q.i. to $\mathbb Z$, then all its asymptotic cones are lines. In our paper with Cornelia Drutu, "Tree-graded spaces and asymptotic cones of groups", Topology 44 (2005), no. 5, 959--1058 (see Corollary 6.2), we prove that if even one asymptotic cone of a group is a line, then the group is virtually cyclic.

Now about the original question. We need to show that if the growth of $G$ is linear, say ~$Cn$, then an asymptotic cone of $G$ is a line. Since the group is infinite, it a sequence of arbitrary long geodesics $g_n$ of length $n$ with midpoint $1$. Now pick any number $m$ and two points $a,b$ at distance $2m$ on $g_n$, $n\gg m$, let $c$ be the midpoint between $a,b$ on $g_0$. The balls $B(a,m)$, $B(b,m)$ then contain $~Cm$ points each, hence their (disjoint!) union is (very close to) the ball $B(c,2m)$. Hence the $2m$-neighborhood of $g_n$ is contained in the $m$-neighborhood of $g_0$. This should be true for a sequence of $m_i$'s tending to $\infty$. From this it is easy to deduce that the asymptotic cone ${\mathcal C}=Con^\omega(G,(m_i))$ is at distance $1$ from the geodesic line $g$ which is the limit of $g_n$. But then ${\mathcal C}$ is quasi-isometric to a line, hence its asymptotic cone is a line. It is proved in the paper cited above that an asymptotic cone of $\mathcal C$ is again an asymptotic cone of $G$, and we are done.

Answer 4

This is a very nice question! There is a well-known question "if $G$ is qi to $Z^n$ then $G$ is virtually $Z^n$." I've been told that Yehuda Shalom has a proof that avoids using Gromov's theorem - I couldn't find a reference on-line for this.

Here is an idea for an answer to your question. A finitely generated group $G$ has either 0, 1, 2 or infinitely many ends, in the sense of Stallings. Assuming linear growth for $G$ rules out zero and infinity. If $G$ has two ends then Stallings proves that $G$ is virtually cyclic. So we may assume, for a contradiction, that $G$ is one-ended.

Choose a geodesic ray $R \subset G$ that starts at the identity and exits the unique end of the Cayley graph of $G$. (Note that $R$ exists because the Cayley graph is proper - metric balls are compact.) Here is the vague bit; deduce somehow that $G$ is quasi-isometric to $R$. This gives a quasi-action of $G$ on the positive reals. Thus there are group elements $g_n \in G$ act on $R$ essentially via positive translation by $n$. (This is a lie, of course; they may also expand/contract, but only a uniformly bounded amount.) However, for sufficiently large $n$ the element $g_n$ cannot have an inverse in $G$, and we are done.

Answer 5

A (more) recent paper by Tointon and Yadin gives a short proof using horofunctions. Links: arXiv (2016), DOI pointing to published version (Comptes Rendus Math., 2016)