An average John theorem

Naor, Assaf¹

¹ Department of Mathematics, Princeton University, Princeton, NJ, United States

Geometry & topology, Tome 25 (2021) no. 4, pp. 1631-1717.

Résumé

We prove that the $\frac{1}{2}$–snowflake of any finite-dimensional normed space $X$ embeds into a Hilbert space with quadratic average distortion

We deduce from this (optimal) statement that if an $n$–vertex expander embeds with average distortion $D\ge 1$ into $X$, then necessarily $dim\left(X\right)\ge n^{\Omega \left(1∕D\right)}$, which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound $dim\left(X\right)\gtrsim {\left(logn\right)}^2∕D^2$ of Linial, London and Rabinovich (1995), strengthens a theorem of Matoušek (1996) which resolved questions of Johnson and Lindenstrauss (1982), Bourgain (1985) and Arias-de-Reyna and Rodríguez-Piazza (1992), and answers negatively a question that was posed (for algorithmic purposes) by Andoni, Nguyen, Nikolov, Razenshteyn and Waingarten (2016).

Détail

DOI : 10.2140/gt.2021.25.1631

Classification : 30L05
Keywords: metric embeddings, dimension reduction, expander graphs, nonlinear spectral gaps, Markov type

Bibliographie

[1] I Abraham, Y Bartal, O Neiman, Advances in metric embedding theory, Adv. Math. 228 (2011) 3026 | DOI

[2] F Albiac, F Baudier, Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces Lp and lp for 0 p ∞, J. Geom. Anal. 25 (2015) 1 | DOI

[3] N Alon, The diameter of SLn(Fq), preprint (2019)

[4] N Alon, P Frankl, V Rödl, Geometrical realization of set systems and probabilistic communication complexity, from: "26th Annual Symposium on Foundations of Computer Science", IEEE (1985) 277 | DOI

[5] N Alon, Y Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994) 271 | DOI

[6] N Alon, J H Spencer, The probabilistic method, Wiley (1992)

[7] A Andoni, P Indyk, I Razenshteyn, Approximate nearest neighbor search in high dimensions, from: "Proceedings of the International Congress of Mathematicians, IV" (editors B Sirakov, P N de Souza, M Viana), World Sci. (2018) 3287

[8] A Andoni, A Naor, O Neiman, Snowflake universality of Wasserstein spaces, Ann. Sci. École Norm. Sup. 51 (2018) 657 | DOI

[9] A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Complex interpolation, Hölder homeomorphisms, and algorithmic applications, in preparation

[10] A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Spectral partitioning of metric spaces, in preparation

[11] A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Data-dependent hashing via nonlinear spectral gaps, from: "Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing" (editors I Diakonikolas, D Kempe, M Henzinger), ACM (2018) 787 | DOI

[12] A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten, Hölder homeomorphisms and approximate nearest neighbors, from: "59th Annual IEEE Symposium on Foundations of Computer Science" (editor M Thorup), IEEE (2018) 159 | DOI

[13] A Andoni, H L Nguyen, A Nikolov, I Razenshteyn, E Waingarten, Approximate near neighbors for general symmetric norms, from: "Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing" (editors H Hatami, P McKenzie, V King), ACM (2017) 902 | DOI

[14] D Andrén, L Hellström, K Markström, On the complexity of matrix reduction over finite fields, Adv. Appl. Math. 39 (2007) 428 | DOI

[15] J Arias-De-Reyna, L Rodríguez-Piazza, Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces, Israel J. Math. 79 (1992) 103 | DOI

[16] N Aronszajn, Differentiability of Lipschitzian mappings between Banach spaces, Studia Math. 57 (1976) 147 | DOI

[17] T Austin, A Naor, A Valette, The Euclidean distortion of the lamplighter group, Discrete Comput. Geom. 44 (2010) 55 | DOI

[18] U Bader, A Furman, T Gelander, N Monod, Property (T) and rigidity for actions on Banach spaces, Acta Math. 198 (2007) 57 | DOI

[19] K Ball, Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal. 2 (1992) 137 | DOI

[20] K Ball, The Ribe programme, from: "Séminaire Bourbaki, 2011/2012", Astérisque 352, Soc. Math. France (2013) 147

[21] K Ball, E A Carlen, E H Lieb, Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math. 115 (1994) 463 | DOI

[22] S Banach, Théorie des opérations linéaires, 1, Inst. Mat. Polish Acad. Sci. (1932)

[23] Y Bartal, N Linial, M Mendel, A Naor, On metric Ramsey-type phenomena, Ann. of Math. 162 (2005) 643 | DOI

[24] S Bates, W B Johnson, J Lindenstrauss, D Preiss, G Schechtman, Affine approximation of Lipschitz functions and nonlinear quotients, Geom. Funct. Anal. 9 (1999) 1092 | DOI

[25] F P Baudier, Quantitative nonlinear embeddings into Lebesgue sequence spaces, J. Topol. Anal. 8 (2016) 117 | DOI

[26] Y Benyamini, J Lindenstrauss, Geometric nonlinear functional analysis, I, 48, Amer. Math. Soc. (2000) | DOI

[27] J Bergh, J Löfström, Interpolation spaces: an introduction, 223, Springer (1976) | DOI

[28] J Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (1985) 46 | DOI

[29] J Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. 56 (1986) 222 | DOI

[30] J Bourgain, V Milman, H Wolfson, On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986) 295 | DOI

[31] J Bretagnolle, D Dacunha-Castelle, J L Krivine, Fonctions de type positif sur les espaces Lp, C. R. Acad. Sci. Paris 261 (1965) 2153

[32] A Brudnyi, Y Brudnyi, Methods of geometric analysis in extension and trace problems, II, 103, Birkhäuser (2012) | DOI

[33] Y Brudnyi, P Shvartsman, Stability of the Lipschitz extension property under metric transforms, Geom. Funct. Anal. 12 (2002) 73 | DOI

[34] A P Calderón, Intermediate spaces and interpolation, the complex method, Studia Math. 24 (1964) 113 | DOI

[35] F Chaatit, On uniform homeomorphisms of the unit spheres of certain Banach lattices, Pacific J. Math. 168 (1995) 11 | DOI

[36] J Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, from: "Problems in analysis" (editor R C Gunning), Princeton Univ. Press (1970) 195 | DOI

[37] Q Cheng, Sphere equivalence, property H, and Banach expanders, Studia Math. 233 (2016) 67 | DOI

[38] 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 (1973) 29

[39] F R K Chung, Laplacians of graphs and Cheeger’s inequalities, from: "Combinatorics : Paul Erdős is eighty, II" (editors D Miklós, V T Sós, T Szőnyi), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc. (1996) 157

[40] J A Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936) 396 | DOI

[41] M Cwikel, Complex interpolation spaces, a discrete definition and reiteration, Indiana Univ. Math. J. 27 (1978) 1005 | DOI

[42] M Cwikel, S Reisner, Interpolation of uniformly convex Banach spaces, Proc. Amer. Math. Soc. 84 (1982) 555 | DOI

[43] M Daher, Homéomorphismes uniformes entre les sphères unité des espaces d’interpolation, Canad. Math. Bull. 38 (1995) 286 | DOI

[44] G David, S Semmes, Fractured fractals and broken dreams, 7, Oxford Univ. Press (1997)

[45] M M Day, Uniform convexity in factor and conjugate spaces, Ann. of Math. 45 (1944) 375 | DOI

[46] P Enflo, On the nonexistence of uniform homeomorphisms between Lp–spaces, Ark. Mat. 8 (1969) 103 | DOI

[47] P Enflo, Banach spaces which can be given an equivalent uniformly convex norm, Israel J. Math. 13 (1972) 281 | DOI

[48] P Enflo, Uniform homeomorphisms between Banach spaces, from: "Séminaire Maurey–Schwartz, 1975/1976 : Espaces, , applications radonifiantes et géométrie des espaces de Banach", Cent. Math. École Polytech. (1976)

[49] A Eskenazis, A Naor, On coarse and uniform embeddings into Lp, in preparation

[50] T Figiel, On the moduli of convexity and smoothness, Studia Math. 56 (1976) 121 | DOI

[51] T Figiel, G Pisier, Séries aléatoires dans les espaces uniformément convexes ou uniformément lisses, C. R. Acad. Sci. Paris Sér. A 279 (1974) 611

[52] M Fréchet, Sur quelques points du calcul fonctionnel, Rend. Circ. Mat. Palermo 22 (1906) 1 | DOI

[53] I Gelfand, Abstrakte Funktionen und lineare Operatoren, Mat. Sb. 4 (1938) 235

[54] R I Grigorchuk, P W Nowak, Diameters, distortion, and eigenvalues, European J. Combin. 33 (2012) 1574 | DOI

[55] M Gromov, Spaces and questions, from: "Visions in Mathematics: GAFA 2000, I" (editors N Alon, J Bourgain, A Connes, M Gromov, V Milman) (2000) 118 | DOI

[56] M Gromov, Random walk in random groups, Geom. Funct. Anal. 13 (2003) 73 | DOI

[57] J L Gross, Every connected regular graph of even degree is a Schreier coset graph, J. Combinatorial Theory Ser. B 22 (1977) 227 | DOI

[58] O Hanner, On the uniform convexity of Lp and lp, Ark. Mat. 3 (1956) 239 | DOI

[59] A Hatcher, Algebraic topology, Cambridge Univ. Press (2002)

[60] J Heinonen, Lectures on analysis on metric spaces, Springer (2001) | DOI

[61] S Heinrich, Ultraproducts in Banach space theory, J. Reine Angew. Math. 313 (1980) 72 | DOI

[62] M Herman, J Pakianathan, On the distribution of distances in homogeneous compact metric spaces, Topology Appl. 193 (2015) 97 | DOI

[63] S Hoory, N Linial, A Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006) 439 | DOI

[64] H Izeki, S Nayatani, Combinatorial harmonic maps and discrete-group actions on Hadamard spaces, Geom. Dedicata 114 (2005) 147 | DOI

[65] R C James, Super-reflexive Banach spaces, Canad. J. Math. 24 (1972) 896 | DOI

[66] F John, Extremum problems with inequalities as subsidiary conditions, from: "Studies and essays presented to R Courant on his 60th birthday" (editor K O Friedrichs), Interscience (1948) 187

[67] W B Johnson, J Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, from: "Conference in modern analysis and probability" (editors R Beals, A Beck, A Bellow, A Hajian), Contemp. Math. 26, Amer. Math. Soc. (1984) 189 | DOI

[68] W B Johnson, J Lindenstrauss, Basic concepts in the geometry of Banach spaces, from: "Handbook of the geometry of Banach spaces, I" (editors W B Johnson, J Lindenstrauss), North-Holland (2001) 1 | DOI

[69] W B Johnson, J Lindenstrauss, G Schechtman, On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces, from: "Geometrical aspects of functional analysis" (editors J Lindenstrauss, V D Milman), Lecture Notes in Math. 1267, Springer (1987) 177 | DOI

[70] P N Jolissaint, A Valette, Lp–distortion and p–spectral gap of finite graphs, Bull. Lond. Math. Soc. 46 (2014) 329 | DOI

[71] N J Kalton, The nonlinear geometry of Banach spaces, Rev. Mat. Complut. 21 (2008) 7 | DOI

[72] M Kassabov, Kazhdan constants for SLn(Z), Int. J. Algebra Comput. 15 (2005) 971 | DOI

[73] S Khot, A Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006) 821 | DOI

[74] M D Kirszbraun, Über die zusammenziehenden und Lipschitzchen Transformationen, Fund. Math. 22 (1934) 77 | DOI

[75] T Kondo, CAT(0) spaces and expanders, Math. Z. 271 (2012) 343 | DOI

[76] T J Laakso, Plane with A∞–weighted metric not bi-Lipschitz embeddable to RN, Bull. Lond. Math. Soc. 34 (2002) 667 | DOI

[77] T De Laat, M De La Salle, Banach space actions and L2–spectral gap, Anal. PDE 14 (2021) 45 | DOI

[78] V Lafforgue, Un renforcement de la propriété (T), Duke Math. J. 143 (2008) 559 | DOI

[79] V Lafforgue, Propriété (T) renforcée banachique et transformation de Fourier rapide, J. Topol. Anal. 1 (2009) 191 | DOI

[80] J R Lee, A Naor, Extending Lipschitz functions via random metric partitions, Invent. Math. 160 (2005) 59 | DOI

[81] J Lindenstrauss, On the modulus of smoothness and divergent series in Banach spaces, Michigan Math. J. 10 (1963) 241 | DOI

[82] J Lindenstrauss, L Tzafriri, Classical Banach spaces, I : Sequence spaces, 92, Springer (1977)

[83] J Lindenstrauss, L Tzafriri, Classical Banach spaces, II : Function spaces, 97, Springer (1979)

[84] N Linial, E London, Y Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995) 215 | DOI

[85] N Linial, A Magen, Least-distortion Euclidean embeddings of graphs : products of cycles and expanders, J. Combin. Theory Ser. B 79 (2000) 157 | DOI

[86] N Linial, A Magen, A Naor, Girth and Euclidean distortion, Geom. Funct. Anal. 12 (2002) 380 | DOI

[87] J L Lions, Une construction d’espaces d’interpolation, C. R. Acad. Sci. Paris 251 (1960) 1853

[88] P Mankiewicz, On Lipschitz mappings between Fréchet spaces, Studia Math. 41 (1972) 225 | DOI

[89] J Matoušek, Extension of Lipschitz mappings on metric trees, Comment. Math. Univ. Carolin. 31 (1990) 99

[90] J Matoušek, Note on bi-Lipschitz embeddings into normed spaces, Comment. Math. Univ. Carolin. 33 (1992) 51

[91] J Matoušek, On the distortion required for embedding finite metric spaces into normed spaces, Israel J. Math. 93 (1996) 333 | DOI

[92] J Matoušek, On embedding expanders into lp spaces, Israel J. Math. 102 (1997) 189 | DOI

[93] J Matoušek, Lectures on discrete geometry, 212, Springer (2002) | DOI

[94] S Mazur, Une remarque sur l’homéomorphie des champs fonctionels, Studia Math. 1 (1929) 83 | DOI

[95] M Mendel, A Naor, Euclidean quotients of finite metric spaces, Adv. Math. 189 (2004) 451 | DOI

[96] M Mendel, A Naor, Metric cotype, Ann. of Math. 168 (2008) 247 | DOI

[97] M Mendel, A Naor, Markov convexity and local rigidity of distorted metrics, J. Eur. Math. Soc. 15 (2013) 287 | DOI

[98] M Mendel, A Naor, Spectral calculus and Lipschitz extension for barycentric metric spaces, Anal. Geom. Metr. Spaces 1 (2013) 163 | DOI

[99] M Mendel, A Naor, Nonlinear spectral calculus and super-expanders, Publ. Math. Inst. Hautes Études Sci. 119 (2014) 1 | DOI

[100] M Mendel, A Naor, Expanders with respect to Hadamard spaces and random graphs, Duke Math. J. 164 (2015) 1471 | DOI

[101] D Milman, On some criteria for the regularity of spaces of the type (B), C. R. (Dokl.) Acad. Sci. URSS 20 (1938) 243

[102] J Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964) 275 | DOI

[103] M Mimura, Sphere equivalence, Banach expanders, and extrapolation, Int. Math. Res. Not. 2015 (2015) 4372 | DOI

[104] G J Minty, On the extension of Lipschitz, Lipschitz–Hölder continuous, and monotone functions, Bull. Amer. Math. Soc. 76 (1970) 334 | DOI

[105] A Naor, An introduction to the Ribe program, Japan. J. Math. 7 (2012) 167 | DOI

[106] A Naor, On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon–Roichman graphs, Combin. Probab. Comput. 21 (2012) 623 | DOI

[107] A Naor, Comparison of metric spectral gaps, Anal. Geom. Metr. Spaces 2 (2014) 1

[108] A Naor, Uniform nonextendability from nets, C. R. Math. Acad. Sci. Paris 353 (2015) 991 | DOI

[109] A Naor, Discrete Riesz transforms and sharp metric Xp inequalities, Ann. of Math. 184 (2016) 991 | DOI

[110] A Naor, A spectral gap precludes low-dimensional embeddings, from: "33rd International Symposium on Computational Geometry" (editors B Aronov, M J Katz), Leibniz Int. Proc. Inform. 77, Schloss Dagstuhl (2017) | DOI

[111] A Naor, Metric dimension reduction : a snapshot of the Ribe program, from: "Proceedings of the International Congress of Mathematicians, I" (editors B Sirakov, P N de Souza, M Viana), World Sci. (2018) 759

[112] A Naor, Y Peres, O Schramm, S Sheffield, Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces, Duke Math. J. 134 (2006) 165 | DOI

[113] A Naor, Y Rabani, On Lipschitz extension from finite subsets, Israel J. Math. 219 (2017) 115 | DOI

[114] A Naor, Y Rabani, A Sinclair, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, J. Funct. Anal. 227 (2005) 273 | DOI

[115] A Naor, G Schechtman, Metric Xp inequalities, Forum Math. Pi 4 (2016) | DOI

[116] A Naor, L Silberman, Poincaré inequalities, embeddings, and wild groups, Compos. Math. 147 (2011) 1546 | DOI

[117] I Newman, Y Rabinovich, Hard metrics from Cayley graphs of abelian groups, Theory Comput. 5 (2009) 125 | DOI

[118] E Odell, T Schlumprecht, The distortion problem, Acta Math. 173 (1994) 259 | DOI

[119] M I Ostrovskii, Metric embeddings: bilipschitz and coarse embeddings into Banach spaces, 49, de Gruyter (2013) | DOI

[120] N Ozawa, A note on non-amenability of B(lp) for p = 1,2, Int. J. Math. 15 (2004) 557 | DOI

[121] B J Pettis, A proof that every uniformly convex space is reflexive, Duke Math. J. 5 (1939) 249 | DOI

[122] G Pisier, Martingales with values in uniformly convex spaces, Israel J. Math. 20 (1975) 326 | DOI

[123] G Pisier, Some applications of the complex interpolation method to Banach lattices, J. Analyse Math. 35 (1979) 264 | DOI

[124] G Pisier, Complex interpolation between Hilbert, Banach and operator spaces, 978, Amer. Math. Soc. (2010) | DOI

[125] Y Rabinovich, On average distortion of embedding metrics into the line, Discrete Comput. Geom. 39 (2008) 720 | DOI

[126] Y Raynaud, On ultrapowers of non commutative Lp spaces, J. Operator Theory 48 (2002) 41

[127] M Ribe, On uniformly homeomorphic normed spaces, Ark. Mat. 14 (1976) 237 | DOI

[128] É Ricard, Hölder estimates for the noncommutative Mazur maps, Arch. Math. (Basel) 104 (2015) 37 | DOI

[129] M Riesz, Sur les maxima des formes bilinéaires et sur les fonctionnelles linéaires, Acta Math. 49 (1927) 465 | DOI

[130] T R Riley, Navigating in the Cayley graphs of SLN(Z) and SLN(Fp), Geom. Dedicata 113 (2005) 215 | DOI

[131] I J Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938) 522 | DOI

[132] E M Stein, Interpolation of linear operators, Trans. Amer. Math. Soc. 83 (1956) 482 | DOI

[133] R Thom, Sur l’homologie des variétés algébriques réelles, from: "Differential and combinatorial topology" (editor S S Cairns), Princeton Univ. Press (1965) 255 | DOI

[134] G O Thorin, Convexity theorems generalizing those of M Riesz and Hadamard with some applications, Comm. Sém. Math. Univ. Lund 9 (1948) 1

[135] J H Wells, L R Williams, Embeddings and extensions in analysis, 84, Springer (1975) | DOI