Let be an origin-symmetric symmetric convex body in , What is the optimal upper bound for the number of vertices of the convex polytope satisfying ? Here we may consider both large and small . 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 regime. Recently I asked the participants of Online IMC 2020 to prove the bound and I found out from the discussions after the contest that the sharp order is . 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 of can see only part of ).

First of all, we make a linear transform so that the John ellipsoid of is a unit ball , now .

is contained in and thus it suffices to find points in whose convex hull contains . The idea is to use the *parallel surface*.

Namely, consider the boundary of the set and choose a minimal (by cardinality) -net on , denote it by . We have (since is bi-Lipschitz equivalent to the surface of the unit cube, for example). For denote by the outer normal to at (it is unique, but we do not use this), that is, such a unit vector that

It means that , where is an outer normal at for the set (there may exist other outer normals at ). The point belongs to . Define It suffices to prove that if we assume . By convex duality, is equivalent to

for any unit vector . For fixed let be a point on such that is maximal. We have , thus there exists such that

We have and , thus

in particular since . Thus for we have

and (1) for is proved.

### Like this:

Like Loading...