POINCARÉ INEQUALITIES, EMBEDDINGS, AND WILD GROUPS

ASSAF NAOR AND LIOR SILBERMAN

Abstract. We present geometric conditions on a metric space (Y, d_{Y}) ensuring that almost surely, any isometric action on Y by Gromov’s expander-based random group has a common fixed point. These geometric conditions involve uniform convexity and the validity of nonlinear Poincaré inequalities, and they are stable under natural operations such as scaling, Gromov-Hausdorff limits, and Cartesian products. We use methods from metric embedding theory to establish the validity of these conditions for a variety of classes of metric spaces, thus establishing new fixed point results for actions of Gromov’s “wild groups”.

1. Introduction

We establish the existence of finitely generated groups with strong fixed point properties. The seminal work on this topic is Gromov’s construction [14] of random groups from expander graph families, leading to a solution [17, Sec. 7] of the Baum-Connes conjecture for groups, with coefficients in commutative C^{∗}-algebras. Here we study Gromov’s construction, highlighting the role of the geometry of the metric space on which the group acts. As a result, we isolate key properties of the space acted upon that imply that any isometric action of an appropriate random group has a common fixed point. Using techniques from the theory of metric embeddings in order to establish these properties, we obtain new fixed point results for a variety of spaces that will be described below. This answers in particular a question of Pansu [35] (citing Gromov). In fact, we prove the stronger statement that for every Euclidean building B (see [23]), there exists a torsion-free hyperbolic group for which every isometric action on ℓ_{2}(B) has a common fixed point (this statement extends to appropriate ℓ_{2} products of more than one building). Thus, following Ollivier’s terminology [31], Gromov’s groups are even “wilder” than previously shown.

For p ⩾ 1 say that a geodesic metric space (Y, d_{Y}) is p-uniformly convex if there exists a constant c > 0 such that for every x, y, z ∈ Y, every geodesic segment γ : [0, 1] → Y with γ(0) = y, γ(1) = z, and every t ∈ [0, 1] we have:

d_{Y} (x, γ(t))^{p} ⩽ (1 − t)d_{Y} (x, y)^{p} + td_{Y} (x, z)^{p} − ct(1 − t)d_{Y} (y, z)^{p}.  (1.1)

It is immediate to check that (1.1) can hold only for p ⩾ 2. The inequality (1.1) is an obvious extension of the classical notion of p-uniform convexity of Banach spaces (see, e.g., [5]), and when p = 2 it is an extension of the CAT(0) property (see, e.g., [9]).

2010 Mathematics Subject Classification. 20F65,58E40,46B85.

Key words and phrases. Gromov’s random groups, fixed points, Poincaré inequalities.

A.N. is supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

This work was completed when L.S. was an intern at Microsoft Research, Redmond WA, June–August 2004. He wishes to thank Microsoft Research for their hospitality.

We shall say that a metric space (Y, d_{Y}) admits a sequence of high girth p-expanders if there exists k ∈ ℕ, γ, η > 0, and a sequence of k-regular finite graphs {G_{n} = (V_{n}, E_{n})}_{n=1}^{∞} with lim_{n→∞} |V_{n}| = ∞ such that the length of the shortest non-trivial closed path (the “girth”) in G_{n} is at least η log |V_{n}|, and such that for every f : V_{n} → Y we have,

\frac{1}{|V_{n}|^{2}} ∑_{u,v∈V_{n}} d_{Y} (f(u), f(v))^{p} ⩽ \frac{γ}{|E_{n}|} ∑_{uv∈E_{n}} d_{Y} (f(u), f(v))^{p}.  (1.2)

When Y = ℝ it is well-known that inequality (1.2) with p = 2 is equivalent to the usual notion of combinatorial expansion (for a survey on expander graphs see [18], especially Section 2). It is less well-known [27] that this is true for all 1 < p < ∞; we reproduce the proof in Lemma 4.4. It is also worth noting that unless Y consists of a single point, the sequence of graphs considered must necessarily be a sequence of combinatorial expanders.

As we shall see later, a large class of metric spaces of interest consists of spaces that are both p-uniformly convex and admit a sequence of high girth p-expanders. In fact, in all cases that we study, the Poincaré inequality (1.2) holds for every sequence of combinatorial expanders. It is an open problem whether the existence of a sequence of bounded degree graphs satisfying (1.2) implies the same conclusion for all combinatorial expanders, but we will not deal with this issue here as the existence statement suffices for our purposes.

Gromov’s remarkable construction [14] of random groups is described in detail in Section 6. In order to state our results, we briefly recall it here. Given a (possibly infinite) graph G = (V, E), and integers j, d ∈ ℕ, a probability distribution over groups Γ associated to G and generated by d elements s_{1}, …, s_{d} is defined as follows. Orient the edges of G arbitrarily. For every edge e ∈ E choose a word w_{e} of length j in s_{1}, …, s_{d} and their inverses uniformly at random from all such (2d)^{j} words, such that the random variables {w_{e}}_{e∈E} are independent. Each cycle in G induces a random relation obtained by traversing the cycle, and for each edge e of the cycle, multiplying by either w_{e} or w_{e}^{−1}, depending on whether e is traversed according to its orientation or not. These relations induce the random group Γ = Γ(G, d, j).

Our main result is:

Theorem 1.1. Assume that a geodesic metric space (Y, d_{Y}) is p-uniformly convex and admits a sequence of high girth p-expanders {G_{n} = (V_{n}, E_{n})}_{n=1}^{∞}. Then for all d ⩾ 2 and j ⩾ 1 with probability tending to 1 as n → ∞, any isometric action of the group Γ(G_{n}, d, j) on Y has a common fixed point.

It was shown in [14, 32, 3] that for every d ⩾ 2, for large enough j (depending only on d and the parameters k, η), the group Γ(G_{n}, d, j) is torsion-free and hyperbolic with probability tending to 1 as n → ∞.

Using a variety of results and techniques from the theory of metric embeddings, we present a list of metric spaces (Y, d_{Y}) for which the conditions of Theorem 1.1 are satisfied^{1}. These spaces include all Lebesgue spaces L_{q}(μ) for 1 < q < ∞, and more generally all Banach lattices which are p-uniformly convex for some p ∈ [2, ∞). Moreover, they include all (possibly infinite dimensional) Hadamard manifolds (in which case p = 2, c = 1), all Euclidean buildings (p = 2, c = 1, again), and all p-uniformly convex Gromov hyperbolic metric spaces of bounded local geometry. It was asked by Pansu in [35] whether for every symmetric space or Euclidean building an appropriate random group has the fixed point property. Our results imply that this is indeed the case. As a corollary, by a “gluing” construction of [2] (see also [13, Sec. 3.3]) it follows that there exists a torsion-free group that has the fixed point property with respect to all the spaces above. This yields one construction of “wild groups”. Alternatively, one could follow the original approach of Gromov [14], who considers the group Γ = Γ(G, d, j), where the graph G is the disjoint union of an appropriate subsequence of the expanders {G_{n}}_{n=1}^{∞} from Theorem 1.1, which is a torsion-free group with positive probability [14, 32, 3]. For this group Γ, Pansu asked [35] whether it has the fixed point property with respect to all symmetric spaces and all buildings of type Ã_{n}. Our result implies that for every d, j, almost surely Γ will indeed have this fixed point property, and also on all ℓ_{2} products of such spaces.

1Note that our conditions on the metric space (Y, d_{Y}) in Theorem 1.1 are closed under ℓ_{p} sums (⊕_{s=1}^{N}Y_{s})_{p}, provided that in (1.2), the same high-girth expander sequence works for all the Y_{s}. This holds true in all the examples that we present, for which (1.2) is valid for every connected graph, with γ depending only on p, the spectral gap of the graph, and certain intrinsic geometric parameters of Y.

Theorem 1.2. Let G be the disjoint union of a family of high-girth combinatorial expanders (that is, of a family of graphs for which a single γ applies in (1.2) for all ℝ-valued functions). Let d ⩾ 2 and j ⩾ 1. Then with probability 1 the group Γ(G, d, j) has the fixed-point property for isometric actions on all p-uniformly convex Banach Lattices, all buildings associated to linear groups, all non-positively curved symmetric spaces, and all p-uniformly convex Gromov hyperbolic spaces. The fixed-point property also holds for an ℓ_{p}-product of p-uniformly convex spaces, as long as the constant in (1.2) is uniformly bounded for these spaces.

Problems similar to those studied here were also investigated in [20, 19], where criteria were introduced that imply fixed point properties of random groups in Żuk’s triangular model [40]. These criteria include a Poincaré-type inequality similar to (1.2), with the additional requirement that the constant γ is small enough (in our normalization, they require p = 2 and γ < 2). Unfortunately, it is not known whether it is possible to establish such a strong Poincaré inequality for the spaces studied here, except for CAT(0) manifolds, trees, and a specific example of an Ã_{2} building (see [20, 19]). Our approach is insensitive to the exact value of γ in (1.2). In fact, γ can be allowed to grow to infinity with |V_{n}|; see (4.4) and Theorem 7.6 below.

It was shown in [36] that any cocompact lattice Γ in Sp_{n,1}(ℝ) admits a fixed-point-free action by linear isometries on L_{p} for any p ⩾ 4n + 1. Also, Γ acts by isometries on the symmetric space of Sp_{n,1}(ℝ) (which is a Hadamard manifold) without fixed points. Thus, while it is known [14, 37] that Gromov’s random groups have property (T), our results do not from follow from property (T) alone. See [12, 4] for a discussion of the relation between property (T) and fixed points of actions on L_{p}.

We end this introduction by noting that the above gluing-type construction based on Theorem 1.1 yields a non-hyperbolic group. This is necessary, since it was shown in [39] that any hyperbolic group admits a proper (and hence fixed-point free) isometric action on an L_{p}(μ) space for p large enough. It remains open whether there exists a hyperbolic group with the fixed-point property on all symmetric spaces and Euclidean buildings. Such a group would have no infinite linear images. (This is related to the well known problem of the existence of a hyperbolic group which is not residually finite.)

Overview of the structure of this paper. In Section 2 we recall some background on fixed point properties of groups, and how they are classically proved. The natural approach to finding a fixed point from a bounded orbit by considering the average (or center of mass) of the orbit requires appropriate definitions in general uniformly convex metric spaces; this is discussed in Section 3. But, in our situation orbits are not known to be bounded, so the strategy is to average over certain bounded subsets of an orbit. The hope is that by iterating this averaging procedure we will converge to a fixed point. It turns out that this approach works in the presence of sufficiently good Poincaré inequalities; this is explained in Section 7, a key technical tool being Theorem 3.10 (before reading Section 7, readers should acquaint themselves with the notations and definitions of Section 6, which recalls Gromov’s construction of random groups). We prove the desired Poincaré inequalities (in appropriate metric spaces) via a variety of techniques from the theory of metric embeddings; Section 4 and Section 5 are devoted to this topic.

Asymptotic notation. We use A ≲ B, B ≳ A to denote the estimate A ⩽ CB for some absolute constant C; if we need C to depend on parameters, we indicate this by subscripts, thus A ≲_{p} B means that A ⩽ C_{p}B for some C_{p} depending only on p. We shall also use the notation A ≍ B for A ≲ B ∧ B ≲ A.

2. Background on fixed point properties of groups

We start by setting some terminology.

Definition 2.1. Let Γ be a finitely generated group, let (Y, d_{Y}) be a metric space, and let ρ: Γ → Isom(Y) be an action by isometries. We say that the action satisfies the condition:

(N), if the image ρ(Γ) is finite;

(F), if the image ρ(Γ) has a common fixed point; (B), if some (equiv. every) Γ-orbit in Y is bounded.

For a class C of metric spaces, we say that Γ has property (NC), (FC) or (BC) if every action ρ: Γ → Isom(Y), where Y ∈ C, satisfies the respective condition.

The Guichardet-Delorme Theorem [16, 10] asserts that if H is Hilbert space then Γ has property (FH) if and only if it has Kazhdan property (T). The reader can take this as the definition of property (T) for the purpose of this paper.

Fixed-point properties can have algebraic implications for the group’s structure. For example, finitely generated linear groups have isomorphic embeddings into linear groups over local fields, and these latter groups act by isometries on non-positively curved spaces with well-understood point stabilizers. For completeness and later reference, we include the following simple lemma.

Lemma 2.2 (Strong non-linearity). Let S be the class of the symmetric spaces and buildings associated to the groups GL_{n}(F), where F is a non-Archimedean local field. Let Γ be a finitely generated group with property (FS). Then any homomorphic image of Γ into a linear group is finite.

Proof. Let Γ be finitely generated group with property (FS). Let K be a field, and let ρ: Γ → GL_{n}(K) be a homomorphism. Without loss of generality we can assume K to be the field generated by the matrix elements of the images of the generators of Γ, and then let A ⊂ K be the set of matrix elements of the images of all elements of Γ. Clearly ρ(Γ) is finite iff A is a finite set, and [8, Lem. 2.1] reduces the finiteness of A to showing that the image of A under any embedding of K in a local field F is relatively compact. Hence, let ι: K → F be such an embedding. This induces a group homomorphism GL_{n}(K) → GL_{n}(F) which we also denote ι. Composing with ρ we obtain a homomorphism ι ∘ ρ: Γ → GL_{n}(F). Now let S be the symmetric space (if F is Archimedean) or Bruhat-Tits building (if F is non-Archimedean) associated to GL_{n}(F). Since GL_{n}(F) is a group of isometries of S, the image of ι ∘ ρ must fall in the stabilizer in GL_{n}(F) of a point of S. Since these stabilizers are compact subgroups of GL_{n}(F) we are done. □

Lemma 2.2 implies, via our results as stated in the introduction, that Gromov’s wild groups are not isomorphic to linear groups. Alternatively, this fact also follows from the result of [15] that asserts that any linear group admits a coarse embedding into Hilbert space, while it was shown in [14] that Gromov’s random group does not admit such an embedding (indeed, this was the original motivation for Gromov’s construction). It also follows from Lemma 2.2 that all linear homomorphic images of Gromov’s random group are finite. In fact, it was later observed in [13] that the random group has no finite images, and hence also no linear images, since finitely generated linear groups are residually finite.

It is clear that the condition (B) is implied by either condition (N) or (F). When Y is complete and p-uniformly convex the converse holds as well (weaker notions of uniform convexity suffice here). We recall the standard proof of this fact below, since it illustrates a “baby version” of the averaging procedure on uniformly convex spaces that will be used extensively in what follows.

Lemma 2.3 (“Bruhat’s Lemma”). Let Y be a uniformly convex geodesic metric space. Then the condition (B) for isometric actions on Y implies condition (F).

Proof. To any bounded set A ⊂ Y associate its radius function r_{A}(y) = sup_{a∈A} d_{Y} (y, a). For any a ∈ A and y_{0}, y_{1} ∈ Y let y_{1/2} be a midpoint of the geodesic segment connecting them. By equation (1.1) we have that d_{Y} (a, y_{1/2})^{p} is less than the average of d_{Y} (a, y_{0})^{p} and d_{Y} (a, y_{0})^{p} by a positive quantity depending only on d_{Y} (y_{0}, y_{1}) and growing with it. It follows that the diameter of the set C_{ε} ⊂ Y on which r_{A} exceeds its minimum by no more than ε goes to zero with ε. Since Y is complete it follows that r_{A}(y) has a unique global minimizer, denoted c_{∞}(A) ∈ Y, and called the circumcenter of A. Since its definition involved only the metric on Y, the circumcenter map is equivariant under isometries of Y. It follows that the circumcenter of a bounded orbit for a group action is a fixed point. □

3. Averaging on metric spaces

We saw above how to find a fixed point from a bounded orbit, by forming a kind of “average” (circumcenter) along the orbit. When the orbits are not known to be bounded, it is not possible to form such averages. However, if Γ (generated by S = S^{−1}) acts on a p-uniformly convex space Y, it is possible to average over small pieces of the orbit: passing from a point y to an appropriately defined average of the finite set {sy}_{s∈S} (the precise notion of averaging is described below). Under suitable conditions this averaging procedure is a contraction on Y, leading to a fixed point. In practice we will need to average over small balls rather than just S itself, but the idea remains the same.

“Averaging” means specifying a function that associates to Borel probability measures σ on Y a point c(σ) ∈ Y, in a well-behaved manner. We will not axiomatize the needed properties, instead defining the procedures we will use. We start with a particularly simple example. In what follows all measures are assumed to have finite support—this suffices for our purposes, and the obvious generalizations are standard.

Example 3.1. Let Y be a Banach space, and let σ be a (finitely supported) probability measure on Y. The vector-valued integral

c_{lin}(σ) = ∫_{Y} ydσ(y)

is called the linear center of mass of σ.

This center of mass behaves well under linear maps, but its metric properties are not so clear. Thus even for the purpose of proving fixed-point properties for actions on L_{p} we use a nonlinear averaging method, related to a metric definition of linear averaging on Hilbert space. This is a standard method in metric geometry (see for example [21, Chapter 3]).

For a metric space (Y, d_{Y}) we write M(Y) for the space of probability measures on Y with finite support. Generally it is enough to assume below that the measures have finite pth moment for the appropriate p ⩾ 2 but we will not use such measures since our groups are finitely generated.

3.1. Uniformly convex metric spaces and the geometric center of mass. We continue with our complete metric space (Y, d_{Y}). A geodesic segment in Y is an isometry γ: I → Y where I ⊆ ℝ is a closed interval, and the metric on I is induced from the standard metric on ℝ. If the endpoints a < b of I are mapped to y, z ∈ Y respectively, we will say that the segment γ connects y to z, and usually denote it by [y, z]. Moreover, for any t ∈ [0, 1] we will use [y, z]_{t} to denote γ((1 − t)a + tb). This notation obscures the fact that there may be distinct geodesic segments connecting y to z, but this will not be the case for the spaces we consider (see below).

We now assume that Y is a geodesic metric space, i.e., that every two points of Y are connected by a geodesic segment.

Definition 3.2. Let 2 ⩽ p < ∞. Y is said to be p-uniformly convex if there exists a constant c_{Y} > 0 such that for every x, y, z ∈ Y, every geodesic segment [y, z] ⊆ Y, and every t ∈ [0, 1] we have:

d_{Y} (x, [y, z]_{t})^{p} ⩽ (1 − t)d_{Y} (x, y)^{p} + td_{Y} (x, z)^{p} − c_{Y}^{p} t(1 − t)d_{Y} (y, z)^{p}.  (3.1)

We say that Y is uniformly convex if it is p-uniformly convex for some p ⩾ 2.

The above definition is an obvious extension of the notion of p-uniform convexity of Banach spaces (see, e.g., [11, 5]). For concreteness, an L_{p}(μ) space is p uniformly convex if p ∈ [2, ∞) and 2-uniformly convex if p ∈ (1, 2]. In Hilbert space specifically, (3.1) with p = 2 and c_{Y} = 1 is an equality, and it follows that the same holds for conclusions such (3.3) below. We also note that it is easy to see that a uniformly convex metric space is uniquely geodesic by examining midpoints.

We now recall the notion of CAT(0) spaces. For y_{1}, y_{2}, y_{3} ∈ Y, choose Y_{1}, Y_{2}, Y_{3} ∈ ℝ^{2} such that ∥Y_{i} − Y_{j}∥_{2} = d_{Y} (y_{i}, y_{j}) for any i, j. Such a triplet of reference points always exists, and is unique up to a global isometry of ℝ^{2}. It determines a triangle Δ = I_{12} ∪I_{23} ∪I_{13} consisting of three segments of lengths d_{Y} (y_{i}, y_{j}). Any choice of three geodesic segments γ_{ij}: I_{ij} → Y connecting y_{i}, y_{j} gives a reference map R: Δ → Y. We say that (Y, d_{Y}) is a CAT(0) space if for every three points y_{i} ∈ Y every associated reference map R does not increase distances. It is a standard fact (see [9]) that (Y, d_{Y}) is a CAT(0) space iff it is 2-uniformly convex with the constant c_{Y} in (3.1) equal to 1. CAT(0) spaces are p-uniformly convex for all p ∈ [2, ∞) since the plane ℝ^{2} is p-uniformly convex (it is isometric to a subset of L_{p}).

Assume that (Y, d_{Y}) is p-uniformly convex. Let σ ∈ M(Y). Integrating equation (3.1) we see that for all y, z ∈ Y:

c_{Y}^{p} t(1 − t)d_{Y} (y, z)^{p} ⩽ (1 − t)d_{p}(σ, y)^{p} + td_{p}(σ, z)^{p} − d_{p}(σ, [y, z]_{t})^{p},  (3.2)

where for w ∈ Y we write

d_{p}(σ, w) = (∫_{Y} d_{Y} (u, w)^{p}dσ(u))^{1/p} .

Now let d = inf_{y∈Y} d_{p}(σ, y), and assume d_{p}(σ, y), d_{p}(σ, z) ⩽ (d^{p} +ε)^{1/p}. Letting w ∈ Y denote the midpoint of any geodesic segment connecting y and z we have d_{p}(σ, w) ⩾ d and hence:

\frac{c_{Y}^{p}}{4} d_{Y} (y, z)^{p} ⩽ d^{p} + ε − d^{p} = ε.

In other words, the set of y ∈ Y such that d_{p}(σ, y)^{p} is at most d^{p} + ε has diameter ≲_{c_{Y}} ε^{1/p}. By the completeness of Y, there exists a unique point c_{p}(σ) ∈ Y such that d_{p}(σ, c_{p}(σ)) = d.

To justify the notation c_{∞}(A) introduced in Lemma 2.3 notes that d_{∞}(σ, y) = r_{A}(y) where A is the essential support of σ.

Definition 3.3. The point c_{p}(σ) is called the geometric center of mass of σ. We will also use the term p-center of mass when we wish to emphasize the choice of exponent. The point c_{∞}(A) is called the circumcenter of A.

Remark 3.4. Consider the special case of the real line with the standard metric, and of σ = tδ_{1} + (1 − t)δ_{0}. Then c_{p}(σ) represents a weighted average of 0, 1 ∈ ℝ. We note that (except for special values of t), the c_{p}(σ) vary depending on p.

We now apply equation (3.2) where z = c_{p}(σ). Still using d_{p}(σ, [y, z]_{t}) ⩾ d we get:

c_{Y}^{p} t(1 − t)d_{Y} (c_{p}(σ), y)^{p} ⩽ (1 − t)(d_{p}(σ, y)^{p} − d^{p}).

Dividing by 1 − t and letting t → 1 we get the following useful inequality:

d_{p}(σ, y)^{p} ⩾ d_{p}(σ, c_{p}(σ))^{p} + c_{Y}^{p} d_{Y} (c_{p}(σ), y)^{p}.  (3.3)

3.2. Random walks. Let X be a discrete set. Following Gromov [14] we shall use the following terminology.

Definition 3.5. By a random walk (or a Markov chain) on X we shall mean a function μ: X → M(X). The space of random walks will be denoted W(X).

For a random walk μ and x ∈ X we will denote below the measure μ(x) by either μ_{x} or μ(x → ·). The latter notation emphasizes the view of μ as specifying the transition probabilities of a Markov chain on X. For ν ∈ M(X), μ, μ′ ∈ W(X) we write

ν ∗ μ =^{def} ∫_{X} dν(x)μ_{x} ∈ M(X).

The map x ↦ (μ′∗μ)_{x} =^{def} μ′_{x}∗μ defines a random walk on X. For n ∈ ℕ we define inductively

μ^{n+1} =^{def} μ^{n} ∗ μ.

Let ν be a measure on X. We say that a random walk μ ∈ W(X) is ν-reversible, if we have

dν(x)dμ(x → x′) = dν(x′)dμ(x′ → x),  (3.4)

as an equality of measures on X × X. If X is finite, we can assume that ν is a probability measure. In general integrating equation (3.4) w.r.t. x′, we see that ν is a stationary measure for μ, in the sense that ν ∗ μ = ν.

Finally, let the discrete group Γ act freely on X. The induced action of Γ on M(X) preserves M(X) in this case. The space of Γ-equivariant random walks will be denoted W^{Γ}(X). Moreover, we have a quotient space Γ\X. Fixing a probability measure ν̄ on Γ\X, we will call μ ∈ W^{Γ}(X) ν̄-reversible if it is ν-reversible where ν is the pull-back of ν̄ defined by ∫_{X} fdν = ∫_{Γ\X} (∑_{γ∈Γ} f(γx)) dν̄(x) for any f ∈ C_{c}(X).

3.3. Averaging of equivariant functions into uniformly convex spaces. Continuing with the notation used so far, let μ ∈ W^{Γ}(X) be reversible w.r.t. the probability measure ν̄ on Γ\X. Let (Y, d_{Y}) be a p-uniformly convex metric space on which Γ acts by isometries.

Now let f: X → Y be Γ-equivariant. For x ∈ X, the push-forward f_{∗}μ_{x} is a probability measure on Y with finite support (the image of the support of μ_{x} under f). We set:

|∇_{μ}(f)|_{p} (x) = (∫_{X} dμ(x → x′)d_{Y} (f(x), f(x′)^{p}))^{1/p} ,  (3.5)

E_{μ}^{(p)}(f) = \frac{1}{2} ∫_{Γ\X} (|∇_{μ}(f)|_{p} (x))^{p} dν̄(x),  (3.6)
B(X, Y) = {f ∈ C(X, Y)^{Γ} | E_{μ}^{(p)}(f) < ∞} .  (3.7)

For f, g ∈ C(X, Y)^{Γ}, the function x ↦ d_{Y} (f(x), g(x)) is Γ-invariant, and we can hence set

d_{p}(f, g) =^{def} (∫_{Γ\X} d_{Y} (f(x), g(x))^{p}dν̄(x))^{1/p} .

This defines a (possibly infinite) complete metric. The triangle inequality gives:

Lemma 3.6. We have, (1) Let f, g ∈ C(X, Y)^{Γ}. Assume d_{p}(f, g) < ∞. Then f ∈ B(X, Y) iff g ∈ B(X, Y).

(2) Let f ∈ B(X, Y). Then E_{μ^{n}}^{(p)}(f) < ∞ for all n ⩾ 1.

Proof. For all x, x′ ∈ X,

d_{Y} (g(x), g(x′)) ⩽ d_{Y} (g(x), f(x)) + d_{Y} (f(x), f(x′)) + d_{Y} (f(x′), g(x′))

and hence

3^{1−p}d_{Y} (g(x), g(x′))^{p} ⩽ d_{Y} (g(x), f(x))^{p} + d_{Y} (f(x), f(x′))^{p} + d_{Y} (f(x′), g(x′))^{p}.  (3.8)

Integrating dμ(x → x′) gives Γ-invariant functions of x which may be integrated dν̄(x). Using the stationarity of dν̄ we then have:

E_{μ}^{(p)}(g) ⩽ 3^{p−1}E_{μ}^{(p)}(f) + 3^{p−1}d_{p}(f, g)^{p}.

Similarly, integrating

n^{1−p}d_{Y} (f(x_{0}), f(x_{n}))^{p} ⩽ ∑_{i=0}^{n−1} d_{Y} (f(x_{i}), f(x_{i+1}))^{p}

against dν̄(x_{0}) ∏_{i=0}^{n−1} dμ(x_{i} → x_{i+1}) gives E_{μ^{n}}^{(p)}(f) ⩽ n^{p−1}E_{μ}^{(p)}(f). □

Continuing the analysis of the map x ↦ f_{∗}μ_{x}, we note that this is a Γ-equivariant map X → M(Y). Since Γ acts by isometries, the map

(A_{μ}^{(p)}f) (x) =^{def} c_{p}(f_{∗}μ_{x})

is also Γ-equivariant; this will be our averaging procedure. If Y is a Hilbert space and p = 2, A_{μ}^{(p)} is the usual linear average with respect to μ. In particular, A_{μ_{1}}^{(2)}A_{μ_{2}}^{(2)} = A_{μ_{1}∗μ_{2}}^{(2)}. This does not hold in general (for spaces other than Hilbert space, or even in Hilbert space for p > 2). In particular, we will later use A_{μ^{n}}^{(p)} for large n and not just (A_{μ}^{(p)})^{n}.

We first verify that the averaging procedure remains in the space B(X, Y).

Lemma 3.7. For f ∈ B(X, Y) we have

d_{p}(f, A_{μ}^{(p)}f) ≲_{c_{Y}} (E_{μ}^{(p)}(f))^{1/p} ,
E_{μ}^{(p)}(A_{μ}^{(p)}f) ≲_{p,c_{Y}} E_{μ}^{(p)}(f).

Proof. At every x ∈ X the fundamental estimate (3.3) gives:

c_{Y}^{p} d_{p} (f(x), A_{μ}^{(p)}f(x))^{p} ⩽ d_{p}(f(x), f_{∗}(μ_{x})^{p} = ∫ d_{Y} (f(x), f(x′))^{p}dμ(x → x′).

Now both sides are Γ-invariant functions of x ∈ X and the first claim follows by integrating against dν̄. For the second claim apply inequality (3.8) from the proof of Lemma 3.6 with g = A_{μ}^{(p)}(f). □

We measure the contractivity of A_{μ}^{(p)} with respect to the energy E_{μ}^{(p)}. It is not hard to verify that contraction will imply the existence of fixed points:

Proposition 3.8. Assume that there exist n ⩾ 1 and c < 1 such that for all f ∈ B(X, Y) we have E_{μ}^{(p)}(A_{μ^{n}}^{(p)}f) ⩽ cE_{μ}^{(p)}(f). Suppose that the graph on X given by connecting x, x′ if μ(x → x′) > 0 is connected. Then, as long as B(X, Y) is non-empty (this is the case, for example, when Γ\X is finite), it contains constant maps. In particular, Γ fixes a point in Y.

Proof. Choose an arbitrary f_{0} ∈ B(X, Y) and let f_{k+1} = A_{μ^{n}}^{(p)}f_{k}. By assumption we have E_{μ}^{(p)}(f_{k}) ⩽ c^{k}E_{μ}^{(p)}(f_{0}). By Lemma 3.6 E_{μ^{n}}^{(p)}(f_{k}) ⩽ n^{p−1}c^{k}E_{μ}^{(p)}(f_{0}), and by Lemma 3.7 this means that

d_{p}(f_{k+1}, f_{k})^{p} ≲_{p,c_{Y} ,n} c^{k}E_{μ}^{(p)}(f_{0}).

It now follows that f_{k} are a Cauchy sequence and hence converge to a function f ∈ B(X, Y). We have E_{μ}^{(p)}(f) = 0 so f(x) = f(x′) whenever μ(x → x′) > 0. By the connectivity assumption this means f is constant on X and its value is the desired fixed point. □

We now address the problem of showing that averaging reduces the energy. We prove two technical inequalities:

Proposition 3.9. (generalization of [37, B.25]) We have,

E_{μ}^{(p)} (A_{μ^{n}}^{(p)}f) ≲_{p,c_{Y}} ∫_{Γ\X} dν̄(x) ∫_{X} [dμ^{n+1}(x → x′) − dμ^{n}(x → x′)] d_{Y} (A_{μ^{n}}^{(p)}f(x), f(x′))^{p} .

∫_{Γ\X} dν̄(x) ∫_{X} dμ^{n}(x → x′)d_{Y} (A_{μ^{n}}^{(p)}f(x), f(x′))^{p} ≲_{p,c_{Y}} E_{μ^{n}}^{(p)}(f).  (3.9)

Proof. Recall that A_{μ^{n}}^{(p)}f(x) = c_{p}(f_{∗}μ^{n}(x → ·)). The fundamental estimate (3.3) then reads:

c_{Y}^{p} d_{Y} (y, A_{μ^{n}}^{(p)}f(x))^{p}

⩽ ∫_{X} d_{Y} (y, f(x′))^{p}dμ^{n}(x → x′) − ∫_{X} d_{Y} (A_{μ^{n}}^{(p)}f(x), f(x′))^{p} dμ^{n}(x → x′). (3.10)

Setting y = A_{μ^{n}}^{(p)}f(x′′) integrate (3.10) dμ(x′′ → x). The resulting function of x′′ is Γ-invariant and we integrate it dν̄(x′′) to get (also using the reversibility),

2c_{Y}^{p} E_{μ}^{(p)}(A_{μ^{n}}^{(p)}f) ⩽ ∫_{Γ\X} dν̄(x′′) ∫_{X} dμ^{n+1}(x′′ → x′)d_{Y} (A_{μ^{n}}^{(p)}f(x′′), f(x′))^{p}

− ∫_{Γ\X} dν̄(x) ∫_{X} dμ^{n}(x → x′′)d_{Y} (A_{μ^{n}}^{(p)}f(x′′), f(x))^{p}.

Inequality (3.9) follows directly from the triangle inequality and Lemma 3.7. □

Theorem 3.10. Let Γ be a group generated by the symmetric set S of size 2d, acting by isometries on the p-uniformly convex space Y, let X = Cay(Γ; S) (the Cayley graph of Γ), and let f ∈ B(X, Y). Let μ be the jth convolution power of the standard random walk on X for an even j. Then

E_{μ}^{(p)} (A_{μ^{n}}^{(p)}f) ≲_{p,c_{Y} ,d,j} \sqrt{\frac{log n}{n}} · E_{μ^{n}}^{(p)}(f) + \frac{1}{n} · E_{μ}^{(p)}(f).

Proof. Pulling back f to a function on the free group on S (acting on Y via the quotient map) we may assume that Γ is the free group and X the 2d-regular tree. Now, [37, Prop. 2.9] implies that μ^{n+1}(x → x′) − μ^{n}(x → x′) is typically small: given x, except for a set of

x′ of (μ^{n+1} + μ^{n})(x → ·)-mass ≲_{d} n^{−θ}, the difference is ≲_{d,j,θ} \sqrt{\frac{log n}{n}}μ^{n}(x → x′), where θ > 0 is arbitrary.

Applying this in Proposition 3.9 we find that:

E_{μ}^{(p)}(A_{μ^{n}}^{(p)}f) ≲_{p,c_{Y} ,d,j,θ} \sqrt{\frac{log n}{n}} · E_{μ^{n}}^{(p)}(f) + n^{−θ} max_{\begin{matrix}d_{X}(x,x′′)⩽j(n+1) \\ 2|d_{X}(x,x′′) \end{matrix}} d_{Y} (A_{μ^{n}}^{(p)}f(x), f(x′′))^{p}.

Now

d_{Y} (A_{μ^{n}}^{(p)}f(x), f(x′′)^{p}) ≲_{p,c_{Y}} max_{\begin{matrix}d_{X}(x,x′)⩽jn \\ 2|d_{X}(x,x′) \end{matrix}} d_{Y} (f(x′), f(x′′))^{p},

and by the triangle inequality

d_{Y} (f(x′), f(x′′))^{p} ⩽ (2n + 1)^{p−1} max_{\begin{matrix}d_{X}(x,x′)⩽j \\ 2|d_{X}(x,x′) \end{matrix}} d_{Y} (f(x), f(x′))^{p}.

Finally, the latter quantity is at most ≲_{j,d} E_{μ}^{(p)}(f) (one needs that μ^{j}(x → ·) is supported on all points x′ at even distance from x at most j). Putting it all together we have:

E_{μ}^{(p)}(A_{μ^{n}}^{(p)}f) ≲_{p,c_{Y} ,d,j,θ} \sqrt{\frac{log n}{n}} · E_{μ^{n}}^{(p)}(f) + n^{p−1−θ}E_{μ}^{(p)}(f),

as required. □

It is now clear that (assuming we can arrange n to be large) what is needed is that E_{μ^{n}}^{(p)}(f) is not too large compared to E_{μ}^{(p)}(f). This is what we establish in the next two sections.

4. Poincaré inequalities on metric spaces

It turns out that it is hard to show directly that averaging with respect to the generators of the random group reduces the energy (compare [19]). Instead, it is preferable to average with respect to some power of the generators, as in Theorem 3.10, where we gain by making n large. This requires controlling E_{μ^{n}}^{(p)}(f) in terms of E_{μ}^{(p)}(f). Such a control takes the form of inequalities involving distances alone rather than centers-of-mass, so that methods from metric embedding theory can be used to prove them. In this section we state the inequalities the we need, and show that they hold for functions from expander graphs to certain target metric spaces (L_{p} spaces and CAT(0) manifolds). In Section 5 we use metric embeddings to establish these inequalities for additional classes of metric spaces. In section 7 we then show that a strong enough Poincaré inequality for a particular target is enough to control averaging so that the random group has the fixed-point property on that target.

We fix a group Γ, a discrete Γ-space X, a Γ-equivariant random walk μ ∈ W(X), reversible with respect to the Γ-invariant measure ν which gives finite measure to any fundamental domain for Γ\X.

Definition 4.1. Let Y be a metric space, and p ⩾ 1. Let n > m ⩾ 1 be integers. We say that a Poincaré inequality of exponent p holds if there exists c > 0 such that for any f ∈ B(X, Y),

E_{μ^{n}}^{(p)}(f) ⩽ c^{p}E_{μ^{m}}^{(p)}(f).  (4.1)

If ν itself is a probability measure, we also say that a Poincaré inequalty holds if exists c̄ > 0 such that for any f,

∫_{X×X} dν(x)dν(x′)d_{Y} (f(x), f(x′))^{p} ⩽ c̄^{p}E_{μ^{m}}^{(p)}(f).  (4.2)

Inequality (4.2), when Y is a Hilbert space and p = 2 is the classical Poincaré inequality. It is sometimes easier to work with than the inequality (4.1) (for example when proving such results as the extrapolation lemma below). It will be inequality (4.1), however, that will be used for obtaining fixed point properties for the random group. Note that inequality (4.2) can be thought of as the limit as n → ∞ of (4.1).

Lemma 4.2. Let ν be a probability measure.

(1) Assume that (4.2) holds with the constant c̄. Then (4.1) holds with c = 2c̄ for all n > m.

(2) Assume that Y is p-uniformly convex, and let V^{(p)}(f) = ∫_{X} dν(x)d_{Y}^{p} (f(x), c_{p}(f_{∗}ν)). Then

V^{(p)}(f) ⩽ ∫_{X×X} dν(x)dν(x′)d_{Y}^{p} (f(x), f(x′)) ⩽ 2^{p−1}V^{(p)}(f).

Proof. For any x, x′, x′′ ∈ X we raise the triangle inequality to the pth power to obtain:

d_{Y} (f(x), f(x′))^{p} ⩽ 2^{p−1}d_{Y} (f(x), f(x′′))^{p} + 2^{p−1}d_{Y} (f(x′), f(x′′))^{p}.

Integrating against dν(x)dμ^{n}(x → x′)dν(x′′) and using the stationarity and reversibility of the Markov chain gives:

E_{μ^{n}}^{(p)}(f) ⩽ 2^{p−1} ∫_{X×X} dν(x)dν(x′)d_{Y} (f(x), f(x′))^{p},

whence the first claim. For the proof of the second claim write y_{0} = c_{p}(f_{∗}ν), and recall that ∫_{X} dν(x)d_{Y} (f(x), y_{0})^{p} ⩽ ∫_{X} dν(x)d_{Y} (f(x), y)^{p} holds for all y ∈ Y by definition of c_{p}. Setting y = f(x′) and averaging w.r.t. x′ gives half of the inequality. For the other half use d_{Y} (f(x), f(x′)) ⩽ d_{Y} (f(x), y_{0}) + d_{Y} (y_{0}, f(x′)). □

We study metric inequalities for functions on finite Markov chains (typically, the standard random walks on finite graphs). In the following we use the shorthand (V, μ, ν) for the data of a finite set V (“vertices”), and a Markov chain μ ∈ W(V) reversible with respect to a probability measure ν ∈ M(V). Recall that the Markov chain is ergodic if for any u, v ∈ V there is n such that μ^{n}(u → v) > 0. For such a Markov chain the averaging operator A_{μ}^{(}2) acting on L^{2}(ν) is the usual nearest-neighbour averaging operator Af(u) = ∫_{V} f(v)dμ(u → v). It is well-known that this is a self-adjoint operator with spectrum contained in [−1, 1], with 1 a simple eigenvalue (here we use ergodicity). The spectral gap of the chain is then the difference between 1 and the second largest eigenvalue.

Definition 4.3. To the metric space Y we associate its Poincaré modulus of exponent p, p ⩾ 2. Denoted Λ_{Y}^{(p)}(σ), it is the smallest number Λ such that for any finite reversible ergodic Markov chain (V, μ, ν) with spectral gap at least σ and any function f: V → Y we have

∫_{V ×V} dν(u)dν(v)d_{Y} (f(u), f(v))^{p} ⩽ Λ^{p} ∫_{V ×V} dν(u)dμ(u → v)d_{Y} (f(u), f(v))^{p}.  (4.3)

Observe that spectrally expanding both sides of (4.3) shows that for Y Hilbert space, Λ_{Y}^{(2)}(σ) = \frac{1}{\sqrt{σ}}.

We also define the Local Poincaré modulus of exponent p to be

Λ_{Y}^{(p)}(σ, N) = sup {Λ_{Y′}^{(p)}(σ) | Y′ ⊆ Y, |Y′| ⩽ N} .

We say that Y has small Poincaré moduli of exponent p if its local Poincaré moduli of that exponent satisfy

Λ_{Y}^{(p)}(σ, N) ≲_{p,σ} o ((\frac{log N}{log log N} )^{\frac{1}{2p}} ) .  (4.4)

Note that a bound of O(log N) in (4.4) holds true for any metric space, by Bourgain’s embedding theorem [7] and (4.6) below.

We shall proceed to bound the Poincaré modulus for non-Hilbertian spaces, i.e., to show that a Poincaré inequality holds for Markov chains on these spaces, with the constant bounded by a function of the spectral gap of the chain. The first case is that of L_{p}. The proof below is a slight variant of Matoušek’s extrapolation lemma for Poincaré inequalities; see [27], and [6, Lem. 5.5]; we include it since it has been previously stated for graphs rather than general Markov chains.

Lemma 4.4 (Matoušek extrapolation). Let (V, μ, ν) be a reversible Markov chain. Assume the Poincaré inequality (4.2) holds with exponent p ⩾ 1 and Poincaré modulus Ap for functions f: V → ℝ. Then for any q ⩾ p the inequality (4.2) holds for such functions with the exponent q and modulus 4Aq and for any 1 < q ⩽ p the inequality holds with exponent q and modulus Aq.

Proof. For u ∈ V set g(u) = |f(u)|^{\frac{q}{p}} sgn f(u). Shifting f by a constant does not change the claimed inequalities, and using the intermediate value theorem we may assume ∫ gdν = 0. By the convexity of the norm, Hölder’s inequality, and the assumed Poincaré inequality, we have:

∥g∥_{L_{p}(ν)} = ∥g − ∫ gdν∥_{L_{p}(ν)} ⩽ ∫ dν(v) ∥g − g(v)∥_{L_{p}(ν)} ⩽ (∫ dν(v) ∥g − g(v)∥_{L_{p}(ν)}^{p})^{\frac{1}{p}}

= (∫ dν(u)dν(v) |g(u) − g(v)|^{p})^{\frac{1}{p}} ⩽ (Ap) (∫ dν(u)dμ(u → v) |g(u) − g(v)|^{p})^{\frac{1}{p}} .

We next use the elementary inequality

|a^{\frac{q}{p}} ± b^{\frac{q}{p}} | ⩽ \frac{q}{p} |a ± b| (a^{\frac{q}{p} −1} + b^{\frac{q}{p} −1}) ,

to deduce that:

∥g∥_{L_{p}(ν)} ⩽ (Aq) [∫ dν(u)dμ(u → v) |f(u) − f(v)|^{p} (|f(u)|^{\frac{q}{p} −1} + |f(v)|^{\frac{q}{p} −1})^{p}]^{\frac{1}{p}}

⩽ (Aq) [∫ dν(u)dμ(u → v) |f(u) − f(v)|^{q}]^{\frac{1}{q}}

· [∫ dν(u)dμ(u → v) (|f(u)|^{\frac{q}{p} −1} + |f(v)|^{\frac{q}{p} −1})^{\frac{qp}{q−p}} ]^{\frac{q−p}{pq}} ,  (4.5)

where we used Hölder’s inequality.

By the triangle inequality in L_{qp/(q−p)}, symmetry and reversibility, the last term in (4.5) is at most:

2 [∫ dν(u) |f(u)|^{\frac{q−p}{p} · \frac{qp}{q−p}} ]^{\frac{q−p}{pq}} = 2 ∥f∥L_{q}(ν)^{\frac{q−p}{p}} .

Recalling that |g(u)| = |f(u)|^{\frac{q}{p}}, this means

∥f∥L_{q}(ν)^{\frac{q}{p}} ⩽ (2Aq) [∫ dν(u)dμ(u → v) |f(u) − f(v)|^{q}]^{\frac{1}{q}} ∥f∥_{L_{q}(ν)}^{\frac{q}{p} −1} ,

and collecting terms finally gives

∥f∥_{L_{q}(ν)} ⩽ (2Aq) [∫ dν(u)dμ(u → v) |f(u) − f(v)|^{q}]^{\frac{1}{q}} .

To conclude the proof we note that

[∫ dν(u)dν(v) |f(u) − f(v)|^{q}]^{\frac{1}{q}} ⩽ 2 ∥f∥_{L_{q}(ν)}

follows by applying the triangle inequality in L_{q}(ν × ν) to the functions (u, v) ↦ f(u) and (u, v) ↦ −f(u). □

Corollary 4.5. We have Λ_{ℝ}^{(p)}(σ) ⩽ 2p\frac{1}{\sqrt{σ}}. Integrating, this bound also holds for for Λ_{L_{p}}^{(p)}(σ).

Since Hilbert space embeds isometrically into L_{p} for all p ⩾ 1, we see that for p ⩾ 2,

Λ_{L_{2}}^{(p)}(σ) ⩽ Λ_{L_{p}}^{(p)}(σ) ⩽ \frac{2p}{\sqrt{σ}} .  (4.6)

Remark 4.6. In [27] it is shown that any N-point metric space embeds in L_{p} with distortion ≲ 1 + \frac{1}{p} log_{N}. It follows that for any metric space Y and any exponent p ⩾ 2,

Λ_{Y}^{(p)}(σ, N) ≲ \frac{p + log N}{\sqrt{σ}} .

Remark 4.7. The argument above was special for L_{p} spaces. But, using a different method, it was shown in [34] that for any Banach lattice Y that does not contain almost isometric copies of every finite metric space, we have Λ_{Y}^{(2)}(σ) ≲_{Y,σ} 1. While this is not stated explicitly in [34], it follows easily from the proof of Lemma A.4 there; this observation is carried out in detail in [30].

We also note for future reference that the Poincaré modulus behaves well under natural operations on metric spaces. The (trivial) proof is omitted.

Proposition 4.8. Fix a function L(σ, N) and let C be the class of metric spaces Y such that Λ_{Y}^{(p)} ⩽ L. Then C is closed under completion, passing to subspaces, ℓ_{p} products, and ultralimits. The property of being p-uniformly convex with constant c_{Y} is also preserved by the same operations, except that that one must pass to convex (i.e. totally geodesic) subspaces.

In the class of CAT(0) spaces, a further reduction is possible: it is enough to establish the Poincaré inequality for all the tangent cones of the space Y. This is essentially an observation from [38, Pf of Thm. 1.1] (see also [20, Lem. 6.2]). It relies on the equivalent formulation from Lemma 4.2. We recall the definition of the tangent cone to a metric space Y at the point y ∈ Y. Let γ, γ′: : [0, ε] → Y be unit-speed geodesic segments issuing from y. For each t > 0 let θ_{t,t′} be the angle such that

d_{Y} (γ(t), γ′(t′)^{2} = d_{Y} (y, γ(t))^{2} + d_{Y} (y, γ′(t′))^{2} − 2d_{Y} (y, γ(t))d_{Y} (y, γ′(t′)) cos θ_{t,t′}.

The Alexandroff angle between γ, γ′ is defined as θ(γ, γ′) = lim sup_{t,t′→0} θ_{t,t′}. It is easy to check that this provides a pesudometric on the space of germs of geodesic segments issuing from y. Identifying segments at angle zero gives the space of directions S_{y}Y. Now let T_{y}Y be the infinite cone over S_{y}Y with the metric d̃(aγ, bγ′) = \sqrt{a^{2} + b^{2} − 2ab cos θ(γ, γ′)}. There is a natural “inverse of the exponential map” π_{y}: Y → T_{y}Y given by mapping z ∈ Y to d_{Y} (y, z) · [y, z] where [y, z] is the geodesic segment connecting y to z (π_{y}(y) is the cone point). By definition π_{y} preserves distances from y, in that d̃(π_{y}(y), π_{y}(z)) = d_{Y} (y, z). The key properties for us are that when Y is CAT(0), π_{y} is 1-Lipschitz (in fact, this is equivalent to the CAT(0) inequality) and that in that case (T_{y}Y, d̃) is a CAT(0) metric space as well. [9, Thm. II.3.19]. It is also important to note that if σ is a probability measure on Y and y = c_{2}(σ) then c_{2}(π_{y∗}σ) = π_{y}(y) (this is since the fact that y minimizes z ↦ d_{Y} (σ, z) can be stated in terms of distances from y alone; see [20, Prop. 3.5]).

The following proposition was proved in an equivalent form in [38].

Proposition 4.9. Let Y be a CAT(0) space. Then

Λ_{Y}^{(2)}(σ, N) ⩽ 2 sup_{y∈Y} Λ_{T_{y}Y}^{(2)} (σ, N).

In particular, Λ_{Y}^{(2)}(σ) ⩽ 2 sup_{y∈Y} Λ_{T_{y}Y}^{(2)} (σ).

Proof. Let (V, μ, ν) be a finite Markov chain as above. For a CAT(0) space Y let v(Y) be minimal such that for all f: V → Y we have

V^{(2)}(f) ⩽ v(Y)E_{μ^{m}}^{(2)}(f).

Lemma 4.2 shows that the constant c in the Poincaré inequality for functions from V to Y satisfies v(Y) ⩽ c ⩽ 2v(Y). It thus remains to show that v(Y) ⩽ sup_{y∈Y} v(T_{y}Y). Indeed, let f: X → Y, and let y = c_{2}(f_{∗}ν), f̃ = π_{y} ∘ f. As noted above we have c_{2}(f̃_{∗}ν) = π_{y}(y), and since distances from y are preserved that V^{(2)}(f) = V^{2}(f̃). Since π_{y} is non-expansive, E_{μ^{m}}^{(2)}(f̃) ⩽ E_{μ^{m}}^{(2)}(f). It follows that V^{(2)}(f) ⩽ v(T_{c_{2}(f_{∗}ν)})E_{μ^{m}}^{(p)}(f) and we are done. □

Note that when Y is a Riemannian manifold, the tangent cone constructed above is isometric to the ordinary tangent space at y, equipped with the inner product given by the Riemannian metric at that point. in other words, the tangent cones of a manifold are all isometric to Hilbert spaces. An approximation argument also shows that Λ_{Y}^{(2)}(σ) ⩾ Λ_{T_{y}Y}^{(2)} (σ) for all y ∈ Y.

Corollary 4.10. Let Y be a Hilbert manifold with a CAT(0) Riemannian metric (for example, a finite-dimensional simply connected Riemannian manifold of non-positive sectional curvature). Then \frac{1}{\sqrt{σ}} ⩽ Λ_{Y}^{(2)}(σ) ⩽ \frac{2}{\sqrt{σ}}.

5. Padded decomposability and Nagata dimension

We start by recalling some definitions and results from [26]. Let (X, d_{X}) be a metric space. Given a partition 𝒫 of X and x ∈ X we denote by 𝒫(x) the unique element of 𝒫 containing x. For Δ > 0, a distribution Pr over partitions of X is called a Δ-bounded stochastic decomposition if

Pr [∀ C ∈ 𝒫, diam(C) ⩽ Δ] = 1,

i.e., almost surely with respect to Pr partitions of X contain only subsets whose diameter is bounded by Δ. Given ε, δ > 0 we shall say that a Δ-bounded stochastic decomposition Pr is (ε, δ)-padded if for every x ∈ X,

Pr [𝒫(x) ⊇ B_{X}(x, εΔ)] ⩾ δ.

Here, and in what follows, B_{X}(x, r) =^{def} {y ∈ X : d_{X}(x, y) ⩽ r} denotes the closed unit ball of radius r centered at x.

Given two metric spaces (Y, d_{Y}) and (Z, d_{Z}), and X ⊆ Y, we denote by e(X, Y, Z) the infimum over all constant K such that every Lipschitz function f : X → Z can be extended to a function f̃: Y → Z such that ∥f̃∥_{Lip} ⩽ K · ∥f∥_{Lip}. The absolute Lipschitz extendability constant of (X, d_{X}), denoted ae(X), is defined as

ae(X) =^{def} sup {e(X, Y, Z) : Y ⊇ X, Z a Banach space} .

In words, the inequality ae(X) < K implies that any Banach space valued Lipschitz mapping on X can be extended to any metric space containing X such that the Lipschitz constant of the extension grows by at most a factor of K. This notion was introduced in [26], where several classes of spaces were shown to be absolutely extendable. We note that in the extension theorems we quote below from [26] the role of the target space being a Banach space is very weak, and it can also be, for example, any CAT(0) space; we refer to [26] for a discussion of this issue.

The following theorem was proved in [26].

Theorem 5.1 (Absolute extendability criterion [26]). Fix ε, δ ∈ (0, 1) and assume that (X, d_{X}) admits a 2^{k}-bounded (ε, δ)-padded stochastic decomposition for every k ∈ ℤ. Then

ae(X) ≲ \frac{1}{εδ} .

In [26] several classes of spaces were shown to satisfy the conditions of Theorem 5.1, including subsets of Riemannian surfaces of bounded genus and doubling metric spaces. For our applications we need to enrich the repertoire of these spaces. We do so by relating the notion of padded decomposability to having finite Nagata dimension, and using results from [24] which bound the Nagata dimension of various classes of spaces (which will be listed shortly).

Let (X, d_{X}) be a metric space. Following [28, 24], given γ ⩾ 1 and d ∈ ℕ we say that X has Nagata dimension at most d with constant γ if for every s > 0 there exists a family of subsets 𝒞 ⊆ 2^{X} ∖ {∅} with the following properties.

(1) 𝒞 covers X, i.e. ⋃_{C∈𝒞} C = X.

(2) For every C ∈ 𝒞, diam(C) ⩽ γs.

(3) For every A ⊆ X with diam(A) ⩽ s, we have |{C ∈ 𝒞 : C ∩ A ≠ ∅}| ⩽ d + 1. The infimum over all γ for which X has Nagata dimension at most d with constant γ will be denoted γ_{d}(X). If no such γ exists we set γ_{d}(X) = ∞. Finally, the Nagata dimension of X is defined as

dim_{N}(X) = inf {d ⩾ 0 : γ_{d}(X) < ∞} .

It was proved in [24] that X has finite Nagata dimension if and only if X embeds quasisymmetrically into a product of finitely many trees.

Lemma 5.1 (Bounded Nagata dimension implies padded decomposability). Let (X, d_{X}) be a metric space, γ ⩾ 1 and d ∈ ℕ. Assume that γ_{d}(X) < γ < ∞. Then for every k ∈ ℤ, X admits a 2^{k}-bounded (\frac{1}{100γd^{2}} , \frac{1}{d+1})-padded stochastic decomposition.

Proof. It is easy to iterate the definition of Nagata dimension to prove the following fact, which is (part of) Proposition 4.1 in [24] (with explicit, albeit sub-optimal, estimates, that can be easily obtained from an examination of the proof in [24]). Let r = 50γ · d^{2}. For every j ∈ ℤ there exists a family of subsets ℬ ⊆ 2^{X} ∖ {∅} with the following properties.

(1) For every x ∈ X there exists B ∈ ℬ such that B_{X} (x, r^{j}) ⊆ B.

(2) ℬ = ⋃_{i=0}^{d} ℬ_{i}, where for every i ∈ {0, …, d} the sets in ℬ_{i} are disjoint, and for every B ∈ ℬ_{i}, diam(B) ⩽ r^{j+1}.

We now construct a random partition P of X as follows. Let π be a permutation of {0, …, d} chosen uniformly at random from all such (d + 1)! permutations. Define a family of subsets ℬ̃_{i}^{π} ⊆ 2^{X} ∖ {∅} inductively as follows: ℬ̃_{0}^{π} = ℬ_{π(0)}, and for 0 ⩽ i < d,

ℬ̃_{i+1}^{π} = {B ∖ ⋃ ; C∈⋃_{ℓ=0}^{i} ℬ̃_{π(ℓ)}^{π} C : B ∈ ℬ_{π(i+1)}} ∖ {∅}.

Finally we set 𝒫^{π} = ⋃_{i=0}^{d} ℬ̃_{i}^{π} . Since ℬ covers X, 𝒫^{π} is a partition of X. Moreover, by construction, for every C ∈ 𝒫^{π}, diam(C) ⩽ r^{j+1}.

Fix x ∈ X. By the first condition above there exists i ∈ {0, …, d} and B ∈ ℬ_{i} such that B_{X} (x, r^{j}) ⊆ B. If π(0) = i then 𝒫^{π}(x) = B ⊇ B(x, r^{j}). This happens with probability \frac{1}{d+1}.

Letting k be the largest integer j such that r^{j+1} ⩽ 2^{k} we see that 𝒫^{π} is a 2^{k}-bounded stochastic partition such that for every x ∈ X

Pr [𝒫^{π}(x) ⊇ B (x, \frac{2^{k−1}}{r} )] ⩾ \frac{1}{d + 1},

as required. □

The following corollary shows that many of the Lipschitz extension theorems proved in [24] are direct conequences of the earlier results of [26]. The cubic dependence on the Nagata dimension is an over-estimate, and can be easily improved. We believe that the true bound should depend linearly on the dimension, but this is irrelevant for the purposes of the present paper.

Corollary 5.2. For every metric space X and d ∈ ℕ,

ae(X) = O (γ_{d}(X)d^{3}) .

Thus, doubling metric spaces, subsets of compact Riemannian surfaces, Gromov hyperbolic spaces of bounded local geometry, Euclidean buildings, symmetric spaces, and homogeneous Hadamard manifolds, all have finite absolute extendability constant.

The list of spaces presented in Corollary 5.2 is a combination of the results of [26] and [24]. In particular the last four classes listed in Corollary 5.2 were shown in [24] to have finite Nagata dimension. It should be remarked here that Lipschitz extension theorems for Gromov hyperbolic spaces of bounded local geometry were previously proved in [29] via different methods.

We will use the following embedding theorem, which follows from the proof of Theorem 5.1 in [25], though it isn’t explicitly stated there in full generality. We include the simple proof for the sake of completeness.

Theorem 5.2 (Snowflake embedding). Fix ε, δ, θ ∈ (0, 1). Let (X, d_{X}) be a metric space which admits for every k ∈ ℤ a 2^{k}-bounded (ε, δ)-padded stochastic decomposition. Then the metric space (X, d_{X}^{θ}) embeds into Hilbert space with bi-Lipschitz distortion ≲ \frac{1}{ε\sqrt{δθ(1−θ)}}.

Proof. For every k ∈ ℤ let Pr_{k} be an (ε, δ)-padded distribution over 2^{k}-bounded partitions of X. We also let {σ_{C}}_{C⊆X} be i.i.d. symmetric ±1 Bernoulli random variables, which are independent of Pr_{k}. Denote by Ω_{k} the measure space on which all of these distributions are defined. Let f_{k} : X → L_{2}(Ω_{k}) be given by the random variable

f_{k}(x) = σ_{𝒫(x)} · min {d_{X} (x, X ∖ 𝒫(x)) , 2^{k}} (𝒫 is a partition of X ).

Finally, define F : X → (⨁_{k∈ℤ} L_{2}(Ω_{k})) ⊗ ℓ_{2} by

F (x) = ∑_{k∈Z} 2^{−k(1−θ)}f_{k}(x) ⊗ e_{k}.

Fix x, y ∈ X and let k ∈ ℤ be such that 2^{k} < d_{X}(x, y) ⩽ 2^{k+1}. It follows that for every 2^{k}- bounded partition 𝒫 of X, 𝒫(x) ≠ 𝒫(y). Thus σ_{𝒫(x)} and σ_{𝒫(y)} are independent random variables, so that

∥F (x) − F (y)∥_{2}^{2} ⩾ 2^{−2k(1−θ)} ∥f_{k}(x) − f_{k}(y)∥_{L_{2}(Ω_{k})}^{2}

= \frac{𝔼_{σ}𝔼_{Pr_{k}} [σ_{𝒫(x)} · min \{d_{X} (x, X ∖ 𝒫(x)) , 2^{k}\} − σ_{𝒫(y)} · min \{d_{X} (y, X ∖ 𝒫(y)) , 2^{k}\}]^{2}}{2^{2k(1−θ)}}
=^{(♣)} \frac{𝔼_{Pr_{k}} [min \{d_{X} (x, X ∖ 𝒫(x)) ^{2} , 2^{2k}\}] + 𝔼_{Pr_{k}} [min \{d_{X} (y, X ∖ 𝒫(y)) ^{2} , 2^{2k}\}]}{2^{2k(1−θ)}}
⩾^{(♠)} \frac{δ (ε2^{k})^{2}}{2^{2k(1−θ)}} ⩾ \frac{ε^{2}δ}{2^{2θ}} · d_{X}(x, y)^{2θ},  (5.1)

where in (♣) we used the independence of σ_{𝒫(x)} and σ_{𝒫(y)} , and in (♠) we used the (ε, δ)- padded property.

In the reverse direction, for every j ∈ ℤ, if 𝒫 is a 2^{j}-bounded partition of X then it is straightforward to check that for all x, y ∈ X we have the point-wise inequality,

|σ_{𝒫(x)} · min {d_{X} (x, X ∖ 𝒫(x)) , 2^{j}} − σ_{𝒫(y)} · min {d_{X} (y, X ∖ 𝒫(y)) , 2^{j}}|

⩽ 2 min {d_{X}(x, y), 2^{j}} . (5.2)

Indeed, if d_{X}(x, y) ⩾ 2^{j} then (5.2) is trivial. If 𝒫(x) = 𝒫(y) then (5.2) follows from the Lipschitz condition |d_{X} (x, X ∖ 𝒫(x)) − d_{X} (y, X ∖ 𝒫(x)) | ⩽ d_{X}(x, y). Finally, if d_{X}(x, y) < 2^{j} and 𝒫(x) ≠ 𝒫(y) then d_{X} (x, X ∖ 𝒫(x)) , d_{X} (y, X ∖ 𝒫(y)) ⩽ d_{X}(x, y) < 2^{j}, implying (5.2) in this case as well.

It follows from (5.2) that

∥F (x) − F (y)∥_{2}^{2} ≲ ∑_{j∈ℤ} \frac{min \{d_{X}(x, y)^{2}, 4^{j}\}}{4^{j(1−θ)}} ≲ ∑_{j⩽k} 4^{jθ} + d_{X}(x, y)^{2} ∑_{j⩾k+1} 4^{−j(1−θ)}

≲ \frac{4^{kθ}}{θ} + d_{X}(x, y)^{2} · \frac{4^{−k(1−θ)}}{1 − θ} ≲ \frac{d_{X}(x, y)^{2θ}}{θ(1 − θ)} . (5.3)

Combining (5.1) and (5.3), we get that the bi-Lipschitz distortion of f is ≲ \frac{1}{ε\sqrt{δθ(1−θ)}}. □

Corollary 5.3. Let (Y, d_{Y}) be a metric space which admits for every k ∈ ℤ a 2^{k}-bounded (ε, δ)-padded stochastic decomposition (thus, (Y, d_{Y}) can belong to one of the classes of spaces listed in Corollary 5.2). Then, using the notation of Section 4, for every p ∈ [1, ∞) we have

Λ_{Y}^{(p)}(σ) ≲_{ε,δ,p,σ} 1.  (5.4)

Proof. By Theorem 5.2 the metric space (Y, \sqrt{d_{Y}} ) embeds into Hilbert space with distortion ≲_{ε,δ} 1. By (4.6) we know that Λ_{L_{2}}^{(2p)}(σ) ≲_{p} σ^{−1/2}. It follows that Λ_{Y}^{(p)}(σ) ≲_{ε,δ,p} σ^{−1} ≲_{ε,δ,p,σ} 1, as required. □

Remark 5.4. For our purposes the dependence on σ in (5.4) is irrelevant. Nevertheless, the proof Corollary 5.3 can be optimized as follows. For θ ∈ (0, 1), use Theorem 5.2 to embed the metric space (Y, d_{Y}^{θ}) into Hilbert space with distortion ≲ \frac{1}{ε\sqrt{δθ(1−θ)}}. Since by (4.6) we

know that Λ_{L_{2}}^{(p/θ)}(σ) ≲ \frac{p}{θ\sqrt{σ}}. Thus, there exists a universal constant c > 1 such that

Λ_{Y}^{(p)}(σ) ⩽ (\frac{p}{θ\sqrt{σ}} · \frac{c}{ε\sqrt{θ(1 − θ)}})^{1/θ} .  (5.5)

One can then choose θ so as to minimize the right hand side of (5.5). If one cares about the behavior of our bound as σ → 0, then the optimal choice is θ = 1 − \frac{log log(1/σ)}{log(1/σ)}, yielding for σ ∈ (0, 1/4), the estimate

Λ_{Y}^{(p)}(σ) ≲_{ε,δ,p} \frac{log(1/σ)}{\sqrt{σ}}.  (5.6)

Using the ideas presented here more carefully, the logarithmic term in (5.6) was subsequently removed in [30] (where the dependence on σ was of importance for certain applications).

6. A brief review of the construction of the random group

We recall here the “graph model” for random groups and the iterative construction of a group from an appropriate sequence of graphs. The construction is due to Gromov [14]; further details may be found in the works of Ollivier [31, 32], or in the more recent work of Arzhantseva-Delzant [3].

Let G = (V, E) be an undirected simple graph. The set of edges E then has a natural double cover, the set of oriented edges of G

E⃗ = {(u, v), (v, u) | {u, v} ∈ E} .

Now let Γ be a group. A symmetric Γ-labeling of G is a map α: E⃗ → Γ such that α(u, v) = α(v, u)^{−1} for all {u, v} ∈ E. The set of these will be denoted A(G, Γ). More generally an S-labeling is a labeling whose image lies in a (symmetric) subset S ⊆ Γ. The set of such labels will be denotes A(G, S).

Let S ⊆ Γ be a symmetric subset, 1 ∉ S. The Cayley graph Cay(Γ; S) is the graph with vertex set Γ and directed edge set {(x, xs) | x ∈ Γ, s ∈ S}. This is actually an undirected graph since S is symmetric and carries the natural symmetric labeling α(x, xs) = s. The Cayley graph Cay(Γ; S) is connected iff S generates Γ. In that case let c⃗ be an oriented cycle (that is, a closed path) in that graph, and let w ∈ S^{∗} be the word in S read along the cycle. It is clear that w is trivial as an element of Γ. Conversely, any relator w ∈ S^{∗} for Γ induces many closed cycles on Cay(Γ; S): starting at any x ∈ Γ one follows the edges labeled by successive letters in w. Since w = 1 in Γ, this path is a closed cycle in the Cayley graph. This observation motivates the following construction.

Given a symmetric Γ-labeling α ∈ A(G, Γ) and an oriented path p⃗ = (e⃗_{1}, …, e⃗_{r}) in G, we set α(p⃗) = α(e⃗_{1}) · . . . · α(e⃗_{r}). We write

R_{α} = {α(c⃗) | c⃗ a cycle in G} ,

and will consider groups of the form

Γ_{α} = Γ/ ⟨R_{α}⟩^{N} ,  (6.1)

where ⟨R_{α}⟩^{N} is the normal closure of ⟨R_{α}⟩. Alternatively, given a presentation Γ = ⟨S|R⟩ we also have Γ_{α} = ⟨S|R ∪ R_{α}⟩ once we write the labels α(e⃗) as words in S. Given u ∈ V (G) and x ∈ Cay(Γ_{α}; S) we define a map α_{u→x}: G → Cay(Γ_{α}; S) as follows. For v ∈ V (G) choose a path p⃗ from u to v in G, and define α_{u→x}(v) = xα(p⃗). Note that by construction, α_{u→x}(v) does not depend on the choice of the path p⃗, and hence α_{u→x} is well defined.

With a choice of a probability measure Pr on A(G, Γ), the groups Γ_{α} become “random groups”. Note the ad-hoc nature of this construction: it is very useful for proving the existence of groups with desired properties (for example see [33]). However, the groups Γ_{α} are not “typical” in any sense of the word.

As above, let S be a symmetric set of generators for Γ. For any integer j let Pr_{j} on A(G, S^{j}) be given by independently assigning a label to each edge, uniformly at random from S^{j}. Fixing an orientation of E (i.e. a section ι: E → E⃗ of the covering map E⃗ → E) shows that that A(G, S^{j}) is non-canonically isomorphic to the product space E^{S_{j}} and identifies Pr_{j} with the natural product measure on that space.

Definition 6.1. ([31, Def. 50]) A sequence of finite connected graphs {G_{i}}_{i=1}^{∞} is called good for random quotients if there exist positive constants C, Δ such that:

(1) The maximum degree of G_{i} satisfies Δ(G_{i}) ⩽ Δ.

(2) The girth of G_{i} satisfies g(G_{i}) ⩾ C · diam(G_{i})

(3) |V (G_{i})| (equivalently, g(G_{i})) tend to ∞ with i.

Theorem 6.2. ([31, Thm. 51], [3, Thm. 6.3]) Let {G_{i}}_{i=1}^{∞} be good for random quotients, let Γ be a non-elementary torsion-free hyperbolic group with property (T), and let ε > 0. Then there exist A > 0, an integer j ⩾ 1 and a subsequence {i_{k}}_{k⩾1} such that for G = ⨆_{k⩾1} G_{i_{k}} and α chosen from A(G, S^{j}) we have with positive Pr_{j}-probability that:

(1) For any K ⩾ 1 if we set G_{(K)} = ⨆_{k⩽K} G_{i_{k}} and α_{(K)} = α↾_{G_{(K)}}, then Γ_{(K)} = Γ_{α_{(K)}} is a torsion-free non-elementary hyperbolic group. In particular, Γ_{α} is an infinite group.

(2) For any choice of vertices u_{0}, v, w ∈ V (G_{i_{k}}) and x_{0} ∈ Cay(Γ_{α}; S) the natural map

α_{u_{0}→x_{0}} : G_{i_{k}} → X_{α} =^{def} Cay(Γ_{α}; S) has

A (d_{G_{i_{k}}} (v, w) − ε diam(G_{i_{k}})) ⩽ \frac{1}{j}d_{X_{α}}(α_{u_{0}→x_{0}}(v), α_{u_{0}→x_{0}}(w)) ⩽ d_{G_{i_{k}}} (v, w).

When we apply Theorem 6.2 in Section 7, we will take the initial group Γ to be a free group. Even though Γ does not have property (T), Theorem 6.2 still applies if we assume that Γ_{(1)}, the quotient by the relations on G_{i_{1}}, satisfies the assumptions of Theorem 6.2. This happens with positive probability if we take i_{1} large enough, as explained in the discussion preceding Definition 50 in [31]

7. From Poincaré inequalities to fixed points

Let {G_{i}}_{i=1}^{∞} be an expander family of graphs, with all vertices of degrees between 3 and d and g(G_{i}) ≳ log |V (G_{i})|. For later convenience we assume that the graphs are non-bipartite. Let G = ⨆_{i⩾1} G_{i} be the disjoint union of the graphs.

Let Γ = ⟨S⟩ be free on the symmetric set of generators S of size 2k. We set X = Cay(Γ; S); a 2k-regular tree. As in Section 6, for j ⩾ 1 let A(G, S^{j}) denote the space of symmetric maps from the (directed) edges of G to S^{j}. Given α ∈ A(G, S^{j}) let Γ_{α} be the quotient of Γ presented by declaring every word read along a cycle in G to be a relator. To every α ∈ A(G, S^{j}) we associate its restrictions α_{k} to the copy of G_{k}.

Our model for random groups is obtained by choosing the value of α at each edge independently and uniformly at random. In Section 6 we reviewed the assumptions on G_{i} needed so that, with high probability, the group Γ_{α} is infinite. We now show that with probability 1 the quotient group Γ_{α} has strong fixed-point properties.

We follow below the lines of [37], with the natural changes that are required for handling powers p rather than powers 2, and p-uniformly convex metric spaces rather than CAT(0) spaces. Moreover, the handling of j > 1 in [37] was rather awkward. Taking advantage of the fact that we are reproducing much of the analysis of [37], we give a cleaner argument here for the case j > 1.

7.1. Simulating random walks and transferring Poincaré inequalities. Let G be a connected finite graph (one of the G_{i}). We assume 3 ⩽ δ(G) ⩽ Δ(G) ⩽ d and let g = g(G), N = |V (G)|. We choose α ∈ A(G, S^{j}) uniformly at random. In particular, independently for each edge. Given u, v ∈ V (G) such that d_{G}(u, v) < g/2, and x ∈ X, let β_{u→x}(v) denote the vertex xα(p⃗) of X, where p⃗ is the unique shortest path joining u and v in G. Note that, using the notation of Section 6, π_{α}(β_{u→x}(v)) = α_{u→x}(v), where π_{α} : X → X_{α} is the natural quotient map.

For every q ∈ ℕ, q < g/2, we define the random walk μ_{G,α}^{q} on the tree X as follows:

μ_{G,α}^{q}(x → ·) = ∑_{u∈G} ν_{G}(u)((β_{u→x})_{∗}μ_{G}^{q}(u → ·)),  (7.1)

where μ_{G} is the standard random walk on G and ν_{G} is its stationary measure. Since β_{u→γx}(v) = γβ_{u→x}(v), equation (7.1) is a Γ-equivariant random walk on X.

For any fixed x, x′ ∈ X, μ_{G,α}^{q}(x → x′) is a random variable depending on the choice of α. We denote its expectation by μ̄_{G,X}^{q}(x → x′) ∈ W^{Γ}(X). It is important to note that while μ_{G}^{q} and μ_{X}^{q} are indeed q-fold convolutions of the random walks μ_{G} and μ_{X}, this is not the case for the other walks we consider such as μ_{G,α}^{q}.

The walks μ_{G,α}^{q}(x → x′) will now be used to “simulate” the walks μ_{X}^{n} on X. Indeed, with high (asymptotic) probability the walks μ_{G,α}^{q}(x → x′) are close to their expectation values μ̄_{G,X}^{q}(x → x′), and these expectation values can be related to walks μ_{X}^{n} for appropriate values of n.

Equation (7.1) above furnishes the connection between the averaging notions on X and on G. For computations, however, we rewrite it as:

μ_{G,α}^{q}(x → x′) = ∑_{\left|{ \atop p}\right|=q} ν_{G}(p_{0})μ_{G}^{q}(p⃗)𝟙 (xα(p⃗) = x′) ,  (7.2)

where the sum is over all oriented paths p⃗ of length q in G starting at p_{0}, and 𝟙(x = y) is the characteristic function of the diagonal of X × X, so that α ↦ 𝟙(xα(p⃗) = x′) is an indicator random variable for the event that α(p⃗) equals x^{−1}x′ as elements of Γ.

We now easily compute the mean walk μ̄_{G,X}^{q}. We start with the instructive case q = 1, where unwinding the definitions of ν_{G} and μ_{G} gives:

μ_{G,α}^{1}(x → x′) = \frac{1}{2 |E(G)|} ∑_{e⃗∈E⃗} 𝟙(xα(e⃗) = x′).

Taking expectation we conclude that μ̄_{G,X}^{1}(x → x′) equals the probability that following a random word in S^{j} will lead us from x to x′, that is μ_{X}^{j}(x → x′).

A similar calculation for q > 1 gives the following.

Lemma 7.1 (generalization of [37, Lem. 2.12]). Let q < g/2. We can write μ̄_{G,X}^{q} as a convex combination

μ̄_{G,X}^{q} = ∑_{l=0}^{q} P_{G}^{q}(l)μ_{X}^{jl}  (7.3)

where the weights P_{G}^{q}(l) are concentrated on large values of l, in the sense that

Q_{G}^{q} =^{def} ∑_{l⩽q/6} P_{G}^{q}(l) ⩽ e^{−q/18}.  (7.4)

Also, wherever μ̄_{G,X}^{q}(x → x′) is non-zero then it is at least

ε(d, k, j)^{q} =^{def} (\frac{1}{d(2k)^{j}} )^{q} .  (7.5)

Proof. Given a path p⃗ in G of length q < g/2, let p̃ be the shortest path connecting the endpoints of G. Since the ball of radius q in G around the starting vertex p_{0} of p⃗ is a tree, p̃ is unique and can be obtained from p⃗ by successively cancelling “backtracks” (consecutive steps which traverse a single edge in opposite directions). This p̃ is a simple path, traversing each of its edges exactly once. It follows that the law of the Γ-valued random variable α ↦ α(p̃) is that of a uniformly chosen element in S^{jl} where l = \left|{ \atop p̃}\right|. Moreover, the symmetry of the labelling α shows that the words α(p⃗) and α(p̃) are equal as elements of the free group Γ. In particular, the expectation of the indicator variable 𝟙 (xα(p⃗) = x′) in (7.2) is μ_{X}^{jl}(x, x′). Equation (7.3) now follows, with

P_{G}^{q}(l) = ∑_{\left|{ \atop p}\right|=q,\left|{ \atop p̃}\right|=l} ν_{G}(p_{0})μ_{G}^{q}(p⃗).

Note that P_{G}^{q}(l) is precisely the probability that q steps of the stationary random walk on G travel a distance l. The bound (7.4) is established in [37, Lem. 2.12].

For the lower bound on μ̄_{G,X}^{q}(x → x′) note first that for any path p⃗ in G of length q, μ_{G}^{q}(p⃗) ⩾ d^{−q} since every vertex has degree at most d. Now let 0 ⩽ l ⩽ q and assume that l, q have the same parity (if either condition fails then P_{G}^{q}(l) = 0). Then for any vertex p_{0} there exists paths p⃗ of length q and reduced length l starting at p_{0}. It follows that P_{G}^{q}(l) ⩾ ∑_{p_{0}} ν_{G}(p_{0})d^{−q} ⩾ d^{−q} for l as above.

Finally, let x, x′ ∈ X and let their distance be at most jq and have the same parity as jq (otherwise, for every term in (7.3) either P_{G}^{q}(l) or μ_{X}^{jl}(x → x′) vanishes). Then the same argument shows that μ_{X}^{jq}(x → x′) ⩾ (2k)^{−jq}. Equation (7.5) now follows from the estimate μ̄_{G,X}^{q}(x → x′) ⩾ P_{G}^{q}(q)μ_{X}^{jq}(x → x′). □

Definition 7.2. We say that μ_{G,α}^{•} effectively simulates μ_{X}^{•} up to time q_{0} if for every 1 ⩽ q ⩽ q_{0} and every x, x′ ∈ X we have:

μ_{G,α}^{q}(x → x′) ⩾ \frac{1}{2}μ̄_{G,X}^{q}(x → x′),

and in addition we have for every x, x′ ∈ X:

μ_{G,α}^{1}(x → x′) ⩽ 2μ_{X}^{j}(x → x′).

When the walks on G effectively simulate the walks on X we can transfer Poincaré inequalities from G to Γ_{α}:

Proposition 7.3. Let G = (V, E) be a finite graph on N vertices, and let σ be the spectral gap of G. Let α ∈ A(G, S^{j}) be such that μ_{G,α}^{•} effectively simulates μ_{X}^{•} up to a time q_{0} ≳ log N. Let Y be a metric space on which Γ_{α} acts by isometries. Write B(X, Y) for the space of Γ-equivariant functions from X to Y where the free group Γ acts via its quotient Γ_{α}. Then for every f ∈ B(X, Y) there exists m comparable to log N such that

E_{μ_{X}^{jm}}^{(p)}(f) ≲ (Λ_{Y}^{(p)}(σ, N))^{p} E_{μ_{X}^{j}}^{(p)}(f).

Proof. By definition of μ_{G,α}^{q}, we have for q < g/2:

|∇_{μ_{G,α}^{q}}(f)|_{p}^{p} (x) = ∑_{u∈V} ν_{G}(u) |∇_{μ_{G}^{q}}(f ∘ β_{u→x})|_{p}^{p} (u).  (7.6)

Note that in (7.6) the composition f ∘ β_{u→x} is well-defined since β_{u→x}(v) is defined for all v ∈ V (G) with d_{G}(u, v) < g/2, and q < g/2. The same remark applies for the remainder of the computations below, where we treat β_{u→x} as a function even though it is only a partially defined function.

Since the action of Γ on Y factors via Γ_{α}, the function f can also be viewed as an equivariant function on X_{α}. Fixing u_{0} ∈ V, we use this to set f_{0} = f ∘ α_{u_{0}→x}. Then for each u ∈ V (G) we have

|∇_{μ_{G}^{q}}(f ∘ β_{u→x})|_{p}^{p} (u) = |∇_{μ_{G}^{q}}(f_{0})|_{p}^{p} (u),

by projecting to X_{α} and translating by the element γ ∈ Γ which sends α_{u_{0}→x}(u) back to x. It follows that

|∇_{μ_{G,α}^{q}}(f)|_{p}^{p} (x) = 2E_{μ_{G}^{q}}^{(p)}(f_{0}).  (7.7)

Applying the Poincaré inequality (4.1) for maps from G to Y and using (7.7) on both sides we have:

|∇_{μ_{G,α}^{q}}(f)|_{p}^{p} (x) ≲ (Λ_{Y}^{(p)}(σ(G), N))^{p} |∇_{μ_{G,α}}(f)|_{p}^{p} (x).  (7.8)

If q is small enough then the assumption of effective simulation allows us to replace the random walks in (7.8) by their expectations up to a constant loss. Applying Lemma 7.1 and omitting some (non-negative) terms in the sum in (7.3), we find:

min_{q⩾l>q/6} |∇_{μ_{X}^{jl}}(f)|_{p}^{p} (x) ⩽^{(7.4)} ∑_{q⩾l>q/6} \frac{P_{G}^{q}(l)}{1 − Q_{G}^{q}} |∇_{μ_{X}^{jl}}(f)|_{p}^{p} (x) ≲ (Λ_{Y}^{(p)}(σ(G), N))^{p} |∇_{μ_{X}^{j}}(f)|_{p}^{p} (x).

By assumption we can take q ≍ log N, and the proof is complete. □

Proposition 7.4. (generalization of [37, Lem. 2.13]) Let G be a finite graph with 3 ⩽ δ(G) ⩽ Δ(G) ⩽ d. Let N = |V (G)|, and assume g = g(G) ⩾ C log N. Then there exists C′ > 0 depending on d, k, j, C so that the probability of μ_{G,α}^{•} failing to effectively simulate μ_{X}^{•} up to time C′ log N is o_{d,k,j}(1) as N → ∞.

Proof. Since Γ acts transitively on X, our measure-valued random variables μ_{G,α}^{q}(x → ·) are determined by their value at any particular x ∈ X, which we fix. For each choice of α, the measure μ_{G,α}^{q}(x → ·) is supported on the ball B_{X}(x, jq), so for each q we need to control |B_{X}(x, jq)| real-valued random variables on A(G, S^{j}). Let μ_{G,α}^{q}(x → x′) be one such random variable. We give a bound τ_{q} to its Lipschitz constant as a map from A(G, S^{j}) (equipped with the Hamming metric) to [0, 1]. For this it suffices to consider a pair of labelings α, α′ which agree everywhere except at e ∈ E. We then have (sum over paths which traverse e at some point)

|μ_{G,α}^{q}(x → x′) − μ_{G,α′}^{q}(x → x′)| ⩽ ∑_{e∈p⃗} ν_{G}(p_{0})μ_{G}^{q}(p⃗).

There are at most 2qd^{q−1} such paths, and each contributes at most \frac{2d}{3N} 3^{−q} to the right-hand-side since ν_{G}(u) = d(u)/2|E(G)|. the vertex degrees allow us to take

τ_{q} = \frac{4q}{3N} (\frac{d}{3})^{q} .

We would like to rule out μ_{G,α}^{q}(x → x′) deviating from its non-zero mean μ̄_{G,X}^{q}(x → x′) by a factor of at least 2. It enough to bound the probability of deviation by at least \frac{1}{2}ε(d, k, j)^{q}, where \frac{1}{2}ε(d, k, j) is as in (7.5)). Azuma’s inequality (see, e.g., [1, Thm. 7.2.1]) shows that the probability for this is at most:

exp \{−\frac{ε(d, k, j)^{2q}}{8 |E(G)| τ_{q}^{2}} \} .

We can choose C′ small enough to ensure (\frac{d}{3ε^{2}} )^{jq} is an arbitrary small power of N. Also |E(G)| ≲_{d} N, so the probability of deviation is exponentially small in a positive power of N. The number of random variables is polynomial in N (it is at most (2k)^{qj} for each q) so we can take the union bound. A similar analysis shows that probability of some μ_{G,α}^{1}(x → x′) being too large also decays. □

7.2. Fixed points. Returning to G being the union of finite components G_{i}, we summarize the result of the previous section:

Theorem 7.5. Assume that the {G_{i}}_{i⩾1} are connected non-bipartite graphs on N_{i} vertices with vertex degrees in [3, d], spectral gaps σ(G_{i}) ⩾ σ > 0 and girths ≳ log N_{i}. Let G = ⨆_{i⩾1} G_{i} and let Γ_{α} be constructed at random from α ∈ A(G, S^{j}) with j even. Then almost surely for every metric space Y, and every action of Γ_{α} on Y by isometries, there exists arbitrarily large N_{i} such that for any f ∈ B(X_{α}, Y) there exist m comparable to log N_{i} such that

E_{μ_{X}^{jm}}^{(p)}(f) ≲ (Λ_{Y}^{(p)}(σ, N_{i}))^{p} E_{μ_{X}^{j}}^{(p)}(f).

Theorem 7.6. Let Γ_{α} satisfy the conclusion of Theorem 7.5. Let Y be p-uniformly convex, and assume that Λ_{Y}^{(p)}(σ) < ∞ or, in greater generality, that

lim_{N→∞} (\frac{log log N}{log N} )^{\frac{1}{2p}} Λ_{Y}^{(p)}(σ, N) = 0

(in the terminology of Definition 4.3, we are assuming that Y has small Poincaré moduli of exponent p). Then every isometric action of Γ_{α} on Y fixes a point.

Proof. By Theorems 3.10 and 7.5, there exist arbitrarily large N such that for any equivariant f ∈ B(X_{α}, Y) (identified with its pull-back to X) there is some m comparable to log N such that:

E_{μ_{X}^{j}}^{(p)} (A_{μ_{X}^{jm}}^{(p)}f) ≲_{p,c_{Y} ,j,d} (Q(N) + \frac{1}{log N} ) E_{μ_{X}^{j}}^{(p)}(f),

where Q(N) → 0 as N → ∞. Choosing N large enough, we see can ensure the existence of m such that

E_{μ_{X}^{j}}^{(p)} (A_{μ_{X}^{jm}}^{(p)}f) ⩽ \frac{1}{2}E_{μ_{X}^{j}}^{(p)}(f).

Note that the choice of N was independent of f. Now Proposition 3.8 shows that iterating the averaging (with m depending on f but bounded by N) leads to a sequence converging to a fixed point (here Γ\X is a s single point, so B(X, Y) is non-empty).

In more detail, let μ_{X_{α}} denote the standard random walk on X_{α}. We have in fact shown the existence of m such that

E_{μ_{Xα}^{j}}^{(p)} (A_{μ_{Xα}^{jm}}^{(p)}f) ⩽ \frac{1}{2}E_{μ_{Xα}^{j}}^{(p)}(f).

In order to apply Proposion 3.8 we further need to verify that a certain graph is connected – specifically the Cayley graph of Γ_{α} with respect to the set S^{j}. Since j is even S^{j} contains S^{2} (as sets of elements of Γ_{α}), so it is enough to verify that S^{2} is a set of generators for Γ_{α}. Indeed, the graphs G_{i} are non-bipartite and hence contain odd cycles. It follows that some relators in R_{α} have odd length, so that up to multiplication by a relator, every element of Γ_{α} can be represented by a word in S of even length. □

Remark 7.7. Theorem 7.6 was formulated for the limiting wild group Γ_{α}, i.e., the group corresponding to the infinite graph G. Arguing identically for the random group corresponding to the relations of each G_{i} separately, we obtain Theorem 1.1.

Acknowledgements. We are very grateful to the anonymous referee for the careful reading of our manuscript, and for many helpful suggestions.

Added in proof. Francois Dahmani pointed out to us that the answer to one of the questions that we asked in the introduction is known. Specifically, in [22, Sec. 8] it is shown how to construct a hyperbolic group with the fixed-point property on all symmetric spaces and buildings associated to linear groups.

References

[1] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience [John Wiley & Sons], New York, second edition, 2000. With an appendix on the life and work of Paul Erdős.

[2] G. Arzhantseva, M. R. Bridson, T. Januszkiewicz, I. J. Leary, A. Minasyan, and J. Świa̧tkowski. Infinite groups with fixed point properties. Geom. Topol., 13(3):1229–1263, 2009.

[3] G. A. Arzhantseva and T. Delzant. Examples of random groups. submitted; preprint available at

http://www.unige.ch/math/folks/arjantse/publicationsGA.html, 2008.

[4] U. Bader, A. Furman, T. Gelander, and N. Monod. Property (T) and rigidity for actions on Banach spaces. Acta Math., 198(1):57–105, 2007.

[5] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[6] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[7] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[8] E. Breuillard and T. Gelander. A topological Tits alternative. Ann. of Math. (2), 166(2):427–474, 2007.

[9] M. R. Bridson and A. Haefliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999.

[10] P. Delorme. 1-cohomologie des représentations unitaires des groupes de Lie semi-simples et résolubles. Produits tensoriels continus de représentations. Bull. Soc. Math. France, 105(3):281–336, 1977.

[11] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56(2):121–155, 1976.

[12] D. Fisher and G. Margulis. Almost isometric actions, property (T), and local rigidity. Inv. Math., 162(1):19–80, 2005.

[13] D. Fisher and L. Silberman. Groups not acting on manifolds. Int. Math. Res. Not. IMRN, (16):Art. ID rnn060, 11, 2008.

[14] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1):73–146, 2003.

[15] E. Guentner, N. Higson, and S. Weinberger. The Novikov conjecture for linear groups. Publ. Math. Inst. Hautes Études Sci., (101):243–268, 2005.

[16] A. Guichardet. Étude de la l-cohomologie et de la topologie du dual pour les groupes de Lie à radical abélien. Math. Ann., 228(3):215–232, 1977.

[17] N. Higson, V. Lafforgue, and G. Skandalis. Counterexamples to the Baum-Connes conjecture. Geom. Funct. Anal., 12(2):330–354, 2002.

[18] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561 (electronic), 2006.

[19] H. Izeki, T. Kondo, and S. Nayatani. Fixed-point property of random groups. Ann. Global Anal. Geom., 35(4):363–379, 2009.

[20] H. Izeki and S. Nayatani. Combinatorial harmonic maps and discrete-group actions on Hadamard spaces. Geom. Dedicata, 114:147–188, 2005.

[21] J. Jost. Nonpositive curvature: geometric and analytic aspects. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1997.

[22] M. Kapovich. Representations of polygons of finite groups. Geom. Topol., 9:1915–1951 (electronic), 2005.

[23] B. Kleiner and B. Leeb. Rigidity of quasi-isometries for symmetric spaces and Euclidean buildings. Inst. Hautes Études Sci. Publ. Math., (86):115–197 (1998), 1997.

[24] U. Lang and T. Schlichenmaier. Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Int. Math. Res. Not., (58):3625–3655, 2005.

[25] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: Dimension, snowflakes, and average distortion. Eur. J. Comb., 26(8):1180–1190, 2005.

[26] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[27] J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

[28] J.-i. Nagata. Modern dimension theory, volume 2 of Sigma Series in Pure Mathematics. Heldermann Verlag, Berlin, revised edition, 1983.

[29] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromovhyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[30] A. Naor and Y. Rabani. Spectral inequalities on curved spaces. Preprint, 2005.

[31] Y. Ollivier. A January 2005 invitation to random groups, volume 10 of Ensaios Matemáticos [Mathematical Surveys]. Sociedade Brasileira de Matemática, Rio de Janeiro, 2005. avaliable at

    http://www.umpa.ens-lyon.fr/~yollivie/publs.html.

[32] Y. Ollivier. On a small cancellation theorem of Gromov. Bull. Belg. Math. Soc. Simon Stevin, 13(1):75– 89, 2006.

[33] Y. Ollivier and D. T. Wise. Kazhdan groups with infinite outer automorphism group. Trans. Amer. Math. Soc., 359(5):1959–1976 (electronic), 2007.

[34] N. Ozawa. A note on non-amenability of ℬ(l_{p}) for p = 1, 2. Internat. J. Math., 15(6):557–565, 2004.

[35] P. Pansu. Fixed points of actions of building groups on CAT(0) spaces. In workshop ”Group theory: geometric and probabilistic methods”, Ein Gedi, Octobre 2006, available at

    http://www.math.u-psud.fr/~pansu/ein_gedi_beamer.pdf.

[36] P. Pansu. Cohomologie L^{p}: invariance sous quasiisométrie. Preprint available at

    http://www.math.u-psud.fr/~pansu/qi04.pdf, 1995.

[37] L. Silberman. Addendum to: “Random walk in random groups” [Geom. Funct. Anal. 13 (2003), no. 1, 73–146; mr1978492] by M. Gromov. Geom. Funct. Anal., 13(1):147–177, 2003.

[38] M.-T. Wang. A fixed point theorem of discrete group actions on Riemannian manifolds. J. Differential Geom., 50(2):249–267, 1998.

[39] G. Yu. Hyperbolic groups admit proper affine isometric actions on l^{p}-spaces. Geom. Funct. Anal., 15(5):1144–1151, 2005.

[40] A. Żuk. Property (T) and Kazhdan constants for discrete groups. Geom. Funct. Anal., 13(3):643–670, 2003.

Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York NY 10012, USA.

  E-mail address: naor@cims.nyu.edu

Department of Mathematics, University of British Columbia, 1984 Mathematics Road, Vancouver BC V6T 1Z2, Canada.

  E-mail address: lior@math.ubc.ca