Small subsets with large sumset: Beyond the Cauchy–Davenport bound

Abstract

Abstract For a subset $A$ of an abelian group $G$ , given its size $|A|$ , its doubling $\kappa =|A+A|/|A|$ , and a parameter $s$ which is small compared to $|A|$ , we study the size of the largest sumset $A+A'$ that can be guaranteed for a subset $A'$ of $A$ of size at most $s$ . We show that a subset $A'\subseteq A$ of size at most $s$ can be found so that $|A+A'| = \Omega (\!\min\! (\kappa ^{1/3},s)|A|)$ . Thus, a sumset significantly larger than the Cauchy–Davenport bound can be guaranteed by a bounded size subset assuming that the doubling $\kappa$ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of $\mathbb{F}_p$ of size at most $\alpha p$ for an appropriate constant $\alpha \gt 0$ , one only needs three elements $b_1,b_2,b_3\in B$ to guarantee $|A+\{b_1,b_2,b_3\}|\ge |A|+|B|-1$ . Allowing the use of larger subsets $A'$ , we show that for sets $A$ of bounded doubling, one only needs a subset $A'$ with $o(|A|)$ elements to guarantee that $A+A'=A+A$ . We also address another conjecture and a question raised by Bollobás, Leader and Tiba on high-dimensional analogues and sets whose sumset cannot be saturated by a bounded size subset.

Locations

• arXiv (Cornell University) - View - PDF
• Combinatorics Probability Computing - View