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

Abstract 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'| = (\!\! (^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₂, 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.