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

Solution [in elementary terms] Let \(\displaystyle \{p_1,\ldots,p_m\}\) be an inclusion-maximal collection of points on the boundary \(\displaystyle \partial K\) of \(\displaystyle K\) such that the homothetic copies \(\displaystyle K_i:=p_i+\frac\varepsilon2 K\) have disjoint interiors. We claim that the convex hull \(\displaystyle L:=\textrm{conv}\{ p_1,\ldots,p_m \}\) satisfies all the conditions.

First, note that by convexity of \(\displaystyle K\) we have \(\displaystyle aK+bK=(a+b)K\) for \(\displaystyle a,b>0\). It follows that \(\displaystyle K_i\subset (1+\frac\varepsilon2) K\). On the other hand, if \(\displaystyle k\in K\), \(\displaystyle a>0\) and and \(\displaystyle ak\in K_i\), then

\(\displaystyle p_i\in ak-\frac\varepsilon2 K =ak+\frac\varepsilon2 K\subset(a+\frac\varepsilon2) K, \)

and since \(\displaystyle p_i\) is a boundary point of \(\displaystyle K\), we get \(\displaystyle a+\frac\varepsilon2\geqslant 1\), \(\displaystyle a\geqslant 1-\frac\varepsilon2\). It means that all \(\displaystyle K_i\) lie between \(\displaystyle (1-\frac\varepsilon2)K\) and \(\displaystyle (1+\frac\varepsilon2)K\). Since their interiors are disjoint, by the volume counting we obtain

\(\displaystyle m\left(\frac\varepsilon2\right)^d \leqslant \left(1+\frac\varepsilon2\right)^d- \left(1-\frac\varepsilon2\right)^d \leqslant (3/2)^d\varepsilon \)

(since \(\displaystyle F(\varepsilon)= (1+\frac\varepsilon2)^d-(1-\frac\varepsilon2)^d\) is a polynomial in \(\displaystyle \varepsilon\) without constant term with non-negative coefficients which sum up to \(\displaystyle (3/2)^d-(1/2)^d\)), therefore \(\displaystyle m\leqslant 3^d\varepsilon^{1-d}\).

It is clear that \(\displaystyle L\subseteq K\), so it remains to prove that \(\displaystyle (1-\varepsilon)K\subseteq L\). Assume the contrary: there exists a point \(\displaystyle p\in (1-\varepsilon)K\setminus L\). Separate \(\displaystyle p\) from \(\displaystyle L\) by a hyperplane: Choose a linear functional \(\displaystyle \ell\) such that \(\displaystyle \ell(p)>\max_{x\in L} \ell(x) =\max_i \ell(p_i)\). Choose \(\displaystyle x\in K\) such that \(\displaystyle \ell(x)=:a\) is maximal possible. Note that by our construction \(\displaystyle x+\frac\varepsilon2 K\) has a common point with some \(\displaystyle K_i\): there exists a point \(\displaystyle z\in (x+\frac\varepsilon2 K)\cap (p_i+\frac\varepsilon2 K)\). We have

\(\displaystyle \ell(p_i)+\frac\varepsilon2 a\geqslant \ell(z)\geqslant \ell(x)-\frac\varepsilon2 a, \)

and therefore \(\displaystyle \ell(p_i)\geqslant a(1-\varepsilon)\). Since \(\displaystyle p\in (1-\varepsilon)K\), we obtain \(\displaystyle \ell(p)\leqslant a(1-\varepsilon)\). A contradiction.

Solution [in the language of Banach spaces] Equip \(\displaystyle \mathbb R^d\) with the norm \(\displaystyle \|\cdot\|\), whose unit ball is \(\displaystyle K\), call this Banach space \(\displaystyle V\). Choose an inclusion maximal set \(\displaystyle X\subset\partial K\) whose pairwise distances are \(\displaystyle \ge \varepsilon\). Put \(\displaystyle L=\textrm{conv} X\).

The inclusion \(\displaystyle L \subseteq K\) follows from the convexity of \(\displaystyle K\). If the inclusion \(\displaystyle (1-\varepsilon) K \subseteq L\) fails then the Hahn–Banach theorem provides a unit linear functional \(\displaystyle \lambda\in V^*\) such that \(\displaystyle \max \{\lambda(L)\} = \max \{\lambda X\} \le 1 - \varepsilon\). Then the point \(\displaystyle x\in K\), where the maximum \(\displaystyle \max \{\lambda(K)\} = 1\) is attained (thanks to the finite dimension and compactness) is in \(\displaystyle \partial K\) and, as \(\displaystyle \lambda\) witnesses, at distance \(\displaystyle \ge \varepsilon\) from all other points of \(\displaystyle L\) and \(\displaystyle X\), contradicting the inclusion-maximality of \(\displaystyle X\).

The upper bound for the cardinality \(\displaystyle |X|\) is obtained by noting that the \(\displaystyle \varepsilon/2\) balls centered at the points of \(\displaystyle X\) are pairwise disjoint and lie in the difference of balls \(\displaystyle (1+\varepsilon/2)K\setminus (1-\varepsilon/2)K\), whose volume is \(\displaystyle \left( (1+\varepsilon/2)^d - (1-\varepsilon/2)^d \right) \textrm{vol} K\), the volume of each of the small balls being \(\displaystyle \varepsilon^d/2^d \textrm{vol} K\). Hence

\(\displaystyle |X| \le \frac{(2+\varepsilon)^d - (2-\varepsilon)^d}{\varepsilon^d} = O(\varepsilon^{1-d}). \)