IMPROVED BOUNDS IN THE METRIC COTYPE INEQUALITY FOR BANACH SPACES

OHAD GILADI, MANOR MENDEL, AND ASSAF NAOR

Abstract. It is shown that if (X, ∥·∥_{X}) is a Banach space with Rademacher cotype q then for every integer n there exists an even integer m ≲ n^{1+ \frac{1}{q}} such that for every f : ℤ_{m}^{n} → X we have

∑_{j=1}^{n} 𝔼_{x}[ ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} ] ≲ m^{q}𝔼_{ε,x}[ ∥f(x + ε) − f(x)∥_{X}^{q} ],  (1)

where the expectations are with respect to uniformly chosen x ∈ ℤ_{m}^{n} and ε ∈ {−1, 0, 1}^{n}, and all the implied constants may depend only on q and the Rademacher cotype q constant of X. This improves the bound of m ≲ n^{2+ \frac{1}{q}} from [10]. The proof of (1) is based on a “smoothing and approximation” procedure which simplifies the proof of the metric characterization of Rademacher cotype of [10]. We also show that any such “smoothing and approximation” approach to metric cotype inequalities must require m ≳ n^{\frac{1}{2} + \frac{1}{q}}.

Contents

1. Introduction  2
1.1. The smoothing and approximation scheme  3
1.2. A lower bound on smoothing and approximation with general kernels  6
1.3. The relation to nonembeddability results and some open problems  7
2. Proof of Theorem 1.2  9
3. Proof of Lemma 2.1  13
3.1. Estimates for the bivariate Bernoulli numbers  13
3.2. Some combinatorial identities  14
3.3. Putting things together  17
4. Lower bounds  20
4.1. A lower bound for general convolution kernels: Proof of Proposition 4.1  20
4.2. A sharp lower bound for E_{j} averages: Proof of Proposition 4.2  23
4.3. Symmetrization  25
References  27

2010 Mathematics Subject Classification. 46B80,46B85,51F99,05C12.

1. Introduction

A metric space (ℳ , d_{ℳ} ) is said [10] to have metric cotype q > 0 with constant Γ > 0 if for every integer n there exists an even integer m such that for every f : ℤ_{m}^{n} → X we have

∑_{j=1}^{n} 𝔼_{x}[d_{ℳ} (f (x + \frac{m}{2}e_{j}) , f(x))^{q} ] ⩽ Γ^{q}m^{q}𝔼_{ε,x}[d_{ℳ} (f(x + ε), f(x))^{q} ].  (2)

In (2) the expectations are taken with respect to x chosen uniformly at random from the discrete torus ℤ_{m}^{n}, and ε chosen uniformly at random from {−1, 0, 1}^{n} (the ℓ_{∞} generators of ℤ_{m}^{n}). Also, in (2) and in what follows, {e_{j}}_{j=1}^{n} denotes the standard basis of ℤ_{m}^{n}.

A Banach space (X, ∥ · ∥_{X}) is said to have Rademacher cotype q > 0 if there exists a constant C < ∞ such that for every n ∈ ℕ and for every x_{1}, x_{2}, ...., x_{n} ∈ X,

∑_{j=1}^{n} ∥x_{j}∥_{X}^{q} ⩽ C^{q}𝔼_{ε} [∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{q}] .  (3)

X is said to have Rademacher type p > 0 if there exists a constant T < ∞ such that for every n ∈ ℕ and for every x_{1}, x_{2}, ...., x_{n} ∈ X,

𝔼_{ε} [∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{p}] ⩽ T^{p} ∑_{j=1}^{n} ∥x_{j}∥_{X}^{p}.  (4)

The smallest possible constants C, T in (3), (4) are denoted C_{p}(X), T_{p}(X), respectively. We refer to [13, 7] for more information on the notions of type and cotype, though the present paper requires minimal background of this theory. We shall use throughout standard Banach space notation and terminology, as appearing in, say, [17].

The following theorem was proved in [10]:

Theorem 1.1 ([10]). A Banach space (X, ∥ · ∥_{X}) has Rademacher cotype q if and only if it has metric cotype q.

Thus, for Banach spaces the linear notion of Rademacher cotype q is equivalent to the notion of metric cotype q, which ignores all the structure of the Banach space except for its metric properties. Theorem 1.1 belongs to a comprehensive program, first formulated by Bourgain in [2], which is known as the Ribe program, whose goal is to recast the local theory of Banach spaces as a purely metric theory. A byproduct of this program is that linear properties such as Rademacher cotype can be made to make sense in general metric spaces, with applications to metric geometry in situations which lack any linear structure. We refer to [10] and the references therein for more information on the Ribe program and its applications.

Definition (2) and Theorem 1.1 suppress the value of m, since it is irrelevant for the purpose of a metric characterization of Rademacher cotype. Nevertheless, good bounds on m are important for applications of metric cotype to embedding theory, some of which will be recalled in Section 1.3. It was observed in [10] that if the metric space ℳ contains at least two points then the value of m in (2) must satisfy m ≳ n^{1/q} (where the implied constant depends only on Γ). If X is a Banach space with Rademacher type p > 1 and Rademacher cotype q, then it was shown in [10] that X satisfies the metric cotype q inequality (2) for every m ⩾ n^{1/q} (in which case Γ depends only on p, q, T_{p}(X), C_{q}(X)). Such a sharp bound on m is crucial for certain applications [10, 11] of metric cotype, and perhaps the most important open problem in [10] is whether this sharp bound on m holds true even when the condition that X has type p > 1 is dropped. The bound on m from [10] in Theorem 1.1 is m ≳ n^{2+ \frac{1}{q}}. Our main result improves this bound to m ≳ n^{1+ \frac{1}{q}}:

Theorem 1.2. Let X be a Banach space with Rademacher cotype q ⩾ 2. Then for every n ∈ ℕ, every integer m ⩾ 13n^{1+ \frac{1}{q}} which is divisible by 4, and every f : ℤ_{m}^{n} → X, we have

∑_{j=1}^{n} 𝔼_{x}[ ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} ] ≲_{X} m^{q}𝔼_{ε,x}[ ∥f(x + ε) − f(x)∥_{X}^{q} ].  (5)

In (5), and in what follows, ≲_{X}, ≳_{X} indicate the corresponding inequalities up to constants which may depend only on q and C_{q}(X). Similarly, we will use the notation ≲_{q}, ≳_{q} to indicate the corresponding inequalities up to constants which may depend only on q.

Though a seemingly modest improvement over the result of [10], the strengthened metric cotype inequality (5) does yield some new results in embedding theory, as well as a new proof of a result of Bourgain [3]; these issues are discussed in Section 1.3. More importantly, our proof of Theorem 1.2 is based on a better understanding and sharpening of the underlying principles behind the proof of Theorem 1.1 in [10]. As a result, we isolate here the key approach to the metric characterization of Rademacher cotype in [10], yielding a simpler and clearer proof of Theorem 1.1, in addition to the improved bound on m. This is explained in detail in Section 1.1. While the bound m ≳ n^{1+ \frac{1}{q}} is far from the conjectured optimal bound m ⩾ n^{1/q}, our second main result is that (a significant generalization of) the scheme for proving Theorem 1.1 and Theorem 1.2 (which is implicit in [10] and formulated explicitly here) cannot yield a bound better than m ≳ n^{\frac{1}{2} + \frac{1}{q}}. Our method for proving this lower bound is presented in Section 4, and might be of independent interest.

We remark in passing that in [10] a one parameter family of variants of the notion of metric cotype is studied, corresponding to raising the distances to powers other than q, and modifying the right-hand side of (2), (5) accordingly (we refer to [10] for more details). The argument presented here can be modified to yield simplifications and improvements of all the corresponding variants of Theorem 1.1. While these variants are crucial for certain applications of metric cotype [10, 8], we chose to present Theorem 1.2 only for the simplest “vanilla” version of metric cotype (2), for the sake of simplicity of exposition.

Notation for measures. Since our argument uses a variety of averaging procedures over several spaces, it will be convenient to depart from the expectation notation that we used thus far. In particular, throughout this paper μ will denote the uniform probability measure on ℤ_{m}^{n} (m, n will always be clear from the context), σ will denote the uniform probability measure on {−1, 0, 1}^{n}, and τ will denote the uniform probability measure on {−1, 1}^{n}.

1.1. The smoothing and approximation scheme. We start with a description of an abstraction of the approach of [10] to proving the metric characterization of Rademacher cotype of Theorem 1.1.

For a Banach space X, a function f : ℤ_{m}^{n} → X and a probability measure ν on ℤ_{m}^{n}, we use the standard notation for the convolution f ∗ ν : ℤ_{m}^{n} → X:

f ∗ ν(x) = ∫_{ℤ_{m}^{n}} f(x − y)dν(y).

Assume that we are given n probability measures ν_{1}, …, ν_{n} on ℤ_{m}^{n}, and two additional probability measures β_{1}, β_{2} on the pairs in ℤ_{m}^{n} × ℤ_{m}^{n} of ℓ_{∞} distance 1, i.e., on the set

E_{∞}(ℤ_{m}^{n}) =^{def} {(x, y) ∈ ℤ_{m}^{n} × ℤ_{m}^{n} : x − y ∈ {−1, 0, 1}^{n}}.  (6)

For A, S, q ⩾ 1, we shall say that the measures ν_{1}, …, ν_{n}, β_{1}, β_{2} are a (q, A, S)-smoothing and approximation scheme on ℤ_{m}^{n} if for every Banach space (X, ∥ · ∥_{X}) and every f : ℤ_{m}^{n} → X we have the following two inequalities:

(A) Approximation property:

\frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν_{j} − f∥_{X}^{q} dμ(x) ⩽ A^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{1}(x, y).  (7)

(S) Smoothing property:

∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j}))∥_{X}^{q} dτ(ε)dμ(x)

⩽ S^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{2}(x, y). (8)

Often, when the underlying space ℤ_{m}^{n} is obvious from the context, we will not mention it explicitly, and simply call ν_{1}, …, ν_{n}, β_{1}, β_{2} a (q, A, S)-smoothing and approximation scheme. In some cases, however, it will be convenient to mention the underlying space ℤ_{m}^{n} so as to indicate certain restrictions on m.

We introduce these properties for the following simple reason. We wish to deduce the metric cotype inequality (5) from the Rademacher cotype inequality (3). In essence, the Rademacher cotype condition (3) is the same as the metric cotype inequality (5) when restricted to linear mappings. This statement is not quite accurate, but it suffices for the purpose of understanding the intuition behind the ensuing argument; we refer to Section 5.1 in [10] for the precise argument. In any case, it stands to reason that in order to prove (5) from (3), we should first smooth out f, so that it will be locally well approximated (on average) by a linear function. As we shall see momentarily, it turns out that the appropriate way to measure the quality of such a smoothing procedure is our smoothing property (8). Of course, while the averaging operators corresponding to convolution with the measures ν_{1}, …, ν_{n} yield a better behaved function, we still need the resulting averaged function to be close enough to the original function f, so as to deduce a meaningful inequality such as (5) for f itself. Our approximation property (7) is what’s needed for carrying out such an approach.

The above general scheme is implicit in [10]. Once we have isolated the crucial approximation and smoothing properties, it is simple to see how they relate to metric cotype. For this purpose, assume that the Banach space X has Rademacher cotype q, and for each x ∈ ℤ_{m}^{n} apply the Rademacher cotype q inequality to the vectors {f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j})}_{j=1}^{n} (where the averaging in (3) is with respect to ε ∈ {−1, 1}^{n}, rather than ε ∈ {−1, 0, 1}^{n}; it is an easy standard fact that these two variants of Rademacher cotype q coincide):

∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j}))∥_{X}^{q} dτ(ε)

≳_{X} ∑_{j=1}^{n} ∥f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j})∥_{X}^{q} . (9)

The triangle inequality, combined with the convexity of the function t ↦ t^{q}, implies that for every x ∈ ℤ_{m}^{n} and j ∈ {1, …, n} we have

∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} ⩽ 3^{q−1} ∥f ∗ ν_{j} (x + \frac{m}{2}e_{j}) − f ∗ ν_{j}(x)∥_{X}^{q}

+ 3^{q−1} ∥f ∗ ν_{j} (x + \frac{m}{2}e_{j}) − f (x + \frac{m}{2}e_{j})∥_{X}^{q} + 3^{q−1}∥f ∗ ν_{j}(x) − f(x)∥_{X}^{q}. (10)

At the same time (recalling that m is divisible by 4), a combination of the triangle inequality and Hölder’s inequality bounds the first term in the right hand side of (10) as follows:

∥f ∗ ν_{j} (x + \frac{m}{2}e_{j}) − f ∗ ν_{j}(x)∥_{X}^{q} ⩽ (∑_{t=1}^{m/4} ∥ν_{j} ∗ f(x + 2te_{j}) − ν_{j} ∗ f(x + 2(t − 1)e_{j})∥_{X} )^{q}

⩽ (\frac{m}{4})^{q−1} ∑_{t=1}^{m/4} ∥ν_{j} ∗ f(x + 2te_{j}) − ν_{j} ∗ f(x + 2(t − 1)e_{j})∥_{X}^{q} . (11)

Substituting (11) into (10), summing up over j ∈ {1, …, n}, and integrating with respect to x ∈ ℤ_{m}^{n} while using the translation invariance of the measure μ, we deduce the inequality

∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x) ≲ 3^{q} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν_{j} − f∥_{X}^{q} dμ

+ m^{q} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j})∥_{X}^{q} dμ(x). (12)

We can now bound the first term in the right hand side of (12) using the approximation property (7), and the second term in the right hand side of (12) using (9) and the smoothing property (8). The inequality thus obtained is

∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x)

≲_{X} (nA^{q} + m^{q}S^{q}) ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{3}(x, y), (13)

where β_{3} = (β_{1} + β_{2})/2. Note in passing that when m ≲ A, an inequality such as (13), with perhaps a different measure β_{3} on E_{∞}(ℤ_{m}^{n}), is a consequence of the triangle inequality, and therefore holds trivially on any Banach space X. Thus, for our purposes, we may assume throughout that a (q, A, S)-smoothing and approximation scheme on ℤ_{m}^{n} satisfies m ≳ A.

Assuming that

m ≳ \frac{A}{S} · n^{1/q},  (14)

inequality (13) becomes

∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x) ≲_{X} S^{q}m^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{3}(x, y). (15)

If we could come up with a smoothing and approximation scheme for which S ≲ 1, and m satisfied (14), then inequality (15) would not quite be the desired metric cotype inequality (5), but it would be rather close to it. The difference is that the probability measure β_{3} is not uniformly distributed on all ℓ_{∞} edges E_{∞}(ℤ_{m}^{n}), as required in (5). Nevertheless, for many measures β_{3}, elementary triangle inequality and symmetry arguments can be used to “massage” inequality (15) into the desired inequality (5). This last point is a technical issue, but it is not the heart of our argument: we wish to design a smoothing and approximation scheme satisfying S ≲ 1 with A as small as possible. In [10] such a scheme was designed with A ≲ n^{2}. Here we carefully optimize the approach of [10] to yield a smoothing and approximation scheme with A ≲ n, in which case (14) becomes the desired bound m ≳ n^{1+ \frac{1}{q}}.

The bounds that we need in order to establish this improved estimate on m are based on the analysis of some quite delicate cancelations; indeed the bounds that we obtain are sharp for our smoothing and approximation scheme, as discussed in Section 1.2. In proving such sharp bounds, a certain bivariate extension of the Bernoulli numbers arises naturally; these numbers, together with some basic asymptotic estimates for them, are presented in Section 3.1. The cancelations in the Rademacher sums corresponding to our convolution kernels are analyzed via certain combinatorial identities in Section 3.2.

1.2. A lower bound on smoothing and approximation with general kernels. One might wonder whether our failure to prove the bound m ≳ n^{1/q} without the non-trivial Rademacher type assumption is due to the fact we chose the wrong smoothing and approximation scheme. This is not the case. In Section 4 we show that any approach based on smoothing and approximation is doomed to yield a sub-optimal dependence of m on n (assuming that the conjectured n^{1/q} bound is indeed true). Specifically, we show that for any (q, A, S)-smoothing and approximation scheme on ℤ_{m}^{n}, with m ≳ A, we must have AS ≳_{q} \sqrt{n}. Thus the bound S ≲ 1 forces the bound A ≳_{q} \sqrt{n}, and correspondingly (14) becomes m ≳_{q} n^{\frac{1}{2} + \frac{1}{q}}. Additionally, we show in Section 4 that for the specific smoothing and approximation scheme used here, the bound m ≳ n^{1+ \frac{1}{q}} is sharp.

It remains open what is the best bound on m that is achievable via a smoothing and approximation scheme. While this question is interesting from an analytic perspective, our current lower bound shows that we need to use more than averaging with respect to positive measures in order to prove the desired bound m ≳ n^{1/q}.

Note that the lower bound m ≳_{q} n^{\frac{1}{2} + \frac{1}{q}} for smoothing and approximation schemes rules out the applicability of this method to some of the most striking potential applications of metric cotype to embedding theory in the coarse, uniform, or quasisymmetric categories, as explained in Section 1.3; these applications rely crucially on the use of a metric cotype inequality with m ≍ n^{1/q}.

The cancelation that was exploited in [10] in order to prove the sharp bound on m in the presence of non-trivial Rademacher type was also related to smoothing properties of convolution kernels, but with respect to signed measures: the smoothed Rademacher sums in the left hand side of (8) are controlled in [10] via the Rademacher projection, and the corresponding smoothing inequality (for signed measures) is proved via an appeal to Pisier’s K-convexity theorem [12]. It would be of great interest to understand combinatorially/geometrically the cancelations that underly the estimate m ⩾ n^{1/q} from [10], though there seems to be a lack of methods to handle smoothing properties of signed convolution kernels in spaces with trivial Rademacher type and finite Rademacher cotype.

1.3. The relation to nonembeddability results and some open problems. We recall some standard terminology. Let (X, d_{X}) and (Y, d_{Y}) be metric spaces. X is said to embed with distortion D into Y if there exists a mapping f : X → Y and (scaling factor) λ > 0, such that for all x, y ∈ X we have λd_{X}(x, y) ⩽ d_{Y} (f(x), f(y)) ⩽ Dλd_{X}(x, y). X is said to embed uniformly into Y if there exists an into homeomorphism f : X → Y such that both f and f^{−1} are uniformly continuous. X is said to embed coarsely into Y if there exists a mapping f : X → Y and two non-decreasing functions α, β : [0, ∞) → [0, ∞) such that lim_{t→∞} α(t) = ∞, and for all x, y ∈ X we have α(d_{X}(x, y)) ⩽ d_{Y} (f(x), f(y)) ⩽ β(d_{X}(x, y)). X is said to admit a quasisymmetric embedding into Y if there exists a mapping f : X → Y and an increasing (modulus) η : (0, ∞) → (0, ∞) such that for all distinct x, y, z ∈ X we have \frac{d_{Y} (f(x),f(y))}{d_{Y} (f(x),f(z)} ⩽ η (\frac{d_{X}(x,y)}{d_{X}(x,z)}).

For a Banach space X, let q_{X} denote the infimum over those q ⩾ 2 such that X has Rademacher (equiv. metric) cotype q. It was shown in [10, 11] that if X, Y are Banach spaces, Y has Rademacher type p > 1, and X embeds uniformly, coarsely, or quasisymmetrically into Y, then q_{X} ⩽ q_{Y}. Thus, under the Rademacher type > 1 assumption on the target space, Rademacher cotype q is an invariant that is stable under embeddings of Banach spaces, provided that the embedding preserves distances in a variety of (seemingly quite weak) senses. The role of the assumption that Y has non-trivial Rademacher type is via the metric cotype inequality with optimal m: the proofs of these results only use that Y satisfies the metric cotype q inequality (2) for some m ≍ n^{1/q} (under this assumption, Y can be a general metric space and not necessarily a Banach space). This fact motivates our conjecture that for any Banach space Y with Rademacher cotype q, the metric cotype inequality (5) holds for every m ≳_{Y} n^{1/q}. The same assertion for general metric spaces of metric cotype q is too much to hope for; see [15].

Perhaps the simplest Banach spaces for which we do not know how to prove a sharp metric cotype inequality are L_{1} and the Schatten-von Neumann trace class S_{1} (see, e.g., [17]). Both of these spaces have Rademacher cotype 2 (for S_{1} see [14]), yet the currently best known bound on m in the metric cotype inequality (5) (with q = 2) for both of these spaces is the bound m ≳ n^{3/2} obtained here. The above embedding results in the uniform, coarse or quasisymmetric categories do hold true for embeddings into L_{1} (i.e., a Banach space X that embeds in one of these senses into L_{1} satisfies q_{X} = 2). This fact is due to an ad-hoc argument, which fails for S_{1} (see Section 8 in [10] for an explanation). We can thus ask the following natural questions (many of which were already raised in [10]):

Question 1. Can a Banach space X with q_{X} = ∞ admit a uniform, coarse, or quasisymmetric embedding into S_{1}? Can L_{r} admit such an embedding when r > 2? More ambitiously, can a Banach space X with q_{X} > 2 embed in one of these senses into S_{1}? In greatest generality: can a Banach space X embed in one of these senses into a Banach space Y with q_{Y} < q_{X}?

Consider for example the Banach space of null sequences c_{0}, which has infinite Rademacher cotype. By [10, 11] c_{0} does not admit a uniform, coarse, or quasisymmetric embedding into a Banach space with non-trivial Rademacher type (or L_{1}). By [6], c_{0} does not admit a uniform or coarse embedding into any reflexive Banach space. Can c_{0} embed in one of these senses into S_{1}?

Question 2. Does S_{1} admit a uniform, coarse, or quasisymmetric embedding into a Banach space Y with Rademacher type p > 1? More ambitiously, does S_{1} embed in one of these senses into Banach space Y with Rademacher type p > 1 and q_{Y} = 2? In greatest generality: does every Banach space X embed in one of these senses into a Banach space Y with Rademacher type p > 1? Perhaps we can even ensure in addition that q_{Y} = q_{X}?

Question 2 relates to Question 1 since embeddings into spaces with type > 1 would allow us to use the nonembeddability results of [10].

While the improved bound on m in Theorem 1.2 does not solve any of these fundamental questions, it does yield new restrictions on the possible moduli of embeddings in the uniform, coarse, or quasisymmetric categories. Instead of stating our nonembedding corollaries in greatest generality, let us illustrate our (modest) improved nonembeddability results for snowflake embeddings of L_{4} into S_{1} (this is just an illustrative example; the method of [10] yields similar results for embeddings of any Banach space X with q_{X} > 2 into S_{1}, and S_{1} itself can be replaced by general Banach spaces of finite cotype). Take θ ∈ (0, 1) and assume the metric space (L_{4}, ∥x − y∥_{4}^{θ}) admits a bi-Lipschitz embedding into S_{1}. Our strong conjectures imply that this cannot happen, but at present the best we can do is give bounds on θ. An application of Theorem 1.2 shows that θ ⩽ 4/5, i.e., we have a definite quantitative estimate asserting that a uniform embedding of L_{4} into S_{1} must be far from bi-Lipschitz. The previous bound from [10] for S_{1} was m = n^{5/2}, yielding θ ⩽ 8/9. Our lower bound shows that by using a smoothing and approximation scheme we cannot hope to get a bound of θ < 2/3.

Turning to bi-Lipschitz embeddings, consider the grid {0, 1, …, m}^{n} ⊆ ℝ^{n}, equipped with the ℓ_{∞}^{n} metric. We denote this metric space by [m]_{∞}^{n}. Bourgain [3] proved that if Y is a Banach space with Rademacher cotype q, then any embedding of [n^{1+ \frac{1}{q}} ]_{∞}^{n} into Y incurs

distortion ≳_{Y} n^{1/q}. The same result follows from Theorem 1.2, while the previous estimate on m from [10] only yields the weaker distortion lower bound of ≳_{Y} n^{\frac{q+1}{q(2q+1)}} for embeddings of [n^{1+ \frac{1}{q}} ]_{∞}^{n} into Y. The sharp bound on m from [10] when Y has Rademacher type > 1

implies that in this case, any embedding of [n^{1/q}]_{∞}^{n} into Y incurs distortion ≳ n^{1/q} (where the implied constant is now allowed to depend also on the Rademacher type parameters of Y). Our main conjecture implies the same improvement of Bourgain’s result without the assumption that Y has non-trivial Rademacher type.

Bourgain’s theorem [3] is part of his more general investigation of embeddings of ε-nets in unit balls of finite dimensional normed spaces. Bourgain’s approach in [3] is based on ideas similar to ours, that are carried out in the continuous domain. Specifically, given a mapping f : [m]_{∞}^{n} → Y, he finds a mapping g : ℝ^{n} → Y which is L-Lipschitz and close in an appropriate sense (depending on L, m, n) to f on points of the grid [m]_{∞}^{n}. Once this is achieved, it is possible to differentiate g to obtain the desired distortion lower bound. Bourgain’s approximate Lipschitz extension theorem (an alternative proof of which was found in [1]) is a continuous version of a smoothing and approximation scheme; it seems plausible that our method in Section 4 for proving impossibility results for such schemes can be used to prove similar restrictions on Bourgain’s approach to approximate Lipschitz extension. When Y has non-trivial Rademacher type, the improvement in [10] over Bourgain’s nonembeddability result for grids is thus based on a more delicate cancelation than was used in [3, 1].

Question 3. Is it true that for any Banach space Y of Rademacher cotype q, any embedding of [n^{1/q}]_{∞}^{n} into Y incurs distortion ≳_{Y} n^{1/q} (if true, this is a sharp bound). Specializing to the Schatten-von Neumann trace class S_{1}, we do not even know whether the distortion of [\sqrt{n}]_{∞}^{n} in S_{1} is ≳ \sqrt{n}. Theorem 1.2 implies a distortion lower bound of ≳ n^{1/6}, while the bound on m from [10] only yields a distortion lower bound of ≳ n^{1/10}. Our results in Section 4 show that one cannot get a distortion lower bound asymptotically better than n^{1/4} by using smoothing and approximation schemes.

We did not discuss here metric characterizations of Rademacher type. We refer to [9] for more information on this topic. We would like to mention, however, that our approach to Theorem 1.2 is likely to yields improved bounds in [9] as well.

Acknowledgements. O. G. was partially supported by NSF grant CCF-0635078. M. M. was partially supported by ISF grant no. 221/07, BSF grant no. 2006009, and a gift from Cisco research center. A. N. was supported in part by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

2. Proof of Theorem 1.2

For n ∈ ℕ denote [n] = {1, …, n}. When B ⊆ [n], and x ∈ ℤ_{m}^{B}, we will sometimes slightly abuse notation by treating x as an element of ℤ_{m}^{n}, with the understanding that for i ∈ [n]\B we have x_{i} = 0. For y ∈ ℤ_{m}^{n}, we denote by y_{B} the restriction of y to the coordinates in B.

As in [10], for j ∈ [n] and an odd integer k < m/2, we define S(j, k) ⊆ ℤ_{m}^{n} by

S(j, k) =^{def} {y ∈ [−k, k]^{n} ⊆ ℤ_{m}^{n}: y_{j} is even ∧ ∀ℓ ∈ [n] \ {j} y_{ℓ} is odd}.  (16)

The parameter k will be fixed throughout the ensuing argument, and will be specified later. For every j ∈ [n] let ν_{j} be the uniform probability measure on S(j, k). Following the notation of [10], for a Banach space (X, ∥ · ∥_{X}) and f : ℤ_{m}^{n} → X, we write f ∗ ν_{j} = E_{j}f, that is,

E_{j}f(x) =^{def} \frac{1}{μ(S(j, k))} ∫_{S(j,k)} f(x + y)dμ(y).  (17)

Recall that E_{∞}(ℤ_{m}^{n}), defined in (6), is the set of all ℓ_{∞} edges of ℤ_{m}^{n}. Similarly, we denote the ℓ_{1} edges of ℤ_{m}^{n} by E_{1}(ℤ_{m}^{n}), i.e.,

E_{1}(ℤ_{m}^{n}) =^{def} {(x, y) ∈ ℤ_{m}^{n} × ℤ_{m}^{n} : x − y ∈ {±e_{1}, …, ±e_{n}}}.  (18)

Clearly E_{1}(Z_{m}^{n}) ⊆ E_{∞}(Z_{m}^{n}).

Let β_{1}^{∘} denote the uniform probability distribution on the pairs (x, y) ∈ E_{∞}(ℤ_{m}^{n}) with x − y ∈ {−1, 1}^{n}, and let β_{1}^{∘∘} denote the uniform probability distribution on E_{1}(ℤ_{m}^{n}). We shall consider the probability measure on E_{∞}(ℤ_{m}^{n}) given by β_{1} = (β_{1}^{∘} + β_{1}^{∘∘})/2.

Lemma 5.1 in [10] implies that for all q ⩾ 1 and f : ℤ_{m}^{n} → X we have:

\frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥E_{j}f − f∥_{X}^{q} dμ ≲ (2k)^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{1}(x, y).  (19)

Inequality (19) corresponds to the approximation property (7), with A ≲ k. The relevant smoothing inequality is the main new ingredient in our proof of Theorem 1.2, and it requires a more delicate choice of probability measure β_{2} on E_{∞}(ℤ_{m}^{n}). If (x, y) ∈ E_{∞}(ℤ_{m}^{n}) then x − y ∈ {−1, 0, 1}^{n}. Let S = {i ∈ [n] : x_{i} = y_{i}}, and define

β_{2}(x, y) =^{def} \frac{1}{Z} · \frac{(n/k)^{q|S|}}{2^{n−|S|}m^{n}\binom{n}{|S|}},  (20)

where Z is a normalization factor ensuring that β_{2} is a probability measure, i.e.,

Z = ∑_{ℓ=0}^{n} (\frac{n}{k})^{qℓ} ≍ 1,  (21)

provided that, say,

k ⩾ 2n.  (22)

Our final choice of k will satisfy (22), so we may assume throughout that Z satisfies (21).

The key smoothing property of the averaging operators {E_{j}}_{j=1}^{n} is contained in the following lemma:

Lemma 2.1. Let X be a Banach space, q ⩾ 1, n, m ∈ ℕ, where m > 4n is divisible by 4, and f : ℤ_{m}^{n} → X. Suppose that k is an odd integer satisfying 2n ⩽ k < \frac{m}{2}. Then,

∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]∥_{X}^{p} dτ(ε)dμ(x)

⩽ S^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{2}(x, y), (23)

where S ≲ 1.

We shall postpone the proof of Lemma 2.1 to Section 3, and proceed now to deduce Theorem 1.2 assuming its validity. Before doing so, we recall for future use the following simple lemma from [10]:

Lemma 2.2 (Lemma 2.6 from [10]). For every q ⩾ 1 and for every f : ℤ_{m}^{n} → X,

\frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{q}dμ(x) ≲ 2^{q} ∫_{\{−1,0,1\}^{n}} ∫_{ℤ_{m}^{n}} ∥f(x + δ) − f(x)∥_{X}^{q}dμ(x)dσ(δ). (24)

Proof of Theorem 1.1. The argument in the introduction leading to (15), when specialized to our smoothing and approximation scheme using (19) and (23), shows that if k ⩾ 2n and m ⩾ 2kn^{1/q}, then

∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x) ≲_{X} m^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ_{3}(x, y), (25)

where

β_{3} = \frac{β_{1} + β_{2}}{2} ⩽ β_{1}^{∘} + β_{1}^{∘∘} + β_{2}.

Note that β_{1}^{∘} ≲ β_{2} due to the contribution of S = ∅ in (20). Thus, (25) implies the following bound:

∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x) ≲_{X} \frac{m^{q}}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{q}dμ(x)

+ m^{q} ∑_{S⊆[n]} \frac{(n/k)^{q|S|}}{\binom{n}{|S|}} ∫_{\{−1,1\}^{[n]\S}} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x)dτ(ε), (26)

where the first term in the right hand side of (26) corresponds to β_{1}^{∘∘}.

In order to deduce the desired metric cotype inequality (5) from (26), we shall apply (26) to lower dimensional sub-tori of ℤ_{m}^{n}. Note that we are allowed to do so since our requirements on k, namely k ⩾ 2n and m ⩾ 2kn^{1/q}, remain valid for smaller n.

Fix ∅ ≠ B ⊆ [n] and x_{[n]\B} ∈ ℤ_{m}^{[n]\B}. We can then consider the mapping g : ℤ_{m}^{B} → X given by g(x_{B}) = f(x_{[n]\B}, x_{B}). Applying (26) to g, and averaging the resulting inequality over x_{[n]\B} ∈ ℤ_{m}^{[n]\B}, we obtain

∑_{j∈B} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q}dμ(x) ≲_{X} \frac{m^{q}}{|B|} ∑_{j∈B} ∫_{ℤ_{m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{q}dμ(x)

+ m^{q} ∑_{S⊆B} \frac{(|B|/k)^{q|S|}}{\binom{|B|}{|S|}} ∫_{\{−1,1\}^{B\S}} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x)dτ(ε). (27)

For B ⊆ [n] define the weight W_{|B|} =^{def} \frac{2^{|B|−1}}{3^{n−1}} . Multiplying (27) by W_{|B|} and summing over ∅ ≠ B ⊆ [n], we obtain the bound

\frac{1}{m^{q}} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j})−f(x)∥_{X}^{q}dμ(x) ≲_{X} ∑_{\begin{matrix}B⊆[n] \\ B≠∅ \end{matrix}} \frac{W_{|B|}}{|B|} ∑_{j∈B} ∫_{ℤ_{m}^{n}} ∥f(x+e_{j})−f(x)∥_{X}^{q}dμ(x)

+ ∑_{\begin{matrix}B⊆[n] \\ B≠∅ \end{matrix}} W_{|B|} ∑_{S⊆B} \frac{(|B|/k)^{q|S|}}{\binom{|B|}{|S|}} ∫_{\{−1,1\}^{B\S}} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x)dτ(ε), (28)

where we used the identity

∑_{B⊆[n]} W_{|B|} ∑_{j∈B} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q}dμ(x) = ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q} dμ(x).

The first term in the right hand side of (28) is easy to bound, using Lemma 2.2, as follows:

∑_{\begin{matrix}B⊆[n] \\ B≠∅ \end{matrix}} \frac{W_{|B|}}{|B|} ∑_{j∈B} ∫_{ℤ_{m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{q}dμ(x) = \frac{3}{4n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{q}dμ(x)

≲^{(24)} 2^{q} ∫_{{−1,0,1}^{n}} ∫_{ℤ_{m}^{n}} ∥f(x + δ) − f(x)∥_{X}^{q}dμ(x)dσ(δ). (29)

To bound the second term in the right hand side of (28), note that it equals

C =^{def} ∑_{S⊆[n]} ∑_{\begin{matrix}S⊆B⊆[n] \\ B≠∅ \end{matrix}} ∑_{ε∈\{−1,1\}^{B\S}} \frac{2^{|B|−1}}{3^{n−1}} · \frac{(|B|/k)^{q|S|}}{2^{|B|−|S|}\binom{|B|}{|S|}} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x)

≲ \frac{1}{3^{n}} ∑_{T ⊆[n]} ∑_{ε∈\{−1,1\}^{T}} a_{T} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x), (30)

where we used the change of variable T = B \ S, and for every T ⊆ [n] we write,

a_{T} =^{def} ∑_{B⊇T} \frac{2^{|B|−|T |}(|B|/k)^{q(|B|−|T |)}}{\binom{|B|}{|B|−|T |}} = ∑_{ℓ=|T |}^{n} \binom{n − |T |}{ℓ − |T |} · \frac{2^{ℓ−|T |}(ℓ/k)^{q(ℓ−|T |)}}{\binom{ℓ}{ℓ−|T |}} .  (31)

Fix T ⊆ [n]. Using the standard bounds (\frac{u}{v})^{v} ⩽ \binom{u}{v} ⩽ (\frac{eu}{v})^{v}, which hold for all integers 0 ⩽ v ⩽ u, we can bound a_{T} as follows:

a_{T} ⩽ ∑_{ℓ=|T |}^{n} (\frac{e(n − |T |)}{ℓ − |T |})^{ℓ−|T |} (\frac{ℓ − |T |}{ℓ})^{ℓ−|T |} (\frac{ℓ}{k} )^{q(ℓ−|T |)} 2^{ℓ−|T |}

= ∑_{ℓ=|T |}^{n} (\frac{2e(n − |T |)ℓ^{q−1}}{k^{q}} )^{ℓ−|T |} ≲_{q} 1, (32)

provided, say, k ⩾ 6n.

Combining (32) with (30), we see that the second term in the right hand side of (28) is

C ≲_{q} \frac{1}{3^{n}} ∑_{T ⊆[n]} ∑_{ε∈\{−1,1\}^{T}} ∫_{ℤ_{m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{q}dμ(x)

= ∫_{{−1,0,1}^{n}} ∫_{ℤ_{m}^{n}} ∥f(x + δ) − f(x)∥_{X}^{q}dμ(x)dσ(δ).

In combination with (29), inequality (28) implies that

\frac{1}{m^{q}} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f(x)∥_{X}^{q}dμ(x)

≲_{X} ∫_{{−1,0,1}^{n}} ∫_{ℤ_{m}^{n}} ∥f(x + δ) − f(x)∥_{X}^{q}dμ(x)dσ(δ), which is precisely the desired inequality (5). Recall that in the above argument, our requirement on k was k ⩾ 6n, and our requirement on m was m ⩾ 2kn^{1/q} (and that it is divisible by 4). This implies the requirement m ≳ n^{1+ \frac{1}{q}} of Theorem 1.2. □

3. Proof of Lemma 2.1

Lemma 2.1 is the main new ingredient of Theorem 1.2. Its proof is based on combinatorial identities which relate the “smoothed out Rademacher sum”

∑_{l=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]  (33)

to a certain bivariate extension of the Bernoulli numbers. We shall therefore first, in Section 3.1, do some preparatory work which introduces these numbers and establishes estimates that we will need in the ensuing argument. We shall then derive, in Section 3.2, certain combinatorial identities that relate (33) to the bivariate Bernoulli numbers. In Section 3.3 we shall combine the results of Section 3.1 and Section 3.2 to complete the proof of Lemma 2.1.

3.1. Estimates for the bivariate Bernoulli numbers. There are two commonly used definitions of the Bernoulli numbers {B_{r}}_{r=0}^{∞}. For more information on these two conventions,

we refer to http://en.wikipedia.org/wiki/Bernoulli_number. Here we shall refer to the

variant of the Bernoulli numbers that was originally defined by J. Bernoulli, for which B_{1} = \frac{1}{2}, and which is defined via the recursion

B_{0} = 1 and r = ∑_{a=0}^{r−1} B_{a}\binom{r}{a}.  (34)

The recursion (34) extends naturally to a bivariate sequence {B_{r,s}}_{r,s=0}^{n}, given by

B_{0,0} = 1 and r − s = ∑_{a=0}^{r−1} B_{a,s}\binom{r}{a} − ∑_{b=0}^{s−1} B_{r,b}\binom{s}{b}.  (35)

It is well-known (cf. [16, Sec. 2.5]) that the exponential generating function for {B_{r}}_{r=0}^{∞} is

F (x) =^{def} \frac{xe^{x}}{e^{x} − 1} = ∑_{r=0}^{∞} B_{r} \frac{x^{r}}{r!} .

We shall require the following analogous computation of the bivariate exponential generating function of {B_{r,s}}_{r,s=0}^{n}:

Lemma 3.1. For all x, y ∈ ℂ with |x|, |y| < π we have

F (x, y) =^{def} \frac{(x − y)e^{x+y}}{e^{x} − e^{y}} = ∑_{r=0}^{∞} ∑_{s=0}^{∞} B_{r,s} \frac{x^{r}y^{s}}{r! · s!},  (36)

where the series in (36) is absolutely convergent on {(x, y) ∈ ℂ × ℂ : |x|, |y| ⩽ r} for all r < π.

Proof. The function F (x, y) is analytic on D_{π} = {(x, y) ∈ ℂ × ℂ : |x|, |y| < π}, since its only non-removable singularities are when x − y ∈ 2πi(ℤ \ {0}). It follows that we can write F (x, y) = ∑_{r=0}^{∞} ∑_{s=0}^{∞} z_{r,s}x^{r}y^{s}, for some {z_{r,s}}_{r,s=0}^{∞} ⊆ ℂ, where the series converges absolutely on any compact subset of D_{π} (see, e.g., [4, Thm. 2.2.6]). Note that

(e^{x} − e^{y})F (x, y) = (∑_{n=1}^{∞} \frac{x^{n} − y^{n}}{n!} ) (∑_{r=0}^{∞} ∑_{s=0}^{∞} z_{r,s}x^{r}y^{s})

= ∑_{r=0}^{∞} ∑_{s=0}^{∞} (∑_{a=0}^{r−1} \frac{z_{a,s}}{(r − a)!} − ∑_{b=0}^{s−1} \frac{z_{r,b}}{(s − b)!}) x^{r}y^{s}. (37)

At the same time,

(e^{x} − e^{y})F (x, y) = (x − y)e^{x}e^{y} = (x − y) ∑_{r=0}^{∞} ∑_{s=0}^{∞} \frac{x^{r}y^{s}}{r!s!} = ∑_{r=0}^{∞} ∑_{s=0}^{∞} (r − s) \frac{x^{r}y^{s}}{r!s!} .  (38)

By equating coefficients in (37) and (38), we see that for all r, s ∈ ℕ ∪ {0},

r − s = r!s! (∑_{a=0}^{r−1} \frac{z_{a,s}}{(r − a)!} − ∑_{b=0}^{s−1} \frac{z_{r,b}}{(s − b)!}) = ∑_{a=0}^{r−1} \binom{r}{a}a!s!z_{a,s} − ∑_{b=0}^{s−1} \binom{s}{b}r!b!z_{r,b}.

Since z_{0,0} = 1, the recursive definition (35) implies that z_{r,s} = \frac{B_{r,s}}{r!s!} , as required. □

An immediate corollary of Lemma 3.1 is that since F (x, y) = F (y, x),

∀r, s ∈ ℕ ∪ {0}, B_{r,s} = B_{s,r}.  (39)

Another (crude) corollary of Lemma 3.1 is that since the power series in (36) converges absolutely on {(x, y) ∈ ℂ × ℂ : |x|, |y| ⩽ 2}, for all but at most finitely many r, s ∈ ℕ ∪ {0} we have |B_{r,s}/(r!s!)|^{1/(r+s)} ⩽ 1/2. Thus,

∀r, s ∈ ℕ ∪ \{0\}, |B_{r,s}| ≲ \frac{r!s!}{2^{r+s}} .  (40)

Remark 3.1. Since B_{2m} = \frac{(−1)^{m−1}2ζ(2m)(2m)!}{(2π)^{2m}}, where ζ(s) is the Riemann zeta function (and

B_{2m+1} = 0 for m ⩾ 1), one has the sharp asymptotics |B_{2m}| ∼ \frac{2(2m)!}{(2π)^{2m}} for the classical Bernoulli numbers. We did not investigate the question whether similar sharp asymptotics can be obtained for the bivariate Bernoulli numbers.

3.2. Some combinatorial identities. We start by introducing some notation. For y ∈ ℤ_{m}^{n} write:

↑y↑ =^{def} |{l : y_{l} = k (mod m)}|,

↓y↓ =^{def} |{l : y_{l} = −k (mod m)}|,

↕y↕ =^{def} ↑y↑ + ↓y↓ and ↑y↓ =^{def} ↑y↑ − ↓y↓ .

We also define

𝕊 =^{def} {y ∈ [−k, k]^{n} ⊆ ℤ_{m}^{n} : y_{t} is odd ∀t ∈ [n]}.

For x ∈ ℤ_{m}^{n} and ε ∈ {−1, 1}^{n}, let x ⊙ ε ∈ ℤ_{m}^{n} be the coordinate wise multiplication, i.e., (x ⊙ ε)_{j} = x_{j}ε_{j}. Also for ε, ε′ ∈ {−1, 1}^{n} let ⟨ε, ε′⟩ = ∑_{j=1}^{n} ε_{j}ε′_{j}.

We need to define additional auxiliary averaging operators.

Definition 3.2. For f : ℤ_{m}^{n} → X, k < \frac{m}{2} odd, and B ⊆ [n], let

Δ_{B}f(x) =^{def} \frac{1}{μ(L_{B})} ∫_{L_{B}} f(x + y)dμ(y),

where

L_{B} =^{def} {y ∈ (−k, k)^{n} ⊆ ℤ_{m}^{n} : ∀i ∉ B, y_{i} = 0 ∧ ∀i ∈ [n] y_{i} is even}.

Definition 3.3. Define for z ∈ ℤ_{m}^{n}, ε ∈ {−1, 1}^{n}, i ∈ [n], and 0 ⩽ j ⩽ i,

b_{i,j}(z, ε) = ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{S} \\ ⟨δ,ε_{S}⟩=i−2j \end{matrix}} (1_{δk+ε_{[n]\S}+L_{[n]\S}}(z) − 1_{δk−ε_{[n]\S}+L_{[n]\S}}(z)) ,  (41)
a(z, ε) = ∑_{j=1}^{n} ε_{j} (1_{e_{j}+S(j,k)}(z) − 1_{−e_{j}+S(j,k)}(z)) ,  (42)

where we recall that S(j, k) was defined in (16).

The next lemma follows immediately from an inspection of our definitions. Lemma 3.2. The following identities hold true:

∑_{y∈ℤ_{m}^{n}} b_{i,j}(y − x, ε)f(y)

= k^{n−i} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{S} \\ ⟨δ_{S},ε_{S}⟩=i−2j \end{matrix}} (Δ_{[n]\S}f(x + δ_{S}k + ε_{[n]\S}) − Δ_{[n]\S}f(x + δ_{S}k − ε_{[n]\S})), (43)

∑_{y∈ℤ_{m}^{n}} a(y − x, ε)f(y) = k(k + 1)^{n−1} ∑_{j=1}^{n} ε_{j}(E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})).  (44)

Claim 3.3. If there exits t ∈ [n] such that z_{t} is even, then a(z, ε) = b_{i,j}(z, ε) = 0 for all ε ∈ {−1, 1}^{n}. Proof. This follows directly from the definitions of the sets S(j, k), and L_{B}, since all values of the coordinates are odd in all the points of the sets

δk + ε_{[n]\S} + L_{[n]\S}, δk − ε_{[n]\S} + L_{[n]\S}, e_{j} + S(j, k), −e_{j} + S(j, k),

for every δ ∈ {−1, 1}^{S} and ε ∈ {−1, 1}^{n}. □ Claim 3.4. If z_{t} is odd and either z_{t} ≠ ±k (mod m) for all t ∈ [n], or |z_{t_{0}}| > k for some t_{0} ∈ [n], then a(z, ε) = b_{i,j}(z, ε) = 0. Proof. We may assume that z ∈ [−m/2, m/2]^{n}. If there is t_{0} ∈ [n] for which |z_{t_{0}}| > k then all the terms in the right hand side of (41) and (42) are 0. If |z_{t}| < k for all t ∈ [n], then all the terms in the right hand side of (41) and (42) cancel out. □

It follows that for z ∉ 𝕊 we have a(z, ε) = b_{i,j}(z, ε) = 0 for every ε ∈ {−1, 1}^{n} and every 0 ⩽ j ⩽ i ⩽ n. Thus, in particular, identity (43) can be rewritten as:

∑_{y∈x+𝕊} b_{i,j}(y − x, ε)f(y)

= k^{n−i} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{S} \\ ⟨δ_{S},ε_{S}⟩=i−2j \end{matrix}} (Δ_{[n]\S}f(x + δ_{S}k + ε_{[n]\S}) − Δ_{[n]\S}f(x + δ_{S}k − ε_{[n]\S})), (45)

Note that the definition (42) shows that for z ∈ 𝕊 we have

a(z, ε) = ∑_{\begin{matrix}t∈[n] \\ z_{t}=k \end{matrix}} ε_{t} − ∑_{\begin{matrix}t∈[n] \\ z_{t}=−k \end{matrix}} ε_{t} = ↑z ⊙ ε↓ .  (46)

Using Claim 3.3 and Claim 3.4, in conjunction with (44) and (46), we conclude that:

Lemma 3.5. The following identity holds for all x ∈ ℤ_{m}^{n} and ε ∈ {−1, 1}^{n}:

∑_{j=1}^{n} ε_{j}(E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})) = \frac{1}{k(k − 1)^{n−1}} ∑_{y∈x+𝕊} ↑(y − x) ⊙ ε↓ f(y). (47)

Lemma 3.6. If z ∈ 𝕊 and i ⩾ ↕z↕ then ∀j ∈ {0, …, i} and ∀ε ∈ {−1, 1}^{n}, we have b_{i,j}(z, ε) = 0.

Proof. If i > ↕z↕ then

z ∉ (δk + ε_{[n]\S} + L_{[n]\S}) ⋃ (δk − ε_{[n]\S} + L_{[n]\S}),

for every S ⊆ [n] with |S| = i, and δ ∈ {−1, 1}^{S}. If i = ↕z↕ then there exists exactly one subset S ⊆ [n] in (41) where z can appear, namely S = {ℓ ∈ [n] : z_{ℓ} ∈ {−k, k}}. If

z ∈ (δk + ε_{[n]\S} + L_{[n]\S}) ⋃ (δk − ε_{[n]\S} + L_{[n]\S}),

for some δ ∈ {−1, 1}^{S}, then

z ∈ (δk + ε_{[n]\S} + L_{[n]\S}) ⋂ (δk − ε_{[n]\S} + L_{[n]\S}),

since for all coordinates i ∈ [n] \ S we have |z_{i}| < k. Hence in this case the terms in the sum in the right hand side of (41) cancel out. □

Lemma 3.7. For every z ∈ 𝕊, ε ∈ {−1, 1}^{n}, and 0 ⩽ j ⩽ i < ↕z↕,

b_{i,j}(z, ε) = \begin{cases}\binom{↕z↕−j}{i−j} & ↓z ⊙ ε↓ = j, \\ −\binom{↕z↕−(i−j)}{j} & ↑z ⊙ ε↑ = i − j, \\ 0 & otherwise. \end{cases}

Proof. By looking at the elements of

(δk + ε_{[n]\S} + L_{[n]\S}) ⋃ (δk − ε_{[n]\S} + L_{[n]\S}),

it is clear that we must have S ⊆ {h : z_{h} ∈ {−k, k}} in order to get a nonzero contribution to the right hand side of (41). For such an S there is at most one δ ∈ {−1, 1}^{S} which can contributes to the sum, namely δ_{h} = sgn(z_{h}) for every h ∈ S. But since this δ should also satisfy ⟨δ_{S}, ε_{S}⟩ = i − 2j, we conclude that a non-zero contribution can occur only when ↓z_{S} ⊙ ε_{S}↓ = j. In those cases, there is an actual contribution only if either sgn(z_{h}ε_{h}) = 1 for every h ∈ {ℓ : z_{ℓ} ∈ {−k, k}} \ S, or sgn(z_{h}ε_{h}) = −1 for every h ∈ {ℓ : z_{ℓ} ∈ {−k, k}} \ S, and those contributions have different signs. The claim now follows. □

The following lemma relates, via Lemma 3.7, what we have done so far to the bivariate Bernoulli numbers.

Lemma 3.8. There exists a sequence \{h_{α,β}\}\begin{matrix}0⩽α⩽n \\ 0⩽β⩽α \end{matrix} ⊆ ℝ such that for all y ∈ ℤ_{m}^{n} and all

ε ∈ {−1, 1}^{n},

↑y ⊙ ϵ↓ = ∑_{α=0}^{n} ∑_{β=0}^{α} h_{α,β}b_{α,β}(y, ε),  (48)

|h_{α,β}| ≲ \frac{(α − β)!β!}{2^{α}}, for all 0 ⩽ β ⩽ α  (49)
h_{α,β} = h_{α,α−β}.  (50)

Proof. Write r = ↑z ⊙ ε↑ and s = ↓z ⊙ ε↓. Thus r + s = ↕z↕ and r − s = ↑z ⊙ ε↓. With this notation, if we substitute the values of b_{α,β}(y, ε) from Lemma 3.7, the desired identity (48) becomes:

r − s = ∑_{α=s}^{n} h_{α,s}\binom{r}{α − s} − ∑_{β=0}^{n} h_{β+r,β}\binom{s}{β} =^{(♠)} ∑_{a=0}^{n−s} h_{a+s,s}\binom{r}{a} − ∑_{b=0}^{n} h_{b+r,b}\binom{s}{b}

=^{(♣)} ∑_{a=0}^{r−1} h_{a+s,s}\binom{r}{a} − ∑_{b=0}^{s−1} h_{b+r,b}\binom{s}{b}, (51)

where in (♠) we used the change of variable β = b, α = a + b, and in (♣) we noted that r + s = ↕z↕ ⩽ n and that the terms corresponding to a > r or b > r vanish, while the terms corresponding to a = r and b = r cancel out.

Thus, the desired identity (51) shows that we must take h_{a+b,b} = B_{a,b}, or h_{α,β} = B_{α−β,β}. The bound (49) is now the same as (40), and the identity (50) is the same as (39). □

3.3. Putting things together. We are now ready to complete the proof of Lemma 2.1 using the tools developed in the previous two sections.

Lemma 3.9. Let \{h_{α,β}\}\begin{matrix}0⩽α⩽n \\ 0⩽β⩽α \end{matrix} be the sequence from Lemma 3.8. Then for all f : ℤ_{m}^{n} → X

and all ε ∈ {−1, 1}^{n} we have,

∫_{ℤ_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} (∑_{i=0}^{n} ∑_{j=0}^{i} h_{i,j} ∑_{y∈x+𝕊} b_{i,j}(y − x, ε)f(y)) ∥_{X}^{q}dμ(x)

≲_{q} ∑_{ℓ=0}^{n} \begin{matrix}(n/k) & ℓp \\ ( & {n \atop ℓ} & ) \end{matrix} ∑_{\begin{matrix}S⊆[n] \\ |S|=ℓ \end{matrix}} ∫_{ℤ_{m}^{n}} ∥f(x + ε_{[n]\S}) − f(x)∥_{X}^{q} dμ(x). (52)

Proof. For every x ∈ ℤ_{m}^{n} and 0 ⩽ j ⩽ i ⩽ n write

D_{ij}(x) =^{def} ∥\frac{1}{k(k + 1)^{n−1}} ( ∑_{y∈x+𝕊} b_{i,j}(y − x, ε)f(y)) ∥_{X}.

Note that,

(∑_{i=0}^{n} ∑_{j=0}^{i} |h_{i,j}|D_{ij}(x))^{q} = (∑_{i=0}^{n} 2^{−(i+1)} ∑_{j=0}^{i} 2^{i+1}|h_{i,j}|D_{ij}(x))^{q}

⩽^{(∗)} ∑_{i=0}^{n} 2^{−(i+1)} (∑_{j=0}^{i} 2^{i+1}|h_{i,j}|D_{ij}(x))^{q} ⩽^{(∗∗)} ∑_{i=0}^{n} ∑_{j=0}^{i} 2^{(i+1)(q−1)}(i + 1)^{q−1}|h_{i,j}|^{q}D_{ij}(x)^{q}, (53)

where in (∗) we used the convexity of the function t ↦ t^{q} and that ∑_{i=0}^{∞} 2^{−(i+1)} = 1, and in (∗∗) we used Hölder’s inequality. It follows from (53), combined with the bound (49) on h_{i,j}, that,

∥\frac{1}{k(k + 1)^{n−1}} (∑_{i=0}^{n} ∑_{j=0}^{i} h_{i,j} ∑_{y∈ℤ_{m}^{n}} b_{i,j}(y − x, ε)f(y)) ∥_{X}^{q} ⩽ (∑_{i=0}^{n} ∑_{j=0}^{i} |h_{i,j}|D_{ij}(x))^{q}

≲ ∑_{i=0}^{n} ∑_{j=0}^{i} 2^{(i+1)(q−1)}(i + 1)^{q−1} (\frac{(i − j)!j!}{2^{i}})^{q} D_{ij}(x)^{q}. (54)

Now, D_{ij}(x) can be estimated using the identity (45) as follows:

k^{i}D_{ij}(x) ⩽ \frac{(k + 1)^{n−1}}{k^{n−i−1}} D_{ij}(x)

⩽ ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{S} \\ ⟨δ_{S},ε_{S}⟩=i−2j \end{matrix}} ∥Δ_{[n]\S}f(x + δ_{S}k + ε_{[n]\S}) − Δ_{[n]\S}f(x + δ_{S}k − ε_{[n]\S})∥_{X}. (55)

Note that the number of terms in the sum in the right hand side of (55) is \binom{n}{i}\binom{i}{j}. Thus

D_{ij}(x)^{q} ⩽ \frac{1}{k^{iq}} \binom{n}{i}^{q−1}\binom{i}{j}^{q−1}

· ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{S} \\ ⟨δ_{S},ε_{S}⟩=i−2j \end{matrix}} ∥Δ_{[n]\S}f(x + δ_{S}k + ε_{[n]\S}) − Δ_{[n]\S}f(x + δ_{S}k − ε_{[n]\S})∥_{X}^{q}. (56)

If we integrate inequality (56) with respect to x, use the translation invariance of μ to eliminate the additive term δ_{S}k in the argument of the integrands, and use the fact that Δ_{B} is an averaging operator for all B ⊆ [n], we obtain the bound

∫_{ℤ_{m}^{n}} D_{ij}(x)^{q}dμ(x) ⩽ \frac{1}{k^{iq}} \binom{n}{i}^{q−1}\binom{i}{j}^{q} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∫_{ℤ_{m}^{n}} ∥f(x + ε_{[n]\S}) − f(x − ε_{[n]\S})∥_{X}^{q}dμ(x)

⩽ \frac{2^{q}}{k^{iq}} \binom{n}{i}^{q−1}\binom{i}{j}^{q} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∫_{ℤ_{m}^{n}} ∥f(x + ε_{[n]\S}) − f(x)∥_{X}^{q}dμ(x), (57)

where in the last step of (57) we used the triangle inequality as follows:

∥f(x + ε_{[n]\S}) − f(x − ε_{[n]\S})∥_{X}^{q} ⩽ 2^{q−1}∥f(x + ε_{[n]\S}) − f(x)∥_{X}^{q} + 2^{q−1}∥f(x) − f(x − ε_{[n]\S})∥_{X}^{q},

while noticing that upon integration with respect to x, by translation invariance, both terms become equal.

Integrating (54) with respect to x, and using (57), we see that that the left hand side of (52) is at most

∑_{i=0}^{n} ∑_{j=0}^{i} \frac{2^{(i+1)(q−1)+q}(i + 1)^{q−1} (\frac{(i−j)!j!}{2^{i}k^{i}} \binom{n}{i}\binom{i}{j})^{q}}{\binom{n}{i}} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∫_{ℤ_{m}^{n}} ∥f(x + ε_{[n]\S}) − f(x)∥_{X}^{q}dμ(x)

= 2^{2q−1} ∑_{i=0}^{n} \frac{(i + 1)^{q}}{2^{i}\binom{n}{i}} (\frac{n!}{k^{i}(n − i)!})^{q} ∑_{\begin{matrix}S⊆[n] \\ |S|=i \end{matrix}} ∫_{ℤ_{m}^{n}} ∥f(x + ε_{[n]\S}) − f(x)∥_{X}^{q}dμ(x). (58)

Inequality (58) implies the desired bound (52), since (i+1)^{q}2^{−i} ≲_{q} 1 and n!/(n−i)! ⩽ n^{i}. □

Proof of Lemma 2.1. It follows from (44) and (47) that

∫_{{−1,1}^{n}} ∫_{ℤ_{m}^{n}} ∥ ∑_{l=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x + e_{j})] ∥_{X}dμ(x)dτ(ε)

= ∫_{\{−1,1\}^{n}} ∫_{ℤ_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈x+𝕊} ↑(y − x) ⊙ ε↓ f(y)∥_{X}^{q} dμ(x)dτ(ε). (59)

An application of identity (48) now shows that

∫_{\{−1,1\}^{n}} ∫_{ℤ_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈x+𝕊} ↑(y − x) ⊙ ε↓ f(y)∥_{X}^{q} dμ(x)dτ(ε)

= ∫_{\{−1,1\}^{n}} ∫_{ℤ_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} (∑_{i=0}^{n} ∑_{j=0}^{i} h_{i,j} ∑_{y∈𝕊} b_{i,j}(y − x, ε)f(y)) ∥_{X}^{p}dμ(x)dτ(ε). (60)

Lemma 2.1 now follows from Lemma 3.9. □

4. Lower bounds

In this section we establish lower bounds for the best possible value of m in Theorem 1.2 that is achievable via a smoothing and approximation scheme. Our first result deals with general convolution kernels:

Proposition 4.1. Assume that the probability measures ν_{1}, …, ν_{n}, β_{1}, β_{2} are a (q, A, S)- smoothing and approximation scheme on ℤ_{m}^{n}, i.e., conditions (7) and (8) are satisfied for every Banach space X and every f : ℤ_{m}^{n} → X. Assume also that m > cA for a large enough universal constant c > 0. Then

S ≳_{q} \frac{\sqrt{n}}{A}.  (61)

Recall, as explained in Section 1.1, that in order for a smoothing and approximation scheme to yield the metric cotype inequality (5), we require S ≲ 1, in which case the bound on m becomes m ≳ An^{1/q}. Proposition 4.1 shows that S ≲ 1 forces the bound A ≳_{q} \sqrt{n}, and correspondingly m ≳_{q} n^{\frac{1}{2} + \frac{1}{q}}.

For the particular smoothing and approximation scheme used in our proof of Theorem 1.2, the following proposition establishes asymptotically sharp bounds.

Proposition 4.2. Fix an odd integer k ⩽ m/2 and consider the averaging operators {E_{j}}_{j=1}^{n} used in our proof of Theorem 1.2, i.e., they are defined as in (17). If there exist probability measures β_{1}, β_{2} on E_{∞}(ℤ_{m}^{n}) for which the associated approximation and smoothing inequalities (7) and (8) are satisfied for every Banach space X and every f : ℤ_{m}^{n} → X, then

A ≳ k and S ≳ \sqrt{\frac{n}{k}}.  (62)

Proposition 4.2 shows that in order to have S ≲ 1 we need to require k ≳ n, in which case A ≳ n, and correspondingly m ≳ n^{1+ \frac{1}{q}}, matching the bound obtained in Theorem 1.2.

4.1. A lower bound for general convolution kernels: Proof of Proposition 4.1. Assume that the probability measures ν_{1}, …, ν_{n}, β_{1}, β_{2} are a (q, A, S)-smoothing and approximation scheme, i.e., they satisfy (7) and (8). It will be convenient to think of these measures as functions defined on the appropriate (finite) spaces, i.e., ν_{1}, …, ν_{n} : ℤ_{m}^{n} → [0, 1] and β_{1}, β_{2} : E_{∞}(ℤ_{m}^{n}) → [0, 1].

For a probability measure ν on ℤ_{m}^{n}, let P_{j}(ν) be the probability measure on ℤ_{m} which is the marginal of ν on the jth coordinate, i.e.,

P_{j}(ν)(r) =^{def} ∑_{\begin{matrix}x∈ℤ_{m}^{n} \\ x_{j}=r \end{matrix}} ν(x).

Define the absolute value of x ∈ ℤ_{m} to be |x| = min{x, m − x}.

Lemma 4.3. Assume that ν_{1}, …, ν_{n}, β_{1} satisfy (7). Then for every s ∈ ℕ we have:

\frac{1}{n} ∑_{j=1}^{n} ∑_{\begin{matrix}x∈ℤ_{m}^{n} \\ |x_{j}|>s \end{matrix}} ν_{j}(x) ≲ \frac{A}{s}.  (63)

Figure 1. g_{s} is truncated jigsaw function.

Proof. We shall apply (7) with X = ℓ_{∞}^{n}. Let g_{s} : ℝ → ℝ be the truncated jigsaw function with period 12s, depicted in Figure 1.

Define f : ℤ_{m}^{n} → X by

f(x) =^{def} (g_{s}(x_{1}), g_{s}(x_{2}), … g_{s}(x_{n})).

The Lipschitz constant of f with respect to the ℓ_{∞} metric on ℤ_{m}^{n} is 1, and therefore it follows from (7) that

(\frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν_{j} − f∥_{ℓ_{∞}^{n}} dμ)^{q} ⩽ \frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν_{j} − f∥_{ℓ_{∞}^{n}}^{q} dμ ≲ A^{q}.  (64)

For every x ∈ ℤ_{m}^{n} and j ∈ [n],

(f ∗ ν_{j} − f)(x) = ∑_{y∈ℤ_{m}^{n}} ν_{j}(y)(f(x − y) − f(x))

= ∑_{y∈ℤ_{m}^{n}} ν_{j}(y)(g_{s}(x_{1} − y_{1}) − g_{s}(x_{1}), …, g_{s}(x_{n} − y_{n}) − g_{s}(x_{n})).

Assume that

(x_{j} mod 12s) ∈ [0, s] ∪ [12s − s, 12s − 1].  (65)

When 3s ⩽ |y_{j}| ⩽ 4s, we have g_{s}(x_{j} − y_{j}) − g_{s}(x_{j}) ⩾ s, and for every y_{j} ∈ ℤ_{m}, we have g_{s}(x_{j} − y_{j}) − g_{s}(x_{j}) ⩾ 0. Hence,

∥(f ∗ ν_{j} − f)(x)∥_{ℓ_{∞}^{n}} ⩾ ∑_{y∈ℤ_{m}^{n}} ν_{j}(y)(g_{s}(x_{j} + y_{j}) − g_{s}(x_{j}))

⩾ sP_{j}(ν_{j})[z ∈ ℤ_{m} : 3s ⩽ |z| ⩽ 4s]. (66)

Note that (65) holds for a constant fraction of x ∈ ℤ_{m}^{n}, and hence by integrating (66) over ℤ_{m}^{n} we obtain:

∑_{\begin{matrix}y∈ℤ_{m}^{n} \\ 3s⩽|y_{j}|⩽4s \end{matrix}} ν_{j}(y) ≲ \frac{1}{s} ∫_{ℤ_{m}^{n}} ∥(f ∗ ν_{j} − f)(x)∥_{ℓ_{∞}^{n}}dμ(x).

Therefore

∑_{\begin{matrix}y∈ℤ_{m}^{n} \\ |y_{j}|>s \end{matrix}} ν_{j}(y) ≲ (∑_{ℓ=0}^{∞} \frac{1}{s · (4/3)^{ℓ}} ) ∫_{ℤ_{m}^{n}} ∥(f ∗ ν_{j} − f)(x)∥_{ℓ_{∞}^{n}}dμ(x)

≲ \frac{1}{s} ∫_{ℤ_{m}^{n}} ∥(f ∗ ν_{j} − f)(x)∥_{ℓ_{∞}^{n}}dμ(x). (67)

Averaging (67) over j ∈ [n], and using (64), we obtain (63). □

Corollary 4.4. Assume that m > cA for a large enough universal constant c ∈ ℕ. Then:

\frac{1}{n} ∑_{j=1}^{n} ∑_{z∈ℤ_{m}} |P_{j}(ν_{j})(z + 1) − P_{1}(ν_{j})(z − 1)| ≳ \frac{1}{A}.  (68)

Proof. We may assume that A is an integer. By Lemma 4.3, for c large enough we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{|z|⩽cA} P_{j}(ν_{j})(z) ⩾ \frac{3}{4} and \frac{1}{n} ∑_{j=1}^{n} ∑_{z=cA+2}^{3cA+2} P_{j}(ν_{j})(z) ⩽ \frac{1}{4}.

Therefore,

\frac{1}{2} ⩽ \frac{1}{n} ∑_{j=1}^{n} ∑_{|z|⩽cA} P_{j}(ν_{j})(z) − \frac{1}{n} ∑_{j=1}^{n} ∑_{|z−2cA−2|⩽cA} P_{j}(ν_{j})(z)

= \frac{1}{n} ∑_{j=1}^{n} ∑_{|z|⩽cA} [P_{j}(ν_{j})(z) − P_{j}(ν_{j})(z + 2cA + 2)]

= \frac{1}{n} ∑_{j=1}^{n} ∑_{|z|⩽cA} ∑_{t=1}^{cA+1} [P_{j}(ν_{j})(z + 2(t − 1)) − P_{j}(ν_{j})(z + 2t)]

≲ \frac{A}{n} ∑_{j=1}^{n} ∑_{z∈ℤ_{m}} |P_{j}(ν_{j})(z + 1) − P_{1}(ν_{j})(z − 1)| ,

as required. □

Proof of Proposition 4.1. We shall apply the smoothing inequality (8) when X = L_{1}(ℤ_{m}^{n}, μ) and f : ℤ_{m}^{n} → X is defined as f(x) = m^{n} · δ_{{x}}, i.e., for x ∈ ℤ_{m}^{n} the function f(x) : ℤ_{m}^{n} → ℝ is

f(x)(y) =^{def} \begin{cases}m^{n} & x = y, \\ 0 & otherwise. \end{cases}  (69)

For every ε ∈ {−1, 1}^{n} and x ∈ ℤ_{m}^{n} we have:

∑_{j=1}^{n} ε_{j} (f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j}))

= ∑_{j=1}^{n} ε_{j} ( ∑_{y∈ℤ_{m}^{n}} (ν_{j}(y − e_{j}) − ν_{j}(y + e_{j}))f(x − y)) (70)

By Kahane’s inequality [5, 17] and the fact that L_{1}(ℤ_{m}^{n}, μ) has cotype 2 (see [17]),

∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j} ( ∑_{y∈ℤ_{m}^{n}} (ν_{j}(y − e_{j}) − ν_{j}(y + e_{j}))f(x − y))∥_{L_{1}(ℤ_{m}^{n},μ)}^{q} dτ(ε)

≳_{q} (∑_{j=1}^{n} ∥ ∑_{y∈ℤ_{m}^{n}} (ν_{j}(y − e_{j}) − ν_{j}(y + e_{j}))f(x − y)∥_{L_{1}(ℤ_{m}^{n},μ)}^{2})^{q/2} (71)

Note that by the definition of f, for every x ∈ ℤ_{m}^{n} and j ∈ [n] we have,

∥ ∑_{y∈ℤ_{m}^{n}} (ν_{j}(y − e_{j}) − ν_{j}(y + e_{j}))f(x − y)∥_{L_{1}(ℤ_{m}^{n},μ)} = ∑_{z∈ℤ_{m}^{n}} |ν_{j}(z − e_{j}) − ν_{j}(z + e_{j})|

⩾ ∑_{w∈ℤ_{m}} | ∑_{\begin{matrix}z∈ℤ_{m}^{n} \\ z_{j}=w \end{matrix}} (ν_{j}(z − e_{j}) − ν_{j}(z + e_{j}))| = ∑_{w∈ℤ_{m}} |P_{j}(ν_{j})(w − 1) − P_{j}(ν_{j})(w + 1)|. (72)

Hence,

\frac{1}{n} ∑_{j=1}^{n} ∥ ∑_{y∈ℤ_{m}^{n}} (ν_{j}(y − e_{j}) − ν_{j}(y + e_{j}))f(x − y)∥_{L_{1}(ℤ_{m}^{n},μ)}^{2}

⩾^{(72)} (\frac{1}{n} ∑_{j=1}^{n} ∑_{w∈ℤ_{m}} |P_{j}(ν_{j})(w − 1) − P_{j}(ν_{j})(w + 1)|)^{2} ≳^{(68)} \frac{1}{A^{2}} . (73)

Finally, since ∥f(x) − f(y)∥_{L_{1}(ℤ_{m}^{n},μ)} ⩽ ∥f(x)∥_{L_{1}(ℤ_{m}^{n},μ)} + ∥f(y)∥_{L_{1}(ℤ_{m}^{n},μ)} ⩽ 2 for all x, y ∈ ℤ_{m}^{n}, we can use the smoothing inequality (8) to deduce that

S^{q} ≳ S^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{L_{1}(ℤ_{m}^{n},μ)}^{q}dβ_{2}(x, y)

⩾^{(8)} ∫_{ℤ_{m}^{n}} ∫_{\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j} (f ∗ ν_{j}(x + e_{j}) − f ∗ ν_{j}(x − e_{j}))∥_{L_{1}(ℤ_{m}^{n},μ)}^{q} dτ(ε)dμ(x)≳_{q} \frac{n^{q/2}}{A^{q}} ,

where in the last step we used the identity (70), combined with the inequalities (71) and (73). The proof of Proposition 4.1 is complete. □

4.2. A sharp lower bound for E_{j} averages: Proof of Proposition 4.2. Recall that S(j, k) is defined in (16), and in the setting of Proposition 4.2 we have:

ν_{j}(x) = \frac{1_{S(j,k)}(x)}{k(k + 1)^{n−1}} .

If s is odd then by the definition of S(j, k) we have for every odd integer \frac{k}{2} < s < k:

∑_{\begin{matrix}x∈ℤ_{m}^{n} \\ |x_{j}|>s \end{matrix}} ν_{j}(x) = \frac{(k − s − 1)(k + 1)^{n−1}}{k(k + 1)^{n−1}} ≳ 1.

Plugging this estimate into (63) we see that A/k ≳ 1, proving the first assertion in (62).

To prove the second assertion of Proposition 4.2, we shall apply the smoothing inequality (8), as in Section 4.1, to the Banach space X = L_{1}(ℤ_{m}^{n}, μ) and the function f from (69), i.e., f(x) = m^{n}δ_{{x}} ∈ L_{1}(ℤ_{m}^{n}, μ). We shall use here notation from Section 3.2.

In our setting, the value of

∥∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]∥_{L_{1}(ℤ_{m}^{n},μ)}

does not depend on x ∈ ℤ_{m}^{n} and ε ∈ {−1, 1}^{n}. Thus the left hand side of (8) equals (by Lemma 3.5),

∥∑_{j} (E_{j}f(e_{j}) − E_{j}f(−e_{j}))∥_{L_{1}(ℤ_{m}^{n},μ)}^{q} = (\frac{1}{k(k + 1)^{n−1}} ∑_{y∈𝕊} | ↑y↓ |)^{q} .

At the same time, as noted in Section 4.1, the right hand side of (8) is ≲ S^{q}. It follows that

S ≳ \frac{1}{k(k + 1)^{n−1}} ∑_{y∈𝕊} | ↑y↓ |.  (74)

In order to estimate ∑_{y∈𝕊} | ↑y↓ |, compute it as follows: for every s ∈ [n], choose s coordinates on which the value of y is ±k, and in the rest of the coordinates choose odd values in the range [−k + 1, k − 1]. The expression thus obtained is:

∑_{y∈𝕊} | ↑y↓ | = ∑_{s=0}^{n} \binom{n}{s}(k − 1)^{n−s} ∑_{i=0}^{s} \binom{s}{i}|s − 2i|.  (75)

Now,

∑_{i=0}^{s} \binom{s}{i}|s − 2i| = 2^{s} ∫_{\{−1,1\}^{s}} |∑_{i=1}^{s} ε_{i}| dτ(ε) ≍ 2^{s}\sqrt{s},  (76)

Observe that for all u ∈ ℝ we have the identity,

∑_{s=0}^{n} \binom{n}{s}\frac{Γ(s + 1)}{Γ (s + \frac{1}{2})}u^{s− \frac{1}{2}} = \frac{d^{1/2}}{(du)^{1/2}} (1 + u)^{n} = \frac{Γ(n + 1)}{Γ (n + \frac{1}{2})}(1 + u)^{n− \frac{1}{2}} .

An application of Stirling’s formula therefore yields the estimate:

∑_{s=0}^{n} \binom{n}{s}u^{s}\sqrt{s} ≳ (1 + u)^{n− \frac{1}{2}} \sqrt{nu}.  (77)

Substituting u = 2/(k − 1) in (77) yields the bound:

∑_{y∈𝕊} | ↑y↓ | ≳^{(75)∧(76)} ∑_{s=0}^{n} \binom{n}{s}(k − 1)^{n−s}2^{s}\sqrt{s}

≳^{(77)} (k − 1)^{n} (\frac{n}{k − 1})^{\frac{1}{2}} (\frac{k + 1}{k − 1})^{n− \frac{1}{2}} ≳ (k + 1)^{n}\sqrt{\frac{n}{k}}.

Plugging this into (74) gives S ≳ \sqrt{n/k}. The proof of Proposition 4.2 is complete. □

4.3. Symmetrization. We do not know what is the smallest m for which the metric cotype inequality (5) can be shown to hold true via a smoothing and approximation scheme: all we know is that it is between n^{1+ \frac{1}{q}} and n^{\frac{1}{2} + \frac{1}{q}}. In this short section, we note that the special symmetric structure of the smoothing and approximation scheme that we used in the proof of Theorem 1.2 can be always assumed to hold true without loss of generality. This explains why our choice of convolution kernels is natural. Additionally, this fact might be useful in improving the lower bound on m of Proposition 4.1, though we do not know how to use it in our current proof of Proposition 4.1.

For π ∈ S_{n}, i.e., a permutation of [n], and x ∈ ℤ_{m}^{n}, write

x^{π} =^{def} (x_{π(1)}, x_{π(2)}, …, x_{π(n)}) .

For f : ℤ_{m}^{n} → X we define f^{π} : ℤ_{m}^{n} → X by f^{π}(x) = f(x^{π}). Note that if ν is a probability measure on ℤ_{m}^{n} then for all x ∈ ℤ_{m}^{n} we have

f ∗ ν^{π} = (f^{π^{−1}} ∗ ν)^{π} .  (78)

Indeed,

f ∗ ν^{π}(x) = ∫_{ℤ_{m}^{n}} f(x − y)ν(y^{π})dμ(y)= ∫_{ℤ_{m}^{n}} f (x − z^{π^{−1}}) ν(z)dμ(z)

= ∫_{ℤ_{m}^{n}} f^{π^{−1}} (x^{π} − z) ν(z)dμ(z) = f^{π^{−1}} ∗ ν(x^{π}) = (f^{π^{−1}} ∗ ν)^{π} (x).

It follows from (78) that

∥f ∗ ν^{π} − f∥_{L_{q}(ℤ_{m}^{n},X)} = ∥f^{π^{−1}} ∗ ν − f^{π^{−1}} ∥_{L_{q}(ℤ_{m}^{n},X)} .  (79)

Lemma 4.5. Assume that the probability measures ν_{1}, …, ν_{n}, β_{1}, β_{2} are a (q, A, S)-smoothing and approximation scheme. Then there exist probability measures ν̄_{1}, …, ν̄_{n} on ℤ_{m}^{n} and two probability measures β̄_{1}, β̄_{2} on E_{∞}(ℤ_{m}^{n}), such that

1. The sequence ν̄_{1}, …, ν̄_{n}, β̄_{1}, β̄_{2} is also a (q, A, S)-smoothing and approximation scheme,

2. For any j, h ∈ [n] we have ν̄_{j} = ν̄_{h}^{(j,h)}, where (j, h) ∈ S_{n} is the transposition of j and h.

3. For every j, h ∈ [n] \ {i} we have P_{j}(ν̄_{i}) = P_{h}(ν̄_{i}).

Proof. Define for j ∈ [n],

ν̄_{j} =^{def} \frac{1}{n!} ∑_{π∈S_{n}} ν_{π(j)}^{π^{−1}}.  (80)

We also define for (x, y) ∈ E_{∞}(ℤ_{m}^{n}),

β̄_{1}(x, y) =^{def} \frac{1}{n!} ∑_{π∈S_{n}} β_{1} (x^{π}, y^{π}) and β̄_{2}(x, y) =^{def} \frac{1}{n!} ∑_{π∈S_{n}} β_{2} (x^{π}, y^{π}) .  (81)

Fix f : ℤ_{m}^{n} → X and assume the validity of the approximation and smoothing inequalities (7), (8). Then, by the convexity of ∥ · ∥_{X}^{q},

\frac{1}{n} ∑_{j=1}^{n} ∫_{ℤ_{m}^{n}} ∥f ∗ ν̄_{j} − f∥_{X}^{q}dμ ⩽^{(79)∧(80)} \frac{1}{n!} ∑_{π∈S_{n}} \frac{1}{n} ∑_{j=1}^{n} ∥f^{π} ∗ ν_{π(j)} − f^{π}∥_{L_{q}(ℤ_{m}^{n},X)}^{q}

⩽^{(7)∧(81)} A^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ̄_{1}(x, y). (82)

This is precisely the approximation property for ν̄_{1}, …, ν̄_{n}, β̄_{1}, β̄_{2}.

Similarly,

∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν̄_{j}(x + e_{j}) − f ∗ ν̄_{j}(x − e_{j}))∥_{X}^{q} dτ(ε)dμ(x)

⩽^{(81)} \frac{1}{n!} ∑_{π∈S_{n}} ∫_{ℤ_{m}^{n}} ∫_{\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν_{π(j)}^{π^{−1}}(x + e_{j}) − f ∗ ν_{π(j)}^{π^{−1}}(x − e_{j}))∥_{X}^{q} dτ(ε)dμ(x). (83)

Note that

∑_{j=1}^{n} ε_{j}(f ∗ ν_{π(j)}^{π^{−1}}(x + e_{j}) − f ∗ ν_{π(j)}^{π^{−1}}(x − e_{j}))

=^{(78)} ∑_{i=1}^{n} ε_{π^{−1}(i)} (f^{π} ∗ ν_{i} (x^{π^{−1}} + e_{i}) − f^{π} ∗ ν_{i} (x^{π^{−1}} − e_{i})) , (84)

where we made the change of variable j = π^{−1}(i) and used the fact that e_{r}^{π^{−1}} = e_{π(r)} for all r ∈ [n] and π ∈ S_{n}. Hence,

∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν_{π(j)}^{π^{−1}}(x + e_{j}) − f ∗ ν_{π(j)}^{π^{−1}}(x − e_{j}))∥_{X}^{q} dτ(ε)dμ(x)

=^{(84)} ∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{r=1}^{n} ε_{r}(f^{π} ∗ ν_{r}(x + e_{r}) − f^{π} ∗ ν_{r}(x − e_{r}))∥_{X}^{q} dτ(ε)dμ(x). (85)

The smoothing inequality for ν̄_{1}, …, ν̄_{n}, β̄_{1}, β̄_{2} now follows:

∫_{ℤ_{m}^{n}} ∫_{{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j}(f ∗ ν̄_{j}(x + e_{j}) − f ∗ ν̄_{j}(x − e_{j}))∥_{X}^{q} dτ(ε)dμ(x)

⩽^{(83)∧(85)∧(8)} S^{q} ∫_{E_{∞}(ℤ_{m}^{n})} ∥f(x) − f(y)∥_{X}^{q}dβ̄_{2}(x, y).

Assertions 2. and 3. of Lemma 4.5 follow directly from the definition (80). □

References

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

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

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

[4] L. Hörmander. An introduction to complex analysis in several variables, volume 7 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, third edition, 1990.

[5] J.-P. Kahane. Sur les sommes vectorielles ∑ ±u_{n}. C. R. Acad. Sci. Paris, 259:2577–2580, 1964.

[6] N. J. Kalton. Coarse and uniform embeddings into reflexive spaces. Q. J. Math., 58(3):393–414, 2007.

[7] B. Maurey. Type, cotype and K-convexity. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1299–1332. North-Holland, Amsterdam, 2003.

[8] M. Mendel. Metric dichotomies. In Limits of graphs in group theory and computer science, pages 59–76. EPFL Press, Lausanne, 2009.

[9] M. Mendel and A. Naor. Scaled Enflo type is equivalent to Rademacher type. Bull. Lond. Math. Soc., 39(3):493–498, 2007.

[10] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247–298, 2008.

[11] A. Naor. An application of metric cotype to quasisymmetric embeddings. Preprint, 2006. Available at

http://arxiv.org/abs/math/0607644.

[12] G. Pisier. Holomorphic semigroups and the geometry of Banach spaces. Ann. of Math. (2), 115(2):375– 392, 1982.

[13] G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.

[14] N. Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ⩽ p < ∞). Studia Math., 50:163–182, 1974.

[15] A. Veomett and K. Wildrick. Spaces of small metric cotype. Preprint, 2010. Available at

http://arxiv.org/abs/1001.3326.

[16] H. S. Wilf. generatingfunctionology. A K Peters Ltd., Wellesley, MA, third edition, 2006.

[17] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

Courant Institute, New York University

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

Computer Science Division, The Open University of Israel

E-mail address: mendelma@gmail.com

Courant Institute, New York University

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