Return to Answer

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'm pretty sure there's a fairly elementary complete proof based on that, just thinking of components of the sphere of radius R as defining a cocycle. I could supply details on demand.

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.

2. Similarly to (1), you can look at the combinatorial derivative of the distance function from a vertex $v$, that a 1-cycle 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.

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.

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-cycle 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.