A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction

Abstract

Fix $0<\theta ⩽1$. We prove that if $1⩽p⩽2/\theta$, then the $\theta$-snowflake of ${\ell }_2^k$, namely, ${\mathbb{R}}^k$ equipped with the metric $((x,y)\in {\mathbb{R}}^k\times {\mathbb{R}}^k)\mapsto \Vert x-y{\Vert }_2^{\theta }$, embeds with distortion $O(1)$ into ${\ell }_p^m$ for some integer $m{\lesssim }_{p,\theta }k$, which is optimal as $k\to \infty$, as seen by comparing dimensions. However, for $p$ larger than the sharp threshold $2/\theta$ the following change in behavior occurs: If a $(1/\sqrt{k})$-dense subset of the Euclidean sphere $S^{k-1}$ embeds into ${\ell }_p^m$ with distortion $O(1)$, then necessarily $m{\gtrsim }_{p,\theta }(k/\log k{)}^{p\theta /2}$, which grows super-linearly in $k$ as $p\theta /2>1$, and this dimension bound is optimal as $k\to \infty$ up to lower order factors. We deduce from this statement that if $2<p<\infty$, then there exist arbitrarily large $n$-point subsets of ${\ell }_p$ with the property that if they embed with distortion $O(1)$ into ${\ell }_p^m$, then necessarily $m{\gtrsim }_p((\log n)/(\log \log n{)}^2{)}^{p/2}$, thus demonstrating that the statement of the Johnson--Lindenstrauss dimension reduction lemma fails to hold for ${\ell }_p$