Design a site like this with WordPress.com

# Approximation of a symmetric convex body by polytopes

Let $K$ be an origin-symmetric symmetric convex body in $\mathbb{R}^d$, $\varepsilon>0.$ What is the optimal upper bound for the number of vertices of the convex polytope $L$ satisfying $K\subset L\subset (1+\varepsilon)K$? Here we may consider both large $d$ and small $\varepsilon$. As far as I understand, in full generality the 2-parametric asymptotic is still open, see some recent results and a survey in the paper of Alexander Barvinok. UPDATE: Sasha Polyanskii immediately informed me about the result by Fedja Nazarov, Dima Ryabogin and Márton Naszódi where the sharp estimate is obtained.

Consider the fixed $d$ regime. Recently I asked the participants of Online IMC 2020 to prove the $O(\varepsilon^{1-d})$ bound and I found out from the discussions after the contest that the sharp order is $\varepsilon^{(1-d)/2}$. The goal of this post is to share a nice argument for that borrowed from the paper by Bronstein and Ivanov (Siberian Math. Journal 1975), and a bit simplified. The lower bound is realised already for the Euclidean sphere, it is easy (each vertex $a$ of $L$ can see only $O(\varepsilon^{(d-1)/2})$ part of $\partial K$).

First of all, we make a linear transform so that the John ellipsoid of $K$ is a unit ball $B$, now $B\subset K\subset \sqrt{d}B$. $K+\varepsilon B$ is contained in $(1+\varepsilon)K$ and thus it suffices to find $O(\varepsilon^{(1-d)/2})$ points in $K+\varepsilon B$ whose convex hull contains $K$. The idea is to use the parallel surface.

Namely, consider the boundary $\Gamma$ of the set $K+B$ and choose a minimal (by cardinality) $\sqrt{\varepsilon}$-net on $\Gamma$, denote it by $T$. We have $|T|=O(\varepsilon^{(1-d)/2})$ (since $\Gamma$ is bi-Lipschitz equivalent to the surface of the unit cube, for example). For $a\in T$ denote by $n_a$ the outer normal to $K+B$ at $x$ (it is unique, but we do not use this), that is, such a unit vector that $\langle a,n_a\rangle=\max_{K+B} \langle \cdot,n_a\rangle= \max_{K} \langle \cdot,n_a\rangle +\max_{B} \langle \cdot,n_a\rangle=\max_{K} \langle \cdot,n_a\rangle+1.$

It means that $a=x_a+n_a$, where $n_a$ is an outer normal at $x_a$ for the set $K$ (there may exist other outer normals at $x_a$). The point $f(a):=x_a+\varepsilon n_a$ belongs to $K+\varepsilon B$. Define $L={\rm conv} \{f(a):a\in T\}.$ It suffices to prove that $K\subset L$ if we assume $\varepsilon<1/4$. By convex duality, $K\subset L$ is equivalent to $\max_L \langle \cdot,n\rangle \geqslant \max_K \langle \cdot,n\rangle\quad\quad (1)$

for any unit vector $n$. For fixed $n$ let $x$ be a point on $\partial K$ such that $\langle x,n\rangle$ is maximal. We have $x+n\in \Gamma$, thus there exists $a=x_a+n_a\in T$ such that $\varepsilon\geqslant |(x+n)-(x_a+n_a)||^2=\|x-x_a\|^2+\|n-n_a\|^2+2\langle x-x_a,n\rangle+2\langle x_a -x,n_a\rangle.$

We have $\langle x-x_a,n\rangle\geqslant 0$ and $\langle x_a-x,n_a\rangle\geqslant 0$, thus $\varepsilon\geqslant \varepsilon+ 2\langle x_a-x,n\rangle \geqslant |n-n_a|^2 \geqslant 0,$

in particular $|n-n_a|\leqslant \sqrt{\varepsilon}<1/2$ since $\varepsilon<1/4$. Thus for $f(a)=x_a+\varepsilon n_a\in L$ we have $\langle f(a),n\rangle=\langle x_a+\varepsilon n_a,n\rangle=\langle x,n\rangle+\langle x_a-x,n\rangle +\varepsilon+\varepsilon\langle n_a-n,n\rangle \geqslant \langle x,n\rangle+\varepsilon/2+\varepsilon\langle n_a-n,n\rangle\geqslant \langle x,n\rangle$

and (1) for $n$ is proved.