11
$\begingroup$

Given two symmetric convex bodies $B, B'$ in ${\bf R}^d$, define the Banach-Mazur distance $d(B,B')$ between them to be the least constant $\tau \geq 1$ such that $$ B \subset TB' \subset \tau B$$ for some invertible linear transformation $T: {\bf R}^d \to {\bf R}^d$. (One should work with $\log \tau$ instead of $\tau$ if one wants this distance to actually be a (pseudo-)metric, but it seems more conventional to use $\tau$ in this subject.)

John's theorem for symmetric convex bodies is equivalent to the assertion that every symmetric convex body is within $\sqrt{d}$ of the Euclidean unit ball $B_{\ell^2}$. The bound of $\sqrt{d}$ is best possible, as can be seen by considering the unit cube. Thus, we get an extremely structured approximation to any symmetric convex body - namely, the Euclidean ball - at the cost of a somewhat weak bound ($\sqrt{d}$) on the accuracy of the approximation in Banach-Mazur distance.

I am interested in results that improve the accuracy of approximation, at the cost of weakening the structure of the approximant. An example of the type of result I have in mind is in

Barvinok, Alexander, Thrifty approximations of convex bodies by polytopes, Int. Math. Res. Not. 2014, No. 16, 4341-4356 (2014). ZBL1300.52007.

in which it is shown for instance that an arbitrary convex body can be approximated to error $\varepsilon \sqrt{d}$ in Banach-Mazur distance by a polytope with a polynomial number of vertices (roughly $d^{1/\varepsilon}$), or to error $1+\varepsilon$ with an exponential number of vertices (roughly $\varepsilon^{-d/2}$), as well as various interpolations between these two results.

My question is: are there other interesting classes of convex bodies (e.g., zonotopes) than just the unit ball (or ellipsoids) for which one has a John-type theorem with a significantly better approximation than $\sqrt{d}$? For instance, what if instead of approximating by a unit ball, one wishes to approximate by a convex body $B'$ that is only an epsilon away in measure from being a unit ball, in the sense that $$ \mathrm{vol}(B' \Delta B_{\ell^2}) \leq \varepsilon \mathrm{vol}(B_{\ell^2}):$$ can one significantly reduce the loss of $\sqrt{d}$ if one does this?

Alternatively, what if one is willing to pass to a reasonably high-dimensional slice of ${\bf R}^d$, e.g., an $\varepsilon d$-dimensional slice - does one get significant improvements to the constant $\sqrt{d}$ in John's theorem in this case? Of course by Dvoretsky's theorem one will eventually get approximation arbitrarily close to 1 if one takes a low enough dimensional slice (of dimension $\log d$ or so), but I would like to keep the dimension of the slice comparable to the dimension of the whole space.

$\endgroup$
5
  • 2
    $\begingroup$ Regarding your second question : Not sure in what kind of improvement you are looking for, but a theorem by Maurey seems to indicate that looking for large-dimensional slices cannot very significantly (more than up to log factors) improve John's theorem: every subspace of $\ell_\infty^n$ of dimension $d$ is at Banach-Mazur distance $\geq C \sqrt{\frac{d}{\log n}}$ from a Euclidean space. In fact, this is even a lower bound on the type 2 constant of the dual, which is an obvious upper bound on the Banach-Mazur distance. $\endgroup$ Commented Sep 14, 2023 at 1:38
  • $\begingroup$ See Theorem 3 for $p=2$ in Pisier's Remarques sur un résultat non publié de B. Maurey numdam.org/item/?id=SAF_1980-1981____A5_0 $\endgroup$ Commented Sep 14, 2023 at 1:38
  • $\begingroup$ Of course, there quite some room between $\sqrt{d}$ and $\sqrt{d/\log d}$, so this does not really answer your question. $\endgroup$ Commented Sep 14, 2023 at 1:48
  • 2
    $\begingroup$ On the other hand, Milman's QS-Theorem gives a very significant improvement on John's theorem if you allow not only slices, but also projections, see en.wikipedia.org/wiki/Quotient_of_subspace_theorem $\endgroup$ Commented Sep 14, 2023 at 15:18
  • 2
    $\begingroup$ Since you mention zonoids, here is an approximation result for them: any n -dimensional zonoid can be approximated with Banch-Mazur distance ⩽1+ϵ by the Minkowski sum of N=O(nlogn/ϵ2) segments. See M. Talagrand, Embedding subspaces of L_1 into l_1^N, Proc. AMS (1990), cf jstor.org/stable/2048283 $\endgroup$ Commented Sep 19, 2023 at 11:26

0

You must log in to answer this question.

Browse other questions tagged .