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

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.

Use the lexicographic embedding of a sumset: choose the least tuple $(s_1,\dots ,s_n)\in {\prod }_i{S}_i$ representing each distinct sum, and let $B$ be the set of those tuples. Then $|B|=|S|$. If two projections onto $A$ had the same partial sum but different tuples, replacing the larger projected tuple by the smaller one inside its full representative would preserve that full sum and improve its lexicographic order. This is impossible. Thus the summation map is injective on the projection $B_A$, giving $|B_A|\le |S_A|$.

Replace every integer tuple of $B$ by the closed unit cube centered there. Their interiors are disjoint, and each coordinate projection is a union of unit cubes indexed by $B_A$, so the resulting body has volume $|B|$ and projected volume $|B_A|$. Apply the box theorem to obtainThe empty-set case uses $S_{\varnothing }=\{0\}$ and the empty product one.

Translate each two-element set by its smaller element to write $S_i=\{0,s_i\}$ with $s_i>0$. Translation does not affect any sumset cardinality. The pair-sum hypothesis forces the $s_i$ to be distinct, since equal values would give only three pair sums. Relabel so $s_1<\cdots <s_n$.

The distinct-positive-integer subset-sum lower bound has a short inductive proof. Suppose the first $n-1$ values have sum $P$, their largest subset sum. Adding $s_n$ creates the $n$ distinct sums $P+s_n$ and $P+s_n-s_i$ for $1\le i<n$. They are all above $P$, since $s_n>s_i$, and hence are all new. Starting with one sum for no elements and adding $1,2,\dots ,n$ new sums givesEquality is attained by $S_i=\{0,i\}$. Their subset sums fill every integer from zero to $n(n+1)/2$, by induction on $n$, and each pair of distinct positive values has four different pair sums. Thus the bound is best possible for every $n$.