BOURGAIN’S DISCRETIZATION THEOREM

OHAD GILADI, ASSAF NAOR, AND GIDEON SCHECHTMAN

Abstract. Bourgain’s discretization theorem asserts that there exists a universal constant C ∈ (0, ∞) with the following property. Let X, Y be Banach spaces with dim X = n. Fix D ∈ (1, ∞) and set δ = e^{−n^{Cn}}. Assume that N is a δ-net in the unit ball of X and that N admits a bi-Lipschitz embedding into Y with distortion at most D. Then the entire space X admits a bi-Lipschitz embedding into Y with distortion at most CD. This mostly expository article is devoted to a detailed presentation of a proof of Bourgain’s theorem. We also obtain an improvement of Bourgain’s theorem in the important case when Y = L_{p} for some p ∈ [1, ∞): in this case it suffices to take δ = C^{−1}n^{−5/2} for the same conclusion to hold true. The case p = 1 of this improved discretization result has the following consequence. For arbitrarily large n ∈ ℕ there exists a family 𝒴 of n-point subsets of {1, …, n}^{2} ⊆ ℝ^{2} such that if we write |𝒴 | = N then any L_{1} embedding of 𝒴 , equipped with the Earthmover metric (a.k.a. transportation cost metric or minimumum weight matching metric) incurs distortion at least a constant multiple of \sqrt{log log N}; the previously best known lower bound for this problem was a constant multiple of \sqrt{log log log N}.

1. Introduction

If (X, d_{X}) and (Y, d_{Y}) are metric spaces then the (bi-Lipschitz) distortion of X in Y, denoted c_{Y} (X), is the infimum over those D ∈ [1, ∞] such that there exists f : X → Y and s ∈ (0, ∞) satisfying sd_{X}(x, y) ⩽ d_{Y} (f(x), f(y)) ⩽ Dsd_{X}(x, y) for all x, y ∈ X. Assume now that X, Y are Banach spaces, with unit balls B_{X}, B_{Y}, respectively. Assume furthermore that X is finite dimensional. It then follows from general principles that for every ε ∈ (0, 1) there exists δ ∈ (0, 1) such that for every δ-net N_{δ} in B_{X} (recall that a δ-net is a maximal δ-separated subset of B_{X}) we have c_{Y} (N_{δ}) ⩾ (1 − ε)c_{Y} (X). Indeed, set D = c_{Y} (X) and assume that for all k ∈ ℕ there is a 1/k-net N_{1/k} of B_{X} and f_{k} : N_{1/k} → Y satisfying ∥x − y∥_{X} ⩽ ∥f_{k}(x) − f_{k}(y)∥_{Y} ⩽ (1 − ε)D∥x − y∥_{X} for all x, y ∈ N_{1/k}. For each x ∈ B_{X} fix some z_{k}(x) ∈ N_{1/k} satisfying ∥x − z_{k}(x)∥_{X} ⩽ 1/k. Let 𝒰 be a free ultrafilter on ℕ. Consider the ultrapower Y_{𝒰} , i.e., the space of equivalence classes of bounded Y -valued sequences modulo the equivalence relation (x_{k})_{k=1}^{∞} ∼ (y_{k})_{k=1}^{∞} ⟺ lim_{k→𝒰} ∥x_{k} − y_{k}∥_{Y} = 0, equipped with the norm ∥(x_{k})_{k=1}^{∞}/ ∼ ∥_{Y_{𝒰}} = lim_{k→𝒰} ∥x_{k}∥_{Y}. Define f_{𝒰} : B_{X} → Y_{𝒰} by f_{𝒰} (x) = (f_{k}(z_{k}(x))_{k=1}^{∞})/ ∼. Then ∥x − y∥_{X} ⩽ ∥f_{𝒰} (x) − f_{𝒰} (y)∥_{Y_{𝒰}} ⩽ (1 − ε)D∥x − y∥_{X} for all x, y ∈ X. By a (nontrivial) w^{∗}-Gâteaux differentiability argument due to Heinrich and Mankiewicz [14] it now follows that there exists a linear mapping T_{1} : X → (Y_{𝒰} )^{∗∗} satisfying ∥x∥_{X} ⩽ ∥T_{1}x∥_{(Y_{𝒰} )^{∗∗}} ⩽ (1 − ε/2)D∥x∥_{X} for all x ∈ X. Since X, and hence also T_{1}X, is finite dimensional, the Principle of Local Reflexivity [19] says there exists a linear mapping T_{2} : T_{1}X → Y_{𝒰} satisfying ∥y∥_{(Y_{𝒰} )^{∗∗}} ⩽ ∥T_{2}y∥_{Y_{𝒰}} ⩽ (1 + ε/5)∥y∥_{(Y_{𝒰} )^{∗∗}} for all y ∈ T_{1}X. By general properties of ultrapowers (see [13]) there exists a linear mapping T_{3} : T_{2}T_{1}X → Y satisfying ∥y∥_{Y_{𝒰}} ⩽ ∥T_{3}y∥_{Y} ⩽ (1 + ε/5)∥y∥_{Y_{𝒰}} for all y ∈ T_{2}T_{1}X. By considering T_{3}T_{2}T_{1} : X → Y we have D = c_{Y} (X) ⩽ (1 − ε/2)(1 + ε/5)^{2}D, a contradiction.

O. G. was supported by Fondation Sciences Mathématiques de Paris and NSF grant CCF-0832795. A. N.

was supported by NSF grant CCF-0832795, BSF grant 2006009 and the Packard Foundation. G. S. was supported by the Israel Science Foundation. This work was completed when A. N. and G. S. were visiting the Quantitative Geometry program at MSRI.

The argument sketched above is due to Heinrich and Mankiewicz [14]. An earlier and different argument establishing the existence of δ is due to important work of Ribe [22]. See the book [5] for a detailed exposition of both arguments. These proofs do not give a concrete estimate on δ. The first purpose of the present article, which is mainly expository, is to present in detail a different approach due to Bourgain [7] which does yield an estimate on δ. Before stating Bourgain’s theorem, it will be convenient to introduce the following quantity.

Definition 1.1 (Discretization modulus). For ε ∈ (0, 1) let δ_{X↪Y} (ε) be the supremum over those δ ∈ (0, 1) such that every δ-net N_{δ} in B_{X} satisfies c_{Y} (N_{δ}) ⩾ (1 − ε)c_{Y} (X).

Theorem 1.1 (Bourgain’s discretization theorem). There exists C ∈ (0, ∞) such that for every two Banach spaces X, Y with dim X = n < ∞ and dim Y = ∞, and every ε ∈ (0, 1), we have

δ_{X↪Y} (ε) ⩾ e^{−(n/ε)^{Cn}}.  (1)

Theorem 1.1 was proved by Bourgain in [7] for some fixed ε_{0} ∈ (0, 1). The above statement requires small technical modifications of Bourgain’s argument, but these are minor and all the conceptual ideas presented in the proof of Theorem 1.1 below are due to Bourgain. Readers might notice that our presentation of the proof of Theorem 1.1 seems somewhat different from [7], but this impression is superficial; the exposition below is merely a restructuring of Bourgain’s argument.

We note that it is possible to refine the estimate (1) so as to depend on the distortion c_{Y} (X). Specifically, we have the bound

δ_{X↪Y} (ε) ⩾ e^{−(c_{Y} (X)/ε)^{Cn}}.  (2)

The estimate (2) implies (1) since due to Dvoretzky’s theorem [12] c_{Y} (ℓ_{2}^{n}) = 1, and therefore c_{Y} (X) ⩽ \sqrt{n} by John’s theorem [16]. If we do not assume that dim Y = ∞ then we necessarily have dim Y ⩾ n since otherwise c_{Y} (X) = ∞, making (2) hold vacuously. Thus, by John’s theorem once more, c_{Y} (X) ⩽ n, and again we see that (2) implies (1). The proof below will establish (2), and not only the slightly weaker statement (1). We remark that Bourgain’s discretization theorem is often quoted with the conclusion that if δ is at most as large as the right hand side of (2) and N_{δ} is a δ-net of B_{X} then Y admits a linear embedding into Y whose distortion is at most c_{Y} (N_{δ})/(1 − ε). The Heinrich-Mankiewicz argument described above shows that for finite dimensional spaces X, a bound on c_{Y} (X) immediately implies the same bound when the bi-Lipschitz embedding is required to be linear. For this reason we ignore the distinction between linear and nonlinear bi-Lipschitz embeddings, noting also that for certain applications (e.g., in computer science), one does not need to know that embeddings are linear.

We do not know how close is the estimate (1) to being asymptotically optimal, though we conjecture that it can be improved. The issue of finding examples showing that δ_{X↪Y} (ε) must be small has not been sufficiently investigated in the literature. The known upper bounds on δ_{X↪Y} (ε) are very far from (1). For example, the metric space (ℓ_{1}^{n}, \sqrt{∥x − y∥_{1}}) embeds isometrically into L_{2} (see [11]). It follows that any δ-net in B_{ℓ_{1}^{n}} embeds into L_{2} with distortion at most \sqrt{2/δ}. Contrasting this with c_{L_{2}}(ℓ_{1}^{n}) = \sqrt{n} shows that δ_{ℓ_{1}^{n}↪L_{2}}(ε) ⩽ 2/ ((1 − ε)^{2}n).

It turns out that a method that was introduced by Johnson, Maurey and Schechtman [17] (for a different purpose) can be used to obtain improved bounds on δ_{X↪Y} (ε) for certain Banach spaces Y, including all L_{p} spaces, p ∈ [1, ∞); the second purpose of this article is to present this result. To state our result recall that if (Ω, ν) is a measure space and (Z, ∥ · ∥_{X}) is a Banach space then for p ∈ [1, ∞] the vector valued L_{p} space L_{p}(ν, Z) is the space of all equivalence classes of measurable functions f : Ω → Z such that ∥f∥_{L_{p}(ν,Z)}^{p} = ∫_{Ω} ∥f∥_{Z}^{p}dν < ∞ (and ∥f∥_{L_{∞}(ν,Z)} = esssup_{ω∈Ω}∥f(ω)∥_{Y}). Theorem 1.2. There exists a universal constant κ ∈ (0, ∞) with the following property. Assume that δ, ε ∈ (0, 1) and D ∈ [1, ∞) satisfy δ ⩽ κε^{2}/(n^{2}D). Let X, Y be Banach spaces with dim X = n < ∞, and let N_{δ} be a δ-net in B_{X}. Assume that c_{Y} (N_{δ}) ⩽ D. Then there exists a separable probability space (Ω, ν), a finite dimensional linear subspace Z ⊆ Y, and a linear operator T : X → L_{∞}(ν, Z) satisfying

∀x ∈ X, \frac{1 − ε}{D}∥x∥_{X} ⩽ ∥T x∥_{L_{1}(ν,Z)} ⩽ ∥T x∥_{L_{∞}(ν,Z)} ⩽ (1 + ε)∥x∥_{X}.

Theorem 1.2 is proved in Section 5; as we mentioned above, its proof builds heavily on ideas from [17]. Because ν is a probability measure, for all p ∈ [1, ∞] and all h ∈ L_{∞}(ν, Y) we have ∥h∥_{L_{1}(ν,Y)} ⩽ ∥h∥_{L_{p}(ν,Y)} ⩽ ∥h∥_{L_{∞}(ν,Y)}. Therefore, the following statement is a consequence of Theorem 1.2.

δ ⩽ \frac{κε^{2}}{n^{2}c_{Y} (N_{δ})} ⟹ ∀p ∈ [1, ∞), c_{Y} (N_{δ}) ⩾ \frac{1 − ε}{1 + ε}c_{L_{p}(ν,Y)}(X).  (3)

We explained above that if Y is infinite dimensional then c_{Y} (N_{δ}) ⩽ \sqrt{n}. It therefore follows from (3) that if L_{p}(ν, Y) admits an isometric embedding into Y, as is the case when Y = L_{p}, then δ_{X↪Y} (ε) ⩾ κε^{2}/(n^{5/2}). This is recorded for future reference as the following corollary.

Corollary 1.3. There exists a universal constant κ ∈ (0, ∞) such that for every p ∈ [1, ∞) and ε ∈ (0, 1), for every n-dimensional Banach space X we have

δ_{X↪L_{p}}(ε) ⩾ \frac{κε^{2}}{n^{5/2}} .  (4)

There is a direct application of the case p = 1 of Corollary 1.3 to the minimum cost matching metric on ℝ^{2}. Given n ∈ ℕ, consider the following metric τ on the set of all n-point subsets of ℝ^{2}, known as the minimum cost matching metric.

τ(A, B) = min {∑_{a∈A} ∥a − f(a)∥_{2} : f : A → B is a bijection} .

Corollary 1.4. There exists a universal constant c ∈ (0, ∞) with the following property. For arbitrarily large n ∈ ℕ there exists a family 𝒴 of n-point subsets of {1, …, n}^{2} ⊆ ℝ^{2} such that if we write |𝒴 | = N then c_{L_{1}}(𝒴 , τ) ⩾ c\sqrt{log log N}.

The previously best known lower bound in the context of Corollary 1.4, due to [20], was c_{L_{1}}(𝒴 , τ) ⩾ c\sqrt{log log log N}. We refer to [20] for an explanation of the relevance of such problems to theoretical computer science. The deduction of Corollary 1.4 from Corollary 1.3 follows mutatis mutandis from the argument in [20, Sec. 3.1], the only difference being the use of the estimate (4) when p = 1 rather than the estimate (1) when Y = L_{1}.

For an infinite dimensional Banach space Y define

δ_{n}(Y) =^{def} inf {δ_{X↪Y} (1/2) : X is an n dimensional Banach space} ,

and set

δ_{n} =^{def} inf {δ_{n}(Y) : Y is an infinite dimensional Banach space} .

Theorem 1.1 raises natural geometric questions. Specifically, what is the asymptotic behavior of δ_{n} as n → ∞? The difficulty of this question does not necessarily arise from the need to consider all, potentially “exotic”, Banach spaces Y. In fact, the above discussion shows that Ω(1/n^{5/2}) ⩽ δ_{n}(L_{2}) ⩽ O(1/n), so we ask explicitly what is the asymptotic behavior of δ_{n}(L_{2}) as n → ∞? For applications to computer science (see e.g. [20]) it is especially important to bound δ_{n}(L_{1}), so we also single out the problem of evaluating the asymptotic behavior of δ_{n}(L_{1}) as n → ∞. Recently, two alternative proofs of Theorem 1.1 that work for certain special classes of spaces Y were obtained in [18, 15], using different techniques than those presented here (one based on a quantitative differentiation theorem, and the other on vector-valued Littlewood-Paley theory). These new proofs yield, however, the same bound as (1). The proof of Theorem 1.1 presented below is the only known proof of Theorem 1.1 that works in full generality.

Remark 1.2. The questions presented above are part of a more general discretization problem in embedding theory. One often needs to prove nonembeddability results for finite spaces, where the distortion is related to their cardinality. In many cases it is, however, easier to prove nonembeddability results for infinite spaces, using techniques that are available for continuous objects. It is natural to then prove a discretization theorem, i.e., a statement that transfers a nonembeddability theorem from a continuous object to its finite nets, with control on their cardinality. This general scheme was used several times in the literature, especially in connection to applications of embedding theory to computer science; see for example [20], where Bourgain’s discretization theorem plays an explicit role, and also, in a different context, [9]. The latter example deals with the Heisenberg group rather than Banach spaces, the discretization in question being of an infinitary nonembeddability theorem of Cheeger and Kleiner [8]. It would be of interest to study the analogue of Bourgain’s discretization theorem in the context of Carnot groups. This can be viewed as asking for a quantitative version of a classical theorem of Pansu [21]. In the special case of embeddings of the Heisenberg group into Hilbert space, a different approach was used in [2] to obtain a sharp result of this type.

Remark 1.3. A Banach space Z is said to be finitely representable in a Banach space Y if there exists K ∈ [1, ∞) such that for every finite dimensional subspace X ⊆ Z there exists an injective linear operator T : X → Y satisfying ∥T ∥·∥T^{−1}∥ ⩽ K. A theorem of Ribe [22] states that if Z and Y are uniformly homeomorphic, i.e., there exists a homeomorphism f : Z → Y such that both f and f^{−1} are uniformly continuous, then Z is finitely representable in Y and vice versa. This rigidity phenomenon suggests that isomorphic invariants of Banach spaces which are defined using statements about finitely many vectors are preserved under uniform homemorphisms, and as such one might hope to reformulate them in a way that is explicitly nonlinear, i.e., while only making use of the metric structure and without making any reference to the linear structure. Once this (usually nontrivial) task is achieved, one can hope to transfer some of the linear theory of Banach spaces to the context of general metric spaces. This so called “Ribe program” was put forth by Bourgain in [6]; a research program that attracted the work of many mathematicians in the past 25 years, and has had far reaching consequences in areas such as metric geometry, theoretical computer science, and group theory. The argument that we presented for the positivity of δ_{X↪Y} (ε) implies Ribe’s rigidity theorem. Indeed, it is a classical observation [10] that if f : Z → Y is a uniform homeomorphism then it is bi-Lipschitz for large distances, i.e., for every d ∈ (0, ∞) there exists L ∈ (0, ∞) such that L^{−1}∥x − y∥_{Z} ⩽ ∥f(x) − f(y)∥_{Y} ⩽ L∥x − y∥_{Z} whenever x, y ∈ Z satisfy ∥x − y∥_{Z} ⩾ d. Consequently, if X ⊆ Z is a finite dimensional subspace then d-nets in rB_{X} embed into Y with distortion at most L^{2} for every r > d. By rescaling, the same assertion holds for δ-nets in B_{X} for every δ ∈ (0, 1). Hence X admits a linear embedding into Y with distortion is at most 2L^{2}. For this reason, in [7] Bourgain calls his discretization theorem a quantitative version of Ribe’s finite representability theorem. Sufficiently good improved lower bounds on δ_{X↪Y} (ε) are expected to have impact on the Ribe program.

2. The strategy of the proof of Theorem 1.1

From now on (X, ∥ · ∥_{X}) will be a fixed n-dimensional normed space (n > 1), with unit ball B_{X} = {x ∈ X : ∥x∥_{X} ⩽ 1} and unit sphere S_{X} = {x ∈ X : ∥x∥_{X} = 1}. We will identify X with ℝ^{n}, and by John’s theorem [16] we will assume without loss of generality that the standard Euclidean norm ∥ · ∥_{2} on ℝ^{n} satisfies

∀ x ∈ X, \frac{1}{\sqrt{n}}∥x∥_{2} ⩽ ∥x∥_{X} ⩽ ∥x∥_{2}.  (5)

Fix ε, δ ∈ (0, 1/8) and let N_{δ} be a fixed δ-net in B_{X}. We also fix D ∈ (1, ∞), a Banach space (Y, ∥ · ∥_{Y}), and a mapping f : N_{δ} → Y satisfying

∀ x, y ∈ N_{δ}, \frac{1}{D}∥x − y∥_{X} ⩽ ∥f(x) − f(y)∥_{Y} ⩽ ∥x − y∥_{X}.  (6)

By translating f, we assume without loss of generality that f(N_{δ}) ⊆ 2B_{Y}. Our goal will be to show that provided δ is small enough, namely δ ⩽ e^{−(D/ε)^{Cn}}, there exists an injective linear operator T : X → Y satisfying ∥T ∥ · ∥T^{−1}∥ ⩽ (1 + 12ε)D.

The first step is to construct a mapping F : ℝ^{n} → Y that is a Lipschitz almost-extension of f, i.e., it is Lipschitz and on N_{δ} it takes values that are close to the corresponding values of f. The statement below is a refinement of a result of Bourgain [7]. The proof of Bourgain’s almost extension theorem has been significantly simplified by Begun [4], and our proof of Lemma 2.1 below follows Begun’s argument; see Section 3. Lemma 2.1. If δ < \frac{ε}{4n} then there exists a mapping F : ℝ^{n} → Y that is differentiable almost everywhere on ℝ^{n}, is differentiable everywhere on \frac{1}{2}B_{X}, and has the following properties.

• F is supported on 3B_{X}.

• ∥F (x) − F (y)∥_{Y} ⩽ 6∥x − y∥_{X} for all x, y ∈ ℝ^{n}.

• ∥F (x) − F (y)∥_{Y} ⩽ (1 + ε) ∥x − y∥_{X} for all x, y ∈ \frac{1}{2}B_{X}.

• ∥F (x) − f(x)∥_{Y} ⩽ \frac{9nδ}{ε} for all x ∈ N_{δ}.

In what follows, the volume of a Lebesgue measurable set A ⊆ ℝ^{n} will be denoted vol(A). For t ∈ (0, ∞) the Poisson kernel P_{t} : ℝ^{n} → [0, ∞) is given by

P_{t}(x) = \frac{c_{n}t}{(t^{2} + ∥x∥_{2}^{2})^{\frac{n+1}{2}}} ,

where c_{n} is the normalization factor ensuring that ∫_{ℝ^{n}} P_{t}(x)dx = 1. Thus c_{n} = Γ (\frac{n+1}{2}) /π^{\frac{n+1}{2}} , as computed for example in [23, Sec. X.3]. We will use repeatedly the standard semigroup property P_{t} ∗ P_{s} = P_{t+s}, where as usual f ∗ g(x) = ∫_{ℝ^{n}} f(y)g(y − x)dx for f, g ∈ L_{1}(ℝ^{n}).

Assume from now on that δ < \frac{ε}{4n} and fix a mapping F : ℝ^{n} → Y satisfying the conclusion of Lemma 2.1. We will consider the evolutes of F under the Poisson semigroup, i.e., the functions P_{t}∗F : ℝ^{n} → Y given by P_{t}∗F (x) = ∫_{ℝ^{n}} P_{t}(y−x)F (y)dy. Our goal is to show that there exists t_{0} ∈ (0, ∞) and x ∈ ℝ^{n} such that the derivative T = (P_{t_{0}} ∗F)′(x) is injective and satisfies ∥T ∥ · ∥T^{−1}∥ ⩽ (1 + 10ε)D. Intuitively, one might expect this to happen for every small enough t, since in this case P_{t} ∗ F is close to F, and F itself is close to a bi-Lipschitz map when restricted to the δ-net N_{δ}. In reality, proving the existence of t_{0} requires work; the existence of t_{0} will be proved by contradiction, i.e., we will show that it cannot not exist, without pinpointing a concrete t_{0} for which (P_{t_{0}} ∗ F)′(x) has the desired properties.

Lemma 2.2. Let μ be a Borel probability measure on S_{X}. Fix R, A ∈ (0, ∞) and m ∈ ℕ. Then there exists t ∈ (0, ∞) satisfying

\frac{A}{(R + 1)^{m+1}} ⩽ t ⩽ A,  (7)

such that

∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a}(P_{t}∗F)(x)∥_{Y} dxdμ(a) ⩽ ∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a}(P_{(R+1)t}∗F)(x)∥_{Y} dxdμ(a)+ \frac{6vol(3B_{X})}{m}. (8)

Proof. If (8) fails for all t satisfying (7) then for every k ∈ {0, …, m + 1} we have

∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a} (P_{A(R+1)^{k−m−1}} ∗ F ) (x)∥_{Y} dxdμ(a)

> ∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a} (P_{A(R+1)^{k−m}} ∗ F ) (x)∥_{Y} dxdμ(a) + \frac{6vol(3B_{X})}{m}. (9)

By iterating (9) we get the estimate

∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a} (P_{A(R+1)^{−m−1}} ∗ F ) (x)∥_{Y} dxdμ(a)

> ∫_{S_{X}} ∫_{ℝ^{n}} ∥∂_{a} (P_{A(R+1)} ∗ F ) (x)∥_{Y} dxdμ(a) + \frac{6(m + 1)vol(3B_{X})}{m}. (10)

At the same time, since F is differentiable almost everywhere and 6-Lipschitz, for every a ∈ S_{X} we have ∥∂_{a}F ∥_{Y} ⩽ 6 almost everywhere. Since F is supported on 3B_{X}, it follows that

∫_{ℝ^{n}} ∥∂_{a} (P_{A(R+1)^{−m−1}} ∗ F ) (x)∥_{Y} dx = ∫_{ℝ^{n}} ∥(P_{A(R+1)^{−m−1}} ∗ ∂_{a}F ) (x)∥_{Y} dx

⩽ ∫_{ℝ^{n}} ∫_{ℝ^{n}} P_{A(R+1)^{−m−1}}(x − y)∥∂_{a}F (y)∥_{Y} dxdy = ∫_{3B_{X}} ∥∂_{a}F (y)∥_{Y} dy ⩽ 6vol(3B_{X}). (11)

If we integrate (11) with respect to μ, then since μ is a probability measure we obtain a contradiction to (10) □

In order to apply Lemma 2.2, we will contrast it with the following key statement (proved in Section 4), which asserts that the directional derivatives of P_{t} ∗ F are large after an appropriate averaging.

Lemma 2.3. Assume that t ∈ (0, 1/2], R ∈ (0, ∞) and δ ∈ (0, ε/(4n)) satisfy

δ ⩽ \frac{εt log(7/t)}{2\sqrt{n}} ⩽ \frac{ε^{4}}{6n^{5/2}(80D)^{2}} ,  (12)

and

\frac{720n^{3/2}D^{2} log(7/t)}{ε^{2}} ⩽ R ⩽ \frac{ε}{32t\sqrt{n}}.  (13)

Then for every x ∈ \frac{1}{8}B_{X} and a ∈ S_{X} we have

(∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) ⩾ \frac{1 − ε}{D}.  (14)

We record one more (simpler) fact about the evolutes of F under the Poisson semigroup.

Lemma 2.4. Assume that 0 < t < \frac{ε}{25\sqrt{n}}. Then for every x, y ∈ \frac{1}{4}B_{X} we have

∥P_{t} ∗ F (x) − P_{t} ∗ F (y)∥_{Y} ⩽ (1 + 2ε)∥x − y∥_{X}.

With the above tools at hand, we will now show how to conclude the proof of Theorem 1.1. It will then remain to prove Lemma 2.1 (in Section 3), Lemma 2.3 (Section 4) and Lemma 2.4 (also in Section 4).

Proof of Theorem 1.1. Assume that δ ∈ (0, 1) satisfies

δ ⩽ (\frac{ε}{cD})^{12n(cD/ε)^{n+1}} ,  (15)

where c = 300 (this is an overestimate for the ensuing calculation). Fix an (ε/D)-net F in S_{X} with |F| ⩽ (3D/ε)^{n} (for the existence of nets of this size, see e.g. [1, Lem. 12.3.1]). Let μ be the uniform probability measure on F. Define

A = (\frac{ε}{cD})^{5n} , R = (\frac{cD}{ε})^{4n} − 1, m = ⌊(\frac{cD}{ε})^{n+1}⌋ − 1.  (16)

Apply Lemma 2.2 with the above parameters, obtaining some t ∈ (0, ∞) satisfying

(\frac{ε}{cD})^{12n(cD/ε)^{n+1}} ⩽ t ⩽ (\frac{ε}{cD})^{5n} ,  (17)

such that

∑_{a∈F} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x)∥_{Y} dx ⩽ ∑_{a∈F} ∫_{ℝ^{n}} ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} dx + \frac{6|F|vol(3B_{X})}{m}. (18)

One checks that for δ satisfying (15), R as in (16), and any t satisfying (17), inequalities (12) and (13) are satisfied. Thus the conclusion (14) of Lemma 2.3 holds true for all a ∈ S_{X} and x ∈ \frac{1}{8}B_{X}.

Note that by convexity we have for every a ∈ S_{X} and almost every x ∈ ℝ^{n},

∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} = ∥ (P_{Rt} ∗ (∂_{a}(P_{t} ∗ F))) (x)∥_{Y} ⩽ (∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x).

Thus ∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt} − ∥∂_{a}(P_{(R+1)t} ∗ F)∥_{Y} ⩾ 0, so we may use Markov’s inequality as follows.

vol (\{x ∈ \frac{1}{8}B_{X} : (∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) − ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} ⩾ \frac{ε}{D}\})
⩽ \frac{D}{ε} (∫_{ℝ^{n}} ((∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) − ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} ) dx)
= \frac{D}{ε} (∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x)∥_{Y} dx − ∫_{ℝ^{n}} ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} dx) .  (19)

Hence,

vol (\{x ∈ \frac{1}{8}B_{X} : ∃a ∈ F, (∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) − ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} ⩾ \frac{ε}{D}\})

⩽^{(19)} \frac{D}{ε} (∑_{a∈F} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x)∥_{Y} dx − ∑_{a∈F} ∫_{ℝ^{n}} ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} dx)

⩽^{(18)} \frac{D}{ε} · \frac{6|F|vol(3B_{X})}{m}
⩽^{(16)} \frac{12D}{ε} (\frac{3D}{ε})^{n} (\frac{ε}{cD})^{n+1} (24)^{n}vol (\frac{1}{8}B_{X})
= \frac{6^{n}}{25^{n+1}} vol (\frac{1}{8}B_{X}) < vol (\frac{1}{8}B_{X}) .

Consequently, there exists x ∈ \frac{1}{8}B_{X} satisfying

∀a ∈ F, (∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) − ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} < \frac{ε}{D}.  (20)

But we already argued that (14) holds as well, so (20) implies that

∀a ∈ F, ∥∂_{a}(P_{(R+1)t} ∗ F)(x)∥_{Y} ⩾ \frac{1 − 2ε}{D}.  (21)

Note that by (16) and (17) we have (R + 1)t ⩽ (ε/(cD))^{n} < ε/ (25\sqrt{n}). Hence, if we define T = (P_{(R+1)t}∗F)′(x) then by Lemma 2.4 we have ∥T ∥ ⩽ 1+2ε. By (21), ∥T a∥_{Y} ⩾ (1−2ε)/D for all a ∈ F. For z ∈ S_{X} take a ∈ F such that ∥z − a∥_{X} ⩽ ε/D. Then,

∥T z∥ ⩾ ∥T a∥ − ∥T ∥ · ∥z − a∥_{X} ⩾ \frac{1 − 2ε}{D} − (1 + 2ε)\frac{ε}{D} ⩾ \frac{1 − 4ε}{D}.

Hence T is invertible and ∥T^{−1}∥ ⩽ D/(1−4ε). Thus ∥T ∥·∥T^{−1}∥ ⩽ \frac{1+2ε}{1−4ε}D ⩽ (1+12ε)D. □

3. Proof of Lemma 2.1

We will use the following lemma of Begun [4].

Lemma 3.1. Let K ⊆ ℝ^{n} be a convex set and fix τ, η, L ∈ (0, ∞). Assume that we are given a mapping h : K + τB_{X} → Y satisfying ∥h(x) − h(y)∥_{Y} ⩽ L (∥x − y∥_{X} + η) for all x, y ∈ K + τB_{X}. Define H : K → Y by

H(x) = \frac{1}{τ^{n}vol(B_{X})} ∫_{τB_{X}} h(x − y)dy.

Then ∥H(x) − H(y)∥_{Y} ⩽ L (1 + \frac{nη}{2τ}) ∥x − y∥_{X} for all x, y ∈ K.

We refer to [4] for an elegant proof of Lemma 3.1. The deduction of Lemma 2.1 from Lemma 3.1 is via the following simple partition of unity argument. Let {ϕ_{p} : ℝ^{n} → [0, 1]}_{p∈N_{δ}} be a family of smooth functions satisfying ∑_{p∈N_{δ}} ϕ_{p}(x) = 1 for all x ∈ B_{X} and ϕ_{p}(x) = 0 for all (p, x) ∈ N_{δ} × ℝ^{n} with ∥x − p∥_{X} ⩾ 2δ. A standard construction of such functions can be obtained by taking a smooth ψ : ℝ^{n} → [0, 1] which is equals 1 on B_{X} and vanishes outside 2B_{X}, and defining ψ_{p}(x) = ψ((x − p)/δ) for (p, x) ∈ N_{δ} × ℝ^{n}. If we then write N_{δ} = {p_{1}, p_{2}, …, p_{N}}, define ϕ_{p_{1}} = ψ_{p_{1}} and ϕ_{p_{j}} = ψ_{p_{j}} ∏_{i=1}^{j−1}(1 − ψ_{p_{i}}) for j ∈ {2, …, N}. Then ∑_{p∈N_{δ}} ϕ_{p} = 1 − ∏_{p∈N_{δ}}(1 − ψ_{p}) = 1 on B_{X} since every x ∈ B_{X} satisfies ∥x − p∥_{X} ⩽ δ for some p ∈ N_{δ}.

Now define g : B_{X} → Y by g(x) = ∑_{p∈N_{δ}} ϕ_{p}(x)f(p). Setting β(t) = max{0, 2 − t} for t ∈ [0, ∞), consider the mapping h : ℝ^{n} → Y given by

h(x) = \{ \begin{matrix}g(x) & if x ∈ B_{X}, \\ β(∥x∥_{X})g (x/∥x∥_{X}) & if x ∈ ℝ^{n} ∖ B_{X}. \end{matrix}  (22)

Observe that if x, y ∈ B_{X} then

h(x) − h(y) = g(x) − g(y) = ∑_{p∈N_{δ}∩(x+2δB_{X})} ϕ_{p}(x)f(p) − ∑_{q∈N_{δ}∩(y+2δB_{X})} ϕ_{q}(y)f(q)

= ∑_{\begin{matrix}p∈N_{δ}∩(x+2δB_{X}) \\ q∈N_{δ}∩(y+2δB_{X}) \end{matrix}} ϕ_{p}(x)ϕ_{q}(y) [f(p) − f(q)] .

This identity implies that

∀x, y ∈ B_{X}, ∥h(x) − h(y)∥_{Y} ⩽ ∥x − y∥_{X} + 4δ  (23)

If x ∈ B_{X} and y ∈ ℝ^{n} ∖ B_{X} then using f(N_{δ}) ⊆ 2B_{Y} and the fact that β is 1-Lipschitz,

∥h(x) − h(y)∥_{Y} ⩽ ∥g(x) − g (\frac{y}{∥y∥_{X}} )∥_{Y} + (1 − β(∥y∥_{X})) ∥g (\frac{y}{∥y∥_{X}} )∥_{Y}

⩽^{(23)} ∥x − \frac{y}{∥y∥_{X}} ∥_{X} + 4δ + (∥y∥_{X} − 1) sup_{p∈N_{δ}} ∥f(p)∥_{Y} ⩽ ∥x − y∥_{X} + 3(∥y∥_{X} − 1) + 4δ.

Since ∥y∥_{X} − 1 ⩽ ∥x − y∥_{X} + ∥x∥_{X} − 1 ⩽ ∥x − y∥_{X}, it follows that

∀x ∈ B_{X}, ∀y ∈ ℝ^{n} ∖ B_{X}, ∥h(x) − h(y)∥_{Y} ⩽ 4(∥x − y∥_{X} + δ).  (24)

If x, y ∈ ℝ^{n} ∖ B_{X} then

∥h(x)−h(y)∥_{Y} ⩽ ∥g (\frac{x}{∥x∥_{X}} ) − g (\frac{y}{∥y∥_{X}} )∥_{Y} β(∥x∥)+∥g (\frac{y}{∥y∥_{X}} )∥_{Y} |β(∥x∥_{X}) − β(∥y∥_{X})|

⩽^{(23)} ∥\frac{x}{∥x∥_{X}} − \frac{y}{∥y∥_{X}} ∥_{X} + 4δ + 2 ∥x − y∥_{X} ⩽ 4(∥x − y∥_{X} + δ). (25)

Set τ = 2nδ/ε ∈ (0, 1/2) and define for x ∈ ℝ^{n},

F (x) = \frac{1}{τ^{n}vol(B_{X})} ∫_{τB_{X}} h(x − y)dy.  (26)

It follows from the definition (22) that h is differentiable almost everywhere on ℝ^{n}. Since h is differentiable on B_{X} ∖ S_{X} and τ ∈ (0, 1/2), it follows from (26) that F is differentiable almost everywhere on ℝ^{n}, and is differentiable everywhere on \frac{1}{2}B_{X}. Clearly F is supported on (2 + τ)B_{X} ⊆ 3B_{X}, i.e., the first assertion of Lemma 2.1 holds. Due to (23), (24), (25), an application of Lemma 3.1 with K = ℝ^{n}, L = 4 and η = δ shows that F is 4 (1 + ε/2)- Lipschitz on ℝ^{n}, proving the second assertion of Lemma 2.1. Due to (23), an application of Lemma 3.1 with K = (1−τ)B_{X} shows that F is (1 + ε)-Lipschitz on (1−τ)B_{X} ⊇ \frac{1}{2}B_{X}. This establishes the third assertion of Lemma 2.1. To prove the fourth assertion of Lemma 2.1, fix x ∈ N_{δ}. Then,

∥F (x) − h(x)∥_{Y} ⩽ \frac{1}{τ^{n}vol(B_{X})} ∫_{τB_{X}} ∥h(x − y) − h(x)∥_{Y} dy ⩽^{(23)∧(24)} 4(τ + δ). (27)

Also,

∥h(x) − f(x)∥_{Y} ⩽ ∑_{p∈N_{δ}} ∥f(x) − f(p)∥_{Y} ϕ_{p}(x) ⩽ max_{p∈N_{δ}∩(x+2δB_{X})} ∥f(x) − f(p)∥_{Y} ⩽ 2δ. (28)

Recalling that τ = 2nδ/ε, the fourth assertion on Lemma 2.1 follows from (27) and (28). □

4. Proof of Lemma 2.4 and Lemma 2.3

We will need the following standard estimate, which holds for all r, t ∈ (0, ∞).

∫_{ℝ^{n}∖(rB_{X})} P_{t}(x)dx ⩽ \frac{t\sqrt{n}}{r}.  (29)

To check (29), letting s_{n−1} denote the surface area of the unit Euclidean sphere S^{n−1}, and recalling that P_{t}(x) = t^{−n}P_{1}(x/t), we have

∫_{∥x∥_{X}⩾r} P_{t}(x)dx ⩽^{(5)} ∫_{∥x∥_{2}⩾r} P_{t}(x)dx = ∫_{∥x∥_{2}⩾r/t} P_{1}(x)dx

= c_{n}s_{n−1} ∫_{r/t}^{∞} \frac{s^{n−1}}{(1 + s^{2})^{\frac{n+1}{2}}} ds ⩽ c_{n}s_{n−1} ∫_{r/t}^{∞} \frac{ds}{s^{2}} = \frac{c_{n}s_{n−1}t}{r}.

It remains to recall that c_{n} = Γ (\frac{n+1}{2}) /π^{\frac{n+1}{2}} and s_{n−1} = nπ^{\frac{n}{2}} /Γ (\frac{n}{2} + 1) (see e.g. [3, Sec. 1]), and, using Stirling’s formula, to obtain the estimate c_{n}s_{n−1} ⩽ \sqrt{2n/π}.

Another standard estimate that we will use is that for every y ∈ ℝ^{n} we have

∫_{ℝ^{n}} |P_{t}(x) − P_{t}(x + y)| dx ⩽ \frac{\sqrt{n}∥y∥_{2}}{t} .  (30)

Since P_{t}(x) = t^{−n}P_{1}(x/t) it suffices to check (30) when t = 1. Now,

∫_{ℝ^{n}} |P_{1}(x) − P_{1}(x + y)| dx = ∫_{ℝ^{n}} |∫_{0}^{1}⟨∇P_{1}(x + sy), y⟩ds| dx ⩽ ∥y∥_{2} ∫_{ℝ^{n}} ∥∇P_{1}(x)∥_{2} dx

= (n+1)c_{n}∥y∥_{2} ∫_{ℝ^{n}} \frac{∥x∥_{2}}{(1 + ∥x∥_{2}^{2})^{\frac{n+3}{2}}} dx = (n+1)c_{n}s_{n−1}∥y∥_{2} ∫_{0}^{∞} \frac{r^{n}}{(1 + r^{2})^{\frac{n+3}{2}}} dr = c_{n}s_{n−1}∥y∥_{2},

where we used the fact that the derivative of r^{n+1}/(1 + r^{2})^{\frac{n+1}{2}} equals (n + 1)r^{n}/(1 + r^{2})^{\frac{n+3}{2}} . The required estimate (30) now follows from Stirling’s formula.

Proof of Lemma 2.4. We have,

∥P_{t} ∗ F (x) − P_{t} ∗ F (y)∥_{Y} ⩽ ∫_{ℝ^{n}} P_{t}(z)∥F (x − z) − F (y − z)∥_{Y} dz

⩽^{(∗)} ((1 + ε) ∫_{\frac{1}{4} B_{X}} P_{t}(z)dz + 6 ∫_{ℝ^{n}∖(\frac{1}{4} B_{X})} P_{t}(z)dz) ∥x − y∥_{X}

⩽^{(29)} (1 + ε + 24t\sqrt{n}) ∥x − y∥_{X},

where in (∗) we used the fact that F is (1 + ε)-Lipschitz on \frac{1}{2}B_{X} and 6-Lipschitz on ℝ^{n}. □

Lemma 4.1. For every t ∈ (0, 1/2] and every x ∈ B_{X} we have

∥P_{t} ∗ F (x) − F (x)∥_{Y} ⩽ 8\sqrt{n}t log (\frac{7}{t}) .

Proof. Since F is supported on 3B_{X},

∥P_{t} ∗ F (x) − F (x)∥_{Y}

⩽ ∫_{x+3B_{X}} ∥F (y − x) − F (x)∥_{Y} P_{t}(y)dy + ∥F (x)∥_{Y} ∫_{y∈ℝ^{n}∖(x+3B_{X})} P_{t}(y)dy. (31)

Since F is 6-Lipschitz and it vanishes outside 3B_{X}, we have ∥F (x)∥_{Y} ⩽ 18. Moreover, if ∥y − x∥_{X} ⩾ 3 then ∥y∥_{X} ⩾ ∥x − y∥_{X} − ∥x∥_{X} ⩾ 2, and therefore

∥F (x)∥_{Y} ∫_{y∈ℝ^{n}∖(x+3B_{X})} P_{t}(y)dy ⩽ 18 ∫_{ℝ^{n}∖(2B_{X})} P_{t}(y)dy ⩽^{(29)} 9t\sqrt{n}.  (32)

To bound the first term in the right hand side of (31) note that if ∥y − x∥_{X} ⩽ 3 then ∥y∥_{2} ⩽ \sqrt{n}∥y∥_{X} ⩽ 4\sqrt{n}. Moreover, ∥F (y − x) − F (x)∥_{X} ⩽ 6∥y∥_{X} ⩽ 6∥y∥_{2}. Hence,

∫_{x+3B_{X}} ∥F (y − x) − F (x)∥_{Y} P_{t}(y)dy ⩽ 6 ∫_{∥y∥_{2}⩽4\sqrt{n}} ∥y∥_{2}P_{t}(y)dy

= 6t ∫_{∥y∥_{2}⩽ \frac{4\sqrt{n}}{t}} ∥y∥_{2}P_{1}(y)dy = 6tc_{n}s_{n−1} ∫0^{\frac{4\sqrt{n}}{t}} \frac{s^{n}}{(1 + s^{2})^{\frac{n+1}{2}}} ds (33)

Direct differentiation shows that the maximum of s^{n}/(1 + s^{2})^{\frac{n+1}{2}} is attained when s = \sqrt{n}, and therefore s^{n}/(1 + s^{2})^{\frac{n+1}{2}} ⩽ min\{1/\sqrt{en}, 1/s\} for all s ∈ (0, ∞). Hence,

∫0^{\frac{4\sqrt{n}}{t}} \frac{s^{n}}{(1 + s^{2})^{\frac{n+1}{2}}} ds ⩽ 1 + ∫\sqrt{en}^{\frac{4\sqrt{n}}{t}} \frac{ds}{s} = 1 + log (\frac{4}{t\sqrt{e}}) .  (34)

The required result now follows from substituting (32), (33), (34) into (31), and using the fact that t ⩽ 1/2 and c_{n}s_{n−1} ⩽ \sqrt{n}. □

Proof of Lemma 2.3. Define

Θ = \frac{100D\sqrt{n}t log(7/t)}{ε}.  (35)

For w, y ∈ \frac{1}{2}B_{X} let p, q ∈ N_{δ} ∩ (\frac{1}{2}B_{X}) satisfy ∥p − w∥_{X}, ∥q − y∥_{Y} ⩽ 2δ. Assume that ∥w−y∥_{X} ⩾ Θ. Using the third and fourth assertions of Lemma 2.1, together with Lemma 4.1, we have

∥(P_{t} ∗ F)(w) − (P_{t} ∗ F)(y)∥_{Y} ⩾ ∥f(p) − f(q)∥_{Y} − ∥F (p) − f(p)∥_{Y} − ∥F (q) − f(q)∥_{Y} −∥F (w) − F (p)∥_{Y} − ∥F (y) − F (q)∥_{Y} − ∥(P_{t} ∗ F)(w) − F (w)∥_{Y} − ∥(P_{t} ∗ F)(y) − F (y)∥_{Y}

⩾^{(6)} \frac{∥p − q∥_{Y}}{D} − \frac{18nδ}{ε} − 4(1 + ε)δ − 16\sqrt{n}t log (\frac{7}{t})
⩾ \frac{∥w − y∥_{X} − 4δ}{D} − \frac{18nδ}{ε} − 4(1 + ε)δ − 16\sqrt{n}t log (\frac{7}{t})
⩾ \frac{1 − ε/3}{D}∥w − y∥_{X},  (36)

where (36) uses the assumptions ∥w − y∥_{X} ⩾ Θ and (12).

Note that the second inequality in (12) implies that Θ ⩽ 1/4. Therefore, since ∥a∥_{X} = 1 it follows from (36) that for every z ∈ \frac{1}{4}B_{X},

\frac{1 − ε/3}{D}Θ ⩽ ∥P_{t} ∗ F (z + Θa) − P_{t} ∗ F (z)∥_{Y}

= ∥∫_{0}^{Θ} ∂_{a}(P_{t} ∗ F)(z + sa)ds∥_{Y} ⩽ ∫_{0}^{Θ} ∥∂_{a}(P_{t} ∗ F)(z + sa)∥_{Y} ds. (37)

Since in the statement of Lemma 2.3 we are assuming that ∥x∥_{X} ⩽ 1/8,

\frac{1}{Θ} ∫_{0}^{Θ} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x + sa − y)∥_{Y} P_{Rt}(y)dyds ⩾^{(37)} \frac{1 − ε/3}{D} ∫_{\frac{1}{8} B_{X}} P_{Rt}(y)dy

⩾^{(29)} \frac{1 − ε/3}{D} (1 − 8Rt\sqrt{n}) ⩾^{(13)} \frac{(1 − ε/3)(1 − ε/4)}{D} ⩾ \frac{1 − 7ε/12}{D}. (38)

Since F is 6-Lipschitz, ∥∂_{a}F ∥_{Y} ⩽ 6 almost everywhere, and therefore ∥∂_{a}(P_{t} ∗ F)∥_{Y} ⩽ 6 almost everywhere. Hence,

∫_{0}^{Θ} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x − y)∥_{Y} (P_{Rt}(y + sa) − P_{Rt}(y)) dyds

⩽ 6 ∫_{0}^{Θ} ∫_{ℝ^{n}} |P_{Rt}(y + sa) − P_{Rt}(y)| dyds ⩽^{(30)} \frac{6\sqrt{n}∥a∥_{2}}{Rt} · \frac{Θ^{2}}{2} ⩽^{(5)} \frac{3nΘ^{2}}{Rt} ⩽^{(13)∧(35)} \frac{5εΘ}{12D}. (39)

We can now conclude the proof of Lemma 2.3 as follows.

(∥∂_{a}(P_{t} ∗ F)∥_{Y} ∗ P_{Rt}) (x) = \frac{1}{Θ} ∫_{0}^{Θ} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x + sa − y)∥_{Y} P_{Rt}(y)dyds

− \frac{1}{Θ} ∫_{0}^{Θ} ∫_{ℝ^{n}} ∥∂_{a}(P_{t} ∗ F)(x − y)∥_{Y} (P_{Rt}(y + sa) − P_{Rt}(y)) dyds ⩾^{(38)∧(39)} \frac{1 − ε}{D}. □

5. Proof of Theorem 1.2

The following general lemma will be used later; compare to [17, Prop. 1].

Lemma 5.1. Let (V, ∥ · ∥_{V}) be a Banach space and U = (ℝ^{n}, ∥ · ∥_{U}) be an n-dimensional Banach space. Assume that g : B_{U} → V is continuous and everywhere differentiable on the interior of B_{U}. Then

∥\frac{1}{vol(B_{U})} ∫_{B_{U}} g′(u)du∥_{U→V} ⩽ n∥g∥_{L_{∞}(S_{U})}.  (40)

Proof. Fix y ∈ ℝ^{n} with ∥y∥_{2} = 1. Let P_{y^{⊥}} : ℝ^{n} → y^{⊥} denote the orthogonal projection onto the hyperplane y^{⊥}. For every u ∈ P_{y^{⊥}}(B_{U}) there are unique a_{u}, b_{u} ∈ ℝ satisfying a_{u} ⩽ b_{u} and ∥u + a_{u}y∥_{U} = ∥u + b_{u}y∥_{U} = 1. Hence,

∥\frac{1}{vol(B_{U})} ∫_{B_{U}} g′(u)(y)du∥_{V} = ∥\frac{1}{vol(B_{U})} ∫_{P_{y^{⊥}}(B_{U})} ∫_{a_{u}}^{b_{u}} \frac{d}{ds}g(u + sy)dsdu∥_{V}

= ∥\frac{1}{vol(B_{U})} ∫_{P_{y^{⊥}}(B_{U})} (g(u + b_{u}y) − g(u + a_{u}y)) du∥_{V} ⩽ 2∥g∥_{L_{∞}(S_{U})} · \frac{vol_{n−1}(P_{y^{⊥}}(B_{U}))}{vol(B_{U})}.

Therefore, in order to prove (40) it suffices to show that vol_{n−1}(P_{y^{⊥}}(B_{U})) ⩽ n∥y∥_{U}vol(B_{U})/2. This is the same as vol(K) ⩽ vol(B_{U}), where K is the convex hull of P_{y^{⊥}}(B_{U}) ∪ {±y/∥y∥_{U}}, i.e., K is the union of the two cones with base P_{y^{⊥}}(B_{U}) and cusp ±y/∥y∥_{U}. For u ∈ P_{y^{⊥}}(B_{U}) let c_{u} ∈ [1, ∞) be the largest c ∈ [1, ∞) for which cu ∈ P_{y^{⊥}}(B_{U}). Then

K = ⋃_{u∈P_{y^{⊥}}(B_{U})} (u + [−\frac{c_{u} − 1}{c_{u}∥y∥_{U}} , \frac{c_{u} − 1}{c_{u}∥y∥_{U}} ] y) .  (41)

Recalling the definition of a_{u} above, by the definition of c_{u} we have c_{u}u+a_{c_{u}u}y ∈ S_{U}. Hence, since ±y/∥y∥_{U} ∈ B_{U}, by convexity we know that the points

\frac{1}{c_{u}} (c_{u}u + a_{c_{u}u}y) + (1 − \frac{1}{c_{u}} ) \frac{y}{∥y∥_{U}}  and  \frac{1}{c_{u}} (c_{u}u + a_{c_{u}u}y) − (1 − \frac{1}{c_{u}} ) \frac{y}{∥y∥_{U}}

are both in B_{U}. Consequently, by convexity again, we have that

⋃_{u∈P_{y^{⊥}}(B_{U})} (u + [\frac{a_{c_{u}u}}{c_{u}} − \frac{c_{u} − 1}{c_{u}∥y∥_{U}} , \frac{a_{c_{u}u}}{c_{u}} + \frac{c_{u} − 1}{c_{u}∥y∥_{U}} ] y) ⊆ B_{U}.  (42)

Since, by Fubini, the volume of the left hand side of (42) equals the volume of the right hand side of (41), we conclude the desired estimate vol(K) ⩽ vol(B_{U}). □

Fix ε, δ ∈ (0, 1/2) and let N_{δ} be a δ-net in B_{X} ⊆ ℝ^{n}. Fixing also D ∈ (1, ∞), assume that f : N_{δ} → Y satisfies ∥x − y∥_{X}/D ⩽ ∥f(x) − f(y)∥_{Y} ⩽ ∥x − y∥_{X} for all x, y ∈ N_{δ}. Define Z = span (f(N_{δ})). Thus Z is a finite dimensional subspace of Y. Assume that

δ ⩽ \frac{ε^{2}}{30n^{2}D}.  (43)

Since consequently δ < ε/(4n), there exists F : X → Z that is differentiable everywhere on \frac{1}{2}B_{X} and satisfies the conclusion of Lemma 2.1. Let ν be the normalized Lebesgue measure on \frac{1}{2}B_{X} and define a linear operator T : X → L_{∞}(ν, Z) by

(T y)(x) = F′(x)(y).  (44)

Since F is (1 + ε)-Lipschitz on \frac{1}{2}B_{X} we have the operator norm bound

∥T ∥_{X→L_{∞}(ν,Z)} ⩽ 1 + ε.

Theorem 1.2 will therefore be proven once we show that for all y ∈ X we have

\frac{1 − ε}{D}∥y∥_{X} ⩽ ∥T y∥_{L_{1}(ν,Z)} = \frac{1}{vol (\frac{1}{2}B_{X})} ∫_{\frac{1}{2} B_{X}} ∥F′(x)(y)∥_{Y} dx.  (45)

To prove (45), let J : X → ℓ_{∞} be a linear isometric embedding. By the nonlinear Hahn-Banach theorem (see e.g. [5, Ch. 1]) there exists a mapping G : Z → ℓ_{∞} satisfying

∀x ∈ N_{δ}, G(f(x)) = J(x)  (46)

and G is D-Lipschitz; we are extending here the mapping J ∘(f^{−1}|_{f(N_{δ})}) : f(N_{δ}) → ℓ_{∞} while preserving its Lipschitz constant. By convolving G with a smooth bump function whose integral on Y equals 1 and whose support has a small diameter, we can find H : Z → ℓ_{∞} with Lipschitz constant at most D and satisfying

∀z ∈ F (B_{X}), ∥H(z) − G(z)∥_{ℓ_{∞}} ⩽ \frac{nDδ}{ε} .  (47)

Define a linear operator S : L_{1}(ν, Z) → ℓ_{∞} by setting for h ∈ L_{1}(ν, Z),

Sh = ∫_{\frac{1}{2} B_{X}} H′(F (x))(h(x))dν(x).  (48)

Since H is D-Lipschitz and ν is a probability measure, we have the operator norm bound

∥S∥_{L_{1}(ν,Z)→ℓ_{∞}} ⩽ D.  (49)

By the chain rule, for every y ∈ X we have

ST (y) =^{(44)∧(48)} ∫_{\frac{1}{2} B_{X}} H′(F (x))(F′(x)(y))dν(x) = ∫_{\frac{1}{2} B_{X}} (H ∘ F)′ (x)(y)dν(x). (50)

Note that if y ∈ N_{δ} then

∥H(F (y)) − Jy∥_{ℓ_{∞}} =^{(46)} ∥H(F (y)) − G(f(y))∥_{ℓ_{∞}}
⩽ ∥H(F (y)) − G(F (y))∥_{ℓ_{∞}} + ∥G(F (y)) − G(f(y))∥_{ℓ_{∞}}
⩽^{(47)} \frac{nDδ}{ε} + D∥F (y) − f(y)∥_{Y}
⩽ \frac{nDδ}{ε} + D · \frac{9nδ}{ε} ⩽ \frac{10nDδ}{ε} ,  (51)

where in the penultimate inequality in (51) we used the fact that ∥F (y) − f(y)∥_{Y} ⩽ 9nδ/ε for all y ∈ N_{δ}, due to Lemma 2.1. If x ∈ \frac{1}{2}B_{X} then there exists y ∈ N_{δ} ∩ (\frac{1}{2}B_{X}) satisfying ∥x − y∥_{X} ⩽ 2δ. Using the fact that H ∘ F is (1 + ε)D-Lipschitz on \frac{1}{2}B_{X}, it follows that

∥H(F (x)) − Jx∥_{ℓ_{∞}} ⩽ ∥H(F (y)) − Jy∥_{ℓ_{∞}} + ∥H(F (x)) − H(F (y))∥_{ℓ_{∞}} + ∥Jx − Jy∥_{ℓ_{∞}}

⩽^{(51)} \frac{10nDδ}{ε} + (1 + ε)D · 2δ + 2δ ⩽ \frac{15nDδ}{ε} . (52)

By Lemma 5.1 with V = ℓ_{∞}, ∥ · ∥_{U} = 2∥ · ∥_{X} and g = H ∘ F − J, it follows from (52) that

∥ST − J∥_{X→ℓ_{∞}} =^{(50)} ∥∫_{\frac{1}{2} B_{X}}(H ∘ F)′(x)dν(x) − J∥_{X→ℓ_{∞}} ⩽ \frac{30n^{2}Dδ}{ε} ⩽^{(43)} ε.  (53)

It follows that for all y ∈ X,

D∥T y∥_{L_{1}(ν,Z)} ⩾^{(49)} ∥ST y∥_{ℓ_{∞}} ⩾ ∥Jy∥_{ℓ_{∞}} − ∥ST − J∥_{X→ℓ_{∞}} · ∥y∥_{X} ⩾^{(53)} (1 − ε)∥y∥_{X}.

This concludes the proof of (45), and hence the proof of Theorem 1.2 is complete. □

References

[1] F. Albiac and N. J. Kalton. Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics. Springer, New York, 2006.

[2] T. Austin, A. Naor, and R. Tessera. Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces. Preprint available at http://arxiv.org/abs/1007.4238. To appear in Groups Geom. Dyn., 2010.

[3] K. Ball. An elementary introduction to modern convex geometry. In Flavors of geometry, volume 31 of Math. Sci. Res. Inst. Publ., pages 1–58. Cambridge Univ. Press, Cambridge, 1997.

[4] B. Begun. A remark on almost extensions of Lipschitz functions. Israel J. Math., 109:151–155, 1999.

[5] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[6] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222– 230, 1986.

[7] J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987.

[8] J. Cheeger and B. Kleiner. Differentiating maps into L^{1}, and the geometry of BV functions. Ann. of Math. (2), 171(2):1347–1385, 2010.

[9] J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisenberg group to L_{1}. Acta Math., 207(2):291–373, 2011.

[10] H. Corson and V. Klee. Topological classification of convex sets. In Proc. Sympos. Pure Math., Vol. VII, pages 37–51. Amer. Math. Soc., Providence, R.I., 1963.

[11] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

[12] A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123–160. Jerusalem Academic Press, Jerusalem, 1961.

[13] S. Heinrich. Ultraproducts in Banach space theory. J. Reine Angew. Math., 313:72–104, 1980.

[14] S. Heinrich and P. Mankiewicz. Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces. Studia Math., 73(3):225–251, 1982.

[15] T. Hytönen, S. Li, and A. Naor. Quantitative affine approximation for UMD targets. Preprint, 2011.

[16] F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, pages 187–204. Interscience Publishers Inc., 1948.

[17] W. B. Johnson, B. Maurey, and G. Schechtman. Non-linear factorization of linear operators. Bull. Lond. Math. Soc., 41(4):663–668, 2009.

[18] S. Li and A. Naor. Discretization and affine approximation in high dimensions. Preprint available at

http://arxiv.org/abs/1202.2567, 2011.

[19] J. Lindenstrauss and H. P. Rosenthal. The L_{p} spaces. Israel J. Math., 7:325–349, 1969.

[20] A. Naor and G. Schechtman. Planar earthmover is not in L_{1}. SIAM J. Comput., 37(3):804–826 (electronic), 2007.

[21] P. Pansu. Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1):1–60, 1989.

[22] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14(2):237–244, 1976.

[23] A. Torchinsky. Real-variable methods in harmonic analysis, volume 123 of Pure and Applied Mathematics. Academic Press Inc., Orlando, FL, 1986.

Institut de Mathématiques de Jussieu, Université Paris VI

E-mail address: giladi@math.jussieu.fr

Courant Institute, New York University

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

Department of Mathematics, Weizmann Institute of Science

E-mail address: gideon@weizmann.ac.il