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

For a subset A of an abelian group G , given its size $|A|$ , its doubling κ =|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'⊆ A of size at most s can be found so that |A+A'| = Ω (\!min\! (κ 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 κ is large. Building up on the same ideas, we resolve a conjecture of Bollobás, Leader and Tiba that for subsets $A,B$ of Fₚ of size at most α p for an appropriate constant α > 0 , one only needs three elements b₁,b₂,b₃∈ B to guarantee |A+₁,b₂,b₃\|≥ |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.