The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite

Abstract

Let $X$ be a normed space that satisfies the Johnson-Lindenstrauss lemma (J-L lemma, in short) in the sense that for any integer $n$ and any $x_1,\dots ,x_n\in X$ there exists a linear mapping $L:X\to F$, where $F\subseteq X$ is a linear subspace of dimension $O(\log n)$, such that $\Vert x_i-x_j\Vert \le \Vert L(x_i)-L(x_j)\Vert \le O(1)\cdot \Vert x_i-x_j\Vert$ for all $i,j\in \{1,\dots ,n\}$. We show that this implies that $X$ is almost Euclidean in the following sense: Every $n$-dimensional subspace of $X$ embeds into Hilbert space with distortion $2^{2^{O({\log }^{\ast }n)}}$. On the other hand, we show that there exists a normed space $Y$ which satisfies the J-L lemma, but for every $n$ there exists an $n$-dimensional subspace $E_n\subseteq Y$ whose Euclidean distortion is at least $2^{\Omega (\alpha (n))}$, where $\alpha$ is the inverse Ackermann function.