.

METRIC X_{p} INEQUALITIES

ASSAF NAOR AND GIDEON SCHECHTMAN

Abstract. For every p ∈ (0, ∞) we associate to every metric space (X, d_{X}) a numerical invariant 𝔛_{p}(X) ∈ [0, ∞] such that if 𝔛_{p}(X) < ∞ and a metric space (Y, d_{Y}) admits a bi-Lipschitz embedding into X then also 𝔛_{p}(Y) < ∞. We prove that if p, q ∈ (2, ∞) satisfy q < p then 𝔛_{p}(L_{p}) < ∞ yet 𝔛_{p}(L_{q}) = ∞. Thus our new bi-Lipschitz invariant certifies that L_{q} does not admit a bi-Lipschitz embedding into L_{p} when 2 < q < p < ∞. This completes the long-standing search for bi-Lipschitz invariants that serve as an obstruction to the embeddability of L_{p} spaces into each other, the previously understood cases of which were metric notions of type and cotype, which however fail to certify the nonembeddability of L_{q} into L_{p} when 2 < q < p < ∞. Among the consequences of our results are new quantitative restrictions on the bi-Lipschitz embeddability into L_{p} of snowflakes of L_{q} and integer grids in ℓ_{q}^{n}, for 2 < q < p < ∞. As a byproduct of our investigations, we also obtain results on the geometry of the Schatten p trace class S_{p} that are new even in the linear setting.

1. Introduction

1.1. Nontechnical overview. As a special case of the main contribution of the present article, for p ∈ (0, ∞) we associate to every metric space (X, d_{X}) a numerical invariant 𝔛_{p}(X) ∈ [0, ∞]; a precise description of this quantity appears in Definition 1.1 below. Given p ∈ (0, ∞) and two metric spaces (X, d_{X}) and (Y, d_{Y}), any f : X → Y incurs distortion at least 𝔛_{p}(X)/𝔛_{p}(Y). Thus, 𝔛_{p}(·) is a bi-Lipschitz invariant. We shall prove that for 2 < q < p < ∞ we have 𝔛_{p}(L_{p}) ≍ p/ log p, while 𝔛_{p}(L_{q}) = ∞. Consequently, L_{q} does not admit a bi-Lipschitz embedding into L_{p}.

Qualitatively, the above nonembedding conclusion is well known. Namely, the fact that L_{q} fails to admit a bi-Lipschitz embedding into L_{p} when 2 < q < p < ∞ follows from a differentiation argument that allows one to reduce the question to the linear theory. Specifically, every Lipschitz mapping f : L_{q} → L_{p} must have [54, 25, 5] a point of Gâteaux differentiability x_{0} ∈ L_{q}. The derivative f′(x_{0}) : X → Y is a bounded linear operator, and if f were bi-Lipschitz then it would follow that f′(x_{0}) is invertible with a bounded inverse, and therefore L_{q} would be isomorphic to the linear subspace f′(x_{0})L_{q} of L_{p}. However, a classical theorem of Paley [75] asserts that L_{q} is not isomorphic to any subspace of L_{p}, so it follows that L_{q} also fails to admit a bi-Lipschitz embedding into L_{p}. The above reasoning is due to Mankiewicz [54, Theorem 4]; Section 1.2 below contains a more detailed description of the relevant background.

Such differentiation arguments rely on an existential statement (a point of differentiability must exist), followed by a limiting procedure (differentiation itself) that uses the linear structure. As such, they do not apply in many settings, examples of which include understanding the L_{p} distortion of certain (often discrete) subsets of L_{q}, as well as treating non-Lipschitz (e.g. Hölder) mappings, a setting in which the mapping may be non-differentiable at every point ^{1}. Crucially, such arguments also fail to give any indication as to how to devise an invariant of metric spaces that certifies that the geometry of certain subsets of L_{q} is incompatible with the geometry of any subset of L_{p}.

The search for such metric invariants has been an important theme in modern metric geometry, underpinned by a classical rigidity theorem of Ribe [81] that laid the groundwork for what is known today as the Ribe program; for more on this research program see its original formulation by Bourgain [17] as well as the recent (though by now not quite up-to-date) surveys [44, Section 3],[10] and [66]. It suffices to say here that Ribe’s theorem indicates that certain types of linear properties of Banach spaces (including those properties that are used in some, but not all, of the known proofs that L_{q} is not isomorphic to any linear subspace of L_{p} when 2 < q < p < ∞), may in fact be metric properties in disguise, i.e., they could be reformulated without making any reference to the linear structure whatsoever, so as to make sense in any metric space and thus provide a dictionary that allows one to apply linear intuitions in purely metric contexts. This paradigm is very powerful, leading to solutions of questions in a wide variety of areas, ranging from the nonlinear geometry of Banach spaces themselves, to settings that a priori have seemingly nothing to do with Banach spaces, such as group theory, harmonic analysis, probability and combinatorial optimization.

1By [58, Remark 5.10] there does exist a bi-Hölder embedding of L_{q} into L_{p} when 2 < q < p < ∞. Hence, the pertinent question is to determine which Hölder exponents are possible here. The non-Lipschitz setting therefore exhibits phenomena that are truly nonlinear and cannot be explained by a direct reduction to the linear theory.

Among the first questions that one would ask about bi-Lipschitz embeddings is to characterise those p, q ∈ [1, ∞) such that L_{q} fails to admit a bi-Lipschitz embedding into L_{p}. Not surprisingly, efforts to understand this question influenced some of the most important developments in the Ribe program. By a reduction to the linear theory through differentiation in a manner that is similar to what we described above, the qualitative answer here is known: L_{q} does not admit a bi-Lipschitz embedding into L_{p} if and only if p, q ∈ [1, ∞) satisfy one of the following three conditions.

q < min{p, 2}  or  q > max{p, 2}  or  2 < q < p < ∞.  (1)

The search for metric invariants that explain the first range in (1) was an important impetus in the development of the theory of type of metric spaces, with notable contributions by Enflo [29, 30, 31], Bourgain–Milman–Wolfson [19], Pisier [78] and Ball [9]; see also [71, 70, 60, 68, 73, 35, 69, 27, 39, 67]. The search for metric invariants that explain the second range in (1) was an important impetus in the development of the theory of cotype of metric spaces; see the work of Mendel and Naor [61] as well as [9, 34, 63, 64]. The second range in (1) could also be explained through a metric invariant called Markov convexity; see [17, 47, 62]. Over the years, many applications of the above invariants (metric type, metric cotype, Markov convexity) to a wide range of areas were discovered; the above mentioned references contain examples of such results, and a variety of additional examples appears in [51, 13, 59, 8, 86, 48, 7, 86, 65, 4, 22]. Despite these developments, the question of formulating a metric invariant that explains the third range in (1) remained unresolved for many years. Here we settle this remaining case by introducing an invariant of metric spaces that serves as an obstruction to the embeddability of L_{q} into L_{p} when 2 < q < p < ∞, thus completing the repertoire of metric invariants that classify those p, q ∈ [1, ∞) for which L_{q} admits a bi-Lipschitz embedding into L_{p}.

Our new metric invariant is described in the following definition, in which (and in what follows) for every n ∈ ℕ we let e_{1}, …, e_{n} denote the standard basis of ℝ^{n}, and for S ⊆ {1, …, n} and ε = (ε_{1}, …, ε_{n}) ∈ {−1, 1}^{n} we denote ε_{S} = ∑_{j∈S} ε_{j}e_{j}.

Definition 1.1 (X_{p} metric space). Let (X, d_{X}) be a metric space and p ∈ (0, ∞). Say that (X, d_{X}) is an X_{p} metric space if there exists 𝔛 ∈ (0, ∞) such that for every n ∈ ℕ and k ∈ {1, …, n} there exists m ∈ ℕ such that every mapping f : ℤ_{2m}^{n} → X satisfies

(\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼[d_{X}(f(x + mε_{S}), f(x))^{p}])^{\frac{1}{p}}

⩽ 𝔛m(\frac{k}{n} ∑_{j=1}^{n} 𝔼[d_{X} (f(x + e_{j}), f(x))^{p} ] + (\frac{k}{n})^{\frac{p}{2}} 𝔼[d_{X}(f(x + ε), f(x))^{p}])^{\frac{1}{p}} , (2)

where the expectations in (2) are with respect to (x, ε) ∈ ℤ_{2m}^{n} × {−1, 1}^{n} chosen uniformly at random. The infimum over those 𝔛 ∈ (0, ∞) for which (2) holds true is denoted 𝔛_{p}(X, d_{X}), or simply 𝔛_{p}(X) if the metric is clear from the context.

Theorem 1.2 below establishes that L_{p} is an X_{p} metric space when p ⩾ 2. We shall also check that L_{q} is not an X_{p} metric space when q ∈ (2, p). Since for a metric space (X, d_{X}) the property of being an X_{p} metric space is obviously inherited by all the metric spaces that admit a bi-Lipschitz embedding into X, we thus obtain a new proof of the fact that L_{q} fails to admit a bi-Lipschitz embedding into L_{p} when 2 < q < p < ∞. We shall show that the metric X_{p} invariant yields results that were beyond the reach of previous methods. For example, we shall obtain the first nontrivial upper bound on those θ ∈ (0, 1] for which L_{q} admits a bi-θ-Hölder embedding into L_{p}.

The above overview covered the context of our results without going into various technicalities, and as such it did not provide an explanation of how we arrived at Definition 1.1. There are also technical subtleties that partially explain (in hindsight) why understanding the third range in (1) remained open for so much longer than the same question for the first two ranges in (1). These matters will be clarified in the remainder of this introduction starting from Section 1.2 below, where we shall also describe consequences of our work, including new results even within the linear theory, as well as intriguing open questions that it raises.

1.2. Detailed statements and technical background. The ensuing discussion uses standard notation and terminology from Banach space theory, as in [50]. In particular, for p ∈ [1, ∞] and n ∈ ℕ, the space ℓ_{p}^{n} (respectively ℓ_{p}^{n}(ℂ)) denotes the vector space ℝ^{n} (respectively ℂ^{n}), equipped with the standard ℓ_{p} norm. Our results apply equally well to any infinite dimensional Lebesgue function space L_{p}(μ), but for concreteness we fix (as usual) the space L_{p} to be equal to L_{p}([0, 1], ℒ), where ℒ is the Lebesgue measure. Banach spaces are assumed to be over real scalars unless stated otherwise, though our results hold true mutatis mutandis for complex Banach spaces as well.

We shall also use standard notation and terminology from the theory of metric embeddings, as in [55, 74]. In particular, a metric space (X, d_{X}) is said to admit a bi-Lipschitz embedding into a metric space (Y, d_{Y}) if there exist s ∈ (0, ∞), D ∈ [1, ∞) and a mapping f : X → Y such that

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

When this happens we say that (X, d_{X}) embeds into (Y, d_{Y}) with distortion at most D. Given f : X → Y, the infimum over those D ∈ [1, ∞) for which there exists s ∈ (0, ∞) such that (3) holds true is called the distortion of f and is denoted dist(f). If no such D exists set dist(f) = ∞. We denote by c_{(Y,d_{Y} )}(X, d_{X}) (or simply c_{Y} (X) if the metrics are clear from the context) the infimum over those D ∈ [1, ∞] for which (X, d_{X}) embeds into (Y, d_{Y}) with distortion at most D. If (X, d_{X}) does not admit a bi-Lipschitz embedding into (Y, d_{Y}) then we set c_{(Y,d_{Y} )}(X, d_{X}) = ∞. When Y = L_{p} we use the shorter notation c_{L_{p}}(X, d_{X}) = c_{p}(X, d_{X}).

As we discussed in Section 1.1, among the simplest and most basic questions that one could ask in the context of metric embeddings is to determine those p, q ∈ [1, ∞) for which L_{q} admits a bi-Lipschitz embedding into L_{p}. This is well understood via a reduction to the linear theory, from which we deduce that L_{q} admits a bi-Lipschitz embedding into L_{p} if and only if either q = 2 or 1 ⩽ p ⩽ q ⩽ 2 (moreover, in these cases we have c_{p}(L_{q}) = 1). Indeed, by general principles (see Chapter 7 of [15] and the references therein), relying mainly on differentiation theorems for Lipschitz mappings between Banach spaces (the case p = 1 being somewhat different from the reflexive range), it suffices to understand when L_{q} is isomorphic to a subspace of L_{p}, a question that is perhaps among the first issues that one would investigate when studying linear embeddings of Banach spaces. Chapter 12 of Banach’s book [12] is devoted to this topic. Banach proved there that if L_{q} is isomorphic to a subspace of L_{p} then necessarily either p ⩽ q ⩽ 2 or 2 ⩽ q ⩽ p, and that L_{2} is isomorphic to a subspace of L_{p} for all p ∈ [1, ∞). Banach also conjectured [12, page 205] that L_{q} is isomorphic to a subspace of L_{p} if p < q < 2 or 2 < q < p. In the range p < q < 2, Banach’s question was answered affirmatively by Kadec [42], who showed that in this case L_{q} is linearly isometric to a subspace of L_{p}. When 2 < q < p, Banach’s question was answered negatively by Paley [75], i.e., L_{q} is not isomorphic to a subspace of L_{p} when 2 < q < p.

As we explained above, our goal here is to obtain a nonlinear version of Paley’s theorem, i.e., the formulation of a bi-Lipschitz invariant that serves as an obstruction to the embeddability of L_{q} into L_{p} when 2 < q < p. This invariant allows us to obtain nonembeddability results that were beyond the reach of previously available methods, and in addition it leads to interesting open questions. Our new invariant thus completes a long line of work on the bi-Lipschitz classification of L_{p} spaces, because the remaining cases, namely the bi-Lipschitz nonembeddability of L_{q} into L_{p} when either q ∈ [1, 2) and p > q, or q ∈ (2, ∞) and p < q, were previously understood through notions of metric type and cotype that were introduced over the past four decades (see below for more on this topic).

Our main result is the following theorem, which, using the notation and terminology of Definition 1.1, asserts that if p ∈ (2, ∞) then L_{p} is an X_{p} metric space, with 𝔛_{p}(L_{p}) ≲ p/ log p.

Theorem 1.2 (Metric X_{p} inequality). Fix p ∈ [2, ∞). Suppose that m, n ∈ ℕ and k ∈ {1, …, n} satisfy

m ⩾ \frac{n^{\frac{3}{2}} log p}{\sqrt{k}} + pn.

Then, for every f : ℤ_{4m}^{n} → L_{p} we have

\frac{(p/ log p)^{−p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{𝔼 [∥f (x + 2mε_{S}) − f(x)∥_{p}^{p}]}{m^{p}}

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

where the expectation is with respect to (x, ε) ∈ ℤ_{4m}^{n} × {−1, 1}^{n} chosen uniformly at random.

Asymptotic notation. In Theorem 1.2, and in what follows, we use the (somewhat nonstandard) convention that for a, b ∈ [0, ∞) and p ∈ [1, ∞) the notation a ≲_{p} b (respectively a ≳_{p} b) stands for a ⩽ c^{p}b (respectively a ⩾ c^{p}b) for some universal constant c ∈ (0, ∞). The notation a ≲ b (respectively a ≳ b) stands for a ⩽ cb (respectively a ⩾ cb) for some universal constant c ∈ (0, ∞). The notation a ≍ b stands for (a ≲ b)∧(b ≲ a). At times our discussion will be in the presence of an auxiliary Banach (or metric) space X, in which case the notation a ≲_{X} b will stand for a ⩽ c(X)b, where c(X) ∈ (0, ∞) is allowed to depend only on X (in fact, c(X) will always depend on certain numerical geometric invariants of X that will be clear from the context).

The term p/ log p in the left-hand side of (4) is sharp up to a universal constant factor. We defer the explanation of why (4) is called a metric X_{p} inequality to the ensuing discussion. Note that since (4) involves the p’th power of L_{p} norms, it suffices to prove its validity when f is real-valued, but we stated Theorem 1.2 for functions with values in L_{p} since this is the way by which we will apply it to prove new nonembeddability results. The fact that in Theorem 1.2 the function f is assumed to be defined on the discrete torus ℤ_{4m}^{n} rather than on ℤ_{m}^{n} is not important: for notational reasons it is beneficial to work with ℤ_{m}^{n} when the modulus m is divisible by 4, and this suffices for all of the applications of (4) that we can imagine. However, it is straightforward to modify our proof of Theorem 1.2 so as to obtain variants of (4) for functions defined on discrete tori whose modulus is not necessarily divisible by 4.

Remark 1.3. If one makes the weaker assumption m ⩾ n^{3/2}/\sqrt{k} in Theorem 1.2 then (4) holds true with the (sharp) term p/ log p in the left-hand side replaced by p^{2}/ log p. This, and additional tradeoffs of this type, can be deduced from an inspection of our proof of Theorem 1.2.

1.3. Quantitative nonembeddability. The above classification of those p, q ∈ [1, ∞) for which L_{q} admits a bi-Lipschitz embedding into L_{p} is based on an abstract reduction to linear embeddings, and as such it fails to yield a metric invariant that serves as an obstruction to bi-Lipschitz embeddings. This argument also does not imply various quantitative estimates that are inherently nonlinear and cannot be deduced from the linear theory. For example, given a metric space (X, d_{X}) and θ ∈ (0, 1], the θ-snowflake of (X, d_{X}) is defined (see e.g. [26]) to be the metric space (X, d_{X}^{θ}). A natural quantitative refinement of the assertion that L_{q} does not admit a bi-Lipschitz embedding into L_{p} is that if the θ-snowflake of L_{q} admits a bi-Lipschitz embedding into L_{p} then necessarily θ must be bounded away from 1 by a definite constant (depending on p, q). While such statements are known (through the theory of metric type and cotype; see below) when either q ∈ [1, 2) and p > q, or p ∈ (2, ∞) and q > p, in the range 2 < q < p no such quantitative refinement of bi-Lipschitz nonembeddability was previously known. For 2 < q < p, in Theorem 1.7 below we obtain, as a consequence of Theorem 1.2, an explicit δ(p, q) ∈ (0, 1) such that if the θ-snowflake of L_{q} admits a bi-Lipschitz embedding into L_{p} then necessarily θ ⩽ 1 − δ(p, q). In Section 6 we formulate a conjectural convolution inequality that is shown to yield the sharp value δ(p, q) in this context. Since Hölder mappings need not be differentiable anywhere, and moreover continuous linear mappings are necessarily Lipschitz, it seems impossible to obtain a restriction on those snowflakes of L_{q} that embed into L_{p} via a reduction to linear embeddings as above.

Another natural quantitative refinement of the bi-Lipschitz nonembeddability of L_{q} into L_{p} is, given m, n ∈ ℕ, to ask for a lower bound on c_{p}([m]_{q}^{n}), where here, and in what follows, [m]_{q}^{n} denotes the grid {0, …, m}^{n} ⊆ ℝ^{n}, equipped with the metric inherited from ℓ_{q}^{n}. While such an estimate can be obtained from general principles, namely Bourgain’s discretization theorem [18, 36] (see Remark 3.2 below), in Theorem 1.11 we obtain, as a consequence of Theorem 1.2, the best known lower bound on c_{p}([m]_{q}^{n}) when 2 < q < p. The convolution inequality that is conjectured in Section 6 is shown to imply an asymptotically sharp evaluation of c_{p}([m]_{q}^{n}), exhibiting a striking phase transition when m ≍ n^{(p−q)/(q(p−2))}; see Theorem 1.14 below.

1.4. Local invariants. Suppose that p, q ∈ [1, ∞) are such that L_{q} does not admit a bi-Lipschitz embedding into L_{p}. This assertion is local in the sense that the smallest possible distortion of a linear embedding of ℓ_{q}^{n} into L_{p} tends to ∞ with n. Thus, there is a finite dimensional linear obstruction (which will be stated explicitly in Section 1.5 below) showing that no n-dimensional subspace of L_{p} can be close to ℓ_{q}^{n}. As we discussed in Section 1.1, an important rigidity theorem of Ribe [81] suggests that such finite dimensional linear obstructions can be reformulated while only referring to distances between pairs of points. This is the basis for the Ribe program [17, 66, 10], and our work constitutes a completion of this program for L_{p} spaces, the previously missing case being when 2 < q < p. The next step in the Ribe program, a step that has proven in the past to be useful for various questions in metric geometry, would be to study X_{p} metric spaces in their own right. However, unlike previous advances in the Ribe program, in the present setting it seems more natural for the linear theory to be developed further before its metric counterpart is investigated; we discuss this matter and formulate some related open problems in Section 1.7 below.

1.5. Type, cotype and symmetric structures. For r, s ∈ [1, ∞), a Banach space (X, ∥ · ∥_{X}) is said to have Rademacher type r and cotype s if for every n ∈ ℕ and x_{1}, …, x_{n} ∈ X we have

(𝔼[∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{r}])^{\frac{1}{r}} ≲_{X} ( ∑_{j=1}^{n} ∥x_{j}∥_{X}^{r})^{\frac{1}{r}} and ( ∑_{j=1}^{n} ∥x_{j}∥_{X}^{s})^{\frac{1}{s}} ≲_{X} (𝔼[∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{s}])^{\frac{1}{s}} , (5)

where the expectation is with respect to ε ∈ {−1, 1}^{n} chosen uniformly at random. The infimum over the implicit constants for which (5) holds true are denoted T_{r}(X) and C_{s}(X), respectively. See [56] and the references therein for more on these important notions. It suffices to say here that if p ∈ [1, ∞) then L_{p} has type min{p, 2} and cotype max{q, 2}, from which one deduces that there exists κ(p) ∈ (0, ∞) such that if T : ℓ_{q}^{n} → L_{p} is an invertible linear operator then necessarily

dist(T) = ∥T ∥ · ∥T^{−1}∥ ⩾ κ(p) · \{ \begin{matrix}n^{\frac{1}{q} − \frac{1}{p}} & if 1 ⩽ q ⩽ p ⩽ 2, \\ n^{\frac{1}{q} − \frac{1}{2}} & if 1 ⩽ q ⩽ 2 ⩽ p < ∞, \\ n^{\frac{1}{p} − \frac{1}{q}} & if 2 ⩽ p ⩽ q, \\ n^{\frac{1}{2} − \frac{1}{q}} & if 1 ⩽ p ⩽ 2 ⩽ q. \end{matrix}  (6)

(6) follows from an application of (5) with X = L_{p}, r = min{p, 2}, s = max{p, 2} and x_{j} = T e_{j}. The bounds in (6) cannot be improved up to the value of κ(p). Thus, type and cotype constitute the finite dimensional linear invariants that were alluded to in Section 1.4, i.e., they certify (in a sharp way) that if either q ∈ [1, 2) and p > q or q ∈ (2, ∞) and q > p, then any linear embedding of ℓ_{q}^{n} into L_{p} incurs large distortion.

The usefulness of the notions of Rademacher type and cotype goes far beyond their relevance to embeddings of L_{p} spaces. For this reason (in addition to the intrinsic geometric interest arising from the Ribe program) there has been considerable effort to reformulate these notions while using only distances between pairs of points rather than linear combinations of vectors as in (5), thereby understanding when a metric space has type r and cotype s. We will quickly recall now a very small part of what is known in this direction, stating only those results that are needed for the present discussion on metric X_{p} inequalities.

Following Enflo [31], a metric space (X, d_{X}) is said to have Enflo type r ∈ [1, ∞) if for every n ∈ ℕ and f : {−1, 1}^{n} → X,

𝔼 [d_{X}(f(ε), f(−ε))^{r}] ≲_{X} ∑_{j=1}^{n} 𝔼 [d_{X}(f(ε), f(ε_{1}, …, ε_{j−1}, −ε_{j}, ε_{j+1}, …, ε_{n}))^{r}] ,  (7)

where the expectation is with respect to ε ∈ {−1, 1}^{n} chosen uniformly at random. Note that if X is a Banach space then (7) coincides with the leftmost inequality in (5) when f is the linear function given by f(ε) = ∑_{j=1}^{n} ε_{j}x_{j}. For p ∈ [1, ∞), L_{p} actually has Enflo type r = min{p, 2}, i.e., X = L_{p} satisfies (7) with f : {−1, 1}^{n} → L_{p} allowed to be an arbitrary mapping rather than only a linear mapping. This statement was first proved for p ∈ [1, 2] in [29] and for p ∈ (2, ∞) in [71].

One is tempted to define when a metric space (X, d_{X}) has cotype s ∈ (0, ∞) by reversing the inequality in (7) (with r replaced by s). But, note that if d_{X}(f(ε), f(δ)) = 1 for every distinct ε, δ ∈ {−1, 1}^{n} (this can occur even if X is a Hilbert space) then the right-hand side of (7) grows linearly with n as n → ∞, while the left hand side of (7) remains bounded. Thus, there are truly nonlinear phenomena that do not occur in the linear setting of Rademacher cotype which do not allow for the straightforward reversal of the inequality in (7). In essence, the total mass of the measure that appears in the right-hand side of (7) is too large in comparison to the total mass of the measure that appears in the left-hand side of (7) for an inequality that is the reverse of (7) to make any sense even in Hilbert space (it actually fails in any non-singleton metric space; see [61]).

The solution to this problem comes by considering functions defined on ℤ_{m}^{n} rather than on {−1, 1}^{n}, and scaling the argument of the function. Specifically, following [61] say that a metric space (X, d_{X}) has metric cotype s ∈ (0, ∞) if for every n ∈ ℕ there exists m ∈ ℕ such that

∀ f : ℤ_{2m}^{n} → X,  ∑_{j=1}^{n} \frac{𝔼 [d_{X}(f(x + me_{j}), f(x))^{s}]}{m^{s}} ≲_{X} 𝔼 [d_{X}(f(x + ε), f(x))^{s}] ,  (8)

where the expectation is with respect to (x, ε) ∈ ℤ_{2m}^{n} × {−1, 0, 1}^{n} chosen uniformly at random. It was proved in [61] that a Banach space (X, ∥ · ∥_{X}) has Rademacher cotype s if and only if it has metric cotype s, in particular L_{p} has metric cotype max{p, 2}. “Scaling” refers to the fact that in (8) we consider displacements of the argument of f by a multiple of m, i.e., we consider distances between f(x+me_{j}) and f(x) rather than distances between f(x+e_{j}) and f(x), and then we compensate for this by normalizing the distances appropriately. This idea makes its appearance also in the left-hand side of our metric X_{p} inequality (4), but we shall see below that the need for scaling in the context of Theorem 1.2 is due to a more subtle reason than the above explanation of why scaling is needed in the context of metric cotype (compare the total masses of the measures that appear in both sides of (4) to see that it doesn’t cause the problem that we presented above).

1.5.1. The case 2 < q < p. While Paley’s work [75] from 1936 established that L_{q} is not isomorphic to a subspace for L_{p} when 2 < q < p, several decades later more structural approaches to this theorem were developed. In 1962, Kadec and Pełczyński [43] introduced an influential way to solve this problem through a structural study of basic sequences in L_{p} spaces. In particular, it follows from [43] that for p ∈ (2, ∞), any infinite symmetric basic sequence in L_{p} is equivalent to either the standard basis of ℓ_{p} or the standard basis of ℓ_{2}. Consequently, for q ∈ (2, p) there does not exist a symmetric basic sequence in L_{p} that is equivalent to the unit basis of ℓ_{q}, and therefore ℓ_{q} cannot be isomorphic to a subspace of ℓ_{p}. In 1979, Johnson, Maurey, Schechtman and Tzafriri [40] obtained a proof of Paley’s theorem via a classification of finite symmetric bases in function spaces, leading to a comprehensive theory of symmetric structures in Banach spaces to which the research monograph [40] is devoted. In particular, in [40] a “local” version of the above theorem of Kadec and Pełczyński is studied, leading to a classification of all finite symmetric bases in L_{p}. It turns out that in this finitary setting the classification involves more structures than those that are allowed (by the Kadec–Pełczyński theorem) for infinite symmetric sequences in L_{p}, namely, a one-parameter family of such sequences can occur, yet any finite symmetric sequence in L_{p} is equivalent to a member of this one-parameter family. This theorem of [40] is the starting point of our work here.

Given a Banach space (X, ∥ · ∥_{X}), n ∈ ℕ and K ∈ [1, ∞), recall that a linearly independent sequence of vectors (x_{1}, …, x_{n}) ∈ X^{n} is said to be K-symmetric if for every sequence of scalars a_{1}, …, a_{n} ∈ ℝ, every permutation π ∈ S_{n} and every sequence of signs ε = (ε_{1}, …, ε_{n}) ∈ {−1, 1}^{n}, we have ∥ε_{1}a_{π(1)}x_{1} + … + ε_{n}a_{π(n)}x_{n}∥_{X} ⩽ K∥a_{1}x_{1} + … + a_{n}x_{n}∥_{X}. The sequence (x_{1}, …, x_{n}) ∈ X^{n} is said to be normalized if ∥x_{j}∥_{X} = 1 for all j ∈ {1, …, n}. Given two Banach spaces (X, ∥·∥_{X}) and (Y, ∥·∥_{Y}), two sequences (x_{1}, …, x_{n}) ∈ X^{n} and (y_{1}, …, y_{n}) ∈ Y^{n} are said to be K-equivalent if there exists s ∈ (0, ∞) such that s∥a_{1}x_{1} +…+a_{n}x_{n}∥_{X} ⩽ ∥a_{1}y_{1} +…+a_{n}y_{n}∥_{Y} ⩽ Ks∥a_{1}x_{1} +…+a_{n}x_{n}∥_{X} for all choices of scalars a_{1}, …, a_{n} ∈ ℝ.

Fixing p ∈ (2, ∞), examples of symmetric sequences in L_{p} are furnished by Rosenthal’s X_{p}^{n}(ω) symmetric bases [82], as ω ranges over [0, ∞). The definition of these bases is very simple: let u_{1}, …, u_{n} be an orthonormal basis of ℓ_{2}^{n} and define {x_{j}(p, ω)}_{j=1}^{n} ⊆ (ℓ_{p}^{n} ⊕ ℓ_{2}^{n})_{p} by

x_{j}(p, ω) =^{def} \frac{1}{(1 + ω^{p})^{\frac{1}{p}}} · e_{j} + \frac{ω}{(1 + ω^{p})^{\frac{1}{p}}} · u_{j}.  (9)

The 1-symmetric sequence {x_{j}(p, ω)}_{j=1}^{n} is known in the literature as Rosenthal’s X_{p}^{n}(ω) basis. Note that since ℓ_{2} is isometric to a subset of L_{p} (see e.g. [89]), the sequence {x_{j}(p, ω)}_{j=1}^{n} can be realized as elements of L_{p}.

In [40] it was proved that for every K ∈ [1, ∞) and p ∈ (2, ∞) there exists D(p, K) ∈ (0, ∞) such that every K-symmetric sequence (x_{1}, …, x_{n}) in L_{p} is D(p, K)-equivalent to an X_{p}^{n}(ω) basis for some ω ∈ [0, ∞). This classification theorem has immediate relevance to linear embeddings of ℓ_{q}^{n} into L_{p}. Indeed, if T : ℓ_{q}^{n} → L_{p} is injective and linear then (T e_{1}, …, T e_{n}) is a dist(T)-symmetric sequence in L_{p}, and is therefore D(p, dist(T))-equivalent to an X_{p}^{n}(ω) basis for some ω ∈ (0, ∞). Direct inspection now reveals that this is only possible if dist(T) tends to ∞ as n → ∞. In fact, by computing the various bounds explicitly and optimizing over ω ∈ [0, ∞), as done in [33] (relying in part on a computation from [37]), one can deduce that for every 2 < q < p < ∞ there exists σ(p, q) ∈ (0, ∞) such that for every invertible linear mapping T : ℓ_{q}^{n} → L_{p} we have

dist(T) ⩾ σ(p, q) · n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} .  (10)

The lower bound in (10) is asymptotically sharp (up to the implicit dependence on p, q), as exhibited by the embedding J_{(q→p;n)}^{R} : ℓ_{q}^{n} → (ℓ_{p}^{n} ⊕ ℓ_{2}^{n})_{p} ⊆ L_{p} given by^{2}

∀ j ∈ \{1, …, n\},  J_{(q→p;n)}^{R}(e_{j}) =^{def} n^{\frac{1}{2}} · e_{j} + n^{\frac{1}{q}} · u_{j},  (11)

where, as in (9), u_{1}, …, u_{n} is an orthonormal basis of ℓ_{2}^{n}. Indeed, by a straightforward Langrange multiplier argument (see Section 2 below), for every 2 < q ⩽ p we have

dist(J_{(q→p;n)}^{R}) ≍ n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} .  (12)

A sequence of random variables {Y_{j}}_{j=1}^{n} is said to be symmetrically exchangeable if for every π ∈ S_{n} and ε ∈ {−1, 1}^{n} the random vectors (ε_{1}Y_{π(1)}, …, ε_{n}Y_{π(n)}) and (Y_{1}, …, Y_{n}) are identically distributed. The proof of the above classification of finite symmetric sequences in L_{p} relies on the following inequality [40]. Fix p ∈ [2, ∞) and suppose that {Y_{j}}_{j=1}^{n} are symmetrically exchangeable random variables with 𝔼[|Y_{j}|^{p}] = 1 for all j ∈ {1, …, n}. Then for every t_{1}, …, t_{n} ∈ ℝ,

(\frac{log p}{p})^{p} · 𝔼 [| ∑_{j=1}^{n} t_{j}Y_{j}|^{p}] ≲_{p} ∑_{j=1}^{n} |t_{j}|^{p} + (\frac{1}{n} ∑_{j=1}^{n} t_{j}^{2})^{\frac{p}{2}} 𝔼 [(∑_{j=1}^{n} Y_{j}^{2})^{\frac{p}{2}} ] .  (13)

The term (log p)/p in the left-hand side of (13) is sharp up to a universal constant factor: in this sharp form the inequality (13) is due to [41]. Without a sharp dependence on p, inequality (13) was first proved in [40]. The proof of (13) with sharp dependence on p is significantly more involved than the proof in [40]. The dependence on p is not of major importance for us here, but it is worthwhile to state the above sharp form of (13) since it is available in the literature.

Fix p ∈ [2, ∞), n ∈ ℕ and a_{1}, …, a_{n} ∈ ℝ. For (ε, π) ∈ {−1, 1}^{n}×S_{n} chosen uniformly at random, define

Y_{j}(ε, π) =^{def} \frac{ε_{j}a_{π(j)}}{(\frac{1}{n} ∑_{s=1}^{n} |a_{s}|^{p})^{\frac{1}{p}}} .

Then {Y_{j}}_{j=1}^{n} are symmetrically exchangeable random variables (the underlying probability space being the uniform measure on {−1, 1}^{n} × S_{n}), with 𝔼[|Y_{j}|^{p}] = 1. For k ∈ {1, …, n}, an application of (13) with t_{1} = … = t_{k} = 1 and t_{k+1} = … = t_{n} = 0 therefore yields the following inequality.

\frac{(p/ log p)^{−p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼 [| ∑_{j∈S} ε_{j}a_{j}|^{p}] ≲_{p} \frac{k}{n} ∑_{j=1}^{n} |a_{j}|^{p} + (\frac{k}{n})^{\frac{p}{2}} (∑_{j=1}^{n} a_{j}^{2})^{\frac{p}{2}} ,  (14)

where in (14), as well as in (15), (16), (17) and (18) below, the expectation is with respect to ε ∈ {−1, 1}^{n} chosen uniformly at random. Since, by Jensen’s inequality,

(∑_{j=1}^{n} a_{j}^{2})^{\frac{p}{2}} = (𝔼 [| ∑_{j=1}^{n} ε_{j}a_{j}|^{2}])^{\frac{p}{2}} ⩽ 𝔼 [| ∑_{j=1}^{n} ε_{j}a_{j}|^{p}] ,  (15)

2The superscript in the notation J_{(q→p;n)}^{R}(·) refers to Rosenthal.

it follows from (14) that

\frac{(p/ log p)^{−p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼 [| ∑_{j∈S} ε_{j}a_{j}|^{p}] ≲_{p} \frac{k}{n} ∑_{j=1}^{n} |a_{j}|^{p} + (\frac{k}{n})^{\frac{p}{2}} 𝔼 [| ∑_{j=1}^{n} ε_{j}a_{j}|^{p}] .  (16)

An inspection of the argument in [41] reveals that the term p/ log p in (16) is sharp up to a constant factor even in this special case of (13) (this is true if one requires the validity of (16) for all k ∈ {1, …, n}, while for a fixed k there might be a better dependence as a function of k, n, p).

Our main result, namely Theorem 1.2, is a nonlinear version of (16). By following the reasoning that led to the definition (7) of Enflo type, one is tempted to try to establish the validity of the following inequality, which should hold true for every f : {−1, 1}^{n} → ℝ and for some α(p) ∈ (0, ∞).

\frac{α(p)}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼[ |f(ε) − f (ε_{\{1,...,n\}∖S} − ε_{S})|^{p} ]

⩽ \frac{k}{n} ∑_{j=1}^{n} 𝔼[|f(ε) − f(ε_{1}, …, ε_{j−1}, −ε_{j}, ε_{j+1}, …, ε_{n})|^{p}] + (\frac{k}{n})^{\frac{p}{2}} 𝔼[ |f(ε) − f(−ε)|^{p} ]. (17)

Inequality (17) holds true when p = 2. Indeed, the fact that the real line has Enflo type 2 with constant 1 (as shown by Enflo in [29]) implies that for every S ⊆ {1, …, n} we have

𝔼[ |f(ε) − f (ε_{{1,...,n}∖S} − ε_{S})|^{2} ] ⩽ ∑_{j∈S} 𝔼[ |f(ε) − f(ε_{1}, …, ε_{j−1}, −ε_{j}, ε_{j+1}, …, ε_{n})|^{2} ]. (18)

By averaging (18) over all of those S ⊆ {1, …, n} satisfying |S| = k we see that (17) holds true when p = 2, with α(2) = 1 and even without the final term in the right-hand side of (17).

The validity of (17) for p = 2 indicates that the reason why scaling is needed for the definition (8) of metric cotype does not arise in the context of (17). However, Proposition 1.4 below shows that scaling is nevertheless necessary in the context of metric X_{p} inequalities, thus explaining our formulation of Theorem 1.2. Note that the conclusion of Theorem 1.2 implies the linear X_{p} inequality (16). Roughly speaking, this follows by applying (4) to the linear function f : ℤ_{4m}^{n} → ℝ given by f(x) = ∑_{j=1}^{n} x_{j}a_{j}. However, this reasoning isn’t quite accurate because this f isn’t well defined as a function on the discrete torus ℤ_{4m}^{n}; for a precise argument see Proposition 2.1 below.

Proposition 1.4 (Scaling is necessary). Fix p ∈ (2, ∞), α ∈ (0, 1), m, n ∈ ℕ and k ∈ {1, …, n}. Suppose that for every f : ℤ_{2m}^{n} → ℝ we have

\frac{α^{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{𝔼[ |f (x + mε_{S}) − f(x)|^{p} ]}{m^{p}}

⩽ \frac{k}{n} ∑_{j=1}^{n} 𝔼[ |f(x + e_{j}) − f(x)|^{p} ] + (\frac{k}{n})^{\frac{p}{2}} 𝔼[ |f (x + ε) − f(x)|^{p} ], (19)

where the expectation is with respect to (x, ε) ∈ ℤ_{2m}^{n} × {−1, 1}^{n} chosen uniformly at random. Then

k ⩾ (\frac{5}{α})^{\frac{2p}{p−2}} ⟹ m ⩾ \frac{α}{3}\sqrt{\frac{n}{k}}.  (20)

The proof of Proposition 1.4 appears in Section 2. We conjecture that the dependence of m on n and k that appears in Proposition 1.4 is sharp, up to the (possibly p-dependent) constant. This is the content of Conjecture 1.5 below. It seems that in order to prove Conjecture 1.5 one would need to exploit cancelations that are more subtle than those that we used to prove Theorem 1.2.

Conjecture 1.5. For every p ∈ (2, ∞) there exist α_{p} ∈ (0, 1) and C_{p} ∈ [1, ∞) such that if m, n ∈ ℕ and k ∈ \{1, …, n\} satisfy m ⩾ C_{p}\sqrt{n/k} then for every f : ℤ_{4m}^{n} → ℝ we have

\frac{α_{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{𝔼[ |f (x + 2mε_{S}) − f(x)|^{p} ]}{m^{p}}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} 𝔼[ |f(x + e_{j}) − f(x)|^{p} ] + (\frac{k}{n})^{\frac{p}{2}} 𝔼[ |f (x + ε) − f(x)|^{p} ], (21)

where the expectation is with respect to (x, ε) ∈ ℤ_{4m}^{n} × {−1, 1}^{n} chosen uniformly at random.

We will see in Section 1.6.3 below that, in addition to its intrinsic interest, a positive resolution of Conjecture 1.5 would have striking consequences in the theory of metric embeddings. A conjectural convolution inequality (of independent interest) that we formulate in Question 6.1 below is shown in Proposition 6.2 below to imply a positive answer to Conjecture 1.5.

Before passing to a description of the geometric consequences of Theorem 1.2, we note that the linear X_{p} inequality (16) also has a (much easier) converse [40]. Specifically, for every p ∈ (2, ∞) there exists K(p) ∈ (0, ∞) such that for every a_{1}, …, a_{n} ∈ ℝ and k ∈ {1, …, n} we have

\frac{k}{n} ∑_{j=1}^{n} |a_{j}|^{p} + (\frac{k}{n})^{\frac{p}{2}} 𝔼 [| ∑_{j=1}^{n} ε_{j}a_{j}|^{p}] ⩽ \frac{K(p)^{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼 [| ∑_{j∈S} ε_{j}a_{j}|^{p}] ,  (22)

where the expectation is over ε ∈ {−1, 1}^{n} chosen uniformly at random. An inspection of the proof of (22) in [40] (or in [41]) reveals that one can take K(p) ≲ \sqrt{p} in (22). Theorem 1.6 below is a nonlinear version of (22). Although we do not have a new geometric application of the reverse metric X_{p} inequality that appears in Theorem 1.6, it is worthwhile to establish it so as to obtain a complete picture of the X_{p} phenomenon in the metric setting. As a side product, our proof of Theorem 1.6 yields some new information on metric cotype; see Theorem 5.2 below and the discussion immediately preceding it.

Theorem 1.6 (Reverse metric X_{p} inequality). Fix p ∈ [2, ∞) and k, m ∈ ℕ with m ⩾ \frac{k^{1/p}}{\sqrt{p}}. Fix also an integer n ⩾ k. Then for every f : ℤ_{8m}^{n} → L_{p} we have

\frac{k}{n} ∑_{j=1}^{n} \frac{𝔼 [∥f(x + 4me_{j}) − f(x)∥_{p}^{p}]}{m^{p}} + (\frac{k}{n})^{\frac{p}{2}} 𝔼 [∥f (x + ε) − f(x − ε)∥_{p}^{p}]

≲_{p} \frac{p^{\frac{p}{2}}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼 [∥f (x + ε_{S}) − f(x)∥_{p}^{p}] , (23)

where the expectation is with respect to (x, ε) ∈ ℤ_{8m}^{n} × {−1, 1}^{n} chosen uniformly at random.

1.6. Metric X_{p} inequalities as obstructions to embeddings. Theorem 1.2 yields a bi-Lipschitz invariant that can be used to obtain new nonembeddability results which we shall now describe.

1.6.1. Snowflakes. Fix p, q ∈ [1, ∞). Sharp restrictions on those θ ∈ (0, 1] for which the θ-snowflake of L_{q} admits a bi-Lipschitz embedding into L_{p} follow from the theory of metric type and cotype when either q ∈ [1, 2] and p ⩾ q, or q ∈ [2, ∞) and p ⩽ q; see [52, 59, 34]. Here we obtain, as a consequence of Theorem 1.2, the first such result when 2 < q < p.

Theorem 1.7 (L_{q} snowflakes in L_{p}). For every 2 < q < p there exists δ(p, q) > 0 such that if θ ∈ (0, 1) is such that the metric space (L_{q}, ∥x − y∥_{q}^{θ}) admits a bi-Lipschitz embedding into L_{p} then necessarily θ ⩽ 1 − δ(p, q). Specifically, θ must satisfy

θ ⩽ \frac{2q(p − q) + q^{2}(p − 1)(p − 2)}{2p^{2}(q − 2)} (\sqrt{1 + \frac{4p(p − 2)(q − 2)}{(pq − 3q + 2)^{2}}} − 1) ⩽ 1 − \frac{(p − q)(q − 2)}{2p^{3}}.  (24)

It was shown in [58, Remark 5.10] that for 2 < q < p that the (q/p)-snowflake of L_{q} is isometric to a subset of L_{p}. We conjecture that this is sharp, i.e., that the upper bound on θ that appears in (24) can be improved to θ ⩽ q/p.

Conjecture 1.8. Suppose that 2 < q < p and θ ∈ (0, 1) is such that the metric space (L_{q}, ∥x − y∥_{q}^{θ}) admits a bi-Lipschitz embedding into L_{p}. Then necessarily θ ⩽ q/p.

In fact, when 2 < q ⩽ p, we ask whether or not L_{q} has a unique snowflake that admits a bi-Lipschitz embedding into L_{p}. If true, this would be manifestly different than the case 1 ⩽ q ⩽ p ⩽ 2, where it is known [21] (see also [88]) that the metric space (L_{q}, ∥x − y∥_{q}^{θ}) admits an isometric embedding into L_{p} for every 0 < θ ⩽ q/p.

Question 1.9 (Uniqueness of snowflakes). Suppose that 2 < q ⩽ p and θ ∈ (0, 1). Is it true that if the metric space (L_{q}, ∥x − y∥_{q}^{θ}) admits a bi-Lipschitz embedding into L_{p} then necessarily θ = q/p?

The case q = p of Question 1.9 is a well-known problem that has been open for many years (though apparently not stated explicitly in the literature): is it true that if p ∈ (2, ∞) then for no θ ∈ (0, 1) the metric space (L_{p}, (∥x − y∥_{p}^{θ}) admits a bi-Lipschitz embedding into L_{p}? Related results appear in [58, Section 5].

Remark 1.10. The analogue of Conjecture 1.8 for sequence spaces has a positive answer. Indeed, a combination of [14, Cor. 2.19] and [14, Cor. 2.23] shows that for every 1 ⩽ q ⩽ p < ∞, if θ ∈ (0, 1] is such that the metric space (ℓ_{q}, ∥x−y∥_{q}^{θ}) admits a bi-Lipschitz embedding into ℓ_{p} then necessarily θ ⩽ q/p. The proof of this result in [14] relies on an infinite dimensional argument of [45] that is specific to sequence spaces (the above statement from [14] becomes false if q ∈ [1, 2], p ∈ (2, ∞) and ℓ_{p} is replaced by L_{p}). Conversely, in [2] (see also [74, Exercise 1.61]) it was shown that for every 1 ⩽ q ⩽ p < ∞ the (q/p)-snowflake of ℓ_{q} does admit a bi-Lipschitz embedding into ℓ_{p}.

1.6.2. Grids. Recall that for q ∈ [1, ∞) and m, n ∈ ℕ the integer grid {1, …, m}^{n}, equipped with the metric inherited from ℓ_{q}^{n}, is denoted [m]_{q}^{n}. Theorem 1.11 below, which is a consequence of Theorem 1.2, contains the best-known lower bound on c_{p}([m]_{q}^{n}) when 2 < q < p, thus yielding another quantitative version of the fact that L_{q} does not admit a bi-Lipschitz embedding into L_{p}.

Theorem 1.11 (L_{p} distortion of L_{q} grids). For every p ∈ (2, ∞) there exists α_{p} ∈ (0, ∞) such that for every q ∈ (2, p) and m, n ∈ ℕ we have

c_{p}([m]_{q}^{n}) ≳ α_{p} (min \{m^{\frac{q(p−2)}{q(p−2)+p−q}} , n\})^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} .  (25)

In particular,

m ⩾ n^{1+ \frac{p−q}{q(p−2)}} ⟹ c_{p} ([m]_{q}^{n}) ⩾ α_{p}n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} ≳ α_{p}c_{p}(ℓ_{q}^{n}) .  (26)

The fact that the lower bound in (25) becomes weaker for smaller m is necessary, as exhibited by the following embedding from [59]. First, let G_{2,p} : L_{2} → L_{p} be an isometric embedding of L_{2} into L_{p}. By a classical theorem of Schoenberg [83] (see also [88]) there exists an isometric embedding of the (2/q)-snowflake of ℓ_{2}^{n} into L_{2}, i.e., there exists ψ_{q}^{n} : ℓ_{2}^{n} → L_{2} such that

∀ x, y ∈ ℓ_{2}^{n}, ∥ψ_{q}^{n}(x) − ψ_{q}^{n}(y)∥_{2} = ∥x − y∥2^{\frac{2}{q}} .

Finally, let I_{q→2}^{n} : ℓ_{q}^{n} → ℓ_{2}^{n} be the identity mapping, and define^{3}

J_{(q→p;n)}^{S} =^{def} G_{2,p} ∘ ψ_{q}^{n} ∘ I_{q→2}^{n} : ℓ_{q}^{n} → L_{p}.  (27)

As argued in [59], the distortion of the restriction of J_{(q→p;n)}^{S} to [m]_{q}^{n} satisfies

dist(J_{(q→p;n)}^{S}|_{[m]_{q}^{n}}) ⩽ m^{1− \frac{2}{q}} .

Recalling the definition of the embedding J_{(q→p;n)}^{R} in (11), we therefore have

c_{p}([m]_{q}^{n}) ⩽ min \{dist(J_{(q→p;n)}^{R}|_{[m]_{q}^{n}}) , dist(J_{(q→p;n)}^{S}|_{[m]_{q}^{n}})\} ≲ min \{n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} , m^{1− \frac{2}{q}} \} . (28)

We conjecture that (28) is asymptotically sharp up to constant factors that depend only on p, q.

Conjecture 1.12. For 2 < q < p and m, n ∈ ℕ, the better of the embeddings J_{(q→p;n)}^{R} and J_{(q→p;n)}^{S} appearing in (11) and (27), respectively, is the best possible bi-Lipschitz embedding of the L_{q} integer grid [m]_{q}^{n} into L_{p}. Equivalently, c_{p}([m]_{q}^{n}) is bounded from above and from below by positive constants that may depend only on p and q times the quantity

min \{n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} , m^{1− \frac{2}{q}} \} .  (29)

In particular, there exists η(p, q) ∈ (0, 1) such that

m ⩾ n^{\frac{p−q}{q(p−2)}} ⟹ c_{p}([m]_{q}^{n}) ⩾ η(p, q)c_{p}(ℓ_{q}^{n}),

yet

m = o(n^{\frac{p−q}{q(p−2)}} ) ⟹ c_{p}([m]_{q}^{n}) = o(c_{p}(ℓ_{q}^{n})) (as n → ∞).

An affirmative answer to Conjecture 1.12 would imply that if the linear embedding J_{(q→p;n)}^{R} of ℓ_{q}^{n} into an appropriate Rosenthal X_{p}(ω) space fails to yield the best possible bi-Lipschitz embedding of [m]_{q}^{n} into L_{p} then (up to constant factors that are independent of m, n), the best possible way to embed [m]_{q}^{n} into L_{p} would be to embed it into L_{2} (ignoring the fact that we are seeking an embedding into the larger space L_{p}), via the (highly nonlinear) Schoenberg embedding ψ_{q}^{n}. Admittedly, if true, this phenomenon would be quite exotic, but we conjecture that it indeed occurs partially because it is a consequence of Conjecture 1.5, as we shall see in Section 1.6.3 below.

Remark 1.13. There are also interesting open problems related to embeddings of [m]_{p}^{n} into L_{q} when p > q > 2. Specifically, by combining the upper bound in [59] with the metric cotype-based lower bound in [61], we see that

\frac{1}{\sqrt{q}} · min \{n^{\frac{1}{q} − \frac{1}{p}} , m^{1− \frac{q}{p}} \} ≲ c_{q}([m]_{p}^{n}) ⩽ min \{n^{\frac{1}{q} − \frac{1}{p}} , m^{1− \frac{2}{p}} \} .  (30)

The bounds in (30) match only when q = 2, and it remains open to evaluate c_{q}([m]_{p}^{n}) up to constant factors that are independent of m, n. An inspection of the argument in [59] reveals that the lower bound on c_{q}([m]_{p}^{n}) in (30) would be sharp (up to constant factors that may depend only on p, q) if the (q/p)-snowflake of L_{q} admitted a bi-Lipschitz embedding into L_{q}. When q = 2 this is indeed the case due to the theorem of Schoenberg that was quoted above, but for q > 2 a positive answer to Question 1.9 (see also the paragraph immediately following Question 1.9) would imply that no nontrivial snowflake of L_{q} admits a bi-Lipschitz embedding into L_{q}. In the spirit of Conjecture 1.12, one is tempted to ask whether or not the upper bound on c_{q}([m]_{p}^{n}) in (30) is asymptotically sharp, i.e., if also in this setting it is best to embed [m]_{p}^{n} into L_{q} via an appropriate embedding into the smaller space L_{2}. However, if this were true then one would need to find a better lower bound on c_{q}([m]_{p}^{n}) than what follows from the fact that L_{q} has metric cotype q. For this reason, at present we do not have a concrete conjecture as to the sharp asymptotics of c_{q}([m]_{p}^{n}) when p > q > 2.

3The superscript in the notation J_{(q→p;n)}^{S}(·) refers to Schoenberg.

1.6.3. Consequences of Conjecture 1.5. The following theorem asserts that Conjecture 1.5 implies a positive solution of Conjecture 1.8 and Conjecture 1.12. Thus, obtaining the conjecturally sharp value of m in the metric X_{p} inequality of Theorem 1.2, in addition to its intrinsic analytic interest, would yield striking nonembeddability results. As we mentioned earlier, in Section 6 we present a concrete convolution inequality (that is interesting on its own right) and prove that it implies an affirmative answer to Conjecture 1.5, and hence also to Conjecture 1.8 and Conjecture 1.12.

Theorem 1.14. If Conjecture 1.5 holds true then for every 2 < q < p and θ ∈ (0, 1),

c_{p}(L_{q}, ∥x − y∥_{q}^{θ}) < ∞ ⟹ θ ⩽ \frac{q}{p}.  (31)

Moreover, for every m, n ∈ ℕ the L_{p} distortion of the L_{q} grid [m]_{q}^{n} is bounded from above and below by a constant that may depend only on p times the quantity appearing in (29).

1.7. X_{p} metric spaces? For p ∈ (0, ∞), by pursuing the Ribe program in light of Theorem 1.2, one arrives at Definition 1.1 of when a metric space (X, d_{X}) is an X_{p} metric space. One would then want to investigate the structure of such metric spaces, motivated in part by analogies from the linear theory. However, in contrast to previous successful steps in the Ribe program, in the present setting the linear theory of X_{p} spaces hasn’t been studied yet, and it therefore seems to be more natural to first understand what makes a Banach space an X_{p} Banach space. Specifically, say that a Banach space (X, ∥ · ∥_{X}) is an X_{p} Banach space if for every n ∈ ℕ and k ∈ {1, …, n}, every v_{1}, …, v_{n} ∈ X satisfy

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} 𝔼 [∥ ∑_{j∈S} ε_{j}v_{j}∥_{X}^{p} ] ≲_{X} \frac{k}{n} ∑_{j=1}^{n} ∥v_{j}∥_{X}^{p} + (\frac{k}{n})^{\frac{p}{2}} 𝔼 [∥ ∑_{j=1}^{n} ε_{j}v_{j}∥_{X}^{p} ] ,

where the expectation is over ε ∈ {−1, 1}^{n} chosen uniformly at random. Being an X_{p} Banach space is clearly a local property. Our proof of Theorem 1.2 shows that a Banach space is an X_{p} metric space if and only if it is an X_{p} Banach space, thus completing the Ribe program in this setting.

For p > 2, it seems that the only Banach spaces that were previously known to be X_{p} Banach spaces were those that are isomorphic to subspaces of L_{p}. However, there exist separable X_{p} Banach spaces that are not isomorphic to a subspace of L_{p}. In Section 7 we prove that for p ∈ [2, ∞) the Schatten p trace class S_{p} is an X_{p} Banach space. The fact that S_{p} is not isomorphic to a subspace of L_{p} was proved in [57] (see also [77]). Obtaining a satisfactory understanding of those Banach spaces that are X_{p} spaces remains an interesting, though probably quite difficult, research challenge.

Since S_{p} is an X_{p} Banach space, our work here shows that it is also an X_{p} metric space. The nonembeddability results that were stated above for embeddings into L_{p} therefore hold true for embeddings into S_{p} as well. In the setting of S_{p}, these nonembeddability results are new even in the linear category. It was known that for 2 < q < p the Banach–Mazur distance of ℓ_{q}^{n} to any subspace of S_{p} must tend to ∞ with n: this follows from the non-commutative Kadec–Pełczyński result in [84]; see also Theorem 10.7 in [80]. The literature gives no information on the rate at which c_{S_{p}}(ℓ_{q}^{n}) tends to infinity with n (extracting quantitative estimates from the proof in [84], if at all possible, would probably require significant effort and yield weak bounds). Here we see that c_{S_{p}}(ℓ_{q}^{n}) is asymptotically n^{(p−q)(q−2)/(q^{2}(p−2))}, up to constant factors that may depend only on p, q.

2. Preliminaries

Here we establish some initial facts and prove some of the simpler statements that were presented in the Introduction. The results of the present section will not be used for the proofs of Theorem 1.2 and its consequences, so they could be skipped on first reading.

We shall start with the proof of Proposition 1.4, i.e., that scaling is needed for the metric X_{p} inequality of Theorem 1.2 to hold true.

Proof of Proposition 1.4. We shall use here the notation that was introduced in the statement of Proposition 1.4. Since ℓ_{2} embeds isometrically into L_{p}, by [58, Lem. 5.2] there exists F : ℤ_{2m}^{n} → L_{p} such that for every distinct x, y ∈ ℤ_{2m}^{n} we have

1 ⩽ \frac{∥F (x) − F (y)∥_{p}}{min \{2\sqrt{k}, \sqrt{∑_{j=1}^{n} |e^{πi(x_{j}−y_{j})/m} − 1|^{2}}\}} ⩽ 2.  (32)

By integrating (19) we see that

\frac{α^{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{𝔼 [∥F (x + mε_{S}) − F (x)∥_{p}^{p}]}{m^{p}}

⩽ \frac{k}{n} ∑_{j=1}^{n} 𝔼 [∥F (x + e_{j}) − F (x)∥_{p}^{p}] + (\frac{k}{n})^{\frac{p}{2}} 𝔼 [∥F (x + ε) − F (x)∥_{p}^{p}] . (33)

It follows from (32) that if S ⊆ \{1, …, n\} satisfies |S| = k then ∥F (x + mε_{S}) − F (x)∥_{p} ⩾ 2\sqrt{k} for every x ∈ ℤ_{2m}^{n}. Also, the elementary inequality |e^{πi/m} − 1|^{2} ⩽ π^{2}/m^{2} implies that for every j ∈ {1, …, n} we have ∥F (x + e_{j}) − F (x)∥_{p} ⩽ 2π/m, and for every (x, ε) ∈ ℤ_{2m}^{n} × {−1, 1}^{n} we have ∥F (x + ε) − F (x)∥_{p} ⩽ 4\sqrt{k}. In conjunction with (33) these estimates show that

\frac{2^{p}α^{p}k^{\frac{p}{2}}}{m^{p}} ⩽ \frac{2^{p}π^{p}k}{m^{p}} + \frac{(4k)^{p}}{n^{\frac{p}{2}}} ,

which yields the desired implication (20). □

Next, we shall check the validity of (12), i.e., evaluate the distortion of the mapping J_{(q→p;n)}^{R} given in (11). This is a known (and easy) statement which is included here only because we could not locate a clean reference for it.

Proof of (12). The definition (11) implies that for every x ∈ ℓ_{q}^{n} we have

∥J_{(q→p;n)}^{R}(x)∥_{(ℓ_{p}^{n}⊕ℓ_{2}^{n})_{p}}^{p} = n^{\frac{p}{2}} ∥x∥_{p}^{p} + n^{\frac{p}{q}} ∥x∥_{2}^{p}.

Consequently, it suffices to show that for every x ∈ ℓ_{q}^{n} we have

\frac{n^{\frac{p}{2}} ∥x∥_{q}^{p}}{2^{\frac{p}{q}} n^{\frac{p(p−q)(q−2)}{q^{2}(p−2)}}} ⩽ n^{\frac{p}{2}} ∥x∥_{p}^{p} + n^{\frac{p}{q}} ∥x∥_{2}^{p} ⩽ 2n^{\frac{p}{2}} ∥x∥_{q}^{p}.  (34)

The rightmost inequality in (34) is an immediate consequence of the estimates ∥x∥_{2} ⩽ n^{\frac{1}{2} − \frac{1}{q}} ∥x∥_{q} and ∥x∥_{p} ⩽ ∥x∥_{q}, which hold true because 2 < q < p.

Let x ∈ ℓ_{q}^{n} with ∥x∥_{q} = 1 be such that n^{\frac{p}{2}} ∥x∥_{p}^{p} + n^{\frac{p}{q}} ∥x∥_{2}^{p} is minimal. We may also assume that the number of nonzero entries of x is minimal, and that x_{1}, …, x_{k} > 0 and x_{k+1} = … = x_{n} = 0 for some k ∈ {1, …, n}. Hence, there exists (a Lagrange multiplier) λ ∈ ℝ such that

∀ j ∈ \{1, …, k\},  n^{\frac{p}{2}} x_{j}^{p−1} + n^{\frac{p}{q}} ∥x∥_{2}^{p−2}x_{j} = λx_{j}^{q−1}.  (35)

For s ∈ [0, ∞) write ψ(s) =^{def} n^{\frac{p}{2}} s^{p−2} −λs^{q−2} +n^{\frac{p}{q}} ∥x∥_{2}^{p−2}. Since p, q > 2 we have ψ(0) > 0, and since p > q we have lim_{s→∞} ψ(s) = ∞. It follows from (35) that λ > 0, and therefore there is a unique s_{0} ∈ (0, ∞) for which ψ′(s_{0}) = 0. This means that ψ starts at a positive value, decreases on (0, s_{0}), and then increases to ∞. Consequently, there exist a, b ∈ (0, ∞) such that ψ(s) = 0 ⟹ s ∈ {a, b} for every s ∈ (0, ∞). Since by (35) we have ψ(x_{j}) = 0 for every j ∈ {1, …, k}, it follows that there exists S ⊆ {1, … k} such that x_{j} = a1_{S}(j) + b1_{{1,...,k}∖S}(j) for all j ∈ {1, …, k}. Since ∥x∥_{q} = 1, we may assume without loss of generality that a^{q}|S| ⩾ 1/2, i.e., that a ⩾ 1/(2|S|)^{1/q}. Consequently,

n^{\frac{p}{2}} ∥x∥_{p}^{p} + n^{\frac{p}{q}} ∥x∥_{2}^{p} ⩾ n^{\frac{p}{2}} |S|a^{p} + n^{\frac{p}{q}} |S|^{\frac{p}{2}} a^{p} ⩾ \frac{n^{\frac{p}{2}}}{2^{\frac{p}{q}} |S|^{\frac{p}{q} −1}} + \frac{n^{\frac{p}{q}} |S|^{\frac{p}{2} − \frac{p}{q}}}{2^{\frac{p}{q}}} ⩾ 2^{− \frac{p}{q}} n^{\frac{p}{2} − \frac{p(p−q)(q−2)}{q^{2}(p−2)}} ,

where the last step follows by computing the minimum of n^{\frac{p}{2}} /s^{\frac{p}{q} −1} + n^{\frac{p}{q}} s^{\frac{p}{2} − \frac{p}{q}} over s ∈ (0, ∞). □

In the present work, Banach spaces are assumed to be over real scalars unless stated otherwise. However, it will sometimes be notationally convenient to work with complex Banach spaces, and in fact all the results presented below hold true for Banach spaces over the complex numbers as well. This follows from a straightforward complexification argument. Specifically, given a real Banach space (Z, ∥ · ∥_{Z}) and p ∈ [1, ∞) denote by Z_{p}(ℂ) the following p-complexification of Z. As a vector space, Z_{p}(ℂ) = Z × Z. As usual, we consider Z_{p}(ℂ) as a vector space over ℂ by setting (a + bi)(u, v) = (au − bv, av + bu) for every u, v ∈ Z and a, b ∈ ℝ. The norm on Z_{p}(ℂ) is given by

∀(u, v) ∈ Z × Z,  ∥(u, v)∥_{Z_{p}(ℂ)} =^{def} (∫_{0}^{2π} ∥(cos θ)u − (sin θ)v∥_{Z}^{p}dθ)^{\frac{1}{p}} .  (36)

This turns (Z_{p}(ℂ), ∥ · ∥_{Z_{p}(ℂ)}) into a Banach space over the complex numbers, which is isometric as a real Banach space to a subspace of L_{p}([0, 2π], Z). For every z ∈ Z we have

∥(z, 0)∥_{Z_{p}(ℂ)}^{p} = ∥z∥_{Z}^{p} ∫_{0}^{2π} | cos θ|^{p}dθ = \frac{4\sqrt{π}Γ (\frac{p}{2} + \frac{1}{2})}{Γ (\frac{p}{2} + 1)}∥z∥_{Z}^{p}.  (37)

Hence, by considering an appropriate rescaling of the first coordinate of elements of Z_{p}(ℂ), we see that Z is isometric to a subspace of Z_{p}(ℂ). Since Z_{p}(ℂ) is a subspace of L_{p}([0, 2π], Z), all properties that are closed under ℓ_{p} sums are inherited by Z_{p}(ℂ) from Z.

The final matter that will be treated in the present section is to show that the metric X_{p} inequality of Theorem 1.2 implies the linear X_{p} inequality (16). We shall show this in the context of general Banach spaces, i.e., if a Banach space is an X_{p} metric space then it is also an X_{p} Banach space. The converse of this assertion, i.e., that an X_{p} Banach space is also an X_{p} metric space, follows from the proof of Theorem 1.2 that can be found in Section 4.

Proposition 2.1 (Metric X_{p} inequalities imply linear X_{p} inequalities). Let (Z, ∥ · ∥_{Z}) be a Banach space. Fix p ∈ [2, ∞) and γ ∈ (0, 1). Fix also m, n ∈ ℕ and k ∈ {1, …, n}. Suppose that for every f : ℤ_{2m}^{n} → Z we have

\frac{γ}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{2m}^{n}} \frac{∥f(x + mε_{S}) − f(x)∥_{Z}^{p}}{m^{p}}

⩽ \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{2m}^{n}} ∥f(x + e_{j}) − f(x)∥_{Z}^{p} + \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{2m}^{n}} ∥f(x + ε) − f(x)∥_{Z}^{p}. (38)

Then for every z_{1}, …, z_{n} ∈ Z we have

\frac{(2/π)^{2p}γ}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j∈S} ε_{j}z_{j}∥_{Z}^{p} ⩽ \frac{k}{n} ∑_{j=1}^{n} ∥z_{j}∥_{Z}^{p} + \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j}z_{j}∥_{Z}^{p} . (39)

Proof. Since (38) holds true in Z, it also holds true in its p-complexification Z_{p}(ℂ). Fixing z_{1}, …, z_{n} ∈ Z and δ ∈ {−1, 1}^{n}, apply (38) to the function f_{δ} : ℤ_{2m}^{n} → Z_{p}(ℂ) given by

∀ x ∈ ℤ_{2m}^{n}, f_{δ}(x) =^{def} ∑_{j=1}^{n} δ_{j}e^{\frac{πix_{j}}{m}} (z_{j}, 0) ∈ Z × Z.

By averaging the resulting inequality over δ ∈ {−1, 1}^{n}, we deduce that

\frac{2^{p}γ}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{δ∈\{−1,1\}^{n}} ∑_{x∈ℤ_{2m}^{n}} \frac{∥∑_{j∈S} δ_{j}e^{\frac{πix_{j}}{m}} (z_{j}, 0)∥_{Z_{p}(ℂ)}^{p}}{m^{p}}

⩽ \frac{k(2m)^{n}}{n} ∑_{j=1}^{n} |1 − e^{\frac{πi}{m}} |^{p} · ∥(z_{j}, 0)∥_{Z_{p}(ℂ)}^{p}

+ \frac{(k/n)^{\frac{p}{2}}}{4^{n}} ∑_{x∈ℤ_{2m}^{n}} ∑_{ε,δ∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} δ_{j} (e^{\frac{πi(x_{j} +ε_{j})}{m}} − e^{\frac{πix_{j}}{m}} ) (z_{j}, 0)∥_{Z_{p}(ℂ)}^{p} ,  (40)

where for the left-hand side of (40) we used the fact that e^{\frac{πi(x+mσ)}{m}} − e^{\frac{πix}{m}} = −2e^{\frac{πix}{m}} for every σ ∈ {−1, 1} and x ∈ ℤ_{2m}.

Recalling the definition (36) of the norm of Z_{p}(ℂ), for every S ⊆ {1, …, n} we have

∑_{δ∈\{−1,1\}^{n}} ∑_{x∈ℤ_{2m}^{n}} ∥∑_{j∈S} δ_{j}e^{\frac{πix_{j}}{m}} (z_{j}, 0)∥_{Z_{p}(ℂ)}^{p} = ∑_{x∈ℤ_{2m}^{n}} ∫_{0}^{2π} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j∈S} δ_{j} cos (θ + \frac{πx_{j}}{m} ) z_{j}∥_{Z}^{p} dθ

= ∑_{x∈ℤ_{2m}^{n}} ∫_{0}^{2π} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j∈S} δ_{j} |cos (θ + \frac{πx_{j}}{m} )| z_{j}∥_{Z}^{p} dθ

⩾ 2π(2m)^{n} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j∈S} \frac{δ_{j}}{2π} (∫_{0}^{2π} |cos θ| dθ) z_{j}∥_{Z}^{p} (41)

= \frac{2^{p+1}(2m)^{n}}{π^{p−1}} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j∈S} δ_{j}z_{j}∥_{Z}^{p} ,  (42)

where in (41) we used Jensen’s inequality.

To bound the first term in the right-hand side of (40), use the fact that |1 − e^{iθ}| ⩽ θ for every θ ∈ [0, π], and the identity (37) to get

∑_{j=1}^{n} |1 − e^{\frac{πi}{m}} |^{p} · ∥(z_{j}, 0)∥_{Z_{p}(ℂ)}^{p} ⩽ \frac{π^{p}}{m^{p}} (∫_{0}^{2π} | cos θ|^{p}dθ) ∑_{j=1}^{n} ∥z_{j}∥_{Z}^{p} ⩽ \frac{π^{p+1}}{m^{p}} ∑_{j=1}^{n} ∥z_{j}∥_{Z}^{p}, (43)

where we used the fact that, since p ⩾ 2, we have ∫_{0}^{2π} | cos θ|^{p}dθ ⩽ ∫_{0}^{2π} cos^{2} θdθ = π. To bound the second term in the right-hand side of (40), recall the contraction principle (see [46, Thm. 4.4]), which asserts that for every a_{1}, …, a_{n} ∈ ℝ we have

∑_{δ∈{−1,1}^{n}} ∥∑_{j=1}^{n} a_{j}δ_{j}z_{j}∥_{Z}^{p} ⩽ ( max_{j∈{1,...,n}} |a_{j}|^{p}) ∑_{δ∈{−1,1}^{n}} ∥∑_{j=1}^{n} δ_{j}z_{j}∥_{Z}^{p} .  (44)

Hence, for every x ∈ ℤ_{2m}^{n} and ε ∈ {−1, 1}^{n} we have

∑_{δ∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} δ_{j} (e^{\frac{πi(x_{j} +ε_{j})}{m}} − e^{\frac{πix_{j}}{m}} ) (z_{j}, 0)∥_{Z_{p}(ℂ)}^{p}

= ∫_{0}^{2π} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} (cos (θ + \frac{πx_{j}}{m} + \frac{πε_{j}}{m} ) − cos (θ + \frac{πx_{j}}{m} )) δ_{j}z_{j}∥_{Z}^{p} dθ

⩽ 2π ( max_{θ∈[0,2π]} max_{j∈\{1,...,n\}} |cos (θ + \frac{πx_{j}}{m} + \frac{πε_{j}}{m} ) − cos (θ + \frac{πx_{j}}{m} )|^{p}) ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} δ_{j}z_{j}∥_{Z}^{p} (45)

⩽ \frac{2π^{p+1}}{m^{p}} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} δ_{j}z_{j}∥_{Z}^{p} ,  (46)

where (45) uses (44) and (46) uses |cos (α ± π/m) − cos α| = |∫_{α}^{α±π/m} sin tdt| ⩽ π/m, which holds true for every α ∈ [0, 2π]. The desired inequality (39) follows by combining (40), (42), (43), (46). □

3. Nonembeddability

Here we assume for the moment the validity of Theorem 1.2, whose proof appears in Section 4, and proceed to deduce its geometric consequences that were stated in the Introduction. Namely, we will prove here Theorem 1.7, Theorem 1.11 and Theorem 1.14.

Proof of Theorem 1.7. We first make some preparatory elementary estimates that explain the origin of the quantities that appear in (24). Define ψ_{p,q} : ℝ → ℝ by

ψ_{p,q}(t) =^{def} \frac{3tp}{q} − 3 + (tp + 2 − \frac{2tp}{q} − p) (1 + \frac{tp − q}{q(p − 2)}) = \frac{p^{2}(q − 2)}{q^{2}(p − 2)}t^{2} + \frac{p(pq − 3q + 2)}{q(p − 2)}t − p.

Then for every s ∈ (0, 1) we have

\frac{q^{2}(p − 2)}{p} · ψ_{p,q}(1 − s) − (p − q)(q − 2) = −(2pq + 2q − 4p + pq^{2} − 3q^{2})s + p(q − 2)s^{2}

> −(2pq + 2q − 4p + pq^{2})s > −(2p^{2} − 2p + p^{3})s > −2p^{3}s.

Hence ψ_{p,q}(1 − (p − q)(q − 2)/(2p^{3})) > 0. Note that ψ_{p,q}(0) = −p < 0 and ψ_{p,q}(q/p) = −(p − q) < 0. Since ψ is quadratic with lim_{t→±∞} ψ_{p,q}(t) = ∞, it follows that ψ_{p,q} has exactly one positive zero that lies in the interval (q/p, 1 − (p − q)(q − 2)/(2p^{3})). One checks that ψ_{p,q}(θ_{p,q}) = 0, where

θ_{p,q} =^{def} \frac{2q(p − q) + q^{2}(p − 1)(p − 2)}{2p^{2}(q − 2)} (\sqrt{1 + \frac{4p(p − 2)(q − 2)}{(pq − 3q + 2)^{2}}} − 1) .

Consequently, q/p < θ_{p,q} < 1 − (p − q)(q − 2)/(2p^{3}) (in particular, the rightmost inequality in (24) is valid), and

∀ θ ∈ (0, 1),  ψ_{p,q}(θ) ⩽ 0 ⟹ θ ⩽ θ_{p,q}.  (47)

Now, suppose that (L_{q}, ∥x − y∥_{q}^{θ}) admits a bi-Lipschitz embedding into L_{p}. If θ ⩽ q/p < θ_{p,q} then we are done, so we may assume below that θ > q/p. Since ℓ_{q}(ℂ) embeds isometrically into L_{q}, there exists Λ ∈ [1, ∞) such that for every m, n ∈ ℕ there is a mapping f_{m,n} : ℤ_{4m}^{n} → L_{p} that satisfies for every x, y ∈ ℤ_{4m}^{n},

(∑_{j=1}^{n} |e^{\frac{πix_{j}}{2m}} − e^{\frac{πiy_{j}}{2m}} |^{q})^{\frac{θ}{q}} ⩽ ∥f_{m,n}(x) − f_{m,n}(y)∥_{p} ⩽ Λ (∑_{j=1}^{n} |e^{\frac{πix_{j}}{2m}} − e^{\frac{πiy_{j}}{2m}} |^{q})^{\frac{θ}{q}} .  (48)

Suppose that m ⩾ n and define k ∈ {1, …, n} by k =^{def} ⌈n^{3}/m^{2}⌉. By Theorem 1.2 and Remark 1.3, in conjunction with (48), we have

\frac{n^{\frac{3θp}{q}}}{m^{\frac{2θp}{q} +p}} = \frac{k^{\frac{θp}{q}}}{m^{p}} ⩽ (c(p)Λ)^{p} (\frac{k}{m^{θp}} + (\frac{k}{n})^{\frac{p}{2}} · \frac{n^{\frac{θp}{q}}}{m^{θp}} ) = (2c(p)Λ)^{p} (\frac{n^{3}}{m^{θp+2}} + \frac{n^{p+ \frac{θp}{q}}}{m^{(1+θ)p}} ) , (49)

where c(p) ∈ (1, ∞) may depend only on p.

Choose m ∈ ℕ by setting

m =^{def} ⌈n^{\frac{p−3+θp/q}{p−2}} ⌉ = ⌈n^{1+ \frac{θp−q}{q(p−2)}} ⌉ .

Observe that since θ > q/p and p > 2 we have m ⩾ n. The above choice of m ensures that

\frac{n^{3}}{m^{θp+2}} + \frac{n^{p+ \frac{θp}{q}}}{m^{(1+θ)p}} ≲_{p} \frac{n^{3}}{m^{θp+2}} ,

and therefore by (49) (and our choice of m) we have

n^{\frac{3θp}{q} −3+(θp+2− \frac{2θp}{q} −p)(1+ \frac{θp−q}{q(p−2)} )} ≲_{p} (c(p)Λ)^{p}.  (50)

Since (50) is supposed to hold true for n that can be arbitrarily large, we necessarily have

ψ_{p,q}(θ) = \frac{3θp}{q} − 3 + (θp + 2 − \frac{2θp}{q} − p) (1 + \frac{θp − q}{q(p − 2)}) ⩽ 0.

Recalling (47), this implies that θ ⩽ θ_{p,q}, as required. □

Before proving Theorem 1.11 we record for future use the following very simple lemma.

Lemma 3.1. For every two integers m, n ⩾ 2 there exists a mapping h_{m}^{n} : ℤ_{m}^{n} → {0, …, 4m}^{2n} such that for every q ∈ [2, ∞) and x, y ∈ ℤ_{m}^{n} we have

m (∑_{j=1}^{n} |e^{\frac{2πix_{j}}{m}} − e^{\frac{2πiy_{j}}{m}} |^{q})^{\frac{1}{q}} ⩽ ∥h_{m}^{n}(x) − h_{m}^{n}(y)∥_{q} ⩽ 3m (∑_{j=1}^{n} |e^{\frac{2πix_{j}}{m}} − e^{\frac{2πiy_{j}}{m}} |^{q})^{\frac{1}{q}} .

Proof. For every u ∈ ℤ_{m} choose a_{m}(u), b_{m}(u) ∈ {0, …, 4m} such that

|2m + 2m cos (\frac{2πu}{m}) − a_{m}(u)| ⩽ \frac{1}{2}  and  |2m + 2m sin (\frac{2πu}{m}) − b_{m}(u)| ⩽ \frac{1}{2}.

Then, for every distinct u, v ∈ ℤ_{m} we have

(|a_{m}(u) − a_{m}(v)|^{q} + |b_{m}(u) − b_{m}(v)|^{q})^{\frac{1}{q}} ⩽ \sqrt{|a_{m}(u) − a_{m}(v)|^{2} + |b_{m}(u) − b_{m}(v)|^{2}}

⩽ 2m |e^{\frac{2πiu}{m}} − e^{\frac{2πiv}{m}} | + \frac{2}{\sqrt{2}} ⩽ 3m |e^{\frac{2πiu}{m}} − e^{\frac{2πiv}{m}} | ,

since for distinct u, v ∈ ℤ_{m} we have |e^{\frac{2πiu}{m}} − e^{\frac{2πiv}{m}} | ⩾ |e^{\frac{2πi}{m}} − 1| ⩾ \frac{4}{m}. Similarly,

(|a_{m}(u) − a_{m}(v)|^{q} + |b_{m}(u) − b_{m}(v)|^{q})^{\frac{1}{q}} ⩾ \frac{1}{\sqrt{2}}\sqrt{|a_{m}(u) − a_{m}(v)|^{2} + |b_{m}(u) − b_{m}(v)|^{2}}

⩾ \frac{2 − \frac{\sqrt{2}}{4}}{\sqrt{2}} m |e^{\frac{2πiu}{m}} − e^{\frac{2πiv}{m}} | ⩾ m |e^{\frac{2πiu}{m}} − e^{\frac{2πiv}{m}} | .

Hence h_{m}^{n}(x) =^{def} (a_{m}(x_{1}), b_{m}(x_{1}), a_{m}(x_{2}), b_{m}(x_{2}), …, a_{m}(x_{n}), b_{m}(x_{n})) has the desired property. □

Proof of Theorem 1.11. We shall show that for an appropriate choice of β_{p} ∈ (0, ∞) we have

m ⩾ n^{1+ \frac{p−q}{q(p−2)}} ⟹ c_{p} ([16m]_{q}^{2n}) ⩾ β_{p}n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} .  (51)

Since [M]_{q}^{n} ⊇ [m]_{q}^{n} for every integer M ⩾ m and [m]_{q}^{N} contains an isometric copy of [m]_{q}^{n} for every integer N ⩾ n, the validity of (51) implies the desired estimate (25).

Fix D ∈ [1, ∞) and suppose that f : [16m]_{q}^{2m} → L_{p} satisfies

∀ x, y ∈ [16m]_{q}^{2n},  ∥x − y∥_{q} ⩽ ∥f(x) − f(y)∥_{p} ⩽ D∥x − y∥_{q}.  (52)

Our goal is to bound D from below. Define F : ℤ_{4m}^{n} → L_{p} by F = f ∘ h_{4m}^{n}, where h_{4m}^{n} is the mapping from Lemma 3.1. Then for every x ∈ ℤ_{4m}^{n}, every j ∈ {1, …, n}, every ε ∈ {−1, 1}^{n} and every S ⊆ {1, …, n} we have

∥F (x + e_{j}) − F (x)∥_{p} ⩽ 3mD |e^{\frac{πi}{2m}} − 1| ≲ D,  (53)

∥F (x + ε) − F (x)∥_{p} ⩽ 3mD (∑_{j=1}^{n} |e^{\frac{πiε_{j}}{2m}} − 1|^{q})^{\frac{1}{q}} ≲ Dn^{\frac{1}{q}} ,  (54)

and

∥F (x + 2mε_{S}) − F (x)∥_{p} ⩾ m (∑_{j∈S} |e^{πi} − 1|^{q})^{\frac{1}{q}} ≳ m|S|^{\frac{1}{q}} .  (55)

Denote

k = ⌈n^{\frac{p(q−2)}{q(p−2)}} ⌉ .  (56)

Then k ⩽ n and the assumption on m in (51) implies that m ⩾ n^{3/2}/\sqrt{k}. Hence, by Theorem 1.2 and Remark 1.3, combined with (53), (54) and (55), there exists K_{p} ∈ (0, ∞) such that

n^{\frac{p^{2}(q−2)}{q^{2}(p−2)}} ⩽ k^{\frac{p}{q}} ⩽ K_{p}^{p}D^{p} (k + \frac{k^{\frac{p}{2}}}{n^{\frac{p}{2} − \frac{p}{q}}} ) ≲_{p} K_{p}^{p}D^{p}n^{\frac{p(q−2)}{q(p−2)}} .

Consequently,

D ≳ \frac{n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}}}{K_{p}} .  □

Remark 3.2. Lower bounds on c_{p}([m]_{q}^{n}) that are weaker than those of Theorem 1.11 can also be deduced from general discretization principles (combined with the asymptotic computation of c_{p}(ℓ_{q}^{n}) in [33]), namely from Bourgain’s discretization theorem [18] and its quantitative improvement for L_{p} spaces in [36]. Specifically, let B_{q}^{n} denote the unit ball of ℓ_{q}^{n}. Observe that \frac{1}{m}\{−m, …, m\}^{n} contains a δ-dense subset of B_{q}^{n}, with δ ⩽ n^{1/q}/m. By Theorem 1.3 in [36] (and the discussion immediately following it) we see that there exists a universal constant γ ∈ (0, 1) such that if

\frac{n^{\frac{1}{q}}}{m} ⩽ \frac{γ}{σ(p, q)n^{2+ \frac{(p−q)(q−2)}{q^{2}(p−2)}}} ⩽ \frac{β}{n^{2}c_{p}(ℓ_{q}^{n})}

then

c_{p} ([2m]_{q}^{n}) ⩾ \frac{c_{p}(ℓ_{q}^{n})}{2} ≳ σ(p, q)n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} ,

where σ(p, q) ∈ (0, ∞) is as in (10). Consequently,

m ⩾ \frac{σ(p, q)}{γ} · n^{2+ \frac{1}{q} + \frac{(p−q)(q−2)}{q^{2}(p−2)}} = \frac{σ(p, q)}{γ} · n^{2+ \frac{p−q}{q(p−2)} + \frac{p(q−2)}{q^{2}(p−2)}} ⟹ c_{p}([2m]_{q}^{n}) ≳ σ(p, q)n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} . (57)

We note that a direct application of Bourgain’s discretization theorem [18] (which holds true also for target spaces that need not be L_{p} spaces) would imply the same bound on c_{p}([2m]_{q}^{n}) as in (57), provided that m is much larger than the requirement appearing in (57) (specifically, m would have to be at least doubly exponential in n log n).

Proof of Theorem 1.14. The proof follows the proofs of Theorem 1.7 and Theorem 1.11 with a different (optimal) setting of parameters that is made possible due to the assumed validity of Conjecture 1.5. Specifically, we are now assuming that (21) holds true provided m ⩾ C_{p}\sqrt{n/k}.

Dealing first with (31), fix θ ∈ (q/p, 1] and n ∈ ℕ. Choose m, k ∈ ℕ as follows.

m =^{def} ⌊n^{\frac{θp−q}{q(p−2)}} ⌋  and  k =^{def} ⌈\frac{C_{p}^{2}n}{m^{2}}⌉ .  (58)

Since θ > q/p we may assume that n is large enough so that m ⩾ C_{p}, in which case we have k ∈ \{1, …, n\} and m ⩾ C_{p}\sqrt{n/k}. Suppose for the sake of obtaining a contradiction that there exists f_{m,n} : ℤ_{4m}^{n} → L_{p} satisfying (48). An application of (21) then yields the following estimate.

α_{p}Cp^{\frac{2θp}{q}} n^{\frac{p(q^{2}−2θ^{2}p)}{q^{2}(p−2)}} ⩽^{(58)} \frac{α_{p}k^{\frac{θp}{q}}}{m^{p}} ⩽^{(21)∧(48)} Λ^{p} (\frac{k}{m^{θp}} + (\frac{k}{n})^{\frac{p}{2}} · \frac{n^{\frac{θp}{q}}}{m^{θp}} ) ≲_{p}^{(58)} (C_{p}Λ)^{p}n^{1−(2+θp) \frac{θp−q}{q(p−2)}} . (59)

Since (59) holds true for arbitrarily large n, we conclude that

\frac{p(q^{2} − 2θ^{2}p)}{q^{2}(p − 2)} ⩽ 1 − (2 + θp)\frac{θp − q}{q(p − 2)} = \frac{p(q^{2} − 2θ^{2}p)}{q^{2}(p − 2)} − \frac{θp(q − 2)(θp − q)}{q^{2}(p − 2)}.

Consequently θ ⩽ q/p, contradicting the initial assumption that θ > q/p. This proves (31).

Next, we have already seen in (28) that c_{p}([m]_{q}^{n}) is bounded from above by a constant multiple of the quantity appearing in (29). By arguing as in the beginning of the proof of Theorem 1.11, it therefore suffices to show that for every m, n ∈ ℕ we have

m ⩾ n^{\frac{p−q}{q(p−2)}} ⟹ c_{p} ([16m]_{q}^{2n}) ⩾ ξ(p)n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}}  (60)

for some ξ(p) ∈ (0, ∞). To this end, suppose that there exists f : [16m]_{q}^{2n} → L_{p} satisfying (52), our goal being to bound D from below. As explained in the proof of Theorem 1.11, this implies the existence of F : ℤ_{4m}^{n} → L_{p} that satisfies (53), (54) and (55). Similarly to (56), choose k ∈ ℕ to be

k =^{def} ⌈C_{p}^{2}n^{\frac{p(q−2)}{q(p−2)}} ⌉ .  (61)

We may suppose that n is large enough so that k ∈ {1, …, n}, since otherwise (60) is vacuous. The lower bound on m that is assumed in (60) implies that m ⩾ C_{p}\sqrt{n/k}, so we may apply (21), yielding, in conjunction with (53), (54) and (55), that the following holds true.

α_{p}Cp^{\frac{p}{q}} n^{\frac{p^{2}(q−2)}{q^{2}(p−2)}} ⩽^{(61)} α_{p}k^{\frac{p}{q}} ≲_{p} D^{p} (k + \frac{k^{\frac{p}{2}}}{n^{\frac{p}{2} − \frac{p}{q}}} ) ≲_{p}^{(61)} (C_{p}D)^{p}n^{\frac{p(q−2)}{q(p−2)}} ⟹ D ≳ \frac{αp^{\frac{1}{p}}}{C_{p}^{1− \frac{1}{q}}} · n^{\frac{(p−q)(q−2)}{q^{2}(p−2)}} . □

4. Proof of Theorem 1.2

Suppose from now on that m, n ∈ ℕ satisfy m ⩾ n and that R ∈ [n, 2m] is an odd integer. In what follows we shall use the canonical identification of ℤ_{4m}^{n} with [−(2m − 1), 2m − 1]^{n} ∩ ℤ^{n}. Fix S ⊆ {1, …, n} and define U_{S} ⊆ ℤ_{4m}^{n} by

U_{S} =^{def} {y ∈ [−R, R]^{n} : ∀(i, j) ∈ S × ({1, …, n} ∖ S), (y_{i}, y_{j}) ∈ (2ℤ) × (1 + 2ℤ)} .  (62)

Thus U_{S} consists for those y ∈ ℤ_{4m}^{n} satisfying |y_{j}| ⩽ R for every j ∈ {1, …, n}, and such that y_{j} is even for every j ∈ S and y_{j} is odd for every j ∈ {1, …, n} ∖ S. Observe that since R is odd, for every y ∈ U_{S} we actually have |y_{j}| < R if j ∈ S. Hence |U_{S}| = R^{|S|}(R + 1)^{n−|S|}. Given a Banach space (X, ∥ · ∥_{X}), the averaging operator corresponding to U_{S} will be denoted below by D_{S} : L_{2}(ℤ_{4m}^{n}, X) → L_{2}(ℤ_{4m}^{n}, X), i.e., for every f : ℤ_{4m}^{n} → X and x ∈ ℤ_{4m}^{n} we set

D_{S}f(x) =^{def} \frac{1}{|U_{S}|} ∑_{y∈U_{S}} f(x + y).  (63)

The following lemma extends Lemma 5.1 in [61], which corresponds to the special case |S| = 1.

Lemma 4.1. Suppose that m, n ∈ ℕ, and that R ∈ {1, …, 2m − 1} is odd. Let (X, ∥ · ∥_{X}) be a Banach space and p ∈ [1, ∞). Then for every f : ℤ_{4m}^{n} → X and S ⊆ {1, …, n} we have

∑_{x∈ℤ_{4m}^{n}} ∥f(x) − D_{S}f(x)∥_{X}^{p}

≲_{p} \frac{R^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p} + \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + ε_{S}) − f(x)∥_{X}^{p} . (64)

Proof. For every w ∈ ℤ^{n} all of whose coordinates are odd fix γ_{w} : ℕ ∪ {0} → ℤ^{n} that satisfies γ_{w}(0) = 0, γ_{w}(∥w∥_{∞}) = w and γ_{w}(t) − γ_{w}(t − 1) ∈ {−1, 1}^{n} for every t ∈ ℕ. The existence of such γ_{w} is explained in [61, Lem. 5.1], and we shall quickly recall now why this is so for the sake of completeness. We may assume without loss of generality that all the coordinates of w are positive, since for general w we could then define γ_{w} = sign(w) · γ_{|w|}, where the multiplication is coordinate-wise and we denote sign(w) = (sign(w_{1}), …, sign(w_{n})) and |w| = (|w_{1}|, …, |w_{n}|). Now, supposing that all the coordinates of w are positive, define γ_{w}(0) = 0 and, inductively, for every t ∈ ℕ such that γ_{w}(2t − 2) has already been defined, set

γ_{w}(2t − 1) =^{def} γ_{w}(2t − 2) + ∑_{j=1}^{n} e_{j} and γ_{w}(2t) =^{def} γ_{w}(2t − 1) + ∑_{\begin{matrix}j∈\{1,...,n\} \\ γ_{w}(2t−1)_{j}<w_{j} \end{matrix}} e_{j} − ∑_{\begin{matrix}j∈\{1,...,n\} \\ γ_{w}(2t−1)_{j}=w_{j} \end{matrix}} e_{j}.

This explicit definition of γ_{w} is not used below; we shall only need to know that γ_{w} exists, and that, as our construction guarantees, we have εγ_{w} = γ_{εw} for every ε ∈ {−1, 1}^{n}. Note that, since the restriction of γ_{w} to {0, …, ∥w∥_{∞}} is an ℓ_{∞} geodesic joining 0 and w, for every distinct s, t ∈ {0, …, ∥w∥_{∞}} we have γ_{w}(s) ≠ γ_{w}(t).

If y ∈ U_{S} and η ∈ {−1, 1}^{n} then all the coordinates of y − η_{S} are odd, and we can therefore consider γ_{y−η_{S}}. For every x ∈ ℤ_{4m}^{n} define γ_{x,y}^{η} : ℕ → ℤ^{n} by γ_{x,y}^{η} = x + η_{S} + γ_{y−η_{S}}. Thus γ_{x,y}^{η}(0) = x + η_{S}, γ_{x,y}^{η}(∥y − η_{S}∥_{∞}) = x + y and γ_{x,y}^{η}(t) − γ_{x,y}^{η}(t − 1) ∈ {−1, 1}^{n} for all t ∈ ℕ. Note that γ_{x,y}^{η} depends only on those coordinates of η that belong to S.

For every z ∈ ℤ_{4m}^{n} and ε, η ∈ {−1, 1}^{n} define

F_{η}(z, ε) =^{def} {(x, y) ∈ ℤ_{4m}^{n} × U_{S} : γ_{x,y}^{η}(t − 1) = z and γ_{x,y}^{η}(t) = z + ε for some t ∈ [1, ∥y − η_{S}∥_{∞}]} .

Observe that for every (x, y) ∈ ℤ_{4m}^{n}×U_{S} and η ∈ {−1, 1}^{n} there is at most one t ∈ {1, …, ∥y−η_{S}∥_{∞}} for which γ_{x,y}^{η}(t − 1) = z and γ_{x,y}^{η}(t) = z + ε.

We claim that

N =^{def} ∑_{η∈{−1,1}^{n}} |F_{η}(z, ε)|  (65)

is independent of z ∈ ℤ_{4m}^{n} and ε ∈ {−1, 1}^{n}. Indeed, for every ε, δ ∈ {−1, 1}^{n} and z, w ∈ ℤ_{4m}^{n} define a bijection ψ_{z,w}^{ε,δ} : ℤ_{4m}^{n} × U_{S} → ℤ_{4m}^{n} × U_{S} by

ψ_{z,w}^{ε,δ}(x, y) =^{def} (w − εδz + εδx, εδy).

Then for every η ∈ {−1, 1}^{n} we have γ_{ψ_{z,w}^{ε,δ}(x,y)}^{εδη} = w − εδz + εδγ_{x,y}^{η}. Consequently,

(γ_{x,y}^{η}(t − 1), γ_{x,y}^{η}(t)) = (z, z + ε) ⟺ (γ_{ψ_{z,w}^{ε,δ}(x,y)}^{εδη}(t − 1), γ_{ψ_{z,w}^{ε,δ}(x,y)}^{εδη}(t)) = (w, w + δ)

for every t ∈ {1, …, ∥y − η_{S}∥_{∞}}. This shows that for every η ∈ {−1, 1}^{n} the mapping ψ_{z,w}^{ε,δ} is a bijection between F_{η}(z, ε) and F_{εδη}(w, δ), whence |F_{η}(z, ε)| = |F_{εδη}(w, δ)|. Consequently,

∑_{η∈{−1,1}^{n}} |F_{η}(z, ε)| = ∑_{η∈{−1,1}^{n}} |F_{εδη}(w, δ)| = ∑_{η∈{−1,1}^{n}} |F_{η}(w, δ)|,

implying that the integer N defined in (65) is indeed independent of (z, ε) ∈ ℤ_{4m}^{n} × {−1, 1}^{n}. We shall need an estimate on N, which is proved by double counting as follows.

N(8m)^{n} = ∑_{z∈ℤ_{4m}^{n}} ∑_{ε,η∈{−1,1}^{n}} |F_{η}(z, ε)|

= ∑_{z∈ℤ_{4m}^{n}} ∑_{ε,η∈{−1,1}^{n}} ∑_{(x,y)∈ℤ_{4m}^{n}×U_{S}} ∑_{t=1}^{∥y−η_{S}∥_{∞}} 1_{{γ_{x,y}^{η}(t−1)=z ∧ γ_{x,y}^{η}(t)=z+ε}}

= ∑_{η∈{−1,1}^{n}} ∑_{(x,y)∈ℤ_{4m}^{n}×U_{S}} ∥y − η_{S}∥_{∞}

⩽ R(8m)^{n}|U_{S}|.

Consequently,

N ⩽ R|U_{S}|.  (66)

Now, fix f : ℤ_{4m}^{n} → X. For every x ∈ ℤ_{4m}^{n}, y ∈ U_{S} and η ∈ {−1, 1}^{n} we have

∥f(x) − f(x + y)∥_{X}^{p}

≲_{p} ∥f(x) − f(x + η_{S})∥_{X}^{p} + ∥f (γ_{x,y}^{η}(0)) − f (γ_{x,y}^{η}(∥y − η_{S}∥_{∞}))∥_{X}^{p}

≲_{p} ∥f(x) − f(x + η_{S})∥_{X}^{p} + ∥y − η_{S}∥_{∞}^{p−1} ∑_{t=1}^{∥y−η_{S}∥_{∞}} ∥f (γ_{x,y}^{η}(t − 1)) − f (γ_{x,y}^{η}(t))∥_{X}^{p}

⩽ ∥f(x) − f(x + η_{S})∥_{X}^{p} + R^{p−1} ∑_{t=1}^{∥y−η_{S}∥_{∞}} ∥f (γ_{x,y}^{η}(t − 1)) − f (γ_{x,y}^{η}(t))∥_{X}^{p} .

By averaging this inequality over η ∈ {−1, 1}^{n} we see that

∥f(x) − f(x + y)∥_{X}^{p}

≲_{p} \frac{1}{2^{n}} ∑_{η∈\{−1,1\}^{n}} ∥f(x) − f(x + η_{S})∥_{X}^{p} + \frac{R^{p−1}}{2^{n}} ∑_{η∈\{−1,1\}^{n}} ∑_{t=1}^{∥y−η_{S}∥_{∞}} ∥f (γ_{x,y}^{η}(t − 1)) − f (γ_{x,y}^{η}(t))∥_{X}^{p} .

Consequently, using the definition of the operator D_{S} and convexity, we see that

∑_{x∈Z_{4m}^{n}} ∥f(x) − D_{S}f(x)∥_{X}^{p}

⩽ \frac{1}{|U_{S}|} ∑_{x∈Z_{4m}^{n}} ∑_{y∈U_{S}} ∥f(x) − f(x + y)∥_{X}^{p}

≲_{p} \frac{1}{2^{n}} ∑_{η∈\{−1,1\}^{n}} ∑_{x∈Z_{4m}^{n}} ∥f(x) − f(x + η_{S})∥_{X}^{p}

+ \frac{R^{p−1}}{2^{n}|U_{S}|} ∑_{η∈\{−1,1\}^{n}} ∑_{t=1}^{∥y−η_{S}∥_{∞}} ∑_{x∈Z_{4m}^{n}} ∑_{y∈U_{S}} ∥f (γ_{x,y}^{η}(t − 1)) − f (γ_{x,y}^{η}(t))∥_{X}^{p}

= \frac{1}{2^{n}} ∑_{η∈\{−1,1\}^{n}} ∑_{x∈Z_{4m}^{n}} ∥f(x) − f(x + η_{S})∥_{X}^{p} + \frac{R^{p−1}N}{2^{n}|U_{S}|} ∑_{ε∈\{−1,1\}^{n}} ∑_{z∈ℤ_{4m}^{n}} ∥f(z + ε) − f(z)∥_{X}^{p}.

Recalling the upper bound on N appearing in (66), this implies the desired estimate (64). □

We record for future use the following very simple lemma.

Lemma 4.2. Suppose that (X, d_{X}) is a metric space and p ∈ [1, ∞). Then for every f : ℤ_{4m}^{n} → X, ε ∈ {−1, 1}^{n} and S ⊆ {1, …, n} we have

∑_{x∈ℤ_{4m}^{n}} d_{X} (f (x + ε_{S}) , f(x))^{p} ⩽ |S|^{p−1} ∑_{j∈S} ∑_{x∈ℤ_{4m}^{n}} d_{X} (f (x + e_{j}) , f (x))^{p} .  (67)

Proof. Write S = {j(1), …, j(|S|)} and for every ℓ ∈ {0, …, |S|} denote S(ℓ) = {j(1), …, j(ℓ)} (with the convention S(0) = ∅). Then by the triangle inequality and Hölder’s inequality, for every ε ∈ {−1, 1}^{n} we have

d_{X} (f (x + ε_{S}) , f(x))^{p} ⩽ |S|^{p−1} ∑_{ℓ=1}^{|S|} d_{X} (f (x + ε_{S(ℓ−1)} + ε_{j(ℓ)}e_{j(ℓ)}) , f (x + ε_{S(ℓ−1)}))^{p} .

Hence,

∑_{x∈ℤ_{4m}^{n}} d_{X} (f (x + ε_{S}) , f(x))^{p} ⩽ |S|^{p−1} ∑_{ℓ=1}^{|S|} ∑_{y∈ℤ_{4m}^{n}} d_{X} (f (y + ε_{j(ℓ)}e_{j(ℓ)}) , f (y))^{p}

= |S|^{p−1} ∑_{ℓ=1}^{|S|} ∑_{z∈ℤ_{4m}^{n}} d_{X} (f (z + e_{j(ℓ)}) , f (z))^{p} = |S|^{p−1} ∑_{j∈S} ∑_{z∈ℤ_{4m}^{n}} d_{X} (f (z + e_{j}) , f (z))^{p} . □

Lemma 4.3. Suppose that m, n ∈ ℕ, and that R ∈ {1, …, 2m − 1} is odd and k ∈ {1, …, n}. Let (X, ∥ · ∥_{X}) be a Banach space and p ∈ [1, ∞). Then for every f : ℤ_{4m}^{n} → X and δ ∈ {−1, 1}^{n},

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + 2mδ_{S}) − f(x)∥_{X}^{p}

≲_{p} \frac{m^{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2δ_{S}) − D_{S}f(x)∥_{X}^{p}

+ \frac{R^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p} + \frac{k^{p}}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + e_{j}) − f(x)∥_{X}^{p} . (68)

Proof. For every S ⊆ {1, …, n} with |S| = k we have

∑_{x∈ℤ_{4m}^{n}} ∥f(x + 2mδ_{S}) − f(x)∥_{X}^{p}

≲_{p} ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2mδ_{S}) − D_{S}f(x)∥_{X}^{p}

+ ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2mδ_{S}) − f(x + 2mδ_{S})∥_{X}^{p} + ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x) − f(x)∥_{X}^{p}

= ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2mδ_{S}) − D_{S}f(x)∥_{X}^{p} + 2 ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x) − f(x)∥_{X}^{p} .  (69)

The first term in (69) can be bounded as follows.

∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2mδ_{S}) − D_{S}f(x)∥_{X}^{p} ⩽ m^{p−1} ∑_{t=1}^{m} ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2tδ_{S}) − D_{S}f(x + (2t − 2)δ_{S})∥_{X}^{p}
= m^{p} ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2δ_{S}) − D_{S}f(x)∥_{X}^{p} .  (70)

The second term in (69) is bounded using Lemma 4.1 and Lemma 4.2 as follows.

∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x) − f(x)∥_{X}^{p}

≲_{p} \frac{R^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p} + |S|^{p−1} ∑_{j∈S} ∑_{x∈ℤ_{4m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p} . (71)

Note that for every x ∈ ℤ_{4m}^{n},

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{j∈S} ∥f (x + e_{j}) − f (x)∥_{X}^{p} = \frac{k}{n} ∑_{j=1}^{n} ∥f (x + e_{j}) − f (x)∥_{X}^{p} .

Hence, the desired inequality (68) follows by substituting (70) and (71) into (69) and averaging the resulting inequality over all S ⊆ {1, …, n} with |S| = k. □

Our next goal is to bound the first term in the right-hand side of (68). To this end we first recall some results from [34].

Fixing a Banach space (X, ∥·∥_{X}), consider the averaging operator A : L_{2}(ℤ_{4m}^{n}, X) → L_{2}(ℤ_{4m}^{n}, X) given, for every f : ℤ_{4m}^{n} → X and x ∈ ℤ_{4m}^{n}, by

Af(x) =^{def} \frac{1}{R^{n}} ∑_{y∈(−R,R)^{n}∩(2ℤ)^{n}} f(x + y).  (72)

For j ∈ {1, …, n} denote B_{j} = D_{{j}}, i.e., B_{j} is the averaging operator corresponding to the set U_{{j}}, which consists of those y ∈ [−R, R]^{n} such that y_{j} is even and y_{ℓ} is odd for every ℓ ∈ {1, …, n}∖{j}. (In [34] the set U_{{j}} was denoted S(j, R) and the operator B_{j} was denoted E_{j}.)

It follows from [34] that for every f : ℤ_{4m}^{n} → X, every p ∈ [1, ∞) and every ε ∈ {−1, 1}^{n} we have

∑_{x∈ℤ_{4m}^{n}} ∥(\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε)) − ∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

≲_{p} p^{p} ∑_{s=0}^{n−1} \frac{(n/R)^{(n−s)p}}{\binom{n}{s}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=s \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x + 2ε_{S}) − f(x)∥_{X}^{p} . (73)

Since (73) is only implicit in [34] (it follows from proofs in [34] rather than from explicit statements in [34]), we shall now explain how to establish (73).

Proof of (73). For every T ⊆ {1, …, n} define L_{T} ⊆ ℤ_{4m}^{n} by

L_{T} =^{def} {y ∈ (−R, R)^{n} : ∀(i, j) ∈ T × ({1, …, n} ∖ T), (y_{i}, y_{j}) ∈ 2ℤ × {0}} .

Thus L_{T} consists of those y ∈ (−R, R)^{n} all of whose coordinates are even, and all of whose coordinates that lie outside T vanish. As in [34, Def. 3.2], we let Δ_{T} : L_{2}(ℤ_{4m}^{n}, X) → L_{2}(ℤ_{4m}^{n}, X) denote the averaging operator corresponding to L_{T}, i.e., for every f : ℤ_{4m}^{n} → X and x ∈ ℤ_{4m}^{n},

Δ_{T} f(x) =^{def} \frac{1}{|L_{T} |} ∑_{y∈L_{T}} f(x + y).

We note in passing that the operator A given in (72) coincides with Δ_{{1,...,n}}.

For ε ∈ {−1, 1}^{n}, α ∈ {0, …, n} and β ∈ {0, …, α} define V_{α,β}^{ε} : L_{2}(ℤ_{4m}^{n}, X) → L_{2}(ℤ_{4m}^{n}, X) by setting for every f : ℤ_{4m}^{n} → X and x ∈ ℤ_{4m}^{n},

V_{α,β}^{ε}f(x) =^{def} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{\{1,...,n\}∖T} \\ ⟨δ,ε_{\{1,...,n\}∖T} ⟩=α−2β \end{matrix}} [Δ_{T} f (x + Rδ + ε_{T}) − Δ_{T} f (x + Rδ − ε_{T})] .  (74)

Here ⟨·, ·⟩ denotes the standard scalar product on ℝ^{n}. It is worthwhile to compare the right-hand side of (74) to the right-hand side of equation (44) in [34] (however, note that there is a difference of a normalization factor. Our R is the same as the parameter k of [34]). By combining Lemma 3.8 of [34] with Lemma 3.5 of [34] and identity (44) of [34] we see that for every α ∈ {0, …, n} and β ∈ {0, …, α} there exists h_{α,β} ∈ ℝ (related to the bivariate Bernoulli numbers; see [34, Sec. 3.1]) such that h_{0,0} = 1,

∀ α ∈ \{0, …, n\}, ∀ β ∈ \{0, …, α\},  |h_{α,β}| ≲ \frac{(α − β)!β!}{2^{α}},  (75)

and for every f : ℤ_{4m}^{n} → X and x ∈ ℤ_{4m}^{n},

∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})] = (\frac{R}{R + 1})^{n−1} ∑_{α=0}^{n} ∑_{β=0}^{α} \frac{h_{α,β}}{R^{α}} V_{α,β}^{ε}f(x).  (76)

Observe that V_{0,0}^{ε}f(x) = Af(x + ε) − Af(x − ε), so it follows from (76) that

∥∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})] − (\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε))∥_{X}

⩽^{(76)} ∑_{α=1}^{n} ∑_{β=0}^{α} \frac{|h_{α,β}|}{R^{α}} ∥V_{α,β}^{ε}f(x)∥_{X} ≲^{(75)} ∑_{α=1}^{n} \frac{1}{2^{α}} ∑_{β=0}^{α} \frac{(α − β)!β!}{R^{α}} ∥V_{α,β}^{ε}f(x)∥_{X} . (77)

By convexity, it follows from (77) that

∥∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})] − (\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε))∥_{X}^{p}

≲_{p} ∑_{α=1}^{n} \frac{1}{2^{α}} (∑_{β=0}^{α} \frac{(α − β)!β!}{R^{α}} ∥V_{α,β}^{ε}f(x)∥_{X} )^{p} ⩽ ∑_{α=1}^{n} ∑_{β=0}^{α} \frac{(α + 1)^{p−1} ((α − β)!β!)^{p}}{2^{α}R^{αp}} ∥V_{α,β}^{ε}f(x)∥_{X}^{p} .

We can therefore bound the left-hand side of (73) as follows.

∑_{x∈ℤ_{4m}^{n}} ∥(\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε)) − ∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

≲_{p} ∑_{α=1}^{n} ∑_{β=0}^{α} \frac{(α + 1)^{p−1} ((α − β)!β!)^{p}}{2^{α}R^{αp}} ∑_{x∈ℤ_{4m}^{n}} ∥V_{α,β}^{ε}f(x)∥_{X}^{p} . (78)

Since the number of terms in the sums that appear in the definition (74) of V_{α,β}^{ε} is \binom{n}{α}\binom{α}{β},

∑_{x∈ℤ_{4m}^{n}} ∥V_{α,β}^{ε}f(x)∥_{X}^{p}

⩽ \binom{n}{α}^{p−1}\binom{α}{β}^{p−1} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{\begin{matrix}δ∈\{−1,1\}^{\{1,...,n\}∖T} \\ ⟨δ,ε_{\{1,...,n\}∖T} ⟩=α−2β \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥Δ_{T} f (x + Rδ + ε_{T}) − Δ_{T} f (x + Rδ − ε_{T})∥_{X}^{p}

= \binom{n}{α}^{p−1}\binom{α}{β}^{p} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥Δ_{T} f (x + 2ε_{T}) − Δ_{T} f (x)∥_{X}^{p}

⩽ \binom{n}{α}^{p−1}\binom{α}{β}^{p} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥f (x + 2ε_{T}) − f (x)∥_{X}^{p} ,  (79)

where (79) is valid since Δ_{T} is an averaging operator.

By combining (78) with (79) we see that

∑_{x∈ℤ_{4m}^{n}} ∥(\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε)) − ∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

≲_{p} ∑_{α=1}^{n} ∑_{β=0}^{α} \frac{(α + 1)^{p−1} ((α − β)!β!)^{p}}{2^{α}R^{αp}} \binom{n}{α}^{p−1}\binom{α}{β}^{p} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥f (x + 2ε_{T}) − f (x)∥_{X}^{p}

= ∑_{α=1}^{n} \frac{(α + 1)^{p}}{2^{α}R^{αp}\binom{n}{α}} (\frac{n!}{(n − α)!})^{p} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=n−α \end{matrix}} ∑_{x∈ℤ_{4m}^{n}} ∥f (x + 2ε_{T}) − f (x)∥_{X}^{p} .  (80)

The desired estimate (73) is a consequence of (80) via the change of variable s = n − α and by using the bounds n!/(n − α)! ⩽ n^{α} and (α + 1)^{p}/2^{α} ⩽ (2p)^{p}. □

In what follows, we will use the following simple lemma several times.

Lemma 4.4. Suppose that (X, d_{X}) is a metric space. Fix S ⊆ {1, …, n} and p ∈ [1, ∞). Then for every f : ℤ_{4m}^{n} → X we have

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} d_{X} (f(x), f(x + 2ε_{S}))^{p} ⩽ 2^{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} d_{X} (f(x), f(x + ε))^{p} .  (81)

Proof. For every ε, δ ∈ {−1, 1}^{n} we have

d_{X} (f(x), f(x + 2ε_{S}))^{p}

⩽ 2^{p−1}d_{X} (f(x), f(x + ε_{S} + δ_{{1,...,n}∖S}))^{p} + 2^{p−1}d_{X} (f(x + ε_{S} + δ_{{1,...,n}∖S}), f(x + 2ε_{S}))^{p} .

Hence,

∑_{x∈ℤ_{4m}^{n}} d_{X} (f(x), f(x + 2ε_{S}))^{p}

⩽ 2^{p−1} ∑_{x∈ℤ_{4m}^{n}} (d_{X} (f(x), f(x + ε_{S} + δ_{{1,...,n}∖S}))^{p} + d_{X} (f(x + ε_{S} + δ_{{1,...,n}∖S}), f(x + 2ε_{S}))^{p})

= 2^{p−1} ∑_{x∈ℤ_{4m}^{n}} (d_{X} (f(x), f(x + ε_{S} + δ_{{1,...,n}∖S}))^{p} + d_{X} (f(x), f(x + ε_{S} − δ_{{1,...,n}∖S}))^{p}) . (82)

By averaging (82) over δ ∈ {−1, 1}^{n} while using the fact that δ_{{1,...,n}∖S} and −δ_{{1,...,n}∖S} are identically distributed, we deduce that

∑_{x∈ℤ_{4m}^{n}} d_{X} (f(x), f(x + 2ε_{S}))^{p} ⩽ \frac{2^{p}}{2^{n}} ∑_{δ∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} d_{X} (f(x), f(x + ε_{S} + δ_{\{1,...,n\}∖S}))^{p} .  (83)

If ε and δ are i.i.d. and uniformly distributed over {−1, 1}^{n} then the vector ε_{S} + δ_{{1,...,n}∖S} is also uniformly distributed over {−1, 1}^{n}. Consequently, the desired estimate (81) follows by averaging (83) over ε ∈ {−1, 1}^{n}. □

The following two lemmas contain estimates that will be used crucially in the ensuing discussion.

Lemma 4.5. Let (X, ∥ · ∥_{X}) be a Banach space. Suppose that R ⩾ 2n − 1 (in addition to the previous assumptions on R, i.e., that it is an odd integer with R ⩽ 2m). Then for every p ∈ [1, ∞) and f : ℤ_{4m}^{n} → X we have

∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥(\frac{R}{R + 1})^{n−1} (Af(x + ε) − Af(x − ε)) − ∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

≲_{p} (\frac{pn}{R})^{p} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x) − f(x + ε)∥_{X}^{p} . (84)

Proof. By summing (73) over ε ∈ {−1, 1}^{n} and using Lemma 4.4 we see that the left-hand side of (84) is at most (O(1)p)^{p} times the following quantity

(∑_{s=0}^{n−1} (\frac{n}{R})^{(n−s)p}) ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x) − f(x + ε)∥_{X}^{p} ≲ (\frac{n}{R})^{p} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x) − f(x + ε)∥_{X}^{p} ,

where in the last step we used the fact that R ⩾ 2n − 1. □

The following lemma contains an estimate that will be used to control the average over all δ ∈ {−1, 1}^{n} of the first term in the right-hand side of (68).

Lemma 4.6. Let (X, ∥ · ∥_{X}) be a Banach space and fix S ⊆ {1, …, n}. Suppose that R is an odd integer satisfying 2|S| − 1 ⩽ R ⩽ 2m. Then for every p ∈ [1, ∞) and f : ℤ_{4m}^{n} → X we have

∑_{δ∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥D_{S}f(x + 2δ_{S}) − D_{S}f(x)∥_{X}^{p}

≲_{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥∑_{j∈S} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

+ (\frac{p|S|}{R})^{p} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} ∥f(x) − f(x + ε)∥_{X}^{p} .  (85)

Proof. Denote k =^{def} |S|, T =^{def} {1, …, n} ∖ S and consider ℤ_{4m}^{n} as being equal to ℤ_{4m}^{S} × ℤ_{4m}^{T}. For every y ∈ ℤ_{4m}^{T} define f_{y} : ℤ_{4m}^{S} → X by setting for every x ∈ ℤ_{4m}^{S},

f_{y}(x) =^{def} \frac{1}{(R + 1)^{n−k}} ∑_{z∈(1+2ℤ)^{T} ∩[−R,R]^{T}} f(x, y + z).

Let A^{(S)} be the averaging operator corresponding to (72) with ℤ_{4m}^{n} replaced by ℤ_{4m}^{S}, i.e., for every h : ℤ_{4m}^{S} → X and x ∈ ℤ_{4m}^{S},

A^{(S)}h(x) =^{def} \frac{1}{R^{k}} ∑_{w∈(−R,R)^{S}∩(2ℤ)^{S}} h(x + w).

Similarly, for every j ∈ S let B_{j}^{(S)} be the averaging operator analogous to B_{j} but with ℤ_{4m}^{n} replaced by ℤ_{4m}^{S}, i.e., for every h : ℤ_{4m}^{S} → X and x ∈ ℤ_{4m}^{S},

B_{j}^{(S)}h(x) =^{def} \frac{1}{R(R + 1)^{k−1}} ∑_{\begin{matrix}a∈[−R,R]∩(2ℤ) \\ b∈([−R,R]∩(1+2ℤ))^{S∖\{j\}} \end{matrix}} h (x + ae_{j} + ∑_{s∈S∖\{j\}} b_{s}e_{s})

With these definitions, for every (x, y) ∈ ℤ_{4m}^{S} × ℤ_{4m}^{T} and j ∈ S we have

D_{S}f(x, y) = A^{(S)}f_{y}(x)  and  B_{j}f(x, y) = B_{j}^{(S)}f_{y}(x).  (86)

Since R ⩾ 2k − 1, an application of (73) to f_{y} yields the following estimate, which holds true for every fixed δ ∈ {−1, 1}^{n} and y ∈ ℤ_{4m}^{T}.

∑_{x∈ℤ_{4m}^{S}} ∥A^{(S)}f_{y}(x + 2δ_{S}) − A^{(S)}f_{y}(x)∥_{X}^{p} = ∑_{x∈ℤ_{4m}^{S}} ∥A^{(S)}f_{y}(x + δ_{S}) − A^{(S)}f_{y}(x − δ_{S})∥_{X}^{p}

≲_{p} ∑_{x∈ℤ_{4m}^{S}} ∥∑_{j∈S} δ_{j} [B_{j}^{(S)}f_{y}(x + e_{j}) − B_{j}^{(S)}f_{y}(x − e_{j})]∥_{X}^{p}

+ p^{p} ∑_{s=0}^{k−1} \frac{(k/R)^{(k−s)p}}{\binom{k}{s}} ∑_{\begin{matrix}W ⊆S \\ |W |=s \end{matrix}} ∑_{x∈ℤ_{4m}^{S}} ∥f_{y}(x + 2δ_{W}) − f_{y}(x)∥_{X}^{p} .  (87)

By summing (87) over δ ∈ {−1, 1}^{n} and y ∈ ℤ_{4m}^{T}, while using the identities (86), we see that

∑_{δ∈{−1,1}^{n}} ∑_{z∈ℤ_{4m}^{n}} ∥D_{S}f(z + 2δ_{S}) − D_{S}f(z)∥_{X}^{p}

≲_{p} ∑_{δ∈{−1,1}^{n}} ∑_{z∈ℤ_{4m}^{n}} ∥∑_{j∈S} δ_{j} [B_{j}f(z + e_{j}) − B_{j}f(x − e_{j})]∥_{X}^{p}

+ p^{p} ∑_{s=0}^{k−1} \frac{(k/R)^{(k−s)p}}{\binom{k}{s}} ∑_{\begin{matrix}W ⊆S \\ |W |=s \end{matrix}} ∑_{δ∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{S}} ∑_{y∈ℤ_{4m}^{T}} ∥f_{y}(x + 2δ_{W}) − f_{y}(x)∥_{X}^{p} . (88)

Recalling that f_{y} is obtained from f by averaging, it follows by convexity that for every W ⊆ S and δ ∈ {−1, 1}^{n} we have

∑_{x∈ℤ_{4m}^{S}} ∑_{y∈ℤ_{4m}^{T}} ∥f_{y}(x + 2δ_{W}) − f_{y}(x)∥_{X}^{p} ⩽ ∑_{z∈ℤ_{4m}^{n}} ∥f(z + 2δ_{W}) − f(z)∥_{X}^{p} .

Consequently, using Lemma 4.4 and the assumption R ⩾ 2k − 1, the final term in (88) is at most (O(1)p)^{p} times the following quantity

(∑_{s=0}^{k−1} (\frac{k}{R})^{(k−s)p}) ∑_{ε∈\{−1,1\}^{n}} ∑_{z∈ℤ_{4m}^{n}} ∥f(z + 2ε) − f(z)∥_{X}^{p}

≲_{p} (\frac{k}{R})^{p} ∑_{ε∈\{−1,1\}^{n}} ∑_{z∈ℤ_{4m}^{n}} ∥f(z + ε) − f(z)∥_{X}^{p} .

Hence (88) implies the desired inequality (85). □

Proof of Theorem 1.2. From now on choose R to be the smallest odd integer that is greater than pn, and suppose that

m ⩾ \frac{n^{3/2} log p}{\sqrt{k}} + pn.

In particular we have 2n ⩽ R ⩽ 2m. Fix x ∈ ℤ_{4m}^{n} and apply inequality (16) to the scalars a_{j} = B_{j}f(x + e_{j}) − B_{j}f(x − e_{j}). The resulting estimate is

\frac{(p/ log p)^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} |∑_{j∈S} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} |B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})|^{p}

+ \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} |∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p} .  (89)

By summing (89) over x ∈ ℤ_{4m}^{n} we deduce that

\frac{(p/ log p)^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j∈S} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p}

≲_{p} \frac{k}{n} ∑_{x∈ℤ_{4m}^{n}} ∑_{j=1}^{n} |B_{j}f(x + 2e_{j}) − B_{j}f(x)|^{p}

+ \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p} . (90)

For every j ∈ {1, …, n}, since B_{j} is an averaging operator we have

∑_{x∈ℤ_{4m}^{n}} |B_{j}f(x + 2e_{j}) − B_{j}f(x)|^{p} ⩽ ∑_{x∈ℤ_{4m}^{n}} |f(x + 2e_{j}) − f(x)|^{p} ≲_{p} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} . (91)

Recalling that R ⩾ pn, by Lemma 4.5 we have

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j=1}^{n} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p}

≲_{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Af(x + 2ε) − Af(x)|^{p} + ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}

⩽ ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + 2ε) − f(x)|^{p} + ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}  (92)

≲_{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p},  (93)

where in (92) we used the fact that A is an averaging operator.

By substituting (91) and (93) into (90) we see that

\frac{(p/ log p)^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j∈S} ε_{j} [B_{j}f(x + e_{j}) − B_{j}f(x − e_{j})]|^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} + \frac{1}{2^{n}} (\frac{k}{n})^{\frac{p}{2}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}. (94)

By averaging (85) over all S ⊆ {1, …, n} with |S| = k and substituting (94) into the resulting inequality, we obtain the following estimate.

\frac{(p/ log p)^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{δ∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |D_{S}f(x + δ_{S}) − D_{S}f(x − δ_{S})|^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} + \frac{1}{2^{n}} (\frac{k}{n})^{\frac{p}{2}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}. (95)

Next, average (68) over δ ∈ {−1, 1}^{n} and substitute (95) into the resulting inequality, thus obtaining the following estimate (recall that in the present setting R ≲ pn).

\frac{1}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} \frac{|f(x + 2mε_{S}) − f(x)|^{p}}{m^{p}}

≲_{p} (\frac{p^{p}}{(log p)^{p}} + \frac{k^{p−1}}{m^{p}} ) \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p}

+ (\frac{p^{p}}{(log p)^{p}} + \frac{(pn)^{p}}{m^{p}} (\frac{n}{k})^{\frac{p}{2}} ) \frac{1}{2^{n}} (\frac{k}{n})^{\frac{p}{2}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}.  (96)

Since m ⩾ \frac{n^{3/2} log p}{\sqrt{k}}, the desired inequality (4) is a consequence of (96). □

5. Proof of Theorem 1.6

The desired inequality (23) is equivalent to the conjunction of the following two inequalities.

∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} |f(x + 2ε) − f(x)|^{p} ≲_{p} \frac{(pn/k)^{\frac{p}{2}}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} |f(x + ε_{S}) − f(x)|^{p}, (97)

and

∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} \frac{|f(x + 4me_{j}) − f(x)|^{p}}{m^{p}} ≲_{p} \frac{p^{\frac{p}{2}}}{2^{n}\binom{n−1}{k−1}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} |f(x + ε_{S}) − f(x)|^{p}. (98)

The proofs of (97) and (98) are of a different nature: (97) is related to metric type and (98) is related to metric cotype. We therefore treat (97) and (98) in separate subsections.

5.1. Metric type and proof of (97). For every n ∈ ℕ and j ∈ {1, …, n} let σ^{j} ∈ {−1, 1}^{n} be given by

σ^{j} =^{def} −e_{j} + ∑_{s∈{1,...,n}∖{j}} e_{s}.

Thus, for every ε ∈ {−1, 1}^{n}, coordinate-wise multiplication by σ^{j} yields

σ^{j}ε = (ε_{1}, …, ε_{j−1}, −ε_{j}, ε_{j+1}, …, ε_{n}).

Suppose that (X, ∥ · ∥_{X}) is a Banach space and that p ∈ [1, ∞]. Slightly abusing notation that was introduced in [39], let 𝔓_{p}^{n}(X) be the infimum over those 𝔓 ∈ (0, ∞) such that for every h : {−1, 1}^{n} → X we have

(\frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥h(ε) − h(−ε)∥_{X}^{p})^{\frac{1}{p}} ⩽ 𝔓(\frac{1}{4^{n}} ∑_{ε,δ∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} δ_{j} [h (σ^{j}ε) − h(ε)] ∥_{X}^{p})^{\frac{1}{p}} .  (99)

Note that in [39] the quantity 𝔓_{p}^{n}(X) denotes the best constant in an inequality that is stronger than but closely related to (99). However, this distinction is not important for us here and we prefer to use the notation 𝔓_{p}^{n}(X) rather than introducing ad hoc terminology.

The quantity 𝔓_{p}^{n}(X) is called the Pisier constant of (X, ∥·∥_{X}) (corresponding to dimension n and exponent p). In the context of his work on metric type, Pisier proved in [78] that 𝔓_{p}^{n}(X) ≲ log n for every Banach space (X, ∥ · ∥_{X}). In order to prove (97) we will deal with X = ℝ, in which case it will be important that sup_{n∈ℕ} 𝔓_{p}^{n}(ℝ) < ∞. This strengthening of Pisier’s inequality for real-valued functions is due to Talagrand [85], who proved that sup_{n∈ℕ} 𝔓_{p}^{n}(ℝ) ⩽ K^{p} for some universal constant K ∈ (1, ∞), an estimate that was later improved in [71] to sup_{n∈ℕ} 𝔓_{p}^{n}(ℝ) ≲ p. The rate of growth of sup_{n∈ℕ} 𝔓_{p}^{n}(ℝ) as p → ∞ remains unknown, the best available lower bound, due to Talagrand [85], being that sup_{n∈ℕ} 𝔓_{p}^{n}(ℝ) is at least a constant multiple of log p. We refer to [87, 71, 39] for additional classes of Banach space (X, ∥ · ∥_{X}) for which sup_{n∈ℕ} 𝔓_{p}^{n}(X) < ∞.

Given a metric space (X, ∥ · ∥_{X}), for every n ∈ ℕ and q ∈ [1, ∞) define BMW_{q}^{n}(X; p) to be the infimum over those B ∈ [1, ∞) such that for every h : {−1, 1}^{n} → X we have

∑_{ε∈\{−1,1\}^{n}} d_{X}(h(ε), h(−ε))^{p} ⩽ B^{p}n^{\frac{p}{q} −1} ∑_{j=1}^{n} ∑_{ε∈\{−1,1\}^{n}} d_{X} (h (σ^{j}ε) , h(ε))^{p} .  (100)

The quantity BMW_{q}^{n}(X; p) is called the Bourgain-Milman-Wolfson type q constant of (X, ∥ · ∥_{X}) (corresponding to dimension n and exponent p). It was introduced and studied by Bourgain, Milman and Wolfson in [19], though, as we explained in the Introduction, the case p = q was previously introduced by Enflo [31] and Gromov [38] (Gromov only dealt with the case p = q = 2). It follows from (99) and Hölder’s inequality that if (X, ∥ · ∥_{X}) is a Banach space then

BMW_{q}^{n}(X; p) ⩽ 𝔓_{p}^{n}(X) · T_{q}^{n}(X; p) ≲ (log n) · T_{q}^{n}(X; p),  (101)

where the (Rademacher type q) constant T_{q}^{n}(X; p) is defined to be the infimum over those T ∈ (0, ∞) such that for every x_{1}, …, x_{n} ∈ X we have

(\frac{1}{2^{n}} ∑_{δ∈\{−1,1\}^{n}} ∥∑_{i=1}^{n} δ_{i}x_{i}∥_{X}^{p} )^{\frac{1}{p}} ⩽ T (∑_{j=1}^{n} ∥x_{j}∥_{X}^{q} )^{\frac{1}{q}}

Since for many Banach spaces (X, ∥ · ∥_{X}) good estimates on T_{q}^{n}(X; p) are known, in conjunction with the available bounds on 𝔓_{p}^{n}(X), inequality (101) often yields a satisfactory estimate on BMW_{q}^{n}(X; p). Such an estimate will be relevant to the ensuing proof of a metric-space-valued extension of (97). There are also several important classes of (non-Banach) metric spaces (X, d_{X}) for which good bounds on BMW_{q}^{n}(X; p) have been obtained; see for example [71, 70, 73, 72, 67]. When X = ℝ, a bound that is even better than what follows from (101) is known: see inequality (6.32) in [67], which yields the estimate

sup_{n∈ℕ} BMW_{2}^{n}(ℝ; p) ≲ \sqrt{p}.  (102)

The following lemma, in conjunction with (102), implies (97). Note that there is no requirement that m is sufficiently large here: the lower bound on m that is assumed in Theorem 1.6 will be needed only for the proof of (98).

Lemma 5.1. Suppose that (X, d_{X}) is a metric space and p, q ∈ [1, ∞). Then for every n ∈ ℕ, k ∈ {1, …, n} and f : ℤ_{8m}^{n} → X we have

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε), f(x))^{p}

≲_{p} (BMW_{q}^{⌊n/k⌋+1}(X; p))^{p} \frac{(n/k)^{\frac{p}{q}}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + ε_{S}), f(x))^{p}. (103)

Proof. Write n = ak + b where a = ⌊n/k⌋ and b ∈ {0, …, k − 1}. For every j ∈ {1, …, a} define I_{j} = {(j − 1)k + 1, …, jk}, and also define I_{a+1} = {ak + 1, …, ak + b}. Fix x ∈ ℤ_{8m}^{n} and ε ∈ {−1, 1}^{n}. For every permutation π ∈ S_{n} define h_{x,ε}^{π} : {−1, 1}^{a+1} → X by

∀ δ ∈ {−1, 1}^{a+1}, h_{x,ε}^{π}(δ) =^{def} f (x + ∑_{j=1}^{a+1} δ_{j}ε_{π(I_{j})}) .

Note that for every π ∈ S_{n}, every x ∈ ℤ_{8m}^{n} and every δ ∈ {−1, 1}^{a+1} we have

∑_{ε∈{−1,1}^{n}} d_{X} (h_{x,ε}^{π}(δ), h_{x,ε}^{π}(−δ))^{p} = ∑_{ε∈{−1,1}^{n}} d_{X}(f(x + ε), f(x − ε))^{p}

= ∑_{ε∈{−1,1}^{n}} d_{X}(f(x + 2ε), f(x))^{p}.  (104)

Also, for every π ∈ S_{n} and j ∈ {1, …, n} we have

\frac{1}{2^{a+1}} ∑_{ε∈\{−1,1\}^{n}} ∑_{δ∈\{−1,1\}^{a+1}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (h_{x,ε}^{π} (σ^{j}δ) , h_{x,ε}^{π}(δ))^{p}

= ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f (x + ε_{π(I_{j})}) , f (x − ε_{π(I_{j})}))^{p}

= ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f (x + 2ε_{π(I_{j})}) , f (x))^{p} .  (105)

Fix B > BMW_{q}^{a+1}(X; p), apply (100) to h_{x,ε}^{π}, and sum the resulting inequality over ε ∈ {−1, 1}^{n} and x ∈ ℤ_{8m}^{n}, while using the identities (104) and (105). The resulting inequality is

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε), f(x))^{p}

⩽ B^{p}(a + 1)^{\frac{p}{q} −1} ∑_{j=1}^{a+1} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f (x + 2ε_{π(I_{j})}) , f (x))^{p} . (106)

By averaging (106) over π ∈ S_{n} we see that

B^{−p}(a + 1)^{1− \frac{p}{q}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε), f(x))^{p}

⩽ ∑_{j=1}^{a} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{|\{π ∈ S_{n} : π(I_{j}) = S\}|}{n!} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε_{S}), f(x))^{p}

+ ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=b \end{matrix}} \frac{|\{π ∈ S_{n} : π(I_{a+1}) = T \}|}{n!} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + 2ε_{T}), f(x))^{p}

= \frac{a}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + 2ε_{S}), f(x))^{p}

+ \frac{1}{\binom{n}{b}} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=b \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + 2ε_{T}), f(x))^{p} .  (107)

By Lemma 4.4, if T ⊆ S ⊆ {1, …, n} then

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + 2ε_{T}), f(x))^{p} ⩽ 2^{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + ε_{S}), f(x))^{p} .  (108)

Fixing T ⊆ {1, …, n} with |T | = b, by averaging (108) over all k-point subsets S ⊆ {1, …, n} with S ⊇ T we see that

∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + 2ε_{T}), f(x))^{p} ⩽ \frac{2^{p}}{\binom{n−b}{k−b}} ∑_{\begin{matrix}T ⊆S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + ε_{S}), f(x))^{p} .

Consequently,

\frac{1}{\binom{n}{b}} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=b \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε_{T}), f(x))^{p}

⩽ \frac{2^{p}}{\binom{n}{b}\binom{n−b}{k−b}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} |\{T ⊆ S : |T | = b\}| ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + ε_{S}), f(x))^{p}

= \frac{2^{p}\binom{k}{b}}{\binom{n}{b}\binom{n−b}{k−b}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X} (f(x + ε_{S}), f(x))^{p}

= \frac{2^{p}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + ε_{S}), f(x))^{p}.  (109)

Since by the triangle inequality we also have

∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε_{S}), f(x))^{p} ⩽ 2^{p} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + ε_{S}), f(x))^{p},

it follows from (107) and (109) that

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + 2ε), f(x))^{p}

⩽ \frac{(2B)^{p}(a + 1)^{\frac{p}{q}}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + ε_{S}), f(x))^{p}

⩽ \frac{(2B)^{p}(2n/k)^{\frac{p}{q}}}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} d_{X}(f(x + ε_{S}), f(x))^{p}.  □

5.2. Metric cotype and proof of (98). Given a metric space (X, d_{X}) and m, n ∈ ℕ, for p ∈ (1, ∞) define Γ_{p}(X; m, n) to be the infimum over those Γ ∈ (0, ∞) such that for every f : ℤ_{2m}^{n} → X,

∑_{j=1}^{n} ∑_{x∈ℤ_{2m}^{n}} \frac{d_{X} (f(x + me_{j}), f(x))^{p}}{m^{p}} ⩽ \frac{Γ^{p}}{3^{n}} ∑_{ε∈\{−1,0,1\}^{n}} ∑_{x∈ℤ_{2m}^{n}} d_{X}(f(x + ε), f(x))^{p}.  (110)

As discussed in the Introduction, following [61], we say that (X, d_{X}) has metric cotype p if

Γ_{p}(X) =^{def} sup_{n∈ℕ} inf_{m∈ℕ} Γ_{p}(X; m, n) < ∞.

We need to briefly recall some facts related to K-convexity of Banach spaces; see the survey [56] for much more on this topic. Given a Banach space (X, ∥ · ∥_{X}), p ∈ (1, ∞) and n ∈ ℕ, for every f : {−1, 1}^{n} → X define its Rademacher projection Rad(f) : {−1, 1}^{n} → X by

∀ ε ∈ \{−1, 1\}^{n}, Rad(f)(ε) =^{def} ∑_{j=1}^{n} \frac{∑_{δ∈\{−1,1\}^{n}} f(δ)δ_{j}}{2^{n}} ε_{j}.

For p ∈ (1, ∞) let K_{p}(X) ∈ [1, ∞] be the infimum over those K ∈ [1, ∞] such that for every n ∈ ℕ and every f : {−1, 1}^{n} → X we have

∑_{ε∈{−1,1}^{n}} ∥Rad(f)(ε)∥_{X}^{p} ⩽ K^{p} ∑_{ε∈{−1,1}^{n}} ∥f(ε)∥_{X}^{p}.

A simple application of Khinchine’s inequality (with asymptotically sharp constant, see [76, Lem. 2]) shows that K_{p}(ℝ) ≲ \sqrt{p} for p ∈ [2, ∞). A Banach space (X, ∥ · ∥_{X}) is said to be K-convex if K_{p}(X) < ∞ for some (equivalently for all) p ∈ (1, ∞); see [56] and the references therein.

Theorem 5.2 below establishes a sharp metric cotype inequality for K-convex Banach spaces, with one difference: the averaging on the right-hand side is over ε ∈ {−1, 1}^{n} rather than ε ∈ {−1, 0, 1}^{n}. The same result with averages over ε ∈ {−1, 0, 1}^{n} (and x ∈ ℤ_{4m}^{n} rather than x ∈ ℤ_{8m}^{n}) is the content of Theorem 4.1 in [61]. The proof here follows the argument in [61] with some technical modifications. It seems likely that a similar statement could be proved for the metric cotype p inequalities for Banach spaces of Rademacher cotype p (with no assumption of K-convexity) in [61, 34], though this may require changes to the arguments of [61, 34] that are more substantial than what we do here.

Theorem 5.2. Fix p ∈ [2, ∞) and α ∈ [1, ∞). Let (X, ∥ · ∥_{X}) be a K-convex Banach space of cotype p. Suppose that m, n ∈ ℕ satisfy

m ⩾ \frac{n^{1/p}}{αK_{p}(X)C_{p}(X)},  (111)

where, recalling (5), C_{p}(X) is the cotype p constant of X. Then for every f : ℤ_{8m}^{n} → X we have

∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} \frac{∥f(x + 4me_{j}) − f(x)∥_{X}^{p}}{m^{p}} ≲_{p} \frac{(αK_{p}(X)C_{p}(X))^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x+ε)−f(x)∥_{X}^{p}. (112)

Before proving Theorem 5.2 we deduce the following simple corollary, which implies (98) because C_{p}(ℝ) = 1 and K_{p}(ℝ) ≲ \sqrt{p}.

Corollary 5.3. Fix p ∈ [2, ∞) and α ∈ [1, ∞). Let (X, ∥ · ∥_{X}) be a K-convex Banach space of cotype p. Suppose that m, n ∈ ℕ and k ∈ {1, …, n} satisfy

m ⩾ \frac{k^{1/p}}{αK_{p}(X)C_{p}(X)}.

Then for every f : ℤ_{8m}^{n} → X we have

∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} \frac{∥f(x + 4me_{j}) − f(x)∥_{X}^{p}}{m^{p}}

≲_{p} \frac{(αK_{p}(X)C_{p}(X))^{p}}{2^{n}\binom{n−1}{k−1}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε_{S}) − f(x)∥_{X}^{p}. (113)

Proof. By Theorem 5.2, for every S ⊆ {1, …, n} with |S| = k we have

∑_{j∈S} ∑_{x∈ℤ_{8m}^{n}} \frac{∥f(x + 4me_{j}) − f(x)∥_{X}^{p}}{m^{p}} ≲_{p} \frac{(αK_{p}(X)C_{p}(X))^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε_{S}) − f(x)∥_{X}^{p}.

By averaging this inequality over all S ⊆ {1, …, n} with |S| = k we obtain (113). □

In order to prove Theorem 5.2 we first introduce a small amount of notation and prove an auxiliary lemma. For every j ∈ {1, …, n} define a linear operator T_{j} : L_{2}(ℤ_{8m}^{n}, X) → L_{2}(ℤ_{8m}^{n}, X) by setting for every f : ℤ_{8m}^{n} → X and x ∈ ℤ_{8m}^{n},

T_{j}f(x) =^{def} \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} f (x + 2ε_{\{1,...,n\}∖\{j\}}) .  (114)

Lemma 5.4. Let (X, ∥·∥_{X}) be a Banach space and p ∈ [1, ∞). Fix also m, n ∈ ℕ and j ∈ {1, …, n}. Then for every f : ℤ_{8m}^{n} → X we have

∑_{x∈ℤ_{8m}^{n}} ∥f(x) − T_{j}f(x)∥_{X}^{p} ⩽ \frac{2^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p}.  (115)

Moreover, for every x ∈ ℤ_{8m}^{n} we have

∑_{ε∈{−1,1}^{n}} ∥∑_{j=1}^{n} ε_{j} [T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})]∥_{X}^{p}

⩽ (2K_{p}(X))^{p} ∑_{ε∈{−1,1}^{n}} ∥f(x + 2ε) − f(x)∥_{X}^{p} ⩽ (4K_{p}(X))^{p} ∑_{ε∈{−1,1}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p} . (116)

Proof. By the definition (114) and convexity,

∑_{x∈ℤ_{8m}^{n}} ∥f(x) − T_{j}f(x)∥_{X}^{p} ⩽ \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x) − f (x + 2ε_{\{1,...,n\}∖\{j\}})∥_{X}^{p}

⩽ \frac{2^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p},

where in the last step we used Lemma 4.4. This proves (115).

To prove (116), for every fixed x ∈ ℤ_{8m}^{n} define h^{x} : {−1, 1}^{n} → X by

∀ ε ∈ {−1, 1}^{n}, h^{x}(ε) =^{def} f(x + 2ε) − f(x).

We claim that the following identity holds true.

Rad(h^{x})(ε) = \frac{i}{2} ∑_{j=1}^{n} ε_{j} [T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})] .  (117)

Once (117) is proved, the desired inequality (116) would follow from the definition of K_{p}(X).

By composing with linear functionals, it suffices to verify the validity of (117) when X = ℂ. Moreover, for every y ∈ ℤ_{8m}^{n} define W_{y} : ℤ_{8m}^{n} → ℂ by

∀ x ∈ ℤ_{8m}^{n}, W_{y}(x) =^{def} exp (\frac{πi}{4m} ∑_{j=1}^{n} x_{j}y_{j}) .

Then {W_{y}}_{y∈ℤ_{8m}^{n}} forms an orthonormal basis of L_{2}(ℤ_{8m}^{n}), and therefore it suffices to verify the validity of (117) when f = W_{y} for some y ∈ ℤ_{8m}^{n}. Now,

W_{y}^{x}(ε) = − (1 − ∏_{j=1}^{n} (cos (\frac{πε_{j}y_{j}}{2m} ) + i sin (\frac{πε_{j}y_{j}}{2m} ))) W_{y}(x)

= − (1 − ∏_{j=1}^{n} (cos (\frac{πy_{j}}{2m} ) + iε_{j} sin (\frac{πy_{j}}{2m} ))) W_{y}(x)

Consequently,

Rad(W_{y}^{x})(ε) = i (∑_{j=1}^{n} ε_{j} sin (\frac{πy_{j}}{2m} ) ∏_{s∈\{1,...,n\}∖\{j\}} cos (\frac{πy_{s}}{2m} )) W_{y}(x).  (118)

At the same time, for every j ∈ {1, …, n} we have

T_{j}W_{y}(x) = (\frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∏_{s∈\{1,...,n\}∖\{j\}} exp (\frac{πiε_{s}y_{s}}{2m} )) W_{y}(x)

= ( ∏_{s∈\{1,...,n\}∖\{j\}} cos (\frac{πy_{s}}{2m} )) W_{y}(x).

Therefore

∑_{j=1}^{n} ε_{j} [T_{j}W_{y}(x + 2e_{j}) − T_{j}W_{y}(x − 2e_{j})]

= (∑_{j=1}^{n} ε_{j} (W_{y}(2e_{j}) − W_{y}(−2e_{j})) ∏_{s∈\{1,...,n\}∖\{j\}} cos (\frac{πy_{s}}{2m} )) W_{y}(x)

= 2 (∑_{j=1}^{n} ε_{j} sin (\frac{πy_{j}}{2m} ) ∏_{s∈\{1,...,n\}∖\{j\}} cos (\frac{πy_{s}}{2m} )) W_{y}(x) = \frac{2}{i}Rad(W_{y}^{x})(ε),

where in the last step we used (118). □ Proof of Theorem 5.2. By the triangle inequality, for every j ∈ {1, …, n} we have

∥f(x + 4me_{j}) − f(x)∥_{X}^{p}

≲_{p} ∥T_{j}f(x + 4me_{j}) − T_{j}f(x)∥_{X}^{p} + ∥f(x + 4me_{j}) − T_{j}f(x + 4me_{j})∥_{X}^{p} + ∥f(x) − T_{j}f(x)∥_{X}^{p} . Hence, using (115) we see that

∑_{x∈ℤ_{8m}^{n}} ∥f(x + 4me_{j}) − f(x)∥_{X}^{p}

≲_{p} ∑_{x∈ℤ_{8m}^{n}} ∥T_{j}f(x + 4me_{j}) − T_{j}f(x)∥_{X}^{p} + \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p}. (119)

By the triangle inequality combined with Hölder’s inequality we have

∑_{x∈ℤ_{8m}^{n}} ∥T_{j}f(x + 4me_{j}) − T_{j}f(x)∥_{X}^{p} ⩽ m^{p−1} ∑_{s=1}^{m} ∑_{x∈ℤ_{8m}^{n}} ∥T_{j}f(x + 4se_{j}) − T_{j}f(x + 4(s − 1)e_{j})∥_{X}^{p}

= m^{p} ∑_{x∈ℤ_{8m}^{n}} ∥T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})∥_{X}^{p} .

In combination with (119), this implies that

∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} \frac{∥f(x + 4me_{j}) − f(x)∥_{X}^{p}}{m^{p}}

≲_{p} ∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} ∥T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})∥_{X}^{p} + \frac{n}{m^{p}2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p}. (120)

By the definition of the cotype p constant C_{p}(X), for every x ∈ ℤ_{8m}^{n} we have

∑_{j=1}^{n} ∥T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})∥_{X}^{p} ⩽ \frac{C_{p}(X)^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j} [T_{j}f(x + 2e_{j}) − T_{j}f(x − 2e_{j})]∥_{X}^{p}
≲_{p} \frac{(K_{p}(X)C_{p}(X))^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p},  (121)

where in the last step of (121) we used (116). By substituting (121) into (120) we conclude that

∑_{j=1}^{n} ∑_{x∈ℤ_{8m}^{n}} \frac{∥f(x + 4me_{j}) − f(x)∥_{X}^{p}}{m^{p}}

≲_{p} \frac{(K_{p}(X)C_{p}(X))^{p} + n/m^{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{8m}^{n}} ∥f(x + ε) − f(x)∥_{X}^{p}. (122)

Due to (111), (122) implies the desired inequality (112). □

6. A conjectural convolution inequality as a way to prove Conjecture 1.5

For every j ∈ {1, …, n} define an averaging operator E_{j} : L_{2}(ℤ_{m}^{n}) → L_{2}(ℤ_{m}^{n}) by setting for every f : ℤ_{m}^{n} → ℝ and x ∈ ℤ_{m}^{n},

E_{j}f(x) =^{def} \frac{f(x + e_{j}) + f(x − e_{j})}{2}.

We also set E_{j} =^{def} ∏_{s∈{1,...,n}∖{j}} E_{s} and E =^{def} ∏_{s=1}^{n} E_{j}. Thus, for every f : ℤ_{m}^{n} → ℝ and x ∈ ℤ_{m}^{n},

E_{j}f(x) = \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} f (x + ε_{\{1,...,n\}∖\{j\}})  and  Ef(x) = \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} f(x + ε). (123)

Question 6.1. Is it true that for every p ∈ (2, ∞) there exists β_{p} ∈ (0, 1] such that for every m, n ∈ ℕ, every f : ℤ_{m}^{n} → ℝ satisfies

\frac{β_{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{m}^{n}} |Ef(x + ε) − Ef(x − ε)|^{p}

⩽ \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{m}^{n}} |∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p} + ∑_{j=1}^{n} ∑_{x∈ℤ_{m}^{n}} |f(x + e_{j}) − f(x)|^{p} . (124)

It may very well be the case that (124) holds true without the second term that appears in the right-hand side, i.e., that

β_{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{m}^{n}} |Ef(x + ε) − Ef(x − ε)|^{p} ⩽ ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{m}^{n}} |∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p} .

We formulated Question 6.1 in the above weaker form since it suffices for the following proposition.

Proposition 6.2. A positive answer to Question 6.1 implies that Conjecture 1.5 holds true, and hence also that all the conclusions of Theorem 1.14 hold true. Specifically, for every δ ∈ (0, ∞), if m, n ∈ ℕ and k ∈ \{1, …, n\} satisfy m ⩾ δ\sqrt{n/k} then (21) holds true with

α_{p} ≳_{p} min \{β_{p} (\frac{log p}{p^{\frac{3}{2}}})^{p} , δ^{p}\} .

where β_{p} is as in (124).

Proof. Fix f : ℤ_{4m}^{n} → ℝ. By convexity, it follows from (123) that

∑_{x∈ℤ_{4m}^{n}} |f(x) − Ef(x)|^{p} ⩽ \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}.

Hence, for every S ⊆ {1, …, n} we have

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + 2mε_{S}) − f(x)|^{p}

≲_{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + 2mε_{S}) − Ef(x)|^{p} + ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}. (125)

Arguing as in (70), it follows from the triangle inequality that

∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + 2mε_{S}) − Ef(x)|^{p} ⩽ m^{p} ∑_{ε∈{−1,1}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + ε_{S}) − Ef(x − ε_{S})|^{p} . (126)

For every z ∈ ℤ_{4m}^{{1,...,n}∖S} apply (124) to the mapping (y ∈ ℤ_{4m}^{S}) ↦ ∏_{j∈{1,...,n}∖S} E_{j}f(y, z), and then average the resulting inequality over z. The estimate thus obtained is

\frac{β_{p}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + ε_{S}) − Ef(x − ε_{S})|^{p}

⩽ \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j∈S} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p} + ∑_{j∈S} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} . (127)

By averaging (127) over those S ⊆ {1, …, n} with |S| = k we see that

\frac{β_{p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + ε_{S}) − Ef(x − ε_{S})|^{p}

⩽ \frac{1}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j∈S} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p}

+ \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} .  (128)

Note that since E_{j} is an averaging operator,

∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})|^{p} ⩽ 2^{p} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} .

Hence, using the linear X_{p} inequality (16), we deduce that

\frac{(p/ log p)^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j∈S} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p}

+ \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p} .  (129)

The same reasoning that leads to the identity (117) (alternatively, by [61, Sec. 5]) shows that if for fixed x ∈ ℤ_{4m}^{n} we define g^{x} : {−1, 1}^{n} → ℝ by setting g^{x}(ε) = f(x + ε) − f(x) for every ε ∈ {−1, 1}^{n}, then that Rademacher projection of g^{x} satisfies

Rad(g^{x})(ε) = \frac{i}{2} ∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})] .

Hence, recalling that the K-convexity constant of ℝ satisfies K_{p}(ℝ) ≲ \sqrt{p},

∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |∑_{j=1}^{n} ε_{j} [E_{j}f(x + e_{j}) − E_{j}f(x − e_{j})]|^{p} ≲_{p} p^{\frac{p}{2}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}. (130)

By combining (128) with (129) and (130) we have

\frac{(p^{3/2}/ log p)^{−p}β_{p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |Ef(x + ε_{S}) − Ef(x − ε_{S})|^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p} + \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}.

Recalling (125) and (126), we therefore have

\frac{(p^{3/2}/ log p)^{−p}β_{p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} \frac{|f(x + 2mε_{S}) − f(x)|^{p}}{m^{p}}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∑_{x∈ℤ_{4m}^{n}} |f(x + e_{j}) − f(x)|^{p}

+ (1 + \frac{(p^{3/2}/ log p)^{−p}}{m^{p} (k/n)^{\frac{p}{2}}} β_{p}) \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∑_{x∈ℤ_{4m}^{n}} |f(x + ε) − f(x)|^{p}. □

7. The Schatten p trace class is an X_{p} Banach space

For p ∈ [1, ∞) and d ∈ ℕ, the Schatten p-norm of a d by d matrix A ∈ M_{d}(ℝ) is defined as

∥A∥_{S_{p}} = (Tr((A^{∗}A)^{\frac{p}{2}} ))^{\frac{1}{p}} = (Tr((AA^{∗})^{\frac{p}{2}} ))^{\frac{1}{p}} .

See [80] for relevant background. The following theorem asserts that S_{p} is an X_{p} Banach space.

Theorem 7.1. Fix p ∈ [2, ∞), d, n ∈ ℕ and k ∈ {1, …, n}. Then for every A_{1}, …, A_{n} ∈ M_{d}(ℝ),

\frac{(p/\sqrt{log p})^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j∈S} ε_{j}A_{j}∥_{S_{p}}^{p} ≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∥A_{j}∥_{S_{p}}^{p} + \frac{(k/n)^{\frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j}A_{j}∥_{S_{p}}^{p} .

Question 7.2. It remains an interesting open problem to determine whether or not the quantity p/\sqrt{log p} in Theorem 7.1 can be replaced by the (sharp) quantity p/ log p. This was proved in the scalar case in [41], but additional ideas seem to be required in order to carry out the proof of [41] in the above noncommutative setting.

The key step in the proof of Theorem 7.1 is the following proposition.

Proposition 7.3. Fix q ∈ [1, ∞), d, n ∈ ℕ and k ∈ {1, …, n}. Suppose that B_{1}, …, B_{n} ∈ M_{d}(ℝ) are symmetric and positive semidefinite. Then

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S} B_{j})^{q}) ≲_{q} (\frac{q}{log(2q)})^{q} max \{\frac{k}{n} ∑_{j=1}^{n} Tr(B_{j}^{q}) , (\frac{k}{n})^{q} Tr(( ∑_{j=1}^{n} B_{j})^{q})\} .

Before proving Proposition 7.3, we assume its validity for the moment and proceed to show how it implies Theorem 7.1.

Proof of Theorem 7.1. Lust-Piquard’s noncommutative Khinchine inequality [53] asserts that for every S ⊆ {1, …, n} we have

\frac{p^{− \frac{p}{2}}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j∈S} ε_{j}A_{j}∥_{S_{p}}^{p} ≲_{p} Tr(( ∑_{j∈S} A_{j}^{∗}A_{j})^{\frac{p}{2}} ) + Tr(( ∑_{j∈S} A_{j}A_{j}^{∗})^{\frac{p}{2}} ) .  (131)

The (asymptotically optimal) dependence on p in the left-hand side of (131) is not stated in Lust-Piquard’s original proof of (131), but it can be found in [79, page 106]. By averaging (131) over all those S ⊆ {1, …, n} with |S| = k we see that

\frac{p^{− \frac{p}{2}}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j∈S} ε_{j}A_{j}∥_{S_{p}}^{p}

≲_{p} \frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S}^{n} A_{j}^{∗}A_{j})^{\frac{p}{2}} ) + \frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S} A_{j}A_{j}^{∗})^{\frac{p}{2}} ) . (132)

Two applications of Proposition 7.3 with q = p/2 ⩾ 1, once with B_{j} = A_{j}^{∗}A_{j} and once with B_{j} = A_{j}A_{j}^{∗}, so as to control the two terms that appear in the right-hand side of (132), yield

\frac{(p/\sqrt{log p})^{−p}}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j∈S} ε_{j}A_{j}∥_{S_{p}}^{p}

≲_{p} \frac{k}{n} ∑_{j=1}^{n} ∥A_{j}∥_{S_{p}}^{p} + (\frac{k}{n})^{\frac{p}{2}} Tr(( ∑_{j=1}^{n} A_{j}^{∗}A_{j})^{\frac{p}{2}} ) + (\frac{k}{n})^{\frac{p}{2}} Tr(( ∑_{j=1}^{n} A_{j}A_{j}^{∗})^{\frac{p}{2}} ) . (133)

The other direction of Lust-Piquard’s noncommutative Khinchine inequality [53] asserts that

Tr(( ∑_{j=1}^{n} A_{j}^{∗}A_{j})^{\frac{p}{2}} ) + Tr(( ∑_{j=1}^{n} A_{j}A_{j}^{∗})^{\frac{p}{2}} ) ≲_{p} \frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥∑_{j=1}^{n} ε_{j}A_{j}∥_{S_{p}}^{p} .  (134)

Theorem 7.1 now follows by combining (133) and (134). □

Lemma 7.4 below makes the same assertion as Proposition 7.3, but only for k ⩽ n/2 (and an explicit universal constant that arises from our proof; we do not claim that it is optimal). This is actually the main step in the proof of Proposition 7.3, which we will show below to easily follow from Lemma 7.4.

Lemma 7.4. Fix q ∈ [1, ∞) and d, k, n ∈ ℕ with k ⩽ n/2. Then for every B_{1}, …, B_{n} ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S} B_{j})^{q}) ≲ (\frac{4q}{log(2q)})^{q} max \{\frac{k}{n} ∑_{j=1}^{n} Tr(B_{j}^{q}) , (\frac{k}{n})^{q} Tr(( ∑_{j=1}^{n} B_{j})^{q})\} .

Assuming the validity of Lemma 7.4 for the moment, we proceed to deduce Proposition 7.3, which amounts to removing the restriction k ⩽ n/2 in Lemma 7.4.

Proof of Proposition 7.3. Write k = u + v with u, v ∈ ℕ satisfying u, v ⩽ n/2. By the triangle inequality in S_{q}, for every S, T ⊆ {1, …, n} with T ⊆ S we have

Tr(( ∑_{j∈S} B_{j})^{q}) = ∥∑_{s∈T} B_{s} + ∑_{s∈S∖T} B_{s}∥_{S_{q}}^{q} ⩽ 2^{q−1} ∥∑_{s∈T} B_{s}∥_{S_{q}}^{q} + 2^{q−1} ∥ ∑_{s∈S∖T} B_{s}∥_{S_{q}}^{q} .

Consequently,

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S} B_{j})^{q}) ⩽ \frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} \frac{2^{q−1}}{\binom{k}{u}} ∑_{\begin{matrix}T ⊆S \\ |T |=u \end{matrix}} (∥∑_{s∈T} B_{s}∥_{S_{q}}^{q} + ∥ ∑_{s∈S∖T} B_{s}∥_{S_{q}}^{q} )

= \frac{2^{q−1}}{\binom{n}{u}} ∑_{\begin{matrix}U⊆\{1,...,n\} \\ |U|=u \end{matrix}} Tr(( ∑_{j∈U} B_{j})^{q}) + \frac{2^{q−1}}{\binom{n}{v}} ∑_{\begin{matrix}V ⊆\{1,...,n\} \\ |V |=v \end{matrix}} Tr(( ∑_{j∈V} B_{j})^{q}) . (135)

Proposition 7.3 now follows by applying Lemma 7.4 to each of the summands that appear in the right-hand side of (135). □

Our proof of Lemma 7.4 relies on certain matrix inequalities of independent interest. These inequalities are established in the following section.

7.1. Auxiliary trace inequalities. Proposition 7.5 and Proposition 7.8 below will be used crucially in the proof of Lemma 7.4. Note that the same statements are trivial when matrices are replaced by scalars. See Section 7.1.1 for a discussion on the context of these results, where it is explained in particular that Proposition 7.5 was known when q ∈ [1, 2] by either directly applying the work of Carlen and Lieb [24], or through a simple argument that relies on operator convexity. At the same time, it is explained in Section 7.1.1 that when q ∈ (0, 1) ∪ (2, ∞), a range of values of q that is used crucially in our proof of Lemma 7.4 below, Proposition 7.5 exhibits a phenomenon that is qualitatively different from the simpler case q ∈ [1, 2].

Proposition 7.5. Suppose that q ∈ [1, ∞) and d ∈ ℕ. Then for every A, B ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

(Tr ((A + B)^{q}A))^{\frac{1}{q}} ⩽ (Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} .  (136)

Before proving Proposition 7.5, we record for future use the following Hölder-type estimate.

Lemma 7.6. Fix d, k ∈ ℕ and q ∈ (0, ∞). Suppose that a_{0}, …, a_{k−1}, b_{1}, …, b_{k} ∈ (0, ∞) satisfy b_{j} + b_{j+1} ⩽ 2qa_{j} for every j ∈ {0, …, k − 1}, where we set b_{0} = b_{k}. Suppose also that

∑_{j=0}^{k−1} a_{j} + ∑_{j=1}^{k} b_{j} = q + 1.  (137)

Then for every A, B ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) ⩽ (Tr (A^{q+1}))^{1− \frac{1}{q} ∑_{j=1}^{k} b_{j}} (Tr (B^{q}A))^{\frac{1}{q} ∑_{j=1}^{k} b_{j}} .

Proof. By applying an arbitrarily small perturbation, we may assume that a_{j} −(b_{j} +b_{j+1})/(2q) > 0 for every j ∈ {0, …, k − 1}. We can then define p_{0}, r_{0}, …, p_{k−1}, r_{k−1} ∈ (0, ∞) by

∀ j ∈ \{0, …, k − 1\},  p_{j} =^{def} \frac{q + 1}{a_{j} − \frac{b_{j}+b_{j+1}}{2q}}  and  r_{j} =^{def} \frac{q}{b_{j+1}} .  (138)

Using the cyclicity of the trace, the choices in (138) imply that we have

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) = Tr (∏_{j=0}^{k−1} A^{\frac{q+1}{p_{j}}} (A^{\frac{1}{2r_{j}}} B^{\frac{q}{r_{j}}} A^{\frac{1}{2r_{j}}} )) ,  (139)

Moreover,

∑_{j=0}^{k−1} \frac{1}{p_{j}} + ∑_{j=0}^{k−1} \frac{1}{r_{j}} = \frac{1}{q + 1} ∑_{j=0}^{k−1} a_{j} + (\frac{1}{q} − \frac{1}{q(q + 1)}) ∑_{j=1}^{k} b_{j} =^{(137)} 1.

Therefore p_{j}, r_{j} ∈ (1, ∞) for all j ∈ {0, …, k − 1} and we may use Hölder’s inequality for traces (Théorème 6 in [28]) to deduce from (139) that

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) ⩽ ∏_{j=0}^{k−1} (Tr (A^{q+1}))^{\frac{1}{p_{j}}} (Tr ((A^{\frac{1}{2r_{j}}} B^{\frac{q}{r_{j}}} A^{\frac{1}{2r_{j}}} )^{r_{j}}))^{\frac{1}{r_{j}}} .  (140)

The Lieb–Thirring inequality [49] asserts that Tr((XY X)^{r}) ⩽ Tr(X^{r}Y^{r}X^{r}) for every r ∈ [1, ∞) and for every symmetric and positive semidefinite matrices X, Y ∈ M_{d}(ℝ). Recalling the definition of r_{0}, …, r_{k−1} in (138), for every j ∈ {0, …, k − 1} we therefore have

Tr ((A^{\frac{1}{2r_{j}}} B^{\frac{q}{r_{j}}} A^{\frac{1}{2r_{j}}} )^{r_{j}}) ⩽ Tr (\sqrt{A}B^{q}\sqrt{A}) = Tr (B^{q}A) .

A substitution of this estimate into (140) gives

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) ⩽ (Tr (A^{q+1}))^{∑{k−1 \atop j=0} \frac{1}{p_{j}}} (Tr (B^{q}A))^{∑{k−1 \atop j=0} \frac{1}{r_{j}}}

= (Tr (A^{q+1}))^{1− \frac{1}{q} ∑_{j=1}^{k} b_{j}} (Tr (B^{q}A))^{\frac{1}{q} ∑_{j=1}^{k} b_{j}} ,  (141)

where we used the fact that, due to (138), we have ∑_{j=0}^{k−1} \frac{1}{r_{j}} = \frac{1}{q} ∑_{j=1}^{k} b_{j}. □

Remark 7.7. For future use, note that if q, a_{0}, …, a_{k−1}, b_{1}, …, b_{k} ∈ (0, ∞) satisfy (137) and we also know that a_{0}, …, a_{k−1} ⩾ 1 then the assumptions of Lemma 7.6 hold true, i.e., b_{j} + b_{j+1} ⩽ 2qa_{j} for every j ∈ {0, …, k − 1}. Indeed, by (137) we have max{b_{j}, b_{j+1}} ⩽ q + 1 − a_{j} ⩽ qa_{j}, and consequently b_{j} + b_{j+1} ⩽ 2 max{b_{j}, b_{j+1}} ⩽ 2qa_{j}.

Proof of Proposition 7.5. Write q = 2m + θ, where m ∈ ℕ ∪ {0} and θ ∈ (0, 2]. The proof of (136) treats the cases θ ∈ (0, 1) and θ ∈ [1, 2] differently.

Case 1: θ ∈ [1, 2]. In this range the mapping t → t^{θ} is operator-convex (see Theorem 2.6 in [23]). This means that for every s ∈ (0, 1) we have

(A + B)^{θ} = (s\frac{A}{s} + (1 − s)\frac{B}{1 − s})^{θ} ⩽ \frac{A^{θ}}{s^{θ−1}} + \frac{B^{θ}}{(1 − s)^{θ−1}} ,  (142)

where, as usual, we interpret the inequality (142) in terms of the PSD order of matrices, i.e., that the right-hand side of (142) minus the left-hand side of (142) is a positive semidefinite matrix.

It follows from (142) that

\sqrt{A}(A + B)^{q}\sqrt{A} ⩽ \frac{\sqrt{A}(A + B)^{m}A^{θ}(A + B)^{m}\sqrt{A}}{s^{θ−1}} + \frac{\sqrt{A}(A + B)^{m}B^{θ}(A + B)^{m}\sqrt{A}}{(1 − s)^{θ−1}}.

So, by taking traces while making use of the cyclicity of the trace, we see that

Tr ((A + B)^{q}A) ⩽ \frac{Tr ((A + B)^{m}A^{θ}(A + B)^{m}A)}{s^{θ−1}} + \frac{Tr ((A + B)^{m}B^{θ}(A + B)^{m}A)}{(1 − s)^{θ−1}}.  (143)

By choosing s so as to minimize the quantity appearing in the right-hand side of (143), we have

(Tr ((A + B)^{q}A))^{\frac{1}{θ}}

⩽ (Tr ((A + B)^{m}A^{θ}(A + B)^{m}A))^{\frac{1}{θ}} + (Tr ((A + B)^{m}B^{θ}(A + B)^{m}A))^{\frac{1}{θ}} . (144)

We shall now proceed to estimate each of the terms that appear in the right-hand side of (144) separately. By expanding the mth powers appearing in the matrix (A + B)^{m}A^{θ}(A + B)^{m}A, and using the cyclicity of the trace, we see that Tr ((A + B)^{m}A^{θ}(A + B)^{m}A) equals the sum of 2^{2m} terms, each of which is of the form

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) ,  (145)

for some k ∈ ℕ∪{0} and a_{0}, …, a_{k−1}, b_{1}, …, b_{k} ∈ (0, ∞) that satisfy (137) (recall that q = 2m+θ). Here we use the convention that when k = 0 the quantity appearing in (145) equals Tr(A^{q+1}). Note that b_{j} is an integer for every j ∈ {1, …, k}, and for every r ∈ {0, …, 2m} the number of terms of the form (145) that appear in the above expansion of Tr ((A + B)^{m}A^{θ}(A + B)^{m}A) with ∑_{j=1}^{k} b_{j} = r equals \binom{2m}{r}; this is because ∑_{j=1}^{k} b_{j} is the total number of times that B was chosen when one expands the two occurrences of (A + B)^{m} in (A + B)^{m}A^{θ}(A + B)^{m}A as a product of matrices, each of which is either A or B. Note also that a_{0}, …, a_{k−1} ⩾ 1, since θ ⩾ 1. Recalling Remark 7.7, we may therefore use Lemma 7.6 to deduce that

Tr (A^{a_{0}} (∏_{j=1}^{k−1} B^{b_{j}}A^{a_{j}} ) B^{b_{k}} ) ⩽ (Tr (A^{q+1}))^{1− \frac{1}{q} ∑_{j=1}^{k} b_{j}} (Tr (B^{q}A))^{\frac{1}{q} ∑_{j=1}^{k} b_{j}} .  (146)

Hence,

Tr ((A + B)^{m}A^{θ}(A + B)^{m}A) ⩽ ∑_{r=0}^{2m} \binom{2m}{r} (Tr (A^{q+1}))^{1− \frac{r}{q}} (Tr (B^{q}A))^{\frac{r}{q}}

= (Tr (A^{q+1}))^{1− \frac{2m}{q}} ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{2m}
= (Tr (A^{q+1}))^{\frac{θ}{q}} ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{2m} ,  (147)

where in the final step we used the fact that 2m + θ = q.

The second term in the right-hand side of (144) is bounded using similar reasoning. As before, Tr ((A + B)^{m}B^{θ}(A + B)^{m}A) equals the sum of terms as in (145), for some k ∈ ℕ ∪ {0} and a_{0}, …, a_{k−1}, b_{1}, …, b_{k} ∈ (0, ∞) that satisfy (137). However, now we know that a_{1}, …, a_{k−1} ∈ ℕ and ∑_{j=0}^{k−1} b_{j} − θ ∈ {0, …, 2m}. By Lemma 7.6 (and Remark 7.7), the estimate (146) holds true for the terms of the form (145) that appear in the expansion of Tr ((A + B)^{m}B^{θ}(A + B)^{m}A). For every r ∈ {0, …, 2m}, the number of terms of the form (145) that appear in the expansion of Tr ((A + B)^{m}B^{θ}(A + B)^{m}A) with ∑_{j=1}^{k} b_{j} = r + θ equals \binom{2m}{r}, so by (146) we have

Tr ((A + B)^{m}B^{θ}(A + B)^{m}A)

⩽ ∑_{r=0}^{2m} \binom{2m}{r} (Tr (A^{q+1}))^{1− \frac{r+θ}{q}} (Tr (B^{q}A))^{\frac{r+θ}{q}}

= (Tr (A^{q+1}))^{1− \frac{2m+θ}{q}} (Tr (B^{q}A))^{\frac{θ}{q}} ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{2m}

= (Tr (B^{q}A))^{\frac{θ}{q}} ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{2m} ,  (148)

where the last step uses the fact that 2m + θ = q.

By substituting (147) and (148) into (144) we see that

(Tr ((A + B)^{q}A))^{\frac{1}{θ}} ⩽ ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{1+ \frac{2m}{θ}} = ((Tr (A^{q+1}))^{\frac{1}{q}} + (Tr (B^{q}A))^{\frac{1}{q}} )^{\frac{q}{θ}} ,

using 2m + θ = q once more. This completes the proof of the desired estimate (136) in Case 1.

Case 2: θ ∈ (0, 1). Note that since the underlying assumption of Proposition 7.5 is that q ⩾ 1, the facts that q = 2m + θ and θ ∈ (0, 1) imply that the integer m is positive. Moreover, in the range θ ∈ (0, 1) the mapping t → t^{θ} is no longer operator-convex but we have the following commonly used (see e.g. [32]) integral representation at our disposal. Since for every a ∈ (0, ∞) we have

a^{θ} = \frac{sin(πθ)}{π} ∫_{0}^{∞} t^{θ} (\frac{1}{t} − \frac{1}{t + a}) dt,

it follows that for every s ∈ (0, ∞),

(sA + B)^{θ} = \frac{sin(πθ)}{π} ∫_{0}^{∞} t^{θ} (\frac{1}{t}I − (tI + sA + B)^{−1}) dt.  (149)

Since \frac{d}{dt}X(t)^{−1} = −X(t)^{−1}X′(t)X(t)^{−1} for every differentiable X : (0, ∞) → M_{d}(ℝ) such that X(t) is an invertible matrix for every t ∈ (0, ∞) (simply differentiate the identity X(t)^{−1}X(t) = I), it follows from (149) that

\frac{d}{ds}(sA + B)^{θ} = \frac{sin(πθ)}{π} ∫_{0}^{∞} t^{θ} (tI + sA + B)^{−1} A (tI + sA + B)^{−1} dt.  (150)

By integrating over s ∈ [0, 1], in order to prove (136) it will suffice to show that

∀ s ∈ (0, 1), \frac{d}{ds} (Tr ((sA + B)^{q}A))^{\frac{1}{q}} ⩽ (Tr (A^{q+1}))^{\frac{1}{q}} .

Equivalently, we want to prove that

∀ s ∈ (0, 1),  \frac{d}{ds} Tr ((sA + B)^{q}A) ⩽ q (Tr (A^{q+1}))^{\frac{1}{q}} (Tr ((sA + B)^{q}A))^{1− \frac{1}{q}} .  (151)

Define for every s ∈ (0, 1),

f(s) =^{def} Tr ((\frac{d}{ds}(sA + B)^{m}) (sA + B)^{m+θ}A) ,

g(s) =^{def} Tr ((sA + B)^{m} (\frac{d}{ds}(sA + B)^{θ}) (sA + B)^{m}A) ,

and

h(s) =^{def} Tr ((sA + B)^{m+θ} (\frac{d}{ds}(sA + B)^{m}) A) .

Then, since (sA + B)^{q} = (sA + B)^{m}(sA + B)^{θ}(sA + B)^{m}, we have

\frac{d}{ds} Tr ((sA + B)^{q}A) = f(s) + g(s) + h(s).

Hence, because q = 2m + θ, in order to establish the validity of (151) it suffice to show that for every s ∈ [0, 1] we have

max\{f(s), h(s)\} ⩽ m (Tr (A^{q+1}))^{\frac{1}{q}} (Tr ((sA + B)^{q}A))^{1− \frac{1}{q}} ,  (152)

and

g(s) ⩽ θ (Tr (A^{q+1}))^{\frac{1}{q}} (Tr ((sA + B)^{q}A))^{1− \frac{1}{q}} .  (153)

Observe that

f(s) = ∑_{r=1}^{m} Tr ((sA + B)^{r−1}A(sA + B)^{m−r}(sA + B)^{m+θ}A)

= ∑_{r=1}^{m} Tr ((sA + B)^{r−1}A(sA + B)^{q−r}A) .  (154)

Similarly, using the cyclicity of the trace, we have

h(s) = ∑_{r=1}^{m} Tr ((sA + B)^{q−r}A(sA + B)^{r−1}A) = f(s).  (155)

Finally, by the integral representation (150) we have

g(s) = \frac{sin(πθ)}{π} ∫_{0}^{∞} t^{θ} Tr ((sA + B)^{m} (tI + sA + B)^{−1} A (tI + sA + B)^{−1} (sA + B)^{m}A) dt. (156)

By denoting C = sA + B, it follows from (154), (155) and (156) that the desired estimates (152) and (153) will be proven once we show that for every C ∈ M_{d}(ℝ) that is symmetric and positive semidefinite we have

∀ r ∈ \{1, …, m\},  Tr (C^{r−1}AC^{q−r}A) ⩽ (Tr (A^{q+1}))^{\frac{1}{q}} (Tr (C^{q}A))^{1− \frac{1}{q}} ,  (157)

and

∫_{0}^{∞} t^{θ} Tr (C^{m} (tI + C)^{−1} A (tI + C)^{−1} C^{m}A) dt ⩽ \frac{πθ}{sin(πθ)} (Tr (A^{q+1}))^{\frac{1}{q}} (Tr (C^{q}A))^{1− \frac{1}{q}} . (158)

(157) is a consequence of Lemma 7.6 (with B replaced by C). It therefore remains to establish the validity of (158). To this end, note that for every t ∈ (0, ∞), since (tI +C)^{−1} and C^{m} commute, by the cyclicity of the trace we have

Tr (C^{m} (tI + C)^{−1} A (tI + C)^{−1} C^{m}A) = Tr ((\sqrt{A}C^{m} (tI + C)^{−1} \sqrt{A})^{2})

⩽ Tr (AC^{2m} (tI + C)^{−2} A) = Tr (C^{2m} (tI + C)^{−2} A^{2}) , (159)

where for the inequality in (159) we used the Lieb–Thirring inequality. This upper bound on the integrand in the left-hand side of (158) yields the following estimate.

∫_{0}^{∞} t^{θ} Tr (C^{m} (tI + C)^{−1} A (tI + C)^{−1} C^{m}A) dt ⩽ Tr (C^{2m} (∫_{0}^{∞} t^{θ}(tI + C)^{−2}dt) A^{2}) . (160)

Note that for every c ∈ (0, ∞) we have

∫_{0}^{∞} \frac{t^{θ}}{(t + c)^{2}} dt = c^{θ−1} ∫_{0}^{∞} \frac{s^{θ}}{(s + 1)^{2}} ds = \frac{πθ}{sin(πθ)}c^{θ−1}.

Consequently,

Tr (C^{2m} (∫_{0}^{∞} t^{θ}(tI + C)^{−2}dt) A^{2}) = \frac{πθ}{sin(πθ)} Tr (C^{2m+θ−1}A^{2}) = \frac{πθ}{sin(πθ)} Tr (C^{q−1}A^{2})

= \frac{πθ}{sin(πθ)} Tr (AC^{q−1}A) ⩽^{(157)} \frac{πθ}{sin(πθ)} (Tr (A^{q+1}))^{\frac{1}{q}} (Tr (C^{q}A))^{1− \frac{1}{q}} . (161)

A substitution of (161) into (160) yields the desired inequality (158). □

The following Proposition is a variant of Proposition 7.5 when q ∈ (0, 1).

Proposition 7.8. Suppose that q ∈ (0, 1) and d ∈ ℕ. Then for every A, B ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

Tr ((A + B)^{q}A) ⩽ Tr (A^{q+1}) + Tr (B^{q}A) .

Proof. By the integral identity (150), with θ replaced by q (which is allowed since 0 < q < 1), for every s ∈ (0, ∞) we have

\frac{d}{ds} Tr ((sA + B)^{q}A) = \frac{sin(πq)}{π} ∫_{0}^{∞} t^{q} Tr ((tI + sA + B)^{−1} A (tI + sA + B)^{−1} A) dt. (162)

Fix s, t ∈ (0, ∞) and define F : [0, ∞) → ℝ by

∀ w ∈ [0, ∞), F (w) =^{def} Tr ((tI + sA + wB)^{−1} A (tI + sA + wB)^{−1} A) .

This mapping was investigated in Section III of [11], where it was shown to be convex. Here we need to know that it is non-increasing, which follows from the following computation.

F′(w) = − Tr ((tI + sA + wB)^{−1} B (tI + sA + wB)^{−1} A (tI + sA + wB)^{−1} A)
− Tr ((tI + sA + wB)^{−1} A (tI + sA + wB)^{−1} B (tI + sA + wB)^{−1} A)
= − Tr(CD) − Tr(DC) = −2 Tr(CD) ⩽ 0,

where C, D ∈ M_{d}(ℝ) are the symmetric and positive semidefinite matrices given by

C =^{def} (tI + sA + wB)^{−1} B (tI + sA + wB)^{−1}  and  D =^{def} A (tI + sA + wB)^{−1} A.

It follows from these considerations that

Tr ((tI + sA + B)^{−1} A (tI + sA + B)^{−1} A) = F (1) ⩽ F (0) = Tr ((tI + sA)^{−1} A (tI + sA)^{−1} A) .

A substitution of this estimate into (162) shows that

\frac{d}{ds} Tr ((sA + B)^{q}A) ⩽ \frac{sin(πq)}{π} ∫_{0}^{∞} t^{q} Tr ((tI + sA)^{−1} A (tI + sA)^{−1} A) dt

=^{(149)} \frac{d}{ds} Tr ((sA)^{q}A) = qs^{q−1} Tr (A^{q+1}) . (163)

By integrating (163) over [0, 1] we therefore see that Tr ((A + B)^{q}A) − Tr (B^{q}A) ⩽ Tr (A^{q+1}) . □

We record for future use the following simple reformulation of Proposition 7.5 and Proposition 7.8. When q ∈ [1, 2] it follows from Proposition 7.8 (with q replaced by q − 1), and when q > 2 it follows from Proposition 7.5 (with q replaced by q − 1) and the convexity of t ↦ t^{q−1} on [0, ∞).

Corollary 7.9. Suppose that q ∈ [1, ∞) and d ∈ ℕ. Set r =^{def} max{q−2, 0}. For every A, B ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

Tr ((A + B)^{q−1}A) ⩽ min \{\frac{Tr (A^{q})}{λ^{r}} + \frac{Tr (B^{q−1}A)}{(1 − λ)^{r}} : λ ∈ (0, 1)\} .

7.1.1. Discussion and counterexamples. An inspection of our proof of Lemma 7.4 below shows that, for p ∈ (2, ∞), what we really need in order to show that S_{p} is an X_{p} Banach space is that there exists K = K_{p} ∈ (0, ∞) such that if A, B ∈ M_{d}(ℝ) are symmetric and positive semidefinite then

Tr((A + B)^{\frac{p}{2} −1}A) ⩽ K (Tr(A^{\frac{p}{2} −1}A) + Tr(B^{\frac{p}{2} −1}A)) .  (164)

Specifically, (164) implies Theorem 7.1 with the term p/\sqrt{log p} replaced by a constant that depends only on K and p. By Corollary 7.9, (164) holds true with K = 2^{max{0,(p−4)/2}}.

Setting q = (p − 2)/2 > 0, it is natural to ask whether multiplication by A is crucial for (164) to hold true. Specifically, one would naturally investigate whether for every A, B, C ∈ M_{d}(ℝ) that are symmetric and positive semidefinite we have

Tr((A + B)^{q}C) ⩽ K (Tr(A^{q}C) + Tr(B^{q}C)) ,  (165)

with K ∈ (0, ∞) independent of A, B, C. By a simple duality argument (e.g. Lemma 5.12 in [23]), the above requirement is equivalent to the matrix inequality

(A + B)^{q} ⩽ K (A^{q} + B^{q}) ,  (166)

where, as usual, we interpret the inequality (166) in terms of the PSD order of matrices.

Since for q ∈ [1, 2] the function t ↦ t^{q} is operator-convex (see e.g. [16]), for such q the PSD inequality (166) holds true with K = 2^{q−1} (recall (142)). This yields a simple proof of (164) when 4 ⩽ p ⩽ 6. Moreover, when q ∈ [1, 2] the operator convexity of the function t ↦ t^{q} shows that if A, B, C ∈ M_{d}(ℝ) are symmetric and positive semidefinite then for every λ ∈ (0, 1) we have

Tr((A + B)^{q}C) ⩽ \frac{Tr(A^{q}C)}{λ^{q−1}} + \frac{Tr(B^{q}C)}{(1 − λ)^{q−1}} .  (167)

By choosing λ so as to minimize the right hand side of (167) we see that

(Tr ((A + B)^{q}C))^{\frac{1}{q}} ⩽ (Tr (A^{q}C))^{\frac{1}{q}} + (Tr (B^{q}C))^{\frac{1}{q}} .  (168)

The inequality (168) is a strengthening of Proposition 7.5 in the special case q ∈ [1, 2], showing that when q belongs to this range Proposition 7.5 is a simple consequence of the operator convexity of the function t ↦ t^{q} (alternatively, one can deduce Proposition 7.5 directly from the work of Carlen and Lieb [24]; see specifically Theorem 1.1 and Remark 1.2 in [24]). However, the above argument is special to the range q ∈ [1, 2] since, as we shall explain below, if q ∈ (0, 1) ∪ (2, ∞) then (166) fails to hold true with any constant K that is independent of A, B.

The failure of such PSD subadditivity inequalities prompted much work in search for substitutes (note, however, that the literature did not focus on inequalities that allow for an arbitrary constant K in (166), but was rather devoted to, e.g., finding substitutes for (166) with q ∈ (0, 1) and K = 1). One such substitute allows for conjugation by unitary matrices, as initiated in [1]. A satisfactory recent result [6] along these lines asserts that if f : [0, ∞) → ℝ is nondecreasing, concave, and f(0) ⩾ 0, then for every A, B ∈ M_{d}(ℝ) there exist unitary matrices U, V ∈ M_{d}(ℂ) such that f(A + B) ⩽ Uf(A)U^{∗} + V f(B)V^{∗}. Another substitute for PSD subadditivity is a subadditivity inequality for unitarily invariant norms. Recall that a norm ∥ · ∥ on M_{d}(ℂ) is unitarily invariant if ∥UXV ∥ = ∥X∥ for every X, U, V ∈ M_{d}(ℂ) such that U, V are unitary. The papers [3, 20] contain satisfactory results along these lines, obtaining inequalities of the form ∥f(A+B)∥ ⩽ ∥f(A)+f(B)∥.

For q ∈ (0, 1), when f(t) = t^{q} and ∥ · ∥ is the Schatten 1 norm, the resulting inequality goes back to [57] and it corresponds to (165) with C = I (and K = 1).

Here we study a different type of substitute for (166). For example, when A ∈ M_{d}(ℝ) is symmetric and positive semidefinite define F_{A} : M_{d}(ℝ) → ℝ by F_{A}(X) = (Tr(|X|^{q}A))^{1/q} (F_{A} need not be unitarily invariant). Proposition 7.5 asserts that if q > 1 then F_{A}(X + Y) ⩽ F_{A}(X) + F_{A}(Y) for symmetric and positive semidefinite X, Y ∈ M_{d}(ℝ), provided that either X or Y equals A. Weakenings of (165) (the special case C = A) suffice for our application (i.e., proving the X_{p} inequality for S_{p}, and consequently obtaining various nonembeddability results), but we believe that they are interesting in their own right and deserve further investigation. Possible extensions include understanding inequalities of the form Tr(f(A + B)A) ⩽ K Tr(f(A)A) + K Tr(f(B)A).

We shall end this discussion by presenting the aforementioned example that exhibits the failure of (166) for every q ∈ (0, 1) ∪ (2, ∞) and K ∈ (0, ∞). Fix s ∈ (0, ∞) which we will eventually take to be sufficiently small. Define A_{s}, B_{s} ∈ M_{2}(ℝ) and w_{s} ∈ ℝ^{2} by

A_{s} =^{def} ( \begin{matrix}s^{2} & 0 \\ 0 & 0 \end{matrix} ) ,  B_{s} =^{def} ( \begin{matrix}1 & s \\ s & s^{2} \end{matrix} )  and  w_{s} =^{def} ( \begin{matrix}−s \\ 1 \end{matrix} ) .

A_{s} and B_{s} are symmetric and positive semidefinite, yet by direct computation for every K ∈ (0, ∞),

⟨(K(A_{s}^{4} + B_{s}^{4}) − (A_{s} + B_{s})^{4}) w_{s}, w_{s}⟩ = −s^{6} − 3s^{8} + (K − 1)s^{10}.

The above quantity is negative for s < 1/\sqrt[4]{K}, in which case the matrix K(A_{s}^{4} + B_{s}^{4}) − (A_{s} + B_{s})^{4} is not positive semidefinite. This shows that (166) fails to hold true for q = 4 with any constant K ∈ (0, ∞) that is independent of A and B (this corresponds to the failure of (164) when p = 10). A similar, though more tedious, computation shows that (166) also fails for every q ∈ (0, 1)∪(2, ∞). Indeed, direct computation (via diagonalization) yields that A_{s}^{q} = s^{2q}A_{s}, B_{s}^{q} = (1 + s^{2})^{q−1}B_{s} and

(A_{s} + B_{s})^{q} = ( \begin{matrix}\frac{a(s)^{q}(\sqrt{1+4s^{2}}+1)+b(s)^{q}(\sqrt{1+4s^{2}}−1)}{2\sqrt{1+4s^{2}}} & \frac{s(a(s)^{q}−b(s)^{q})}{\sqrt{1+4s^{2}}} \\ \frac{s(a(s)^{q}−b(s)^{q})}{\sqrt{1+4s^{2}}} & \frac{a(s)^{q}(\sqrt{1+4s^{2}}−1)+b(s)^{q}(\sqrt{1+4s^{2}}+1)}{2\sqrt{1+4s^{2}}} \end{matrix} ) ,

where

a(s) =^{def} s^{2} + \frac{1}{2} + \frac{\sqrt{1 + 4s^{2}}}{2}  and  b(s) =^{def} s^{2} + \frac{1}{2} − \frac{\sqrt{1 + 4s^{2}}}{2} .

One then directly computes that as s → 0,

⟨(K(A_{s}^{q} + B_{s}^{q}) − (A_{s} + B_{s})^{q}) w_{s}, w_{s}⟩ = (Ks^{2(q+1)} − s^{6} − s^{4q}) (1 + O_{q,K}(s^{2})) .  (169)

When q ∈ (0, 1) we have 4q < min{2(q + 1), 6} and when q ∈ (2, ∞) we have 6 < min{2(q + 1), 4q}. Consequently, for q ∈ (0, 1) ∪ (2, ∞) the quantity appearing in (169) is negative for small enough s, which means that the matrix K(A_{s}^{q} + B_{s}^{q}) − (A_{s} + B_{s})^{q} is not positive semidefinite.

7.2. Proof of Lemma 7.4. For the sake of simplicity denote

U =^{def} \frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} Tr(( ∑_{j∈S} B_{j})^{q}) , V =^{def} \frac{k}{n} ∑_{j=1}^{n} Tr(B_{j}^{q}) , W =^{def} Tr((\frac{k}{n} ∑_{j=1}^{n} B_{j})^{q}) . (170)

Our goal is therefore to show that

U ⩽ (\frac{4q}{log(2q)})^{q} max\{V, W \}.  (171)

Fix λ ∈ (0, 1) to be specified later. For every S ⊆ {1, …, n} and j ∈ S, by Corollary 7.9, with A = B_{j} and B = ∑_{s∈S∖{j}} B_{s}, we have

Tr(( ∑_{s∈S} B_{s})^{q−1}B_{j}) ⩽ \frac{1}{λ^{r}} Tr (B_{j}^{q}) + \frac{1}{(1 − λ)^{r}} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j}) ,

where, as denoted in Corollary 7.9, r = max{q − 2, 0}. Hence,

Tr(( ∑_{j∈S} B_{j})^{q}) = ∑_{j∈S} Tr(( ∑_{s∈S} B_{s})^{q−1}B_{j})

⩽ \frac{1}{λ^{r}} ∑_{j∈S} Tr (B_{j}^{q}) + \frac{1}{(1 − λ)^{r}} ∑_{j∈S} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j}) .  (172)

By averaging (172) over all of those S ⊆ {1, …, n} with |S| = k, and recalling (170), we see that

U ⩽ \frac{V}{λ^{r}} + \frac{1}{(1 − λ)^{r}\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{j∈S} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j}) .  (173)

Now,

∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{j∈S} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j}) = ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=k−1 \end{matrix}} ∑_{j∈\{1,...,n\}∖T} Tr(( ∑_{t∈T} B_{t})^{q−1}B_{j})

= ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=k−1 \end{matrix}} Tr(( ∑_{t∈T} B_{t})^{q−1}( ∑_{j∈\{1,...,n\}∖T} B_{j})) ⩽ ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=k−1 \end{matrix}} Tr(( ∑_{t∈T} B_{t})^{q−1}( ∑_{j=1}^{n} B_{j})) , (174)

where in the last step of (174) we used the fact that if A, B, C ∈ M_{d}(ℝ) are symmetric and positive semidefinite then Tr(AB) ⩽ Tr(A(B +C)). To bound the final term in (174), use Hölder’s inequality for traces to deduce that for every T ⊆ {1, …, n} we have

Tr(( ∑_{t∈T} B_{t})^{q−1}( ∑_{j=1}^{n} B_{j})) ⩽ (Tr(( ∑_{j=1}^{n} B_{j})^{q}))^{\frac{1}{q}} (Tr(( ∑_{t∈T} B_{t})^{q}))^{1− \frac{1}{q}}

= \frac{nW^{\frac{1}{q}}}{k} (Tr(( ∑_{t∈T} B_{t})^{q}))^{1− \frac{1}{q}} ,  (175)

where we recall the definition of W in (170).

The function t ↦ t^{q} is operator trace-increasing (see Theorem 2.10 in [23]), i.e., if C, D ∈ M_{d}(ℝ) are symmetric and positive semidefinite with C ⩽ D then Tr(C^{q}) ⩽ Tr(D^{q}). Consequently, for every T ⊊ {1, …, n} and u ∈ {1, …, n} we have Tr ((∑_{t∈T} B_{t})^{q}) ⩽ Tr ((B_{u} + ∑_{t∈T} B_{t})^{q}). By raising this inequality to the power (q − 1)/q and averaging over all u ∈ {1, …, n} ∖ T we see that

(Tr(( ∑_{t∈T} B_{t})^{q}))^{1− \frac{1}{q}} ⩽ \frac{1}{n − |T |} ∑_{u∈\{1,...,n\}∖T} (Tr(( ∑_{t∈T ∪\{u\}} B_{t})^{q}))^{1− \frac{1}{q}} .  (176)

Hence, by combining (175) and (176) with (174), we see that

∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{j∈S} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j})

⩽ \frac{nW^{\frac{1}{q}}}{k(n − k + 1)} ∑_{\begin{matrix}T ⊆\{1,...,n\} \\ |T |=k−1 \end{matrix}} ∑_{u∈\{1,...,n\}∖T} (Tr(( ∑_{t∈T ∪\{u\}} B_{t})^{q}))^{1− \frac{1}{q}}  (177)

= \frac{nW^{\frac{1}{q}}}{n − k + 1} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} (Tr(( ∑_{s∈S} B_{s})^{q}))^{1− \frac{1}{q}} ,  (178)

where for (178) note that for every S ⊆ {1, …, n} with |S| = k the term corresponding to ∑_{s∈S} B_{s} occurs in the sum that appears in (177) with multiplicity k, once for each u ∈ S.

Recalling the definition of U in (170), by Jensen’s inequality we see that

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} (Tr(( ∑_{s∈S} B_{s})^{q}))^{1− \frac{1}{q}} ⩽ U^{1− \frac{1}{q}} .  (179)

By substituting (179) into (178) and using k ⩽ n/2, we have

\frac{1}{\binom{n}{k}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=k \end{matrix}} ∑_{j∈S} Tr(( ∑_{s∈S∖\{j\}} B_{s})^{q−1}B_{j}) ⩽ 2W^{\frac{1}{q}} U^{\frac{q−1}{q}} .  (180)

In conjunction with (180), it follows from (173) that

U ⩽ min \{\frac{V}{λ^{r}} + \frac{2W^{\frac{1}{q}} U^{\frac{q−1}{q}}}{(1 − λ)^{r}} : λ ∈ (0, 1)\} ⩽ (V ^{\frac{1}{r+1}} + 2^{\frac{1}{r+1}} W^{\frac{1}{q(r+1)}} U^{\frac{q−1}{q(r+1)}} )^{r+1} ,  (181)

where the final inequality in (181) is seen by choosing 1/λ = 1 + (2W^{\frac{1}{q}} U^{\frac{q−1}{q}} /V )^{\frac{1}{r+1}} . By (181),

U^{\frac{1}{r+1}} ⩽ V ^{\frac{1}{r+1}} + 2^{\frac{1}{r+1}} W^{\frac{1}{q(r+1)}} U^{\frac{q−1}{q(r+1)}} .  (182)

The desired inequality (171) is a formal consequence of (182), as follows. If U ⩽ (4q/ log(2q))^{r+1}V then (171) holds true because r + 1 ⩽ q. We may therefore assume that U > (4q/ log(2q))^{r+1}V, in which case (182) implies that

\frac{U^{\frac{1}{r+1}}}{(2q)^{\frac{1}{2q}}} ⩽ (1 − \frac{log(2q)}{4q}) U^{\frac{1}{r+1}} ⩽ 2^{\frac{1}{r+1}} W^{\frac{1}{q(r+1)}} U^{\frac{q−1}{q(r+1)}} ,  (183)

where we used the fact that (1 − t) ⩾ e^{−2t} for every t ∈ [0, 1/2]. The estimate (183) simplifies to

U ⩽ 2^{q}(2q)^{\frac{r+1}{2}} W ⩽ 2^{q}(2q)^{\frac{q}{2}} W ⩽ (\frac{4q}{log(2q)})^{q} W,

where we used the elementary inequality log t ⩽ \sqrt{t}, which holds true for every t ∈ (0, ∞). □

Acknowledgements. We are grateful to Eric Carlen and Oded Regev for helpful pointers to the literature related to Section 7.1, as well as showing us counter-examples to (166) when q = 4. We also thank the anonymous referee for carefully reading our manuscript and many helpful comments. A. N. was supported in part by the NSF, the BSF, the Packard Foundation and the Simons Foundation. G. S. was supported in part by the ISF and the BSF.

References

[1] C. A. Akemann, J. Anderson, and G. K. Pedersen. Triangle inequalities in operator algebras. Linear and Multilinear Algebra, 11(2):167–178, 1982.

[2] F. Albiac and F. Baudier. Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces L_{p} and ℓ_{p} for 0 < p < ∞. J. Geom. Anal., 25(1):1–24, 2015.

[3] T. Ando and X. Zhan. Norm inequalities related to operator monotone functions. Math. Ann., 315(4):771–780, 1999.

[4] A. Andoni, A. Naor, and O. Neiman. Snowflake universality of Wasserstein spaces. Preprint, available at

http://arxiv.org/abs/1509.08677, 2015.

[5] N. Aronszajn. Differentiability of Lipschitzian mappings between Banach spaces. Studia Math., 57(2):147–190, 1976.

[6] J. S. Aujla and J.-C. Bourin. Eigenvalue inequalities for convex and log-convex functions. Linear Algebra Appl., 424(1):25–35, 2007.

[7] T. Austin and A. Naor. On the bi-Lipschitz structure of Wasserstein spaces. Preprint, 2015.

[8] T. Austin, A. Naor, and Y. Peres. The wreath product of ℤ with ℤ has Hilbert compression exponent \frac{2}{3} . Proc. Amer. Math. Soc., 137(1):85–90, 2009.

[9] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[10] K. Ball. The Ribe programme. Astérisque, (352):Exp. No. 1047, viii, 147–159, 2013. Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058.

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

[12] S. Banach. Théorie des opérations linéaires. Éditions Jacques Gabay, Sceaux, 1993. Reprint of the 1932 original.

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

[14] F. Baudier. Quantitative nonlinear embeddings into Lebesgue sequence spaces. To appear in J. Topol. Anal.,

preprint available at http://arxiv.org/abs/1210.0588, 2012.

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

[16] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1997.

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

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

[19] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

[20] J.-C. Bourin and M. Uchiyama. A matrix subadditivity inequality for f(A + B) and f(A) + f(B). Linear Algebra Appl., 423(2-3):512–518, 2007.

[21] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Fonctions de type positif sur les espaces L^{p}. C. R. Acad. Sci. Paris, 261:2153–2156, 1965.

[22] J. Brieussel and T. Zheng. Speed of random walks, isoperimetry and compression of finitely generated groups.

Preprint, available at http://arxiv.org/abs/1510.08040, 2015.

[23] E. Carlen. Trace inequalities and quantum entropy: an introductory course. In Entropy and the quantum, volume 529 of Contemp. Math., pages 73–140. Amer. Math. Soc., Providence, RI, 2010.

[24] E. A. Carlen and E. H. Lieb. A Minkowski type trace inequality and strong subadditivity of quantum entropy. II. Convexity and concavity. Lett. Math. Phys., 83(2):107–126, 2008.

[25] J. P. R. Christensen. Measure theoretic zero sets in infinite dimensional spaces and applications to differentiability of Lipschitz mappings. Publ. Dép. Math. (Lyon), 10(2):29–39, 1973. Actes du Deuxième Colloque d’Analyse Fonctionnelle de Bordeaux (Univ. Bordeaux, 1973), I, pp. 29–39.

[26] G. David and S. Semmes. Fractured fractals and broken dreams, volume 7 of Oxford Lecture Series in Mathematics and its Applications. The Clarendon Press, Oxford University Press, New York, 1997. Self-similar geometry through metric and measure.

[27] J. Ding, J. R. Lee, and Y. Peres. Markov type and threshold embeddings. Geom. Funct. Anal., 23(4):1207–1229, 2013.

[28] J. Dixmier. Formes linéaires sur un anneau d’opérateurs. Bull. Soc. Math. France, 81:9–39, 1953.

[29] P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105, 1969.

[30] P. Enflo. Uniform structures and square roots in topological groups. I, II. Israel J. Math. 8 (1970), 230-252; ibid., 8:253–272, 1970.

[31] P. Enflo. Uniform homeomorphisms between Banach spaces. In Séminaire Maurey-Schwartz (1975–1976), Espaces, L^{p}, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, page 7. Centre Math., École Polytech., Palaiseau, 1976.

[32] H. Epstein. Remarks on two theorems of E. Lieb. Comm. Math. Phys., 31:317–325, 1973.

[33] T. Figiel, W. B. Johnson, and G. Schechtman. Random sign embeddings from l_{r}^{n}, 2 < r < ∞. Proc. Amer. Math. Soc., 102(1):102–106, 1988.

[34] O. Giladi, M. Mendel, and A. Naor. Improved bounds in the metric cotype inequality for Banach spaces. J. Funct. Anal., 260(1):164–194, 2011.

[35] O. Giladi and A. Naor. Improved bounds in the scaled Enflo type inequality for Banach spaces. Extracta Math., 25(2):151–164, 2010.

[36] O. Giladi, A. Naor, and G. Schechtman. Bourgain’s discretization theorem. Ann. Fac. Sci. Toulouse Math. (6), 21(4):817–837, 2012.

[37] E. D. Gluskin, A. Pietsch, and J. Puhl. A generalization of Khintchine’s inequality and its application in the theory of operator ideals. Studia Math., 67(2):149–155, 1980.

[38] M. Gromov. Filling Riemannian manifolds. J. Differential Geom., 18(1):1–147, 1983.

[39] T. Hytönen and A. Naor. Pisier’s inequality revisited. Studia Math., 215(3):221–235, 2013.

[40] W. B. Johnson, B. Maurey, G. Schechtman, and L. Tzafriri. Symmetric structures in Banach spaces. Mem. Amer. Math. Soc., 19(217):v+298, 1979.

[41] W. B. Johnson, G. Schechtman, and J. Zinn. Best constants in moment inequalities for linear combinations of independent and exchangeable random variables. Ann. Probab., 13(1):234–253, 1985.

[42] M. Ĭ. Kadec′. Linear dimension of the spaces L_{p} and l_{q}. Uspehi Mat. Nauk, 13(6 (84)):95–98, 1958.

[43] M. I. Kadec and A. Pełczyński. Bases, lacunary sequences and complemented subspaces in the spaces L_{p}. Studia Math., 21:161–176, 1961/1962.

[44] N. J. Kalton. The nonlinear geometry of Banach spaces. Rev. Mat. Complut., 21(1):7–60, 2008.

[45] N. J. Kalton and N. L. Randrianarivony. The coarse Lipschitz geometry of l_{p} ⊕ l_{q}. Math. Ann., 341(1):223–237, 2008.

[46] M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes.

[47] J. R. Lee, A. Naor, and Y. Peres. Trees and Markov convexity. Geom. Funct. Anal., 18(5):1609–1659, 2009.

[48] S. Li. Markov convexity and nonembeddability of the Heisenberg group. Preprint, available at

    http://arxiv.org/abs/1404.6751, 2014.

[49] E. H. Lieb and W. E. Thirring. Inequalities for the moments of the eigenvalues of the Schrödinger Hamiltonian and their relation to Sobolev inequalities. In Studies in Mathematical Physics, pages 269–303. Princeton University Press, 1976.

[50] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. I. Springer-Verlag, Berlin-New York, 1977. Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92.

[51] N. Linial, A. Magen, and A. Naor. Girth and Euclidean distortion. Geom. Funct. Anal., 12(2):380–394, 2002.

[52] G.-M. Lövblom. Uniform homeomorphisms between unit balls in L_{p}-spaces. Math. Scand., 62(2):294–302, 1988.

[53] F. Lust-Piquard. Inégalités de Khintchine dans C_{p} (1 < p < ∞). C. R. Acad. Sci. Paris Sér. I Math., 303(7):289– 292, 1986.

[54] P. Mankiewicz. On Lipschitz mappings between Fréchet spaces. Studia Math., 41:225–241, 1972.

[55] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

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

[57] C. A. McCarthy. c_{p}. Israel J. Math., 5:249–271, 1967.

[58] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[59] M. Mendel and A. Naor. Some applications of Ball’s extension theorem. Proc. Amer. Math. Soc., 134(9):2577– 2584 (electronic), 2006.

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

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

[62] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics. J. Eur. Math. Soc. (JEMS), 15(1):287–337, 2013.

[63] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1:163–199, 2013.

[64] M. Mendel and A. Naor. Nonlinear spectral calculus and super-expanders. Publ. Math. Inst. Hautes Études Sci., 119:1–95, 2014.

[65] M. Mendel and A. Naor. Expanders with respect to Hadamard spaces and random graphs. Duke Math. J., 164(8):1471–1548, 2015.

[66] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2):167–233, 2012.

[67] A. Naor. Comparison of metric spectral gaps. Anal. Geom. Metr. Spaces, 2:Art. 1, 2014.

[68] A. Naor and Y. Peres. Embeddings of discrete groups and the speed of random walks. Int. Math. Res. Not. IMRN, pages Art. ID rnn 076, 34, 2008.

[69] A. Naor and Y. Peres. L_{p} compression, traveling salesmen, and stable walks. Duke Math. J., 157(1):53–108, 2011.

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

[71] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

[72] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Compos. Math., 147(5):1546– 1572, 2011.

[73] S.-i. Ohta. Markov type of Alexandrov spaces of non-negative curvature. Mathematika, 55(1-2):177–189, 2009.

[74] M. I. Ostrovskii. Metric embeddings, volume 49 of De Gruyter Studies in Mathematics. De Gruyter, Berlin, 2013. Bilipschitz and coarse embeddings into Banach spaces.

[75] R. E. A. C. Paley. Some theorems on abstract spaces. Bull. Amer. Math. Soc., 42(4):235–240, 1936.

[76] R. E. A. C. Paley and A. Zygmund. On some series of functions, (1). Math. Proc. Cambridge Philos. Soc., 26(3):337–357, 1930.

[77] G. Pisier. Some results on Banach spaces without local unconditional structure. Compositio Math., 37(1):3–19, 1978.

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

[79] G. Pisier. Non-commutative vector valued L_{p}-spaces and completely p-summing maps. Astérisque, (247):vi+131, 1998.

[80] G. Pisier and Q. Xu. Non-commutative L^{p}-spaces. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1459–1517. North-Holland, Amsterdam, 2003.

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

[82] H. P. Rosenthal. On the subspaces of L^{p} (p > 2) spanned by sequences of independent random variables. Israel J. Math., 8:273–303, 1970.

[83] I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44(3):522–536, 1938.

[84] F. A. Sukochev. Non-isomorphism of L_{p}-spaces associated with finite and infinite von Neumann algebras. Proc. Amer. Math. Soc., 124(5):1517–1527, 1996.

[85] M. Talagrand. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geom. Funct. Anal., 3(3):295–314, 1993.

[86] E. Veomett and K. Wildrick. Spaces of small metric cotype. J. Topol. Anal., 2(4):581–597, 2010.

[87] R. Wagner. Notes on an inequality by Pisier for functions on the discrete cube. In Geometric aspects of functional analysis, volume 1745 of Lecture Notes in Math., pages 263–268. Springer, Berlin, 2000.

[88] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York-Heidelberg, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

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

Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA

   E-mail address: naor@math.princeton.edu

Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

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