Extension, Separation and Isomorphic Reverse Isoperimetry

The Lipschitz extension modulus \mathsf{e}(\mathcal{M}) of a metric space \mathcal{M} is the infimum over those L\in [1,\infty] such that for any Banach space \mathbf{Z} and any \mathscr{C} \subseteq \mathcal{M}, any 1-Lipschitz function f:\mathscr{C} \to \mathbf{Z} can be extended to an L-Lipschitz function F:\mathcal{M}\to \mathbf{Z}. Johnson, Lindenstrauss and Schechtman proved (1986) that if \mathbf X is an n-dimensional normed space, then \mathsf{e}(\mathbf X)\lesssim n. In the reverse direction, we prove that every n-dimensional normed space \mathbf X satisfies \mathsf{e}(\mathbf X)\gtrsim n^c, where c>0 is a universal constant. Our core technical contribution is a geometric structural result on stochastic clustering of finite dimensional normed spaces which implies upper bounds on their Lipschitz extension moduli using an extension method of Lee and the author (2005). The separation modulus of a metric space (\mathcal{M},d_{\mathcal{M}}) is the infimum over those \sigma\in (0,\infty] such that for any \Delta>0 there is a distribution over random partitions of \mathcal{M} into clusters of diameter at most \Delta such that for every two points x,y\in \mathcal{M} the probability that they belong to different clusters is at most \sigma d_{\mathcal M}(x,y)/\Delta. We obtain upper and lower bounds on the separation moduli of finite dimensional normed spaces that relate them to well-studied volumetric invariants (volume ratios and projection bodies). Using these connections, we determine the asymptotic growth rate of the separation moduli of various normed spaces. If \mathbf X is an n-dimensional normed space with enough symmetries, then our bounds imply that its separation modulus is equal to \mathrm{vr}(\mathbf X^*)\sqrt{n} up to factors of lower order, where \mathrm{vr}(\mathbf X^*) is the volume ratio of the unit ball of the dual of \mathbf X. We formulate a conjecture on isomorphic reverse isoperimetric properties of symmetric convex bodies (akin to Ball's reverse isoperimetric theorem (1991), but permitting a non-isometric perturbation in addition to the choice of position) that can be used with our volumetric bounds on the separation modulus to obtain many more exact asymptotic evaluations of the separation moduli of normed spaces. Our estimates on the separation modulus imply asymptotically improved upper bounds on the Lipschitz extension moduli of various classical spaces. In particular, we deduce an improved upper bound on \mathsf{e}(\ell_p^n) when p>2 that resolves a conjecture of Brudnyi and Brudnyi (2005), and we prove that \mathsf{e}(\ell_\infty^n)\asymp{\sqrt{n}}, which is the first time that the growth rate of \mathsf{e}(\mathbf X) has been evaluated (as \dim(\mathbf X)\to \infty) for any finite dimensional normed space \mathbf X.