On approximation by projections of polytopes with few facets (Q476495)

The following problem on approximation by projections of polytopes was posed by \textit{A. Barvinok} and \textit{E. Veomett} [Contemp. Math. 453, 117--137 (2008; Zbl 1145.52002)]. Problem: Let \(K\subset\mathbb{R}^n\) be a symmetric convex body and let \(P\subset\mathbb{R}^n\) be a projection of a polytope with \(N\) facets, which approximates \(K\) within a factor of 2. Is it true that in the worst case the number \(N\) should be at least exponential in \(d:N\geq e^{cn}\) for some absolute constant \(c>1\)? In this paper, the authors provide an affirmative solution to this problem by showing that in general an \(n\)-dimensional convex body cannot be approximated by a projection of a section of a simplex of subexponential dimension. They give a lower estimate for the minimal Banach-Mazur distance between a certain convex symmetric body and a projection of a polytope with \(N\) facets. This estimate is optimal for all \(N>n\) up to logarithmic terms. Main result: Let \(1\leq n\leq N\). There exists an \(n\)-dimensional convex symmetric body \(B\), such that for every \(n\)-dimensional convex body \(K\) obtained as a projection of a section of an \(N\)-dimensional simplex one has \[ d(B,K)\geq c\sqrt{{n\over \ln{2N\ln(2N)\over n}}}, \] where \(d(\cdot,\cdot)\) denotes the Banach-Mazur distance and \(c\) is an absolute positive constant.