Euclidean embedding, randomized clustering, and Lipschitz extension for finite and doubling subsets of Lₚ when $p>2$

Read article Fix $p>2$. We prove that the Euclidean distortion of every n-point subset of Lₚ is p³(log n)12 +o(1), thus, in particular, demonstrating that all n-point subsets of Lₚ exhibit an asymptotic improvement over the O(log n) Euclidean distortion guarantee that Bourgain’s embedding theorem provides for arbitrary n-point metric spaces. We also prove that the separation modulus of every n-point subset of Lₚ is O(p² √log n), which is sharp up to the dependence on p. We deduce from (a refinement of) this asymptotic evaluation of the finitary separation modulus of Lₚ that for any n-point subset C of Lₚ , any Banach space Z, and any $1$-Lipschitz function $f:$C$, there exists a $O(p^2log n)$-Lipschitz function $F:L_p$ that extends $f$. We obtain analogous separation and extension statements for doubling subsets of $L_p$. DOI: https://doi.org/10.15781/d72xfr59