Sharp Lower Bounds for Sumsets in Hypercubes

We prove a sharp lower bound for the cardinality of sumsets of subsets of ${\mathbb{Z}}^d$ confined to a hypercube, resolving in strong form a conjecture that was made explicit by Becker, Ivanisvili, Krachun and Madrid and had circulated in the folklore of the field for some time. Specifically, for sets $A_j\subseteq \{0,1,2,\dots ,m{\}}^d$ we show that $$\mathrm{\mid }{A}_1+\cdots +A_n\mathrm{\mid }\ge (\mathrm{\mid }{A}_1\mathrm{\mid }\cdots \mathrm{\mid }{A}_n\mathrm{\mid }{)}^{1\mathrm{/}p},p=\frac{n\log (m+1)}{\log (nm+1)},$$ with the exponent best possible. The only previously known sharp cases were $A_j\subseteq \{0,1{\}}^d$, for all $n\ge 1$, and $A_j\subseteq \{0,1,2{\}}^d$ for $n=2$. We also prove a sharp inequality in the case when $A_j\subseteq \{0,1,\dots ,m_j{\}}^d$ for different $m_j$. We obtain the above inequality as a corollary of a stronger result on sup-convolution of functions on ${\mathbb{Z}}^d$, whose proof is based on a novel mixed volume representation of a lattice path norm, together with a sharp one-dimensional functional inequality.