The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite (Q2380779): Difference between revisions

To solve a problem about Lipschitz extensions, \textit{W.\,Johnson} and \textit{J.\,Lindenstrauss} [``Extensions of Lipschitz mappings into a Hilbert space,'' Contemp.\ Math.\ 26, 189--206 (1984; Zbl 0539.46017)] proved that every Hilbert space \(X = H\) has the following property: \((JL)\)\quad For every \(K, D > 1\), \(n \geq 1\), \(x_1, \dots, x_n \in X\), there exist a linear subspace \(F \subseteq X\) with \(\dim F \leq K\, \log n\) and a linear map \(L \colon X \to F\) such that \[ \| x_i - x_j\| \leq \| L (x_i) - L (x_j)\| \leq D\,\|x_i - x_j\|\text{ for all }i,j = 1, \dots, n. \] It has appeared, in the course of the past ten years, that this result has important applications, not only in geometry of Banach spaces, but also in computer science. In the present paper, the authors show that, if \(X\) is a Banach space satisfying \((JL)\), then the Banach-Mazur distance \(d_E\) of every \(n\)-dimensional subspace \(E\) of \(X\) to \(\ell_2^n\) is less than \(2^{2^{c \log^\ast \! n}}\), where \(c = c (D, K)\) and \(\log^\ast \! x\) is the unique integer \(l\) such that \(a_l < x \leq a_{l + 1}\), with \(a_1 = 1\) and \(a_{j + 1} = {\text{ e}}^{a_j}\). The proof uses Kwapień's theorem and, more precisely, the fact that \(d_F \leq T_2 (F)\, C_2 (F)\), where \(T_2 (F)\) and \(C_2 (F)\) are the Gaussian type \(2\) and Gaussian cotype \(2\) constants of \(F\subseteq X\). The authors then use the fact that, if \(\dim F = k\), these constants can be computed with at most \(k(k + 1)/2\) vectors and a random procedure to get an upper bound for \(T_2 (F)\) and \(C_2 (F)\). In fact, if \(\Delta (n) = \sup\{d_E:E \subseteq X\) and \(\dim E \leq n\}\), then this upper bound is \(2D\Delta \big(4 K \log (k + 1)\big)\), and one gets the recursive inequality \(\Delta (n) \leq 4D^2 [\Delta \big(4 K \log (n + 1)\big)]^2\), which gives, by iteration, the claimed result \(\Delta (n) \leq 2^{2^{c \log^\ast \! n}}\). Since \(\Delta (n) = o\, (\log n)\), it follows, by a result of \textit{G.\,Pisier} [``Martingales with values in uniformly convex spaces,'' Isr.\ J.\ Math.\ 20, 326--350 (1975; Zbl 0344.46030)] that every Banach space satisfying \((JL)\) is superreflexive. On the other hand, the authors show that the \(2\)-convexified Tsirelson space \(T^{(2)}\) satisfies \((JL)\), though it is far from the Hilbert space: for every \(n \geq 1\), there is an \(n\)-dimensional subspace \(F_n\) of \(T^{(2)}\) such that \(d_{F_n} \geq 2^{c \alpha (n)}\), where \(c > 0\) is a universal constant and \(\alpha (n) \to \infty\) (actually, \(\alpha\) is well determined: it is the so-called inverse Ackerman function). The paper ends with several remarks and open questions.