Sharp Lower Bounds for Sumsets in Hypercubes

Abstract

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 \[|A_1+\dots+A_n|\;\geq\; (|A_1|\cdots|A_n|)^{1/p},\qquad 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.

21 pages, 3 figures