IMC 2020 · Day 1 · P3

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

First, note that by convexity of $K$ we have $aK + bK = (a + b)K$ for $a, b > 0$. It follows that $K_i \subset (1 + \frac{\varepsilon}{2}) K$. On the other hand, if $k \in K$, $a > 0$ and and $ak \in K_i$, then $$p_i \in ak - \frac{\varepsilon}{2} K = ak + \frac{\varepsilon}{2} K \subset \Bigl( a + \frac{\varepsilon}{2} \Bigr) K,$$ and since $p_i$ is a boundary point of $K$, we get $a + \frac{\varepsilon}{2} \geqslant 1$, $a \geqslant 1 - \frac{\varepsilon}{2}$. It means that all $K_i$ lie between $(1 - \frac{\varepsilon}{2}) K$ and $(1 + \frac{\varepsilon}{2}) K$. Since their interiors are disjoint, by the volume counting we obtain $$m \left( \frac{\varepsilon}{2} \right)^d \leqslant \left( 1 + \frac{\varepsilon}{2} \right)^d - \left( 1 - \frac{\varepsilon}{2} \right)^d \leqslant (3/2)^d \varepsilon$$ (since $F(\varepsilon) = (1 + \frac{\varepsilon}{2})^d - (1 - \frac{\varepsilon}{2})^d$ is a polynomial in $\varepsilon$ without constant term with non-negative coefficients which sum up to $(3/2)^d - (1/2)^d$), therefore $m \leqslant 3^d \varepsilon^{1-d}$.

It is clear that $L \subseteq K$, so it remains to prove that $(1 - \varepsilon) K \subseteq L$. Assume the contrary: there exists a point $p \in (1 - \varepsilon) K \setminus L$. Separate $p$ from $L$ by a hyperplane: Choose a linear functional $\ell$ such that $\ell(p) > \max\limits_{x \in L} \ell(x) = \max_i \ell(p_i)$. Choose $x \in K$ such that $\ell(x) =: a$ is maximal possible. Note that by our construction $x + \frac{\varepsilon}{2} K$ has a common point with some $K_i$: there exists a point $z \in (x + \frac{\varepsilon}{2} K) \cap (p_i + \frac{\varepsilon}{2} K)$. We have $$\ell(p_i) + \frac{\varepsilon}{2} a \geqslant \ell(z) \geqslant \ell(x) - \frac{\varepsilon}{2} a,$$ and therefore $\ell(p_i) \geqslant a (1 - \varepsilon)$. Since $p \in (1 - \varepsilon) K$, we obtain $\ell(p) \leqslant a (1 - \varepsilon)$. A contradiction.

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

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

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