DISCRETIZATION AND AFFINE APPROXIMATION IN HIGH DIMENSIONS

SEAN LI AND ASSAF NAOR

Abstract. Lower estimates are obtained for the macroscopic scale of affine approximability of vector-valued Lipschitz functions on finite dimensional normed spaces, completing the work of Bates, Johnson, Lindenstrauss, Preiss and Schechtman. This yields a new approach to Bourgain’s discretization theorem for superreflexive targets.

1. Introduction

Let X, Y be Banach spaces with (closed) unit balls B_{X}, B_{Y}, respectively. For ε ∈ (0, 1) define r^{X→Y} (ε) to be the supremum over those r ∈ (0, 1] for which every Lipschitz function f : B_{X} → Y admits y ∈ X and ρ ∈ [r, ∞) such that y + ρB_{X} ⊆ B_{X}, and there exists an affine mapping A : X → Y satisfying

sup_{z∈y+ρB_{X}} \frac{∥f(z) − A(z)∥}{ρ} ⩽ ε∥f∥_{Lip},  (1)

where ∥f∥_{Lip} is the Lipschitz constant of f. If no such r ∈ (0, 1] exists then set r^{X→Y} (ε) = 0. We call r^{X→Y} (·) the modulus of affine approximability corresponding to X, Y.

The assertion r^{X→Y} (ε) ⩾ r means that every Y -valued 1-Lipschitz function on the unit ball of X is ε-close (after appropriate normalization) to an affine function on some sub-ball of radius at least r. Thus, while a differentiation statement corresponds to an assertion about the infinitesimal regularity of a function, bounding r^{X→Y} (ε) from below corresponds to proving a quantitative differentiation theorem about the regularity of Lipschitz functions on a macroscopic scale. This statement isn’t quite precise, since there is no requirement of the affine mapping A in (1) to have any relation to the derivative of f at y, but it turns out that for interesting applications it suffices (and necessary) to allow for an arbitrary affine approximation of f.

Bates, Johnson, Lindenstrauss, Preiss and Schechtman introduced the above affine approximability problem in [2], where it was shown to have applications to the theory of nonlinear quotient mappings. Following [2] we say that the space of Lipschitz mappings

Lip(X, Y) =^{def} {f : X → Y : ∥f∥_{Lip} < ∞}

has the Uniform Approximation by Affine Property (UAAP) if r^{X→Y} (ε) > 0 for all ε ∈ (0, 1). A beautiful theorem of [2] asserts that Lip(X, Y) has the UAAP if and only if one of the spaces {X, Y } is finite dimensional, and the other space is superreflexive. Recall that a Banach space Z is superreflexive if any Banach space that is finitely representable in Z is reflexive; equivalently all the ultrapowers of Z are reflexive^{1}. Due to deep works of James [17, 18], Enflo [10] and Pisier [22], we know that Z is superreflexive if and only if it admits an equivalent norm || · || for which there exist p ∈ [2, ∞) and K ∈ [1, ∞) such that

S. L. was supported by NSF grant CCF-0832795. A. N. was supported by NSF grant CCF-0832795, BSF grant 2010021, and the Packard Foundation. Some of this work was completed when both authors were in residence at the MSRI Quantitative Geometry program.

∀ x, y ∈ Z, 2∥x∥^{p} + \frac{2}{K^{p}} ∥y∥^{p} ⩽ ∥x + y∥^{p} + ∥x − y∥^{p}.  (2)

A norm that satisfies (2) is said to be uniformly convex of power type p; readers who are not familiar with the theory of superreflexivity can take the above renorming statement as the definition of superreflexivity. For concreteness, we recall [12, 1] that for q ∈ (1, ∞) the usual norm on an L_{q}(μ) space satisfies (2) with p = max\{q, 2\} and K = max\{1/\sqrt{q − 1}, 1\}.

Assume from now on that n = dim X < ∞ and Y is superreflexive. The theorem of Bates, Johnson, Lindenstrauss, Preiss and Schechtman says that r^{X→Y} (ε), r^{Y →X}(ε) > 0 for every ε ∈ (0, 1). The proof in [2] of r^{Y →X}(ε) > 0 is effective, yielding a concrete lower bound on r^{Y →X}(ε). This lower bound is quite small: a O(n)-fold iterated exponential of −1/ε and geometric parameters that measure the degree to which Y is superreflexive. We leave the investigation of the true asymptotic behavior of r^{Y →X}(ε) as an interesting open problem.

Our main purpose here is to obtain a concrete lower bound on r^{X→Y} (ε). While we are partly motivated by an application of such bounds to Bourgain’s discretization problem, as will be described in Section 1.1, our main motivation is that the proof in [2] of the estimate r^{X→Y} (ε) > 0 proceeds by contradiction using an ultrapower argument, and as such it does not yield any concrete quantitative information on r^{X→Y} (ε).

We briefly recall the argument of [2]. The contrapositive assumption r^{X→Y} (ε) = 0 means that for every k ∈ ℕ there is a 1-Lipschitz function f_{k} : B_{X} → Y with f_{k}(0) = 0 such that for all balls y + ρB_{X} ⊆ B_{X} with ρ ⩾ 1/k and for all affine mappings A : X → Y we have ∥f_{k} − A∥_{L_{∞}(y+ρB_{X})} ⩾ ερ. Let 𝒰 be a free ultrafilter on ℕ and consider the mapping f_{𝒰} : B_{X} → Y_{𝒰} given by f(x) = (f_{k}(x))_{k=1}^{∞}. Here Y_{𝒰} denotes the ultrapower of Y; since Y is superreflexive we are ensured that Y_{𝒰} is reflexive. A moment of thought reveals that f_{𝒰} is 1-Lipschitz yet it cannot have a point of differentiability. This contradicts the fact [13] that reflexive spaces have the Radon-Nikodým property (see [4, Ch. 5]), and hence f_{𝒰} is differentiable almost everywhere. Due to the ineffectiveness of this argument, the estimation of the fundamental parameter r^{X→Y} (ε) is a basic question that [2] left open. This problem is resolved here via the following theorem.

Theorem 1.1. Fix n ∈ ℕ, p ∈ [2, ∞) and K ∈ [1, ∞). Assume that n = dim X < ∞ and the norm of Y satisfies (2). Then for all ε ∈ (0, \frac{1}{2}) we have

r^{X→Y} (ε) ⩾ \{ \begin{matrix}ε^{(16K/ε)^{p}} & if n = 1, \\ ε^{K^{p}n^{20(n+p)}/ε^{2p+2n−2}} & if n ⩾ 2. \end{matrix}  (3)

In Section 4 we present an example showing that if ε ∈ (0, \frac{1}{2}) and p ∈ [2, ∞) then for X_{0} = ℓ_{2}^{n} and Y_{0} = ℓ_{2}(ℓ_{p}) we have

r^{X_{0}→Y_{0}}(ε) ⩽ \frac{1}{\sqrt{n}}e^{−(κ/ε)^{p}},

where κ ∈ (0, ∞) is a universal constant. Note that ℓ_{2}(ℓ_{p}) satisfies (2); see [12]. Thus, when n = 1 Theorem 1.1 is quite sharp as ε → 0 (up to a log(1/ε) term in the exponent), but it remains a very interesting open problem to determine the asymptotic behavior of r^{X→Y} (ε) as n → ∞. It is worthwhile to single out the purely Hilbertian special case of this problem.

1See [8] for background on finite representability and ultrapowers of Banach spaces.

Question 1. What is the asymptotic behavior of r^{ℓ_{2}^{n}→ℓ_{2}} (\frac{1}{2}) as n → ∞?

We note that despite the fact that the gap between (3) and the above upper bound on r^{X→Y} (ε) is very large as n → ∞, the lower estimate on r^{X→Y} (ε) in (3) is sufficiently strong to match the best-known bound in Bourgain’s discretization theorem for superreflexive targets; see Section 1.1.

In our forthcoming article [16], written jointly with Tuomas Hytönen, we study a natural variant of the UAAP by replacing the L_{∞} requirement in (1) by

(\frac{1}{ρ^{n}vol(B_{X})} ∫_{y+ρB_{X}} (\frac{∥f(z) − A(z)∥}{ρ})^{p} dz)^{1/p} ⩽ ε∥f∥_{Lip}.

In this setting, we obtain in [16] asymptotically stronger lower bounds on ρ when Y is a UMD Banach space (see [6] for a detailed discussion of UMD spaces). Unlike our proof of Theorem 1.1, which is entirely geometric, the arguments in [16] are based on vector-valued Littlewood-Paley theory.

1.1. Bourgain’s discretization theorem. Let (X, d_{X}) and (Y, d_{Y}) be metric spaces. The distortion of X in Y, denoted c_{Y} (X), is the infimum over those D ∈ [1, ∞] for which there exists f : X → Y and s ∈ (0, ∞) satisfying

∀ x, y ∈ X, sd_{X}(x, y) ⩽ d_{Y} (f(x), f(y)) ⩽ Dsd_{X}(x, y).

Suppose now that (X, ∥ · ∥_{X}) and (Y, ∥ · ∥_{Y}) are normed spaces with dim(X) < ∞ and dim(Y) = ∞. For ε ∈ [0, 1) let δ_{X↪Y} (ε) be the supremum over those δ ∈ (0, 1) such that every δ-net N_{δ} of B_{X} satisfies c_{Y} (N_{δ}) ⩾ (1 − ε)c_{Y} (X).

A classical theorem of Ribe [23] asserts that δ_{X↪Y} (ε) > 0 for all ε ∈ (0, 1). A different proof of this fact, due to Heinrich and Mankiewicz, was obtained in [15]. Bourgain [5] discovered yet another proof of the positivity of δ_{X↪Y} (ε), which, unlike previous proofs, yields the following concrete estimate, known as Bourgain’s discretization theorem.

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

It is an intriguing open question to determine the asymptotic behavior of the best possible lower bound on inf{δ_{X↪Y} (ε) : dim(X) = n}. This is of interest even for special classes of normed spaces Y, though there has been little progress on this problem besides the improved estimate δ_{X↪L_{p}}(ε) ≳ ε^{2}/n^{5/2}, which was obtained in [14] (here p ∈ [1, ∞) and the implied constant is independent of p, n and X).

We shall now describe a different approach to Bourgain’s discretization theorem based on Theorem 1.1. If an affine mapping is bi-Lipschitz on a fine enough net of a ball y +ρB_{X} then it is also bi-Lipschitz on all of X. It is therefore natural to approach the problem of estimating δ_{X↪Y} (ε) by first extending the embedding of the net N_{δ} to a Lipschitz function defined on all of X, and then finding a large enough ball on which the extended function is approximately affine. By the theorem of Bates, Johnson, Lindenstrauss, Preiss and Schechtman, for this strategy to work we need Y to be superreflexive. Bourgain’s discretization theorem is interesting even for superreflexive targets, and moreover the estimate (4) is the best known estimate even with this additional restriction on Y. It turns out that the above strategy, when combined with our estimate (3), suffices to match Bourgain’s bound (4) when Y is superreflexive. The details of this link between Theorem 1.1 and (4) are explained below.

Fix ε ∈ (0, 1), p ∈ [2, ∞) and K ∈ [1, ∞). Suppose that dim(X) = n ⩾ 2 and the norm of Y satisfies the uniform convexity condition (2). Set

δ = e^{−K^{p}(n/ε)^{C(n+p)}},  (5)

where C ∈ (1, ∞) is a universal constant that will be determined later.

Let N_{δ} be a δ-net of B_{X} and write D = c_{Y} (N_{δ}). Note that, by John’s theorem [19] and Dvoretzky’s theorem [9], we have the a priori bound D ⩽ \sqrt{n}. Take f : N_{δ} → Y satisfying

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

By a Lipschitz extension theorem of Johnson, Lindenstrauss and Schechtman [20], there exists F : X → Y that coincides with f when restricted to N_{δ}, and ∥F ∥_{Lip} ⩽ cnD, where c ∈ (1, ∞) is a universal constant.

By Theorem 1.1 there exist y ∈ X, z ∈ Y, a linear mapping T : X → Y, and a radius

ρ ⩾ ε^{K^{p}n^{20(n+p)}(32cnD/ε)^{2p+2n−2}}.  (7)

such that y + ρB_{X} ⊆ B_{X} and

∀ x ∈ y + ρB_{X}, ∥F (x) − z − T x∥_{Y} ⩽ \frac{ε}{32}ρ.  (8)

Note that it follows from (7) that we can choose the constant C in (5) so that

ρ ⩾ \frac{64\sqrt{n}δ}{ε} .  (9)

Fix u ∈ X with ∥u∥_{X} = 1. Choose v, w ∈ N_{δ} ∩ (y + ρB_{X}) such that ∥v − y∥_{X} ⩽ δ and ∥w−y−\frac{ρ}{2}u∥_{X} ⩽ δ. Thus ∥w−v−\frac{ρ}{2}u∥_{X} ⩽ 2δ, and consequently ∥w−v∥_{X} ∈ [ρ/2−2δ, ρ/2+2δ]. Using the fact that F extends f,

∥T w − T v∥_{Y} ⩽^{(8)} ∥f(w) − f(v)∥_{Y} + \frac{ερ}{16} ⩽^{(6)} (1 + \frac{ε}{16}) D∥w − v∥_{X} + \frac{ερ}{16}

⩽ (1 + \frac{ε}{16}) D (\frac{ρ}{2} + 2δ) + \frac{ερ}{16} ⩽^{(9)} (1 + \frac{ε}{4}) \frac{ρ}{2}D.

Hence ∥T u∥_{Y} ⩽ \frac{2}{ρ}∥T w − T v∥_{Y} + \frac{2∥T ∥}{ρ} ∥w − v − \frac{ρ}{2}u∥_{X} ⩽ (1 + \frac{ε}{4}) D + \frac{4δ∥T ∥}{ρ}. Since this holds for all unit vectors u ∈ X,

∥T ∥ ⩽ \frac{1 + ε/4}{1 − 4δ/ρ}D ⩽ (1 + \frac{ε}{2}) D ⩽ 2\sqrt{n}.  (10)

Now,

∥T w − T v∥_{Y} ⩾^{(8)} ∥f(w) − f(v)∥_{Y} − \frac{ερ}{16} ⩾^{(6)} ∥w − v∥_{X} − \frac{ερ}{16} ⩾ \frac{ρ}{2} − 2δ − \frac{ερ}{16} ⩾ (1 − \frac{ε}{4}) \frac{ρ}{2}.

Hence,

∥T u∥_{Y} ⩾ \frac{2}{ρ}∥T w − T v∥_{Y} − \frac{2∥T ∥}{ρ} ∥w − v − \frac{ρ}{2}u∥_{X} ⩾^{(10)} 1 − \frac{ε}{4} − \frac{8\sqrt{n}δ}{ρ} ⩾^{(9)} 1 − \frac{ε}{2}.

We have proved that c_{Y} (X) ⩽ \frac{1+ε/2}{1−ε/2}D = \frac{1+ε/2}{1−ε/2}c_{Y} (N_{δ}) ⩽ \frac{1}{1−ε}c_{Y} (N_{δ}). Thus, recalling the choice of δ in (5),

δ_{X↪Y} (ε) ⩾ e^{−K^{p}(n/ε)^{C(n+p)}}.  (11)

Remark 1.1. In fact, we have the general estimate

δ_{X↪Y} (ε) ⩾ \frac{ε}{n} · r^{X→Y} (\frac{κε}{c_{Y} (X)}) ,  (12)

where κ ∈ (0, ∞) is a universal constant. This estimate follows from a more careful application of the above reasoning. Specifically, we used the Lipschitz extension theorem of Johnson, Lindenstrauss and Schechtman [20] to obtain the function F. This theorem ignores the fact that f was defined on a δ-net: it would apply equally well if f were defined on any subset of X. One can exploit the additional information that the domain of f is a net by invoking an approximate Lipschitz extension theorem of Bourgain [5]. This theorem states that for every τ ∈ (20δ, 1) there exists a function F_{τ} : X → Y such that ∥F_{τ}(x)−f(x)∥_{Y} ⩽ τ for every x ∈ N_{δ} and the Lipschitz constant of F_{τ} on \frac{1}{2}B_{X} is (1 + O(nδ/τ))(1 + ε/16)D (this formulation of Bourgain’s approximate extension theorem is not stated explicitly in [5], but it easily follows from the argument in [14, Sec. 3]). Now, one can deduce (12) by repeating mutatis mutandis the above proof while optimizing over τ. We omit the details since the resulting estimate, when applied to our bounds (3), only affects the constant C in (11).

2. Proof of Theorem 1.1 when n = 1

The proof of Theorem 1.1 when n = 1 follows well-established metric differentiation methodology. This type of reasoning, also known as the approximate midpoint argument, seems to have been first used by Enflo in his classical proof that L_{1} and ℓ_{1} are not uniformly homeomorphic; see [3]. The basic idea is that a Lipschitz function f : ℝ → Y must map the midpoints between many pairs of points x, y ∈ ℝ to “almost midpoints” of f(x) and f(y). See Chapter 10 of [4] for a precise formulation of this principle. One can iterate this idea to deduce that f must map many “discretized geodesic segments” to “discretized almost geodesics”. Such an iteration of the midpoint argument is contained in e.g. [21, Prop. 1.4.9], and a striking recent application of this type of reasoning can be found in [11]. When the target space is uniformly convex, approximate geodesics must be close to straight lines. This rigidity statement explains why one can hope to find a macroscopically large region on which f is almost affine. In order to obtain good quantitative control on the size of such a region one follows the general strategy that is explained in Appendix 2 of [7]. Using the terminology of [7], the “coercive quantity” in our setting is the functional E_{m}^{a,b}(·) defined below.

In Section 3 we build on the tools developed in this section to deduce Theorem 1.1 when n ⩾ 2. In this setting one must deal with higher-dimensional phenomena, and to obtain good dimension-dependent bounds. We will argue that there must exist a cube on which a given Lipschitz function maps all axis-parallel discretized line segments to almost-straight lines. This does not imply that the function itself is almost affine on the same cube: at best it means that it is almost multi-linear. Therefore an additional argument is needed in order to find a scale on which the function is almost affine. Moreover, a crucial new ingredient of our argument is that, when n ⩾ 2, we make use of a more complicated (two-parameter) coercive quantity to obtain good control on this scale; see (42).

Lemma 2.1. Fix p ∈ [2, ∞). Suppose that (Y, ∥·∥_{Y}) is a Banach space satisfying the uniform convexity condition (2). Fix a, b ∈ ℝ with a < b and h : [a, b] → Y. For m ∈ ℕ ∪ {0} define

E_{m}^{a,b}(h) =^{def} \frac{1}{2^{m}} ∑_{k=0}^{2^{m}−1} ∥\frac{h(a + (k + 1)2^{−m}(b − a)) − h(a + k2^{−m}(b − a))}{2^{−m}(b − a)}∥_{Y}^{p} .  (13)

Then

E_{m}^{a,b}(h) ⩾ \frac{∥h(b) − h(a)∥_{Y}^{p}}{(b − a)^{p}} + \frac{1}{(2K)^{p}} max_{k∈\{0,...,2^{m}\}} \frac{∥h (a + \frac{k}{2^{m}} (b − a)) − L_{h}^{a,b} (a + \frac{k}{2^{m}} (b − a))∥_{Y}^{p}}{(b − a)^{p}} ,

where K ∈ (0, ∞) is the constant appearing in (2) and L_{h}^{a,b}(h) : [a, b] → Y is the linear interpolation of the values of h on the endpoints of the interval [a, b], i.e.,

∀t ∈ ℝ, L_{h}^{a,b}(t) =^{def} \frac{t − a}{b − a}h(b) + \frac{b − t}{b − a}h(a).  (14)

Proof. We may assume without loss of generality that a = 0 and b = 1. In this case, denote for the sake of simplicity E_{m}^{0,1}(h) = E_{m}(h) and L_{h}^{0,1} = L_{h}. We will actually prove the following slightly stronger statement by induction on m: for every k ∈ {0, …, 2^{m}},

E_{m}(h) ⩾ ∥h(1) − h(0)∥_{Y}^{p} + \frac{2^{p}}{K^{p} (3 − 2^{−(m−1)})^{p−1}} · ∥h (\frac{k}{2^{m}} ) − L_{h} (\frac{k}{2^{m}} )∥_{Y}^{p} . (15)

Since E_{0}(h) = ∥h(1) − h(0)∥_{Y}^{p}, the desired inequality (15) holds as equality when m = 0. Fix m ∈ ℕ and assume that (15) holds true with m replaced by m − 1.

Convexity of ∥ · ∥_{Y}^{p} implies that for every m ∈ ℕ,

E_{m}(h) = 2^{m(p−1)} ∑_{k=0}^{2^{m}−1} ∥h (\frac{k + 1}{2^{m}}) − h (\frac{k}{2^{m}} )∥_{Y}^{p}

= 2^{m(p−1)+1} ∑_{j=0}^{2^{m−1}−1} \frac{∥h (\frac{2j+1}{2^{m}}) − h (\frac{2j}{2^{m}} )∥_{Y}^{p} + ∥h (\frac{2j+2}{2^{m}}) − h (\frac{2j+1}{2^{m}})∥_{Y}^{p}}{2}

⩾ 2^{m(p−1)+1} ∑_{j=0}^{2^{m−1}−1} ∥\frac{h (\frac{j+1}{2^{m−1}} ) − h (\frac{j}{2^{m−1}} )}{2}∥_{Y}^{p}
= E_{m−1}(h).  (16)

Hence, if k ∈ {0, …, 2^{m}} is even then by the inductive hypothesis

E_{m}(h) ⩾^{(16)} E_{m−1}(h) ⩾^{(15)} E_{0}(h) + \frac{2^{p}}{K^{p} (3 − 2^{−(m−2)})^{p−1}} ∥h (\frac{k/2}{2^{m−1}} ) − L_{h} (\frac{k/2}{2^{m−1}} )∥_{Y}^{p}

⩾ E_{0}(h) + \frac{2^{p}}{K^{p} (3 − 2^{−(m−1)})^{p−1}} ∥h (\frac{k}{2^{m}} ) − L_{h} (\frac{k}{2^{m}} )∥_{Y}^{p} .

It therefore suffices to prove (15) when k is odd, say, k = 2j + 1. In this case, by reasoning analogously to (16), we see that

E_{m}(h) − E_{m−1}(h)
2^{m(p−1)+1}
⩾ \frac{∥h (\frac{2j+1}{2^{m}}) − h (\frac{2j}{2^{m}} )∥_{Y}^{p} + ∥h (\frac{2j+2}{2^{m}}) − h (\frac{2j+1}{2^{m}})∥_{Y}^{p}}{2} − ∥\frac{h (\frac{2j+2}{2^{m}}) − h (\frac{2j}{2^{m}} )}{2}∥_{Y}^{p}

⩾ \frac{1}{K^{p}} ∥\frac{h (\frac{j}{2^{m−1}} ) + h (\frac{j+1}{2^{m−1}} )}{2} − h (\frac{k}{2^{m}} )∥_{Y}^{p} ,  (17)

where in (17) we used (2) with

x = \frac{h (\frac{2j+2}{2^{m}}) − h (\frac{2j}{2^{m}} )}{2} and y = h (\frac{2j + 1}{2^{m}}) − \frac{h (\frac{2j}{2^{m}} ) + h (\frac{2j+2}{2^{m}})}{2}.

The inductive hypothesis implies that

\frac{K^{p}}{2^{p}} (E_{m−1}(h) − E_{0}(h))

⩾ \begin{matrix}max & \{∥h (\frac{j}{2^{m−1}} ) − L_{h} (\frac{j}{2^{m−1}} )∥_{Y}^{p} , ∥h (\frac{j+1}{2^{m−1}} ) − L_{h} (\frac{j+1}{2^{m−1}} )∥_{Y}^{p} \} \\ (3 − 2^{−(m−2)}) & p−1 \end{matrix}. (18)

Since L_{h} is affine, by convexity of ∥ · ∥_{Y}^{p} we have

∥\frac{h (\frac{j}{2^{m−1}} ) + h (\frac{j+1}{2^{m−1}} )}{2} − L_{h} (\frac{k}{2^{m}} )∥_{Y}^{p} = ∥\frac{h (\frac{j}{2^{m−1}} ) − L_{h} (\frac{j}{2^{m−1}} ) + h (\frac{j+1}{2^{m−1}} ) − L_{h} (\frac{j+1}{2^{m−1}} )}{2}∥_{Y}^{p}

⩽ \frac{∥h (\frac{j}{2^{m−1}} ) − L_{h} (\frac{j}{2^{m−1}} )∥_{Y}^{p} + ∥h (\frac{j+1}{2^{m−1}} ) − L_{h} (\frac{j+1}{2^{m−1}} )∥_{Y}^{p}}{2}
⩽ max \{∥h (\frac{j}{2^{m−1}} ) − L_{h} (\frac{j}{2^{m−1}} )∥_{Y}^{p} , ∥h (\frac{j + 1}{2^{m−1}}) − L_{h} (\frac{j + 1}{2^{m−1}})∥_{Y}^{p} \} .  (19)

Therefore, using (17), (18) and (19), we have

\frac{K^{p}}{2^{p}} (E_{m}(h) − E_{0}(h))

⩾ \begin{matrix}∥\frac{h(\frac{j}{2^{m−1}} )+h(\frac{j+1}{2^{m−1}} )}{2} − L_{h} (\frac{k}{2^{m}} )∥ & {p \atop Y} \\ (3 − 2^{−(m−2)}) & p−1 \end{matrix} + 2^{(m−1)(p−1)} ∥\frac{h (\frac{j}{2^{m−1}} ) + h (\frac{j+1}{2^{m−1}} )}{2} − h (\frac{k}{2^{m}} )∥_{Y}^{p}

⩾ \begin{matrix}(∥\frac{h(\frac{j}{2^{m−1}} )+h(\frac{j+1}{2^{m−1}} )}{2} − L_{h} (\frac{k}{2^{m}} )∥_{Y} + ∥\frac{h(\frac{j}{2^{m−1}} )+h(\frac{j+1}{2^{m−1}} )}{2} − h (\frac{k}{2^{m}} )∥_{Y} ) & p \\ (3 − 2^{−(m−2)} + 2^{−(m−1)}) & p−1 \end{matrix}  (20)

⩾ \begin{matrix}∥h (\frac{k}{2^{m}} ) − L_{h} (\frac{k}{2^{m}} )∥ & {p \atop Y} \\ (3 − 2^{−(m−1)}) & p−1 \end{matrix} ,  (21)

where in (20) we used the inequality

∀α, β, u, v ∈ (0, ∞), \frac{u^{p}}{α^{p−1}} + \frac{v^{p}}{β^{p−1}} ⩾ \frac{(u + v)^{p}}{(α + β)^{p−1}} ,

which is an immediate consequence of Hölder’s inequality. Since inequality (21) is the same as the desired inequality (15), the proof of Lemma 2.1 is complete. □

Proof of Theorem 1.1 when n = 1. Our goal is to show that if (Y, ∥ · ∥_{Y}) is a Banach space satisfying (2) then for every ε ∈ (0, \frac{1}{2}) we have

r^{ℝ→Y} (ε) ⩾ (\frac{ε}{8})^{(8K/ε)^{p}} .  (22)

The fact that (22) is better than the desired estimate (3) is a simple elementary inequality (recall that p ⩾ 2, K ⩾ 1 and 0 < ε < 1/2).

Assume for contradiction that (22) fails. Then there exists ε ∈ (0, \frac{1}{2}) and a 1-Lipschitz function h : [−1, 1] → Y such that for every −1 ⩽ a < b ⩽ 1 with b − a ⩾ (ε/8)^{(8K/ε)^{p}} there exists t ∈ [a, b] satisfying ∥h(t) − L_{h}^{a,b}(t)∥_{Y} > ε(b − a)/2. Choose m ∈ ℕ such that ε/8 ⩽ 2^{−m} < ε/4 and take k ∈ {1, …, m} such that if we set s = a + k2^{−m}(b − a) then |s−t| ⩽ (b−a)/2^{m+1}. Because f is 1-Lipschitz, it follows immediately from the definition (14) of L_{h}^{a,b} that it is also 1-Lipschitz. Hence,

max_{k∈\{0,...,2^{m}\}} \frac{∥h (a + \frac{k}{2^{m}} (b − a)) − L_{h}^{a,b} (a + \frac{k}{2^{m}} (b − a))∥_{Y}^{p}}{(b − a)^{p}} ⩾ \frac{∥h(s) − L_{h}^{a,b}(s)∥_{Y}^{p}}{(b − a)^{p}}

⩾ \frac{(∥h(t) − L_{h}^{a,b}(t)∥_{Y} − ∥h(t) − h(s)∥_{Y} − ∥L_{h}^{a,b}(t) − L_{h}^{a,b}(s)∥_{Y} )^{p}}{(b − a)^{p}} ⩾ (\frac{ε}{2} − \frac{1}{2^{m}} )^{p} ⩾ \frac{ε^{p}}{4^{p}} .

Consequently, it follows from Lemma 2.1 that

− 1 ⩽ a < b ⩽ 1 ∧ b − a ⩾ (ε/8)^{(8K/ε)^{p}} ⟹ E_{m}^{a,b}(h) ⩾ \frac{∥h(b) − h(a)∥_{Y}^{p}}{(b − a)^{p}} + (\frac{ε}{8K} )^{p} . (23)

For k ∈ ℕ∪{0} and j ∈ {0, …, 2^{km}} denote a_{j}^{k} = −1+j/2^{km−1}. If 1/2^{km−1} ⩾ (ε/8)^{(8K/ε)^{p}} then it follows from (23) that for every j ∈ {0, …, 2^{km} − 1} we have

E_{m}^{a_{j}^{k},a_{j+1}^{k}}(h) ⩾ \frac{∥h (a_{j+1}^{k}) − h (a_{j}^{k})∥_{Y}^{p}}{2^{(km−1)p}} + (\frac{ε}{8K} )^{p} .  (24)

Hence,

E_{(k+1)m}^{−1,1}(h) =^{(13)} 2^{−km} ∑_{j=0}^{2^{km}−1} E_{m}^{a_{j}^{k},a_{j+1}^{k}}(h)

⩾^{(24)} 2^{−km} ∑_{j=0}^{2^{km}−1} \frac{∥h (a_{j+1}^{k}) − h (a_{j}^{k})∥_{Y}^{p}}{2^{(km−1)p}} + (\frac{ε}{8K} )^{p} =^{(13)} E_{km}^{−1,1}(h) + (\frac{ε}{8K} )^{p} . (25)

Since h is 1-Lipschitz, the definition (13) implies that E_{j}^{a,b}(h) ⩽ 1 for all −1 ⩽ a < b ⩽ 1 and j ∈ ℕ. Denote M = ⌊(1 + (8K/ε)^{p} log_{2}(8/ε)) /m⌋. Then (25) holds for every k ∈ ℕ ∩ [0, M]. It follows that E_{(M+1)m}^{−1,1}(h) ⩾ E_{0}^{−1,1}(h) + (M + 1)(ε/(8K))^{p} ⩾ (M + 1)(ε/(8K))^{p}. Observe that the definition of M, combined with 2^{−m} ⩾ ε/8, implies that (M + 1)(ε/(8K))^{p} > 1. Thus E_{(M+1)m}^{−1,1}(h) > 1, a contradiction. □

3. Proof of Theorem 1.1 when n ⩾ 2

Fix n ∈ ℕ and let (X, ∥ · ∥_{X}) be an n-dimensional normed space. Assume also that (Y, ∥ · ∥_{Y}) is a Banach space and f : X → Y. By John’s theorem [19] there exists a norm ∥ · ∥_{2} on X which is Hilbertian and satisfies ∥x∥_{2} ⩽ ∥x∥_{X} ⩽ \sqrt{n}∥x∥_{2} for all x ∈ X. Let {e_{1}, …, e_{n}} be an orthonormal basis with respect to ∥x∥_{2}. Via the obvious identifications, we may assume below that X = ℝ^{n} and {e_{1}, …, e_{n}} is the standard coordinate basis.

For y ∈ ℝ^{n} and j ∈ {1, …, n} define f_{j}^{y} : ℝ → Y by f_{j}^{y}(t) = f(y +te_{j}). Also, given m ∈ ℕ and j ∈ \{1, …, n\} set F_{j}^{m} = \{z ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n} : z_{j} = 0\}. For x ∈ ℝ^{n} and ϑ ∈ (0, ∞) consider the following quantity

𝒟_{ϑ}^{m}(f)(x) =^{def} max_{\begin{matrix}j∈\{1,...,n\} \\ y∈x+ϑF_{j}^{m} \\ k∈\{0,...,2^{m}\} \end{matrix}} \frac{∥f (y + \frac{kϑ}{2^{m}} e_{j}) − f(y) − \frac{k}{2^{m}} (f (y + ϑe_{j}) − f(y))∥_{X}}{ϑ}

=^{(14)} max_{\begin{matrix}j∈\{1,...,n\} \\ y∈x+ϑF_{j}^{m} \\ k∈\{0,...,2^{m}\} \end{matrix}} \frac{1}{ϑ} ∥f_{j}^{y} (\frac{k}{2^{m}} ϑ) − L_{f_{j}^{y}}^{0,ϑ} (\frac{k}{2^{m}} ϑ)∥_{Y} . (26)

Lemma 3.1. Fix x ∈ ℝ^{n}, m ∈ ℕ and ε, ϑ ∈ (0, ∞) with 2^{m} ⩾ 2/ε ⩾ 10n^{2}. Suppose that f : ℝ^{n} → Y satisfies ∥f(y) − f(z)∥ ⩽ ∥y − z∥_{2} for all y, z ∈ x + [0, ϑ]^{n}, i.e., f is 1-Lipschitz with respect to the Euclidean metric on the cube x+[0, ϑ]^{n}. Suppose also that 𝒟_{ϑ}^{m}(f)(x) ⩽ ε. Then there exists an affine mapping A : ℝ^{n} → Y such that

sup_{z∈x+[0,\sqrt{ε}ϑ]^{n}} ∥f(z) − A(z)∥_{Y} ⩽ 8n^{2}εϑ.  (27)

Proof. By translation and rescaling we may assume without loss of generality that x = 0 and ϑ = 1. We will prove by induction on n that there exist vectors {v_{S}}_{S⊆{1,...,n}} ⊆ Y with

v_{∅} = f(0) and ∀ ∅ ≠ S ⊆ {1, …, n}, ∥v_{S}∥_{Y} ⩽ 2^{|S|−1},  (28)

such that for every y ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n} we have

∥f(y) − ∑_{S⊆{1,...,n}} W_{S}(y)v_{S}∥_{Y} ⩽ εn,  (29)

where the Walsh functions {W_{S} : ℝ^{n} → ℝ}_{S⊆{1,...,n}} are defined as usual by W_{S}(y) =^{def} ∏_{i∈S} y_{i}.

Assuming for the moment that this assertion has been proven, we proceed to deduce (27). Define A : ℝ^{n} → Y by A(z) = v_{∅} + ∑_{i=1}^{n} z_{i}v_{\{i\}}. For z ∈ [0, 1]^{n} choose y ∈ \frac{1}{2^{m}} \{0, …, 2^{m} − 1\}^{n} with |z_{i} − y_{i}| ⩽ 1/2^{m+1} for all i ∈ \{1, …, n\}. If we assume in addition that z ∈ [0, \sqrt{ε}]^{n} then also 0 ⩽ y_{i} ⩽ \frac{1}{2^{m+1}} + \sqrt{ε} for all i ∈ \{1, …, n\}. Setting g(y) = ∑_{S⊆\{1,...,n\}} W_{S}(y)v_{S}, we have

∥f(z) − A(z)∥_{Y}

⩽ ∥f(z) − f(y)∥_{Y} + ∥f(y) − g(y)∥_{Y} + ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|⩾2 \end{matrix}} W_{S}(y) ∥v_{S}∥_{Y} + ∑_{i=1}^{n} |z_{i} − y_{i}| · ∥v_{\{i\}}∥_{Y}

⩽ \frac{\sqrt{n}}{2^{m+1}} + nε + ∑_{k=2}^{n} \binom{n}{k} (\sqrt{ε} + \frac{1}{2^{m+1}} )^{k} 2^{k−1} + \frac{n}{2^{m+1}}  (30)

= \frac{\sqrt{n} + n}{2^{m+1}} + nε + \frac{1}{2} ((1 + 2\sqrt{ε} + \frac{1}{2^{m}} )^{n} − 1 − 2n\sqrt{ε} − \frac{n}{2^{m}} )

⩽ 3nε + \frac{(1 + \sqrt{5ε})^{n} − 1 − n\sqrt{5ε}}{2}  (31)
⩽ 8n^{2}ε,  (32)

where in (30) we used the fact that f is 1-Lipschitz and ∥y − z∥_{2} ⩽ \sqrt{n}∥y − z∥_{∞} ⩽ \frac{\sqrt{n}}{2^{m+1}} , the estimates (28), (29), and the above bounds on ∥y − z∥_{∞} and ∥y∥_{∞}. In (31) we used our assumption 2^{m} ⩾ 2/ε ⩾ 10n^{2}, which directly implies that 2\sqrt{ε}+2^{−m} ⩽ \sqrt{5ε} ⩽ 1/n, together with the fact that the mapping s ↦ (1 + s)^{n} − 1 − ns is increasing on (0, ∞). In (32) we used the elementary inequality (1 + s)^{n} − 1 − ns ⩽ 2n^{2}s^{2}, which is valid when s ∈ (0, 1/n).

It remains to prove (28) and (29), which will be done by induction on n. For n = 1 set v_{∅} = f(0) and v_{{1}} = f (1) − f(0). Since f is 1-Lipschitz we know that ∥v_{{1}}∥_{Y} ⩽ 1, proving (28). For the above choices of v_{∅}, v_{{1}}, the estimate (29) is the same as the assumption 𝒟_{1}^{m}(f)(x) ⩽ ε (recall that ϑ = 1).

If n > 1 apply the inductive hypothesis to the functions f_{0}, f_{1} : ℝ^{n−1} → Y given by f_{0}(y_{1}, …, y_{n−1}) = f(y_{1}, …, y_{n−1}, 0) and f_{1}(y_{1}, …, y_{n−1}) = f(y_{1}, …, y_{n−1}, 1). One obtains {v_{S}^{0}}_{S⊆{1,...,n−1}}, {v_{S}^{1}}_{S⊆{1,...,n−1}} ⊆ Y satisfying v_{∅}^{0} = f(0), v_{∅}^{1} = f(e_{n}), for all nonempty S ⊆ {1, …, n − 1} we have ∥v_{S}^{0}∥_{Y} , ∥v_{S}^{1}∥_{Y} ⩽ 2^{|S|−1}, and if we define g_{0}, g_{1} : ℝ^{n−1} → Y by

g_{i}(y) =^{def} ∑_{S⊆{1,...,n−1}} W_{S}(y)v_{S}^{i},

then

max {∥g_{0}(y) − f_{0}(y)∥_{Y} , ∥g_{1}(y) − f_{1}(y)∥_{Y} } ⩽ ε(n − 1)  (33)

for all y ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n−1}. For S ⊆ \{1, …, n\} define

v_{S} =^{def} \{ \begin{matrix}v_{S}^{0} & if n ∉ S, \\ v_{S∖\{n\}}^{1} − v_{S∖\{n\}}^{0} & if n ∈ S. \end{matrix}  (34)

So, v_{∅} = v_{∅}^{0} = f(0). If S ≠ ∅ and n ∉ S then have ∥v_{S}∥_{Y} = ∥v_{S}^{0}∥_{Y} ⩽ 2^{|S|−1}. If n ∈ S and S ∖ {n} ≠ ∅ then ∥v_{S}∥_{Y} ⩽ ∥v_{S∖{n}}^{0}∥_{Y} + ∥v_{S∖{n}}^{1}∥_{Y} ⩽ 2 · 2^{|S|−2} = 2^{|S|−1}. Finally, since f is 1-Lipschitz we have ∥v_{{n}}∥_{Y} = ∥v_{∅}^{1} − v_{∅}^{0}∥_{Y} = ∥f(e_{n}) − f(0)∥_{Y} ⩽ 1. This completes the proof of (28). To prove (29) define for y ∈ ℝ^{n},

g(y) =^{def} ∑_{S⊆{1,...,n}} W_{S}(y)v_{S} =^{(34)} (1 − y_{n}) g_{0}(y_{1}, …, y_{n−1}) + y_{n}g_{1}(y_{1}, …, y_{n−1}).  (35)

The assumption 𝒟_{1}^{m}(f)(x) ⩽ ε implies that for all y ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n−1} and all k ∈ {0, …, 2^{m}} we have

∥f (y_{1}, …, y_{n−1}, \frac{k}{2^{m}} ) − (1 − \frac{k}{2^{m}} ) f_{0}(y) − \frac{k}{2^{m}} f_{1}(y)∥_{Y} ⩽ ε.  (36)

Hence,

∥f (y_{1}, …, y_{n−1}, \frac{k}{2^{m}} ) − g (y_{1}, …, y_{n−1}, \frac{k}{2^{m}} )∥_{Y}

⩽^{(35)∧(36)} ε + (1 − \frac{k}{2^{m}} ) ∥f_{0}(y) − g_{0}(y)∥_{Y} + \frac{k}{2^{m}} ∥f_{1}(y) − g_{1}(y)∥_{Y} ⩽^{(33)} εn. (37)

Since (37) holds for all y ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n−1} and all k ∈ \{0, …, 2^{m}\}, the proof of (29) is complete. □

Proof of Theorem 1.1 when n ⩾ 2. Our goal is to show that if (Y, ∥ · ∥_{Y}) is a Banach space satisfying (2) then for every ε ∈ (0, \frac{1}{2}) we have

r^{X→Y} (ε) ⩾ R =^{def} ε^{K^{p}n^{20(n+p)}/ε^{2p+2n−2}}.  (38)

Assume for contradiction that (38) fails. Then there exists ε ∈ (0, \frac{1}{2}) and a \frac{1}{\sqrt{n}}-Lipschitz function f : B_{X} → Y such that for all ρ ⩾ R and y ∈ X such that y + ρB_{X} ⊆ B_{X}, if A : X → Y is affine then

sup_{z∈y+ρB_{X}} \frac{∥f(z) − A(z)∥_{Y}}{ρ} > \frac{ε}{\sqrt{n}}.  (39)

We claim that this implies the following statement.

x ∈ \frac{1}{2}B_{X} ∧ ϑ ∈ [\frac{32n^{5/2}}{ε} R, \frac{1}{2n}] ∧ 2^{m} ∈ [\frac{512n^{5}}{ε^{2}} , ∞) ∩ ℕ ⟹ 𝒟_{ϑ}^{m}(f)(x) > \frac{ε^{2}}{256n^{5}} . (40)

Indeed, note that, because ∥ · ∥ ⩽ \sqrt{n}∥ · ∥_{2} ⩽ n∥ · ∥_{∞}, the assumptions in (40) imply that x + [0, ϑ]^{n} ⊆ B_{X}. Since f is \frac{1}{\sqrt{n}}-Lipschitz, it is 1-Lipschitz with respect to the Euclidean norm. If 𝒟_{ϑ}^{m}(f)(x) ⩽ ε^{2}/(256n^{5}) then it would follow from Lemma 3.1 that there exists an affine mapping A : X → Y such that

sup_{z∈x+[0,εϑ/(16n^{5/2})]} \frac{∥f(z) − A(z)∥_{Y}}{εϑ/(16n^{5/2})} ⩽ 8n^{2}\sqrt{\frac{ε^{2}}{256n^{5}}} = \frac{ε}{2\sqrt{n}}.  (41)

Because ∥ · ∥_{X} ⩾ ∥ · ∥_{2}, we have [−1, 1]^{n} ⊇ B_{X}. Setting ρ = εϑ/(32n^{5/2}) ⩾ R, it follows that x + [0, εϑ/(16n^{5/2})]^{n} ⊇ y + ρB_{X} for some y ∈ X with y + ρB_{X} ⊆ B_{X}. Hence (41) contradicts (39), completing the verification of (40).

It remains to argue that (40) leads to a contradiction. To this end, consider the following quantity, defined for every x ∈ \frac{1}{2}B_{X}, m, k ∈ ℕ ∪ \{0\} and ϑ ∈ (0, 1/(2n)].

H_{m,k}^{ϑ}(f)(x) =^{def} \frac{1}{2^{m(n−1)}} ∑_{j=1}^{n} ∑_{\begin{matrix}y∈\{0,...,2^{m}−1\}^{n} \\ y_{j}=0 \end{matrix}} E_{k}^{0,ϑ} (f_{j}^{x+ϑ2^{−m}y}) .  (42)

In (42), recall the notation f_{j}^{u}(t) = f(u + te_{j}) and the definition (13). One checks directly from the definition (42) that the following recursive relation holds true. If α, β, γ ∈ ℕ ∪ {0} and α ⩾ β then for every ϑ ∈ (0, 1/(2n)],

H_{α,β+γ}^{ϑ}(f)(0) = \frac{1}{2^{βn}} ∑_{x∈\{0,...,2^{β}−1\}^{n}} H_{α−β,γ}^{ϑ/2^{β}}(f) (\frac{ϑ}{2^{β}} x) .  (43)

Observe that the fact that f is \frac{1}{\sqrt{n}}-Lipschitz and ∥e_{j}∥_{X} ⩽ \sqrt{n}∥e_{j}∥_{2} = \sqrt{n} implies that in

each of the summands in (42) the function f_{j}^{x+ϑ2^{−m}y} : [0, ϑ] → Y is 1-Lipschitz. Therefore

we have the point-wise bound E_{k}^{0,ϑ} (f_{j}^{x+ϑ2^{−m}y}) ⩽ 1 for each summand in (42), implying that

H_{m,k}^{ϑ}(f)(x) ⩽ n.  (44)

Set

m =^{def} ⌈log_{2} (\frac{512n^{5}}{ε^{2}} )⌉ ,  (45)

and

M =^{def} ⌊\frac{1}{m} log_{2} (\frac{ε}{64n^{7/2}R})⌋ .  (46)

Fix also an integer k ∈ [0, M] and set

ϑ =^{def} \frac{1}{2^{km+1}n}.  (47)

Then ϑ ⩾ 32n^{5/2}R/ε (recall (38), (45), (46)). It follows from (40) that 𝒟_{ϑ}^{m}(f)(x) ⩾ ε^{2}/(2^{8}n^{5}). By the definition (26), this means that there exists j ∈ {1, …, n} and w ∈ x + ϑF_{j}^{m} (recall that F_{j}^{m} = \{z ∈ \frac{1}{2^{m}} \{0, …, 2^{m}\}^{n} : z_{j} = 0\}), such that for some s ∈ \{0, …, 2^{m}\} we have

∥f (w + \frac{sϑ}{2^{m}} e_{j}) − f(w) − \frac{s}{2^{m}} (f (w + ϑe_{j}) − f(w))∥_{Y} ⩾ \frac{ε^{2}}{2^{9}n^{6}2^{km}} .  (48)

Denote ℓ = (M + 1 − k)m and consider the set

C =^{def} \{y ∈ \{0, …, 2^{ℓ} − 1\} : y_{j} = 0 ∧ ∥y − \frac{2^{ℓ}}{ϑ} (w − x)∥_{∞} ⩽ \frac{ε^{2}2^{ℓ}}{2^{10}n^{11/2}} \} .  (49)

Then

|C| ⩾ ⌊\frac{ε^{2}2^{ℓ}}{2^{10}n^{11/2}} ⌋^{n−1} ⩾ (\frac{ε^{2}}{2^{11}n^{11/2}} )^{n−1} 2^{ℓ(n−1)}.  (50)

Since the Lipschitz constant of f with respect to the ℓ_{∞} norm is at most \sqrt{n}, it follows from (48) that for every y ∈ C we have

∥f (x + \frac{ϑ}{2^{ℓ}} y + \frac{sϑ}{2^{m}} e_{j}) − f (x + \frac{ϑ}{2^{ℓ}} y) − \frac{s}{2^{m}} (f (x + \frac{ϑ}{2^{ℓ}} y + ϑe_{j}) − f (x + \frac{ϑ}{2^{ℓ}} y))∥_{Y}

⩾^{(49)} \frac{ε^{2}}{2^{9}n^{6}2^{km}} − 2\sqrt{n} · \frac{ϑ}{2^{ℓ}} · \frac{ε^{2}2^{ℓ}}{2^{10}n^{11/2}} =^{(47)} \frac{ε^{2}}{2^{10}n^{6}2^{km}} . (51)

An equivalent way to write (51) is as follows.

∥f_{j}^{x+ϑ2^{−ℓ}y} (\frac{s}{2^{m}} ) − L_{f_{j}^{x+ϑ2^{−ℓ}y}}^{0,ϑ} (\frac{s}{2^{m}} )∥_{Y} ⩾ \frac{ε^{2}}{2^{10}n^{6}2^{km}} .

An application of Lemma 2.1 now implies that for every y ∈ C we have

∀ y ∈ C, E_{m}^{0,ϑ} (f_{j}^{x+ϑ2^{−ℓ}y}) ⩾ \frac{∥f_{j}^{x+ϑ2^{−ℓ}y} (ϑ) − f_{j}^{x+ϑ2^{−ℓ}y}(0)∥_{Y}^{p}}{ϑ^{p}} + (\frac{ε^{2}}{K(4n)^{5}} )^{p} ,  (52)

where K is the constant in (2). Also, by convexity (see (16)), for every i ∈ {1, …, n} we have

y ∈ \{0, …, 2^{ℓ}\} ∧ y_{i} = 0 ⟹ E_{m}^{0,ϑ} (f_{i}^{x+ϑ2^{−ℓ}y}) ⩾ \frac{∥f_{i}^{x+ϑ2^{−ℓ}y} (ϑ) − f_{i}^{x+ϑ2^{−ℓ}y}(0)∥_{Y}^{p}}{ϑ^{p}} . (53)

Hence,

H_{ℓ,m}^{ϑ}(f)(x) =^{(42)} \frac{1}{2^{ℓ(n−1)}} ∑_{y∈C} E_{m}^{0,ϑ} (f_{j}^{x+ϑ2^{−ℓ}y}) + \frac{1}{2^{ℓ(n−1)}} ∑_{\begin{matrix}y∈\{0,...,2^{ℓ}−1\}^{n} \\ y_{j}=0 \\ y∉C \end{matrix}} E_{m}^{0,ϑ} (f_{j}^{x+ϑ2^{−ℓ}y})

+\frac{1}{2^{ℓ(n−1)}} ∑_{\begin{matrix}i∈\{1,...,n\} \\ i≠j \end{matrix}} ∑_{\begin{matrix}y∈\{0,...,2^{ℓ}−1\}^{n} \\ y_{i}=0 \end{matrix}} E_{m}^{0,ϑ} (f_{i}^{x+ϑ2^{−ℓ}y})

⩾^{(52)∧(53)} \frac{1}{2^{ℓ(n−1)}} ∑_{i=1}^{n} ∑_{\begin{matrix}y∈\{0,...,2^{ℓ}−1\}^{n} \\ y_{i}=0 \end{matrix}} \frac{∥f_{i}^{x+ϑ2^{−ℓ}y} (ϑ) − f_{i}^{x+ϑ2^{−ℓ}y}(0)∥_{Y}^{p}}{ϑ^{p}} + \frac{|C|}{2^{ℓ(n−1)}} (\frac{ε^{2}}{K(4n)^{5}} )^{p}

⩾^{(50)} \frac{1}{2^{ℓ(n−1)}} ∑_{i=1}^{n} ∑_{\begin{matrix}y∈\{0,...,2^{ℓ}−1\}^{n} \\ y_{i}=0 \end{matrix}} \frac{∥f (x + \frac{ϑ}{2^{ℓ}} (y + 2^{ℓ}e_{i})) − f (x + \frac{ϑ}{2^{ℓ}} y)∥_{Y}^{p}}{ϑ^{p}} + \frac{ε^{2(n−1+p)}}{K^{p}(4n)^{6n+5p}} . (54)

Now, using the recursive identity (43), we have

H_{(M+1)m,(k+1)m}^{1/(2n)}(f)(0) = \frac{1}{2^{kmn}} ∑_{x∈\{0,...,2^{km}−1\}^{n}} H_{(M+1−k)m,m}^{2^{−km}/(2n)}(f) (\frac{2^{−km}}{2n} x) .  (55)

We relate (55) to (54) by noting the following identity, in which we recall that ϑ is given in (47) and ℓ = (M + 1 − k)m.

\frac{1}{2^{kmn+ℓ(n−1)}} ∑_{x∈\{0,...,2^{km}−1\}^{n}} ∑_{i=1}^{n} ∑_{\begin{matrix}y∈\{0,...,2^{ℓ}−1\}^{n} \\ y_{i}=0 \end{matrix}} \frac{∥f (\frac{2^{−km}}{2n} x + \frac{ϑ}{2^{ℓ}} (y + 2^{ℓ}e_{i})) − f (\frac{2^{−km}}{2n} x + \frac{ϑ}{2^{ℓ}} y)∥_{Y}^{p}}{ϑ^{p}}

= \frac{1}{2^{(M+1)m(n−1)+km}} ∑_{i=1}^{n} ∑_{z∈\{0,...,2^{(M+1)m}−1\}^{n}} \frac{∥f (\frac{2^{−(M+1)m}}{2n} z + \frac{2^{−km}}{2n} e_{i}) − f (\frac{2^{−(M+1)m}}{2n} z)∥_{Y}^{p}}{(2^{−km}/(2n))^{p}}

=^{(13)} \frac{1}{2^{(M+1)m(n−1)}} ∑_{i=1}^{n} ∑_{\begin{matrix}y∈\{1,...,2^{(M+1)m}−1\} \\ y_{i}=0 \end{matrix}} E_{km}^{0,1/(2n)} (f_{i}^{\frac{2^{−(M+1)m}}{2n} y})

=^{(42)} H_{(M+1)m,km}^{1/(2n)}(f)(0).  (56)

By combining (54), (55) and (56) we conclude that

∀k ∈ \{0, …, M\}, H_{(M+1)m,(k+1)m}^{1/(2n)}(f)(0) ⩾ H_{(M+1)m,km}^{1/(2n)}(f)(0) + \frac{ε^{2(n−1+p)}}{K^{p}(4n)^{6n+5p}} .

Hence,

n ⩾^{(44)} H_{(M+1)m,(M+1)m}^{1/(2n)}(f)(0) ⩾ (M + 1)\frac{ε^{2(n−1+p)}}{K^{p}(4n)^{6n+5p}} .  (57)

Recalling the definitions (38), (45) and (46), and that K ⩾ 1, ε ∈ (0, \frac{1}{2}) and p, n ⩾ 2, one checks that (57) is a contradiction. □

4. An example

We start with a simple one dimensional construction.

Lemma 4.1. Fix p ∈ [2, ∞) and m ∈ ℕ. There exists a 1-Lipschitz function f_{m} : [0, 1] → ℓ_{p}^{m} with f_{m}(0) = f_{m}(1) = 0 such that for every 0 ⩽ a < b ⩽ 1 with b − a ⩾ 4/2^{m} and every affine mapping A : ℝ → ℓ_{p}^{m} we have

sup_{x∈[a,b]} \frac{∥f_{m}(x) − A(x)∥_{p}}{(b − a)/2} > \frac{1}{8m^{1/p}} .

Consequently, if we set ε = \frac{1}{8m^{1/p}} then

r^{ℝ→ℓ_{p}}(ε) ⩽ \frac{4}{2^{1/(8ε)^{p}}} .

Proof. Define inductively a sequence of functions {f_{k} : [0, 1] → ℓ_{p}^{m}}_{k=0}^{m} as follows. Let {e_{1}, …, e_{m}} be the standard basis of ℓ_{p}^{m}. Set f_{0} ≡ 0. Assume that k ∈ ℕ and we have defined f_{k−1} to be affine on each of the dyadic intervals {[j/2^{k−1}, (j + 1)/2^{k−1}]}_{j=0}^{2^{k−1}−1}. For every j ∈ {0, …, 2^{k−1}} define f_{k}(j/2^{k−1}) = f_{k−1}(j/2^{k−1}) and

f_{k} (\frac{2j + 1}{2^{k}}) = f_{k−1} (\frac{2j + 1}{2^{k}}) + \frac{1}{m^{1/p}2^{k}} e_{k}.  (58)

Let f_{k} be the piecewise affine extension of the above values of f_{k} on {j/2^{k}}_{k=0}^{2^{k}−1}. A straightforward induction shows that

∥f_{k} (\frac{j + 1}{2^{k}}) − f_{k} (\frac{j}{2^{k}} )∥_{p} = \frac{1}{2^{k}} (\frac{k}{m})^{1/p} .

Thus f_{m} is 1-Lipschitz.

Assume for contradiction that 0 ⩽ a < b ⩽ 1 satisfy b − a ⩾ 4/2^{m}, and there exists an affine mapping A : ℝ → ℓ_{p} such that

sup_{x∈[a,b]} \frac{∥f_{m}(x) − A(x)∥_{p}}{(b − a)/2} ⩽ \frac{1}{8m^{1/p}} .  (59)

There exists k ∈ {1, …, m} such that 4/2^{k} ⩽ b − a < 8/2^{k}. Because b − a ⩾ 4/2^{k} there is j ∈ {0, …, 2^{k−1} − 1} such that [j/2^{k−1}, (j + 1)/2^{k−1}] ⊆ [a, b]. Now, since A is affine and f_{k−1} is affine on [j/2^{k−1}, (j + 1)/2^{k−1}],

\frac{b − a}{8m^{1/p}} ⩾^{(59)} ∥f_{m} (\frac{j/2^{k−1} + (j + 1)/2^{k−1}}{2} ) − \frac{f_{m} (j/2^{k−1}) + f_{m} ((j + 1)/2^{k−1})}{2}∥_{p}

= ∥f_{k} (\frac{2j + 1}{2^{k}}) − f_{k−1} (\frac{2j + 1}{2^{k}})∥_{p} =^{(58)} \frac{1}{m^{1/p}2^{k}} ,

in contradiction to the fact that b − a < 8/2^{k}. □

Lemma 4.2. Fix p ∈ [2, ∞) and m, n ∈ ℕ. There exists a 1-Lipschitz function g : ℝ → ℓ_{p}^{m+1} such that for every y ∈ ℝ with |y| ⩽ 1/\sqrt{n}, every r ⩾ 32/ (\sqrt{n}2^{m}), and every affine mapping A : ℝ → ℓ_{p}^{m+1},

sup_{x∈[y−r,y+r]} \frac{∥g(x) − A(x)∥_{p}}{r} > \frac{1}{16m^{1/p}} .

Proof. Let {e_{1}, …, e_{m+1}} denote the standard basis of ℓ_{p}^{m+1}. Define g : ℝ → ℓ_{p}^{m+1} by

g(x) =^{def} \{ \begin{matrix}\frac{4}{\sqrt{n}}f (\frac{\sqrt{n}}{4}x + \frac{1}{2}) & if |x| ⩽ \frac{2}{\sqrt{n}}, \\ (|x| − \frac{2}{\sqrt{n}}) e_{m+1} & otherwise. \end{matrix}

where f = f_{m} : [0, 1] → ℓ_{p}^{m} = span({e_{1}, …, e_{m}}) is the function from Lemma 4.1. Because f is 1-Lipschitz and f(0) = f(1) = 0, one checks that g is 1-Lipschitz.

Fix an affine mapping A : ℝ → ℓ_{p} and take y ∈ ℝ satisfying |y| ⩽ 1/\sqrt{n}. Suppose that r ⩾ 32/ (\sqrt{n}2^{m}). If in addition r ⩽ 8/\sqrt{n} then write [y − r, y + r] ∩ [−2/\sqrt{n}, 2/\sqrt{n}] = [a, b], where b − a ⩾ r/2 ⩾ 16/ (\sqrt{n}2^{m}). By Lemma 4.1,

sup_{x∈[y−r,y+r]} \frac{∥g(x) − A(x)∥_{p}}{r} ⩾ sup_{x∈[a,b]} \frac{∥\frac{4}{\sqrt{n}}f (\frac{\sqrt{n}}{4}x + \frac{1}{2}) − A(x)∥_{p}}{2(b − a)}

= \frac{1}{2} sup_{z∈[ \frac{\sqrt{n}}{4} a+ \frac{1}{2} , \frac{\sqrt{n}}{4} b+ \frac{1}{2} ]} \frac{∥f(z) − \frac{\sqrt{n}}{4}A (\frac{4}{\sqrt{n}}z − \frac{2}{\sqrt{n}})∥_{p}}{(\frac{\sqrt{n}}{4}b − \frac{\sqrt{n}}{4}a) /2} > \frac{1}{16m^{1/p}} .

It remains to deal with the case r > 8/\sqrt{n}. In this case y − r, y + r ∉ [−2/\sqrt{n}, \sqrt{n}], so

⟨g(y ± r), e_{m+1}⟩ = |y ± r| − \frac{2}{\sqrt{n}} ⩾ r − |y| − \frac{2}{\sqrt{n}} ⩾ r − \frac{3}{\sqrt{n}} > \frac{5}{\sqrt{n}} > 0.

Assume for contradiction that ∥g(x) − A(x)∥_{p} ⩽ r/(16m^{1/p}) for all x ∈ [y − r, y + r]. Then, since A is affine,

⟨A(y), e_{m+1}⟩ = \frac{⟨A(y + r), e_{m+1}⟩ + ⟨A(y − r), e_{m+1}⟩}{2} ⩾ r − \frac{3}{\sqrt{n}} − \frac{r}{16m^{1/p}} .

Hence,

⟨g(y), e_{m+1}⟩ ⩾ ⟨A(y), e_{m+1}⟩ − ∥g(y) − A(y)∥_{p} ⩾ (1 − \frac{1}{8m^{1/p}} ) r − \frac{3}{\sqrt{n}} > \frac{r}{2} − \frac{3}{\sqrt{n}} > \frac{1}{\sqrt{n}},

contradicting the fact that, since |y| ⩽ 2/\sqrt{n}, we have ⟨g(y), e_{m+1}⟩ = 0. □

We now use the function g of Lemma 4.2 as a building block of a function F : ℓ_{2}^{n} → ℓ_{2}^{n}(ℓ_{p}^{m+1}) whose affine approximability properties deteriorate with the dimension n. This step is similar to an argument in the proof of Theorem 2.7 in [2].

Lemma 4.3. For every p ∈ [2, ∞) and every m, n ∈ ℕ there exists a 1-Lipschitz function F : ℓ_{2}^{n} → ℓ_{2}^{n}(ℓ_{p}^{m+1}) such that for every

r ⩾ \frac{32}{\sqrt{n}2^{m}}

and every affine mapping A : ℓ_{2}^{n} → ℓ_{2}^{n}(ℓ_{p}^{m+1}),

sup_{x∈y+rB_{ℓ^{n}_{2}}} \frac{∥F (x) − A(x)∥_{ℓ_{2}^{n}(ℓ_{p}^{m+1})}}{r} > \frac{1}{16m^{1/p}} .

Consequently, if we set ε = \frac{1}{16m^{1/p}} then for X = ℓ_{2}^{n} and Y = ℓ_{2}^{n}(ℓ_{p}^{m+1}),

r^{X→Y} (ε) ⩽ \frac{32}{\sqrt{n}2^{1/(16ε)^{p}}} .

Proof. Let g : ℝ → ℓ_{p}^{m+1} be the function from Lemma 4.2. Since g is 1-Lipschitz, if we define F (x_{1}, …, x_{n}) = (g(x_{1}), …, g(x_{n})) then F : ℓ_{2}^{n} → ℓ_{2}^{n}(ℓ_{p}^{m+1}) is 1-Lipschitz. Fixing r ⩾ 32/ (\sqrt{n}2^{m}), suppose that A : ℓ_{2}^{n} → ℓ_{2}^{n}(ℓ_{p}^{m+1}) is affine and y+rB_{ℓ_{2}^{n}} ⊆ B_{ℓ_{2}^{n}}. Since ∥y∥_{2} < 1, there exists i ∈ \{1, …, n\} such that |y_{i}| < 1/\sqrt{n}. Writing A(x) = (A_{1}(x), …, A_{n}(x)), define A′_{i} : ℝ → ℓ_{p}^{m+1} by A′_{i}(t) = A_{i} (∑_{j∈{1,...,n}∖{i}} y_{j}e_{j} + te_{i}). By Lemma 4.2 we know that

sup_{x∈y+rB_{ℓ^{n}_{2}}} \frac{∥F (x) − A(x)∥_{ℓ_{2}^{n}(ℓ_{p}^{m+1})}}{r} ⩾ sup_{t∈[y_{i}−r,y_{i}+r]} \frac{∥g(t) − A′_{i}(t)∥_{p}}{r} > \frac{1}{16m^{1/p}} ,

where we used that fact that y + [−r, r]e_{i} ⊆ y + rB_{ℓ_{2}^{n}}. □

References

[1] 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.

[2] S. Bates, W. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geometric and Functional Analysis, 9:1092–1127, 1999.

[3] Y. Benyamini. The uniform classification of Banach spaces. In Texas functional analysis seminar 1984– 1985 (Austin, Tex.), Longhorn Notes, pages 15–38. Univ. Texas Press, Austin, TX, 1985.

[4] 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.

[5] 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.

[6] D. L. Burkholder. Martingales and singular integrals in Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 233–269. North-Holland, Amsterdam, 2001.

[7] 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.

[8] J. Diestel, H. Jarchow, and A. Tonge. Absolutely summing operators, volume 43 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995.

[9] 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.

[10] P. Enflo. Banach spaces which can be given an equivalent uniformly convex norm. Israel J. Math., 13:281–288, 1973.

[11] A. Eskin, D. Fisher, and K. Whyte. Quasi-isometries and rigidity of solvable groups. Pure Appl. Math. Q., 3(4, part 1):927–947, 2007.

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

[13] I. Gelfand. Abstrakte Funktionen und lineare Operatoren. Mat. Sb., 4(2):235–286, 1938.

[14] O. Giladi, A. Naor, and G. Schechtman. Bourgain’s discretization theorem. Preprint available at

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

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

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

[17] R. C. James. Uniformly non-square Banach spaces. Ann. of Math. (2), 80:542–550, 1964.

[18] R. C. James. Super-reflexive Banach spaces. Canad. J. Math., 24:896–904, 1972.

[19] 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.

[20] W. B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel J. Math., 54(2):129–138, 1986.

[21] A. Naor. Geometric problems in non-linear functional analysis. Master’s thesis, Hebrew University, 1998.

[22] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4):326–350, 1975.

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

Courant Institute, New York University, New York NY 10012

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

Courant Institute, New York University, New York NY 10012

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