This is an announcement for the paper "The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite" by William B. Johnson and Assaf Naor.

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,\ldots,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 $|x_i-x_j|\le|L(x_i)-L(x_j)|\le O(1)\cdot|x_i-x_j|$ for all $i,j\in {1,\ldots, 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^*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.

Archive classification: math.FA math.MG

The source file(s), JL-L3.1.TEX: 43297 bytes, is(are) stored in gzipped form as 0807.1919.gz with size 14kb. The corresponding postcript file has gzipped size 74kb.

Submitted from: naor@cims.nyu.edu

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/0807.1919

or

http://arXiv.org/abs/0807.1919

or by email in unzipped form by transmitting an empty message with subject line

uget 0807.1919

or in gzipped form by using subject line

get 0807.1919

to: math@arXiv.org.