1. Introduction

For finite subsets $A,B$ of an abelian group, their sumset is $A+B=\{a+b\;:\;a \in A,b \in B\}$ . Estimating the sizes of sumsets is a classical topic extensively studied in additive combinatorics, and has motivated the development of a wide variety of influential tools and techniques. One of the most classical results in this area is the Cauchy–Davenport bound [Reference Cauchy7–Reference Davenport9], which says that for nonempty subsets $A,B$ of $\mathbb{F}_p$ , $|A+B|\ge \min\! (p,|A|+|B|-1)$ . This strengthens the simple observation that for nonempty subsets $A,B\subseteq \mathbb{Z}$ , $|A+B|\ge |A|+|B|-1$ . The equality cases of the Cauchy–Davenport bound were later characterized by Vosper [Reference Vosper29], who showed that either $A,B$ must be arithmetic progressions of the same common difference, or $\min\! (|A|,|B|)=1$ , or $|A|+|B| \geq p-1$ .

Recently, in a sequence of papers, Bollobás, Leader and Tiba [Reference Bollobás, Leader and Tiba5, Reference Bollobás, Leader and Tiba6] studied several intriguing strengthenings of classical sumset estimates, including the Cauchy–Davenport bound. In particular, they showed that for nonempty subsets $A,B$ of integers with $|A|\ge |B|$ , it is enough to use three elements from $B$ to achieve the sumset bound, that is, there exists a subset $B_{(3)}$ of $B$ of size at most three such that $|A+B_{(3)}| \ge |A|+|B|-1$ . Similarly, they showed that for subsets $A,B$ of $\mathbb{F}_p$ with $|A|\ge |B|$ and $|A|+|B|$ bounded away from $p$ , there exists a subset $B_{(C)}$ of $B$ of constant size $C$ for which $|A+B_{(C)}|\ge \min\! (p,|A|+|B|-1)$ . (Here and throughout the paper, we use the notation $A_{(s)}$ and $B_{(s)}$ to denote subsets of $A$ and $B$ of size at most $s$ .) The results were also later shown in the ‘medium-sized’ regime in [Reference Bollobás, Leader and Tiba6]: for subsets $A,B$ of $\mathbb{F}_p$ with $|A|=|B|=n$ , there exist subsets $A'$ of $A$ and $B'$ of $B$ each of size at most $C\sqrt{n}$ for which $|A'|+|B'|\ge \min\! (p,|A|+|B|-1)$ for some absolute constant $C$ . Bollobás, Leader and Tiba [Reference Bollobás, Leader and Tiba5, Reference Bollobás, Leader and Tiba6] pose several interesting conjectures motivated from their work.

Sumset estimates beyond the Cauchy–Davenport bound have been extensively studied, where the behaviour gets significantly more interesting. For example, while sets achieving the Cauchy–Davenport bound have particularly simple structure, for sets $A,B$ with $|A|=|B|=n$ and $|A+B|\le \lambda n$ for a constant $\lambda \gt 2$ , the structure gets considerably more complex and there is no exact characterization of $A$ and $B$ . Nevertheless, we know from Freiman’s Theorem [Reference Freiman14, Reference Freiman15] that $A$ and $B$ are dense subsets of generalized arithmetic progressions of bounded dimension. This central result has been very influential in the further development of additive combinatorics and related areas, see for example [Reference Nathanson24, Reference Tao and Vu28]. Motivated by this theme, in this paper, we study sumset bounds beyond the Cauchy–Davenport bound that can be achieved using small subsets. We prove several positive results and present constructions which give information about the fundamental limits.

Lower bounds beyond the Cauchy–Davenport bound. Our first main result in the paper shows that we can indeed achieve bounds much better than the Cauchy–Davenport bound using a bounded number of elements, where the size of the sumset we can guarantee using the small subset grows with the size of the sumset $A+A$ . More generally, the result holds for nonabelian groups. For subsets $A,B$ of a group which is not necessarily abelian, we write $AB=\{ab\;:\;a \in A, b \in B\}$ .

Theorem 1.1. There exists $c\gt 0$ such that the following holds. Let $G$ be a group. Let $A\subseteq G$ be nonempty and let $\kappa =\kappa (A)\;:\!=\; |AA|/|A|$ . Then for each $s \ge 1$ , there exists $A_{(s)}\subseteq A$ of size at most $s$ such that

\begin{equation*} \max\! (|AA_{(s)}|,|A_{(s)}A|) \ge c\min\! (\kappa ^{1/3},s)|A|. \end{equation*}

Note that if $G$ is an abelian group, then the conclusion of Theorem 1.1 can be simplified as $|A+A_{(s)}| \ge c\min\! (\kappa ^{1/3},s)|A|$ . In general nonabelian group, it is necessary to consider both $AA_{(s)}$ and $A_{(s)}A$ (see Proposition 2.3). Furthermore, it is clear that $|AA_{(s)}|\le s|A|$ and $|AA_{(s)}| \le \kappa |A|$ . In fact, we give a construction (see Proposition 2.5) showing that a bound better than $c\kappa ^{1/1.29}|A|$ cannot hold even in the abelian case, so the bound in Theorem 1.1 is tight up to possibly replacing $\kappa ^{1/3}$ by $\kappa ^C$ for some $C\in [1/3,1/1.29]$ .

We also prove the following asymmetric version.

Theorem 1.2. There exists $c\gt 0$ such that the following holds. Let $G$ be a group. Let $A,B\subseteq G$ be nonempty such that $|A|=|B|$ and let $\kappa = \kappa (A,B)\;:\!=\;|AB|/|A|$ . Then for each $s \ge 1$ , there exist $A_{(s)}\subseteq A$ and $B_{(s)}\subseteq B$ of size at most $s$ such that

\begin{equation*} \max\! (|AB_{(s)}|,|A_{(s)}B|) \ge c\min\! (\kappa ^{1/3},s)|A|. \end{equation*}

Unlike the result of [Reference Bollobás, Leader and Tiba5] achieving the Cauchy–Davenport bound, in our case, it is necessary to consider $\max\! (|AB_{(s)}|,|BA_{(s)}|)$ even when the group $G$ is abelian (see Proposition 2.6). In Proposition 2.4, we also derive an analogue of Theorem 1.1 for difference sets, in which the power $1/3$ can be replaced by $1/2$ . We further extend these results to the medium-sized regime; however, in this setting, we can only expect to improve over the Cauchy–Davenport bound in a lower order term (see Theorem 2.8 and Proposition 2.9).

To illustrate the idea, we sketch our proof of Theorem 1.1. We first run a greedy procedure to grow $AA_{(s)}$ and $A_{(s)}A$ , and terminate when adding any additional element does not increase $|AA_{(s)}|$ or $|A_{(s)}A|$ by more than $c|A|$ . When this happens, we show that for each element $a\in A\setminus A_{(s)}$ , all but a $c$ fraction of elements $a' a,a'\in A$ have to lie in $AA_{(s)}$ , and all but a $c$ fraction of elements $a a',a'\in A$ have to lie in $A_{(s)}A$ . Using a path counting argument similar to the one employed in the proof of the Balog–Szemerédi–Gowers theorem [Reference Balog and Szemerédi1, Reference Gowers19], we can then upper bound $|AA|$ by $O_c(\max\! (|AA_{(s)}|,|A_{(s)}A|)^3/n^2)$ , which yields the desired bound. The full proofs of Theorem 1.1 and Theorem 1.2 are contained in Section 2.

Application: The Cauchy–Davenport bound over $\mathbb{F}_p$ using three elements. The path counting argument to bound $|A+A|$ from the sum of $A$ and a set of bounded size is useful for other applications. In Section 3, we use this idea to resolve a conjecture of Bollobás, Leader and Tiba (Conjecture 1 of [Reference Bollobás, Leader and Tiba5]), showing that over $\mathbb{F}_p$ , it suffices to use three elements to achieve the Cauchy–Davenport bound.

The proof involves applying the path counting argument as in Section 2 in several iterations to bound the size of $A'+B'$ for appropriate subsets $A'$ of $A$ and $B'$ of $B$ . When dealing with sets that have bounded sumset, one can apply appropriate rectification results to connect the problem over $\mathbb{F}_p$ with a problem over $\mathbb{Z}$ . However, the main difficulty is that sumsets are not stable under addition or removal of a small number of elements, and even controlling sums of subsets of $A$ and $B$ that contain all but at most an $\epsilon$ fraction of elements does not yield similar control on the sum of $A$ and $B$ . (We will later revisit this phenomenon when discussing Theorem 1.7 and Theorem 1.8.) We then need a careful argument that works directly with appropriate rectifications of subsets of $A$ and $B$ and adapts the argument inspired by the argument of [Reference Bollobás, Leader and Tiba5] over $\mathbb{Z}$ appropriately.

High dimensional versions. Another setting where one can expect to go beyond the Cauchy–Davenport bound is the high dimension setting, for example where we have a set $A$ in $\mathbb{Z}^d$ which is not close to a lower dimensional set in an appropriate sense. In particular, using the Freiman–Bilu Theorem [Reference Bilu3, Reference Green and Tao17], we can show that for every $d$ and $\epsilon$ , there exists $t\gt 0$ such that if $A\subseteq \mathbb{Z}^d$ and $A$ cannot be covered by a union of $t$ hyperplanes, then $|A+A| \ge (2^d-\epsilon )|A|$ . In Section 4, we consider the analogue of the results of [Reference Bollobás, Leader and Tiba5] over the high dimension setting and show that the high-dimension analogue of the Cauchy–Davenport bound can be achieved using only a bounded number of elements.

In [Reference Bollobás, Leader and Tiba6, Question 3], it was asked if a medium-sized version holds: for a subset $A\subseteq \mathbb{Z}^d$ that is not contained in the union of any $t$ parallel hyperplanes, does there exist $A'\subseteq A$ with $|A'|\le C\sqrt{|A|}$ and $|A'+A'|\ge (2^d-\epsilon )|A|$ ? It turns out that the answer to this question is negative, as shown in Proposition 4.1. Nevertheless, the bounded size version of this, Theorem 1.4, holds.

Saturating the entire sumset from a subset. In the following parts, we will work with subsets of general abelian groups. As discussed earlier, it is not possible to achieve a fixed positive fraction of $|A+A|$ using the sum of $A$ and a subset $A_C$ of $A$ of size $C$ depending only on the doubling constant $\kappa =|A+A|/|A|$ (see Theorem 1.8 and Proposition 2.5). Nevertheless, it is interesting to determine how large a subset $A'$ of $A$ is needed in order to guarantee $|A+A'|\ge (1-\epsilon )|A+A|$ . It turns out that if $A$ has bounded doubling, $\kappa \le \lambda = O(1)$ , one can always guarantee the existence of a subset $A'$ of $A$ of size $o(|A|)$ with $A'+A=A+A$ . Furthermore, the asymmetric version holds: for any $A$ and $B$ with $|A|=|B|$ and $|A+B|\le \lambda |A|$ , one can find subsets $A'$ of $A$ and $B'$ of $B$ each of size $o(|A|)$ such that $A+B=(A'+B)\cup (A+B')$ . In the case where $A,B$ are dense subsets of $\mathbb{F}_p^n$ , this was earlier shown by Ellenberg [Reference Ellenberg11] with efficient bounds building on the cap-set breakthrough. In Section 5, we show that a much more general phenomenon holds for subsets of groups with bounded doubling which are not necessarily dense.

Our proof also gives rise to the appropriate generalization over general groups.

Both corollaries follow from a more general result (Theorem 5.1) in Section 5, which is proved using the graph theoretic triangle removal lemma. A reduction from an arithmetic removal lemma to a graph removal lemma goes back to work of Král’, Serra and Vena [Reference Král’, Serra and Vena23], and our main technical result builds on and extends their argument. As applications of the graph removal lemma, our proofs of Corollaries 1.5 and 1.6 do not achieve strong quantitative bounds over general groups. By using the bounds for the arithmetic removal lemma over $\mathbb{F}_p^n$ due to Fox and Lovász [Reference Fox and Lovász13], we can achieve a polynomial saving, replacing $o(|S|)$ by an appropriate power $|S|^{1-c_m}$ in the case where $G$ is an abelian group with bounded exponent $m$ . Nevertheless, in the case $G=\mathbb{F}_p^n$ , the argument of Ellenberg [Reference Ellenberg11] gives a better (in fact sharp) exponent for Corollary 1.5. In Section 5, we also give constructions in the cases $G=\mathbb{Z}$ and $G=\mathbb{F}_p^n$ suggesting fundamental limits on quantitative bounds to the corollaries.

A construction of a non-saturating set. While it is not possible to achieve almost all of $A+A$ using a bounded number of elements, one of the key results in [Reference Bollobás, Leader and Tiba5] says that this is possible upon replacing $A$ with a subset $A'$ consisting of almost all elements of $A$ .

Theorem 1.7 ([Reference Bollobás, Leader and Tiba5]). For $\lambda,\epsilon \gt 0$ , there exists $C\gt 0$ such that the following holds. Let $A,B$ be nonempty subsets of an abelian group $G$ with $|A|=|B|$ . Then there exist $A'\subseteq A$ , $B'\subseteq B$ with $|A'|\ge (1-\epsilon )|A|$ and $|B'|\ge (1-\epsilon )|B|$ , such that if $B''$ consists of $C$ randomly chosen elements of $B'$ , then

\begin{equation*} \mathbb {E}[|A'+B''|]\ge \min\! ((1-\epsilon )|A'+B'|,\lambda |A|,\lambda |B|). \end{equation*}

In particular, if $|A+B|\le \lambda |A|$ , then there exists a subset $B''$ of $B'$ of size at most $C$ such that $|A'+B''| \ge (1-\epsilon )|A'+B'|$ .

We remark that it is also straightforward to obtain the symmetric analogue of the above theorem, where $B=A$ and $B'=A'$ .

Much of the subtlety in obtaining sumset bounds growing with $|A+A|$ is that, unlike the Cauchy–Davenport bound which is stable under passing $A$ to a subset $A'$ that contains almost all elements of $A$ , sumsets can generally behave unstably under addition or removal of few elements. For example, consider $A$ which is the union of a progression $P$ of length $n$ , and a small collection of $k$ arbitrary elements. Then $|A+A|$ can be as large as $kn$ , whereas upon removal of $k$ elements, the size of the sumset is only $2n-1$ , matching the Cauchy–Davenport bound. This is the main reason behind stopping at the Cauchy–Davenport bound in [Reference Bollobás, Leader and Tiba5], and Theorem 1.7 suggests that this is the only obstruction.

The example of a progression together with few additional elements mentioned above suggests that it is impossible to replace $|A'+B'|$ with $|A+B|$ in Theorem 1.7. However, it is unclear if we can replace only one of two sets with a subset. Considering that we are allowed to make our selection of elements from $B$ , it could be the case that we only need to replace $A$ by a subset $A'$ with better additive structure. Bollobás, Leader and Tiba (Question 5, [Reference Bollobás, Leader and Tiba5]) ask this explicitly: Given constants $\epsilon \gt 0$ and $\lambda \gt 0$ , is there a constant $c\gt 0$ such that the following assertion holds? If $A,B$ are subsets of $\mathbb{F}_p$ with $|A|=|B|=n$ and $|A+B|\le \lambda n$ , then there are sets $A'\subseteq A$ and $B'\subseteq B$ such that $|A'|\ge (1-\epsilon )n$ and $|B'|\le c$ and $|A'+B'|\ge (1-\epsilon )|A'+B|$ .

It turns out that the answer to this question is negative. In Section 6, we give a construction showing this in a strong sense: It is not possible to achieve a fixed positive fraction of the sumset $A'+A$ using a bounded number of elements from $A'$ even when we are allowed to choose $A'$ which is a subset of $A$ of size at least $(1-\epsilon )|A|$ .

In fact, in our proof, we can even let $s$ grow at some explicit rate together with the size of $A$ . Note that the existence of such a set $A$ is nontrivial: Since we replace $A$ with a subset $A'$ which is ‘regular’ in an appropriate sense in terms of additive structure, if $|A'+A|$ is large, it cannot be due to a small number of bad elements, and we may expect to be able to select many translates of $A'$ that do not have significant overlap, leading to a large sumset. However, it turns out that this intuitive picture is not correct. Our construction involves a niveau-like set $A$ first constructed over $\mathbb{F}_2^n$ , then adapted to the setting of appropriate cyclic groups and then to the integers and prime cyclic groups.

Organization of the paper. In Section 2, we consider bounds beyond the Cauchy–Davenport bound that are achievable using a bounded number of elements, and prove Theorems 1.1 and 1.2, as well as their medium-sized analogues. In Section 3, we prove Theorem 1.3, which verifies the conjecture of Bollobás, Leader and Tiba that it suffices to use three elements to achieve the Cauchy–Davenport bound over $\mathbb{F}_p$ . In Section 4, we consider the high-dimension setting and prove Theorem 1.4. In Section 5, we study the number of elements needed to saturate the entire sumset, and prove Corollaries 1.5 and 1.6. In Section 6, we give the construction proving Theorem 1.8, that it is not possible to achieve a fixed positive fraction of $A'+A$ using a bounded-sized subset of $A'$ , even when we are allowed to choose $A'$ as a subset consisting of almost all elements of $A$ .

Notations and conventions. We use the following standard asymptotic notations. We denote $f=O_P(g)$ , $f\ll _P g$ , or $g=\Omega _P(f)$ when there is a constant $C\gt 0$ depending on $P$ so that $f\le Cg$ , and we denote $f=o_P(g)$ or $g=\omega _P(f)$ if $f/g\to 0$ for fixed $P$ . We omit floors and ceilings when they are not essential. We denote $[x]=\{n\in \mathbb{Z}:1\le n \le x\}$ . For a positive integer $t$ and a set $X$ (a subset of an abelian group), we use $tX = X + X + \cdots + X = \{x_1+\cdots + x_t:x_i\in X, i\in [t]\}$ to denote the $t$ -fold sumset. Throughout, unless otherwise stated, we use $p$ to denote a prime number.