Discrete Brunn-Minkowski Inequality for subsets of the cube

Abstract

We show that for all $A,B\subseteq \{0,1,2{\}}^d$ we have $$|A+B|\ge (|A||B|{)}^{\log (5)/(2\log (3))}.$$ We also show that for all finite $A,B\subset {\mathbb{Z}}^d$, and any $V\subseteq \{0,1{\}}^d$ the inequality $$|A+B+V|\ge |A{|}^{1/p}|B{|}^{1/q}|V{|}^{{\log }_2(p^{1/p}{q}^{1/q})}$$ holds for all $p\in (1,\infty )$, where $q=\frac{p}{p-1}$ is the conjugate exponent of $p$. All the estimates are dimension free with the best possible exponents. We discuss applications to various related problems.

25 pages. References added. Acknowledgments updated