Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 / 2 / i

The uniform cover inequality states that for a positive-volume body $K\subset {\mathbb{R}}^n$ and a multiset $\mathcal{A}$ in which each coordinate occurs exactly $k$ times, $\boxed{|K{|}^k\le \prod _{A\in \mathcal{A}}|K_A|}$, where $K_A$ is its coordinate projection and volumes use the corresponding dimensions.

To deduce the box theorem, maximize ${\sum }_i{x}_i$ subject to ${\sum }_{i\in A}{x}_i\le \log |K_A|$ for every nonempty $A\subseteq [n]$. This linear program is feasible and bounded above by the full-set constraint. Its dual minimizes ${\sum }_A{\lambda }_A\log |K_A|$ over nonnegative weights with ${\sum }_{A\ni i}{\lambda }_A=1$. For rational weights, clearing denominators gives an exact uniform cover, so the uniform cover inequality bounds that dual objective below by $\log |K|$. The same holds for all feasible weights by density of rational points in the rational constraint polyhedron. Strong duality makes the primal optimum at least $\log |K|$, while the full-set constraint makes it at most that value. An optimal solution therefore gives $b_i=e^{x_i}>0$ withThe axis-aligned box with these side lengths has the required volume and projection volumes.