Large sumsets from small subsets

Journal article

In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy–Davenport theorem gives a lower bound on the size of a sumset A + B for subsets of the cyclic group ℤp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset B′ of bounded size such that A + B′ is large, perhaps even comparable to the size of A + B? In particular, can we get close to the lower bound of the Cauchy–Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself. For example, in ℤ, we show that if A and B have size n then there are three elements b1, b2, b3 ∈ B such that ∣(A + b1) ∪ (A + b2) ∪ (A + b3)∣ ⩾ 2n − 1. And for ℤp itself, we show the following: if A and B have size n, where n ⩽ p/3, then there is a subset B′ of B of size c such that ∣A + B′∣ ⩾ 2n − 1. Here c is an absolute constant. In the inverse direction for this result, we show that if for every subset B′ of B of size c we have ∣A + B′∣ ⩽ 2n − 1 + r, where r ⩽ εn for some absolute constant ε, then B is contained in an arithmetic progression of size n + r. We also prove ‘unbalanced’ forms of our results, when the sizes of A and B may differ. As an application, we prove some considerable extensions of the Erdős–Heilbronn problem. We also present versions in the continuous setting, and give several open problems.

Authors: Bollobás, B; Leader, I; Tiba, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Israel Journal of Mathematics
• Volume: 268
• Issue: 1
• Pages: 253-314
• Publication date: 2025-02-17
• DOI: 10.1007/s11856-025-2736-z
• EISSN: 1565-8511
• ISSN: 0021-2172
• Language: English