Applications of Deviation Inequalities on Finite Metric Sets

The first step in this direction is a result by Johnson and Lindenstrauss (see Lemma 1 in [J-L]), which states that (1) holds for X = `2 , provided n > C −2 logN (C numerical constant). Also, the same statement can be easily deduced from Theorem 1 in [J-S 1] for X = `p , 1 ≤ p C( , p) logN. In a recent paper by Bastero, Bernues and Kalton [B-B-K] the following result is proven: “There exists a numerical constant C > 0 such that (1) holds for every 1-subsymmetric n-dimensional normed space X, provided n > C −2 logN ”. Also, it is shown that estimates of the type n ≥ C( ) logN are asymptotically in n and N the best possible. It is worth noting that one actually achieves an embedding of the `∞ -cube into the ` N p -cube, with N ' C −2n. This result is an improvement on the one given by [B-M-W] where an embedding of order N ' C( , p)n is obtained. Unfortunately the method developed in that paper cannot be extended to a wider class of spaces (even to 2-symmetric spaces). We will present here some extensions to the result in [B-B-K]. The key will be deviation inequalities by M.Talagrand, W.Johnson and Schechtman ([T], Theorem 3 and [J-S 2], Corollary 4) and by V.Milman and G.Schechtman ([M-S], Ch.7). We will obtain good estimates for (1) for the 1-unconditional space `p (` m q ), 1 ≤ p, q < ∞ the study of which was suggested to us by N. Kalton as the first step beyond the 1-subsymmetric case, for cotype-2 spaces and for some K-symmetric spaces. In the cases considered the method gives the correct relation between n and N i.e. n ≥ C( ) logN , but in the `p case it produces a dependence on worse than C −2. This can be solved, in a different way than in [B-B-K], by using a sharp deviation inequality (6) for the convex function ||.||p. Notation. For i = 1, ..., n let (Xi, ||.||i) be normed spaces, let Ωi be a finite subset of Xi and let IP i be any probability measure on Ωi. Define (Ω,dp, IP ) as Ω = ∏n 1 Ωi, dp the distance induced on Ω by the norm in X = ( ∑n 1 ⊕ Xi)p , 1 ≤ p ≤ ∞ and IP = ∏n 1 IP i the product probability. x, x ′ will denote elements in X and η, η′ elements in Ω. In case (Xi, ||.||i) = (IR, |.|), we will denote, as usual, (X,dp) = (`p , ||.||p). Given a function f : Ω→ IR, we denote by Mf its median, by σp(f) = σp its Lipschitz constant σp = sup η 6=η′ |f(η)− f(η′)| dp(η, η′) and by ω f (δ) its modulus of continuity ω p f (δ) = sup dp(η,η′)≤δ |f(η)− f(η′)|.