17
$\begingroup$

Question: Does there exist a function $C:~(0,1)\to (0,\infty)$ such that for each $\varepsilon\in(0,1)$ every Banach space $X$ of dimension $\ge C(\varepsilon)\log n$ contains an $n$-point set $\{x_i\}_{i=1}^{n}$ such that $1-\varepsilon\le ||x_i-x_j||\le 1+\varepsilon$ for $i\ne j$?

The Johnson-Lindenstrauss lemma contains a proof of existence of such function if the class of Banach spaces is restricted to finite dimensional Hilbert spaces. The existence of such function for $\{\ell_p^n\}_{n=1,~1\le p\le\infty}^{\infty}$, was proved using some basic facts of coding theory by Bartal, Linial, Mendel, and Naor [Eur. J. Comb. 25, No. 1, 87-92 (2004; Zbl 1042.54020)]

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ One approach would be to take $n$ random vectors of norm $c$ for some $c$ depending on the space (like $2^{1/p-1}$ for $l^p$, I think). If the distribution of the distance between two random such vectors is clustered tightly around $1$, you win. So one question to ask is whether this is clustered tightly for all Banach spaces or not. $\endgroup$
    – Will Sawin
    Commented Nov 26, 2014 at 18:42
  • 3
    $\begingroup$ @Will Sawin That will work just beautifully in every strictly convex space with known modulus of convexity, so out of all examples mentioned only $\ell_1$ and $\ell_\infty$ are nontrivial. However, $\ell^\infty$ is also nice probabilistically (a noticeable portion of coordinates in the difference is nearly maximal by the law of large numbers), so $\ell_1$ looks like the only not totally trivial case among all mentioned so far. $\endgroup$
    – fedja
    Commented Nov 27, 2014 at 0:24
  • $\begingroup$ @fedja (1) No probability is needed for $\ell_\infty$ - just consider $\pm 1$ vectors. (2) I think that you need a uniform bound for the modulus of convexity to get the proof (otherwise you get proof for all finite-dimensional spaces by approximation). (3) There is no such uniform bound for $\ell_p$ as $p\downarrow 1$ or $p\to\infty$. $\endgroup$
    – Mikhail Ostrovskii
    Commented Nov 27, 2014 at 1:37
  • 1
    $\begingroup$ Gideon Schechtman turned my attention to the paper of J. Arias-de-Reyna, K. Ball, and R. Villa [Mathematika 45 (1998), no. 2, 245-252], which contains relevant results and references. $\endgroup$
    – Mikhail Ostrovskii
    Commented Nov 27, 2014 at 17:35
  • 1
    $\begingroup$ That's a good one. Unfortunately, the gap between their $\sqrt 2$ and $2$ is still one half of the gap between $1$ and $2$ (which is trivial). Does anyone know if there has been any progress since then that would allow to answer the question as posed? The best I know is the work of Olivier Guedon & Co, which allows one to show an exponential concentration with $\sqrt n$ instead of $n$, i.e., guarantees $m$ points when $\dim X\ge C(\varepsilon)\log^2 m$ $\endgroup$
    – fedja
    Commented Nov 28, 2014 at 15:17

0

Reset to default

You must log in to answer this question.