Advanced Search

We prove that there exist constants C>0 and 0 < λ < 1 so that for all convex bodies K in ${ℝ}^n$ with non-empty interior and all integers k so that 1 ≤ k ≤ λn/ln(n+1), there exists a k-dimensional affine subspace Y of ${ℝ}^n$ satisfying $d(Y\cap K,B_2^k)\le C(1+\surd (k/ln(n/\left(kln(n+1)\right)))$. This formulation of Dvoretzky’s theorem for large dimensional sections is a generalization with a new proof of the result due to Milman and Schechtman for centrally symmetric convex bodies. A sharper estimate holds for the n-dimensional simplex.

We show that, given an n-dimensional normed space X, a sequence of $N={(8/\epsilon )}^{2n}$ independent random vectors ${\left(X_i\right)}_{i=1}^N$, uniformly distributed in the unit ball of X*, with high probability forms an ε-net for this unit ball. Thus the random linear map $\Gamma :ℝ\to {ℝ}^N$ defined by $\Gamma x={(⟨x,X_i⟩)}_{i=1}^N$ embeds X in ${\ell }_{\infty }^N$ with at most 1 + ε norm distortion. In the case X = ℓ₂ⁿ we obtain a random 1+ε-embedding into ${\ell }_{\infty }^N$ with asymptotically best possible relation between N, n, and ε.