Explicit Euclidean Embeddings in Permutation Invariant Normed Spaces

Abstract

Let $(X,\Vert \cdot \Vert )$ be a real normed space of dimension $N\in \mathbb{N}$ with a basis $(e_i{)}_1^N$ such that the norm is invariant under coordinate permutations. Assume for simplicity that the basis constant is at most $2$. Consider any $n\in \mathbb{N}$ and $0<\epsilon <1/4$ such that $n\le c(\log {\epsilon }^{-1}{)}^{-1}\log N$. We provide an explicit construction of a matrix that generates a $(1+\epsilon )$ embedding of ${\ell }_2^n$ into $X$.

14 pages