# The typical approximate structure of sets with bounded sumset

Marcelo Campos<EMAIL_ADDRESS>Instituto de Matemática Pura e Aplicada,
Rio de Janeiro, RJ, 22460-320, Brazil  Matthew Coulson
<EMAIL_ADDRESS>Department of Combinatorics & Optimization,
University of Waterloo, ON N2L 3G1, Canada  Oriol Serra<EMAIL_ADDRESS>Department of Mathematics, Universitat Politècnica de Catalunya, 08034
Barcelona, Spain  Maximilian Wötzel<EMAIL_ADDRESS>Korteweg-de Vries
Institute for Mathematics, Universiteit van Amsterdam, 1098 XG Amsterdam, The
Netherlands

###### Abstract

Let $A_{1}$ and $A_{2}$ be randomly chosen subsets of the first $n$ positive
integers of cardinalities $s_{2}\geq s_{1}=\Omega(s_{2})$, such that their
sumset $A_{1}+A_{2}$ has size $m$. We show that asymptotically almost surely
$A_{1}$ and $A_{2}$ are almost fully contained in arithmetic progressions
$P_{1}$ and $P_{2}$ with the same common difference and cardinalities
approximately $s_{i}m/(s_{1}+s_{2})$. We also prove a counting theorem for
such pairs of sets in arbitrary abelian groups. The results hold for
$s_{i}=\omega(\log^{3}n)$ and $s_{1}+s_{2}\leq m=o(s_{2}/\log^{3}n)$. Our main
tool is an asymmetric version of the method of hypergraph containers which was
recently used by Campos to prove similar results in the special case $A=B$.

Keywords: additive combinatorics, sumsets, hypergraph containers

MSC2010 classes: 11P70, 11B30, 05C65

##  1 Introduction and Main Results

The general framework of problems in additive combinatorics is to ask for the
structure of a set $A$ subject to some additive constraint in an additive
group. The celebrated theorem of Freiman [9] provides such a structural result
in terms of arithmetic progressions when the sumset $A+A$ is small. Classical
results like the Kneser theorem in abelian groups or the Brunn–Minkowski
inequality in Euclidean spaces naturally address a similar problem for the
addition of _distinct_ sets $A$ and $B$. Ruzsa’s proof of Freiman’s theorem
does provide the same structural result for distinct sets $A,B$ with the same
cardinality when their sumset is small. When the sumset $A+A$ is very small,
then another theorem of Freiman shows that the set is dense in one arithmetic
progression, and this result has been also extended to distinct sets $A$ and
$B$ by Lev and Smeliansky [19] showing that both sets are dense in arithmetic
progressions with the same common difference. Discrete versions of the
Brunn–Minkowski inequality have also been addressed for distinct sets by Ruzsa
[22] and Gardner and Gronchi [10].

Motivated by the Cameron-Erdős conjecture on the number of sum-free sets in
$[n]=\\{1,2,\dots,n\\}$, there has been a quest to analyze the _typical_
structure of sets satisfying some additive constraint. One of the most
efficient techniques to address this problem is the method of hypergraph
containers first introduced by Balogh, Morris and Samotij [3] and
independently by Saxton and Thomason [23], which has been successfully applied
to a number of problems of this flavour.

In [1] Alon, Balog, Morris and Samotij posed a conjecture on the number of
sets $A$ of size $s\geq C\log n$ contained in $[n]$ which have sumset
$|A+A|\leq K|A|$, $K\leq s/C$. This was proved recently by Green and Morris
[12] for $K$ constant and recently extended by Campos [5] to $K=o(s/(\log
n)^{3})$. These counting results are naturally connected to the typical
structure of these sets, showing that they are almost contained in an
arithmetic progression of length $(1+o(1))Ks/2$. We build on the later work by
Campos to adapt the result to distinct sets. Our main result is the following.

######  Theorem 1.1.

Let $n\geq s_{2}\geq s_{1}=\Omega(s_{2})$ be integers and $m$ an integer
satisfying

$s_{1}+s_{2}\leq m=o(s_{2}^{2}/(\log n)^{3}).$

Then for almost all sets $X_{1},X_{2}\subset[n]$ such that $|X_{i}|=s_{i}$ and
$|X_{1}+X_{2}|\leq m$, there exist arithmetic progressions $P_{1}$ and $P_{2}$
with the same common difference of size $|P_{i}|=(1+o(1))s_{i}m/(s_{1}+s_{2})$
and $|X_{i}\setminus P_{i}|=o(s_{i})$.

Theorem 1.1 extends the result by Campos which corresponds to the symmetric
case $X_{1}=X_{2}$. It is derived from Theorem 4.1 in Section 4 which gives
more detailed quantitative estimations of the asymptotics involved in the
above statement.

Our proof requires that the cardinalities of the two sets $X_{1},X_{2}$ are
not arbitrarily far apart, with specifics being discussed in Section 6. But
this seems natural: Even if the condition $|X_{1}|=\Omega(|X_{2}|)$ can be
weakened, it is not clear to us that a nontrivial structural result should
hold when one set is much smaller than the other. As an extreme example,
consider the situation when $|X_{2}|=2$ and $X_{1}$ is a random set
$X_{1}\subset[n]$ of size $|X_{1}|=\Omega(\log n)$ such that
$|X_{1}+X_{2}|\leq|X_{1}|+c$ for some positive constant $c\geq 3$. Then
$X_{1}$ is a union of at most $c$ arithmetic progressions. An arbitrary union
of $c$ progressions will provide an example of a set $X_{1}$ with such a small
sumset, and the probability that a random choice of $c$ progressions is well
covered by a short single one is negligible. Back-of-the-envelope calculations
imply that an equivalent statement might hold, as long as the size of the
smaller set is bounded.

We can also prove the following counting analogue to Theorem 1.1 for an
arbitrary abelian group, which can be compared to Theorem 1.4 in [5]. We need
the following definition. For an abelian group $G$ and any positive real
number $t$ define $\beta(t)=\max\\{|H|:H\leq G,\,|H|\leq t\\}$.

######  Theorem 1.2.

Let $G$ be an abelian group. Let $n\geq s_{2}\geq s_{1}=\Omega(s_{2})$ be
integers and $m$ an integer satisfying $s_{1}+s_{2}\leq m=o(s_{2}^{2}(\log
s_{2})^{-4}(\log n)^{-3})$. Then for any $F_{1},F_{2}\subset G$ with
$|F_{i}|=n$, the number of pairs of sets $(X_{1},X_{2})\in 2^{F_{1}}\times
2^{F_{2}}$ such that $|X_{i}|=s_{i}$ and $|X_{1}+X_{2}|\leq m$ is at most

$2^{o(s_{2})}\binom{\frac{s_{1}}{s_{1}+s_{2}}(m+\beta)}{s_{1}}\binom{\frac{s_{2}}{s_{1}+s_{2}}(m+\beta)}{s_{2}},$

where $\beta=\beta((1+o(1))m)$.

In groups that allow a result similar to Freiman’s $3k-4$ theorem one can get
rid of the $\log s_{2}$ term in the upper bound of $m$ in Theorem 1.2.
Specific examples would be the integers $G=\mathbb{Z}$ or the integers modulo
some prime $p$, that is, $G=\mathbb{Z}/p\mathbb{Z}$. An example discussed in
[5] that can easily be adapted to the asymmetric case shows that the range of
$m$ for which Theorem 1.2 holds cannot be improved to $m=\Omega(s_{2}^{2}/\log
n)$. It is not clear whether the same holds true for Theorem 1.1, and an
interesting question would be to investigate whether it might be true for any
$m=o(s_{2}^{2})$. Furthermore, note that as will become apparent in the
proofs, the requirement $s_{i}=\omega((\log n)^{3})$ mentioned in the abstract
is not used directly. Rather, it exists because otherwise the statements in
Theorems 1.1 and 1.2 would become vacuous, since no $m$ satisfying the bounds
could exist.

The proofs of both Theorem 1.1 and Theorem 1.2 will make use of the method of
hypergraph containers, building upon the approach by Campos [5]. The usual
structure of this method is to essentially have two separate ingredients, the
first being a result about independent sets in hypergraphs following certain
degree conditions, and the second being supersaturation and stability results.
Our proof will also follow along these lines.

To that end, in Section 2 we will present with Theorem 2.1 a new variant of
the asymmetric container lemma introduced by Morris, Samotij and Saxton [20],
which is extended to a multipartite version. This extension does not require
new ideas but the verification of the statement involves some technical issues
so that for completeness we include a full proof in Section 5. The main focus
of Section 2 will instead be the application of this multipartite version of
the container lemma to prove Theorem 2.2, a statement which provides a
relatively small family of sets which essentially contain sets whose product
has bounded cardinality in a (not necessarily abelian) group. We chose to
state Theorem 2.2 in more generality than is required for our results, namely
for general groups, as it follows in a natural way from the container lemma
and can be used in further applications. In Section 3 we will then develop the
required supersaturation and stability results. Unlike previous works on these
problems, which use variants of a theorem by Pollard [21] on averages of the
representation function, for the stability results we use a robust version of
Freiman’s $3k-4$–theorem by Shao and Xu [25], which itself built on earlier
work by Lev [18]. The $3k-4$–theorem of Freiman, or rather its asymmetric
version by Lev and Smeliansky [19], states that if the sumset of two sets is
sufficiently small, then the sets themselves are dense in arithmetic
progressions. Shao and Xu extended the result to the sum of two sets along the
edges of a sufficiently dense graph, its robust version. The statement of Shao
and Xu applies to two sets with the same cardinality, and both its statement
and proof actually rely on this condition, a circumstance which prevents it
from being used in our context directly. We give a similar robust version,
Theorem 3.3, that can be seen as a truly asymmetric robust version of the
Lev–Smeliansky theorem and may be of independent interest. It requires a
different proof than the one given in [25], although a key result in both
proofs is an appropriate robust version of Kneser’s addition theorem, Theorem
3.6 in the current work. To our knowledge this is the first statement of this
kind which is applicable to pairs of sets of completely unrelated
cardinalities, and thus represents progress on a conjecture of Lev [17]. In
Section 4 we combine the two ingredients to prove Theorems 4.1 and 4.3, which
are more technical versions of our main theorems. The paper concludes with
some final remarks in Section 6, both regarding specific aspects of the
current results as well as discussions on some open problems.

##  2 The Method of Hypergraph Containers

One of the key techniques used in [5] is based on an asymmetric version of the
container lemma introduced by Morris, Samotij and Saxton [20] which allows for
applications to forbidden structures with some sort of asymmetry. This
asymmetry can be interpreted as considering bipartite hypergraphs. The first
key component to proving Theorem 1.2 is to further extend this bipartite
version to a multipartite one as follows.

Let $r$ be a positive integer. For an $r$-vector $x=(x_{1},\dots,x_{r})$ with
nonnegative integer entries, we call an $r$-partite hypergraph $\mathcal{H}$
with vertex set $V(\mathcal{H})=V_{1}\cup\dots\cup V_{r}$ _$x$ -bounded_ if
$|E\cap V_{i}|\leq x_{i}$ for every hyperedge $E\in E(\mathcal{H})$ and every
$1\leq i\leq r$. Denote by $\mathcal{I}$ the family of independent sets of
$\mathcal{H}$, and for any $m\in\mathbb{N}$, define

$\mathcal{I}_{m}(\mathcal{H}):=\left\\{I:I\in\mathcal{I}\text{ and }|I\cap
V_{r}|\geq|V_{r}|-m\right\\}.$

For a subset of vertices $L\subset V(\mathcal{H})$, the codegree is defined as
$d_{\mathcal{H}}(L)=|\\{E\in E(\mathcal{H}):L\subset E\\}|$. Also, given a
vector $v=(v_{1},v_{2},\ldots,v_{r})\in\mathbb{Z}^{r}$, denote

$\Delta_{v}(\mathcal{H}):=\max\\{d_{\mathcal{H}}(L):L\subset
V(\mathcal{H}),\leavevmode\nobreak\ |L\cap V_{i}|=v_{i},\leavevmode\nobreak\
1\leq i\leq r\\}.$

Finally, for any vector $y$, $|y|$ will denote its $1$-norm $\sum|y_{i}|$.

######  Theorem 2.1.

For all non-negative integers $r,r_{0}$ and each $R>0$ the following holds.
Suppose that $\mathcal{H}$ is a non-empty $r$-partite
$(1,\dots,1,r_{0})$-bounded hypergraph with $V(\mathcal{H})=V_{1}\cup
V_{2}\cup\ldots\cup V_{r}$, $m\in\mathbb{N}$, and $b,q$ are positive integers
with $b\leq\min\\{|V_{1}|,\dots,|V_{r-1}|,m\\}$ and $q\leq m$, satisfying

$\Delta_{y}(\mathcal{H})\leq
R\left(m^{y_{r}}\prod_{i=1}^{r-1}|V_{i}|^{y_{i}}\right)^{-1}b^{|y|-1}e(\mathcal{H})\left(\frac{m}{q}\right)^{\mathds{1}[y_{r}>0]}$
(1)

for every vector
$y=(y_{1},y_{2},\ldots,y_{r})\in\left(\prod_{i=1}^{r-1}\\{0,1\\}\right)\times\\{0,1,\ldots,r_{0}\\}$.
Then there exists a family
$\mathcal{S}\subset\prod_{i=1}^{r}\binom{V_{i}}{\leq b}$ and functions
$f\colon\mathcal{S}\to\prod_{i=1}^{r}2^{V_{i}}$ and
$g\colon\mathcal{I}_{m}(\mathcal{H})\to\mathcal{S}$, such that, letting
$\delta=2^{-(r_{0}+r-1)(2r_{0}+r)}R^{-1}$, the following statements hold.

  1. (i)

If $f(g(I))=(A_{1},A_{2},\ldots,A_{r})$ with $A_{i}\subset V_{i}$, then $I\cap
V_{i}\subset A_{i}$ for all $1\leq i\leq r$.

  2. (ii)

For every $(A_{1},A_{2},\ldots,A_{r})\in f(\mathcal{S})$, either
$|A_{i}|\leq(1-\delta)|V_{i}|$ for some $1\leq i<r$, or
$|A_{r}|\leq|V_{r}|-\delta q$.

  3. (iii)

If $g(I)=(S_{1},S_{2},\ldots,S_{r})$ and $f(g(I))=(A_{1},A_{2},\ldots,A_{r})$,
then $S_{i}\subset I\cap V_{i}$ for all $1\leq i\leq r$. Furthermore,
$|S_{i}|>0$ only if $|A_{j}|\leq(1-\delta)|V_{j}|$ for some $i\leq j<r$ or
$|A_{r}|\leq|V_{r}|-\delta q$.

The proof of Theorem 2.1 is lengthy and very similar to the original
asymmetric lemma of Morris, Samotij and Saxton [20], but for the sake of
completeness we present it in full in Section 5. For now, let us see how to
successively apply it to construct the container family we want to work with.
We will be making use of the following hypergraph construction. For a group
$G$ and finite subsets $A,B,C\subset G$, define the $3$-partite and
$(1,1,1)$-bounded hypergraph $\mathcal{H}(A,B,C)$ in the following way. The
vertex set is $A\sqcup B\sqcup C$ and $\\{a,b,c\\}$ is a hyperedge if $a\in
A$, $b\in B$, $c\in C$, and $ab=c$. Note that the sets $A,B,C$ need not
actually be disjoint.

######  Theorem 2.2.

Let $G$ be a group and $\epsilon>0$. Suppose $n,m$ and $s_{1}\leq s_{2}$ are
integers such that $\log n\leq s_{2}\leq m\leq s_{1}^{2}\log n$. Let
$F_{1},F_{2}\subset G$ be subsets of $G$ of cardinality $|F_{1}|=|F_{2}|=n$
with product set $F=F_{1}F_{2}$. Then there exists a family
$\mathcal{A}\subset 2^{F_{1}}\times 2^{F_{2}}\times 2^{F}$ of triples
$(A_{1},A_{2},B)$ of size

$|\mathcal{A}|\leq\exp\left(2^{20}\epsilon^{-2}\sqrt{m}(\log n)^{3/2}\right)$
(2)

such that the following hold:

  1. 1.

Let $X_{1}\subset F_{1}$, $X_{2}\subset F_{2}$ with $|X_{i}|=s_{i}$ and
$|X_{1}X_{2}|\leq m$. Then there exists a triple
$(A_{1},A_{2},B)\in\mathcal{A}$ such that $X_{1}\subset A_{1}$, $X_{2}\subset
A_{2}$ and $B\subset X_{1}X_{2}$.

  2. 2.

Let $(A_{1},A_{2},B)\in\mathcal{A}$. Then either
$\max\\{|A_{1}|,|A_{2}|\\}\leq m/\log n$, or there are at most
$\epsilon^{2}|A_{1}||A_{2}|$ tuples $(a_{1},a_{2})\in A_{1}\times A_{2}$ such
that $a_{1}a_{2}\notin B$.

Let us remark that the second part in property 2 states that the $3$-partite
hypergraph $\mathcal{H}(A_{1},A_{2},(A_{1}A_{2})\setminus B)$ has few edges.
Before going into the specifics, let us also mention that in some sense
proving Theorem 2.2 from Theorem 2.1 is a by now standard application of the
container framework. The main idea is that as long as the conditions of
Theorem 2.1 are met, one can continue to apply it to the induced sub-
hypergraphs obtained from the previous application. Since independent sets in
the original hypergraph stay independent, one thus builds a tree of
hypergraphs where the leaves will correspond to the final family one wants to
obtain.

###### Proof.

We will construct a rooted tree $\mathcal{T}$ with root
$\mathcal{H}(F_{1},F_{2},F)$ and leaves $\mathcal{H}(A_{1},A_{2},A_{3})$ such
that one of the following properties holds:

  1. (i)

$|A_{1}|<s_{1}$ or $|A_{2}|<s_{2}$,

  2. (ii)

$\max\\{|A_{1}|,|A_{2}|\\}<m/\log n$,

  3. (iii)

$|A_{3}|<|F|-m$, or

  4. (iv)

$\mathcal{H}(A_{1},A_{2},A_{3})$ has less than $\epsilon^{2}|A_{1}||A_{2}|$
hyperedges.

The end-goal is to essentially have $\mathcal{A}$ be the subset of the leaves
of $\mathcal{T}$ that correspond to properties (ii) and (iv).

We construct $\mathcal{T}$ in the following way. Suppose we are given a vertex
$\mathcal{H}=\mathcal{H}(V_{1},V_{2},V_{3})$ of $\mathcal{T}$ with
$|V_{i}|\geq s_{i}$ for all $i=1,2$, $\max\\{|V_{1}|,|V_{2}|\\}\geq m/\log n$,
$|V_{3}|\geq|F|-m$ and $e(\mathcal{H})\geq\epsilon^{2}|V_{1}||V_{2}|$. We
apply Theorem 2.1 with parameters $R=\epsilon^{-2}$, $q=m/\log n$ and
$b=\sqrt{q}$. Note that $b\leq\min s_{i}$ because of our upper bound on $m$.
Let us show that these choices indeed satisfy the codegree conditions of the
container lemma.

Let $v=(v_{1},v_{2},v_{3})\in\\{0,1\\}^{3}$. The edges of the hypergraph are
defined by a linear relation, so in addition to the $|v|$ fixed components of
a hyperedge, one loses one additional degree of freedom to choose the
remaining $h+1-|v|$ components. In particular, for $|v|\in\\{2,3\\}$ we see
that $\Delta_{v}(\mathcal{H})=1$. Because of the assumption that
$e(\mathcal{H})\geq\epsilon^{2}\prod|V_{1}||V_{2}|$, we see that in order to
prove (1), it suffices that the parameters are chosen such that

$\Delta_{v}(\mathcal{H})\leq\epsilon^{2}Rq^{-v_{3}}|V_{1}|^{1-v_{1}}|V_{2}|^{1-v_{2}}b^{|v|-1}.$
(3)

We now confirm that (3) indeed holds for all possible choices of $v$,
beginning with $v=(1,1,1)$. As stated before we have
$\Delta_{v}(\mathcal{H})=1$ and we see that (3) simplifies to

$1\leq\epsilon^{2}Rb^{2}/q$

which is true for our choices of parameters.

We next move to vectors $v$ such that $|v|=2$. Again, just like before it
holds that $\Delta_{v}(\mathcal{H})=1$ and it is straight-forward to check
that (3) reduces to

$1\leq\epsilon^{2}Rb\min\\{|V_{1}|,|V_{2}|,q\\}/q.$

This inequality clearly holds when the minimum is $q$ (it is a weaker
requirement than the $v=(1,1,1)$ case). When the minimum is
$\min\\{|V_{1}|,|V_{2}|\\}$ instead it also holds since $|V_{1}|,|V_{2}|\geq
s_{1}\geq b=\sqrt{q}$.

Finally we check the vectors $v\in\\{0,1\\}^{3}$ with $|v|=1$. If $v=(0,0,1)$
we see that $\Delta_{v}(\mathcal{H})\leq\min\\{|V_{1}|,|V_{2}|\\}$ and hence
(3) reduces to

$\min\\{|V_{1}|,|V_{2}|\\}\leq\epsilon^{2}R|V_{1}||V_{2}|/q$

which is true since $\max\\{|V_{1}|,|V_{2}|\\}\geq q$ by assumption. For
$v=(1,0,0)$ (resp. $v=(0,1,0)$) it holds that
$\Delta_{v}(\mathcal{H})\leq|V_{2}|$ (resp. $\leq|V_{1}|$) and so (3) reduces
to

$|V_{i}|\leq\epsilon^{2}R|V_{i}|\qquad\text{for $i=1,2$,}$

which again is true for our choice of parameters.

So we see that $R=\epsilon^{-2}$, $q=m/\log n$ and $b=\sqrt{q}$ are indeed
valid choices. Hence, by Theorem 2.1, there exists a family
$\mathcal{C}\subset 2^{V_{1}}\times 2^{V_{2}}\times 2^{V_{3}}$ of size at most

$|\mathcal{C}|\leq\prod_{i=1}^{3}\binom{|V_{i}|}{\leq b}\leq
b^{3}\binom{n^{2}}{b}\binom{n}{b}^{2}\leq n^{4b}=\exp\left(4\sqrt{m\log
n}\right),$ (4)

such that for each $I\in\mathcal{I}_{m}(\mathcal{H})$ there exist
$(A_{1},A_{2},A_{3})\in\mathcal{C}$ with $I\cap V_{i}\subset A_{i}$ for all
$i\in[3]$, and either $|A_{i}|\leq(1-\delta)|V_{i}|$ for some $i=1,2$, or
$|A_{3}|\leq|V_{3}|-\delta q$, with $\delta=\epsilon^{2}2^{-15}$. For each
$(A_{1},A_{2},A_{3})\in\mathcal{C}$, add $\mathcal{H}(A_{1},A_{2},A_{3})$ as a
child of $\mathcal{H}$ in $\mathcal{T}$. In order to bound the number of
leaves of $\mathcal{T}$, we will first bound its height.

######  Claim.

The tree $\mathcal{T}$ has height at most $d=2^{18}\epsilon^{-2}\log n$.

###### Proof.

Suppose $\mathcal{H}(A_{1},A_{2},A_{3})$ is a vertex of $\mathcal{T}$ of depth
$d$. Recall that after each application of Theorem 2.1, one component shrunk,
hence after $d$ applications one of them shrunk at least $d/3$ times. Since we
started at $\mathcal{H}(F_{1},F_{2},F)$ and $\delta=2^{-15}\epsilon^{2}$,
either

$|A_{3}|\leq|F|-\frac{d\delta q}{3}=|F|-\frac{d\epsilon^{2}m}{3\cdot
2^{15}\log n}<|F|-m,$

or for one $i=1,2$,

$|A_{i}|\leq(1-\delta)^{d/3}n\leq\exp(-\delta d/3)n<1,$

and so this vertex has no children. ∎

We will now define the family $\mathcal{A}$ formally. If $\mathcal{L}$ is the
set of leaves of $\mathcal{T}$, let

$\mathcal{A}=\left\\{(A_{1},A_{2},B):\begin{array}[]{c}\mathcal{H}(A_{1},A_{2},F\setminus
B)\in\mathcal{L},\\\ |A_{1}|\geq s_{1},\,|A_{2}|\geq s_{2}\text{ and }|B|\leq
m\end{array}\right\\}.$

Since every tuple $(A_{1},A_{2},B)$ in this family corresponds to a leaf with
$|A_{i}|\geq s_{i}$ for every $i=1,2$ and $|F\setminus B|\geq|F|-m$, we must
have either $\max|A_{i}|\geq m/\log n$ or the corresponding hypergraph must
have less than $\epsilon^{2}|A_{1}||A_{2}|$ edges, that is, there are less
than $\epsilon^{2}|A_{1}||A_{2}|$ tuples $(a_{1},a_{2})\in A_{1}\times A_{2}$
such that $a_{1}a_{2}\notin B$. In any case, 2 holds.

We now check that property 1 holds. Let $X_{1},X_{2}$ with $X_{i}\subset
F_{i}$, such that $|X_{i}|=s_{i}$ for $i=1,2$ and $|X_{1}X_{2}|\leq m$. We see
that $X_{1}\cup X_{2}\cup(F\setminus(X_{1}X_{2}))$ is contained in
$\mathcal{I}_{m}\left(\mathcal{H}(F_{1},F_{2},F)\right)$, and so by the
properties of the containers there is a path in $\mathcal{T}$ from the root to
a leaf $\mathcal{H}(A_{1},A_{2},F\setminus B)$ such that $X_{i}\subset A_{i}$
and $B\subset X_{1}X_{2}$. By the size bounds for $X_{i}$ and $X_{1}X_{2}$ it
is clear that this leaf must correspond to a triple in $\mathcal{A}$.

Finally, the size of $\mathcal{A}$ is at most the $d$th power of the maximal
number of children of a vertex in $\mathcal{T}$, and so by (4) we see that

$|\mathcal{A}|\leq\exp\left(4d\sqrt{m\log
n}\right)\leq\exp\left(2^{20}\epsilon^{-2}\sqrt{m}(\log n)^{3/2}\right),$

and so (2) holds. ∎

##  3 Supersaturation and Stability Statements

For any abelian group $G$ and finite subsets $U,V\subset G$, define

$\alpha(U,V)=\max\\{|V^{\prime}|:V^{\prime}\subset
G,\,|V^{\prime}|\leq|V|,\,|\langle
V^{\prime}\rangle|\leq|U|+|V|-|V^{\prime}|\\}.$

Here, $\langle V^{\prime}\rangle$ denotes the subgroup of $G$ generated by
$V^{\prime}$. For an element $x\in G$, the number of _representations_ of $x$
in $U+V$ will be denoted by $r_{U,V}(x)=|\\{(u,v)\in U\times V:u+v=x\\}|$.

The following theorem is a variant, due to Campos [5], of a generalization of
Pollard’s theorem proved by Hamidoune and Serra [14].

######  Proposition 3.1 (Theorem 3.2 in [5]).

Let $G$ be an abelian group, $t$ be a positive integer and $U,V\subset G$
satisfying $t\leq|V|\leq|U|<\infty$. Then

$\sum_{x\in U+V}\min(r_{U,V}(x),t)\geq t(|U|+|V|-t-\alpha),$ (5)

where $\alpha=\alpha(U,V)$.

This can be used to get the following supersaturation result for sets of
distinct sizes. Recall that $\beta(t)$ denotes the cardinality of the largest
subgroup of $G$ of order at most $t$.

######  Corollary 3.2.

Let $G$ be an abelian group, $A_{1},A_{2},B\subset G$ be finite and non-empty
subsets of $G$ and $0<\epsilon<1/2$, and denote
$\beta=\beta((1+4\varepsilon)|B|)$. If

$|A_{1}|+|A_{2}|\geq(1+2\epsilon)(|B|+\beta),$

then there are at least $\epsilon^{2}|A_{1}||A_{2}|$ pairs $(a_{1},a_{2})\in
A_{1}\times A_{2}$ such that $a_{1}+a_{2}\not\in B$.

###### Proof.

Without loss of generality we can assume $|A_{2}|\geq|A_{1}|$. If
$|B|\leq(1-\epsilon^{2})|A_{2}|$, then since $r_{A_{1},A_{2}}(b)\leq|A_{1}|$
for every fixed $b\in B$, we have at least

$|A_{1}||A_{2}|-|B||A_{1}|\geq\epsilon^{2}|A_{1}||A_{2}|$

pairs $(a_{1},a_{2})\in A_{1}\times A_{2}$ such that $a_{1}+a_{2}\not\in B$.
So we can assume $|B|>(1-\epsilon^{2})|A_{2}|$, which also implies
$|A_{1}|\geq\epsilon|A_{2}|$. Now applying Proposition 3.1 with
$t=\epsilon|A_{2}|$, $U=A_{2}$ and $V=A_{1}$ gives us

$\sum_{x\in
A_{1}+A_{2}}\min(r_{A_{1},A_{2}}(x),\epsilon|A_{2}|)\geq\epsilon|A_{2}|(|A_{1}|+(1-\epsilon)|A_{2}|-\alpha)$

and hence

$\sum_{x\in(A_{1}+A_{2})\setminus
B}\min(r_{A_{1},A_{2}}(x),\epsilon|A_{2}|)\geq\epsilon|A_{2}|(|A_{1}|+(1-\epsilon)|A_{2}|-|B|-\alpha).$
(6)

We will show that

$\alpha\leq\max(\beta,\,|A_{1}|+|A_{2}|-(1+4\epsilon)|B|).$

Indeed, suppose $A^{\prime}\subset G$ satisfies $|A^{\prime}|\leq|A_{1}|$ and
$|\langle A^{\prime}\rangle|\leq|A_{1}|+|A_{2}|-|A^{\prime}|$. If
$|A^{\prime}|\leq\beta$ we are done, so suppose $|A^{\prime}|>\beta$, and
hence $|\langle A^{\prime}\rangle|\geq(1+4\epsilon)|B|$ by definition of
$\beta$. So $A^{\prime}$ satisfies

$|A^{\prime}|\leq|A_{1}|+|A_{2}|-|\langle
A^{\prime}\rangle|\leq|A_{1}|+|A_{2}|-(1+4\epsilon)|B|,$

which is what we wanted to show. Now note that since $\epsilon<1/2$ and
$|B|\geq(1-\epsilon^{2})|A_{2}|$ we have $4|B|>3|A_{2}|$ and hence

$|A_{1}|+(1-\epsilon)|A_{2}|-|B|-(|A_{1}|+|A_{2}|-(1-4\epsilon)|B|)=4\epsilon|B|-\epsilon|A_{2}|>2\epsilon|A_{2}|>\epsilon|A_{1}|.$

Similarly, since $|A_{1}|+|A_{2}|\geq(1+2\epsilon)(|B|+\beta)$ and
$\epsilon<1/2$ we have

$\displaystyle|A_{1}|+(1-\epsilon)|A_{2}|-|B|-\beta$
$\displaystyle\geq|A_{1}|+(1-\epsilon)|A_{2}|-\frac{|A_{1}|+|A_{2}|}{1+2\epsilon}$
$\displaystyle>|A_{1}|+(1-\epsilon)|A_{2}|-(1-\epsilon)(|A_{1}|+|A_{2}|)$
$\displaystyle=\epsilon|A_{1}|.$

Hence (6) implies

$\sum_{x\in(A_{1}+A_{2})\setminus
B}r_{A_{1},A_{2}}(x)\geq\epsilon^{2}|A_{1}||A_{2}|.$

∎

Next we are going to prove a statement giving us structural information on
sets with (very) small sumsets that will later be applied to the containers
obtained from Theorem 2.2. As stated in the introduction, this comes in the
form of Freiman’s $3k-4$ theorem [9] and more specifically its asymmetric
version due to Lev and Smeliansky [19]. In the context of the container
approach, what is actually needed are so-called _robust_ versions of these
results, that is, we want to obtain structural knowledge on sets $U,V$ in a
group $G$ knowing only that $\\{u+v:(u,v)\in\Gamma\\}$ is small for some
subset $\Gamma\subset U\times V$ that is large but not necessarily the full
product.

Prior results of such type in the literature were mainly concerned with
handling the case of sets having the same cardinality. Note that this would
even be an issue if we stipulated that $s_{1}=s_{2}$ in Theorem 1.2. The
problem here is that while the pairs of sets that are counted may have the
same size, the containers obtained via Theorem 2.2 might differ slightly. We
modify the recently obtained robust version of Freiman’s $3k-4$ theorem by
Shao and Xu [25], which itself built on earlier work by Lev [18] to handle
this, and obtain the following stability result.

For subsets $U,V$ of some abelian group $G$ and $\Gamma\subset U\times V$,
denote by

$U\stackrel{{\scriptstyle\Gamma}}{{+}}V=\\{u+v\in G:(u,v)\in\Gamma\\}$

the restricted sumset of $U$ and $V$.

######  Theorem 3.3.

Let $0<\epsilon<1/2$ and let $U,V$ be finite subsets of $\mathbb{Z}$ with
$N=\min\\{|U|,|V|\\}\geq 3$ and $M=\max\\{|U|,|V|\\}\geq 2/\sqrt{\epsilon}$.
Let $\Gamma\subset U\times V$ with $|\Gamma|\geq(1-\epsilon)|U||V|$ and

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|=|U|+|V|+r.$

If

$r<\frac{N}{2}-13\sqrt{\epsilon}M,$ (7)

then there are arithmetic progressions $P$ and $Q$ with the same common
difference and lengths
$|P|\leq|U|+r+5\sqrt{\epsilon}M,|Q|\leq|V|+r+5\sqrt{\epsilon}M$ such that
$|P\cap U|\geq(1-\sqrt{\epsilon})|U|$ and $|Q\cap
V|\geq(1-\sqrt{\epsilon})|V|$.

Let us start by discussing some aspects of this result. The best upper bound
for $r$ in (7) that one might possibly obtain is of the form $N$, the
cardinality of the smaller set. This is true even in the case of
$\Gamma=U\times V$ where at least in the integers this is actually achieved by
the results due to Lev and Smeliansky [19] as well as Stanchescu [26].
Similarly in the special case of $N=M$, that is, both sets are of the same
cardinality, Shao in [24] was recently able to establish a similar robust
result. He achieved this by first proving a new version of the _Balog-
Szemerédi-Gowers Theorem_ [2, 11] and then directly applying the classical
results of Lev–Smeliansky and Stanchescu.

We will soon discuss different proof approaches (including ours) to statements
like Theorem 3.3. Before that, we first apply it to get something needed for
our particular application.

######  Corollary 3.4.

Let $s_{1}\leq s_{2}$ be positive integers, and $0<\epsilon\leq
2^{-8}\left(\frac{s_{1}}{s_{1}+s_{2}}\right)^{2}$. If
$A_{1},A_{2},B\subset\mathbb{Z}$, such that
$(1-\epsilon)|B|\leq|A_{1}|+|A_{2}|$ and
$|A_{i}|\leq\left(\frac{s_{i}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)|B|$ for
$i=1,2$, then one of the following holds:

  1. 1.

There are at least $\epsilon^{2}|A_{1}||A_{2}|$ pairs $(a_{1},a_{2})\in
A_{1}\times A_{2}$ such that $a_{1}+a_{2}\not\in B$.

  2. 2.

There are arithmetic progressions $P_{1},P_{2}$ of length
$|P_{i}|\leq\frac{s_{i}}{s_{1}+s_{2}}|B|+4\sqrt{\epsilon}|B|$ with the same
common difference such that $P_{i}$ contains all but at most $\epsilon|A_{i}|$
points of $A_{i}$.

###### Proof.

Let $\Gamma=\\{(a_{1},a_{2})\in A_{1}\times A_{2}:a_{1}+a_{2}\in B\\}$. If
$|\Gamma|<(1-\epsilon^{2})|A_{1}||A_{2}|$ case 1 holds, so assume the
converse. For $0<\epsilon\leq
2^{-8}\left(\frac{s_{i}}{s_{1}+s_{2}}\right)^{2}$, it holds that

$\left(\frac{1}{2}+13\epsilon\right)\frac{s_{i}}{s_{1}+s_{2}}>\frac{s_{i}}{2(s_{1}+s_{2})}\geq
8\sqrt{\epsilon}\geq
5\sqrt{\epsilon}+\frac{31}{2}\epsilon-26\epsilon^{3/2}+13\epsilon^{2},$

which implies

$\frac{3}{2}\left(\frac{s_{i}}{s_{1}+s_{2}}-2\sqrt{\epsilon}-\epsilon\right)+(1-13\epsilon)\left(1-\frac{s_{i}}{s_{1}+s_{2}}-2\sqrt{\epsilon}-\epsilon\right)>1.$

Since

$|A_{i}|\geq(1-\epsilon)|B|-\left(\frac{s_{3-i}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)|B|=\left(\frac{s_{i}}{s_{1}+s_{2}}-\epsilon-2\sqrt{\epsilon}\right)|B|,$

it thus follows that

$\displaystyle|A_{1}\stackrel{{\scriptstyle\Gamma}}{{+}}A_{2}|$
$\displaystyle\leq|B|$
$\displaystyle\leq\frac{3}{2}\left(\frac{s_{i}}{s_{1}+s_{2}}-2\sqrt{\epsilon}-\epsilon\right)|B|+(1-13\epsilon)\left(1-\frac{s_{i}}{s_{1}+s_{2}}-2\sqrt{\epsilon}-\epsilon\right)|B|$
$\displaystyle\leq\frac{3}{2}|A_{i}|+(1-13\epsilon)|A_{3-i}|.$

We can thus apply Theorem 3.3 with $\epsilon^{2}$ in place of $\epsilon$. Note
that since $s_{2}\geq s_{1}$, both $|A_{1}|$ and $|A_{2}|$ are upper bounded
by $(\frac{s_{2}}{s_{1}+s_{2}}+2\sqrt{\epsilon})|B|$, and so the theorem
implies that there exist arithmetic progressions $P_{1}$, $P_{2}$ with the
same common difference of length

$\displaystyle|P_{i}|$
$\displaystyle\leq|A_{1}\overset{\Gamma}{+}A_{2}|-|A_{3-i}|+5\epsilon\left(\frac{s_{2}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)|B|$
$\displaystyle\leq|B|-\left(\frac{s_{i}}{s_{1}+s_{2}}-\epsilon-2\sqrt{\epsilon}\right)|B|+5\epsilon\left(\frac{s_{2}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)|B|$
$\displaystyle\leq\frac{s_{i}}{s_{1}+s_{2}}|B|+4\sqrt{\epsilon}|B|$

such that

$|A_{i}\setminus P_{i}|=|A_{i}|-|A_{i}\cap P_{i}|\leq\epsilon|A_{i}|,$

so case 2 holds. ∎

### Proof of Theorem 3.3

Before going into specifics, let us discuss the general idea behind our proof
strategy of Theorem 3.3, which follows the outline already used by Lev [18,
17] as well as Shao–Xu [25]. The first main insight is that as long as the set
$\Gamma\subset U\times V$ satisfies some specific regularity conditions, one
can map $U$ and $V$ to an appropriate cyclic group and lower bound the
cardinality of $U\stackrel{{\scriptstyle\Gamma}}{{+}}V$ not only by its
projection. Instead, one also gets an additional translate of the “shorter”
set among $U$ and $V$. One then obtains the desired results by investigating
the projection more closely. When this projection fills out all of the cyclic
group, one uses Kneser’s theorem in abelian groups [15], a classical result in
additive number theory. In case the projection is not the full group one
instead needs a robust version of Kneser’s theorem. Such a result was proved
by Lev in [18] when $U=V$ (but even in nonabelian groups) and more recently by
Shao and Xu [25] when $U$ and $V$ are distinct but of the same cardinality. As
stated before, we follow this general outline and therefore prove a similar
result for sets of distinct cardinalities, Theorem 3.6. This theorem is of
independent interest since in addition to being a key aspect in the proof of
Theorem 3.3 it also has several other implications as already investigated in
[25].

As mentioned before, this is not the only approach to establishing a statement
like Theorem 3.3. In particular, Shao in [24] provided a framework that allows
one to transfer an arbitrary structural result for sumsets of two sets of the
same cardinality to a robust version with essentially the same quantitative
bounds. In fact, his statements also hold in the more general setting when
both sets only differ by a fixed multiplicative constant, or alternatively for
pairs of sets of arbitrary cardinalities when imposing stronger upper bounds
on the size of the restricted sumset. Another approach that lies in between
these two strategies might be to only replace the use of the robust version of
Kneser’s theorem in Lev’s approach. As will become apparent in the sequel,
this is currently the bottleneck for improving the quantitative aspects of (7)
in Theorem 3.3.

We will now go into the technical details of the proof, starting with defining
the exact concept of regularity that we require. We may think of
$\Gamma\subset U\times V$ as a subgraph of the complete bipartite graph
$K_{|U|,|V|}$ where the edges $(u,v)$ are colored by the element $c=u+v\in G$.
The language of graphs will be handy, and in this way $d_{\Gamma}(x)$ and
$N_{\Gamma}(x)$ will denote the degree (resp. neighborhood) of some vertex
$x$. Following Lev [18], we introduce the following definition.

######  Definition 3.5.

Let $U,V$ be two finite sets in an abelian group and $K,s$ non-negative
integers. A subset $\Gamma\subset U\times V$ is _$(K,s)$ -regular_ if the
following two things are true:

  1. (i)

$d_{\Gamma}(u)\geq|V|-s$ for each $u\in U$ and $d_{\Gamma}(v)\geq|U|-s$ for
each $v\in V$.

  2. (ii)

For any $c\in U+V$ with $r_{U,V}(c)\geq K$, it holds that $c\in
U\stackrel{{\scriptstyle\Gamma}}{{+}}V$.

We will now prove the previously mentioned robust version of Kneser’s theorem
which is effective even for sets of very different sizes. This can be compared
to Proposition 3.1 in [25] as well as Theorem 2 in [18] in the abelian case,
which have slightly better constants when the sets are close in size.

######  Theorem 3.6.

Let $U,V$ be finite sets in an abelian group $G$ with $|U|\leq|V|$ and let
$K,s$ be non-negative integers. If $\Gamma\subset U\times V$ is
$(K,s)$-regular and $U\stackrel{{\scriptstyle\Gamma}}{{+}}V\neq U+V,$ then

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|V|+\frac{|U|}{2}-K-2s.$

It would be interesting to know whether one can improve the $|U|/2$ term in
Theorem 3.6 to $|U|$ instead. Even in their less general settings, both Lev
and Shao–Xu were only able to replace the constant $1/2$ by the golden ratio.
As will become apparent in the proofs of Proposition 3.7 this would result in
an immediate quantitative improvement in the upper bound (7) in Theorem 3.3.
It would also confirm a conjecture posed by Lev in [18]. Note further that the
non-triviality of such a statement clearly depends on the choices of $K$ and
$s$. For instance, whenever $K+s\geq|U|/2$, Theorem 3.6 tells us that the
restricted sumset is larger than $|V|-s$, which is a trivial lower bound
obtained from $(K,s)$-regularity looking at only the neighborhood of a single
element $u\in U$ in $\Gamma$. So the interesting cases are when $K$ and $s$
are both small enough compared to $|U|$. Conversely, very small $K$ and $s$
will almost certainly result in either the full and restricted sumsets being
the same (and hence the statement holding vacuously) or both their
cardinalities being closer to the product rather than the sum of the two sets.

###### Proof of Theorem 3.6.

Suppose the statement is false and take a counterexample that minimizes $|U|$,
the cardinality of the smaller set. Note that we can assume that the graph
$\Gamma$ is _saturated_ , meaning that if some color $\sigma\in U+V$ is
contained in $U\stackrel{{\scriptstyle\Gamma}}{{+}}V$, then in fact all edges
$(u,v)\in U\times V$ with $u+v=\sigma$ are contained in $\Gamma$. We start by
showing that for any $u,u^{\prime}\in U$, the distance $u-u^{\prime}$ has many
representations in $V-V$. To do this, note that since $\Gamma$ is
$(K,s)$-regular, we have
$|(u+V)\setminus(U\stackrel{{\scriptstyle\Gamma}}{{+}}V)|\leq s$, and
similarly if we replace $u$ by $u^{\prime}$. So

$|(u+V)\cup(u^{\prime}+V)|\leq|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|+2s<|V|+\frac{|U|}{2}-K,$

which implies

$r_{V,-V}(u-u^{\prime})=|(u+V)\cap(u^{\prime}+V)|=2|V|-|(u+V)\cup(u^{\prime}+V)|>|V|-\frac{|U|}{2}+K.$
(8)

Next, we will show that there are many popular colors in $\Gamma$. For this,
define the set $P$ by

$P=\left\\{\sigma\in
U\stackrel{{\scriptstyle\Gamma}}{{+}}V:r_{U,V}(\sigma)\geq|U|/2\right\\}.$

Note that $\Gamma$ is saturated, so the number of representations in
$U\stackrel{{\scriptstyle\Gamma}}{{+}}V$ and $U+V$ is identical for every
color that actually appears.

The motivation for studying $P$ will be that in fact, if an element $v\in V$
“sees” a single popular color, one can show that it actually has all of $U$ as
its neighborhood and hence any missing color (which exists by assumption) is
“surrounded” only by unpopular colors. This will result in an induced subgraph
of $\Gamma$ that represents a smaller counterexample which runs counter to the
minimality assumption in the beginning. Let us be more precise.

By $(K,s)$-regularity and the assumed upper bound on
$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|$, we have

$\displaystyle|U|(|V|-s)$ $\displaystyle\leq|\Gamma|$
$\displaystyle=\sum_{\sigma\in P}r_{U,V}(\sigma)+\sum_{\sigma\notin
P}r_{U,V}(\sigma)$
$\displaystyle<|P||U|+\left(|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|-|P|\right)\frac{|U|}{2}$
$\displaystyle<|P|\frac{|U|}{2}+\left(|V|+\frac{|U|}{2}-K-2s\right)\frac{|U|}{2},$

which can be rearranged to get

$|P|>|V|-\frac{|U|}{2}+K.$ (9)

Next, we will show that for every $v\in V$ with $(U+v)\cap P\neq\emptyset$, we
in fact have

$U+v\subset U\stackrel{{\scriptstyle\Gamma}}{{+}}V.$ (10)

To see this, suppose $u_{0}+v\in P$. By the definition of $P$, there is a set
${\mathcal{P}}_{0}\in U\times V$ with $|{\mathcal{P}}_{0}|\geq|U|/2$ such that
$u^{\prime}+v^{\prime}=u_{0}+v$ for each
$(u^{\prime},v^{\prime})\in{\mathcal{P}}_{0}$. Note that since $u_{0}+v$ was
fixed, the second components of these tuples are all pairwise distinct. Let
$u\in U$ be chosen arbitrarily. It follows from (8) that there is a set
${\mathcal{P}}_{1}\in V\times V$ with
$|{\mathcal{P}}_{1}|\geq|V|-\frac{|U|}{2}+K$ such that
$v^{\prime\prime}-v^{\prime}=u-u_{0}$ for each
$(v^{\prime},v^{\prime\prime})\in{\mathcal{P}}_{1}$. Again, $u$ and $u_{0}$
are fixed, and hence the first components of these tuples are pairwise
distinct as well. Hence by inclusion-exclusion, there are at least $K$ pairs
in ${\mathcal{P}}_{0}$ whose second coordinate coincides with the first
coordinate of some pair in ${\mathcal{P}}_{1}$. Each two such pairs
$((u^{\prime},v^{\prime}),(v^{\prime},v^{\prime\prime}))\in{\mathcal{P}}_{0}\times{\mathcal{P}}_{1}$
define the relation
$(u^{\prime}+v^{\prime})+(v^{\prime\prime}-v^{\prime})=(u_{0}+v)+(u-u_{0})=v+u$,
implying that

$r_{U,V}(u+v)\geq K,$

and so $u+v\in U\stackrel{{\scriptstyle\Gamma}}{{+}}V$ by $(K,s)$-regularity.
Since the choice of $u$ is arbitrary, this proves (10).

Let $V^{\prime}\subset V$ be the set of elements $v$ such that $(U+v)\cap
P=\emptyset$. Then

$\Gamma\cap(U\times(V\setminus V^{\prime}))=U\times(V\setminus V^{\prime}),$

so since $U\stackrel{{\scriptstyle\Gamma}}{{+}}V\neq U+V,$ we must have
$U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}\neq U+V^{\prime}$,
where $\Gamma^{\prime}=\Gamma\cap(U\times V^{\prime})$ is the induced subgraph
of $\Gamma$ on $U\times V^{\prime}$. Furthermore, $\Gamma^{\prime}$ is
$(K,s)$-regular: Firstly, it is clear that at most $s$ edges are missing in
the neighborhood of every vertex, since this was the case for $\Gamma$.
Secondly, suppose $x\in U+V^{\prime}$ is an element such that
$r_{U,V^{\prime}}(x)\geq K$. Then since $V^{\prime}\subset V$, $r_{U,V}(x)\geq
K$, and so $x\in U\stackrel{{\scriptstyle\Gamma}}{{+}}V$. Since $\Gamma$ was
saturated, _every_ edge that represented $x$ was included, and hence $x\in
U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}$.

Next we will show that $|U|>|V^{\prime}|$. To see this, first note that we
have the trivial lower bound

$|U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|\geq|V^{\prime}|-s,$

by using $(K,s)$-regularity and looking at the neighborhood of a single vertex
of $U$ in $\Gamma^{\prime}$. On the other hand, every color in
$U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}$ is contained in
$(U\stackrel{{\scriptstyle\Gamma}}{{+}}V)\setminus P$, and by (9) we thus have

$|U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|\leq|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|-|P|<|V|+\frac{|U|}{2}-2s-K-\left(|V|-\frac{|U|}{2}+K\right)=|U|-2s-2K.$

Combining these inequalities implies

$|U|>|V^{\prime}|+s+2K,$

so in particular $|U|>|V^{\prime}|$. Since $U$ and $V$ represented a
counterexample that minimized the cardinality of the smaller set, we must have

$|U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|\geq|U|+\frac{|V^{\prime}|}{2}-2s-K.$
(11)

But then by combining (9) and (11),

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|P|+|U\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|>|V|+\frac{|U|}{2}-2s+\frac{|V^{\prime}|}{2}>|V|+\frac{|U|}{2}-2s-K,$

a contradiction. ∎

We next prove a technical intermediate result in the group of integers that is
comparable to Theorem 1 in [18] due to Lev as well as Proposition 2.2 in [25]
due to Shao and Xu. The proof follows essentially the same arguments, using
Theorem 3.6 instead of other robust versions of Kneser’s theorem, as well as
being slightly more careful about the distinct set sizes. The proof consists
of two parts. First, as previously mentioned, one shows that
$(K,s)$-regularity will imply that, after projecting the restricted sumset
into an appropriate cyclic group, one can lower bound the size of the original
sumset by its projection plus one copy of the shorter set. Appropriate here
means that it will be large enough to contain both sets without any new
collisions, but small enough to still get an extra copy of the shorter set.
The second part then analyzes the projected restricted sumset more closely.

For a finite set of integers $U$ we denote its convex hull by
$[U]=[\min(U),\max(U)]$.

######  Proposition 3.7.

Let $U,V$ be two finite sets of integers. Assume that $\gcd(U\cup V)=1$ and
that $[U]=[0,\ell],[V]=[0,\ell^{\prime}]$, where $\ell^{\prime}\leq\ell$. Let
$n=\min\\{|U|,|V|\\}$.

Let $K\geq 2$, $s\geq 0$ and let $\Gamma\subset U\times V$ be $(K,s)$-regular.
Then,

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq\begin{cases}\ell+|V|-2s,&\ell\leq|U|+|V|-2K-2\\\
|U|+|V|+\frac{n}{2}-4s-2K-2,&\ell>|U|+|V|-2K-2.\end{cases}$

###### Proof.

Let $f:\mathbb{Z}\to\mathbb{Z}/\ell\mathbb{Z}$ be the canonical projection. We
write $f(x)=\tilde{x}$ and a similar notation for images of sets. From
$U,V,\Gamma$ we build the modular version $\tilde{U},\tilde{V},\tilde{\Gamma}$
in $\mathbb{Z}/\ell\mathbb{Z}$. We have $|\tilde{U}|\geq|U|-1$ and
$|\tilde{V}|\geq|V|-1$.

######  Claim.

$\tilde{\Gamma}$ is $(2K,s)$-regular.

###### Proof.

The $s$ missing edges incident to each vertex in $\Gamma$ produce at most $s$
missing edges incident to $\tilde{x}$ in $\tilde{\Gamma}$. On the other hand,
since $\ell=\max(U)\geq\max(V)$, the preimage of each color different from
zero in $\tilde{U}\times\tilde{V}$ produces at most two colors in $U\times V$.
Hence, every nonzero color appearing at least $2K$ times in
$\tilde{U}\times\tilde{V}$ must be present in $\Gamma$ and therefore it must
also be present in $\tilde{\Gamma}$. If $\tilde{0}$ appears more than $2K$
times in $\tilde{U}\times\tilde{V}$, since $0$ and $2\ell$ appear at most one
time in $U\times V$ and $K\geq 2$, then $\ell$ must appear at least $K$ times
and the color is in $\Gamma$ (and hence in $\tilde{\Gamma}$). Thus
$\tilde{\Gamma}$ is $(2K,s)$–regular. ∎

Now note that for every element $c\in N_{\Gamma}(0)\cap
N_{\Gamma}(\ell)\subset V$, $c$ and $c+\ell$ are distinct elements in
$U\stackrel{{\scriptstyle\Gamma}}{{+}}V$, but are mapped to the same element
in $\mathbb{Z}/\ell\mathbb{Z}$. Since $|N_{\Gamma}(u)|\geq|V|-s$ for any $u\in
U$ by $(K,s)$-regularity, using inclusion exclusion we see that

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}|+|N_{\Gamma}(0)\cap
N_{\Gamma}(\ell)|\geq|\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}|+|V|-2s.$
(12)

We are now going to analyze different cases and show that in all of these,
Equation (12) will imply the theorem statement.

#### Case 1: $\ell\leq|U|+|V|-2K-2$.

In this case every $\tilde{x}\in\mathbb{Z}/\ell\mathbb{Z}$ appears in
$\tilde{U}\times\tilde{V}$ at least

$\displaystyle|\tilde{U}\cap(\tilde{x}-\tilde{V})|$
$\displaystyle=|\tilde{U}|+|\tilde{V}|-|\tilde{U}\cup(\tilde{x}-\tilde{V})|$
$\displaystyle\geq|\tilde{U}|+|\tilde{V}|-\ell$
$\displaystyle\geq|U|+|V|-2-\ell$ $\displaystyle\geq 2K,$

times, and hence it appears in $\tilde{\Gamma}$ by $(2K,s)$-regularity.
Therefore,
$\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}=\mathbb{Z}/\ell
Z$ and (12) gives

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq\ell+|V|-2s,$

as claimed.

#### Case 2: $\ell>|U|+|V|-2K-2$ and
$\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}\neq\tilde{U}+\tilde{V}$.

In this case we can apply Theorem 3.6 and see that

$|\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}|\geq\max\\{|\tilde{U}|,|\tilde{V}|\\}+\frac{n-1}{2}-2K-2s\geq|U|+\frac{n}{2}-2K-2s-\frac{3}{2},$

and (12) yields

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|U|+|V|+\frac{n}{2}-2K-4s-\frac{3}{2},$

as claimed.

#### Case 3: $\ell>|U|+|V|-2K-2$ and
$\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}=\tilde{U}+\tilde{V}$.

Here there will essentially be two sub-cases. The easier one is if the
restricted sumset is large. Specifically, if
$|\tilde{U}+\tilde{V}|\geq|\tilde{U}|+(n-1)/2$, then again (12) yields

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|\tilde{U}+\tilde{V}|+|V|-2s\geq|U|+|V|+\frac{n}{2}-2s-\frac{3}{2},$

and we are done.

Suppose now that $|\tilde{U}+\tilde{V}|<|\tilde{U}|+(n-1)/2$. Then Kneser’s
theorem [15] implies that there is a nonzero subgroup $H\leq G$ such that
$\tilde{U}+\tilde{V}+H=\tilde{U}+\tilde{V}$ and

$|\tilde{U}+\tilde{V}|=|\tilde{U}+H|+|\tilde{V}+H|-|H|.$ (13)

If $H=\mathbb{Z}/\ell Z$, then (12) with our current hypothesis
$\ell\geq|U|+|V|-2K-2$ gives the conclusion with room to spare. Suppose that
$H$ is a proper subgroup. We now repeat the adaptation by Shao and Xu of Lev’s
argument. Let

$\displaystyle C_{1}$ $\displaystyle=\\{c\in
U\stackrel{{\scriptstyle\Gamma}}{{+}}V:\tilde{c}\in\tilde{V}\\},$
$\displaystyle C_{2}$ $\displaystyle=\\{c\in
U\stackrel{{\scriptstyle\Gamma}}{{+}}V:\tilde{c}\in(\tilde{V}+H)\setminus\tilde{V}\\},\text{
and}$ $\displaystyle C_{3}$ $\displaystyle=\\{c\in
U\stackrel{{\scriptstyle\Gamma}}{{+}}V:\tilde{c}\in(\tilde{U}+\tilde{V})\setminus(\tilde{V}+H)\\},$

which are pairwise disjoint since $0\in(H\cap\tilde{U}\cap\tilde{V})$ implies
$\tilde{V}\subset(\tilde{V}+H)\subset(\tilde{U}+\tilde{V})$.

Using the same argument that was used to justify (12) and noting that
$\tilde{V}\subset\tilde{U}+\tilde{V}=\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}$,
we have

$|C_{1}|\geq|\tilde{V}|+|V|-2s.$ (14)

For $C_{2}$, note that since
$\tilde{U}\stackrel{{\scriptstyle\tilde{\Gamma}}}{{+}}\tilde{V}=\tilde{U}+\tilde{V}$,
every element in $(\tilde{V}+H)\setminus\tilde{V}\subset\tilde{U}+\tilde{V}$
has a preimage in $U\stackrel{{\scriptstyle\Gamma}}{{+}}V$, so that

$|C_{2}|\geq|\tilde{V}+H|-|\tilde{V}|.$ (15)

We start by showing that in certain cases we can obtain a good lower bound on
$|\tilde{V}+H|$ and hence prove the theorem statement using only $C_{1}$ and
$C_{2}$. Since $\gcd(U\cup V)=1$ and $0\in U\cap V$, it cannot happen that
both $\tilde{U}$ and $\tilde{V}$ are contained in a single coset of $H$ since
we assumed that $H\neq\mathbb{Z}/\ell\mathbb{Z}$.

We are now going to investigate different cases. Suppose first that
$\tilde{U}$ is contained in a single coset of $H$, that is $\tilde{U}+H=H$.
Again, recall that since $0\in\tilde{U}\cap\tilde{V}$ and the previous
observation, this means that $\tilde{V}$ intersects at least two distinct
cosets of $H$. That is, we have

$|\tilde{V}+H|\geq 2|H|\geq|\tilde{U}|+n-1,$

so that

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|C_{1}|+|C_{2}|\geq|\tilde{V}+H|+|V|-2s\geq|U|+|V|+n-2s-2$

and we are done.

Assume now that $\tilde{U}+H\neq H$, that is, $\tilde{U}$ intersects at least
two cosets of $H$. This case will be more involved and in particular we will
need $C_{3}$ to establish the theorem statement. Let
$N=|(\tilde{U}+\tilde{V})\setminus(\tilde{V}+H)|/|H|$ be the number of cosets
of $H$ inside $\tilde{U}+\tilde{V}=\tilde{U}+\tilde{V}+H$ but outside
$\tilde{V}+H$. By Kneser’s theorem there is at least one such coset, say
$\tilde{u}+\tilde{v}+H$ with $\tilde{u}\not\in H$. Note that this implies

$f^{-1}(\tilde{u}+\tilde{v}+H)\cap(U\stackrel{{\scriptstyle\Gamma}}{{+}}V)\subset
C_{3}.$ (16)

Let $U^{\prime}=f^{-1}(\tilde{u}+H)\cap U$ and
$V^{\prime}=f^{-1}(\tilde{v}+H)\cap V$ the elements of $U$ and $V$ that are
projected into these respective cosets. Then $U^{\prime}+V^{\prime}\subset
f^{-1}(\tilde{u}+\tilde{v}+H)\cap(U+V)$. On the other hand we see that
$U^{\prime}+V^{\prime}$ contains the $|U^{\prime}|+|V^{\prime}|-1$ pairwise
distinct elements of the form

$\min(U^{\prime})+V^{\prime}\quad\text{and}\quad U^{\prime}+\max(V^{\prime}).$

Since $\Gamma$ is $(K,s)$-regular and the above elements only live in the
neighborhood of two vertices, at most $2s$ of these elements can be missing
from $U\stackrel{{\scriptstyle\Gamma}}{{+}}V$, and hence

$|f^{-1}(\tilde{u}+\tilde{v}+H)\cap(U\stackrel{{\scriptstyle\Gamma}}{{+}}V)|\geq|U^{\prime}|+|V^{\prime}|-2s-1.$
(17)

By inserting in (17) the estimates

$|H|-|U^{\prime}|\leq|(\tilde{U}+H)\setminus\tilde{U}|,\;\;|H|-|V^{\prime}|\leq|(\tilde{V}+H)\setminus\tilde{V}|,$

and using (13) we thus obtain

$\displaystyle|f^{-1}(\tilde{u}+\tilde{v}+H)\cap(U\stackrel{{\scriptstyle\Gamma}}{{+}}V)|$
$\displaystyle\geq
2|H|+|\tilde{U}|+|\tilde{V}|-|\tilde{U}+H|-|\tilde{V}+H|-2s-1$ (18)
$\displaystyle=|H|+|\tilde{U}|+|\tilde{V}|-|\tilde{U}+\tilde{V}|-2s-1.$

We see that clearly, (16) and (18) hold for every of the $N$ pairwise distinct
cosets $\tilde{u}+\tilde{v}+H$ outside of $\tilde{V}+H$. Furthermore, we also
have that the sets $f^{-1}(\tilde{u}+\tilde{v}+H)$ are disjoint for distinct
cosets. We can hence combine (16) and (18) to lower bound the cardinality of
$C_{3}$ as follows, using the definition of $N$ as well as the fact that
$N\geq 1$.

$\displaystyle|C_{3}|$ $\displaystyle\geq
N(|H|+|\tilde{U}|+|\tilde{V}|-|\tilde{U}+\tilde{V}|-2s-1)$ (19)
$\displaystyle\geq N|H|+(|\tilde{U}|+|\tilde{V}|-|\tilde{U}+\tilde{V}|-2s-1)$
$\displaystyle=|(\tilde{U}+\tilde{V})\setminus(\tilde{V}+H)|+(|\tilde{U}|+|\tilde{V}|-|\tilde{U}+\tilde{V}|-2s-1)$
$\displaystyle=|\tilde{U}|+|\tilde{V}|-|\tilde{V}+H|-2s-1.$

Finally, combining (14), (15) and (19) yields

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|C_{1}|+|C_{2}|+|C_{3}|\geq|\tilde{U}|+|\tilde{V}|+|V|-4s-1\geq|U|+|V|+n-4s-3.$

This completes the proof. ∎

Now we can proceed with the proof of Theorem 3.3. For a finite set $X\subset
G$ we will denote by $\ell(X)$ the size of its convex hull, that is
$\ell(X)=\max(X)-\min(X)+1$.

###### Proof of Theorem 3.3.

We begin by extracting a large regular subgraph of $\Gamma$ in order to apply
Proposition 3.7. Let

$U^{\prime}=\\{u\in U:d_{\Gamma}(u)\geq(1-\sqrt{\epsilon})|V|\\},$

and observe that since

$(1-\epsilon)|U||V|\leq|\Gamma|\leq|U^{\prime}||V|+(1-\sqrt{\epsilon})(|U|-|U^{\prime}|)|V|,$

it holds that $|U^{\prime}|\geq(1-\sqrt{\epsilon})|U|$. Similarly, if
$V^{\prime}$ is the set of $v\in V$ with
$d_{\Gamma}(v)\geq(1-\sqrt{\epsilon})|U|$, we have
$|V^{\prime}|\geq(1-\sqrt{\epsilon})|V|$. If
$\Gamma_{1}=\Gamma\cap(U^{\prime}\times V^{\prime})$ is the restriction of
$\Gamma$, then for every $u\in U^{\prime}$ we see that

$d_{\Gamma_{1}}(u)=|N_{\Gamma}(u)\cap V^{\prime}|\geq
d_{\Gamma}(u)+|V^{\prime}|-|V|\geq|V^{\prime}|-\sqrt{\epsilon}|V|.$

Similarly, $d_{\Gamma_{1}}(v)\geq|U^{\prime}|-\sqrt{\epsilon}|U|$ for every
$v\in V^{\prime}$. We may assume that $[U^{\prime}]=[0,\ell(U^{\prime})]$,
$[V^{\prime}]=[0,\ell(V^{\prime})]$ and $\gcd(U^{\prime}\cup V^{\prime})=1$.
Furthermore, without loss of generality assume that

$\ell(U^{\prime})\geq\ell(V^{\prime}).$

We are almost in the position to apply Proposition 3.7. One reason why we
should not do it yet is that, if the shorter set is also the smaller one we
would run into issues. To prevent this, we introduce the following notion. For
a set $X$ with $[X]=[0,\ell(X)]$, denote by $h(X)=\ell(X)-|X|+1$ the number of
holes of $X$. We next split the remainder of the proof into two cases
depending on which of $U^{\prime}$ and $V^{\prime}$ contains more holes.

The intuition is that if the longer set also contains more holes, then
necessarily the shorter set must be larger and hence a straightforward
application of Proposition 3.7 will leads us to our goal. If on the other hand
the shorter set has more holes, we instead apply Proposition 3.7 only to an
appropriately truncated segment and get a single copy of the remainder “for
free”. Let us make this precise, starting with the easy case.

#### Case 1. $h(U^{\prime})>h(V^{\prime})$.

Set $K=s=\sqrt{\epsilon}M$, and define

$\Gamma^{\prime}=\Gamma_{1}\cup\\{(u,v)\in U^{\prime}\times
V^{\prime}:r_{U^{\prime},V^{\prime}}(u+v)\geq K\\}.$

Note that by doing this we have added at most

$\frac{(U^{\prime}\times V^{\prime})\setminus\Gamma_{1}}{K}\leq\frac{(U\times
V)\setminus\Gamma}{K}\leq\sqrt{\epsilon}N$

elements
$x\in(U^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime})\setminus(U^{\prime}\stackrel{{\scriptstyle\Gamma_{1}}}{{+}}V^{\prime})$,
and hence

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|U^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|-\sqrt{\epsilon}N.$
(20)

Since $\Gamma^{\prime}$ is $(K,s)$-regular by construction, we can apply
Proposition 3.7 to get

$|U^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|\geq\begin{cases}\ell(U^{\prime})+|V^{\prime}|-2s,&\ell(U^{\prime})\leq|U^{\prime}|+|V^{\prime}|-2K-2\\\
|U^{\prime}|+|V^{\prime}|+\frac{\min\\{|U^{\prime}|,|V^{\prime}|\\}}{2}-4s-2K-2,&\ell(U^{\prime})>|U^{\prime}|+|V^{\prime}|-2K-2.\end{cases}$
(21)

Note that by our lower bounds on $|U^{\prime}|,|V^{\prime}|$ and (20), the
second line of (21) would imply

$\displaystyle|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|$
$\displaystyle\geq|U^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|-\sqrt{\epsilon}N$
$\displaystyle\geq(1-\sqrt{\epsilon})(|U|+|V|+N/2)-6\sqrt{\epsilon}M-2-\sqrt{\epsilon}N$
$\displaystyle\geq|U|+|V|+\frac{N}{2}-11\sqrt{\epsilon}M,$

which violates our initial assumption on
$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|$, so the first case must hold. In
particular,

$\displaystyle\ell(U^{\prime})$
$\displaystyle\leq|U^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime}}}{{+}}V^{\prime}|-|V^{\prime}|+2\sqrt{\epsilon}M$
$\displaystyle\leq|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|-(1-\sqrt{\epsilon})|V|+2\sqrt{\epsilon}M+\sqrt{\epsilon}N$
$\displaystyle<|U|+r+4\sqrt{\epsilon}M,$

and similarly using $h(U^{\prime})>h(V^{\prime}),$

$\ell(V^{\prime})<\ell(U^{\prime})+|V^{\prime}|-|U^{\prime}|<|V|+r+4\sqrt{\epsilon}M.$

#### Case 2. $h(U^{\prime})\leq h(V^{\prime})$.

Define $U_{1}^{\prime}=U^{\prime}\cap[0,\ell(V^{\prime})]$,
$U_{2}^{\prime}=U^{\prime}\setminus U_{1}^{\prime}$ and
$\Gamma_{1}^{\prime}=\Gamma\cap(U_{1}^{\prime}\times V^{\prime})$. We see that
by definition of $V^{\prime}$ it holds that at most $\sqrt{\epsilon}|U|$ of
the $|U^{\prime}|$ elements in $U^{\prime}+\max(V^{\prime})$ are missing from
$U^{\prime}\stackrel{{\scriptstyle\Gamma_{1}}}{{+}}V^{\prime}$. This implies

$|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|\geq|U^{\prime}\stackrel{{\scriptstyle\Gamma_{1}}}{{+}}V^{\prime}|\geq|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma_{1}^{\prime}}}{{+}}V^{\prime}|+|U_{2}^{\prime}|-\sqrt{\epsilon}|U|.$
(22)

Since $h(U_{1}^{\prime})\leq h(U^{\prime})\leq h(V^{\prime})$ and
$\ell(U_{1}^{\prime})=\ell(V^{\prime})$ by construction, we have
$|U_{1}^{\prime}|\geq|V^{\prime}|$. Furthermore, by definition of
$U^{\prime}$, for every $u\in U_{1}^{\prime}$ it holds that
$d_{\Gamma_{1}^{\prime}}(u)\geq|V^{\prime}|-\sqrt{\epsilon}|V|$, and
similarly, $d_{\Gamma_{1}^{\prime}}(v)\geq|U_{1}^{\prime}|-\sqrt{\epsilon}|U|$
for every $v\in V^{\prime}$. Setting $K=s=\sqrt{\epsilon}M$ and defining

$\Gamma^{\prime\prime}=\Gamma_{1}^{\prime}\cup\\{(u,v)\in U_{1}^{\prime}\times
V^{\prime}:r_{U_{1}^{\prime},V^{\prime}}(u+v)\geq K\\},$

we again see that

$|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma_{1}^{\prime}}}{{+}}V^{\prime}|\geq|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime\prime}}}{{+}}V^{\prime}|-\sqrt{\epsilon}N.$
(23)

Again, $\Gamma^{\prime\prime}$ is $(K,s)$-regular by construction, and so
applying Proposition 3.7 we get

$|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime\prime}}}{{+}}V^{\prime}|\geq\begin{cases}\ell(V^{\prime})+|U_{1}^{\prime}|-2s,&\ell(V^{\prime})\leq|U^{\prime}|+|V^{\prime}|-2K-2\\\
\frac{3}{2}|V^{\prime}|+|U_{1}^{\prime}|-4s-2K-2,&\ell(V^{\prime})>|U^{\prime}|+|V^{\prime}|-2K-2.\end{cases}$
(24)

Putting together (23) and (22), the second line of this would imply

$\displaystyle|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|$
$\displaystyle\geq|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime\prime}}}{{+}}V^{\prime}|+|U_{2}^{\prime}|-\sqrt{\epsilon}|U|-\sqrt{\epsilon}N$
$\displaystyle\geq\frac{3}{2}|V^{\prime}|+|U^{\prime}|-10\sqrt{\epsilon}M$
$\displaystyle\geq|U|+|V|+\frac{N}{2}-13\sqrt{\epsilon}M,$

a contradiction to our initial assumption. Hence the first case of (24) must
hold, which implies

$\displaystyle\ell(V^{\prime})$
$\displaystyle\leq|U_{1}^{\prime}\stackrel{{\scriptstyle\Gamma^{\prime\prime}}}{{+}}V^{\prime}|-|U_{1}^{\prime}|+2\sqrt{\epsilon}M$
$\displaystyle\leq|U\stackrel{{\scriptstyle\Gamma}}{{+}}V|-|U^{\prime}|+4\sqrt{\epsilon}M$
$\displaystyle\leq|V|+r+5\sqrt{\epsilon}M.$

Since $h(U^{\prime})\leq h(V^{\prime})$, we also have

$\ell(U^{\prime})\leq\ell(V^{\prime})-|V^{\prime}|+|U^{\prime}|\leq|U|+r+5\sqrt{\epsilon}M.$

This completes the proof. ∎

##  4 Proofs of the Main Results

In this section we will prove more technical versions of Theorems 1.1 and 1.2.
We start with the structural result.

######  Theorem 4.1.

Let $s_{1},s_{2},n$ be integers and $\alpha>0$ a fixed real number satisfying

$s_{2}\geq s_{1}\geq 2^{10}\alpha^{-1}(s_{1}+s_{2})^{11/12}(\log n)^{1/4},$

and let $m$ be an integer such that

${(1+\alpha)(s_{1}+s_{2})\leq
m<2^{-108}\alpha^{12}s_{1}^{12}(s_{1}+s_{2})^{-10}(\log n)^{-3}.}$

Suppose $X_{1},X_{2}\subset[n]$ are two uniformly chosen random sets with
$|X_{1}|=s_{1}$, $|X_{2}|=s_{2}$ and $|X_{1}+X_{2}|\leq m$. With probability
at least ${1-\exp(-2^{5}m^{1/6}(s_{1}+s_{2})^{2/3}\sqrt{\log n})}$ the
following holds: there are sets $T_{i}\subset X_{i}$ of size ${|T_{i}|\leq
2^{11}\alpha^{-1}m^{1/6}(s_{1}+s_{2})^{2/3}\sqrt{\log n}}$, such that
$X_{i}\setminus T_{i}$ is contained in an arithmetic progression $P_{i}$ of
size

$\frac{s_{i}m}{s_{1}+s_{2}}+2^{6}m^{13/12}(s_{1}+s_{2})^{-1/6}(\log n)^{1/4},$

where $P_{1}$ and $P_{2}$ have the same common difference.

The presence of the $\alpha$ parameter is of a technical nature in the
following sense. If $m$ is very close to $s_{1}+s_{2}$, say
$m=(1+o(1))(s_{1}+s_{2})$, then some of the computations break down. In
particular it becomes difficult to apply a technical result, Lemma 4.2 which
we require to prove Theorem 4.1. On the other hand, from a moral standpoint it
should only help that the parameter $m$ is smaller. In fact, in many
situations such smaller values of $m$ can be handled directly by the
asymmetric version of Freiman’s $3k-4$ theorem, as detailed in the following
proof of Theorem 1.1 using Theorem 4.1.

###### Proof of Theorem 1.1.

If $m=(1+o(1))(s_{1}+s_{2})=s_{1}+s_{2}+o(s_{1})$, we can apply an appropriate
asymmetric version of Freiman’s $3k-4$ theorem (see for instance [19])
directly and see that any sets $X_{1}$, $X_{2}$ satisfying the theorem
hypotheses are contained in arithmetic progressions $P_{1}$ and $P_{2}$ with
the same common difference of size

$|P_{i}|=(1+o(1))s_{i}=(1+o(1))s_{i}m/(s_{1}+s_{2}).$

If on the other hand there exists some absolute constant $\alpha>0$ such that
$m\geq(1+\alpha)(s_{1}+s_{2})$, we can apply Theorem 4.1 instead. ∎

In order to prove Theorem 4.1, we need the following bound on the product of
two particular binomial coefficients which cannot be derived from available
and more generic bounds. The proof is straightforward but rather lengthy and
might distract somewhat from the main thrust of the paper, so we include it in
Appendix A.

######  Lemma 4.2.

Let $m$, $s$ and $t$ be positive integers and let $1\geq\alpha>0$ such that
$m\geq(1+\alpha)(s+t)$ and $s+t\geq 2^{5}\alpha^{-1}$. If $\epsilon>0$
satisfies

$\frac{2^{10}\min(s^{2},t^{2})}{(s+t)^{2}m^{2}}\leq\epsilon\leq\frac{\alpha^{2}\min(s^{2},t^{2})}{2^{10}(s+t)^{2}},$

then

$\binom{\left(\frac{t}{s+t}-2\sqrt{\epsilon}+2\epsilon\right)m}{t}\binom{\left(\frac{s}{s+t}+2\sqrt{\epsilon}\right)m}{s}\leq
e^{-\epsilon(s+t)}\binom{\frac{sm}{s+t}}{s}\binom{\frac{tm}{s+t}}{t}.$ (25)

We are now ready to prove Theorem 4.1.

###### Proof of Theorem 4.1.

The upper bound on $m$ in particular implies $m\leq s_{1}^{2}\log n$, so let
$\mathcal{A}$ be the family obtained from Theorem 2.2 applied with
$G=\mathbb{Z}$, $h=2$, $F_{1}=F_{2}=[n]$ and
$2^{-10}\alpha^{2}s_{1}^{2}/(s_{1}+s_{2})^{2}>\epsilon>2^{10}s_{1}^{2}(s_{1}+s_{2})^{-2}m^{-2}$
to be specified later. We claim that one of the following holds for every
triple $(A_{1},A_{2},B)\in\mathcal{A}$:

  1. 1.

$|A_{1}|+|A_{2}|\leq(1-\epsilon)m$,

  2. 2.

$|A_{i}|>\frac{s_{i}m}{s_{1}+s_{2}}+2\sqrt{\epsilon}m$ for some
$i\in\\{1,2\\}$, or

  3. 3.

There are arithmetic progressions $P_{1}$, $P_{2}$ with the same common
difference and sets $T_{1}$, $T_{2}$ such that
$|P_{i}|\leq\frac{s_{i}m}{s_{1}+s_{2}}+4\sqrt{\epsilon}m$,
$|T_{i}|\leq\epsilon|A_{i}|$ and $A_{i}\setminus T_{i}\subseteq P_{i}$ for
$i=1,2$.

Note first that we always have $|A_{1}|+|A_{2}|\leq(1+2\epsilon)m$ since by
Theorem 2.22 applied with $G=\mathbb{Z}$, either there are at most
$\epsilon^{2}|A_{1}||A_{2}|$ pairs $(a_{1},a_{2})\in A_{1}\times A_{2}$ with
$a_{1}+a_{2}\not\in B$, and hence Corollary 3.2 together with $|B|\leq m$
gives the required upper bound on $|A_{1}|+|A_{2}|$, or
$\max\\{|A_{1}|,|A_{2}|\\}<m/\log n$. Suppose neither 1 nor 2 hold, then by
Corollary 3.42 we see that 3 holds.

We will now count the number of pairs of sets $X_{1},X_{2}$ of size $s_{1}$
and $s_{2}$ respectively, satisfying $|X_{1}+X_{2}|\leq m$ that do not have
large intersections with arithmetic progressions in the sense of the theorem.
To do this, recall that by Theorem 2.21, for any such pair, there exists a
container triple $(A_{1},A_{2},B)\in\mathcal{A}$ such that $X_{i}\subset
A_{i}$.

We begin by giving an upper bound on the number of $X_{1},X_{2}$ with
containers satisfying property 1, that is, $|A_{1}|+|A_{2}|\leq(1-\epsilon)m$.
In fact we will give an upper bound for all such pairs, irrespective of
whether they violate the claimed structural statement. Clearly there are at
most $\sum_{\mathcal{A}}^{(a)}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}$ of
these. By comparing $\binom{a-b}{c}\binom{b}{d}$ and
$\binom{a-b-1}{c}\binom{b+1}{d}$ it is easy to check that an expression of
this form has its maximum at $\binom{ca/(c+d)}{c}\binom{da/(c+d)}{d}$. So
choosing ${\epsilon=2^{8}m^{1/6}(s_{1}+s_{2})^{-1/3}\sqrt{\log
n}<2^{-10}\alpha^{2}s_{1}^{2}(s_{1}+s_{2})^{-2}}$ and using (2), we see that

$\begin{split}\sum_{\mathcal{A}}^{(a)}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}&\leq|\mathcal{A}|\binom{(1-\epsilon)\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{(1-\epsilon)\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}\\\
&\leq\exp(2^{21}\sqrt{m}\epsilon^{-2}(\log
n)^{3/2}-\epsilon(s_{1}+s_{2}))\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}\\\
&\leq\exp(-2^{7}m^{1/6}(s_{1}+s_{2})^{2/3}\sqrt{\log
n})\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}.\end{split}$
(26)

We will now count pairs coming from containers of type 2. As in the last case
we will count all pairs, not such those violating the theorem statement. We
will not make use of the fact that $s_{2}\geq s_{1}$ so suppose without loss
of generality that 2 holds for $i=2$. Similar to the previous case, it
suffices to give an upper bound for

$\sum_{\mathcal{A}}^{(b)}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}\leq\sum_{\mathcal{A}}^{(b)}\binom{\left(\frac{s_{1}}{s_{1}+s_{2}}+2\epsilon-2\sqrt{\epsilon}\right)m}{s_{1}}\binom{\left(\frac{s_{2}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)m}{s_{2}}.$

Noting that $\epsilon=2^{8}m^{1/6}(s_{1}+s_{2})^{-1/3}\sqrt{\log
n}>2^{10}s_{1}^{2}(s_{1}+s_{2})^{-2}m^{-2}$ we can apply Lemma 4.2 and see
that

$\binom{\left(\frac{s_{1}}{s_{1}+s_{2}}+2\epsilon-2\sqrt{\epsilon}\right)m}{s_{1}}\binom{\left(\frac{s_{2}}{s_{1}+s_{2}}+2\sqrt{\epsilon}\right)m}{s_{2}}\leq
e^{-\epsilon(s_{1}+s_{2})}\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}},$

and hence

$\sum_{\mathcal{A}}^{(b)}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}\leq\exp(-2^{7}m^{1/6}(s_{1}+s_{2})^{2/3}\sqrt{\log
n})\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}.$
(27)

Finally, it remains to count the relevant $X_{1},X_{2}$ with containers
satisfying property 3. Observe that there are at most

$\sum_{i=1}^{2}\sum_{s_{i}^{\prime}=8\alpha^{-1}\epsilon(s_{1}+s_{2})}^{s_{i}}\binom{|A_{i}|}{s_{i}-s_{i}^{\prime}}\binom{\epsilon|A_{i}|}{s_{i}^{\prime}}\binom{|A_{3-i}|}{s_{3-i}}$
(28)

pairs of sets $X_{i}\subset A_{i}$ with $|X_{i}|=s_{i}$ that violate the
theorem statement, since for at least one $\delta\in\\{1,2\\}$ there must be
at least $s_{\delta}^{\prime}$ elements in $T_{\delta}$ for some
$s_{\delta}^{\prime}\geq 8\alpha^{-1}\epsilon(s_{1}+s_{2})$. Indeed, otherwise
$X_{i}\setminus T_{i}\subset P_{i}$ with
$|P_{i}|\leq\frac{s_{i}m}{s_{1}+s_{2}}+4\sqrt{\epsilon}m$ and $|X_{i}\cap
T_{i}|\leq 8\alpha^{-1}\epsilon(s_{1}+s_{2})$ for both $i$. For any $d\leq
c\leq a/4$, it holds (see for instance [5]) that

$\binom{a}{c-d}\binom{b}{d}\leq\binom{a}{c}\left(\frac{4bc}{ad}\right)^{d},$

so applying this to each innermost summand of (28) gives

$\displaystyle\binom{|A_{i}|}{s_{i}-s_{i}^{\prime}}\binom{\epsilon|A_{i}|}{s_{i}^{\prime}}\binom{|A_{3-i}|}{s_{3-i}}$
$\displaystyle\leq\left(\frac{4\epsilon
s_{i}}{s_{i}^{\prime}}\right)^{s_{i}^{\prime}}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}$
$\displaystyle\leq\left(\frac{4\epsilon
s_{i}}{s_{i}^{\prime}}\right)^{s_{i}^{\prime}}\binom{(1+2\epsilon)\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{(1+2\epsilon)\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}$
$\displaystyle\leq\left(\frac{4\epsilon
s_{i}}{s_{i}^{\prime}}\right)^{s_{i}^{\prime}}\left(1+4\alpha^{-1}\epsilon\right)^{s_{1}+s_{2}}\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}$

for every $i\in\\{1,2\\}$ and $s_{i}\geq s_{i}^{\prime}\geq
8\alpha^{-1}\epsilon(s_{1}+s_{2})$. Here, for the last inequality we used the
bound $\binom{a}{c}\leq\left(\frac{a-c}{b-c}\right)^{c}\binom{b}{c}$ valid for
any $a\geq b\geq c\geq 0$, as well as the upper bound $\alpha\leq 1$. Note
that, by our choice of $\epsilon$, we have
$\max\\{|\mathcal{A}|,s_{1}+s_{2}\\}\leq\exp(\epsilon(s_{1}+s_{2}))$, hence
summing (28) over all triples $(A_{1},A_{2},B)\in\mathcal{A}$ we obtain

$\begin{split}&\sum_{\mathcal{A}}^{(c)}\sum_{i=1}^{2}\sum_{s_{i}^{\prime}=8\alpha^{-1}\epsilon(s_{1}+s_{2})}^{s_{i}}\binom{|A_{i}|}{s_{i}-s_{i}^{\prime}}\binom{\epsilon|A_{i}|}{s_{i}^{\prime}}\binom{|A_{3-i}|}{s_{3-i}}\\\
\leq{}&|\mathcal{A}|(1+4\alpha^{-1}\epsilon)^{s_{1}+s_{2}}\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}\sum_{i=1}^{2}s_{i}\max_{s_{i}^{\prime}\geq
8\alpha^{-1}\epsilon(s_{1}+s_{2})}\left(\frac{4\epsilon
s_{i}}{s_{i}^{\prime}}\right)^{s_{i}^{\prime}}\\\
\leq{}&\exp\left(6\alpha^{-1}\epsilon(s_{1}+s_{2})\right)2^{-16\alpha^{-1}\epsilon(s_{1}+s_{2})}\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}\\\
\leq{}&\exp(-4\alpha^{-1}\epsilon(s_{1}+s_{2}))\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}\\\
={}&\exp(-2^{10}m^{1/6}(s_{1}+s_{2})^{2/3}\sqrt{\log
n})\binom{\frac{s_{1}m}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}m}{s_{1}+s_{2}}}{s_{2}}.\end{split}$
(29)

To conclude, note that bounds (26), (27) and (29) imply the probability we
claimed in the statement since we can fix a single pair of disjoint arithmetic
progressions of length $\frac{s_{i}m}{s_{1}+s_{2}}$ respectively with the same
common difference and see that any of the
$\prod\binom{s_{i}m/(s_{1}+s_{2})}{s_{i}}$ pairs of $s_{i}$-subsets will have
a sumset of size at most $m$. ∎

Note that in the proof above, the main restriction concerning the relation
between $s_{1}$ and $s_{2}$ comes from the application of Theorem 3.3, our
stability result. Since counting statements using the container framework only
require the use of supersaturation and not stability, we thus get the
following less restrictive result which is the technical version of Theorem
1.2.

######  Theorem 4.3.

Let $G$ be an abelian group. Let $s_{1},s_{2},n$ be integers satisfying

$s_{2}\geq s_{1}\geq\max\left(\sqrt{(s_{1}+s_{2})\log n},2^{48}(\log
n)^{3}-s_{2}\right),$

and let $m$ be an integer such that

$s_{1}+s_{2}\leq m\leq\min\left(\frac{s_{1}^{2}}{\log
n},\frac{(s_{1}+s_{2})^{2}}{2^{48}(\log n)^{3}}\right).$

Then for any $F_{1},F_{2}\subset G$ with $|F_{i}|=n$, it holds that the number
of pairs of sets $(X_{1},X_{2})\in 2^{F_{1}}\times 2^{F_{2}}$ with
$|X_{i}|=s_{i}$ and $|X_{1}+X_{2}|\leq m$ is at most

$\exp\left(2^{10}m^{1/6}(s_{1}+s_{2})^{2/3}\lambda^{2/3}\sqrt{\log
n}\right)\binom{s_{1}(m+\beta)/(s_{1}+s_{2})}{s_{1}}\binom{s_{2}(m+\beta)/(s_{1}+s_{2})}{s_{2}},$

where $\lambda=\min\left(\frac{m}{m-s_{1}-s_{2}},\log(s_{1}+s_{2})\right)$ and
$\beta=\beta(m+2^{8}m^{7/6}(s_{1}+s_{2})^{-1/3}\lambda^{-1/3}\sqrt{\log n})$.

###### Proof.

We can apply Theorem 2.2 with $s_{1},s_{2},m,n$ and $1/4>\epsilon>0$ to be
specified later, let $\mathcal{A}$ be the family obtained this way. So for
every pair of sets $(X_{1},X_{2})\in 2^{F_{1}}\times 2^{F_{2}}$ there exists a
container triple $(A_{1},A_{2},B)\in\mathcal{A}$ such that $X_{i}\subset
A_{1}$ and $B\subset X_{1}+X_{2}$. Note that if we define
$\beta=\beta(m+4\epsilon m)$, it holds true that
$|A_{1}|+|A_{2}|\leq(1+2\epsilon)(m+\beta)$ for any pair $(A_{1},A_{2})$
appearing in a container triple in $\mathcal{A}$. Indeed, by Theorem 2.22, we
either have

$|A_{1}|+|A_{2}|\leq 2\max|A_{i}|<2m/\log n\leq(1+2\epsilon)(m+\beta),$

or there are at most $\epsilon^{2}|A_{1}||A_{2}|$ pairs $(a_{1},a_{2})$ such
that $a_{1}+a_{2}\notin B$, and hence Corollary 3.2 gives the required bound.
Hence the number of pairs $(X_{1},X_{2})$ satisfying the theorem hypotheses is
at most

$\displaystyle|\mathcal{A}|\max_{(A_{1},A_{2},B)\in\mathcal{A}}\binom{|A_{1}|}{s_{1}}\binom{|A_{2}|}{s_{2}}$
$\displaystyle\leq\exp\left(\frac{2^{21}\sqrt{m(\log
n)^{3}}}{\epsilon^{2}}\right)\binom{\frac{s_{1}(1+2\epsilon)(m+\beta)}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}(1+2\epsilon)(m+\beta)}{s_{1}+s_{2}}}{s_{2}}.$
(30)

If $m/(m-s_{1}-s_{2})\leq\log(s_{1}+s_{2})$ we can again apply the bound
$\binom{a}{c}\leq\left(\frac{a-c}{b-c}\right)^{c}\binom{b}{c}$ valid for any
$a\geq b\geq c\geq 0$ to both binomials in (30) separately and see that it is
at most

$\exp\left(2^{21}\epsilon^{-2}\sqrt{m}(\log
n)^{3/2}+2\epsilon\lambda(s_{1}+s_{2})\right)\binom{\frac{s_{1}(m+\beta)}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}(m+\beta)}{s_{1}+s_{2}}}{s_{2}}.$

Suppose now that $m/(m-s_{1}-s_{2})\geq\log(s_{1}+s_{2})$, and note that this
implies in particular $m=s_{1}+s_{2}+o(1)$. We compute

$\displaystyle\log\left(\binom{(1+\delta)a}{b}\binom{a}{b}^{-1}\right)$
$\displaystyle=\sum_{i=0}^{b-1}\log\left(1+\frac{\delta a}{a-i}\right)$
$\displaystyle\leq\delta a\int_{0}^{b}(a-x)^{-1}dx$ $\displaystyle\leq\delta
a\log a.$

Applying this with $\delta=2\epsilon$, $a=s_{i}(m+\beta)/(s_{1}+s_{2})$ and
$b=s_{i}$ and noting that $\beta\leq 2m$, we can upper bound (30) by

$\exp\left(2^{21}\epsilon^{-2}\sqrt{m}(\log
n)^{3/2}+2^{3}\epsilon\lambda(s_{1}+s_{2})\right)\binom{\frac{s_{1}(m+\beta)}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}(m+\beta)}{s_{1}+s_{2}}}{s_{2}}.$

Hence setting
$\epsilon=2^{6}m^{1/6}(s_{1}+s_{2})^{-1/3}\lambda^{-1/3}\sqrt{\log n}<1/4$
implies

$\beta(m+4\epsilon
m)=\beta(m+2^{8}m^{7/6}(s_{1}+s_{2})^{-1/3}\lambda^{-1/3}\sqrt{\log n})$

and the number of pairs $(X_{1},X_{2})$ satisfying the theorem hypotheses is
at most

$\exp\left(2^{10}m^{1/6}(s_{1}+s_{2})^{2/3}\lambda^{2/3}\sqrt{\log
n}\right)\binom{\frac{s_{1}(m+\beta)}{s_{1}+s_{2}}}{s_{1}}\binom{\frac{s_{2}(m+\beta)}{s_{1}+s_{2}}}{s_{2}}.$

∎

We note that Theorem 1.2 is obtained via a straightforward application of
Theorem 4.3. Finally, similar to the proof of Theorem 1.1, when a result
comparable to Freiman’s $3k-4$ exists one can handle the case
$m/(m-s_{1}-s_{2})\geq\log(s_{1}+s_{2})$ differently than it was done in the
proof of Theorem 4.3. Essentially, this case can only happen when $m$ is very
close to $s_{1}+s_{2}$ and hence such a Freiman type result would actually
tell us the precise structure instead of just the number of such pairs.

##  5 Proof of Theorem 2.1

###  5.1 Setup

From now on all hypergraphs are allowed to have multi-edges, and the edges are
counted with multiplicity. Let $r,r_{0}\in\mathbb{N}$, $m\in\mathbb{N}$ and
let $R$ be a positive real. Let $b$ be positive integer and suppose that
$\mathcal{H}$ is a $(1,\dots,1,r_{0})$-bounded $r$-partite hypergraph with
vertex set $V=V_{1}\cup\dots\cup V_{r}$ satisfying (1) for each vector
$y\in\left(\prod_{i=1}^{r-1}\\{0,1\\}\right)\times\\{0,1,\ldots,r_{0}\\}$,
$b\leq\min_{i}|V_{i}|$ and $b\leq m$ as in the statement of Theorem 2.1. We
also define the vector $w=(w_{1},\dots,w_{r})=(|V_{1}|,\dots,|V_{r-1}|,m)$
which will be helpful to reduce notational clutter later. Note that using $w$,
one can write the degree condition (1) as

$\Delta_{y}(\mathcal{H})\leq
R\left(\prod_{i=1}^{r}w_{i}^{y_{i}}\right)^{-1}b^{|y|-1}e(\mathcal{H})\left(\frac{m}{q}\right)^{\mathds{1}[y_{r}>0]}.$

We claim that, without loss of generality we may assume that $m\leq|V_{r}|$.
Indeed, if $m>|V_{r}|$, then we may replace $m$ with $|V_{r}|$ as
$\mathcal{I}_{m}(\mathcal{H})\subseteq\mathcal{I}_{m^{\prime}}(\mathcal{H})$
for any $m^{\prime}\geq m$, and the right-hand side of (1) is a non-increasing
function in $m$. We shall be working only with hypergraphs with edge
cardinalities coming from the set

$\mathcal{U}:=\big{\\{}x\in\left(\prod_{i=1}^{r-1}\\{0,1\\}\right)\times\\{1,2,\ldots,r_{0}\\}:\leavevmode\nobreak\
x_{i}\leq x_{i+1}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
r_{0}x_{r-1}\leq x_{r}\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
1\leq i<r\big{\\}}.$

The maximum codegrees we must check for each edge size $x\in\mathcal{U}$ will
come from the set

$\mathcal{V}(x):=\left(\prod_{i=1}^{r}\\{0,\ldots,x_{i}\\}\right)\setminus\\{(0,\dots,0)\\}.$

We now define a collection of numbers that will be upper bounds on the maximum
codegrees of the hypergraphs constructed by our algorithm. To be more precise,
for each $x\in\mathcal{U}$ and all $v\in\mathcal{V}(x)$, we shall force the
maximum $v$-codegree of the $x$-bounded hypergraph not to exceed the quantity
$\Delta_{v}^{x}$, defined as follows.

######  Definition 5.1.

For every $x\in\mathcal{U}$ and every $v\in\mathcal{V}(x)$, we define the
number $\Delta_{v}^{x}$ using the following recursion:

  1. (1)

If $x=(1,\dots,1,r_{0})$, set $\Delta_{v}^{x}:=\Delta_{v}(\mathcal{H})$ for
all $v\in\mathcal{V}(x)$.

  2. (2)

Given $x\in\mathcal{U}$, let $i^{\prime}=\min\\{i:x_{i}>0\\}$ and
$x-e_{i^{\prime}}=x^{\prime}\in\mathcal{U}$ where $e_{1},\dots,e_{r}$ are the
standard basis vectors of $\mathbb{R}^{r}$. If $v\in\mathcal{V}(x)$ satisfies
$v_{i^{\prime}}>0$, denote similarly
$v-e_{i^{\prime}}=:v^{\prime}\in\mathcal{V}(x^{\prime})$. Note that in this
case $i^{\prime}$ depends on $x$, so $v^{\prime}$ also depends on $x$, not
only on $v$, but we omit it from the notation to avoid clutter. Then define

$\Delta_{v^{\prime}}^{x^{\prime}}:=\max\left\\{2\Delta_{v}^{x},\,\frac{b}{w_{i^{\prime}}}\Delta_{v^{\prime}}^{x}\right\\}.$

The above recursive definition will be convenient in some parts of the
analysis. In other parts, we shall require the following explicit formula for
$\Delta_{v}^{x}$, which one easily derives from Definition 5.1 using a
straightforward induction on $r_{0}+r-1-|x|$.

######  Observation 5.2.

For all $x$ and $v$ as in Definition 5.1,

$\Delta_{v}^{x}=\max\left\\{2^{|z|}\prod_{i=1}^{r-1}\left(\frac{b}{|V_{i}|}\right)^{1-v_{i}-z_{i}}\left(\frac{b}{m}\right)^{r_{0}-v_{r}-z_{r}}\Delta_{v+z}(\mathcal{H}):z\in\left(\prod_{i=1}^{r-1}\\{0,1-x_{i}\\}\right)\times[0,r_{0}-x_{r}]\right\\}.$

For future reference, we note the following two simple corollaries of
Observation 5.2 and our assumptions on the maximum degrees of $\mathcal{H}$,
see (1). Suppose that $x\in\mathcal{U}$ such that $i\in[r]$ is the least index
with $e_{i}\in\mathcal{V}(x)$. If $i<r$, then by definition of $\mathcal{U}$
it holds that $x_{j}=0$ for all $1\leq j<i$, $x_{j}=1$ for all $i\leq j<r$ and
$x_{r}=r_{0}$, so

$\begin{split}\Delta_{e_{i}}^{x}&\leq
2^{i}R\prod_{j=1}^{i-1}\left(\frac{b}{|V_{j}|}\right)\frac{e(\mathcal{H})}{|V_{i}|}.\end{split}$
(31)

If $i=r$, then $x_{j}=0$ for all $1\leq j<r$ and

$\begin{split}\Delta_{e_{i}}^{x}\leq
2^{r+r_{0}}R\prod_{j=1}^{r-1}\left(\frac{b}{|V_{j}|}\right)\left(\frac{b}{m}\right)^{r_{0}-x_{r}}\frac{e(\mathcal{H})}{q}.\end{split}$
(32)

We will build a sequence of hypergraphs with decreasing maximum edge size,
starting with $\mathcal{H}$, and making sure that for each hypergraph
$\mathcal{G}$ in the sequence we have an appropriate bound on its maximum
codegrees. To this end we define the following set of pairs with large
codegree.

######  Definition 5.3.

Given $x\in\mathcal{U}$, $v\in\mathcal{V}(x)$, and an $x$-bounded hypergraph
$\mathcal{G}$, we define

$M^{x}_{v}(\mathcal{G})=\left\\{L\in\prod_{i=1}^{r}\binom{V_{i}}{v_{i}}:d_{\mathcal{G}}(L)\geq\Delta_{v}^{x}/2\right\\}.$

###  5.2 The algorithm

We shall now define precisely a single round of the algorithm we use to prove
the container lemma. To this end, fix some $x\in\mathcal{U}$, set
$i^{\prime}:=\min\\{i:x_{i}>0\\}$ and

$x^{\prime}=x-e_{i^{\prime}}.$ (33)

Suppose that $\mathcal{G}$ is an $x$-bounded hypergraph with
$V(\mathcal{G})=V(\mathcal{H})$. A single round of the algorithm takes as
input an arbitrary $I\in\mathcal{I}(\mathcal{G})$ and outputs an
$x^{\prime}$-bounded hypergraph $\mathcal{G}_{*}$ satisfying
$V(\mathcal{G}_{*})=V(\mathcal{G})$ and $I\in\mathcal{I}(\mathcal{G}_{*})$ as
well as a set $S\subseteq I\cap V_{i^{\prime}}$ such that $|S|\leq b$.
Crucially, the number of possible outputs of the algorithm (over all possible
inputs $I\in\mathcal{I}(\mathcal{G})$) is at most
$\binom{|V_{i^{\prime}}|}{\leq b}$.

Assume that there is an implicit linear order $\preccurlyeq$ on
$V(\mathcal{G})$. The _$i^{\prime}$ -maximum vertex_ of a hypergraph
$\mathcal{A}$ with $V(\mathcal{A})=V(\mathcal{G})$ is the
$\preccurlyeq$-smallest vertex among all $v\in V_{i^{\prime}}$ of maximal
degree.

The algorithm. Set $\mathcal{A}^{(0)}=\mathcal{G}$, $S=\emptyset$ and
$\mathcal{G}_{*}^{(0)}=(V(\mathcal{G}),\emptyset)$. Do the following for each
integer $j\geq 0$ in turn:

  1. (S1)

If $|S|=b$ or $\mathcal{A}^{(j)}$ is empty, then set $L=j$ and STOP.

  2. (S2)

Let $u_{j}\in V_{i^{\prime}}$ be the $i^{\prime}$-maximum vertex of
$\mathcal{A}^{(j)}$.

  3. (S3)

If $u_{j}\in I$, then add $j$ to the set $S$ and let

$\mathcal{G}_{*}^{(j+1)}:=\mathcal{G}_{*}^{(j)}\cup\Big{\\{}E\setminus\\{u_{j}\\}:E\in\mathcal{A}^{(j)}\text{
and }u_{j}\in E\Big{\\}}.$

  4. (S4)

Let $\mathcal{A}^{(j+1)}$ be the hypergraph obtained from $\mathcal{A}^{(j)}$
by removing from it all edges $E$ such that either of the following hold:

    1. (a)

$u_{j}\in E$,

    2. (b)

there exists a non-empty $T\subseteq E$, such that

$T\in M^{x^{\prime}}_{v}\big{(}\mathcal{G}_{*}^{(j+1)}\big{)}$

for some $v\in\mathcal{V}(x^{\prime})$.

Finally, set $\mathcal{A}:=\mathcal{A}^{(L)}$ and
$\mathcal{G}_{*}:=\mathcal{G}_{*}^{(L)}$. Moreover, set

$W:=\big{\\{}0,\dotsc,L-1\big{\\}}\setminus
S=\Big{\\{}j\in\big{\\{}0,\dotsc,L-1\big{\\}}:u_{j}\not\in I\Big{\\}}.$

Observe that the algorithm always stops after at most $|V(\mathcal{G})|$
iterations of the main loop. Indeed, since all hyperedges $E$ with $u_{j}\in
E$ are removed from $\mathcal{A}^{(j+1)}$ in part (S4)(a) of step (S4), the
vertex $u_{j}$ cannot be the $i^{\prime}$-maximum vertex of any
$\mathcal{A}^{(j^{\prime})}$ with $j^{\prime}>j$ and hence the map
$\\{0,\dotsc,L-1\\}\ni j\mapsto u_{j}\in V(\mathcal{G})$ is injective.

###  5.3 The analysis

We shall now establish some basic properties of the algorithm described in the
previous subsection. To this end, let us fix some $x\in\mathcal{U}$,
$x^{\prime}$ and $i^{\prime}$ as defined in (33). Moreover, suppose that
$\mathcal{G}$ is an $x$-bounded hypergraph and that we have run the algorithm
with input $I\in\mathcal{I}(\mathcal{G})$ and obtained the
$x^{\prime}$-bounded hypergraph $\mathcal{G}_{*}$, the integer $L$, the
injective map $\\{0,\dotsc,L-1\\}\ni j\mapsto u_{j}\in V(\mathcal{G})$, and
the partition of $\\{0,\dotsc,L-1\\}$ into $S$ and $W$ such that $u_{j}\in I$
if and only if $j\in S$. We first state two straightforward, but fundamental,
properties of the algorithm.

######  Observation 5.4.

If $I\in\mathcal{I}(\mathcal{G})$, then $I\in\mathcal{I}(\mathcal{G}_{*})$.

###### Proof.

Observe that $\mathcal{G}_{*}$ contains only edges of the form
$E\setminus\\{v\\}$ where $v\in E\cap I$ and $E\in\mathcal{G}$, see (S3).
Hence, if $I$ contained the edge $E\setminus\\{v\\}$ it would also contain the
edge $E$. ∎

The next observation says that if the algorithm applied to two sets $I$ and
$I^{\prime}$ outputs the same set $\\{u_{j}:j\in S\\}$, then the rest of the
output is also the same.

######  Observation 5.5.

Fix the hypergraph $\mathcal{G}$ we input in the algorithm, suppose that the
algorithm applied to $I^{\prime}\in\mathcal{F}(\mathcal{G})$ outputs a
hypergraph $\mathcal{G}_{*}^{\prime}$, an integer $L^{\prime}$, a map
$j\mapsto u_{j}^{\prime}$, and a partition of $\\{0,\dotsc,L^{\prime}-1\\}$
into $S^{\prime}$ and $W^{\prime}$. If $\\{u_{j}:j\in
S\\}=\\{u_{j}^{\prime}:j\in S^{\prime}\\}$, then
$\mathcal{G}_{*}=\mathcal{G}_{*}^{\prime}$, $L=L^{\prime}$,
$u_{j}=u_{j}^{\prime}$ for all $j$, and $W=W^{\prime}$.

###### Proof.

The only step of the algorithm that depends on the input pair $I$ is (S3).
There, an index $j$ is added to the set $S$ if and only if $u_{j}\in I$.
Therefore, the execution of the algorithm depends only on the set
$\\{u_{j}:j\in S\\}$ and the hypergraph $\mathcal{G}$. ∎

The next two lemmas will allow us to maintain suitable upper and lower bounds
on the degrees and densities of the hypergraphs obtained by applying the
algorithm iteratively. The first lemma, which is the easier of the two, states
that if all the maximum degrees of $\mathcal{G}$ are appropriately bounded,
then all the maximum degrees of $\mathcal{G}_{*}$ are also appropriately
bounded.

######  Lemma 5.6.

Given $v\in\mathcal{V}(x)$ with $v_{i^{\prime}}>0$, let
$v^{\prime}=v-e_{i^{\prime}}$. If $\Delta_{v}(\mathcal{G})\leq\Delta_{v}^{x}$,
then
$\Delta_{v^{\prime}}(\mathcal{G}_{*})\leq\Delta_{v^{\prime}}^{x^{\prime}}$.

###### Proof.

Suppose (for a contradiction) that there exists a set $T$, with $|T\cap
V_{i}|=v^{\prime}_{i}$ for all $i$, such that
$\deg_{\mathcal{G}_{*}}(T)>\Delta_{v^{\prime}}^{x^{\prime}}$. Let $j$ be the
smallest integer satisfying

$\deg_{\mathcal{G}_{*}^{(j+1)}}(T)>\Delta_{v^{\prime}}^{x^{\prime}}/2$

and note that $j\geq 0$, since $\mathcal{G}_{*}^{(0)}$ is empty. We claim
first that

$\deg_{\mathcal{G}_{*}}(T)=\deg_{\mathcal{G}_{*}^{(j+1)}}(T).$ (34)

Indeed, observe that $T\in
M^{x^{\prime}}_{v^{\prime}}\big{(}\mathcal{G}_{*}^{(j+1)}\big{)}$, and
therefore the algorithm removes from $\mathcal{A}^{(j)}$ (when forming
$\mathcal{A}^{(j+1)}$ in step (S4)) all edges $E$ such that $T\subset E$. As a
consequence, no further edges $E$ with $T\subseteq E$ are added to
$\mathcal{G}_{*}$ in step (S3).

We next claim that

$\deg_{\mathcal{G}_{*}^{(j+1)}}(T)-\deg_{\mathcal{G}_{*}^{(j)}}(T)\leq\Delta_{v}^{x}.$
(35)

To see this, recall that when we extend $\mathcal{G}_{*}^{(j)}$ to
$\mathcal{G}_{*}^{(j+1)}$ in step (S3), we only add edges
$E\setminus\\{u_{j}\\}$ such that $E\in\mathcal{A}^{(j)}\subseteq\mathcal{G}$
and $u_{j}\in E$. Therefore, setting $T^{*}=T\cup\\{u_{j}\\}$, we have

$\deg_{\mathcal{G}_{*}^{(j+1)}}(T)-\deg_{\mathcal{G}_{*}^{(j)}}(T)\leq\deg_{\mathcal{G}}(T^{*})\leq\Delta_{v}(\mathcal{G})\leq\Delta_{v}^{x},$

where the last inequality is by our assumption, as claimed.

Combining (34) and (35), it follows immediately that

$\deg_{\mathcal{G}_{*}}(T)\leq\Delta_{v^{\prime}}^{x^{\prime}}/2+\Delta_{v}^{x}\leq\Delta_{v^{\prime}}^{x^{\prime}},$

where the final inequality holds by Definition 5.1. This contradicts our
choice of $T$ and therefore the lemma follows. ∎

We are now ready for the final lemma, which is really the heart of the matter.
We will show that if $\mathcal{G}$ has sufficiently many edges and all of the
maximum degrees of $\mathcal{G}$ are appropriately bounded, then either the
output hypergraph $\mathcal{G}_{*}$ has sufficiently many edges, or the output
set $W$ must be big. We remark that here we shall use the assumption that
$|I\cap V_{r}|\geq|V_{r}|-m$.

######  Lemma 5.7.

Suppose that $|I\cap V_{r}|\geq|V_{r}|-m$ and let $\alpha>0$. If

  1. (A1)

$e(\mathcal{G})\geq\alpha\prod_{i=1}^{r-1}\left(\frac{b}{|V_{i}|}\right)^{1-x_{i}}\left(\frac{b}{m}\right)^{r_{0}-x_{r}}e(\mathcal{H})$
and

  2. (A2)

$\Delta_{v}(\mathcal{G})\leq\Delta_{v}^{x}$ for every $v\in\mathcal{V}(x)$,

then at least one of the following statements is true:

  1. (P1)

$e(\mathcal{G}_{*})\geq
2^{-|x|-x_{r}-1}\alpha\prod_{i=1}^{r-1}\left(\frac{b}{|V_{i}|}\right)^{1-x^{\prime}_{i}}\left(\frac{b}{m}\right)^{r_{0}-x^{\prime}_{r}}e(\mathcal{H})$.

  2. (P2)

$i^{\prime}<r$ and $|W|\geq 2^{-i^{\prime}-1}R^{-1}\alpha|V_{i^{\prime}}|$.

  3. (P3)

$i^{\prime}=r$ and $|W|\geq 2^{-r-r_{0}-1}R^{-1}\alpha q$.

###### Proof.

Recall that $\mathcal{G}_{*}$ (and $\mathcal{G}_{*}^{(j)}$ etc.) are multi-
hypergraphs and that edges are counted with multiplicity. We observe that

$e(\mathcal{G}_{*})=\sum_{j\in
S}\left(e(\mathcal{G}_{*}^{(j+1)})-e(\mathcal{G}_{*}^{(j)})\right)=\sum_{j\in
S}\Delta_{e_{i^{\prime}}}(\mathcal{A}^{(j)}),$ (36)

since
$e(\mathcal{G}_{*}^{(j+1)})-e(\mathcal{G}_{*}^{(j)})=d_{\mathcal{A}^{(j)}}(\\{u_{j}\\})$
and $u_{j}$ is the $i^{\prime}$-maximum vertex of $\mathcal{A}^{(j)}$ for each
$j\in S$, and $\mathcal{G}_{*}^{(j+1)}=\mathcal{G}_{*}^{(j)}$ for each
$j\not\in S$. To bound the right-hand side of (36), we count the edges removed
from $\mathcal{A}^{(j)}$ in (S4)(a) and (S4)(b) of step (S4), which gives

$e(\mathcal{A}^{(j)})-e(\mathcal{A}^{(j+1)})\leq\Delta_{e_{i^{\prime}}}(\mathcal{A}^{(j)})+\sum_{v}\big{|}M^{x^{\prime}}_{v}(\mathcal{G}_{*}^{(j+1)})\setminus
M^{x^{\prime}}_{v}(\mathcal{G}_{*}^{(j)})\big{|}\cdot\Delta_{v}(\mathcal{G}).$

Summing over $j\in\\{0,\ldots,L-1\\}$ it follows (using (36)) that

$e(\mathcal{G})-e(\mathcal{A})\leq
e(\mathcal{G}_{*})+|W|\cdot\Delta_{e_{i^{\prime}}}(\mathcal{G})+\sum_{v}\big{|}M^{x^{\prime}}_{v}(\mathcal{G}_{*})\big{|}\cdot\Delta_{v}^{x},$

since
$\mathcal{A}=\mathcal{A}^{(L)}\subseteq\dots\subseteq\mathcal{A}^{(0)}=\mathcal{G}$
and $\Delta_{v}(\mathcal{G})\leq\Delta_{v}^{x}$ by (A2). Furthermore,

$\Delta_{e_{i^{\prime}}}(\mathcal{A})\leq\Delta_{e_{i^{\prime}}}(\mathcal{A}^{(j)})\leq\Delta_{e_{i^{\prime}}}(\mathcal{G})\leq\Delta_{e_{i^{\prime}}}^{x},$
(37)

since $\mathcal{A}\subseteq\mathcal{A}^{(j)}\subseteq\mathcal{G}$ and
$\mathcal{G}$ satisfies (A2), which implies

$e(\mathcal{G})-e(\mathcal{A})\leq
e(\mathcal{G}_{*})+|W|\Delta_{e_{i^{\prime}}}^{x}+\sum_{v}\big{|}M^{x^{\prime}}_{v}(\mathcal{G}_{*})\big{|}\Delta_{v}^{x}.$
(38)

Combining (36) and (37), we get

$e(\mathcal{G}_{*})=\sum_{j\in
S}\Delta_{e_{i^{\prime}}}\big{(}\mathcal{A}^{(j)}\big{)}\geq|S|\Delta_{e_{i^{\prime}}}(\mathcal{A})=b\Delta_{e_{i^{\prime}}}(\mathcal{A}),$
(39)

where the equality is due to the fact that $|S|\neq b$ only when $\mathcal{A}$
is empty, see step (S1).

Next, to bound the sum in (38), observe that, by Definition 5.3, we have

$\big{|}M^{x^{\prime}}_{v}(\mathcal{G}_{*})\big{|}\Delta^{x^{\prime}}_{v}/2\leq\sum_{T:\leavevmode\nobreak\
|T\cap
V_{i}|=v_{i}}\deg_{\mathcal{G}_{*}}(T)\leq\binom{x_{r}}{v_{r}}e(\mathcal{G}_{*})\leq
2^{x_{r}}e(\mathcal{G}_{*})$

for each $v\in\mathcal{V}(x^{\prime})$ and therefore

$\begin{split}\sum_{v\in\mathcal{V}(x^{\prime})}\big{|}M^{x^{\prime}}_{v}(\mathcal{G}_{*})\big{|}\Delta_{v}^{x}&\leq
2^{x_{r}+1}\sum_{v}e(\mathcal{G}_{*})\left(\Delta_{v}^{x}/\Delta^{x^{\prime}}_{v}\right)\\\
&\leq
2^{x_{r}+1}\big{(}2^{|x^{\prime}|}-1\big{)}e(\mathcal{G}_{*})\max_{v}\left\\{\Delta_{v}^{x}/\Delta^{x^{\prime}}_{v}\right\\}\\\
&\leq
2^{x_{r}+1}\big{(}2^{|x^{\prime}|}-1\big{)}e(\mathcal{G}_{*})w_{i^{\prime}}/b,\end{split}$
(40)

where the last inequality follows from Definition 5.1.

Suppose first that $i^{\prime}<r$ and observe that substituting (40) into (38)
yields

$e(\mathcal{G})-e(\mathcal{A})\leq
e(\mathcal{G}_{*})+|W|\Delta_{e_{i^{\prime}}}^{x}+2^{x_{r}+1}\big{(}2^{|x^{\prime}|}-1\big{)}e(\mathcal{G}_{*})|V_{i^{\prime}}|/b.$
(41)

Moreover, by (39) we have

$\frac{e(\mathcal{G}_{*})}{b}\geq\Delta_{e_{i^{\prime}}}(\mathcal{A})\geq\frac{e(\mathcal{A})}{|V_{i^{\prime}}|}$
(42)

since the maximum degree of a hypergraph is at least as large as its average
degree. Combining (41) and (42), we obtain

$\begin{split}e(\mathcal{G})&\leq
e(\mathcal{G}_{*})\frac{|V_{i^{\prime}}|}{b}\left(\frac{b}{|V_{i^{\prime}}|}+1+2^{x_{r}+|x^{\prime}|+1}-2\right)+|W|\Delta_{e_{i^{\prime}}}^{x}\\\
&\leq
e(\mathcal{G}_{*})\frac{|V_{i^{\prime}}|}{b}2^{x_{r}+|x|}+|W|\Delta_{e_{i^{\prime}}}^{x},\end{split}$
(43)

since $b\leq|V_{i^{\prime}}|$. Now, if the first summand on the right-hand
side of (43) exceeds $e(\mathcal{G})/2$, then (A1) implies (P1). Otherwise,
the second summand is at least $e(\mathcal{G})/2$ and by (A1) and (31),

$|W|\geq\frac{e(\mathcal{G})}{2\Delta_{e_{i^{\prime}}}^{x}}\geq\frac{\alpha}{2^{i^{\prime}+1}R}|V_{i^{\prime}}|,$

which is (P2).

Finally, suppose $i^{\prime}=r$. Substituting (40) into (38) yields, using the
bound $\Delta_{v}^{x}/\Delta^{x^{\prime}}_{v}\leq m/b$,

$e(\mathcal{G})-e(\mathcal{A})\leq
e(\mathcal{G}_{*})+|W|\Delta_{e_{r}}^{x}+\big{(}2^{x_{r}+|x|}-2^{x_{r}+1}\big{)}e(\mathcal{G}_{*})\frac{m}{b}.$
(44)

We claim that

$\frac{e(\mathcal{G}_{*})}{b}\geq\Delta_{e_{r}}(\mathcal{A})\geq\frac{e(\mathcal{A})}{m}.$
(45)

The first inequality follows from (39), so we only need to prove the second
inequality. To do so, since $I\in\mathcal{F}(\mathcal{G})$ is an independent
set in $\mathcal{A}$ (and all edges of $\mathcal{A}$ are contained in $V_{r}$)
then every edge in $\mathcal{A}$ must be incident to $V_{r}\setminus I$, which
has size at most $m$ by assumption. This shows that

$\Delta_{e_{r}}(\mathcal{A})\geq\frac{e(\mathcal{A})}{|V_{r}\setminus
I|}\geq\frac{e(\mathcal{A})}{m}.$

Combining (44) and (45), we obtain

$\begin{split}e(\mathcal{G})&\leq
e(\mathcal{G}_{*})\frac{m}{b}\left(\frac{b}{m}+1+2^{x_{r}+|x|}-2^{x_{r}+1}\right)+|W|\Delta_{e_{r}}^{x}\\\
&\leq
e(\mathcal{G}_{*})\frac{m}{b}2^{x_{r}+|x|}+|W|\Delta_{e_{r}}^{x},\end{split}$
(46)

since $b\leq m$. Now, if the first summand on the right-hand side of (43)
exceeds $e(\mathcal{G})/2$, then (A1) implies (P1). Otherwise, the second
summand is at least $e(\mathcal{G})/2$ and by (A1) and (32),

$|W|\geq\frac{e(\mathcal{G})}{2\Delta_{e_{r}}^{x}}\geq\frac{\alpha}{2^{r_{0}+r+1}R}q,$

which is (P3). ∎

###  5.4 Construction of the container

In this section, we present the construction of containers for pairs in
$\mathcal{I}_{m}(\mathcal{H})$ and analyse their properties, thus proving
Theorem 2.1. For each $s\in\\{0,\ldots,r_{0}+r-1\\}$, define

$\alpha_{s}=2^{-s(2r_{0}+r)}\qquad\text{and}\qquad\beta_{s}=\alpha_{s}\prod_{j=1}^{\min\\{{r-1,s\\}}}\left(\frac{b}{|V_{j}|}\right)\left(\frac{b}{m}\right)^{\max\\{0,s-r+1\\}}.$

Given an $I\in\mathcal{I}_{m}(\mathcal{H})$, we construct the container
$(A_{1},\dots,A_{r})$ for $I$ using the following procedure.

Construction of the container. Initialize $s=0,\,x=(1,\dots,1,r_{0})$,
$\mathcal{H}^{x}=\mathcal{H}$ and $S_{i}=\emptyset$ for all $i\in[r]$.

  1. (C1)

Let $i^{\prime}$ and $x^{\prime}$ be defined from $x$ as before.

  2. (C2)

Run the algorithm with $\mathcal{G}\leftarrow\mathcal{H}^{x}$ to obtain the
$x^{\prime}$-bounded hypergraph $\mathcal{G}_{*}$, the sequence
$u_{0},\ldots,u_{L-1}\in V(\mathcal{H})$, and the partition
$\\{0,1,\ldots,L-1\\}=S\cup W$.

  3. (C3)

Let $S_{i^{\prime}}\leftarrow S_{i^{\prime}}\cup\\{u_{j}:j\in S\\}$.

  4. (C4)

If $e(\mathcal{G}_{*})<\beta_{s+1}e(\mathcal{H})$, then define
$(A_{1},\ldots,A_{r})$, the container for $I$, by

$A_{i^{\prime}}=V_{i^{\prime}}\setminus\\{u_{j}:j\in W\\}$

and $A_{j}=V_{j}$ for $j\neq i^{\prime}$ and STOP.

  5. (C5)

Otherwise, let $\mathcal{H}^{x}\leftarrow\mathcal{G}_{*}$, $x\leftarrow
x^{\prime}$ and $s\leftarrow s+1$ and CONTINUE.

We will show that the above procedure indeed constructs containers for
$\mathcal{I}_{m}(\mathcal{H})$ that have the desired properties. To this end,
we first claim that for each $x\in\mathcal{U}\cup\\{0\\}$, the hypergraph
$\mathcal{H}^{x}$, if it was defined, satisfies:

  1. (i)

$I\in\mathcal{I}(\mathcal{H}^{x})$ and

  2. (ii)

$\Delta_{v}(\mathcal{H}^{x})\leq\Delta_{v}^{x}$ for every
$v\in\mathcal{V}(x)$.

Indeed, one may easily prove (i) and (ii) by induction on $|x|-|v|$. The base
case is true by Definition 5.1, and the inductive step follows immediately
from Observation 5.4 and Lemma 5.6.

Secondly, we claim that for each input $I\in\mathcal{I}_{m}(\mathcal{H})$,
step (C4) is called for some $s$ and hence the container
$(A_{1},\ldots,A_{r})$ is defined. If this were not true, the condition in
step (C5) would be met $r+r_{0}-1$ times and, consequently, we would finish
with a non-empty $(0,\dots,0)$-bounded hypergraph $\mathcal{H}^{0}$, i.e., we
would have $\emptyset\in E(\mathcal{H}^{0})$. But this contradicts (i), since
$\emptyset\subset I$, so it would not be independent.

Suppose, therefore, that step (C4) is executed when
$\mathcal{G}=\mathcal{H}^{x}$ for some $x\in\mathcal{U}$. We claim that
$e(\mathcal{H}^{x})\geq\beta_{s}e(\mathcal{H})$. This is trivial if $s=0$
since here $\mathcal{H}^{x}=\mathcal{H}$, and for $s>0$ it holds since
otherwise step (C4) would have been executed in the previous iteration. We
therefore have

$e(\mathcal{G})=e(\mathcal{H}^{x})\geq\beta_{s}e(\mathcal{H})\qquad\text{and}\qquad
e(\mathcal{G}_{*})<\beta_{s+1}e(\mathcal{H}),$

which, by Lemma 5.7 and (ii), implies that either (P2) or (P3) of Lemma 5.7
holds. Define $\delta=2^{-(r_{0}+r-1)(2r_{0}+r)}R^{-1}$ and note that
$\delta\leq\alpha_{s}R^{-1}$ for all $s\in[0,r_{0}+r-1]$. If $i^{\prime}<r$,
we see that (P2) implies

$|W|\geq
2^{-r-1}R^{-1}\alpha_{s}|V_{i^{\prime}}|\geq\alpha_{r}R^{-1}|V_{i^{\prime}}|\geq\delta|V_{i^{\prime}}|,$

Similarly, if $i^{\prime}=r$, then by (P3),

$|W|\geq 2^{-r_{0}-r-1}R^{-1}\alpha_{s}q\geq\alpha_{r_{0}+r-1}R^{-1}q=\delta
q.$

This verifies that $(A_{1},\ldots,A_{r})$ satisfies property (ii) from the
statement of Theorem 2.1.

Let $\mathcal{S}$ denote the set of all tuples $(S_{1},\dots,S_{r})$ that were
defined in (C3) when running the procedure for all
$I\in\mathcal{I}_{m}(\mathcal{H})$. We define $g(I)=(S_{1},\dots,S_{r})$ and
$f(g(I))=(A_{1},\dots,A_{r})$, where $(A_{1},\dots,A_{r})$ is the container
tuple that was defined in (C4). Note that $f$ is well-defined by Observation
5.5. This follows directly when $i^{\prime}<r$, since here the set
$S_{i^{\prime}}$ is equivalent to the set $S$ obtained in (C2). But then, in
particular, everything will be the same the first time that $i^{\prime}=r$,
and hence $r$–maximum vertices will be considered at the same time.

Finally, we see that clearly the inclusion statements of properties (i) and
(iii) hold by construction, and the second one in (iii) is true since every
$S_{i}$ starts empty and we stop as soon as (C4) is true for the first time. ∎

##  6 Concluding Remarks

In this paper we have focussed on the asymmetric version of the typical
structure of a pair of sets subject to a constraint on the size of their
sumset. As explained in the introduction, this formulation of the result is
very natural with respect to the perspective of classical results on sumsets
like the Brunn–Minkowski inequality or Kneser’s theorem. As illustrated by
this paper, obtaining such asymmetric versions of results in additive
combinatorics, which is most often concerned with studying a single set
possessing some additive structure, can be a nontrivial task. It is worth
noting that our result as is does not supersede but rather complements the one
by Campos [5] for the case $A=B$: The latter cannot be directly derived from
ours, as here the estimations leading to an almost surely result are based on
the random choice of two independent sets rather than only one. Still, the
quantitative bounds of our result are comparable when considering sets of the
same size.

Even if a simpler version of the container result, Theorem 2.1, would have
been sufficient for the proof of our main result, we have chosen to state it
in more generality, at no cost, as in this wider generality the result may be
suitable to address a number of additional applications, which nevertheless
require developments which do not fit the length of a single paper.

It is possible to prove a straight-forward generalization of Theorem 2.2 for
arbitrary fixed $h$ using the same arguments that were used in the $h=2$ case,
but there are some caveats in the specifics. Still, in light of this fact, a
natural step further is to handle multiple set addition: if
$A_{1},\ldots,A_{k}$ is a family of independently chosen random sets of
integers with cardinality $s$ among those satisfying a constraint on their
sumset, say $|A_{1}+\cdots+A_{l}|\leq Ks$, then with high probability each of
the sets is almost contained in an arithmetic progression of size $Ks/l$
having the same common difference. The quantitative aspects of the statement
depend on the strength of supersaturation and stability results analogous to
Corollaries 3.2 and 3.4, which are only partially existing in the literature.
Tight bounds on the cardinality of multiple set addition can be found for
example in Lev [16], but to our knowledge no inverse results deriving the
structure of sets in this multiple addition setting are available. A result of
this kind, both for the analogue of the $3k-4$ theorem and its robust version
might be attained along the lines of known results for the addition of two
distinct sets by the use of the multiple set addition version of Kneser’s
theorem given by DeVos, Goddyn, and Mohar [8]. This opens a path to be yet
explored.

A second natural direction is to translate the structural result into the more
general setting of arbitrary abelian groups. The parameter $\beta(t)$
measuring the size of the largest subgroup with cardinality up to $t$ is a
useful one when we consider the counting version of our main result. We have
included its asymmetric version in this paper, Theorem 1.2. The structural
description given by Green and Ruzsa [13] in their extension of Freiman’s
theorem to general abelian groups provides a guideline for the structure of
typical sets with bounded sumset in general abelian groups. As explored in
this paper as well as in [5] and [6], the typical structure of sets with
bounded sumset in the integers, in this case plain arithmetic progressions, is
a lot simpler than the general one given by Freiman’s theorem, so one would
expect the same to be the case in more general groups. The recently obtained
robust version of the Balog-Szemerédi-Gowers theorem by Shao [24], combined
with an appropriate Freiman $3k-4$ type theorem seems to be the correct set of
tools to achieve this objective. An important natural case to explore is that
of groups of prime order, $G=\mathbb{Z}/p\mathbb{Z}$, where sufficiently
strong analogues of the Freiman $3k-4$ Freiman theorem are already available
and an equivalent statement of our main result might require less work to
prove.

An even less explored direction is to also translate the structural result to
general groups, not necessarily abelian. Perhaps the more appropriate quest in
this setting is to ask for the typical structure of approximate groups in the
light of its structural characterization by Breuillard, Green and Tao [4].

Coming back to more classical problems in additive combinatorics, let us
conclude by mentioning a natural example which can illustrate the use of the
techniques used in this paper, the case of $A+B$ when $B=\lambda\ast A$, the
_dilation_ of $A$ by some factor $\lambda$. It is known that $A+\lambda\ast A$
has size at least $(\lambda+1)|A|$ and, for $\lambda$ prime, the structure of
extremal sets is known [7]. Can one prove an approximate structure result
similar in scope to Theorem 1.1 for this specific problem?

## References

  * [1] Noga Alon, József Balogh, Robert Morris, and Wojciech Samotij, _A refinement of the Cameron-Erdős conjecture_ , Proc. Lond. Math. Soc. (3) 108 (2014), no. 1, 44–72.
  * [2] Antal Balog and Endre Szemerédi, _A statistical theorem of set addition_ , Combinatorica 14 (1994), no. 3, 263–268 (English).
  * [3] József Balogh, Robert Morris, and Wojciech Samotij, _Independent sets in hypergraphs_ , J. Amer. Math. Soc. 28 (2015), no. 3, 669–709.
  * [4] Emmanuel Breuillard, Ben Green, and Terence Tao, _The structure of approximate groups_ , Publ. Math. Inst. Hautes Études Sci. 116 (2012), 115–221.
  * [5] Marcelo Campos, _On the number of sets with a given doubling constant_ , Israel J. Math. 236 (2020), no. 2, 711–726.
  * [6] Marcelo Campos, Maurício Collares, Robert Morris, Natasha Morrison, and Victor Souza, _The Typical Structure of Sets With Small Sumset_ , International Mathematics Research Notices (2021), 1–45, rnab021.
  * [7] Javier Cilleruelo, Yahya O. Hamidoune, and Oriol Serra, _On sums of dilates_ , Combin. Probab. Comput. 18 (2009), no. 6, 871–880.
  * [8] Matt DeVos, Luis Goddyn, and Bojan Mohar, _A generalization of Kneser’s addition theorem_ , Adv. Math. 220 (2009), no. 5, 1531–1548.
  * [9] G. A. Freĭman, _Foundations of a structural theory of set addition_ , Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R. I., 1973, Translated from the Russian.
  * [10] R. J. Gardner and P. Gronchi, _A Brunn-Minkowski inequality for the integer lattice_ , Trans. Amer. Math. Soc. 353 (2001), no. 10, 3995–4024.
  * [11] W. T. Gowers, _A new proof of Szemerédi’s theorem for arithmetic progressions of length four_ , Geom. Funct. Anal. 8 (1998), no. 3, 529–551 (English).
  * [12] Ben Green and Robert Morris, _Counting sets with small sumset and applications_ , Combinatorica 36 (2016), no. 2, 129–159.
  * [13] Ben Green and Imre Z. Ruzsa, _Freiman’s theorem in an arbitrary abelian group_ , J. Lond. Math. Soc. (2) 75 (2007), no. 1, 163–175.
  * [14] Yahya. O. Hamidoune and Oriol Serra, _A note on Pollard’s Theorem_ , arXiv e-prints (2008), arXiv:0804.2593.
  * [15] Martin Kneser, _Abschätzung der asymptotischen Dichte von Summenmengen_ , Math. Z. 58 (1953), 459–484.
  * [16] Vsevolod F. Lev, _Structure theorem for multiple addition and the Frobenius problem_ , J. Number Theory 58 (1996), no. 1, 79–88.
  * [17] , _Restricted set addition in groups. I. The classical setting_ , J. London Math. Soc. (2) 62 (2000), no. 1, 27–40.
  * [18] , _Restricted set addition in groups. III. Integer sumsets with generic restrictions_ , Period. Math. Hungar. 42 (2001), no. 1-2, 89–98.
  * [19] Vsevolod F. Lev and Pavel Y. Smeliansky, _On addition of two distinct sets of integers_ , Acta Arith. 70 (1995), no. 1, 85–91.
  * [20] Robert Morris, Wojciech Samotij, and David Saxton, _An asymmetric container lemma and the structure of graphs with no induced $4$-cycle_, 2018, arXiv:1806.03706.
  * [21] J. M. Pollard, _A generalisation of the theorem of Cauchy and Davenport_ , J. London Math. Soc. (2) 8 (1974), 460–462.
  * [22] Imre Z. Ruzsa, _Sum of sets in several dimensions_ , Combinatorica 14 (1994), no. 4, 485–490.
  * [23] David Saxton and Andrew Thomason, _Hypergraph containers_ , Invent. Math. 201 (2015), no. 3, 925–992.
  * [24] Xuancheng Shao, _On an almost all version of the Balog-Szemerédi-Gowers theorem_ , Discrete Anal. 2019 (2019), 18 (English), Id/No 12.
  * [25] Xuancheng Shao and Wenqiang Xu, _A robust version of Freiman’s $3k-4$ theorem and applications_, Math. Proc. Cambridge Philos. Soc. 166 (2019), no. 3, 567–581.
  * [26] Yonutz Stanchescu, _On addition of two distinct sets of integers_ , Acta Arith. 75 (1996), no. 2, 191–194.

## Acknowledgments

Marcelo Campos is partially supported by CNPq.
Matthew Coulson is supported by the Spanish Ministerio de Economá y
Competitividad through the project MTM2017-82166-P and the FPI-scholarship
PRE2018-083621.
Oriol Serra is supported by the Spanish Agencia Estatal de Investigación under
project PID2020-113082GB-I00.
This research was conducted while Maximilian Wötzel was a member of the
Barcelona Graduate School of Mathematics (BGSMath) as well as the Universitat
Politécnica de Catalunya. M. W. also acknowledges financial support from the
Fondo Social Europeo and the Agencia Estatal de Investigación through the FPI
grant number MDM-2014-0445-16-2 and the Spanish Ministry of Economy and
Competitiveness, through the María de Maeztu Programme for Units of Excellence
in R&D (MDM-2014-0445), through the project MTM2017-82166-P, as well as from
the Dutch Science Council (NWO) through the grant number OCENW.M20.009.

##  Appendix A Proof of Lemma 4.2

Dividing by the binomial coefficients on the right hand side of (25) and
taking the logarithm, we need to prove

$\sum_{i=0}^{t-1}\log\bigg{(}1-\frac{(2\sqrt{\epsilon}-2\epsilon)m}{\frac{tm}{s+t}-i}\bigg{)}+\sum_{j=0}^{s-1}\log\bigg{(}1+\frac{2\sqrt{\epsilon}m}{\frac{sm}{s+t}-j}\bigg{)}\leq-\epsilon(s+t).$
(47)

By using the bound $\log(1+x)\leq x-\frac{x^{2}}{2}+\frac{x^{3}}{3}$ valid on
the interval $(-1,\infty)$, it suffices to prove the upper bound in (47) for
the expression

$\begin{split}&-2(\sqrt{\epsilon}-\epsilon)\sum_{i=0}^{t-1}\left(\frac{t}{s+t}-\frac{i}{m}\right)^{-1}-\frac{(2\sqrt{\epsilon}-2\epsilon)^{2}}{2}\sum_{i=0}^{t-1}\left(\frac{t}{s+t}-\frac{i}{m}\right)^{-2}\\\
&+2\sqrt{\epsilon}\sum_{j=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-1}-2\epsilon\sum_{i=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-2}+4\epsilon^{3/2}\sum_{i=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-3}.\end{split}$
(48)

Next, we are going to approximate the sums in (48) by integrals, using the
bounds

$\int_{a}^{b}f(x)-\frac{2(b-a)||f||_{\infty}}{n}\leq\frac{1}{n}\sum_{i=na}^{nb}f\left(\frac{i}{n}\right)\leq\int_{a}^{b}f(x)$

which hold for any continuous, non-decreasing function $f$ on the interval
$[a,b]$. We start with the linear terms. Defining $K>(1+\alpha)$ by
$m=K(s+t)$, we get

$\begin{split}-2(\sqrt{\epsilon}-\epsilon)\sum_{i=0}^{t-1}\frac{1}{\frac{t}{s+t}-\frac{i}{m}}&\leq-2(\sqrt{\epsilon}-\epsilon)\left(m\int_{0}^{t/m}\frac{1}{\frac{t}{s+t}-x}dx-2\frac{t}{m}\left(\frac{t}{s+t}-\frac{t}{m}\right)^{-1}\right)\\\
&=-2(\sqrt{\epsilon}-\epsilon)\left(-m\log\left(1-\frac{s+t}{m}\right)-\frac{2}{K-1}\right)\\\
&\leq-2m(\sqrt{\epsilon}-\epsilon)\log\left(\frac{K}{K-1}\right)+\frac{4\sqrt{\epsilon}}{K-1},\end{split}$
(49)

and similarly

$\begin{split}2\sqrt{\epsilon}\sum_{j=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-1}&\leq
2m\sqrt{\epsilon}\log\left(\frac{K}{K-1}\right).\end{split}$ (50)

For the quadratic terms, we see that

$\begin{split}-\frac{(2\sqrt{\epsilon}-2\epsilon)^{2}}{2}\sum_{i=0}^{t-1}\left(\frac{t}{s+t}-\frac{i}{m}\right)^{-2}&\leq-\frac{(2\sqrt{\epsilon}-2\epsilon)^{2}}{2}\left(\frac{K(s+t)^{2}}{t(K-1)}-\frac{2K(s+t)}{t(K-1)^{2}}\right)\\\
&\leq-\frac{2\epsilon
K(s+t)^{2}}{t(K-1)}+\frac{4\epsilon^{3/2}K(s+t)^{2}}{t(K-1)}+\frac{8\epsilon
K(s+t)}{t(K-1)^{2}},\end{split}$ (51)

and similarly for the one involving $s$,

$\begin{split}-2\epsilon\sum_{i=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-2}\leq-\frac{2\epsilon
K(s+t)^{2}}{s(K-1)}+\frac{4\epsilon K(s+t)}{s(K-1)^{2}}.\end{split}$ (52)

Finally, for the cubic term we see that

$\begin{split}4\epsilon^{3/2}\sum_{i=0}^{s-1}\left(\frac{s}{s+t}-\frac{j}{m}\right)^{-3}&\leq\frac{2\epsilon^{3/2}K(2K-1)(s+t)^{3}}{s^{2}(K-1)^{2}}.\end{split}$
(53)

Note that the $2m\sqrt{\epsilon}$ parts of the linear terms cancel out, while

$2\epsilon K(s+t)\log\left(\frac{K}{K-1}\right)\leq\frac{2\epsilon
K(s+t)^{2}}{\max(s,t)(K-1)},$

which follows from the fact that $x\log(1+x^{-1})\leq 1$ for all $x>0$. On the
other hand, because of $(s+t)\geq 2^{5}\alpha^{-1}\geq 2^{5}(K-1)^{-1}$ and
the bounds on $\epsilon$, the sum of all remaining positive term in Equations
(49)–(53) can be upper bounded by $\frac{\epsilon
K(s+t)^{2}}{\min(s,t)(K-1)}$, and hence we see that

$\eqref{eq:binom_prod_taylor}\leq-\frac{\epsilon
K(s+t)^{2}}{\min(s,t)(K-1)}\leq-\epsilon(s+t),$

which implies (47) and hence proves the statement. $\blacksquare$