DISCRETE RIESZ TRANSFORMS AND SHARP METRIC X INEQUALITIES p ASSAFNAOR Abstract. Forp∈[2,∞)themetricX inequalitywithsharpscalingparameterisprovenhereto p 6 hold true in L . The geometric consequences of this result include the following sharp statements p 1 about embeddingsof L intoL when 2<q<p<∞: themaximal θ∈(0,1] for which L admits q p q 0 a bi-θ-H¨older embedding into L equals q/p, and for m,n ∈ N the smallest possible bi-Lipschitz p 2 distortion of any embedding into L of the grid {1,...,m}n ⊆ℓn is bounded above and below by n constant multiples (dependingonlypon p,q) of the quantitymin{qn(p−q)(q−2)/(q2(p−2)),m(q−2)/q}. a J 3 1 1. Introduction ] G The purpose of the present article is to resolve positively three conjectures that were posed by M the author in collaboration with G. Schechtman in [NS14]. Specifically, we shall prove here that Conjecture 1.5, Conjecture 1.8 and Conjecture 1.12 of [NS14] all have a positive answer. As we . h shall explain below, of these three conjectures, Conjecture 1.8 was a longstanding folklore open t a problem in embedding theory, while Conjecture 1.12 asserts the validity of a quite subtle and m perhaps unexpected phase transition phenomenon that was first formulated as conceivably holding [ true in [NS14]. Conjecture 1.5 relates to a bi-Lipschitz invariant that was introduced in [NS14], asking about finer properties of this invariant in terms of a certain auxiliary parameter. 1 v Itwasprovenin[NS14]thatConjecture1.8andConjecture1.12followfromConjecture1.5. Thus 2 Conjecture1.5 is theheart of the matter andthe main focus of thepresent article, butwe shall first 3 describeall of the above conjectures since, by proving their validity, we establish delicate geometric 3 3 phenomena related to the metric structure of Lp spaces. In addition to these applications, a key 0 contribution of the present article is the use of a deep result of Lust-Piquard [LP98] for geometric . 1 purposes. While [NS14] proposed an approach to resolve the above conjectures, formulated as 0 Question 6.1 in [NS14] and discussed at length in [NS14, Section 6], where it was shown to imply 6 the above conjectures, we do not pursue this approach here, and indeed Question 6.1 of [NS14] 1 : remainsopen. Belowwetakeadifferentroute,yieldinganovelconnectionbetweenpurelygeometric v questions and investigations in modern harmonic analysis and operator algebras. i X 1.1. Geometricstatements. FollowingstandardnotationinBanachspacetheoryandembedding r a theory (as in, say, [LT77, Ost13]), for n N and p [1, ) we let ℓn denote the space Rn equipped ∈ ∈ ∞ p with the ℓ norm. When referring to the space L , we mean for concreteness the Lebesgue space p p L (R), though all of our new geometric results apply equally well to any infinite dimensional L (µ) p p space. The L distortion of a metric space (X,d ), denoted c (X) [0, ], is the infimum over p X p ∈ ∞ those D [0, ] for which there exists a mapping f : X L that satisfies p ∈ ∞ → x,y X, d (x,y) 6 f(x) f(y) 6 Dd (x,y). ∀ ∈ X k − kLp X (X,d ) is said to admit a bi-Lipschitz embedding into L if c (X) < . X p p Given m,n N and q [1, ), themetric space whose underlyingse∞t is 1,...,m n (the m-grid in Rn), equipp∈ed with th∈e met∞ric inherited from ℓn, will be denoted below {by [m]n. I}t follows from q q the classical work [Pal36] of Paley, in combination with general principles related to differentiation of Lipschitz functions (see [BL00, Chapter 7]), that if 2 < q < p < then lim c (ℓn) = . ∞ n→∞ p q ∞ Supportedin part by theBSF, the Packard Foundation and theSimons Foundation. 1 Since [m]n becomes “closer” to ℓn as m , one can apply an ultrapower argument (see [Hei80]) q q → ∞ to deduce from this that lim c ([m]n) = , but such reasoning does not yield information m,n→∞ p q ∞ on the rate of growth of c ([m]n). Effective estimates here follow from an alternative approach of p q Bourgain [Bou87] (with an improvement in [GNS12]), as well as the approach of [NS14], but the resulting bounds are far from being sharp. Resolving Conjecture 1.12 of [NS14], Theorem 1 below computes the quantity c ([m]n) up to constant factors that may depend on p,q but not on m,n. p q Theorem 1 (Sharp evaluation of the L distortion of ℓn grids). Suppose that p,q [2, ) satisfy q < p. Then for every m,n N we havep q ∈ ∞ ∈ cp [m]nq ≍p,q min n(pq−2q()p(−q−2)2),m1−2q . (1) (cid:26) (cid:27) (cid:0) (cid:1) In the statement of Theorem 1, as well as in what follows, we use standard asymptotic notation. Namely, the notation a . b (respectively a & b) stands for a 6 cb (respectively a > cb) for some universal constant c (0, ). The notation a b stands for (a . b) (b . a). When we allow ∈ ∞ ≍ ∧ for implicit constants to depend on parameters, we indicate this by subscripts. Thus a . b p,q (respectively a & b) means that there exists c(p,q) (0, ) that may depend only on p,q such p,q ∈ ∞ that a 6 c(p,q)b (respectively a > c(p,q)b). The notation a b stands for (a . b) (b . a). p,q p,q p,q ≍ ∧ Very few results at the level of precision of Theorem 1 are known, and analogous questions are open even for some values of p,q that are not covered by Theorem 1; see [NS14, Remark 1.13] for more on this interesting topic. Theasymptotic formula (1) expresses thestatement that there exist twospecificembeddingsof[m]n intoL suchthatoneofthemisalwaysthebestpossibleembedding q p of [m]n into L , up to constant factors that do not depend on m,n. One of these embeddings arises q p from the work of Rosenthal [Ros70] (relying also on computations in [GPP80, FJS88]), and the other is due to Mendel and the author [MN06] (relying also on a construction from [Sch38]). These issues,includingprecisedescriptionsoftheabovetwoembeddings,areexplainedindetailin[NS14]. The following immediate corollary of Theorem 1 asserts that if 2 < q < p < and m,n N ∞ ∈ then the L distortion of [m]n exhibits a phase transition at m n(p−q)/(q(p−2)). p q ≍ Corollary 2 (Sharp phase transition of the L distortion of ℓn grids). Suppose that m,n N and p q ∈ p,q (2, ) satisfy q < p. Then ∈ ∞ p−q m & nq(p−2) =⇒ cp [m]nq ≍p,q cp ℓnq , while as n we have (cid:0) (cid:1) (cid:0) (cid:1) → ∞ p−q m = o nq(p−2) =⇒ cp [m]nq = o cp ℓnq . (cid:16) (cid:17) Thus, to state one concrete example so as to illu(cid:0)strate(cid:1)the s(cid:0)itu(cid:0)atio(cid:1)n(cid:1) whose validity we establish here, when, say, q = 3 and p = 4, and one tries to embed the grid [m]n into L , one sees that there 3 4 is a phase transition at m √6 n. If m &√6 n then any embedding of [m]n into L incurs the same ≍ 3 4 distortion (up to universal constant factors) as the distortion required to embed all of ℓn into L , 3 4 which grows like 1√8 n. However, if m = o(√6 n) then one can embed [m]n into L with distortion 3 4 o(1√8 n), and in this case the L distortion of [m]n is √3 m, up to universal constant factors. 4 3 Our second geometric result is Theorem 3 below, which resolves Conjecture 1.8 of [NS14]. Theorem 3 (Evaluation of the critical L snowflake exponent of L ). Suppose that p,q (2, ) p q ∈ ∞ satisfy q < p. Then the maximal θ (0,1] for which the metric space (L , x y θ ) admits a ∈ q k − kLq bi-Lipschitz embedding into L equals q/p. p q/p InthesettingofTheorem3,thefactthatthemetricspace(L , x y )doesindeedadmitabi- q k − kLq Lipschitz (even isometric) embeddinginto L was established by Mendel and the author in [MN04]. p 2 Sincethen, ithasbeenawellknownconjecturethatinthis context theH¨older exponentq/pcannot be increased, but before [NS14] it wasn’t even known that if (L , x y θ ) admits a bi-Lipschitz q k − kLq embedding into L then necessarily θ < 1 δ for some δ = δ(p,q) > 0. Note that the endpoint case p − q = 2 must be removed from Theorem 3 since L embeds isometrically into L . 2 p 1.2. Optimal scaling in the L -valued metric X inequality. In what follows, given n N p p we shall denote the set 1,...,n by [n]. The coordinate basis of Rn will be denoted by e ,...∈,e , 1 n and for a sign vector ε ={ (ε ,...},ε ) 1,1 n and a subset S [n] we shall use the notation 1 n ∈ {− } ⊆ def εS = εjej. (2) j∈S X Fix p (0, ). Following [NS14], a metric space (X,d ) is said to be an X metric space if X p there exis∈ts X∞(0, ) such that for every n N and k [n] there exists m N such that every function f :Zn∈ X∞satisfies the following d∈istance ineq∈uality. ∈ 2m → 1 1 E d f(x+mε ),f(x) p p n X S (cid:18) k SX⊆[n] h (cid:0) (cid:1) i(cid:19) |S|=k (cid:0) (cid:1) n p 1 6 Xm k E d f(x+e ),f(x) p + k 2 E d f(x+ε),f(x) p p. (3) X j X n n Xj=1 h (cid:0) (cid:1) i (cid:18) (cid:19) h (cid:0) (cid:1) i(cid:19) The expectations in (3) are with respect to (x,ε) Zn 1,1 n chosen uniformly at random. ∈ 2m ×{− } We refer to [NS14] for a detailed discussion of the meaning of (3); see also Sections 1.2.1, 1.3 below. The above definition of X metric spaces introduces the auxiliary integer m N, which we p ∈ call the scaling parameter corresponding to n and k. For some purposes m can be allowed to be arbitrary, but for other purposes one needs to obtain good bounds on m (as a function of n,k). It can, however, be quite difficult to obtain sharp bounds on scaling parameters in metric inequalities (for example, an analogous question in the context of metric cotype [MN08] is longstanding and important). In [NS14] it was proven that if p [2, ) then L is an X metric space. The proof p p ∈ ∞ in [NS14] yields the validity of (3) when X = L whenever m & n3/2/√k. It was also shown p p in [NS14, Proposition 1.4] that if p (2, ) and k is sufficiently large (as a function of p) then ∈ ∞ for (3) to hold true in L one must necessarily have m & n/k. Conjecture 1.5 of [NS14] asks p p whether for every p (2, ) this lower bound on m actually expresses the asymptotic behavior of ∈ ∞ p the best possible scaling parameter, i.e., whether the metric X inequality (3) holds true in L for p p every m & n/k. Theorem 4 below resolves this conjecture positively. p Theorem 4p(L is an X metric space with sharp scaling parameter). Suppose that k,m,n N p p ∈ satisfy k [n] and m > n/k. Suppose also that p [2, ). Then every f : Zn L satisfies ∈ ∈ ∞ 8m → p p 1 1 E f(x+4mεS) f(x) p p n k − kLp (cid:18) k SX⊆[n] h i(cid:19) |S|=k (cid:0) (cid:1) n p 1 . m k E f(x+e ) f(x) p + k 2 E f(x+ε) f(x) p p, (4) p n k j − kLp n k − kLp (cid:18) Xj=1 h i (cid:18) (cid:19) h i(cid:19) where the expectations are takenwith respect to(x,ε) Zn 1,1 n chosen uniformly at random. ∈ 8m×{− } Remark 5. Our proof of Theorem 4 shows that the implicit constant in (4) is O(p4/logp). As explainedin[NS14], thisconstant mustbeatleast a(universal)constant multipleofp/logp. While 3 it is conceivable that a more careful implementation of our approach could somewhat decrease the dependence on p that we obtain, it seems that a new idea is required in order to establish the sharp dependence of O(p/logp) in (4) (if true). We leave the question of determining the correct asymptotic dependenceon p in (4) as an interesting (and perhapsquite challenging) open question. 1.2.1. Applications of Theorem 4. The usefulness of the metric X inequality for L stems in part p p from the fact that it allows one to rule out the existence of metric embeddings in situations where the classical differentiation techniques fail. Examples of such situations include the treatment of discrete sets as in Theorem 1, where it isn’t clear how to interpret the notion of derivative, as well as the treatment of H¨older mappings as in Theorem 3, where, unlike the Lipschitz case, mappings need not have any point of differentiability. In fact, by [NS14, Theorem 1.14] both Theorem 1 and Theorem 3 follow from Theorem 4. For completeness, we shall now briefly sketch why this is so. Supposethat 26 q < p < and m,n N. It is simple to check, as done in [NS14, Lemma 3.1], that there exists h: Zn [3∞2m]n such t∈hat for (x,ε) Zn 1,1 n, S [n] and j [n], 8m → q ∈ 8m×{− } ⊆ ∈ h(x+4mεS) h(x) ℓn m S 1q and h(x+ej) h(x) ℓn 1 and h(x+ε) h(x) ℓn nq1. k − k q ≍ | | k − k q ≍ k − k q ≍ FixD [1, )andsupposethatφ: [32m]n L satisfies x y 6 φ(x) φ(y) 6 D x y ∈ ∞ q → p k − kℓnq k − kLp k − kℓnq for every x,y [32m]n. An application of Theorem 4 to f = h φ (with m replaced by 4m), which ∈ q ◦ we are allowed to do only when k [n] is such that 4m > n/k, yields the bound ∈ k1qp D & max . (5) p 1 k>nk/∈(1[n6]m2) k+kp2npq−p2 p By evaluating the maximum in (5), one arrives a(cid:16)t the asympto(cid:17)tic lower bound on c ([32m]n) that p q appears in (1). As we explained earlier, the matching upperbound in (1) corresponds to the better of two explicit embeddings that are described in equations (11) and (27) of [NS14]. This completes the deduction of Theorem 1. Next, fix L [1, ) and θ (0,1]. Supposethat ψ : L L satisfies q p ∈ ∞ ∈ → x y θ 6 ψ(x) ψ(y) 6 L x y θ for every x,y L . For k,n N with k [n], fix k − kLq k − kLp k − kLq ∈ q ∈ ∈ m = n/(2k) and apply Theorem 4 to f = ψ h. The estimate thus obtained is ⌈ ⌉ ◦ p p 1 n θ2 kθq .p L n k+ k 2 nθqp p . k k n r (cid:18) (cid:19) ! (cid:16) (cid:17) Hence, for every n [n] we have ∈ 1 1−θ p p θ−1 p θ 1−1 −1 1 .p Ln 2 min k+k2n (cid:16)q 2(cid:17) k (cid:16)2 q(cid:17) 2. (6) ·k∈[n] (cid:18) (cid:19) Theorem 3 now follows by choosing the optimal k in (6) and letting n ; complete details of → ∞ this computation appear in the proof of Theorem 1.14 in [NS14]. 1.3. Hypercube Riesz transforms and an X inequality for Rademacher chaos. Fixing p n N, for every h : 1,1 n R and j [n] let ∂ h: 1,1 n R be given by j ∈ {− } → ∈ {− } → ε 1,1 n, ∂ h(ε) d=ef h(ε) h(ε ,...,ε , ε ,ε ,...,ε ). (7) j 1 j−1 j j+1 n ∀ ∈ {− } − − Also, given S [n] we shall denote by ESf : 1,1 n R the function that is obtained from h by averaging over⊆the coordinates in S, i.e., reca{l−ling t}he→notation (2), we define 1 ∀ε ∈{−1,1}n, ESh(ε) d=ef 2n h δS+ε[n]rS . (8) δ∈{−1,1}n X (cid:0) (cid:1) 4 In particular, ESh depends only on those entries of ε 1,1 n that belong to [n]r S. Given ∈ {− } p [1, ), we shall reserve from now on the notation h exclusively for the L norm of h with p p ∈ ∞ k k respect to the normalized counting measure on the discrete hypercube 1,1 n, i.e., {− } 1 h d=ef 1 h(ε)p p = E hp p1 . k kp 2n | | [n]| | (cid:18) ε∈{−1,1}n (cid:19) X (cid:0) (cid:1) In what follows, L0( 1,1 n) denotes the subspace of all those h L ( 1,1 n) with E h = 0. p {− } ∈ p {− } [n] We shall work with the usual Fourier–Walsh expansion of a function h : 1,1 n R. Thus, for every A [n] consider the corresponding Walsh function WA : 1,1 n {−R giv}en→by ⊆ {− } → ε 1,1 n, WA(ε) d=ef εj, ∀ ∈ {− } j∈A Y and denote 1 h(A) d=ef h(ε)WA. 2n ε∈{−1,1}n X Then we have b 1 ε 1,1 n, h(ε) = h(A)WA(ε). ∀ ∈ {− } 2n A⊆[n] X In probabilistic terminology, the above representation of bh as a multilinear polynomial in the variables ε ,...,ε expresses it as Rademacher chaos. A useful inequality for Rademacher chaos of 1 n thefirstdegree, i.e., forweighted sumsofi.i.d. Bernoullirandomvariables, servedastheinspiration forthemetricX inequality (3). Specifically, (3)isanonlinearextension ofthefollowing inequality, p which holds true for every p [2, ), k,n N with k [n], and every a ,...,a R. 1 n ∈ ∞ ∈ ∈ ∈ 1 n p n 1 1 ε a p p . p k a p+ (k/n)2 ε a p p. (9) 2n n j j logp n | j| 2n j j (cid:18) k SX⊆[n]ε∈{X−1,1}n(cid:12)Xj∈S (cid:12) (cid:19) (cid:18) Xj=1 ε∈{X−1,1}n(cid:12)Xj=1 (cid:12) (cid:19) |S|=k (cid:12) (cid:12) (cid:12) (cid:12) (cid:0) (cid:1) (cid:12) (cid:12) (cid:12) (cid:12) This inequality is due to Johnson, Maurey, Schechtman and Tzafriri, who proved it in [JMST79] with a constant factor that grows to with p faster than the p/logp factor that appears in (9). ∞ The factor p/logp that is stated in (9) is best possible; in the above sharp form, (9) is due to Johnson, Schechtman and Zinn [JSZ85]. As a step towards Theorem 4, we shall prove the following theorem in Section 3 below, thus extending (9) to Rademacher chaos of arbitrary degree. Theorem 6 (X inequality for Rademacher chaos). Suppose that p [2, ), n N and k [n]. p ∈ ∞ ∈ ∈ Then every h L0( 1,1 n) satisfies ∈ p {− } 1 n p 1 1n E[n]rSh pp p .p nk k∂jhkpp + nk 2 khkpp p. (10) (cid:18) k S⊆[n] (cid:19) (cid:18) j=1 (cid:18) (cid:19) (cid:19) (cid:0) (cid:1) |SX|=k(cid:13)(cid:13) (cid:13)(cid:13) X The deduction of Theorem 4 from Theorem 6 appears in Section 2 below. Remark 7. As in (4), the implicit constant that we obtain in (10) is O(p4/logp). In fact, our proof yields the following slightly more refined estimate in the setting of Theorem 6. 1n E[n]rSh pp p1 . √lpo25gp nk p1 n k∂jhkpp p1 + lopg4p nk ·khkp. (11) (cid:18) k S⊆[n] (cid:19) (cid:18) (cid:19) (cid:18)j=1 (cid:19) r (cid:0) (cid:1) |SX|=k(cid:13)(cid:13) (cid:13)(cid:13) X It remains open to determine the growth rate as p of the implicit constant in (10). → ∞ 5 1.3.1. Lust-Piquard’s work. Our proof of Theorem 6 uses deep work [LP98] of Lust-Piquard on dimension-free bounds for discrete Riesz transforms. Specifically, for every h : 1,1 n R and j [n]the jth (hypercube)Riesz transform of h, denoted R h : 1,1 n R, is{d−efine}da→s follows. j ∈ {− } → h(A) ∀ε∈ {−1,1}n, Rjh(ε) d=ef A WA(ε). (12) AX⊆[n] b | | j∈A p Lust-Piquardprovedthefollowinginequalities,whichholdtrueforp [2, )andh L0( 1,1 n). ∈ ∞ ∈ p {− } 1 n 1 h . (R h)2 2 . p h . (13) p3/2k kp j k kp (cid:13)(cid:13)(cid:16)Xj=1 (cid:17) (cid:13)(cid:13)p (cid:13) (cid:13) The inequalities in (13) were proved by(cid:13)Lust-Piquard(cid:13)in [LP98], though with a dependence on p that is worse than what we stated above. The dependence on p that appears in (13) follows from [BELP08]. Note that these estimates are stated in [BELP08] in terms of the strong (p,p) norm of the Hilbert transform with values in the Schatten–von Neumann trace class S , but this p norm was shown to be O(p) by Bourgain in [Bou86], and the bounds that we stated in (13) result from a direct substitution of Bourgain’s bound into the statements in [BELP08]. Theavailability of dimension independentboundsfor Riesz transformsis a well known paradigm in other (non-discrete) settings, originating from important classical work of Stein [Ste83] in the case of Rn equipped with Lebesgue measure (see also [GV79, DRdF85, Ban˜86]). Most pertinent to thepresentcontext is theclassical theorem of P.A. Meyer [Mey84] (seealso [Gun86])that obtained dimensionindependentboundsfortheRiesztransformsthatareassociatedtoRn equippedwiththe Gaussianmeasure(andtheOrnstein–Uhlenbeckoperator). Pisierdiscoveredin[Pis88]aninfluential alternative proof of P. A. Meyer’s theorem, based on a transference argument (see [CW76]) that allows one to reduce the question to the boundedness of the (one dimensional) Hilbert transform. Lust-Piquard’s work generally follows Pisier’s strategy, but it also uncovers a phenomenon that is genuinely present in the hypercube setting and not in the Gaussian setting. Specifically, Lust- Piquard reduces the task of bounding the hypercube Riesz transforms to that of bounding the S p normof certain operatorsinanoncommutative algebraof(2n by2n)matrices, andproceedstodo ∗ so using operator-theoretic methods, including her noncommutative Khinchine inequalities [LP86]. This indicates why the S -valued Hilbert transform makes its appearance in Lust-Piquard’s p inequality (recall the paragraph above, immediately following (13)), despite the fact that (13) deals with real-valued functions on the (commutative) hypercube. Significantly, while the classical resultsonRiesztransforms(withrespecttoeitherLebesguemeasureortheGaussianmeasure)yield dimensionindependentboundsforevery p (1, ), itturnsoutthat(13) actually fails toholdtrue ∈ ∞ when p (1,2), as explained in [LP98] (where this observation is attributed to unpublished work ∈ of Lamberton); see also [BELP08, Section 5.5]. The reason for this disparity between the ranges p (1,2) and p [2, ) becomes clear when one transfers the question to the noncommutative ∈ ∈ ∞ setting, and this suggests a more complicated (but still dimension-free) replacement for (13) in the range p (1,2), which Lust-Piquard also proved in [LP98]. So, while it is conceivable that a proof ∈ of (13) could be found that does not proceed along Lust-Piquard’s noncommutative route, such a proof has not been found to date, and the qualitative divergence between the discrete situation and its continuous counterparts indicates that there may be an inherently different phenomenon at play here. Since its initial publication, Lust-Piquard’s work influenced developments by herself and others thatfocused onprovingrelated inequalities in other situations; wedonothave anythingnew to add to this interesting body of work other than showing here that in addition to their intrinsic interest, such results can have a decisive role in understanding geometric embedding questions. 6 2. Deduction of Theorem 4 from Theorem 6 Assumingthevalidity of Theorem6forthemoment, weshallnowproceedtoshow howitimplies Theorem 4. Note that since (4) involves only the pth powers of distances in L , by integration it p suffices to prove Theorem 4 for real valued functions. So, from now on we shall assume that m,n N and we are given a function f : Zn R, the goal being to prove the validity of (4) for ∈ 8m → every k [n] provided that m > n/k, with the L norms replaced by absolute values in R. p In wh∈at follows, given S [n] and f : Zn R, define a function TSf : Zn R by ⊆ p 8m → 8m → 1 ∀x ∈ Zn8m, TSf(x)d=ef 2n f(x+2δS). (14) δ∈{−1,1}n X We record for future use the following simple lemma. Lemma 8. For every p [1, ), m,n N, S [n] and f :Zn R we have ∈ ∞ ∈ ⊆ 8m → 1 1 1 p 1 p f(x) TSf(x)p 6 2 f(x+ε) f(x)p . (15) (8m)n | − | (16m)n | − | (cid:18) x∈Zn (cid:19) (cid:18) ε∈{−1,1}nx∈Zn (cid:19) X8m X X8m Proof. By convexity, for every x Zn we have ∈ 8m 1 f(x) TSf(x)p 6 f(x) f(x+2δS)p | − | 2n | − | δ∈{−1,1}n X 2p−1 p p 6 2n f(x)−f(x+δS+δ[n]rS) + f(x+δS+δ[n]rS)−f(x+2δS) . (16) δ∈{X−1,1}n(cid:16)(cid:12) (cid:12) (cid:12) (cid:12) (cid:17) (cid:12) (cid:12) (cid:12) (cid:12) The desired estimate (15) follows by averaging (16) over x Zn while using the translation invariance of the uniformmeasure on Zn , and that if δ is unifo∈rmly8mdistributed over 1,1 n then 8m {− } the sign vectors δS+δ[n]rS and δS+δ[n]rS are both also uniformly distributed over 1,1 n. (cid:3) − {− } Lemma 9. Suppose that m,n N and k [n]. If p [2, ) then every f :Zn R satisfies ∈ ∈ ∈ ∞ 8m → 1 T[n]rSf(x+4mεS) T[n]rSf(x) p − (16m)n n mp k SX⊆[n]ε∈{X−1,1}nx∈XZn8m (cid:12)(cid:12) (cid:12)(cid:12) |S|=k (cid:0) (cid:1) n p . k/n f(x+e ) f(x)p+ (k/n)2 f(x+ε) f(x)p. (17) p (8m)n | j − | (16m)n | − | j=1x∈Zn ε∈{−1,1}nx∈Zn X X8m X X8m Proof. For every fixed S [n] we have ⊆ 1 (161m)n T[n]rSf(x+4mεS)−T[n]rSf(x) p p (cid:18) ε∈{−1,1}nx∈Zn (cid:19) X X8m(cid:12) (cid:12) m (cid:12) (cid:12) 1 6 (161m)n T[n]rSf(x+4kεS)−T[n]rSf(x+4(k−1)εS) p p (18) k=1(cid:18) ε∈{−1,1}nx∈Zn (cid:19) X X X8m(cid:12) (cid:12) (cid:12) 1 (cid:12) = m (161m)n T[n]rSf(y+2εS)−T[n]rSf(y−2εS) p p, (19) (cid:18) ε∈{−1,1}ny∈Zn (cid:19) X X8m(cid:12) (cid:12) (cid:12) (cid:12) where for (19) make the change of variable y = x+2(2k+1)ε in each of the summands of (18). S 7 For every x Zn define h : 1,1 n R by ∈ 8m x {− } → ε 1,1 n, h (ε) d=ef f(x+2ε) f(x 2ε). (20) x ∀ ∈ {− } − − Recalling (8) and (14), observe that for every (x,ε) Zn 1,1 n and S [n] we have ∈ 8m×{− } ⊆ T[n]rSf(x+2εS) T[n]rSf(x 2εS) = E[n]rShx(ε). − − It therefore follows from (19) that 1 T[n]rSf(x+4mεS) T[n]rSf(x) p − (16m)n n mp k SX⊆[n]ε∈{X−1,1}nx∈XZn8m (cid:12)(cid:12) (cid:12)(cid:12) |S|=k (cid:0) (cid:1) n p 6 (8m)1n n E[n]rShx pp .p (8km/n)n k∂jhxkpp+ ((k8/mn))n2 khxkpp, (21) k S⊆[n]x∈Zn j=1 x∈Zn x∈Zn (cid:0) (cid:1) |XS|=k X8m(cid:13)(cid:13) (cid:13)(cid:13) X X8m X8m where in the last step of (21) we applied Theorem 6 with h replaced by h , separately for each x x Zn , which we are allowed to do because the function h is odd, so h L0( 1,1 n). ∈ 8m x x ∈ p {− } Next, observe that for every (x,ε) Zn 1,1 n and j [n] we have ∈ 8m×{− } ∈ ∂ h (ε)p (=20) f(x+2ε) f(x 2ε) f(x+2ε 4ε e )+f(x 2ε+4ε e )p j x j j j j | | | − − − − − | 6 2p−1 f(x+2ε) f(x+2ε 4ε e )p+2p−1 f(x 2ε) f(x 2ε+4ε e )p. (22) j j j j | − − | | − − − | By summing (22) over (x,ε) Zn 1,1 n, we therefore see that ∈ 8m×{− } 1 2p j [n], ∂ h p 6 f(y+4e ) f(y)p. (23) ∀ ∈ (8m)n k j xkp (8m)n | j − | x∈Zn y∈Zn X8m X8m Since for every y Zn we have ∈ 8m 4 f(y+4e ) f(y)p 6 4p−1 f(y+ke ) f(y+(k 1)e )p, j j j | − | | − − | k=1 X it follows from (23) that 1 n 8p n ∂ h p 6 f(z+e ) f(z)p. (24) (8m)n k j xkp (8m)n | j − | j=1x∈Zn j=1z∈Zn X X8m X X8m In the same vein to the above reasoning, for every (x,ε) Zn 1,1 n we have ∈ 8m×{− } 2 (20) h (ε)p 6 4p−1 f(x+kε) f(x+(k 1)ε)p. x | | | − − | k=−1 X Consequently, 1 4p h p 6 f(z+ε) f(z)p. (25) (8m)n k xkp (16m)n | − | x∈Zn ε∈{−1,1}nz∈Zn X8m X X8m The desired estimate (17) now follows from a substitution of (24) and (25) into (21). (cid:3) 8 Proof of Theorem 4. Fixing (x,ε) Zn 1,1 n and S [n], observe that ∈ 8m×{− } ⊆ f(x+4mεS) f(x)p 6 3p−1 T[n]rSf(x+4mεS) T[n]rSf(x) p+ f(x) T[n]rSf(x) p | − | − − (cid:16)(cid:12)(cid:12)+ f(x+4mεS) T[n]rSf(x+4m(cid:12)(cid:12) εS)(cid:12)(cid:12)p . (cid:12)(cid:12) (26) | − | By averaging (26) over (x,ε) Zn 1,1 n and all those S [n] wit(cid:17)h S = k, while using ∈ 8m × {− } ⊆ | | translation invariance in the variable x, we see that 1 f(x+4mεS) f(x) p | − | (16m)n n mp k S⊆[n]ε∈{−1,1}nx∈Zn X X X8m |S|=k (cid:0) (cid:1) 1 T[n]rSf(x+4mεS) T[n]rSf(x) p . − (27) p (16m)n n mp k SX⊆[n]ε∈{X−1,1}nx∈XZn8m (cid:12)(cid:12) (cid:12)(cid:12) |S|=k (cid:0) (cid:1) 1 + mp(8m)n n |f(x)−T[n]rSf(x)|p. (28) k S⊆[n]x∈Zn X X8m |S|=k (cid:0) (cid:1) The quantity that appears in (27) can be bounded from above using Lemma 9, and the quantity that appears in (28) can be bounded from above using Lemma 8. The resulting estimate is 1 f(x+4mεS) f(x)p | − | (16m)n n mp k S⊆[n]ε∈{−1,1}nx∈Zn X X X8m |S|=k (cid:0) (cid:1) p k/n n k 2 + 1 . f(x+e ) f(x)p+ n mp f(x+ε) f(x)p. p (8m)n | j − | (16m)n | − | j=1x∈Zn (cid:0) (cid:1) ε∈{−1,1}nx∈Zn X X8m X X8m This implies the desired estimate (4), since we are assuming that m > n/k. (cid:3) p 3. Proof of Theorem 6 Suppose that n N and h : 1,1 n R. For every k 0,...,n the kth Rademacher projection of h is th∈e function Ra{d−h :} 1→,1 n R that is giv∈en{by } k {− } → Radkh(ε) d=ef h(A)WA(ε). A⊆[n] X |A|=kb WealsohavethecommonnotationRad h = Radh. NotethatRad isthemeanofh,i.e.,recalling 1 0 the notation (8), Rad h= E h. By a classical theorem of Bonami [Bon68], if η : 1,1 n R is 0 [n] {− } → a Rademacher chaos of order at most k, i.e., η(A) = 0 whenever A [n] is such that A > k, then ⊆ | | for every p [2, ) we have η 6 (p 1)k/2 η 6 pk/2 η . Consequently, p 2 2 ∈ ∞ k k − k k k k k b k k Radkh p 6 p2 Radkh 2 6 p2 h 2 6 p2 h p, k k k k k k k k where we used the fact that (by Parseval’s identity) Rad h 6 h , and that h 6 h k 2 2 2 p k k k k k k k k since p> 2. This was a quick (and standard) derivation of the following well-known operator norm bound for Rad , which we state here for ease of future reference. k k kRadkkp→p 6 p2. (29) 9 Given S [n] and α R, for every h: 1,1 n R define a function ∆αh: 1,1 n R by S ⊆ ∈ {− } → {− } → ε 1,1 n, ∆αSh(ε) d=ef A S αh(A)WA(ε). ∀ ∈ {− } | ∩ | A⊆[n] X A∩S6=∅ b Thus, recalling the notation (7) for the hypercube partial derivatives ∂ ,...,∂ , as well the nota- 1 n tion (12) for the hypercube Riesz transforms R ,...,R , we have the following standard identities. 1 n j [n], R = 1∂ ∆−21. ∀ ∈ j 2 j [n] This means that Lust-Piquard’s inequality (13) can we rewritten as follows. 1 1 n 1 1 ∆2 h . (∂ h)2 2 . p ∆2 h . (30) p3/2 [n] j [n] (cid:13)(cid:13) (cid:13)(cid:13)p (cid:13)(cid:13)(cid:16)Xj=1 (cid:17) (cid:13)(cid:13)p (cid:13)(cid:13) (cid:13)(cid:13)p By Khinchine’s inequality ((cid:13)with a(cid:13)symp(cid:13)totically sharp(cid:13)constan(cid:13)t, see(cid:13)[PZ30, Lem. 2]), we have (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) n 1 1 n p p1 n 1 (∂ h)2 2 6 δ ∂ h . √p (∂ h)2 2 . j 2n j j p j (cid:13)(cid:13)(cid:16)Xj=1 (cid:17) (cid:13)(cid:13)p (cid:18) δ∈{X−1,1}n(cid:13)Xj=1 (cid:13) (cid:19) (cid:13)(cid:13)(cid:16)Xj=1 (cid:17) (cid:13)(cid:13)p (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) In combinat(cid:13)ion with (30), t(cid:13)his implies that (cid:13) (cid:13) (cid:13) (cid:13) n 1 1 1 1 p p 3 1 p32 (cid:13)(cid:13)∆2[n]h(cid:13)(cid:13)p . (cid:18)2n δ∈{X−1,1}n(cid:13)Xj=1δj∂jh(cid:13)p(cid:19) . p2 (cid:13)(cid:13)∆2[n]h(cid:13)(cid:13)p. (31) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) For ease of future refe(cid:13)rence,(cid:13)we also record her(cid:13)e the follow(cid:13)ing formal(cid:13)conseq(cid:13)uence of (31), which holds true for every S [n] by an application of (31) to the restriction of h to the coordinates in S. ⊆ 1 1 1 1 p p 3 1 p23 (cid:13)(cid:13)∆2Sh(cid:13)(cid:13)p . (cid:18)2n δ∈{X−1,1}n(cid:13)Xj∈Sδj∂jh(cid:13)p(cid:19) . p2 (cid:13)(cid:13)∆2Sh(cid:13)(cid:13)p. (32) (cid:13) (cid:13) Lemma 10 below co(cid:13)(cid:13)ntains(cid:13)(cid:13) bounds on negat(cid:13)ive powers(cid:13)of the hyp(cid:13)(cid:13)ercub(cid:13)(cid:13)e Laplacian ∆[n] that will be used later, but are more general and precise than what we actually need for the proof of Theorem 6: we will only use the following operator norm estimate corresponding to the case α = 1/2 of Lemma 10, and a worse dependence on p would have sufficed for our purposes as well. −1 p [2, ), sup ∆ 2 . logp. (33) ∀ ∈ ∞ n∈N(cid:13) [n](cid:13)p→p (cid:13) (cid:13) p We include here the sharp estimates of Lemma 1(cid:13)0 bec(cid:13)ause they are interesting in their own right (cid:13) (cid:13) and our proof yields them without additional effort. The boundedness of negative powers of the hypercube Laplacian were studied in [NS02, Section 3] in the context of vector valued mappings. Byspecializing theboundsthatarestated in[NS02]tothecaseofrealvaluedmappingsoneobtains a variant of (33), butwith a much worse dependenceon p (the resultingboundgrows exponentially withp). The(simple)proofbelowofLemma10followsthestrategy of[NS02]whileusingadditional favorablepropertiesofrealvaluedmappingsandtakingcaretoobtainasymptotically sharpbounds. Lemma 10. Suppose that p [2, ) and α (0, ) satisfy ∈ ∞ ∈ ∞ 5+logp α 6 . (34) 4 Then (logp)α sup ∆−α . (35) n∈N [n] p→p ≍ 2αΓ(1+α) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 10