International Mathematics Competition
for University Students
2020

IMC2020: Day 1, Problem 3

Problem 3. Let \(\displaystyle d\ge 2\) be an integer. Prove that there exists a constant \(\displaystyle C(d)\) such that the following holds: For any convex polytope \(\displaystyle K\subset \mathbb{R}^d\), which is symmetric about the origin, and any \(\displaystyle \varepsilon\in (0,1)\), there exists a convex polytope \(\displaystyle L\subset \mathbb R^d\) with at most \(\displaystyle C(d)\varepsilon^{1-d}\) vertices such that

\(\displaystyle (1-\varepsilon)K\subseteq L \subseteq K. \)

(For a real \(\displaystyle \alpha\), a set \(\displaystyle T\subset \mathbb{R}^d\) with nonempty interior is a convex polytope with at most \(\displaystyle \alpha\) vertices, if \(\displaystyle T\) is a convex hull of a set \(\displaystyle X\subset\mathbb R^d\) of at most \(\displaystyle \alpha\) points, i.e., \(\displaystyle T=\{\sum_{x\in X} t_xx\ |\ t_x\ge 0, \sum_{x\in X} t_x = 1\}\). For a real \(\displaystyle \lambda\), put \(\displaystyle \lambda K=\{\lambda x\ |\ x\in K\}\). A set \(\displaystyle T\subset \mathbb{R}^d\) is symmetric about the origin if \(\displaystyle (-1) T = T\).)

Fedor Petrov, St. Petersburg State University

Hint: Recall the ball packing density \(\displaystyle 2^{-d}\) lower estimate.

  Solution