Very tight embeddings of subspaces of \(L_p\), \(1 \leq p < 2\), into \(\ell^n_p\) (Q1413656)

The problem of the existence of bounded-distortion linear embeddings of \(l_q^d\) into low-di\-men\-sional \(l_p^n\) (low-dimensionality means that \(n\) is not much larger than \(d\)) is one of the basic problems of Banach space theory [see \textit{W. B.~Johnson} and \textit{G.~Schechtman}, ``Finite dimensional subspaces of \(L_p\)'', in: Handbook of the geometry of Banach spaces, Vol. I, 837--870 (2001; Zbl 1012.46012), for a survey]. This problem is also of importance for Computer Science [see, e.g., \textit{P.~Indyk}, Algorithmic applications of low-distortion geometric embeddings, 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 10--33 (2001)]. The main result of the paper under review is a further significant progress on this problem, in the case when the distortion is allowed to be `large'. The authors strengthen an estimate of \textit{A.~Naor} and \textit{A.~Zvavitch} [Isr. J. Math. 122, 371--380 (2001; Zbl 1027.46010)] to a result whose form is close to the form of the well-known result of \textit{B. S.~Kashin} [Izv. Akad. Nauk SSSR, Ser. Mat. 41, 334--351 (1977; Zbl 0354.46021)] (Kashin considered the case \(q=2\)). Main Result. For every \(1\leq p<q\leq 2\) and every \(\mu>1\), there is a constant \(K=K(p,q, \mu)\) such that if \(X\) is a \(d\)-dimensional subspace of \(L_q\), then \(X\) \(K\)-embeds into \(l_p^n\) for \(n=[\mu d]\). The paper also contains information about general subspaces of \(L_p\) (Theorem 2).