Amenability, Bilipschitz Equivalence, and the Von Neumann Conjecture

Kevin Whyte, University of Chicago

1 Introduction and Statement of Results

The geometry of discrete metric spaces has been a very active research area recently. The motivation comes, primarily, from two (not completely separate) areas of mathematics. One is the study of non-compact manifolds equipped with metrics well defined up to uniformly bounded distortion. These arise naturally in the study of compact manifolds; for example as universal covers or leaves of foliations. To focus attention purely on the large scale structure, the local topology is thrown away by passing to a discrete subset, called a net, which evenly fills out the space. A typical example is ℤ^{n} in ℝ^{n}. Two nets in a space are bilipschitz equivalent on the large scale, but not the small. This leads to the notion of a quasi-isometry of metric spaces, and gives a functor from manifolds of bounded geometry, up to bounded distortion, to discrete metric spaces up to quasi- isometry.

The second source of motivation and examples is geometric group theory. A finitely generated group can be given a metric by measuring the distance from an element to the identity by the minimal length of a word in the generators which representing the element. This extends to a metric by left translation invariance. This metric, called the (left) word metric, is welldefined up to bilipschitz equivalence (this can be seen simply by expanding one set of generators in another). One can then study the group via the geometry of this space.

The coarse geometry of manifolds and geometric group theory are related, most obviously by the fundamental group. If M is a compact manifold then M̄ has obvious nets given by the orbits of the action of π_{1}(M). These nets are canonically identified, at least as sets, with π_{1}(M). Conversely, if Γ is any finitely presented group there is a compact manifold with π_{1} = Γ. It is a fundamental observation in the subject that the quasi-isometry type of Γ as a net agrees with the word metric. More generally, the Milnor-Svarc theorem says that any path metric space on which Γ acts cocompactly by isometries is quasi-isometric to Γ with its word metric. Thus, for instance, any two compact hyperbolic manifolds of the same dimension have quasi-isometric fundamental groups. The same holds for other locally symmetric spaces. This is sense in which we expect the word metric to capture the “geometric type” of a group.

The reader may have noticed a small distinction between the geometric and algebraic viewpoints: nets are well defined only up to quasi-isometry while the word metric gives a canonical bilipschitz type. This discrepancy is real - one instance where it causes problems is free products. It is not hard to see that the free products of bilipschitz equivalent groups are bilipschitz equivalent. One might therefore expect that quasi-isometric groups have quasi-isometric free products. This is not true, as the case of finite groups shows.

Our first result is a complete description of the difference between quasiisometries and bilipschitz maps. UDBG stands for uniformly discrete of bounded geometry. See the next section for definitions.

Theorem 1.1. If f : X → Y is a quasi-isometry between UDBG-spaces then there is a bilipschitz map at bounded distance from f iff f_{∗}([X]) = [Y] where [X] and [Y] are the fundamental classes in H_{0}^{uf}.

This theorem also gives, more or less directly, a classification of the bilipschitz classes of spaces within a given quasi-isometry type.

Theorem 1.2. For any UDBG-space X, S_{bilip}(X) = H_{0}^{uf+}(X).

Results of [2] show that H_{0}^{uf}(X) is closely related to amenability. Amenability was originally defined, for groups, in terms of invariant means (finitely additive probability measures). This was shown by Følner to be equivalent to the existence of subsets whose boundaries are arbitrarily small compared to the entire subset. This definition makes sense for any discrete space. One of the early conjectures about amenability, called the Von Neumann conjecture (although Pierre de la Harpe informs me that it was, in fact, due to Day) states that a group is either amenable or contains a non-abelian free group (wlog on two generators). This is now known to be false [12], at least for finitely generated groups, but one does not know whether there is a finitely presented counterexample. We formulate and prove a geometric version of this conjecture:

Theorem 1.3. Let Z be a UDBG-space. Z is non-amenable iff Z admits a free action by a free group on two generators by bilipschitz maps at bounded distance from the identity.

If Z = Γ, a group with its left word metric, then a free subgroup acting on the right would give such an action.

As a consequence we show that the vanishing of 0-dimension l^{p}-homology for p > 1 is equivalent to non-amenability.

Theorem 1.4. Let X be a UDBG-space, and p ∈ (1, ∞]. X is non-amenable iff H_{0}^{(p)}(X) = 0.

The case p = ∞ of this theorem is a theorem of [2].

As discussed above, one case where it is useful to know if a quasi-isometry can be replaced by a bilipschitz equivalence is in forming free products. Theorem 1.1 thus gives a way of constructing groups which are quasi-isometric, which do not obviously act isometrically on the same space (the only other source of such examples seems to be [6]).

Theorem 1.5. If Γ_{1} and Γ_{2} are quasi-isometric, finitely generated nonamenable groups then for any finitely generated group G, Γ_{1} ∗ G and Γ_{2} ∗ G are quasi-isometric.

This allows us to construct many new quasi-isometries. In particular we show that neither the sign of the Euler characteristic nor ratios of l^{2}-betti numbers are quasi-isometry invariant, which answers a question of Gromov’s [9]. These are commensurability invariants, and are the same for any two uniform lattices in the same Lie group. Thus the quasi-isometries constructed do not arise in this sort of geometric manner.

We work out the quasi-isometric and commensurability classifications of free products of (any finite number of) surface groups.

Theorem 1.6. Let Σ_{g} be the fundamental group of a surface of genus g.Let Γ_{1} = Σ_{a_{1}} ∗ Σ_{a_{2}} ∗ ... ∗ Σ_{a_{n}} and Γ_{2} = Σ_{b_{1}} ∗ Σ_{b_{2}} ∗ ... ∗ Σ_{b_{m}}. Then Γ_{1} and Γ_{2} are commensurable iff

\frac{χ(Γ_{1})}{n − 1} = \frac{χ(Γ_{2})}{m − 1}

Thus there are infinitely many different commensurability classes, even among free products of two surface groups. By contrast, we have:

Theorem 1.7. Let Γ = Σ_{g_{1}} ∗ Σ_{g_{2}} ∗ ... ∗ Σ_{g_{n}}. Then Γ is quasi-isometric to one of ℤ^{2}, Σ_{2}, ℤ^{2} ∗ ℤ^{2}, ℤ^{2} ∗ Σ_{2}, or Σ_{2} ∗ Σ_{2}.

2 Preliminaries

As geometric group theory and coarse geometry are relatively young fields, not all the notation and terminology is uniform, below are our choices.

Definition 2.1. A space X is uniformly discrete if there is an ε > 0 such that

d(x_{1}, x_{2}) < ε ⇒ x_{1} = x_{2}

.

Definition 2.2. If X is a metric space, a subset S ⊂ X is C-dense if d(x, S) ≤ C for all x in X.

When we are not concerned with the value of C, we will simply say S is dense.

Definition 2.3. A discrete metric space X has bounded geometry if it is uniformly discrete and, for any r > 0 there is a bound N_{r} on the cardinality of any r-ball in X.

To avoid repeating “uniformly discrete metric space of bounded geometry” we use the abbreviation UDBG-space.

A major source of examples of UDBG spaces is finitely generated groups.

Definition 2.4. Let Γ be a finitely generated group. If {g_{i}} are a generating set, we define ||g|| as the minimal length of a word in the {g_{i}} representing g. The (left) word metric is defined by d(x, y) = ||x^{−1}y||. This metric is left invariant, and the word metrics for any two finite generating sets are bilipschitz equivalent.

Definition 2.5. Let X and Y be metric spaces. A map f : X → Y is coarse lipschitz if there are A and B such that for all x_{1}, x_{2} in X,

d(f(x_{1}), f(x_{2})) ≤ Ad(x_{1}, x_{2}) + B

Two coarse lipschitz maps, f_{1} and f_{2}, are equivalent iff there is some R so that d(f_{1}(x), f_{2}(x)) ≤ R for all x.

There is also a notion of “coarse bilipschitz equivalent”, which is more commonly called quasi-isometric:

Definition 2.6. Two metric spaces X and Y are quasi-isometric iff there are coarse lipschitz maps f : X → Y and g : Y → X such that fg and gf are at bounded distance from the identity.

Notice that the image of a quasi-isometry is necessarily dense.

A map which is a quasi-isometry with its image will be called a quasiisometric embedding.

For groups, any homorphism with finite kernel is coarse lipschitz.

For any space, the inclusion of any dense set is a quasi-isometry. In particular, for groups, the inclusion of any subgroup of finite index is a quasiisometry. Thus any two groups with isomorphic subgroups of finite index are quasi-isometric. Two such groups are called commensurable.

It is important to notice that the inclusion of a subgroup of infinite index need not be a quasi-isometric embedding.

Remark 1. For uniformly discrete spaces a coarse lipschitz map is lipschitz iff it is injective. Similarly a quasi-isometric embedding is a bilipschitz embedding iff it is injective and a quasi-isometry is bilipschitz iff it is bijective.

Let X be a UDBG-space, and S ⊂ X.

Definition 2.7.

N_{r}(S) = {x ∈ X such that d(x, S) ≤ r}

and,

∂_{r}(S) = N_{r}(S) − S = {x ∈ X such that 0 < d(x, S) ≤ r}

The following definition of amenability is a direct generalization of a definition for groups due to Følner.

Definition 2.8. X a UDBG-space is amenable if there is a sequence {S_{i} ⊂ X} of finite subsets so that for any r > 0:

lim_{i→∞} \frac{|∂_{r}(S_{i})|}{|S_{i}|} = 0

Such a sequence is called a regular sequence.

Remark 2. Here and throughout |.| denotes cardinality.

It is more common to require that S_{i} ⊂ S_{i+1} and ∪_{i}S_{i} = X. This is equivalent [2]. A similar refinement we will have use for is that the S_{i} can be taken disjoint (so long as X is infinite). This is achieved by taking any regular sequence R_{i}, passing to a subsequence R_{n_{i}} with |R_{n_{i+1}}| >> |R_{n_{i}}| and then taking inductively S_{i} = R_{n_{i}} ∩ S_{i−1}^{c}. The S_{i} are disjoint by construction, and are a regular sequence since the R_{n_{i}} are, and the S_{i} differ from them by a set whose size goes to 0 as a fraction of |S_{i}|.

Lemma 2.1. Let X be a UDBG-space. The following are equivalent:

1. X is non-amenable.

2. For all C > 1 there is r such that for any S ⊂ X, |N_{r}(S)| ≥ C|S|

3. For some C > 1 there is r such that for any S ⊂ X, |N_{r}(S)| ≥ C|S|

4. For all C > 0 there is r such that for any S ⊂ X, |S| ≤ C|∂_{r}(S)|

5. For some C > 0 there is r such that for any S ⊂ X, |S| ≤ C|∂_{r}(S)|

Proof. It is immediate from the definition that all the conditions imply nonamenability. The last two conditions are just rephrasings of the second and third, and (2) ⇒ (3) is trivial. Step 1:(3) ⇒ (2)

For any S we have:

N_{s}(N_{t}(S)) ⊂ N_{s+t}(S)

so if (3) holds for C and r then:

|N_{kr}(S)| ≥ |N_{r}(N_{(k−1)r}(S))| ≥ 1/C|N_{(k−1)r}(S)|

so,

|S| ≤ C^{k}|N_{kr}(S)|

Thus for any C′ taking k large enough that C^{k} ≥ C′ and r′ = kr gives:

|S| ≤ C′|N_{r′}(S)|

as desired. Step 2:(1) ⇒ (5) If (5) does not hold, then there is a sequence {S_{i}} of sets in X for which the condition fails with r = i and C = \frac{1}{i}. This is then a regular sequence, which contradicts (1).

To a UDBG-space X we associate a family of simplicial complexes as follows:

Definition 2.9. For any r > 0, R_{r}(X), the r-Rips complex of X, is the simplicial complex with X as its 0-simplices and in which a set {x_{0}, x_{1}, ..., x_{k}} is the vertex set of a k-simplex if and only if d(x_{i}, x_{j}) ≤ r for all i and j.

We have inclusions R_{r}(X) ⊂ R_{r′}(X) for r ≤ r′. If f : X → Y is coarse lipschitz then for any r > 0 there is r′ so that f extends canonically to a simplicial map from R_{r}(X) to R_{r′}(Y). Thus we can define invariants of a UDBG-space as limits of simplicial invariants of its Rips complexes. In particular this lets us define homologies which are functorial in the coarse lipschitz category. We will use the following:

Definition 2.10. For X a UDBG space, the l^{p} homology groups H_{∗}^{(p)}(X) are defined as the limit as r → ∞ of the l^{p} homology groups of R_{r}(X).

If f : X → Y is coarse lipschitz then, as above, f induces a map on the Rips complexes and thereby a map f_{∗} : H_{∗}^{(p)}(X) → H_{∗}^{(p)}(Y). If f from X to itself is at bounded distance from the identity then the indecude map is the identity on homology. Thus a quasi-isometry induces an isomorphism of homology.

The groups H_{∗}^{(2)}(X) have nice duality properties, and have been studied by many authors. The group H_{1}^{(1)}(X) is related to coarse hyperbolicity in [7], settling a conjecture of Weinberger. The case of p = ∞ is of particular importance to us. Notice that for p = ∞ the homology with ℤ-coefficients make sense, while for p < ∞ we need to use ℝ for a sensible theory. The groups with p = ∞ and ℤ coefficients were introduced and studied in [2] under the name uniformly finite homology, written H_{∗}^{uf}(X). We will use the notation H_{∗}^{uf}(X) as well, reserving H_{∗}^{(∞)}(X) for ℝ coefficients.

Any subset S of X defines a uniformly finite 0-cycle. We denote the class of this cycle by [S]. The class [X] will be called the uniformly finite fundamental class of X.

3 Bilipschitz Structures

The goal of this section it to understand the relationship between bilipschitz equivalence and quasi-isometry.

Definition 3.1. Let X be a UDBG-space. We define the bilipschitz structures on X, S_{bilip}(X), as the set of pairs (Y, f), where Y is a UDBG-space and f : Y → X is a quasi-isometry, up to the relation that (Y_{1}, f_{1}) is equivalent to (Y_{2}, f_{2}) iff there is a bilipschitz map Y_{1} → Y_{2} which commutes up to bounded distance with the f_{i}.

Proposition 3.1. S_{bilip}(pt) = ℕ

Proof. Cardinality is clearly a complete invariant.

Proposition 3.2. S_{bilip}(ℤ) is uncountable.

Proof. Let t be any positive real number, and define f_{t} : ℤ → ℤ by n ↦ [tn] where [x] is the greatest integer less or equal to x. Each f_{t} is a quasi-isometry, so (ℤ, f_{t}) give elements x_{t} of S_{bilip}(ℤ).

If x_{s} and x_{t} are equivalent then there is a bilipschitz map ϕ : ℤ → ℤ such that |tϕ(n) − sn| is bounded independently of n. Equivalently |ϕ(n) − \frac{s}{t}n| is bounded independently of n, so that f\frac{s}{t} is at bounded distance from a bijection.

Lemma 3.3. If n ↦ [αn], α ∈ ℝ^{+}, is at bounded distance from a bijection then α = 1.

Proof. By replacing the map by its inverse, if necessary, we can assume α ≥ 1. Suppose ψ is such a bijection. ψ^{−1}{0, 1, ..., n} is at bounded distance from \{0, 1, ..., [\frac{n}{α}]\} and hence has cardinality at most a bounded amount more that \frac{n}{α}. But ψ is a bijection, so the cardinality of ψ^{−1}\{0, 1, ..., n\} is exactly n + 1. Letting n → ∞ proves α = 1.

This proves that the x_{t} are all distinct, and hence that S_{bilip}(ℤ) is uncountable.

We now generalize to arbitrary X.

Definition 3.2. Let X be a UDBG-space.

χ : S_{bilip}(X) → H_{0}^{uf}(X) is defined by (Y, f) ↦ f_{∗}([Y])

This is well defined because a bilipschitz map Y_{1} → Y_{2} carries [Y_{1}] to [Y_{2}], even on the level of chains.

We start by asking which classes in H_{0}^{uf}(X) arise in this way. If f : Y → X is a quasi-isometry then f_{∗}([Y]), as a chain, is non-negative and is strictly positive on a dense set.

Definition 3.3. A chain c ∈ C_{0}^{uf}(X) is positive if it is everywhere nonnegative and positive on a dense set. A class in H_{0}^{uf}(X) is positive if it is represented by a positive chain. The cones of positive chains and homology classes will be denoted C_{0}^{uf+}(X) and H_{0}^{uf+}(X) respectively.

Proposition 3.4. The image of χ is exactly H_{0}^{uf+}(X)

Proof. We know from the above that the image is contained in H_{0}^{uf+}. We show that every such c arises.

Fix c ∈ C_{0}^{uf+}, and define:

Y_{c} = {(x, n) : x ∈ X, 1 ≤ n ≤ c_{x}}

with the metric it inherits from X × ℕ.

Y_{c} has a canonical map π to X given by projection, and this map is a quasi-isometry by the positivity of c. Thus (Y_{c}, π) gives an element of S_{bilip}(X), and as π_{∗}([Y_{c}]) = c, χ((Y_{c}, π)) = [c].

Next we want to show that χ is a complete invariant. If z_{1} = (Y_{1}, f_{1}) and z_{2} = (Y_{2}, f_{2}) are elements of S_{bilip}(X), then there is a unique (up to bounded distance) quasi-isometry from Y_{1} to Y_{2} which commutes up to bounded distance with the f_{i}, namely g_{2}f_{1} where g_{2} is a coarse inverse for f_{2}. Then z_{1} and z_{2} are equivalent in S_{bilip}(X) iff there is a bilipschitz map within bounded distance of g_{2}f_{1}. Further, χ(z_{1}) = χ(z_{2}) iff (g_{2}f_{1})_{∗}([Y_{1}]) = [Y_{2}]. Thus we are reduced to the question: if ϕ : Y_{1} → Y_{2} is a quasi-isometry with ϕ_{∗}([Y_{1}]) = [Y_{2}] is ϕ at bounded distance from a bilipschitz equivalence? This is theorem 4.1 of the next section. Thus, using the next section, we have shown:

Theorem 3.5. For any UDBG-space X, S_{bilip}(X) = H_{0}^{uf+}(X).

It is not quite accurate to think of S_{bilip}(X) as measuring the number of different bilipschitz classes of spaces within a quasi-isometry type. For example, we saw above that S_{bilip}(ℤ) is uncountable even though any UDBG space quasi-isometric the ℤ is bilipschitz equivalent to it. This happens because there are many more self quasi-isometries of ℤ than self bilipschitz equivalences. The set of UDBG spaces quasi-isometric to X modulo bilipschitz equivalence is S_{bilip}(X)/QI(X). The identification of S_{bilip}(X) with H_{0}^{uf+}(X) is QI(X) equivariant. Call a UDBG space X rigid if any space quasi-isometric to X is bilipschitz equivalent to X. We have:

Corollary 3.6. X is rigid iff QI(X) acts transitively on H_{0}^{uf+}(X).

Deciding when this is true is difficult if H_{0}^{uf+}(X) is large as the group QI(X) is difficult to understand. Even the case of X = ℤ^{2} was open for quite a while. We now know that ℤ^{2} is not rigid ([3],[11]).

4 Constructing Bilipschitz Maps

Theorem 4.1. If f : X → Y is a quasi-isometry between UDBG-spaces with f_{∗}([X]) = [Y] then there is a bilipschitz map at bounded distance from f.

Proof. Observe that a quasi-isometry between UDBG-spaces is bilipschitz if and only if it is bijective. Since any map at bounded distance from a quasiisometry is itself a quasi-isometry, we need to see that there is a bijection at bounded distance from f.

We accomplish this in two stages. First we find an injection at bounded distance from f. If g is a coarse inverse for f then we also get an injection at bounded distance from g. The proof of the Schroeder-Berstein theorem then assembles these to form a bijection.

Lemma 4.2. There is an injective map at bounded distance from f.

Proof. Let r > 0 be fixed. To find an injection within r of f is to select, for each x in X an element of B_{r}(f(x)) without repetition. This is exactly the sort of question addressed by Hall’s selection theorem.

Theorem 4.3. (Hall’s Selection Theorem [8]) If we have α : A → F in(B) (the finite subsets of B), then there is an injective map ϕ : A → B with ϕ(a) ∈ α(a) for all a ∈ A iff for all S ⊂ A finite we have that

|S| ≤ | ∪_{s∈S} α(s)|

In the case of the lemma, we need for all S ⊂ X finite that |S| ≤ |N_{r}(f(S))|. The LHS is increased if we replace S by f^{−1}(f(S)). Thus we see:

Lemma 4.4. If f,X, and Y are as above, f is within r of an injection iff for all S ⊂ Y finite

|f^{−1}(S)| ≤ |N_{r}(S)|

We have

|f^{−1}(S)| = |Σ_{S}f_{∗}([X])|

where Σ_{S}c, for c ∈ C_{0}^{uf}, is just the sum of the coefficients of vertices in S So the condition of lemma 4.4 is satisfied iff

Σ_{S}f_{∗}([X]) ≤ |N_{r}(S)|

equivalently,

Σ_{S}(f_{∗}([X]) − [Y]) ≤ |∂_{r}(S)|

Let c be the chain f_{∗}([X]) − [Y]. It is, by construction, everywhere at least -1, and is non-negative on a dense set.

Lemma 4.5. Let Z be a UDBG-space, c ∈ C_{0}^{uf}(X) everywhere at least -1 and non-negative on a C-dense set. If c = ∂b for b ∈ C_{1}^{uf} then there is some r such that for any S ⊂ Z we have:

Σ_{S}c ≤ |∂_{r}(S)|

Proof. We need some constants. Let M be a bound on the absolute values of the coefficients of b, and α such that b ∈ C_{0}^{uf}(R_{α}(Z)).

Consider the graph Γ which is the subgraph of the 1-skeleton of R_{α} consisting of those edges in the support of b. We orient the edges such that all coefficients of b are positive. Let V be the maximal valence of any vertex of Γ. We can assume Γ has no oriented loops as we can subtract such a loop from b without increasing its norm or changing ∂b.

Fix S.

We next construct a family of oriented edge paths in Γ, with the following properties:

1. Every path ends at a point of S, and the number of paths ending at s is max(c_{s}, 0).

2. Any edge e is traversed at most b_{e} times.

3. Every path either has no initial point or starts at a point where c is -1.

4. No two paths have a common initial point.

Starting with any s ∈ S with c_{s} > 0, follow edges of Γ backwards, choosing at random if there is more than one. This process only gets stuck if it reaches a point without incoming edges. As we used an outgoing edge to reach this point, that implies c is negative at this point, and hence is -1.

This gives one path with the desired properties. Now subtract this path from b and repeat. Subtracting a path changes ∂b only at the endpoints, giving all but the second property above. This property also follows since each time an edge e is traversed, b_{e} decreases by 1, and when it reaches 0 that edge is removed from Γ.

Let r be any real greater than C.

We divide our family of paths into four sets:

P_{0} is paths starting in S. P_{1} is paths starting in ∂_{C}(S). P_{2} is paths starting in ∂_{r}(S) − ∂_{C}(S). P_{3} is paths starting outside ∂_{r}(S) (including the infinite paths)

Proposition 4.6. (Stokes’ Theorem)

Σ_{S}c = |P_{1}| + |P_{2}| + |P_{3}|

Proof. The boundaries of paths in P_{0} contribute nothing to Σ_{S}c, and the boundaries of the others each contribute 1.

We next estimate |P_{1}|, |P_{2}|, and |P_{3}|.

First, we see |P_{1}| ≤ |{z ∈ ∂_{C}(S) with c_{z} = −1}|. We call this set ∂_{C}^{−}(S), and the complement in ∂_{C}(S) we call ∂_{C}^{+}(S).

Lemma 4.7. There is A > 1, independent of r, such that

A|P_{2}| ≤ |∂_{r+C}(S)| + |∂_{C}^{+}(S)|

Proof. To each path in P_{2} we associate two points: its initial point, which by construction has c = −1, and a randomly chosen point which is within C of the initial point and has c ≥ 0. There is such a second point by the definition of C, and any point with c ≥ 0 can be associated to at most the maximal size of a C-ball (call this K) of points. Thus A = 1 + \frac{1}{K} works.

Lemma 4.8. There is B > 0, independent of r, such that:

|P_{3}| ≤ \frac{B(|∂_{r}(S)| − |∂_{C}(S)|)}{r − C}

Proof. Since each path in P_{3} leaves N_{r}(S), and each edge is at most length α, there must be at least \frac{r−C}{α} edges in the path in ∂_{r}(S) − ∂_{C}(S). And as each edge can be on at most M paths, there are at least |P_{3}|\frac{r−C}{M} edges, and therefore at least |P_{3}|\frac{r−C}{V Mα} points, in this region.

We can now finish the proof of lemma 4.5.

If \frac{|P_{2}|+|P_{3}|}{|P_{2}|} ≤ A then by lemmas 4.6 and 4.7 we have

Σ_{S}c ≤ |∂_{r+C}(S)|

While, if \frac{|P_{2}|+|P_{3}|}{|P_{2}|} ≥ A then by lemma 4.8

Σ_{S}c ≤ |∂_{C}(S)| + \frac{AB}{r − C} |∂_{r}(S) − ∂_{C}(S)|

If r > AB + C then the RHS is less than |∂_{r}(S)|.

Thus for r = AB + 2C, we have Σ_{S}c ≤ |∂_{r}(S)| in either case.

This bound is exactly what was needed to produce an injection, as the class f_{∗}([X]) − [Y] is a boundary by assumption.

Applying this to f and a coarse inverse for f, we get injections h_{1} : X → Y and h_{2} : Y → X, so that h_{1} is at bounded distance from f, as is h_{2}^{−1} wherever it is defined. The Schroeder-Berstein theorem (as proven in [10], for example) produces a bijection ϕ : X → Y which everywhere agrees with h_{1} or h_{2}^{−1} and hence is at bounded distance from f.

5 Free Products

We recall the following:

Theorem 5.1. ([2]) If X is a non-amenable UDBG-space then H_{0}^{uf}(X) = 0 iff X is non-amenable.

We give a new proof in a later section (see Theorem 7.1).

If G_{1} and G_{2} are finitely generated groups, then so is their free product. It is not hard to see that the bilipschitz class of the free product is determined by the bilipschitz classes of the factors: the obvious induced map on normal forms is a bilipschitz equivalence.

Theorem 5.2. If Γ_{1} and Γ_{2} are quasi-isometric, finitely generated nonamenable groups then for any finitely generated group G, Γ_{1} ∗ G and Γ_{2} ∗ G are quasi-isometric.

Proof. By Theorem 7.1 or [2], H_{0}^{uf}(Γ_{1}) = 0. By theorem 4.1, Γ_{1} and Γ_{2} are bilipschitz equivalent, and thus so are Γ_{1} ∗ G and Γ_{2} ∗ G.

This is not always true for amenable groups: ℤ/2ℤ∗ℤ/2ℤ is infinite while {e} ∗ ℤ/2ℤ is finite, and ℤ/2ℤ ∗ ℤ/3ℤ is not quasi-isometric to either.

This produces quasi-isometries which are algebraically surprising. As an example, we work out the following case:

Corollary 5.3. Let Γ = Σ_{g_{1}} ∗ Σ_{g_{2}} ∗ ... ∗ Σ_{g_{n}} where Σ_{g} is the fundamental group of a surface of genus g. Then Γ is quasi-isometric to one of ℤ^{2}, Σ_{2}, ℤ^{2} ∗ ℤ^{2}, ℤ^{2} ∗ Σ_{2}, or Σ_{2} ∗ Σ_{2}.

Proof. All the surface groups of higher genus are of finite index in Σ_{2} and therefore quasi-isometric to Σ_{2}. As these are non-amenable they are bilipschitz equivalent. Thus by Theorem 5.2 we only need to consider the case that each g_{i} is 1 or 2.

Σ_{2} ∗ Σ_{2} has a subgroup of index k isomorphic to Σ_{k+1} ∗ Σ_{2} ∗ Σ_{2} ∗ ...Σ_{2} (k-times). This is, again by Theorem 5.2, quasi-isometric to Σ_{2} ∗ Σ_{2} ∗ ... ∗ Σ_{2} (k + 1-times). Thus the free product two or more surface groups of higher genus is quasi-isometric to Σ_{2} ∗ Σ_{2}.

In the same way, the free product of at least one ℤ^{2} and at least one Σ_{2} is quasi-isometric to ℤ^{2} ∗ Σ_{2}.

While ℤ^{2} is amenable, ℤ^{2} ∗ℤ^{2} is non-amenable and so again by passing to subgroups of finite index we see that any free product of at least two copies of ℤ^{2} is quasi-isometric to ℤ^{2} ∗ ℤ^{2}.

That reduces us to the given list.

This should be contrasted with:

Proposition 5.4. Γ_{1} = Σ_{a_{1}} ∗ Σ_{a_{2}} ∗ ... ∗ Σ_{a_{m}} and Γ_{2} = Σ_{b_{1}} ∗ Σ_{b_{2}} ∗ ... ∗ Σ_{b_{n}} are commensurable iff

\frac{χ(Γ_{1})}{m − 1} = \frac{χ(Γ_{2})}{n − 1}

Proof. We will think of these free products and their subgroups of finite index as fundamental groups of graphs of groups, see [14].

Γ_{1} is the fundamental group of the following tree of groups: Let T have m + 1 vertices, one each with vertex group Σ_{a_{i}}, and one with trivial vertex group. Every vertex with non-trivial vertex group is connected by an edge to the vertex with trivial vertex group, and all of these edges have trivial edge group. Thus T is an m-pointed star with the Σ_{a_{i}} on the points.

A subgroup Γ′ of index k in Γ_{1} is of the form Σ_{g_{1}} ∗ Σ_{g_{2}} ∗ ... ∗ Σ_{g_{r}} ∗ F_{l} where F_{l} is the free group of rank l. Considering the corresponding graph covering T we see that the multiset S = {g_{1}, ..., g_{r}} can be partitioned into S_{1}, ..., S_{m} where S_{i} are the genera of the groups at the vertices lying over Σ_{a_{i}}. Thus, for each s ∈ S_{i} we have that Σ_{s} is of finite index in Σ_{a_{i}} and thus that a_{i} − 1 divides s − 1. Further, since this is to be a k-fold covering of graphs of groups, we have the Euler characteristic formula Σ_{s∈S_{i}}(2 − 2s) = k(2 − 2a_{i}). We can compute the Euler characteristic of the free fractor, and hence its rank, from the Euler characteristics of graphs of groups:

Σ_{s∈S}(2 − 2s) − r − l + 1 = χ(Γ′) = kχ(Γ_{1})

We can calculate Σ_{s∈S}(2−2s) as Σ_{1}^{m}Σ_{s∈S_{i}}(2−2s) which is, as in the paragraph above, equal to Σ_{1}^{m}k(2 − 2a_{i}). This in turn is equal to χ(Γ_{1}) + m − 1. Thus we have:

Lemma 5.5. If Γ is a free product of m surface groups and Γ′ is a subgroup of index k, where Γ′ is a free product of r surface groups and a free group of rank l, then

l = k(m − 1) − r + 1

Conversely, given a partition as above we can produce a corresponding graph of groups which is a finite cover of the graph for Γ_{1}. This graph must have Euler characteristic 1 − l, and so can be chosen connected exactly when the rank of the free factor given by the lemma is non-negative.

So, to determine if Γ_{1} and Γ_{2} are commensurable we need to decide if there is a multiset S with partitions corresponding to Γ_{1} and Γ_{2}, satisfying the divisibility requirements for each, and which give the same (non-negative) rank for the free factor. If this corresponds to a subgroup of index k_{i} in Γ_{i} then by the lemma k_{1}(m − 1) = k_{2}(n − 1). Then, as χ(Γ′) = k_{i}χ(Γ_{i}), we see:

\frac{χ(Γ_{1})}{m − 1} = \frac{χ(Γ_{2})}{n − 1}

which shows that the given condition given is necessary.

Going the other way, if this equality holds, we can easily find a multiset S of positive integers with partitions {A_{1}, ..., A_{m}} and {B_{1}, ..., B_{n}} so that Σ_{s∈A_{i}}(2 − 2s) = (2 − 2a_{i})k_{1} and Σ_{s∈B_{i}}(2 − 2s) = (2 − 2b_{i})k_{2} for some k_{1} and k_{2}. By replacing every s with N!(s+1)−1 for N large we increase k_{1} and k_{2}, and gain the divisibility requirements a_{i} − 1|s − 1 for s ∈ A_{i} and b_{i} − 1|s − 1 for s ∈ B_{i} (if any of the a_{i} or b_{i} is 0, all s in the corresponding A_{i} or B_{i} are automatically 0). Since the k_{i} can be increased arbitrarily in this way, we can also make the rank of the free factors predicted by the lemma non-negative. Thus, for N large enough, the partition corresponds to a connected graph of groups coving both of the original trees of groups, and therefore Γ_{1} and Γ_{2} are comensurable.

This shows that in general the quasi-isometric and commensurable classifications of groups are very different. We have enough examples to show that many commensurability invariants are not quasi-isometry invariants. The next corollary answers a question of Gromov.

Corollary 5.6. The sign of the Euler characteristic is not a quasi-isometry invariant.

Proof. Let G = Σ_{2} × Σ_{2} and H = Σ_{2}.

Take G_{k} a subgroup of G of index k, and H_{l} a subgroup of H of index l. All the groups are non-amenable, so all groups of the for G_{k} ∗ H_{l} are

quasi-isometric, but

χ(G_{k} ∗ H_{l}) = kχ(G) + lχ(h) − 1 = 4k − 2l − 1

which can clearly be of either sign.

This shows that the quasi-isometries produced by theorem 5.2 are not “algebraic”, as the sign of the Euler characteristic is a commensurability invariant, and is the same for different uniform lattices in the same Lie group.

All that was really used about the Euler characteristic here is that it is multiplicative under finite coverings and additive for free products. This is a property of many other invariants, L^{2}-betti numbers for example. Exactly the same construction shows no such invariants, for example ratios of L^{2}- betti numbers, can be quasi-isometry invariants. Note that the non-amenable condition will not get in the way as the L^{2}-betti numbers of any amenable group are all zero ([4]).

6 The Von Neumann Conjecture

The Von Neumann conjecture is that a finitely generated group is either amenable or contains a non-abelian free subgroup. While this is know to be false ([12]), it is a good intuitive guide and holds under some restrictions, for example for linear groups there is the Tits alternative [15]. In this section we give a geometric version of the conjecture, and prove it using our earlier results.

To give a geometric version of the conjecture, one needs a geometric analogue of having a free non-abelian subgroup (without loss of generality of rank 2). We replace “subgroup” with “an action of”. If Γ is a group, any subgroup acts both on the right and the left. The left action is by isometries, and the right by bilipschitz maps at bounded distance from the identity. Having a large group of isometries forces more symmetry than it is reasonable to expect from a general space, so we ask for an action which behaves like the action on the right.

Definition 6.1. If X is a UDBG space, and Γ a group then we call an action of Γ on X translation-like if:

1. For each γ ∈ Γ the map x ↦ γx is at bounded distance from the identity.

2. Γ acts freely.

Theorem 6.1. (Geometric Von Neumann conjecture reformulated) A UDBGspace X is non-amenable iff it admits a translation-like action of a nonabelian free group.

Such an action would partition X into orbits, and each orbit would naturally have the structure of a 4-valent tree (the Cayley graph of the free group). Further, these trees would have uniformly bounded edge lengths. Conversely, given such a partition, we can simply build the action orbit by orbit. Thus to prove the theorem we need to find such an orbit-like partition. Since the 4-valent and 3-valent trees are bilipschitz equivalent (use theorem 4.1 or [13]), it is equivalent to find such a partition by 3-valent trees.

Theorem 6.2. (Geometric Von Neumann Conjecture) Let Z be a UDBGspace. Z is non-amenable iff Z has a partition whose pieces are uniformly lipschitz embedded copies of the tri-valent tree.

Proof. If Z admits such a decomposition then it is clearly non-amenable, simply apply any of the criteria of lemma 2.1 piecewise.

If Z is non-amenable, we produce a decomposition with pieces quasiisometric to the tri-valent tree, and then use theorem 4.1 to improve them to lipschitz. From now on we assume Z is non-amenable.

Lemma 6.3. There is a bilipschitz map f from Z × {0, 1} to Z at bounded distance from π_{Z} (projection onto Z), so that for all z ∈ Z f(z, 0) ≠ z and f(z, 1) ≠ z.

Proof. We simply copy the proof of theorem 4.1, but as Z is non-amenable it is much easier, even with the extra restriction. If f is to be within r of the projection, the set of possible values for f(z, ϵ) is B_{r}(z) − {z}. So, for any S in Z, the set of possible values for f(S × {0, 1}) is at least ∂_{r}(S). By lemma 2.1, |∂_{r}(S)| can be made larger than |S × {0, 1}| = 2|S| by taking r large enough. Thus, as in theorem 4.1, we can produce an injection with the desired properties. The other way we have the inclusion z ↦ (z, 0), which can be moved to an injection so that z goes to neither (z, 0) nor (z, 1) in exactly the same way. The Schroeder-Berstein theorem produces f.

Given f, let Γ be the graph with vertex set Z and directed edges from z to f(z, 0)) and (z, f(z, 1)). Thus every vertex has valence three (the obvious two “outgoing” edges, and the “incoming” edge from π_{Z}f^{−1}(z). The fact that f is at bounded distance from π_{Z} means we have a bound on the lengths of the edges is Γ.

Proposition 6.4. Each connected component of Γ has at most one loop.

Proof. Consider a path in Γ. Since each vertex has only one incoming edge, any path starting with an oriented edge must be oriented. Thus any path is either oriented, or there is some vertex with both of its outgoing edges on the path. In this case the path is the union of two oriented paths leaving that point. These two branches can never meet again as that would require a point with two incoming edges. hus any loop in Γ is oriented,

If there are two loops in a component, connect them with a path. Whichever type of path it is, it has one endpoint with the end of the path oriented towards it. This is impossible as this point is also on a oriented loop, and would therefore need two incoming edges.

Removing one edge from each loop from Γ to get a graph Γ′. Each component is a tree, which is either the 3-valent tree or a tree with one vertex of valence 2, and the rest of valence 3. This latter tree is quasi-isometric to the 3-valent tree simply by collapsing one edge adjacent to the vertex of valence 2, and therefore by theorem 4.1 it is bilipschitz to the 3-valent tree.

Remark 3. Translation like actions seem to be interesting objects which have not really been studied. In particular, there are many several (often false) conjectures of the form “A finitely generated group has property ... iff it contains a subgroup isomorphic to ...”. If the property is geometric in nature, it may be more reasonable to hope for a translation-like action. The above “Geometric Von Neumann Conjecture” is one example of this. Some other interesting questions along these lines are:

(Geometric Burnside Problem) Does every infinite finitely generated group admit a translation-like ℤ action?

Of course if the group contains any element of infinite order it will.

Similarly we can ask:

(Geometric Gersten Problem) Does every finitely generated, non word hyperbolic group admit a translation-like action of some Baumslag-Solitar group?

Probably these should be stated for some mildly restricted classes of UDBG spaces rather than just for groups. It might be more reasonable to ask for the action just on some space or group within the given quasi-isometry class.

7 Amenability and 0-dimensional Homology

Theorem 7.1. Let X be a UDBG-space, and p ∈ (1, ∞]. X is non-amenable iff H_{0}^{(p)}(X) = 0.

Proof. If X is amenable we construct a non-trivial 0-cycle as follows:

Let S_{i} be a regular sequence with the S_{i} disjoint (see the remark preceding lemma 2.1). Then for a sequence a_{i} of positive reals, c = Σ_{i}a_{i}S_{i} is an l^{p} chain iff Σ_{i}a_{i}^{p}|S_{i}| < ∞. Now, if c = ∂b then, for each i, the total flow through ∂_{r}S_{i} is at least a_{i}|S_{i}| by Stokes theorem. Then, by Holder’s inequality:

||b||^{p} ≥ Σ_{i}(\frac{a_{i}|S_{i}|}{|∂_{r}S_{i}|})^{p}|∂_{r}S_{i}|

= Σ_{i}a_{i}^{p}|S_{i}|(\frac{|S_{i}|}{|∂_{r}S_{i}|})^{p−1}

(\frac{|S_{i}|}{|∂_{r}S_{i}|})^{p−1} → ∞ since, by assumption, \frac{|S_{i}|}{|∂_{r}S_{i}|} does. Thus it is easy to produce a sequence a_{i} which gives an l^{p} chain but cannot be an l^{p} boundary.

For the other direction, suppose X is non-amenable and c is an l^{p} 0-chain on X. Write X as a disjoint union of trivalent trees, and choose one edge in each tree and cut it to get X as a union of rooted binary trees. Then c restricts to each tree to give an l^{p} chain.

Lemma 7.2. Let T be the infinite rooted binary tree. There is, for each p, a bounded operator I : C_{0}^{l^{p}}(T) → C_{1}^{l^{p}}(T) such that ∂I = Id.

Proof. For q in T, define Iq to be the 1-chain supported on the binary subtree rooted at q with each edge having weight 2^{−d(−,q)}. Then ∂Iq = q.

We define Ic for any 0-chain c by linearity. The sums are finite as each edge has non-zero weight in Iq for unly finitely many q.

We need to see that the I so defined takes l^{p} to l^{p}, and is bounded. For this we use a special case of the Marcinkiewicz interpolation theorem ([5]).

Theorem 7.3. (Marcinkiewicz Interpolation) If T is bounded from l^{∞} → l^{∞} and is weak type (1, 1) then T is bounded from l^{p} to l^{p} for all p > 1.

Recall that T weak type (1, 1) means that there is C such that for any α and any f in l^{1}:

λ_{f}(α)|{v : T f ≥ α}| ≤ C||f||_{1}/α

.

Lemma 7.4. I maps l^{∞} to l^{∞} and c_{0} to c_{0} with ||I||_{∞} ≤ 1.

Proof. For any edge e, If_{e} is the sum along the path from e to root of 2^{−d(v,e)}f_{v}. Each f_{v} ≤ ||f||_{∞}, and the sum is therefore less than the sum of the geometric series Σ_{d=1}^{∞}2^{−d}||f||_{∞} which is equal to ||f||_{∞}. Thus I maps l^{∞} to itself with norm ≤ 1. The space c_{0} of functions which go to 0 at ∞ are isometrically embedded in l^{∞} as the closure of the functions of finite support, so we only need to see that I takes things of finite support into c_{0}. For any v, Iδ_{v} is in c_{0} and as everything of finite support is a finite linear combination of these, the result follows.

Lemma 7.5. I is weak type (1, 1).

Proof. Fix α.

We look for f of l^{1}-norm 1 such that If ≥ α on as many edges as possible. By lemma 7.4 If is ≥ α only on finitely many edges. Since the part of f supported below these edges does not contribute to any edge which is ≥ α, we can take f to have finite support. Let A_{n} be the set of f with l^{1}-norm 1 which are supported in the ball of radius n around the root.

We show, by induction on n, that

sup_{f∈A_{n}}λ_{If}(α) ≤ 2([\frac{1}{α}] − 1)

[x] is the greatest integer ≤ x.

The case n = 0 holds as A_{0} contains only the function which is 1 at the root and 0 elsewhere. For this f, If is \frac{1}{2^{n}} on exactly 2^{n} edges (here n ≥ 1). Thus |\{e : If_{e} ≥ α\}| = 2^{[− log_{2} α]+1} − 2 ≤ 2([\frac{1}{α}] − 1)

Take f ∈ A_{n+1}

Call the components of T − {root} the left and right subtrees, with roots {root_{l}} and {root_{r}}.

Let g_{l}(resp. g_{r}) be f restricted to the left (resp. right) subtree. Consider f_{l} = g_{l} + \frac{f(\{root\})}{2}δ_{\{root_{l}\}}, and similarly for f_{r}. Then If_{r} and

If_{l} agree with the restrictions of If, and each is in A_{n}. Conversely, these determine f. Let t be the l^{1} norm of f_{l}, then:

λ_{f}(α) ≤ ([\frac{1}{tα}] + [\frac{1}{(1 − t)α}] + 2χ_{[α,1−α]}(t))

The last term comes from the edges coming from the root. And therefore:

λ_{f}(α) ≤ sup_{t∈[0,1]}([\frac{1}{tα}] + [\frac{1}{(1 − t)α}] + 2χ_{[α,1−α]}(t))

The desired bound now follows from the fact that λ_{g}(α) = 0 for α > \frac{1}{2} for any g of l^{1}-norm 1.

So, by the Interpolation theorem, I is bounded from l^{p} to l^{p} for all p ∈ (1, ∞].

Now combining the I from each tree gives a splitting of C_{1}^{(p)}(X) → C_{0}^{(p)}(X), and so H_{0}^{(p)}(X) = 0.

The case p = ∞ is a theorem of ([2]). We can also give a new proof of the following theorem which was asserted

in ([1]).

Theorem 7.6. If Z a UDBG-space, c ∈ C_{0}^{uf}(Z), then [c] = 0 iff there are r and C such that for all S ⊂ Z:

|Σ_{S}c| ≤ C|∂_{r}S|

Proof. Let n ∈ ℕ be large enough that c + n[X] is positive.

Consider the elements x_{n} and y_{n} of S_{bilip}(Z) corresponding to c + n[Z] and n[Z] respectively, with representatives (X_{n}, f_{n}) and (Y_{n}, g_{n}).

Clearly [c] = 0 iff f_{∗}([X_{n}]) = g_{∗}([Y_{n}]).

By theorem 3.5, this is true iff there is a bilipschitz map h : X_{n} → Y_{n}, commuting up to bounded distance with f_{n} and g_{n}. Will try to build h as in the proof of theorem 4.1.

Fix r. A map h : X_{n} → Y_{n} commutes within r with f and g iff

h(x) ∈ {y : d(f(x), g(y)) ≤ r}

for all x ∈ X_{n}.

Thus, for any set x in X_{n}, the possible values for h(x) are f^{−1}(B_{r}(g(x)). So, if S ⊂ X_{n}, the set of points in Y_{n} which could be in the image of S under h is g^{−1}(N_{r}(f(S)). To find an injective map Hall’s Selection Theorem requires that this be no smaller than S. This is hardest when S = f^{−1}(f(S)). We can then write things in terms of A = f(S) ⊂ Z. We need, for all A ⊂ Z finite that:

|f^{−1}(A)| ≤ |g^{−1}(N_{r}(A))|

In terms of c, this says:

Σ_{A}c + n[Z] ≤ Σ_{N_{r}A}n[Z]

or,

Σ_{A}c ≤ Σ_{∂_{r}A}n[Z]

or

Σ_{A}c ≤ n|∂_{r}A|

This holds once n is sufficiently large iff there are C and r such that

Σ_{A}c ≤ C|∂_{r}A|

To build the injection the other way, we need

Σ_{A}(n[Z]) ≤ Σ_{N_{r}A}(c + n[Z])

equivalently,

Σ_{A}(−c) ≤ Σ_{∂_{r}A}(c + n[Z])

which holds for n sufficiently large iff there are C and r such that

Σ_{A}(−c) ≤ C|∂_{r}A|

The two conditions together give the Theorem.

If c ∈ C_{0}^{uf}(X) = C_{0}^{(∞)}(X, ℤ) is the boundary of an l^{∞} cycle b with ℝ coefficients, then the Stokes’ theorem argument still forces that for some C and r, we have, for all S ⊂ X finite:

|Σ_{S}c| ≤ C|∂_{r}S|

And therefore, by theorem 7.6 , [c] = 0 in H_{0}^{uf}(X). In other words, the map H_{0}^{(∞)}(X, ℤ) → H_{0}^{(∞)}(X, ℝ) is injective.

What is somewhat more surprising is that this map is usually surjective. We say X is coarsely connected if for r large enough R_{r}(X) is connected. All groups with their word metrics satisfy this, as do almost all UDBG spaces we care about.

Lemma 7.7. If X is an infinite, coarsely connected UDBG space then

H_{0}^{(∞)}(X, ℤ) → H_{0}^{(∞)}(X, ℤ)

is an isomorphism.

Proof. We have already seen injectivity. The short exact sequence of normed abelian groups:

0 → ℤ → ℝ → ℝ/ℤ → 0

induces a long exact sequence in l^{∞} homology

... → H_{0}^{(∞)}(X, ℤ) → H_{0}^{(∞)}(X, ℝ) → H_{0}^{(∞)}(X, ℝ/ℤ) → 0

Since ℝ/ℤ is bounded, H_{0}^{(∞)}(X, ℝ/ℤ) = H_{0}^{lf}(X, ℝ/ℤ). The latter group is, by definition, the limit as r → ∞ of H_{0}^{lf}(R_{r}(X), ℝ/ℤ) which is trivial for r large enough as, by assumption, R_{r}(X) is connected and non-compact.

This shows that H_{0}^{uf}(X) has the structure of a ℝ vector space. This can be seen concretely: for α ∈ H_{0}^{uf}(X) take r large enough so that R_{r}(X) is connected and α is represented by a chain c on R_{r}(X). Then c = ∂b for some b (possibly with unbounded coefficients). Take t ∈ ℝ and define tα = ∂[tb]. It is not hard to see that this gives a well defined class in H_{0}^{uf}(X).

References

[1] J. Block and S. Weinberger, Aperiodic tilings, positive scalar curvature, and amenability, Journal of the AMS, 5 (1992).

[2] , Large scale homology theories and geometry, AMS/IP Studies in Advanced Mathematics, 2 (1997).

[3] D. Burago and B. Kleiner, Separated nets in euclidean space and jacobians of bilipschitz map, Preprint, (1997).

[4] J. Cheeger and M. Gromov, L_{2}-cohomology and group cohomology, Topology, 25 (1986).

[5] G. Folland, Real Analysis. Modern Techniques and their Applications, Wiley, 1984.

[6] S. Gersten, Bounded cocycles and combings of groups, International J. of Algebra and Computation, 2 (1992).

[7] , A homological characterization of hyperbolic groups, Preprint, (1998).

[8] J. Graver and M. Watkins, Combinatorics with Emphasis on the Theory of Graphs, Springer-Verlag, 1977.

[9] M. Gromov, Asymptotic invariants of infinite groups, Geometric Group Theory, LMS lecture notes, 182 (1993).

[10] P. Halmos, Naive Set Theory, Springer-Verlag, 1973.

[11] C. McMullen, Lipschitz maps and nets in euclidean space, preprint, (1997).

[12] V. Olshanskii, On the question of the existence of an invariant mean on a group, Uzpekhi Mat. Nauk., 35 (1980).

[13] P. Papasoglu, Homogeneous trees are bi-lipschitz equivalent, Geom. Dedicata, 54 (1995).

[14] J. Serre, Trees, Springer-Verlag, 1980.

[15] J. Tits, Free subgroups in linear groups, J. Algebra, 20 (1972).

Kevin Whyte Dept. of Mathematics University of Utah Salt Lake City, UT 84112 E-mail: kwhyte@math.utah.edu