# Large Sumsets from Medium-Sized Subsets

Béla Bollobás and Imre Leader and Marius Tiba  Department of Pure Mathematics
and Mathematical Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK, and
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152,
USA<EMAIL_ADDRESS>Department of Pure Mathematics and
Mathematical Statistics, Wilberforce Road, Cambridge, CB3 0WA, UK
<EMAIL_ADDRESS>IMPA, Estrada Dona Castorina 110, Rio de Janeiro,
Brazil<EMAIL_ADDRESS>
###### Abstract.

The classical Cauchy–Davenport inequality gives a lower bound for the size of
the sum of two subsets of ${\mathbb{Z}}_{p}$, where $p$ is a prime. Our main
aim in this paper is to prove a considerable strengthening of this inequality,
where we take only a small number of points from each of the two subsets when
forming the sum. One of our results is that there is an absolute constant
$c>0$ such that if $A$ and $B$ are subsets of ${\mathbb{Z}}_{p}$ with
$|A|=|B|=n\leqslant p/3$ then there are subsets $A^{\prime}\subset A$ and
$B^{\prime}\subset B$ with $|A^{\prime}|=|B^{\prime}|\leqslant c\sqrt{n}$ such
that $|A^{\prime}+B^{\prime}|\geqslant 2n-1$. In fact, we show that one may
take any sizes one likes: as long as $c_{1}$ and $c_{2}$ satisfy
$c_{1}c_{2}\geqslant cn$ then we may choose $|A^{\prime}|=c_{1}$ and
$|B^{\prime}|=c_{2}$. We prove related results for general abelian groups.

The first author was partially supported by NSF grant DMS-1855745

##  1\. Introduction

The Cauchy–Davenport theorem [4, 5, 6] states that if $p$ is a prime and $A$
and $B$ are non-empty subsets of ${\mathbb{Z}}_{p}$ with $|A|+|B|\leqslant
p+1$ then $|A+B|\geqslant|A|+|B|-1$. Intervals show that this bound is best
possible. Over the years, this classical result was followed by a host of
important contributions about sums of subsets of groups, including other
abelian groups such as ${\mathbb{Z}}$ itself. For these contributions, see,
among others, Mann [17, 18], Kneser [16], Erdős and Heilbronn [9], Freiman
[10, 11, 12, 13], Plünnecke [20], Ruzsa [21], Dias da Silva and Hamidoune [7],
Alon, Nathanson and Ruzsa [1], Shao [22], Stanchescu [23], Breuillard, Green
and Tao [3], as well as the books of Nathanson [19], Tao and Vu [24] and
Grynkiewicz [15].

Recently, a new direction of research was started in [2]: can we get similar
bounds for the size of the sum if $A+B$ is replaced by $A+B^{\prime}$, where
$B^{\prime}$ is a small subset of $B$? Among other results, it was proved that
if $A$ and $B$ are finite non-empty subsets of ${\mathbb{Z}}$ with
$|A|\geqslant|B|$ then $B^{\prime}$ can be taken to be really small: there are
three elements $b_{1},b_{2},b_{3}\in B$ such that
$|A+\\{b_{1},b_{2},b_{3}\\}|\geqslant|A|+|B|-1$. For ${\mathbb{Z}}_{p}$, it
was shown that if $A,B\subset{\mathbb{Z}}_{p}$ with $|A|=|B|=n\leqslant p/3$
then $B$ has a subset $B^{\prime}$ with at most $c$ elements such that
$|A+B^{\prime}|\geqslant 2n-1$, where $c$ is an absolute constant. (Here again
$p$ is prime, and for the rest of this paper $p$ will always denote a prime.)

Our aim in this paper is to prove that actually one can replace both $A$ and
$B$ by appropriate small subsets. In the result just mentioned, the product of
the sizes of our two subsets in the sum, namely $A$ and $B^{\prime}$, is $cn$,
and trivially we cannot ever get a sum of size linear in $n$ without the
product of the sizes of the two sets being linear in $n$. But, remarkably, one
can indeed always choose subsets $A^{\prime}$ of $A$ and $B^{\prime}$ of $B$,
of any desired sizes, as long as the product of these sizes is linear in $n$.

The result mentioned in the Abstract has both sizes being a constant times
$\sqrt{n}$, and the sets $A$ and $B$ themselves have size bounded away from
$p/2$. The general form of our result is as follows.

######  Theorem 1.

For all $\alpha,\beta>0$ there exists $c>0$ such that the following holds. Let
$A$ and $B$ be non-empty subsets of $\mathbb{Z}_{p}$ with
$\alpha|B|\leqslant|A|\leqslant\alpha^{-1}|B|$ and
$|A|+|B|\leqslant(1-\beta)p$. Then, for any integers $1\leqslant
c_{1}\leqslant|A|$ and $1\leqslant c_{2}\leqslant|B|$ such that
$c_{1}c_{2}\geqslant c\max(|A|,|B|)$, there exist subsets $A^{\prime}\subset
A$ and $B^{\prime}\subset B$, of sizes $c_{1}$ and $c_{2}$ such that
$|A^{\prime}+B^{\prime}|\geqslant|A|+|B|-1$.

It is rather surprising that this holds with no other restrictions on the
values of $c_{1}$ and $c_{2}$, whatever the form of the sets $A$ and $B$. We
remark that the constant $c$ does have to depend on $\beta$: if our two sets
are allowed to have sizes whose sum approaches $p$ then taking random subsets
shows that $c$ has to grow. Also, it is easy to see that $c$ depends on
$\alpha$. For example, if $B$ is far larger than $A$ then trivially taking $c$
points from $B$ to be summed with all of $A$ will yield a sumset that is too
small.

Our main tool is a similar result that is valid in general abelian groups. The
reader will note that it is ‘worse’ than the above result in that there is an
error term, but it is also far ‘better’ because the lower bound comes from the
sum of two actual sets (the sets $A^{*}$ and $B^{*}$ below) rather than merely
from the lower bound that comes from the sum of their sizes (or, more
precisely, the general Kneser lower bound that generalises the
Cauchy–Davenport theorem).

######  Theorem 2.

For all $K$ and $\varepsilon>0$ there exists $c$ such that the following
holds. Let $A$ and $B$ be finite non-empty subsets of an abelian group, and
let $1\leqslant c_{1}\leqslant|A|$ and $1\leqslant c_{2}\leqslant|B|$ be
integers satisfying $c_{1}c_{2}\geqslant c\max(|A|,|B|)$. Then there are
subsets $A^{*}\subset A$ and $B^{*}\subset B$, with
$|A^{*}|\geqslant(1-\varepsilon)|A|$ and $|B^{*}|\geqslant(1-\varepsilon)|B|$,
such that if we select points $a_{1},\ldots,a_{c_{1}}$ and
$b_{1},\ldots,b_{c_{2}}$ uniformly at random from $A^{*}$ and $B^{*}$ then,
writing $A^{\prime}$ for $\\{a_{1},\ldots,a_{c_{1}}\\}$ and $B^{\prime}$ for
$\\{b_{1},\ldots,b_{c_{2}}\\}$, we have

${\mathbb{E}}|A^{\prime}+B^{\prime}|\geqslant\min\big{(}(1-\varepsilon)|A^{*}+B^{*}|,\
K|A^{*}|,\ K|B^{*}|\big{)}.$

We remark that the terms $K|A^{*}|$ and $K|B^{*}|$ are only present to deal
with unimportant cases: the key term is $(1-\varepsilon)|A^{*}+B^{*}|$. Thus
the result is informally somehow saying that, in terms of sumsets, $A^{*}$ and
$B^{*}$ may really be approximated by very small subsets of themselves (and
indeed most subsets will do).

Interestingly, while this theorem is for general abelian groups, Theorem 1 is
only about $\mathbb{Z}_{p}$. The passage between these does require quite a
lot of work.

The plan of the paper is as follows. In Section 2 we give various
prerequisites that we shall need. Then in Section 3 we prove Theorem 2, and
also provide the consequence of it in $\mathbb{Z}_{p}$ that we use in the
proof of Theorem 1. In Section 4 we prove Theorem 1, and the last section,
Section 5, contains open problems.

Our notation is standard. Sometimes we write ‘$x\mod d$’ as shorthand for the
infinite arithmetic progression $\\{y\in\mathbb{Z}:y\equiv x\mod d\\}$, and
refer to it as a fibre mod $d$. When $S$ is a subset of $\mathbb{Z}$ we often
write $S^{x}$ for the intersection of this fibre with $S$ – when the value of
$d$ is clear. (We sometimes write $S^{x}$ as $S^{x}_{d}$ when we want to
stress the value of $d$.) Thus $S^{x}=S\cap\pi^{-1}(x)$, where $\pi=\pi_{d}$
denotes the natural projection from $\mathbb{Z}$ to $\mathbb{Z}_{d}$.

When we write a probability or an expectation over a finite set, we always
assume that the elements of the set are being sampled uniformly. Thus, for
example, for a finite set $X$ we denote the expectation and probability when
we sample uniformly over all $x\in X$ by ${\mathbb{E}}_{x\in X}\text{ and
}\operatorname*{\mathbb{P}}_{x\in X}$. We also often sample uniformly over all
$c$-sets of a given set $X$. In most of those cases, we could instead sample
$c$ elements uniformly and independently, but the notation would tend to get
unwieldy, and this is why we use the sampling over all $c$-sets instead.

Before we turn to the next section, let us draw attention to the superficial
similarity of our problems to a beautiful result of Ellenberg [8]. Given a
prime $p$ and a positive integer $d$, let $f(p^{d})$ be the smallest integer
such that for any sets $S,T\subset{\mathbb{Z}}_{p}^{d}$ there are subsets
$S^{\prime}\subset S$ and $T^{\prime}\subset T$ satisfying
$(S+T^{\prime})\cup(S^{\prime}+T)=S+T$ and $|S^{\prime}|+|T^{\prime}|\leqslant
f(p^{d})$. Ellenberg proved that $f(p^{d})\leqslant(cp)^{d}$, where $c<1$ is
an absolute constant.

##  2\. Prerequisites

In this section we collect together the various prerequisites that we will
need. Each of these may be treated as a ‘black box’: knowledge of their proofs
will not be required.

The first of the three theorems we shall need is due to Shao [22], and
concerns restricted sums. Let $A$ and $B$ be subsets of an abelian group, and
let $\Gamma\subset A\times B$. The $\Gamma$-restricted sum of $A$ and $B$ is
$A+_{\Gamma}B=\\{a+b:\ a\in A,\ b\in B,(a,b)\in\Gamma\\}$. Here is the result
of Shao.

######  Theorem 3.

For all $\varepsilon,K>0$ there exists $\delta>0$ such that the following
holds. Let $G$ be an abelian group and let $N\in\mathbb{N}$. Let $A,B\subset
G$ be two subsets with $|A|,|B|\geqslant N$. Let $\Gamma\subset A\times B$ be
a subset with $|\Gamma|\geqslant(1-\delta)|A||B|$. If $|A+_{\Gamma}B|\leqslant
KN$, then there exist $A_{0}\subset A$ and $B_{0}\subset B$ such that

$|A_{0}|\geqslant(1-\varepsilon)|A|\text{ and
}|B_{0}|\geqslant(1-\varepsilon)|B|\text{ and
}|A_{0}+B_{0}|\leqslant|A+_{\Gamma}B|+\varepsilon N.$

The second theorem is an easy corollary of a theorem of Grynkiewicz [15].

######  Theorem 4.

Given $\beta,\gamma>0$ there is an $\varepsilon>0$ such that the following
holds. Let $A$ and $B$ be subsets of $\mathbb{Z}_{p}$. Suppose that
$2\leqslant\min(|A|,|B|)\text{ and }|A|+|B|\leqslant(1-\beta)p$ and
$|A+B|\leqslant|A|+|B|-1+\varepsilon\min(|A|,|B|)$. Then there are arithmetic
progressions $P$ and $Q$ with the same common difference that contain $A$ and
$B$ and satisfy $|P\Delta A|\leqslant\gamma\min(|A|,|B|)\text{ and }|Q\Delta
B|\leqslant\gamma\min(|A|,|B|)$.

The last theorem we need is a somewhat technical result from [2]. It gives a
strengthening of the result from [2] mentioned above about sums in
$\mathbb{Z}_{p}$, when the sets $A$ and $B$ ‘relate nicely’ to intervals.

######  Theorem 5.

For all $\beta>0$ there exists $\gamma>0$ such that for every $\alpha>0$ there
is a value of $c$ for which the following holds. Let $A$ and $B$ be subsets of
$\mathbb{Z}_{p}$ and let $I=[p_{l},p_{r}]$ and $J=[q_{l},q_{r}]$ be intervals
in $\mathbb{Z}_{p}$ satisfying $\alpha|J|\leqslant|I|\leqslant\alpha^{-1}|J|$,
$|I|+|J|\leqslant(1-\beta)p$, $\max(|A\Delta I|,|B\Delta
J|)\leqslant\gamma\min(|I|,|J|)$ and $\\{q_{l},q_{r}\\}\subset B\subset J$.
Then there is a family $\mathcal{F}\subset B^{(c)}$, depending only on $I$,
$J$ and $B$ (but not on $A$), such that

$\operatorname*{\mathbb{E}}_{B^{\prime}\in\mathcal{F}}|A+B^{\prime}|\geqslant|A|+|J|-1\geqslant|A|+|B|-1.$

##  3\. Proof of Theorem 2

In this section we prove our main result on general abelian groups, Theorem 2.

We start by giving a brief overview of the proof. Although this paper is self-
contained, we mention that the reader who is familiar with [2] will see that
this proof is similar in spirit to the proof of Theorem 10 in that paper.

We will repeatedly apply Theorem 3 in order to construct a decreasing sequence
of $s+1$ pairs of sets
$(A,B)=(A_{0},B_{0}),(A_{1},B_{1}),\dots,(A_{s},B_{s})$, satisfying
$A_{i}\subset A_{i-1}$ and $B_{i}\subset B_{i-1}$ and
$|A_{i}|>(1-\varepsilon/s)^{i}|A|$ and $|B_{i}|>(1-\varepsilon/s)^{i}|B|$.
Having constructed $A_{i}$ and $B_{i}$ we divide the elements of $A_{i}+B_{i}$
into the set $P_{i}$ of ‘popular’ ones (those hit at least
$\alpha\min(|A_{i}|,|B_{i}|)$ times) and the set $U_{i}$ of unpopular ones.
And we let $\Gamma$ be the pairs summing to popular elements.

We first deal with the situation when $|\Gamma|$ is much smaller than
$|A_{i}||B_{i}|$ or $|P_{i}|$ is much larger than $K\min(|A_{i}|,|B_{i}|)$. In
both cases a simple computational check shows that the pair $(A_{i},B_{i})$
has the desired properties. If we are not in this situation then we can apply
Thm 3 to $A_{i},B_{i}$ and $\Gamma$ to construct the sets $A_{i+1}$,
$B_{i+1}$. These satisfy
$|A_{i+1}+B_{i+1}|<|P_{i}|+(\varepsilon/s)\min(|A_{i+1}|,|B_{i+1}|)$.

We then deal with the case when the process continues for at least $s$ steps.
In this case we have
$|A_{i+1}+B_{i+1}|-(\varepsilon/s)\min(|A_{i+1}|,|B_{i+1}|)<|P_{i}|<|A_{i}+B_{i}|$,
where the second inequality is clear and the first is by Theorem 3.

As $|P_{0}|<10K\min(|A_{0}|,|B_{0}|)$ and $|A_{s}+B_{s}|>|B_{s}|>|B_{0}|/2$,
we deduce that there exists $i$ such that $|P_{i}|$ is about then easy to
check that the pair of sets $(A_{i},B_{i})$ has the desired property. Indeed,
if $c$ is large enough (depending on $\alpha$), then $|A^{\prime}+B^{\prime}|$
is about $|P_{i}|$ as each point in $P_{i}$ is hit with high probability. So
we conclude that $|A^{\prime}+B^{\prime}|$ is about $|A_{i}+B_{i}|$.

We now turn to the proof itself.

###### Proof of Theorem 2.

Fix $\varepsilon>0$ and $K>0$, where we assume that $\varepsilon$ is
sufficiently small and $K$ is sufficiently large. Pick
$s=\lfloor\frac{50K}{\varepsilon}\rfloor$. Let $\delta$ be given by Theorem 3
with parameters $\frac{\varepsilon}{s}$ and $10K$. Also pick
$\alpha=\delta/16K$. Finally, pick
$c\geqslant\max(2^{10}K/\delta,2^{10}|\log(\epsilon)|/\alpha)$. We may assume
that $|A|\geqslant|B|$.

We shall examine a process in which we repeatedly apply Theorem 3 in order to
construct a decreasing sequence of $s+1$ pairs of sets
$(A,B)=(A_{0},B_{0}),(A_{1},B_{1}),\ldots,(A_{s},B_{s}),$ satisfying
$A_{i}\subset A_{i-1}\text{ and }B_{i}\subset B_{i-1}$ and
$|A_{i}|\geqslant(1-\varepsilon/s)^{i}|A|$ and
$|B_{i}|\geqslant(1-\varepsilon/s)^{i}|B|$. Fix $i<s$ and assume that the pair
of sets $(A_{i},B_{i})$ has already been constructed. We shall either stop the
process at step $i$ or construct the pair of sets $(A_{i+1},B_{i+1})$.

Let $A_{i}+B_{i}=C_{i}^{+}\sqcup C_{i}^{-}$ be the partition into ‘popular’
and ‘unpopular’ elements given by $C_{i}^{+}=\\{c\in A_{i}+B_{i}:\
|(c-A_{i})\cap B_{i}|\geqslant\alpha|B_{i}|\\}$, and $C_{i}^{-}=\\{c\in
A_{i}+B_{i}:\ |(c-A_{i})\cap B_{i}|<\alpha|B_{i}|\\}$. Also, let the partition
$A_{i}\times B_{i}=\Gamma_{i}\sqcup\Gamma_{i}^{c}$ be given by
$\Gamma_{i}=\\{(a,b)\in A_{i}\times B_{i}:\ a+b\in C_{i}^{+}\\}\subset
A_{i}\times B_{i}$, and $\Gamma_{i}^{c}=\\{(a,b)\in A_{i}\times B_{i}:\ a+b\in
C_{i}^{-}\\}\subset A_{i}\times B_{i}$, so that
$A_{i}+_{\Gamma_{i}}B_{i}=C_{i}^{+}$ and
$A_{i}+_{\Gamma^{c}_{i}}B_{i}=C_{i}^{-}$. Finally, for each $x\in A_{i}+B_{i}$
set

$A_{i}^{x}=(x-B_{i})\cap A_{i}\text{ and }B_{i}^{x}=(x-A_{i})\cap B_{i}\text{
such that }A_{i}^{x}=x-B_{i}^{x},$
$r_{i}(x)=|A_{i}^{x}|=|B_{i}^{x}|=|\\{(a,b)\in A_{i}\times B_{i}:\ x=a+b\\}|,$

so that $\sum_{x}r_{i}(x)=|A_{i}||B_{i}|.$ We stop this process ‘early’, at
step $i$, if

$|\Gamma_{i}|<(1-\delta)|A_{i}||B_{i}|\text{ or
}|A_{i}+_{\Gamma_{i}}B_{i}|>10K\min(|A_{i}|,|B_{i}|).$

Otherwise, we apply Theorem 3 with parameters $\varepsilon/s,10K$ to the pair
of sets $(A_{i},B_{i})$. Thus we produce a pair of sets $(A_{i+1},B_{i+1})$,
satisfying $A_{i+1}\subset A_{i}$, $B_{i+1}\subset B_{i}$,
$|A_{i+1}|\geqslant(1-\varepsilon/s)|A_{i}|$,
$|B_{i+1}|\geqslant(1-\varepsilon/s)|B_{i}|$ and
$|A_{i+1}+B_{i+1}|\leqslant|A_{i}+_{\Gamma_{i}}B_{i}|+\frac{\varepsilon}{s}\min(|A_{i}|,|B_{i}|)$.
We shall analyse separately the cases in which the process continues until the
end and in which the process stops before that.

Before we begin, we need one easy estimate. Suppose the process continues
until step $j$. If we choose elements $a_{1},\ldots,a_{n_{A}}$ and
$b_{1},\ldots,b_{n_{B}}$ uniformly at random from $A_{j}$ and $B_{j}$, and we
write $A^{\prime}_{j}=\\{a_{1},\ldots,a_{n_{A}}\\}$ and
$B^{\prime}_{j}=\\{b_{1},\ldots,b_{n_{B}}\\}$, then we have

$\begin{split}{\mathbb{E}}|A_{j}^{\prime}+B_{j}^{\prime}|&=\sum_{x}\operatorname*{\mathbb{P}}(x\in
A_{j}^{\prime}+B_{j}^{\prime})\\\
&\geqslant\sum_{x}\sum_{\begin{subarray}{c}X\subset A_{j}^{x},Y\subset
B_{j}^{x}\\\ X=x-Y\\\
|X|=|Y|>\frac{n_{B}r_{j}(x)}{2|B_{j}|}\end{subarray}}\mathbb{P}(B_{j}^{\prime}\cap
B_{j}^{x}=Y\text{ and }A_{j}^{\prime}\cap X\neq\emptyset)\\\
&=\sum_{x}\sum_{\begin{subarray}{c}X\subset A_{j}^{x},Y\subset B_{j}^{x}\\\
X=x-Y\\\
|X|=|Y|>\frac{n_{B}r_{j}(x)}{2|B_{j}|}\end{subarray}}\mathbb{P}(B_{j}^{\prime}\cap
B_{j}^{x}=Y)\mathbb{P}(A_{j}^{\prime}\cap X\neq\emptyset)\\\
&=\sum_{x}\operatorname*{\mathbb{P}}(|B_{j}^{\prime}\cap
B_{j}^{x}|>\frac{n_{B}r_{j}(x)}{2|B_{j}|})\min_{\begin{subarray}{c}X\subset
A_{j}^{x}\\\
|X|>\frac{n_{B}r_{j}(x)}{2|B_{j}|}\end{subarray}}\operatorname*{\mathbb{P}}(|A_{j}^{\prime}\cap
X|>0)\\\
&\geqslant\sum_{x}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\max(\frac{n_{A}}{4|A_{j}|},\frac{n_{A}n_{B}r_{j}(x)}{8|A_{j}||B_{j}|}))).\end{split}$
(1)

Here, the last inequality follows from Chernoff’s inequality (see for example
Corollary 1.9 in [24]) and the fact that $|X|>\frac{n_{B}r_{j}(x)}{2|B_{j}|}$
is equivalent to $|X|\geqslant\max(1,\frac{n_{B}r_{j}(x)}{2|B_{j}|})$.

Claim A. Suppose the process stops early, say at step $j<s$. Then the pair of
sets $(A_{j},B_{j})$ has the desired properties.

###### Proof.

Case 1: Consider first the case when
$|C^{+}_{j}|=|A_{j}+_{\Gamma_{j}}B_{j}|>10K\min(|A_{j}|,|B_{j}|).$ For $x\in
C_{j}^{+}$, by construction we have that $r_{j}(x)=|(x-A_{j})\cap
B_{j}|\geqslant\alpha|B_{j}|.$ If we choose elements $a_{1},\ldots,a_{n_{A}}$
and $b_{1},\ldots,b_{n_{B}}$ uniformly at random from $A_{j}$ and $B_{j}$, and
we write $A^{\prime}_{j}=\\{a_{1},\ldots,a_{n_{A}}\\}$ and
$B^{\prime}_{j}=\\{b_{1},\ldots,b_{n_{B}}\\}$, then we have

$\displaystyle{\mathbb{E}}|A_{j}^{\prime}+B_{j}^{\prime}|$
$\displaystyle\geqslant$
$\displaystyle\sum_{x}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\max(\frac{n_{A}}{4|A_{j}|},\frac{n_{A}n_{B}r_{j}(x)}{8|A_{j}||B_{j}|})))$
$\displaystyle\geqslant$
$\displaystyle\sum_{x}(1-\exp(-\frac{cr_{j}(x)}{16|B_{j}|}))^{2}\geqslant\sum_{x\in
C^{+}_{j}}(1-\exp(-\frac{cr_{j}(x)}{16|B_{j}|}))^{2}$ $\displaystyle\geqslant$
$\displaystyle\sum_{x\in C^{+}_{j}}(1-\exp(-2^{-4}\alpha
c))^{2}\geqslant|C_{j}^{+}|/2\geqslant 5K\min(|A_{j}|,|B_{j}|).$

Here the first inequality follows from (1); the second from the hypothesis
$n_{A}n_{B}\geqslant c|A|\geqslant c|A_{j}|$ which, in particular, gives
$n_{B}\geqslant c|B_{j}|$; the fourth from the construction as
$r_{j}(x)\geqslant\alpha|B_{j}|$ for $x\in C_{j}^{+}$; the fifth from the
hypothesis $c\geqslant 2^{10}/\alpha$; and the last inequality follows from
the assumption on the size of $C^{+}_{j}$.

Case 2: Consider now the case when $|\Gamma_{j}|<(1-\delta)|A_{j}||B_{j}|.$ By
construction, $\sum_{x\in C_{j}^{-}}r_{j}(x)\geqslant\delta|A_{j}||B_{j}|.$
Moreover, for $x\in C_{j}^{-}$ we have $r_{j}(x)=|(x-A_{j})\cap
B_{j}|\leqslant\alpha|B_{j}|.$ If we choose elements $a_{1},\ldots,a_{n_{A}}$
and $b_{1},\ldots,b_{n_{B}}$ uniformly at random from $A_{j}$ and $B_{j}$, and
we write $A^{\prime}_{j}=\\{a_{1},\ldots,a_{n_{A}}\\}$ and
$B^{\prime}_{j}=\\{b_{1},\ldots,b_{n_{B}}\\}$, then we have the following
sequence of inequalities. To make the formulae less cluttered, we define
$D_{j}^{-}=\\{x:n_{B}r_{j}(x)\leqslant 2|B_{j}|\\}$ and
$D_{j}^{+}=\\{x:n_{B}r_{j}(x)>2|B_{j}|\\}$.

$\displaystyle{\mathbb{E}}|A_{j}^{\prime}+B_{j}^{\prime}|$
$\displaystyle\geqslant$
$\displaystyle\sum_{x}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\max(\frac{n_{A}}{4|A_{j}|},\frac{n_{A}n_{B}r_{j}(x)}{8|A_{j}||B_{j}|})))$
$\displaystyle\geqslant$ $\displaystyle\sum_{x\in
D_{j}^{-}}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\frac{n_{A}}{4|A_{j}|}))+\sum_{x\in
D_{j}^{+}}2^{-1}(1-\exp(-\frac{n_{A}n_{B}r_{j}(x)}{8|A_{j}||B_{j}|}))$
$\displaystyle\geqslant$ $\displaystyle\sum_{x\in
D_{j}^{-}}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\frac{n_{A}}{4|A_{j}|}))+\sum_{x\in
D_{j}^{+}}2^{-1}(1-\exp(-\frac{8Kr_{j}(x)}{\delta|B_{j}|}))$
$\displaystyle\geqslant$ $\displaystyle\sum_{x\in C_{j}^{-}\cap
D_{j}^{-}}\frac{n_{B}r_{j}(x)}{32|B_{j}|}\frac{n_{A}}{8|A_{j}|}+\sum_{x\in
C_{j}^{-}\cap D_{j}^{+}}\frac{Kr_{j}(x)}{\delta|B_{j}|}\geqslant\sum_{x\in
C_{j}^{-}}\frac{Kr_{j}(x)}{\delta|B_{j}|}\geqslant K|A_{j}|.$

Here, the first inequality follows from (1), the second inequality follows by
splitting into two cases according to how $\frac{n_{B}r(x)}{2|B_{j}|}$
compares to 1, the third inequality follows from the hypothesis
$n_{A}n_{B}\geqslant c|A|\geqslant c|A_{j}|$ and $c\geqslant 2^{10}K/\delta$,
the fourth inequality follows from the two facts that $1-\exp(-t)\geqslant
t/2$ for $0\leqslant t\leqslant 1/2$ and
$\frac{8Kr_{j}(x)}{\delta|B_{j}|}\leqslant\frac{8K\alpha}{\delta}<1/2$ for
$x\in C_{j}^{-}$, the fifth inequality follows again from the hypothesis
$n_{A}n_{B}\geqslant c|A|\geqslant c|A_{j}|$ and $c\geqslant 2^{10}K/\delta$,
and the last inequality follows from the original assumption that $\sum_{x\in
C_{j}^{-}}r_{j}(x)\geqslant\delta|A_{j}||B_{j}|$.

We conclude the pair of sets $(|A_{j}|,|B_{j}|)$ has the desired properties,
so Claim A is proved. ∎

We now turn to the case when the process does not stop early.

Claim B. Suppose that the process continues until the terminal step $s$. Then
there is an index $j\leqslant s$ such that the pair of sets $(A_{j},B_{j})$
has the desired properties.

###### Proof.

Note that
$|A_{1}+B_{1}|\leqslant|A_{0}+_{\Gamma_{0}}B_{0}|+\frac{\varepsilon}{s}\min(|A_{0}|,|B_{0}|)\leqslant
11K\min(|A_{0}|,|B_{0}|).$ Moreover,
$11K\min(|A|,|B|)=11K\min(|A_{0}|,|B_{0}|)\geqslant|A_{1}+B_{1}|\geqslant\ldots\geqslant|A_{s}+B_{s}|\geqslant
0.$ Therefore
$|A_{j+1}+B_{j+1}|\geqslant|A_{j}+B_{j}|-\frac{11K}{s-1}\min(|A|,|B|)$ for
some index $j$, $1\leqslant j\leqslant s$. We shall show that the pair
$(A_{j},B_{j})$ has the desired properties. Indeed, by construction,

$|A_{j}+_{\Gamma_{j}}B_{j}|+\frac{\varepsilon}{s}\min(|A|,|B|)\geqslant|A_{j}+_{\Gamma_{j}}B_{j}|+\frac{\varepsilon}{s}\min(|A_{j}|,|B_{j}|)\geqslant|A_{j+1}+B_{j+1}|.$

It follows that

$|A_{j}+_{\Gamma_{j}}B_{j}|\geqslant|A_{j}+B_{j}|-\big{(}\frac{11K}{s-1}+\frac{\varepsilon}{s}\big{)}\min(|A|,|B|)\geqslant\big{(}1-\frac{20K}{s}\big{)}|A_{j}+B_{j}|.$

If we choose elements $a_{1},\ldots,a_{n_{A}}$ and $b_{1},\ldots,b_{n_{B}}$
uniformly at random from $A_{j}$ and $B_{j}$, and we write
$A^{\prime}_{j}=\\{a_{1},\ldots,a_{n_{A}}\\}$ and
$B^{\prime}_{j}=\\{b_{1},\ldots,b_{n_{B}}\\}$, then we have

$\displaystyle{\mathbb{E}}|A_{j}^{\prime}+B_{j}^{\prime}|$
$\displaystyle\geqslant$
$\displaystyle\sum_{x}(1-\exp(-\frac{n_{B}r_{j}(x)}{16|B_{j}|}))(1-\exp(-\max(\frac{n_{A}}{4|A_{j}|},\frac{n_{A}n_{B}r_{j}(x)}{8|A_{j}||B_{j}|})))$
$\displaystyle\geqslant$
$\displaystyle\sum_{x}(1-\exp(-\frac{cr_{j}(x)}{16|B_{j}|}))^{2}\geqslant\sum_{x\in
C^{+}_{j}}(1-\exp(-\frac{cr_{j}(x)}{16|B_{j}|}))^{2}$ $\displaystyle\geqslant$
$\displaystyle\sum_{x\in C^{+}_{j}}(1-\exp(-2^{-4}\alpha
c))^{2}\geqslant(1-\exp(-2^{-4}\alpha c))^{2}|A_{j}+_{\Gamma_{j}}B_{j}|$
$\displaystyle\geqslant$ $\displaystyle(1-\exp(-2^{-4}\alpha
c))^{2}(1-\frac{20K}{s})|A_{j}+B_{j}|\geqslant(1-\epsilon)|A_{j}+B_{j}|.$

Here the first inequality follows from (1); the second from the hypothesis
$n_{A}n_{B}\geqslant c|A|\geqslant c|A_{j}|$ which, in particular, gives
$n_{B}\geqslant c|B_{j}|$; the fourth inequality holds by the construction, as
$r_{j}(x)\geqslant\alpha|B_{j}|$ for $x\in C_{j}^{+}$; the fifth inequality
follows from the hypothesis $c\geqslant 2^{10}/\alpha|\log(\epsilon)|$; and
the last inequality follows from the assumption on the size of $C^{+}_{j}$.

Thus the pair $(|A_{j}|,|B_{j}|)$ has the desired properties, so Claim B is
proved. ∎

This concludes the proof of Theorem 2: whether the process stops early or does
not, the pair of sets $(A_{j},B_{j})$ has the desired properties. ∎

When we come to proving Theorem 1, we shall need the following consequence of
this.

######  Theorem 6.

For all $\beta,\gamma>0$ there exists $\epsilon>0$ such that for all
$\alpha>0$ there is a value of $c$ for which the following holds. Let $A$ and
$B$ be subsets of $\mathbb{Z}_{p}$ and let $1\leqslant c_{1}\leqslant|A|$ and
$1\leqslant c_{2}\leqslant|B|$ be integers such that $c_{1}c_{2}\geqslant
c\max(|A|,|B|)$. Suppose that

$2\leqslant\min(|A|,|B|),\alpha|B|\leqslant|A|\leqslant\alpha^{-1}|B|\text{
and }|A|+|B|\leqslant(1-\beta)p$ (2)

and

$\operatorname*{\mathbb{E}}_{A^{\prime}\in A^{(c_{1})},\ B^{\prime}\in
B^{(c_{2})}}|A^{\prime}+B^{\prime}|\leqslant|A|+|B|-1+\varepsilon\min(|A|,|B|).$
(3)

Then there exist arithmetic progressions $P$ and $Q$ with the same common
difference and

$\max(|A\Delta P|,|B\Delta Q|)\leqslant\gamma\min(|A|,|B|).$

###### Proof.

We start by fixing some parameters. Fix $2^{-10}>\beta>\gamma>\alpha>0$. Let
$\varepsilon_{1}$ be the output of Theorem 4 with input $\beta,2^{-11}\gamma$.
Let $\varepsilon=\min(2^{-2}\varepsilon_{1},2^{-6}\gamma)$. Let
$\mu=2^{-12}\min(\alpha\varepsilon,\alpha\gamma)$. Finally, let $c$ be the
output of Theorem 2 with input $(4/\alpha,\mu)$.

By Theorem 2, there are subsets $A^{*}\subset A$ and $B^{*}\subset B$ with

$|A^{*}|\geqslant\lceil(1-\mu)|A|\rceil\text{ and
}|B^{*}|\geqslant\lceil(1-\mu)|B|\rceil$ (4)

such that

$\operatorname*{\mathbb{E}}_{A^{\prime}\in A^{(c_{1})},\ B^{\prime}\in
B^{(c_{2})}}|A^{\prime}+B^{\prime}|\geqslant\min\bigg{(}(1-\mu)|A^{*}+B^{*}|\text{,
}\frac{4}{\alpha}|A|\text{, }\frac{4}{\alpha}|B|\bigg{)}.$ (5)

By (2) we have

$\min\bigg{(}\frac{4}{\alpha}|A|,\frac{4}{\alpha}|B|\bigg{)}\geqslant
4\max(|A|,|B|)>|A|+|B|-1+\varepsilon\min(|A|,|B|),$ (6)

and by (2) and (4) we find that

$2\leqslant\min\big{(}|A^{*}|,|B^{*}|\big{)},\ \ \
\frac{\alpha}{2}|B^{*}|\leqslant|A^{*}|\leqslant\frac{2}{\alpha}|B^{*}|\ \ \
{\rm and}\ \ \ |A^{*}|+|B^{*}|\leqslant(1-\beta)p.$ (7)

Hence (3), (5) and (6) imply

$|A|+|B|-1+\varepsilon\min(|A|,|B|)\geqslant(1-\mu)|A^{*}+B^{*}|.$

Combining this with (4) and (7), we find that

$\begin{split}|A^{*}+B^{*}|&\leqslant(1-\mu)^{-1}(|A|+|B|-1+\varepsilon\min(|A|,|B|))\\\
&\leqslant(1-\mu)^{-2}|A^{*}|+(1-\mu)^{-2}|B^{*}|-1+2\varepsilon\min(|A^{*}|,|B^{*}|)\\\
&\leqslant|A^{*}|+|B^{*}|-1+8\mu\max(|A^{*}|,|B^{*}|)+2\varepsilon\min(|A^{*}|,|B^{*}|)\\\
&\leqslant|A^{*}|+|B^{*}|-1+4\varepsilon\min(|A^{*}|,|B^{*}|).\end{split}$ (8)

Recalling Theorem 4 and (7), we see that there exist arithmetic progressions
$P$ and $Q$ with the same common difference such that

$|A^{*}\Delta P|\leqslant\frac{\gamma}{2^{11}}\min(|A^{*}|,|B^{*}|)\text{ and
}|B^{*}\Delta Q|\leqslant\frac{\gamma}{2^{11}}\min(|A^{*}|,|B^{*}|)$

The conclusion now follows from this and (4):

$\displaystyle|A\Delta P|$ $\displaystyle\leqslant$ $\displaystyle|A^{*}\Delta
P|+|A\Delta A^{*}|\leqslant\frac{\gamma}{2^{11}}\min(|A^{*}|,|B^{*}|)+\mu|A|$
$\displaystyle\leqslant$
$\displaystyle\frac{\gamma}{2^{11}}\min(|A|,|B|)+\mu|A|\leqslant\frac{\gamma}{2^{10}}\min(|A|,|B|).$

and

$\displaystyle|B\Delta Q|$ $\displaystyle\leqslant$ $\displaystyle|B^{*}\Delta
Q|+|B\Delta B^{*}|\leqslant\frac{\gamma}{2^{11}}\min(|A^{*}|,|B^{*}|)+\mu|B|$
$\displaystyle\leqslant$
$\displaystyle\frac{\gamma}{2^{11}}\min(|A|,|B|)+\mu|B|\leqslant\frac{\gamma}{2^{10}}\min(|A|,|B|).$

This completes the proof of Theorem 6. ∎

##  4\. Proof of Theorem 1

We start with a sketch of how the proof of Theorem 1 will proceed.

By Theorem 6, we may assume that $A$ and $B$ are close to intervals $I$ and
$J$. Some delicate analysis around the endpoints of $I$ and $J$, where we may
slightly alter these intervals, will allow us to reduce to the case where $A$
and $B$ are actually contained in $I$ and $J$. Thus there is no ‘wraparound’,
and so we may as well be working in ${\mathbb{Z}}$ instead of
${\mathbb{Z}}_{p}$.

Assume for simplicity that $I=J$ has size $n$, that $A$ and $B$ are contained
in $I$ and $J$ and have size at least say $(1-1/1000)n$, and that
$c_{1}=c_{2}=c\sqrt{n}$ for some large constant $c$. Fix $d$ to be about
$\sqrt{n}$, and as usual write $X^{y}$ for $X\cap(y\mod d)$. Assume $A^{0}$ is
the largest of the fibres $A^{y}$. Then clearly $2|A^{0}|>|B^{y}|$ for all
$y$. By Theorem 5, if $B^{\prime y}$ is a bounded set of $r$ random points in
$B^{y}$, chosen according to some distribution independent of $A$, we have
that $|A^{0}+B^{\prime y}|\geqslant|A^{0}|+|B^{y}|-1$.

If we let $B^{\prime}=\cup_{y}B^{\prime y}$, we have
$|A^{0}+B^{\prime}|\geqslant|A^{0}||\pi(B)|+|B|-|\pi(B)|$ and
$A^{0}+B^{\prime}\subset\pi^{-1}\pi(B)$.

Now pick a random fibre $y\mod d$ and let $A^{\prime}=A^{0}\cup A^{y}$. We
want to show that for each fibre $z\mod d$ we have ${\mathbb{E}}|(A^{\prime
y}+B^{\prime})^{z}|\geqslant n/d$.

Indeed, once we have shown this, then combining the two inequalities and
summing over all $z$ not in $\pi(B)$ gives
${\mathbb{E}}|A^{\prime}+B^{\prime}|\geqslant|A^{0}||\pi(B)|+|B|-|\pi(B)|+(d-|\pi(B)|)n/d\geqslant
n/d|\pi(B)|+|B|-|\pi(B)|+(d-|\pi(B)|)n/d\geqslant n+|B|-d$. So fix sets
$A^{\prime}$ and $B^{\prime}$ which satisfy this bound. To finish from here we
just note that by adding $d$ extra points in $A^{\prime}$ and $d$ extra points
in $B^{\prime}$ we can guarantee $|A^{\prime}+B^{\prime}|\geqslant|A|+|B|-1$.
We also note $|A^{\prime}|=|B^{\prime}|=O(\sqrt{n})$.

To show ${\mathbb{E}}|(A^{\prime y}+B^{\prime})^{z}|\geqslant n/d$, we proceed
as follows. Note that the proportion of fibres $y\mod d$ such that $A^{y}$ and
$B^{y}$ have size at least $9n/10d$ is at least $9/10$. Therefore, for a fixed
fibre $z\mod d$, with probability at least $8/10$ both $A^{y}$ and $B^{z-y}$
have size at least $9n/10d$. Conditioned on this event, it follows that
$2|A^{y}|\geqslant|B^{z-y}|$. Using Theorem 5 again, we obtain
$|A^{y}+B^{\prime z-y}|\geqslant|A^{y}|+|B^{z-y}|-1\geqslant 18n/10d-1$. Hence

${\mathbb{E}}|(A^{\prime
y}+B^{\prime})^{z}|\geqslant(8/10)(18n/10d-1)\geqslant n/d.$

We now start to work towards the proof of Theorem 1. We collect together in
advance some results that we shall need. The first of these results will be
applied when we already know that our sets are close to intervals.

######  Theorem 7.

There exists $\gamma>0$ such that for all $\alpha>0$ there exists $c$ for
which the following holds. Let $X$ and $Y$ be subsets of two intervals $I$ and
$J$ of $\mathbb{Z}_{p}$, and let $1\leqslant c_{1}\leqslant|X|$ and
$1\leqslant c_{2}\leqslant|Y|$ be integers such that $c_{1}c_{2}\geqslant
c\max(|X|,|Y|)$. Suppose that $\alpha|J|\leqslant|I|\leqslant\alpha^{-1}|J|$,
$|I|+|J|\leqslant p$ and $\max(|I\setminus X|,|J\setminus
Y|)\leqslant\gamma\min(|I|,|J|)$. Then there exist $X^{\prime}\in X^{(c_{1})}$
and $Y^{\prime}\in Y^{(c_{2})}$ such that
$|X^{\prime}+Y^{\prime}|\geqslant|X|+|Y|-1$.

###### Proof.

Since $|I|+|J|\leqslant p$, we may assume that the ambient space is
$\mathbb{Z}$ rather than $\mathbb{Z}_{p}$. Let $\gamma^{\prime}$ and $k$ be
the outputs of Theorem 5 with input $\alpha/2$ (since we are now in
$\mathbb{Z}$, there is no $\beta$, or more formally we are applying Theorem 5
inside $\mathbb{Z}_{q}$ for some much larger $q$ with say $\beta=1/2$). By
increasing $\gamma^{\prime}$ if necessary we may assume that $k\geqslant
100/\gamma^{\prime}$. Set $\gamma=\gamma^{\prime}/100$ and let
$t=\lceil\log_{2/3}(1-(1+\alpha\gamma^{\prime}/100)^{-1})\rceil$, and put
$c=2^{5}t(k+1)$. We may assume by symmetry that $c_{1}\geqslant c_{2}$. Let
$d=\lfloor c_{2}(k+1)^{-1}\rfloor$. Note that the hypothesis forces
$c_{2}\geqslant c\geqslant 2(k+1)$, which ensures that $d$ is positive.

The definition of $d$ and the inequality $k\geqslant 100/\gamma^{\prime}$
imply

$\min(|I|,|J|)\geqslant\min(|X|,|Y|)\geqslant c_{2}\geqslant(k+1)d\geqslant
100d/\gamma^{\prime}.$ (9)

Given a set $Z$, recall that we write $Z^{x}_{d}$ for $Z\cap(x\text{ mod }d)$,
the points of $Z$ in a fibre. Since $I$ and $J$ are intervals, for every
$x\in\mathbb{Z}_{d}$ we have

$|I|/d+1\geqslant|I^{x}_{d}|\geqslant|I|/d-1\text{ and
}|J|/d+1\geqslant|J^{x}_{d}|\geqslant|J|/d-1.$

Combining the last two inequalities, for every $x\in\mathbb{Z}_{d}$ we have

$|I^{x}_{d}|\geqslant|I|/d-(\gamma^{\prime}/100d)\min(|I|,|J|)\text{ and
}|J^{x}_{d}|\geqslant|J|/d-(\gamma^{\prime}/100d)\min(|I|,|J|)$ (10)

and

$|I^{x}_{d}|\leqslant|I|/d+(\gamma^{\prime}/100d)\min(|I|,|J|)\text{ and
}|J^{x}_{d}|\leqslant|J|/d+(\gamma^{\prime}/100d)\min(|I|,|J|).$ (11)

We may assume (by taking a translate of $X$, if necessary) that
$|X^{0}_{d}|=\max_{x\in\mathbb{Z}_{d}}|X^{x}_{d}|$. Then

$|X^{0}_{d}|\geqslant|X|/d\geqslant|I|/d-(\gamma/d)\min(|I|,|J|)\geqslant|I|/d-(\gamma^{\prime}/3d)\min(|I|,|J|).$

Now define the sets $E_{X},E_{Y}\subset\mathbb{Z}_{d}$ by

$E_{X}=\\{x\in\mathbb{Z}_{d}\text{ :
}|X^{x}_{d}|\geqslant(|I|/d)-(\gamma^{\prime}/3d)\min(|I|,|J|)\\}$

and

$E_{Y}=\\{x\in\mathbb{Z}_{d}\text{ :
}|Y^{x}_{d}|\geqslant(|J|/d)-(\gamma^{\prime}/3d)\min(|I|,|J|)\\}.$

For all $x\in E_{X}$ and $y\in E_{Y}$, noting that $X^{x}_{d}\subset
I^{x}_{d}$ and $Y^{y}_{d}\subset J^{y}_{d}$, we see by (10) and (11) that

$\max(|X^{x}_{d}\Delta I^{x}_{d}|,|Y^{x}_{d}\Delta
J^{y}_{d}|)\leqslant(1/3+1/100)(\gamma^{\prime}/d)\min(|I|,|J|)\leqslant\gamma^{\prime}\min(|I^{x}_{d}|,|J^{y}_{d}|).$

Since
$(\alpha/2)|J^{y}_{d}|\leqslant|I^{x}_{d}|\leqslant(2/\alpha)|J^{y}_{d}|$, by
Theorem 5, there is a family $\mathcal{F}^{y}_{d}$ of subsets of $Y^{y}_{d}$
of size $k$, depending only on $Y^{y}_{d}$ (not on $X^{x}_{d}$), such that

$\operatorname*{\mathbb{E}}_{Z\in\mathcal{F}^{y}_{d}}|X^{x}_{d}+Z|\geqslant|X^{x}_{d}|+|Y^{y}_{d}|-1.$
(12)

Now construct a family $\mathcal{F}=\\{\cup_{y\in E_{Y}}F^{y}_{d}\text{ :
}F^{y}_{d}\in\mathcal{F}^{y}_{d}\\}$, and note that each set $F\in\mathcal{F}$
satisfies $|F|\leqslant|E_{Y}|k\leqslant dk\leqslant c_{2}-d$. Define sets
$E_{x}^{\prime}\subset E_{X}$ and $E_{Y}^{\prime}\subset E_{Y}$ by

$E_{X}^{\prime}=\\{x\in\mathbb{Z}_{d}\text{ :
}|X^{x}_{d}|\geqslant(|I|/d)-(\gamma^{\prime}/10d)\min(|I|,|J|)\\}$

and

$E_{Y}^{\prime}=\\{x\in\mathbb{Z}_{d}\text{ :
}|Y^{x}_{d}|\geqslant(|J|/d)-(\gamma^{\prime}/10d)\min(|I|,|J|)\\}.$

By Markov’s inequality,

$\mathbb{P}(E_{X}^{\prime})\geqslant
1-\frac{\gamma}{(1/10-1/100)\gamma^{\prime}}\geqslant\frac{2}{3}\ \
\text{and}\ \ \mathbb{P}(E_{Y}^{\prime})\geqslant
1-\frac{\gamma}{(1/10-1/100)\gamma^{\prime}}\geqslant\frac{2}{3}.$

Simple calculations using (10) and (11) now show that for all $x^{\prime}\in
E_{X}^{\prime}\subset E_{X},y^{\prime}\in E_{Y}^{\prime}\subset
E_{Y},x\in\mathbb{Z}_{d}$ and $y\in\mathbb{Z}_{d}\setminus E_{y}$ we have

$\displaystyle|X^{x^{\prime}}_{d}|+|Y^{y^{\prime}}_{d}|$
$\displaystyle\geqslant$
$\displaystyle|I|/d+|J|/d-(\gamma^{\prime}/5d)\min(|I|,|J|)$
$\displaystyle\geqslant$
$\displaystyle[|I|/d+(\gamma^{\prime}/100d)\min(|I|,|J|)]+[|J|/d-(\gamma^{\prime}/3d)\min(|I|,|J|)]$
$\displaystyle+$
$\displaystyle(1/3-1/5-1/100)(\gamma^{\prime}/d)\min(|I|,|J|)$
$\displaystyle\geqslant$
$\displaystyle|X^{x}_{d}|+|Y^{y}_{d}|+(\gamma^{\prime}/10d)\min(|I|,|J|)$
$\displaystyle\geqslant$
$\displaystyle|X^{x}_{d}|+|Y^{y}_{d}|+(\alpha\gamma^{\prime}/10d)\max(|I|,|J|)\geqslant(1+\alpha\gamma^{\prime}/100)(|X^{x}_{d}|+|Y^{y}_{d}|).$

Now consider the family
$\mathcal{G}=\\{X^{0}_{d}\cup_{i=1}^{t}X^{x_{i}}_{d}\text{ : }x_{i}\in
E_{X}^{\prime}\\}$. By (11), every set $G\in\mathcal{G}$ satisfies

$\displaystyle|G|$ $\displaystyle\leqslant$
$\displaystyle(t+1)(|I|/d+(\gamma^{\prime}/100d)\min(|I|,|J|))\leqslant
8td^{-1}|X|$ $\displaystyle\leqslant$ $\displaystyle
2^{4}t(k+1)c_{2}^{-1}|X|\leqslant 2^{-1}cc_{2}^{-1}|X|\leqslant
2^{-1}c_{1}\leqslant c_{1}-d.$

The last ingredient needed to complete the proof of Theorem 7 is the following
lemma.

######  Lemma 8.

The families ${\mathcal{F}}$ and ${\mathcal{G}}$ are such that

$\operatorname*{\mathbb{E}}_{X^{\prime}\in\mathcal{G},\
Y^{\prime}\in\mathcal{F}}|X^{\prime}+Y^{\prime}|\geqslant|X|+|Y|-d.$

###### Proof.

By the linearity of expectation, it is enough to show that for all
$z\in\mathbb{Z}_{d}$ we have

$\operatorname*{\mathbb{E}}_{X^{\prime}\in\mathcal{G},\
Y^{\prime}\in\mathcal{F}}|(X^{\prime}+Y^{\prime})^{z}_{d}|\geqslant|X^{z}_{d}|+|Y^{z}_{d}|-1.$

First assume that $z\in E_{Y}$. Then, using (12), we get

$\operatorname*{\mathbb{E}}_{X^{\prime}\in\mathcal{G},\
Y^{\prime}\in\mathcal{F}}|(X^{\prime}+Y^{\prime})^{z}_{d}|\geqslant\operatorname*{\mathbb{E}}_{Z\in\mathcal{F}^{z}_{d}}|(X^{0}_{d}+Z)^{z}_{d}|=\operatorname*{\mathbb{E}}_{Z\in\mathcal{F}^{z}_{d}}|X^{0}_{d}+Z|\geqslant|X^{0}_{d}|+|Y^{z}_{d}|-1\geqslant|X^{z}_{d}|+|Y^{z}_{d}|-1.$

Now assume instead that $z\not\in E_{Y}$. Then, using (12),
${\mathbb{P}}(E_{X}^{\prime})\geqslant 2/3$, and our bound on
$|X^{x^{\prime}}_{d}|+|Y^{y^{\prime}}_{d}|$, we obtain

$\displaystyle\operatorname*{\mathbb{E}}_{X^{\prime}\in\mathcal{G},\
Y^{\prime}\in\mathcal{F}}|(X^{\prime}+Y^{\prime})^{z}_{d}|\geqslant\operatorname*{\mathbb{E}}_{\begin{subarray}{c}x_{1},\ldots,x_{t}\in
E_{X}^{\prime}\\\
Y^{\prime}\in\mathcal{F}\end{subarray}}|((\cup_{i}X^{x_{i}}_{d})+Y^{\prime})^{z}_{d}|$
$\displaystyle\hskip
30.0pt\geqslant\operatorname*{\mathbb{E}}_{\begin{subarray}{c}x_{1},\ldots,x_{t}\in
E_{X}^{\prime}\\\
Y^{\prime}\in\mathcal{F}\end{subarray}}\bigg{(}|((\cup_{i}X^{x_{i}}_{d})+Y^{\prime})^{z}_{d}|\text{
: }\exists i\text{ such that }z-x_{i}\in E_{Y}^{\prime}\bigg{)}$
$\displaystyle\hskip
130.0pt\times\operatorname*{\mathbb{P}}_{x_{1},\ldots,x_{t}\in
E_{X}^{\prime}}\bigg{(}\exists i\text{ such that }z-x_{i}\in
E_{Y}^{\prime}\bigg{)}$ $\displaystyle\hskip
30.0pt\geqslant\operatorname*{\mathbb{E}}_{\begin{subarray}{c}x\in
E_{X}^{\prime}\cap(z-E_{Y}^{\prime})\\\
Y^{\prime}\in\mathcal{F}\end{subarray}}|(X^{x}_{d}+Y^{\prime})^{z}_{d}|(1-(2/3)^{t})\geqslant\operatorname*{\mathbb{E}}_{\begin{subarray}{c}x\in
E_{X}^{\prime}\cap(z-E_{Y}^{\prime})\\\
Z\in\mathcal{F}^{z-x}_{d}\end{subarray}}|X^{x}_{d}+Z|(1-(2/3)^{t})$
$\displaystyle\hskip
30.0pt\geqslant(|X^{x}_{d}|+|Y^{z-d}_{d}|-1)(1-(2/3)^{t})\geqslant\bigg{(}(1+\alpha\gamma^{\prime}/100)(|X^{0}_{d}|+|Y^{z}_{d}|)-1\bigg{)}(1-(2/3)^{t})$
$\displaystyle\hskip
30.0pt\geqslant(1+100^{-1}\alpha\gamma^{\prime})(|X^{0}_{d}|+|Y^{z}_{d}|)(1-(2/3)^{t})-1\geqslant|X^{0}_{d}|+|Y^{z}_{d}|-1\geqslant|X^{z}_{d}|+|Y^{z}_{d}|-1,$

proving Lemma 8. ∎

To complete the proof of Theorem 7, note that if $X^{\prime}\in X^{(c_{1}-d)}$
and $Y^{\prime}\in Y^{(c_{2}-d)}$ satisfy
$|X^{\prime}+Y^{\prime}|\geqslant|X|+|Y|-d$, then there exist sets
$X^{\prime\prime}\in X^{(c_{1})}$ and $Y^{\prime\prime}\in Y^{(c_{2})}$ such
that $|X^{\prime\prime}+Y^{\prime\prime}|\geqslant|X|+|Y|-1.$ ∎

Having proved Theorem 7, we turn to ‘improving the setup by changing the ends
of the intervals’, the step we mentioned in our sketch of the proof at the
start of the section.

######  Lemma 9.

For all $\beta$ and $\gamma$ with $2^{-20}>\beta>2^{20}\gamma>0$ the following
holds. Let $A$ and $B$ be subsets of $\mathbb{Z}_{p}$ and let $I$ and $J$ be
intervals of $\mathbb{Z}_{p}$ such that $|A|+|B|\leqslant(1-\beta)p$ and
$\max(|A\Delta I|,|B\Delta J|)\leqslant\gamma\min(|A|,|B|)$. Then in
$\mathbb{Z}_{p}$ there are two sets of three consecutive intervals,
$I_{1},I_{2},I_{3}$ and $J_{1},J_{2},J_{3}$, with

$\lfloor(\beta/8)p\rfloor\leqslant\min(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant\max(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant(\beta/4)p$

such that, setting $A_{i}=A\cap I_{i}$ and $B_{i}=B\cap J_{i}$, we have
$|A_{1}|=|B_{1}|$, $|A_{3}|=|B_{3}|$, and

$\max(|A\Delta I_{2}|,|B\Delta J_{2}|)\leqslant 2^{10}\gamma\min(|A|,|B|).$
(13)

Moreover, for $i\in\\{1,3\\}$ and for any two arithmetic progressions $P$ and
$Q$ we have

$\max(|A_{i}\Delta P|,|B_{i}\Delta Q|)\geqslant|A_{i}|/2^{10}=|B_{i}|/2^{10}.$

###### Proof.

Let $I_{2}^{\prime}$ and $J_{2}^{\prime}$ be maximal intervals in
$\mathbb{Z}_{p}$ satisfying (13): note that such intervals do exist by
hypothesis. By our bounds on $|A|+|B|$, $|A\Delta I|$ and $|B\Delta J|$, we
have

$|I_{2}^{\prime}|+|J_{2}^{\prime}|\leqslant|A|+|B|+2\gamma\min(|A|,|B|)\leqslant(1-\beta+2\gamma)p\leqslant(1-(\beta/2))p.$

Thus we can construct intervals $I_{1}^{\prime},I_{3}^{\prime}$ and
$J_{1}^{\prime},J_{3}^{\prime}$ such that
$I_{1}^{\prime},I_{2}^{\prime},I_{3}^{\prime}$ and
$J_{1}^{\prime},J_{2}^{\prime},J_{3}^{\prime}$ are two families of three
consecutive intervals of $\mathbb{Z}_{p}$ with

$|I_{1}^{\prime}|=|I_{3}^{\prime}|=|J_{1}^{\prime}|=|J_{3}^{\prime}|=\lfloor(\beta/8)p\rfloor.$
(14)

Note that, by the maximality of $I_{2}^{\prime}$ and $J_{2}^{\prime}$, for any
intervals $I_{1}^{\prime\prime\prime},I_{3}^{\prime\prime\prime}$ and
$J_{1}^{\prime\prime\prime},J_{3}^{\prime\prime\prime}$ such that
$I_{1}^{\prime\prime\prime},I_{2}^{\prime},I_{3}^{\prime\prime\prime}$ and
$J_{1}^{\prime\prime\prime},J_{2}^{\prime},J_{3}^{\prime\prime\prime}$ are
familes of consecutive intervals, if we set $A_{i}^{\prime\prime\prime}=A\cap
I_{i}^{\prime\prime\prime}$ and $B_{i}^{\prime\prime\prime}=B\cap
J_{i}^{\prime\prime\prime}$, then we have

$|I_{i}^{\prime\prime\prime}|>2|A_{i}^{\prime\prime\prime}|\text{ and
}|J_{i}^{\prime\prime\prime}|>2|B_{i}^{\prime\prime\prime}|.$ (15)

Let $A_{i}^{\prime}=A\cap I_{i}^{\prime}$ and $B_{i}^{\prime}=B\cap
J_{i}^{\prime}$, and assume that
$|A_{1}^{\prime}|\geqslant|B_{1}^{\prime}|\text{ and
}|A_{3}^{\prime}|\geqslant|B_{3}^{\prime}|$. (The three other cases are
analogous.) Note that by (13) we have

$\max(|A_{1}^{\prime}|,|A_{3}^{\prime}|,|I_{2}^{\prime}\setminus
A_{2}^{\prime}|)\leqslant\gamma\min(|A|,|B|)\leqslant
2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|).$ (16)

Now consider subintervals $I_{1}^{\prime\prime}$ and $I_{3}^{\prime\prime}$ at
the ends of interval $I_{2}^{\prime}$ that are minimal subject to the
following two properties: setting $A_{i}^{\prime\prime}=A\cap
I_{i}^{\prime\prime}$, we have

$|A_{1}^{\prime\prime}|\geqslant 14|A_{1}^{\prime}|\text{ and
}|A_{3}^{\prime\prime}|\geqslant 14|A_{3}^{\prime}|$ (17)

and there exist intervals $P_{1}^{\prime\prime}$ and $P_{3}^{\prime\prime}$
(contained inside $I_{1}^{\prime\prime}$ and $I_{3}^{\prime\prime}$
respectively) such that

$|P_{1}^{\prime\prime}\Delta
A_{1}^{\prime\prime}|\leqslant|A_{1}^{\prime\prime}|/14\text{ and
}|P_{3}^{\prime\prime}\Delta
A_{3}^{\prime\prime}|\leqslant|A_{3}^{\prime\prime}|/14.$ (18)

(Here we insist that if $A_{1}^{\prime}=\emptyset$ or
$A_{3}^{\prime}=\emptyset$ then
$I_{1}^{\prime\prime}=P_{1}^{\prime\prime}=A_{1}^{\prime\prime}=\emptyset$ or
$I_{3}^{\prime\prime}=P_{3}^{\prime\prime}=A_{3}^{\prime\prime}=\emptyset$,
respectively.) Note that such intervals $I_{1}^{\prime\prime}$ and
$I_{3}^{\prime\prime}$ do exist, as the intervals
$I_{1}^{\prime\prime}=P_{1}^{\prime\prime}=I_{3}^{\prime\prime}=P_{3}^{\prime\prime}=I_{2}^{\prime}$
have the desired properties by (16).

We now show that

$|I_{1}^{\prime\prime}|+|I_{3}^{\prime\prime}|\leqslant
2^{6}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)<|I_{2}^{\prime}|.$ (19)

The right-hand inequality is immediate, since $A_{2}^{\prime}\subset
I_{2}^{\prime}$ and $\gamma<2^{-6}$. For the left-hand inequality, suppose for
a contradiction that say
$|I_{1}^{\prime\prime}|>2^{5}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$.
Consider first the case when
$2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)<1$. By (16) we have
$A_{1}^{\prime}=A_{3}^{\prime}=\emptyset$, and hence we obtain
$I_{1}^{\prime\prime}=I_{3}^{\prime\prime}=\emptyset$, which is a
contradiction.

Consider now the case when
$2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)\geqslant 1$. In this case we
consider the proper subinterval $I_{1}^{\prime\prime\prime}$ at the end of
$I_{1}^{\prime\prime}$ with $|I_{1}^{\prime\prime\prime}|=\lfloor
2^{5}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)\rfloor\geqslant
30\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$. Let
$A_{1}^{\prime\prime\prime}=I_{1}^{\prime\prime\prime}\cap A$. By (16), we
have $|I_{1}^{\prime\prime\prime}\setminus
A_{1}^{\prime\prime\prime}|\leqslant|I_{2}^{\prime}\setminus
A_{2}^{\prime}|\leqslant 2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$. In
particular, we have $|A_{1}^{\prime\prime\prime}|\geqslant
28\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$, which implies
$|I_{1}^{\prime\prime\prime}\setminus
A_{1}^{\prime\prime\prime}|\leqslant|A_{1}^{\prime\prime\prime}|/14$. But by
(16), we also have $|A_{1}^{\prime}|\leqslant
2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$, which implies
$|A_{1}^{\prime\prime\prime}|\geqslant 14|A_{1}^{\prime}|$.

Therefore $I_{1}^{\prime\prime\prime}$ is an interval strictly smaller than
$I_{1}^{\prime\prime}$ with the desired properties, giving a contradiction.
This proves inequality (19).

By (19), the intervals $I_{1}^{\prime\prime}$ and $I_{3}^{\prime\prime}$
induce a partition $I_{2}^{\prime}=I_{1}^{\prime\prime}\sqcup I_{2}\sqcup
I_{3}^{\prime\prime}$ into consecutive intervals. Moreover, by (19) and (13)
we get

$|A\Delta I_{2}|\leqslant|A\Delta
I_{2}^{\prime}|+|I_{1}^{\prime\prime}|+|I_{3}^{\prime\prime}|\leqslant
2^{7}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|).$ (20)

Note also that by (13) we have

$|J_{2}^{\prime}\setminus B_{2}^{\prime}|\leqslant\gamma\min(|A|,|B|)\leqslant
2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|).$ (21)

Now consider subintervals $J_{1}^{\prime\prime}$ and $J_{3}^{\prime\prime}$ at
the ends of $J_{2}^{\prime}$ such that with $B_{i}^{\prime\prime}=B\cap
J_{i}^{\prime\prime}$ we have

$|B_{1}^{\prime}|+|B_{1}^{\prime\prime}|=|A_{1}^{\prime}|+|A_{1}^{\prime\prime}|\text{
and
}|B_{3}^{\prime}|+|B_{3}^{\prime\prime}|=|A_{3}^{\prime}|+|A_{3}^{\prime\prime}|$
(22)

Note that there are such intervals, since for $i\in\\{1,3\\}$ both
$|B_{i}^{\prime}|\leqslant|A_{i}^{\prime}|\leqslant|A_{i}^{\prime}|+|A_{i}^{\prime\prime}|$
and
$|B_{i}^{\prime}|+|B_{2}^{\prime}|\geqslant|B_{2}^{\prime}|\geqslant|A_{i}^{\prime}|+|I_{i}^{\prime\prime}|\geqslant|A_{i}^{\prime}|+|A_{i}^{\prime\prime}|$
hold. We now show that

$|J_{1}^{\prime\prime}|+|J_{3}^{\prime\prime}|\leqslant
2^{8}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)<|J_{2}^{\prime}|.$ (23)

Assume for a contradiction that $|J_{1}^{\prime\prime}|\geqslant
2^{7}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$. On the one hand, by (21)
we deduce
$|B_{1}^{\prime\prime}|\geqslant|J_{1}^{\prime\prime}|-|J_{2}^{\prime}\setminus
B_{2}^{\prime}|\geqslant 126\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$. On
the other hand, by (16) we have $|A_{1}^{\prime}|\leqslant
2\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$ and by (19) we have
$|A_{1}^{\prime\prime}|\leqslant|I_{1}^{\prime\prime}|\leqslant
2^{6}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$. Thus we obtain
$|B_{1}^{\prime\prime}|>|A_{1}^{\prime}|+|A_{1}^{\prime\prime}|$, which gives
the desired contradiction. This proves inequality (23).

By (23), the intervals $J_{1}^{\prime\prime}$ and $J_{3}^{\prime\prime}$
induce a partition $J_{2}^{\prime}=J_{1}^{\prime\prime}\sqcup J_{2}\sqcup
J_{3}^{\prime\prime}$ into consecutive intervals. Moreover, by (23) and (13)
we have

$|B\Delta J_{2}|\leqslant|B\Delta
J_{2}^{\prime}|+|J_{1}^{\prime\prime}|+|J_{3}^{\prime\prime}|\leqslant
2^{9}\gamma\min(|A_{2}^{\prime}|,|B_{2}^{\prime}|).$ (24)

For $i\in\\{1,3\\}$, set $I_{i}=I_{i}^{\prime}\sqcup I_{i}^{\prime\prime}$,
$J_{i}=I_{i}^{\prime}\sqcup I_{i}^{\prime\prime}$, and note that
$I_{1},I_{2},I_{3}$ and $J_{1},J_{2},J_{3}$ are consecutive intervals.
Moreover, by (14) we have

$\min(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\geqslant\lfloor(\beta/8)p\rfloor.$ (25)

In addition, by (14), (19) and (21), we also have

$\max(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant(\beta/4)p.$ (26)

For $i\in\\{1,2,3\\}$ let $A_{i}=A\cap I_{i}$ and $B_{i}=B\cap J_{i}$. By (22)
we have

$|A_{1}|=|B_{1}|\text{ and }|A_{3}|=|B_{3}|.$ (27)

It remains to show that for any arithmetic progressions $P_{1}$ and $P_{3}$ we
have

$|A_{1}\Delta P_{1}|\geqslant 2^{-10}|A_{1}|\text{ and }|A_{3}\Delta
P_{3}|\geqslant 2^{-10}|A_{3}|.$ (28)

Assume for a contradiction that

$|A_{1}\Delta P_{1}|<2^{-10}|A_{1}|,$ (29)

which in particular means that

$A_{1}\neq\emptyset\text{ i.e. }A_{1}^{\prime}\neq\emptyset.$ (30)

Note that (17), (18) and (29) imply

$\displaystyle|P_{1}^{\prime\prime}\Delta P_{1}|$
$\displaystyle\leqslant|A_{1}\Delta P_{1}|+|P_{1}^{\prime\prime}\Delta
A_{1}|\leqslant|A_{1}\Delta P|+|A_{1}^{\prime}|+|P_{1}^{\prime\prime}\Delta
A_{1}^{\prime\prime}|$
$\displaystyle\leqslant|A_{1}|/2^{10}+|A_{1}^{\prime\prime}|/14+|A_{1}^{\prime\prime}|/14\leqslant(1/2^{9}+1/7)|A_{1}^{\prime\prime}|\leqslant|P_{1}^{\prime\prime}|/4.$

Recall that, when $A_{1}^{\prime}\neq\emptyset$, $P_{1}^{\prime\prime}$ is a
subinterval of $I_{1}^{\prime\prime}$ with
$p/8\geqslant|P_{1}^{\prime\prime}|\geqslant 8$ by (17), (18) and (19). It
follows that $P_{1}$ is an interval intersecting the interval
$I_{1}^{\prime\prime}$ of size $p/4\geqslant|P_{1}|\geqslant 4$. By (26) we
also deduce $|P_{1}|+|I_{1}|\leqslant p/2$, which implies that $P_{1}\cap
I_{1}$ is an interval. By replacing $P_{1}$ with $P_{1}\cap I_{1}$, we may
assume that $P_{1}$ is a subinterval of $I_{1}$.

We distinguish two cases: recalling that $I_{1}^{\prime\prime}$ and
$I_{3}^{\prime\prime}$ were chosen to be minimal subject to (17) and (18), we
ask whether the lower bound on the size of $A_{1}^{\prime\prime}$ in (17) is
attained or not.

Case A. $|A_{1}^{\prime\prime}|=14|A_{1}^{\prime}|$.

In this case, by (15), we have

$|(P_{1}\cap I_{1}^{\prime})\Delta A_{1}^{\prime}|\geqslant|A_{1}^{\prime}|.$

So we obtain

$|A_{1}\Delta P_{1}|\geqslant|(P_{1}\cap I_{1}^{\prime})\Delta
A_{1}^{\prime}|\geqslant|A_{1}^{\prime}|=|A_{1}|/15.$ (31)

Case B. $|A_{1}^{\prime\prime}|>14|A_{1}^{\prime}|\geqslant 14$.

In this case, by the minimality of $I_{1}^{\prime\prime}$, if we let $x$ be
the last point inside $A_{1}^{\prime\prime}$, then by (18) we deduce

$|(P_{1}\cap
I_{1}^{\prime\prime})\Delta(A_{1}^{\prime\prime}\setminus\\{x\\})|>|A_{1}^{\prime\prime}\setminus\\{x\\}|/14.$

This is equivalent to

$|(P_{1}\cap
I_{1}^{\prime\prime})\Delta(A_{1}^{\prime\prime}\setminus\\{x\\})|\geqslant\min(2,|A_{1}^{\prime\prime}\setminus\\{x\\}|/14),$

and hence

$|(P_{1}\cap I_{1}^{\prime\prime})\Delta
A_{1}^{\prime\prime}|\geqslant\min(1,(|A_{1}^{\prime\prime}|-1)/14-1)\geqslant|A_{1}^{\prime\prime}|/28.$

Thus we obtain

$|A_{1}\Delta P_{1}|\geqslant|(P_{1}\cap I_{1}^{\prime\prime})\Delta
A_{1}^{\prime\prime}|\geqslant|A_{1}^{\prime\prime}|/28\geqslant|A_{1}|/56.$
(32)

Inequalities (31) and (32) imply that, in either case, $|A_{1}\Delta
P_{1}|\geqslant|A_{1}|/56$ , contradicting (29) and so proving (28). The proof
of Lemma 9 is now complete, thanks to (25), (26) (27), (20), (24) and (28). ∎

Our next lemma is a simple fact about the ‘stickout’ of sumsets from a set of
fixed size: roughly speaking, it says that if $Y$ is much larger than $X$ then
the sum of $X$ with a random few points of $Y$ is expected to be much larger
than $2|X|$.

######  Lemma 10.

Let $X$, $Y$ and $Z$ be subsets of $\mathbb{Z}_{p}$ and let $1\leqslant
c_{1}\leqslant|X|$ and $1\leqslant c_{2}\leqslant|Y|$ be integers such that
$c_{1}c_{2}\geqslant 16|X|$. Suppose that $8|X|,8|Z|\leqslant|Y|<p/2$. Then
there exist $X^{\prime}\in X^{(c_{1})}$ and $Y^{\prime}\in Y^{(c_{2})}$ such
that $|(X^{\prime}+Y^{\prime})\setminus Z|\geqslant 2|X|$.

###### Proof.

Suppose the assertion is false, i.e. $\max_{X^{\prime}\in
X^{(c_{1})},Y^{\prime}\in Y^{(c_{2})}}|(X^{\prime}+Y^{\prime})\setminus
Z|<2|X|$ which, in particular, implies that $\max_{X^{\prime}\in
X^{(c_{1})},Y^{\prime}\in Y^{(c_{2}/2)}}|(X^{\prime}+Y^{\prime})\setminus
Z|<2|X|$. Let $X^{\prime}=\\{x_{1},\ldots,x_{c_{1}}\\}$ and
$Y^{\prime}=\\{y_{1},\ldots,y_{c_{2}/2}\\}$ be elements of $X^{(c_{1})}$ and
$Y^{(c_{2}/2)}$ chosen uniformly at random. Then
${\mathbb{E}}|(X^{\prime}+Y^{\prime})\setminus Z|$ is bounded from below as
follows:

$\displaystyle\ \ \
\sum_{i,j}{\mathbb{E}}|\\{x_{i}+y_{j}\\}\,\setminus\,[Z\cup(\\{x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{c_{1}}\\}+\\{y_{1},\ldots,y_{j-1},y_{j+1},\ldots,y_{c_{2}}\\})]|$
$\displaystyle=\sum_{i,j}\operatorname*{\mathbb{P}}|x_{i}+y_{j}\not\in
Z\cup(\\{x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{c_{1}}\\}+\\{y_{1},\ldots,y_{j-1},y_{j+1},\ldots,y_{c_{2}}\\})|$
$\displaystyle\geqslant\sum_{i,j}1-\max_{X^{\prime}\in
X^{(c_{1})},Y^{\prime}\in
Y^{(c_{2}/2)}}\frac{|Z\cup(X^{\prime}+Y^{\prime})|}{|Y|-(c_{2}/2)}$
$\displaystyle\geqslant\sum_{i,j}1-\frac{|Z|+2|X|}{|Y|/2}\geqslant\frac{c_{1}c_{2}}{2}(1-\frac{3}{4})\geqslant
2|X|,$

so ${\mathbb{E}}|(X^{\prime}+Y^{\prime})\setminus Z|\geqslant 2|X|$,
completing the proof. ∎

As an immediate corollary we have the following, obtained by applying the
previous lemma inductively on $k$ (increasing $Z$ at each stage).

######  Corollary 11.

Let $X_{1},\ldots,X_{k}$, $Y_{1},\ldots,Y_{k}$ and $Z$ be subsets of
$\mathbb{Z}_{p}$ and let $1\leqslant c_{1}^{i}\leqslant|X_{i}|$ and
$1\leqslant c_{2}^{i}\leqslant|Y_{i}|$ be integers such that for all $i$ we
have $c_{1}^{i}c_{2}^{i}\geqslant 16|X_{i}|$. Suppose that for all $i$ we have
$16|X_{i}|,16|Z|\leqslant|Y_{i}|<p/2$. Then there exist
$X^{\prime}_{i}\in(X_{i})^{(c_{1}^{i})}$ and
$Y^{\prime}_{i}\in(Y_{i})^{(c_{2}^{i})}$ (for each $i$) such that

$\ \ \ \ \ \ |\cup_{i}(X^{\prime}_{i}+Y^{\prime}_{i})\setminus
Z|\geqslant\min(16^{-1}|Y_{1}|,\ldots,16^{-1}|Y_{k}|,2\sum_{i}|X_{i}|).\ \ \ \
\ \ \square$

The final ingredient we need is a somewhat cumbersome result about partitions
into intervals.

######  Lemma 12.

For all $1/2^{10}>\alpha,\beta>0$ the following holds. Consider partitions
$\mathbb{Z}_{p}=I_{0}\sqcup I_{1}\sqcup I_{2}\sqcup I_{3}=J_{0}\sqcup
J_{1}\sqcup J_{2}\sqcup J_{3}$ into consecutive intervals such that
$|I_{2}|+|J_{2}|\leqslant(1-\beta/2)p$,
$(\alpha/2)|J_{2}|\leqslant|I_{2}|\leqslant(2/\alpha)|J_{2}|$,
$\min(|I_{2}|,|J_{2}|)\geqslant 24/\beta$ and

$\lfloor(\beta/8)p\rfloor\leqslant\min(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant\max(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant(\beta/4)p.$

Then there are four families of subsets of $\mathbb{Z}_{p}$, each of size
$k\leqslant 100/\alpha\beta$,

$\mathcal{I}_{0}=\\{I^{1}_{0},\ldots,I^{k}_{0}\\},\ \
\mathcal{I}_{2}=\\{I^{1}_{2},\ldots,I^{k}_{2}\\},\ \
\mathcal{J}_{0}=\\{J_{0}^{1},\ldots,J_{0}^{k}\\},\ \
\mathcal{J}_{2}=\\{J_{2}^{1},\ldots,J_{2}^{k}\\}$

such that $\cup_{i}I_{0}^{i}=I_{0},\cup_{i}J_{0}^{i}=J_{0}\ \text{ and }\
\cup_{i}I_{2}^{i}\subset I_{2},\cup_{i}J_{2}^{i}\subset J_{2}$. Furthermore,
for every $1\leqslant i\leqslant k$ we have
$|I_{2}^{i}|=|J_{2}^{i}|=\lfloor(\beta/24)\min(|I_{2}|,|J_{2}|)\rfloor$ and
$(I_{0}^{i}+J_{2}^{i})\cap(I_{2}+J_{2})=(J_{0}^{i}+I_{2}^{i})\cap(I_{2}+J_{2})=\emptyset$.

###### Proof.

We construct the families of intervals $\mathcal{I}_{0}$ and
$\mathcal{J}_{2}$. The construction of the $\mathcal{J}_{0}$ and
$\mathcal{I}_{2}$ is identical. By the conditions above, for every $x\in
I_{0}$ there is a subinterval $J_{2}^{\prime}$ of $J_{2}$ of size
$\lfloor(\beta/8)\min(|I_{2}|,|J_{2}|)\rfloor$ such that
$(x+J_{2}^{\prime})\cap(I_{2}+J_{2})=\emptyset.$

Let $\mathcal{J}_{2}$ be a maximal collection of disjoint intervals of size
$\lfloor(\beta/24)\min(|I_{2}|,|J_{2}|)\rfloor$ contained inside interval
$J_{2}$. First note that

$|\mathcal{J}_{2}|\leqslant|J_{2}|/\lfloor(\beta/24)\min(|I_{2}|,|J_{2}|)\rfloor\leqslant(48/\beta)(2/\alpha)=100/(\alpha\beta).$

Secondly, note that for any subinterval $J_{2}^{\prime}$ of $J_{2}$ of size
$\lfloor(\beta/8)\min(|I_{2}|,|J_{2}|)\rfloor$ there exists
$J_{2}^{\prime\prime}\in\mathcal{J}_{2}$ such that
$J_{2}^{\prime\prime}\subset J_{2}^{\prime}$. Therefore, for any point $x\in
I_{0}$ there exists $J_{2}^{x}\in\mathcal{J}_{2}$ such that

$(x+J_{2}^{x})\cap(I_{2}+J_{2})=\emptyset.$

Let $\mathcal{J}_{2}=\\{J_{2}^{1},\ldots,J_{2}^{k}\\}$. For each $1\leqslant
i\leqslant k$ set $I_{0}^{i}=\\{x\in I_{0}\text{ : }J_{2}^{x}=J_{2}^{i}\\}$,
and finally put $\mathcal{I}_{0}=\\{I_{0}^{1},\ldots,I_{0}^{k}\\}$. These
families $\mathcal{I}_{0}$ and $\mathcal{J}_{2}$ have the desired properties.
∎

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

Fix $\alpha,\beta>0$ and assume $\alpha,\beta<2^{-30}$. Let $\gamma^{\prime}$
and $c^{\prime}$ be the output of Theorem 7 with input $\alpha/2$. Let
$\gamma=2^{-30}\min(\gamma^{\prime},\beta)$. Let $\epsilon>0$ and
$c^{\prime\prime}>0$ be the output of Theorem 6 with input
$\alpha,\beta,\gamma$. Choose
$c=10^{20}\alpha^{-2}\beta^{-2}\max(c^{\prime},c^{\prime\prime})$.

Let $A$ and $B$ be subsets of $\mathbb{Z}_{p}$ and let $1\leqslant
c_{1}\leqslant|A|$ and $1\leqslant c_{2}\leqslant|B|$ such that
$c_{1}c_{2}\geqslant c\max(|A|,|B|)$. This forces $\min(c_{1},c_{2})\geqslant
c$, which, in particular, implies $\min(|A|,|B|)\geqslant c$. Let
$c_{1}^{\prime}=c_{1}\alpha\beta/10^{5}$ and
$c_{2}^{\prime}=c_{2}\alpha\beta/10^{5}$ and note that
$c_{1}^{\prime}c_{2}^{\prime}\geqslant
10^{10}\max(c^{\prime},c^{\prime\prime})\max(|A|,|B|)$ and
$\min(c_{1}^{\prime},c_{2}^{\prime})\geqslant
10^{10}\max(c^{\prime},c^{\prime\prime})$. Observe that we are done unless

$\max_{A^{\prime}\in A^{(c_{1}^{\prime})},B^{\prime}\in
B^{(c_{2}^{\prime})}}|A^{\prime}+B^{\prime}|<|A|+|B|-1,$

so we may assume that this holds. But then we may apply Theorem 6 to deduce
that there are arithmetic progressions $I$ and $J$ with the same common
difference such that

$\max(|A\Delta I|,|B\Delta J|)\leqslant\gamma\min(|I|,|J|).$ (33)

Furthermore, we may and shall assume that $I$ and $J$ are intervals. But then
Lemma 9 can be used to deduce that $\mathbb{Z}_{p}$ has disjoint partitions
into consecutive intervals, $\mathbb{Z}_{p}=I_{0}\sqcup I_{1}\sqcup
I_{2}\sqcup I_{3}=J_{0}\sqcup J_{1}\sqcup J_{2}\sqcup J_{3}$, that have the
following properties. (Here and elsewhere, the notation $\sqcup$ indicates
that we are taking the union of disjoint sets.) On the one hand we have

$\lfloor(\beta/8)p\rfloor\leqslant\min(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant\max(|I_{1}|,|I_{3}|,|J_{1}|,|J_{3}|)\leqslant(\beta/4)p$
(34)

On the other hand, writing $A_{i}=A\cap I_{i}$ and $B_{i}=B\cap J_{i}$, we
have $|A_{1}|=|B_{1}|$, $|A_{3}|=|B_{3}|$, and

$\max(|A\Delta I_{2}|,|B\Delta J_{2}|)\leqslant 2^{10}\gamma\min(|A|,|B|).$
(35)

Moreover, if $i\in\\{1,3\\}$ and $P$ and $Q$ are arithmetic progressions, then

$\max(|A_{i}\Delta P|,|B_{i}\Delta Q|)\geqslant
2^{-10}|A_{i}|=2^{-10}|B_{i}|.$ (36)

In particular, if $i\in\\{1,3\\}$ we have $|A_{i}|=|B_{i}|=0$ or
$|A_{i}|=|B_{i}|\geqslant 2$. Because
$\min(c_{1}^{\prime},c_{2}^{\prime})\geqslant c^{\prime\prime}$ and
$c_{1}^{\prime}c_{2}^{\prime}\geqslant c^{\prime\prime}|A_{i}||B_{i}|$, we
either have $\min(c_{1}^{\prime},c_{2}^{\prime})\geqslant|A_{i}|=|B_{i}|$ or
$\min(c_{1}^{\prime},|A_{i}|)\min(c_{2}^{\prime},|B_{i}|)\geqslant
c^{\prime\prime}|A_{i}|=c^{\prime\prime}|B_{i}|$. By the contrapositive of
Theorem 6, we deduce that

$\operatorname*{\mathbb{E}}_{A^{\prime}\in A_{i}^{(c_{1}^{\prime})},\
B^{\prime}\in
B_{i}^{(c_{2}^{\prime})}}|A^{\prime}+B^{\prime}|>|A_{i}|+|B_{i}|-1.$

We further deduce that there are sets $A_{1}^{\prime}\in
A_{1}^{(c_{1}^{\prime})},\ B_{1}^{\prime}\in B_{1}^{(c_{2}^{\prime})},\
A_{3}^{\prime}\in A_{3}^{(c_{3}^{\prime})}$ and $B_{3}^{\prime}\in
B_{3}^{(c_{2}^{\prime})}$ such that

$|A_{1}^{\prime}+B_{1}^{\prime}|\geqslant|A_{1}|+|B_{1}|\ \ \text{and}\ \
|A_{3}^{\prime}+B_{3}^{\prime}|\geqslant|A_{3}|+|B_{3}|.$ (37)

Choose a subset $Z$ of $\cup_{i\in\\{1,3\\}}(A_{i}^{\prime}+B_{i}^{\prime})$
with $|A_{1}|+|B_{1}|+|A_{3}|+|B_{3}|$ elements, which, by (35), satisfies

$|Z|=|A_{1}|+|B_{1}|+|A_{3}|+|B_{3}|\leqslant|A\Delta I_{2}|+|B\Delta
J_{2}|\leqslant 2^{11}\gamma\min(|A|,|B|).$ (38)

Now, by (35) we also have

$(1-2^{10}\gamma)|A|\leqslant|I_{2}|\leqslant(1+2^{10}\gamma)|A|\ \ \
\text{and}\ \ \
(1-2^{10}\gamma)|B|\leqslant|J_{2}|\leqslant(1+2^{10}\gamma)|B|,$

and so

$|I_{2}|+|J_{2}|\leqslant(1-\beta)(1+2^{10}\gamma)p\leqslant(1-\beta/2)p$ (39)

and

$(\alpha/2)|I_{2}|\leqslant|J_{2}|\leqslant(2/\alpha)|I_{2}|.$ (40)

Furthermore, we deduce that

$\min(|I_{2}|,|J_{2}|)\geqslant 2^{-1}\min(|A|,|B|)\geqslant 2^{-1}c\geqslant
24/\beta.$ (41)

First, by construction, we have $A_{2}\subset I_{2}\text{ and }B_{2}\subset
J_{2}$. Hence, recalling the relations (35), (39) and (40), and the fact that
$\min(c_{1}^{\prime},|A_{2}|)\min(c_{2}^{\prime},|B_{2}|)\geqslant
4^{-1}c_{1}^{\prime}c_{2}^{\prime}\geqslant
c^{\prime}\max(|A_{2}^{\prime}|,|B_{2}^{\prime}|)$, we may apply Theorem 7
with parameters $\alpha/2$, $\gamma^{\prime}\geqslant 2^{30}\gamma$ and
$c^{\prime}$ to obtain the following: there exist $A_{2}^{\prime}\in
A_{2}^{(c_{1}^{\prime})}$ and $B_{2}^{\prime}\in B_{2}^{(c_{2}^{\prime})}$
such that

$|A_{2}^{\prime}+B_{2}^{\prime}|\geqslant|A_{2}|+|B_{2}|-1.$ (42)

Second, by (34), (39), (40) and (41), we may apply Lemma 12 to find four
families of subsets of $\mathbb{Z}_{p}$, each with $k\leqslant
100/\alpha\beta$ sets,

$\mathcal{I}_{0}=\\{I^{1}_{0},\ldots,I^{k}_{0}\\},\mathcal{I}_{2}=\\{I^{1}_{2},\ldots,I^{k}_{2}\\},\mathcal{J}_{0}=\\{J_{0}^{1},\ldots,J_{0}^{k}\\},\mathcal{J}_{2}=\\{J_{2}^{1},\ldots,J_{2}^{k}\\},$

such that

$\cup_{i}I_{0}^{i}=I_{0},\ \ \cup_{i}J_{0}^{i}=J_{0}\ \ \ \text{ and }\ \ \
\cup_{i}I_{2}^{i}\subset I_{2},\ \ \ \cup_{i}J_{2}^{i}\subset J_{2}$ (43)

and for every $1\leqslant i\leqslant k$ and we have

$|I_{2}^{i}|=|J_{2}^{i}|=\lfloor(\beta/24)\min(|I_{2}|,|J_{2}|)\rfloor$ (44)

and

$(I_{0}^{i}+J_{2}^{i})\cap(I_{2}+J_{2})=(J_{0}^{i}+I_{2}^{i})\cap(I_{2}+J_{2})=\emptyset.$
(45)

Writing $A_{j}^{i}=A\cap I_{j}^{i}$ and $B_{j}^{i}=B\cap J_{j}^{i}$, by (35),
we have

$\max\\{|A_{0}^{i}|,|B_{0}^{i}|\\}\leqslant 2^{10}\gamma\min(|A|,|B|).$

and by (35), (41) and (44), we have

$\big{(}\beta/100\big{)}\
\min(|A|,|B|)\leqslant\min\\{|A_{2}^{i}|,|B_{2}^{i}|\\}\leqslant\max\\{|A_{2}^{i}|,|B_{2}^{i}|\\}\leqslant
p/2.$ (46)

The last two inequalities and inequality (38) imply that

$10^{10}\max\\{|A_{0}^{i}|,\ |B_{0}^{i}|,\
|Z|\\}\leqslant\min\\{|A_{2}^{i}|,|B_{2}^{i}|\\}\leqslant\max\\{|A_{2}^{i}|,|B_{2}^{i}|\\}\leqslant
p/2.$ (47)

As we have $\min(c_{1}^{\prime},c_{2}^{\prime})\geqslant 10^{10}$ and
$c_{1}^{\prime}c_{2}^{\prime}\geqslant 10^{10}\max(|A|,|B|)\geqslant
10^{10}\max(|A_{0}^{i}|,|B_{0}^{i}|)$, we further deduce that

$\min(c_{1}^{\prime},|A_{0}^{i}|)\min(c_{2}^{\prime},|B_{2}^{i}|)\geqslant
16|A_{0}^{i}|\ \ \text{and}\ \
\min(c_{1}^{\prime},|B_{0}^{i}|)\min(c_{2}^{\prime},|A_{2}^{i}|)\geqslant
16|B_{0}^{i}|.$ (48)

By Corollary 11 together with (47) and (48) we deduce that for $i\in[k]$ there
exist $A^{\prime i}_{0}\in(A_{0}^{i})^{(c_{1}^{\prime})},B^{\prime
i}_{2}\in(B_{2}^{i})^{(c_{2}^{\prime})},A^{\prime
i}_{2}\in(A_{2}^{i})^{(c_{1}^{\prime})},B^{\prime
i}_{0}\in(B_{0}^{i})^{(c_{2}^{\prime})}$ such that

$|\cup_{i}(A^{\prime i}_{0}+B^{\prime i}_{2})\cup_{i}(A^{\prime
i}_{2}+B^{\prime i}_{0})\setminus Z|\geqslant
16^{-1}\min(|A_{2}^{1}|,\ldots,|A_{2}^{k}|,|B_{2}^{1}|,\ldots,|B_{2}^{k}|,32\sum_{i}|A^{i}_{0}|+|B^{i}_{0}|)$

By (35) and (46), we further deduce

$|\cup_{i}(A^{\prime i}_{0}+B^{\prime i}_{2})\cup_{i}(A^{\prime
i}_{2}+B^{\prime i}_{0})\setminus Z|\geqslant|A_{0}|+|B_{0}|$ (49)

Finally, note that from (34) and (39) it follows that

$I_{1}+J_{1},I_{2}+J_{2}\text{ and }I_{3}+J_{3}$

are disjoint sets, which in particular implies that

$A_{1}^{\prime}+B_{1}^{\prime},A_{2}^{\prime}+B_{2}^{\prime}\text{ and
}A_{3}^{\prime}+B_{3}^{\prime}$

are disjoint sets. Moreover, by (45), it follows that

$\cup_{i}(A^{\prime i}_{0}+B^{\prime i}_{2})\cup_{i}(A^{\prime
i}_{2}+B^{\prime i}_{0})\text{ and }A_{2}^{\prime}+B_{2}^{\prime}$

are disjoint sets. Let

$A^{\prime}=A_{1}^{\prime}\cup A_{2}^{\prime}\cup
A_{3}^{\prime}\cup_{i}A^{\prime i}_{0}\cup_{i}A^{\prime i}_{2}\text{ and
}B^{\prime}=B_{1}^{\prime}\cup B_{2}^{\prime}\cup
B_{3}^{\prime}\cup_{i}B^{\prime i}_{0}\cup_{i}B^{\prime i}_{2}.$

From (37), (38), (42) and (49) we conclude that

$|A^{\prime}+B^{\prime}|\geqslant(|A_{0}|+|B_{0}|)+(|A_{1}|+|B_{1}|)+(|A_{2}|+|B_{2}|-1)+(|A_{3}|+|B_{3}|)=|A|+|B|-1$

and that

$|A^{\prime}|\leqslant(3+2\times
100\alpha^{-1}\beta^{-1})c_{1}^{\prime}\leqslant c_{1}\text{ and
}|B^{\prime}|\leqslant(3+2\times
100\alpha^{-1}\beta^{-1})c_{2}^{\prime}\leqslant c_{2}.$

This concludes the proof of Theorem 1. ∎

##  5\. Open problems

One very natural question to ask is as follows. Suppose that as usual we are
choosing $c_{1}$ points of $A$ and $c_{2}$ points of $B$, where $|A|=|B|=n$
and $c_{1}c_{2}$ is a fixed multiple of $n$. Are there phenomena that may not
occur in the regime where say we are choosing $c_{1}=n$ (in other words, we
choose the whole of $A$) and $c_{2}$ bounded, but might possibly always hold
when both $c_{1}$ and $c_{2}$ are of order $\sqrt{n}$? One example is the
following.

Question 1. Is there a constant $c$ such that the following is true? If $A$
and $B$ are non-empty subsets of ${\mathbb{Z}}_{p}$ with
$|A|=|B|=n\leqslant(p+1)/2$ then there are subsets $A^{\prime}\subset A$ and
$B^{\prime}\subset B$ with $|A^{\prime}|=|B^{\prime}|\leqslant c\sqrt{n}$ such
that $|A^{\prime}+B^{\prime}|\geqslant 2n-1$.

As remarked in the Introduction, this is not true for $c_{1}=n$ and $c_{2}$
bounded, in other words for $A^{\prime}=A$ and $|B^{\prime}|$ bounded, as may
be seen by taking $A$ and $B$ to be random subsets of ${\mathbb{Z}}_{p}$ of
size approaching $p/2$. But it might conceivably be true when we force both
$c_{1}$ and $c_{2}$ to be large.

In a similar vein, one might ask whether the case of both $c_{1}$ and $c_{2}$
being of order $\sqrt{n}$ is in fact always the ‘best’ case (where $A$ and $B$
are set of size $n$, say). Thus for Theorem 1 we would be asking the
following.

Question 2. Let $c>0$ and $c_{1}=c_{1}(n)$ be such that whenever $A$ and $B$
are subsets of ${\mathbb{Z}}_{p}$ with $|A|=|B|=n\leqslant p/3$ there exist
subsets $A^{\prime}\subset A$ and $B^{\prime}\subset B$, with
$|A^{\prime}|\leqslant c_{1}$ and $|B^{\prime}|\leqslant cn/c_{1}$, such that
$|A^{\prime}+B^{\prime}|\geqslant 2n-1$. Does it follow that whenever $A$ and
$B$ are subsets of ${\mathbb{Z}}_{p}$ with $|A|=|B|=n\leqslant p/3$ there
exist subsets $A^{\prime}\subset A$ and $B^{\prime}\subset B$ with
$|A^{\prime}|=|B^{\prime}|\leqslant\sqrt{cn}$ such that
$|A^{\prime}+B^{\prime}|\geqslant 2n-1$?

One could also ask what the ‘worst’ case is: is it when $c_{1}=c$ and
$c_{2}=n$? More generally, is there ‘monotonicity’ as $c_{1}$ varies from $c$
to $\sqrt{cn}$?

It would also be very interesting to obtain good bounds on the constants
appearing in our various results. For example, in Theorem 1, what is the form
of the dependence of $c$ on $\alpha$ and $\beta$?

Finally, we consider what happens for discrete versions of the Brunn–Minkowski
inequality. Green and Tao [14] showed that, given a dimension $k$ and a
constant $\varepsilon>0$, there exists $t$ such that if $A$ is a subset of
${\mathbb{Z}}^{k}$ of size $n$ that is not contained inside $t$ parallel
hyperplanes (intuitively, $A$ ‘does not look lower-dimensional’), then
$|A+A|\geqslant(2^{k}-\varepsilon)n$. We wonder if the following might be
true. Although this is a question about $\mathbb{Z}$ rather than
$\mathbb{Z}_{p}$, we feel that the methods in this paper are likely to be
relevant.

Question 3. For a given dimension $k$, does there exist a constant $c$ such
that the following holds? For any $\varepsilon>0$ there exists $t$ such that
if $A$ is a subset of ${\mathbb{Z}}^{k}$ of size $n$ that is not contained in
$t$ parallel hyperplanes, then there exists a subset $A^{\prime}$ of $A$ of
size at most $c\sqrt{n}$ such that
$|A^{\prime}+A^{\prime}|\geqslant(2^{k}-\varepsilon)n$.

## References

  * [1] Alon, N., M. B. Nathanson and I. Ruzsa, Adding distinct congruence classes modulo a prime, Amer. Math. Monthly 102 (1995) 250–255.
  * [2] Bollobás, B., I. Leader and M. Tiba, Large sumsets from small subsets, arXiv:2204.07559 43 pp.
  * [3] Breuillard, E., B. Green and T. Tao, Small doubling in groups, in Erdős Centennial, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest, 2013, pp. 129–151.
  * [4] Cauchy, A., Recherches sur les nombres, J. École Polytechnique 9 (1813) 99–116. Also de Cauchy, A.L., Recherches sur les nombres, Œuvres (2nd series, Paris, 1882), vol. 1, pp. 39–63.
  * [5] Davenport, H., On the addition of residue classes, J. London Math. Soc. 10 (1935) 30–32.
  * [6] Davenport, H., A historical note, J. London Math. Soc. 22 (1947) 100–101.
  * [7] Dias da Silva, J. A., and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994) 140–146.
  * [8] Ellenberg, J.S., Sumsets as unions of sumsets of subsets, Discrete Analysis (2017), paper 14, 5 pp.
  * [9] Erdős, P., and H. Heilbronn, On the addition of residue classes mod $p$, Acta Arith. 9 (1964) 149–159.
  * [10] Freǐman, G.A., The addition of finite sets I, Izv. Vysš. Učebn. Zaved. Matematika 6 (1959) 202–213. (in Russian)
  * [11] Freǐman, G.A., Inverse problems of additive number theory VI, On the addition of finite sets III, Izv. Vysš. Učebn. Zaved. Matematika 28 (1962) 151–157. (in Russian)
  * [12] Freǐman, G.A., Foundations of a Structural Theory of Set Addition (in Russian), Kazan, 1966; English translation: American Mathematical Society, Providence, R. I. (1973). Translated from the Russian, Translations of Mathematical Monographs 37, 108 pp.
  * [13] Freiman, G.A., What is the structure of $K$ if $K+K$ is small? In Number Theory (New York, 1984–1985), Lecture Notes in Math. 1240, Springer, Berlin, 1987, pp. 109–134.
  * [14] Green, B., and T. Tao, Compressions, convex geometry and the Freiman–Bilu theorem, Quart. J. Math. 57 (2006) 495–504.
  * [15] Grynkiewicz, D. Structural additive theory. 30. Springer Science and Business Media, 2013.
  * [16] Kneser, M., Summenmengen in lokalkompakten abelschen Gruppen, Math. Z. 66 (1956) 88–110.
  * [17] Mann, H.B., On products of sets of group elements, Canad. J. Math. 4 (1952) 64–66.
  * [18] Mann, H.B., An addition theorem of Abelian groups for sets of elements, Proc. Amer. Math. Soc. 4 (1953) 423.
  * [19] Nathanson, M.B., Additive Number Theory. Inverse Problems and the Geometry of Sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996, xiv +293 pp.
  * [20] Plünnecke, H., Eine zahlentheoretische Anwendung der Graphtheorie, J. Reine Angew. Math. 243 (1970) 171–183.
  * [21] Ruzsa, I.Z., An application of graph theory to additive number theory, Scientia (A) 3 (1989) 97–109.
  * [22] Shao, X., On an almost all version of the Balog–Szeméredi–Gowers theorem, Discrete Analysis (2019), paper 18, 18 pp.
  * [23] Stanchescu, Y., On addition of two distinct sets of integers, Acta Arith. 75 (1996) 191–194.
  * [24] Tao, T., and V.H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics 105, Cambridge University Press, Cambridge, 2006. xviii+512 pp.


# Speech-to-Speech Translation with Discrete-Unit-Based Style Transfer

###### Abstract

Direct speech-to-speech translation (S2ST) with discrete self-supervised
representations has achieved remarkable accuracy, but is unable to preserve
the speaker timbre of the source speech during translation. Meanwhile, the
scarcity of high-quality speaker-parallel data poses a challenge for learning
style transfer between source and target speech. We propose an S2ST framework
with an acoustic language model based on discrete units from a self-supervised
model and a neural codec for style transfer. The acoustic language model
leverages self-supervised in-context learning, acquiring the ability for style
transfer without relying on any speaker-parallel data, thereby overcoming the
issue of data scarcity. By using extensive training data, our model achieves
zero-shot cross-lingual style transfer on previously unseen source languages.
Experiments show that our model generates translated speeches with high
fidelity and style similarity. Audio samples are available at
http://stylelm.github.io/ .

Index Terms—  direct speech-to-speech translation, style-transfer, spoken
language model

##  1 Introduction

Fig. 1: We propose an S2ST approach for style transfer based on discrete
representations from a self-supervised speech model and a neural codec. Figure
(a) shows the inference pipeline of our method; figure (b) illustrates the
self-supervised training process of the acoustic language model of $S_{2}$.

Speech-to-speech translation (S2ST) aims to translate spoken utterances in one
language into corresponding ones in another language, which can bring immense
convenience to communication between speakers of different languages.
Conventional S2ST systems employ pipelines comprising automatic speech
recognition (ASR), machine translation (MT), or speech-to-text translation
(S2T), followed by text-to-speech synthesis (TTS). More recent research has
been exploring direct S2ST without intermediate text generation which has a
more concise pipeline, reducing computation cost and error propagation, and
facilitating application to unwritten languages.

Recent mainstream approaches of direct S2ST [1, 2, 3, 4] utilize discrete
representation of speech from self-supervised models (such as HuBERT [5]) as
prediction target, and then use them to reconstruct the waveform. Such
representation eliminates speaker identity and prosody of the speeches and
retains only semantic contents, which simplifies the target distribution and
makes the translation less challenging. However, it also leads to the drawback
of losing the style information of source speeches. Extra voice conversion
systems are needed if users want to keep the source speaker timbre, which may
bring in additional quality degradation and raise the cost and complexity of
the application.

Some works propose direct S2ST with style transfer [6, 7]. These methods
depend on paired data that source and target speech have the same speaker.
This can be a shortcoming since such data from the real world is extremely
scarce as it requires a large number of multilingual speakers. Simulated data
generated by multilingual TTS systems, which are adopted by these works,
however, also brings in extra cost of data collection, and its style diversity
does not match that of real-world speech due to limitations of TTS systems.

Inspired by recent progress in spoken language models [8, 9, 10], we propose a
novel approach for direct S2ST with the ability of cross-lingual style
transfer, and does not rely on any speaker-parallel data. We utilize two types
of discrete representations, namely semantic and acoustic units, from self-
supervised speech model and neural codec, separately. Our method encompasses
the following stages: 1) speech-to-semantic-unit translation, which translates
source speech to target semantic units; 2) acoustic unit modeling, which
generates target acoustic units from translated semantic units using style
information in the source speech; and 3) unit-to-wave generation, which
reconstructs high-fidelity waveform of target speech from the acoustic units.
Our design decomposes the translation of linguistic contents and the transfer
of style characteristics, and finally generates target speeches with accurate
content and rich acoustic properties.

For the acoustic unit modeling stage, we introduce an acoustic language model
based on discrete units. It employs a self-supervised training approach and
learns style transfer through in-context learning from the sequence formed by
semantic and acoustic units, without relying on any speaker-parallel data, and
thus addresses the issue of data scarcity. By utilizing extensive self-
supervised training data, our model achieves zero-shot cross-lingual style
transfer with source languages that are not included in training. Experiments
show that our model generates results with superior audio quality and style
similarity while maintaining accurate content.

Our contributions can be summarized as follows:

  * •

We propose a novel approach for speech-to-speech translation with style
transfer. With the utilization of extensive training data, our model possesses
cross-lingual style transfer capability even on previously unseen source
languages.

  * •

By employing self-supervised training, our model can obtain style transfer
ability without the need for any speaker-parallel data, thus addressing the
issue of data scarcity.

  * •

Experiments show that our method generates high-quality translated speeches
while maintaining high style similarity to the source speech.

##  2 Method

The overall inference pipeline of our method is illustrated in Fig.1 (a). Our
method comprises three consecutive stages, utilizing two distinct types of
discrete units: 1) speech-to-semantic-unit translation stage $S_{1}$, which
converts source audio into semantic units of the target speech; 2) acoustic
unit modeling stage $S_{2}$, generating target acoustic units conditioned on
the semantic output from the preceding stage and the acoustic units of the
source speech as style prompt; 3) unit-to-wave generation stage $S_{3}$,
producing target audio that maintains consistent style with the source. We
provide details about these two types of units and the three stages in the
following subsections.

###  2.1 Semantic and Acoustic Units

Discrete HuBERT [5] units obtained from the clustering of self-supervised
speech representations are shown [2, 3] to be effective in providing semantic
content information and are adopted in S2ST as prediction target [1, 2, 3, 4].
HuBERT encodes the target speech into continuous representations with a frame
length of 20 ms, and these representations are then discretized with the
k-means algorithm. Through this method, given an spoken utterance $y$, we can
obtain its semantic unit sequence
$\mathbf{s}=[s_{1},s_{2},...,s_{T}],s_{i}\in\\{0,1,...,K_{s}-1\\},\forall
1\leq i\leq T$, with $T$ and $K_{s}$ being number of frames and clusters.

On the other hand, audio codec models with encoder-decoder architecture such
as SoundStream [11] have recently shown outstanding performance in learning
acoustic information. Such a codec model can produce discrete representations
of audio by employing a convolutional encoder followed by a residual vector
quantizer, and these representations can be used to reconstruct waveforms with
the corresponding decoder. Given an audio $y$, we can get its acoustic unit
sequence
$\mathbf{a}=[a_{1}^{1},a_{1}^{2},...,a_{1}^{C},a_{2}^{1},...,a_{T}^{C}],a_{i}^{j}\in\\{0,1,...,K_{a}-1\\},\forall
1\leq i\leq T,1\leq j\leq C$, with $T,C,K_{a}$ being number of frames, number
of residual codebooks and codebook size. We rely on these two types of units
as the intermediate representations for translation.

###  2.2 Speech-to-Semantic-Unit Translation

The speech-to-semantic-unit translation stage generates target semantic units
conditioned on source speech input, achieving translation of linguistic
content. This procedure is commonly referred to as S2UT, and several models
[1, 3, 4] have been proposed for it. These models combine a convolutional
speech encoder with an encoder-decoder architecture based on transformer or
conformer, taking source audios to produce discrete HuBERT units.

Due to the decoupling nature of our method between different stages, we have
the flexibility to adopt various S2UT models in this stage. We conduct
experiments using different S2UT models in different scenarios, and the
details are given in the experimental section.

###  2.3 Acoustic Unit Modeling

The acoustic unit modeling stage $S_{2}$ generates target acoustic units from
semantic tokens and style prompts. The core component of $S_{2}$ is an
acoustic language model, which is basically a decoder-only transformer. The
model takes a prefix sequence formed by concatenating acoustic unit sequence
$\mathbf{a_{p}}$, which serves as a style prompt, and the target semantic
sequence $\mathbf{s}$, and generates the target acoustic sequence $\mathbf{a}$
autoregressively. This procedure can be formulated as

$p\left(\mathbf{a}\mid\mathbf{a}_{\mathbf{p}},\mathbf{s};\theta_{AR}\right)=\prod_{t=1}^{T}\prod_{c=1}^{C}p\left(\mathbf{a}_{t}^{c}\mid\mathbf{a}_{<t},\mathbf{a}_{t}^{<c},\mathbf{a}_{\mathbf{p}},\mathbf{s};\theta_{AR}\right)$
(1)

The entire sequence is in the format of $[\mathbf{a_{p}|s|a}]$, with a
separator token between each pair of adjacent parts. 3 codebooks are used for
both prompt $\mathbf{a_{p}}$ and target $\mathbf{a}$.

The training procedure of $S_{2}$ is illustrated in Figure 1(b). During
training, we extract semantic and acoustic units from the training data. We
divide each training sample into two separate parts, using the acoustic units
from one part as prompt and those from the other as prediction targets, and
train the model to generate corresponding acoustic units from the semantic
units and prompt with cross-entropy loss. This in-context learning approach
enables the model to grasp the correspondence in acoustic characteristics
between the two parts, thus acquiring the ability for style transfer. And such
a self-supervised training approach needs no speaker-parallel data, and can be
scaled to massive training data. During inference, we use semantic tokens from
the previous stage and acoustic units of source speech as the style prompt to
realize cross-lingual style transfer.

###  2.4 Unit-to-Wave Generation

In the waveform generation stage $S_{3}$, the target acoustic units are mapped
to high-fidelity waveforms. Instead of directly using the codec decoder, we
adopt a GAN-based unit vocoder, which is proved to have higher perceptual
quality when the codebook number is limited [10]. Specifically, our vocoder is
derived from BigVGAN [12], with a generator built from a set of look-up tables
(LUT) that embed the discrete units, and a series of blocks composed of
transposed convolution and a residual block with dilated layers. Multi-period
discriminator (MPD) and multi-resolution discriminator (MRD) are used for
adversarial training.

##  3 Experiments

###  3.1 Dataset

We use CVSS-C dataset [13] as the translation benchmark. We conduct
experiments on two language pairs: French-English (Fr-En) and Spanish-English
(Es-En). We also use CVSS-T [13] as a baseline for speaker similarity, whose
target possesses speaker timbre transferred from the source.

For the acoustic part, we use the unlab-60k subset of Libri-Light [14], which
is a large-scale corpus containing about 57.7k hours of unlabeled English
speeches, to train the $S_{2}$ stage model. And we use LibriTTS [15] a to
train the SoundStream for acoustic unit extraction and the vocoder. All audio
is processed at a 16 kHz sampling rate.

###  3.2 Model Configurations

Table 1: Translation Quality on CVSS Dataset. Lang | Model |  BLEU ($\uparrow$) |  MOS ($\uparrow$) |  Cos ($\uparrow$)
---|---|---|---|---
Fr-En | S2UT | 18.08 |  3.73 $\pm$ 0.06 | /
\+ ms-vocoder | 17.59 |  3.35 $\pm$ 0.08 | 0.48
Ours | 17.64 |  3.84 $\pm$ 0.07 | 0.73
GT (CVSS-C) | 84.52 |  3.93 $\pm$ 0.06 | /
GT (CVSS-T) | 81.48 |  3.97 $\pm$ 0.07 | 0.68
Es-En | S2UT | 23.78 |  3.74 $\pm$ 0.07 | /
\+ ms-vocoder | 23.26 |  3.31 $\pm$ 0.09 | 0.50
Ours | 23.41 |  3.87 $\pm$ 0.07 | 0.75
GT (CVSS-C) | 88.54 |  3.91 $\pm$ 0.06 | /
GT (CVSS-T) | 84.81 |  3.93 $\pm$ 0.07 | 0.70
Table 2: Quality and Style Similarity of Voice Conversion Model |  MOS ($\uparrow$) |  SMOS ($\uparrow$) |  Cos ($\uparrow$)
---|---|---|---
PPG-VC |  3.37 $\pm$ 0.07 |  3.30 $\pm$ 0.06 | 0.65
NANSY |  3.56 $\pm$ 0.06 |  3.47 $\pm$ 0.05 | 0.68
YourTTS |  3.74 $\pm$ 0.05 |  3.60 $\pm$ 0.06 | 0.69
Ours |  3.86 $\pm$ 0.05 |  3.69 $\pm$ 0.05 | 0.74
CVSS-T target |  3.95 $\pm$ 0.05 |  3.56 $\pm$ 0.06 | 0.69

For semantic representation, we apply the publicly available pre-trained
multilingual HuBERT (mHuBERT) model and the k-means model of 1000 clusters to
discretize 11th-layer features. For acoustic representation, we train a
SoundStream model with 12 quantization levels and with a size of 1024 for each
codebook and an overall downsampling rate of 320.

For $S_{1}$ stage, we train an S2UT-conformer for Fr-En following [1], and an
xm-transformer for Es-En following [4] but without mbart-decoder
initialization. The decoder-only transformer of $S_{2}$ has about 760M
parameters, with 26 layers and a hidden dimension of 1536. Models are
implemented with fairseq [16] and trained using 6 Tesla V100 GPUs.

###  3.3 Metrics

We measure the performance of our model in terms of translation quality,
speech quality, and style similarity with the source speech. For translation
quality, we transcribe the generated speeches using a wav2vec2 ASR model and
calculate BLEU scores between the generated and reference text. For speech
quality, we employ a subjective evaluation with Mean Opinion Score (MOS),
where testers on the Amazon MTurk platform rate audio naturalness using a 1-5
Likert scale. For style similarity, we calculate Speaker Cosine Similarity
(Cos) and Similarity MOS (SMOS) between the source and results.

We calculate BLEU scores over the entire test split and randomly sample 500
items from each language pair for other metrics, which represents
approximately 3% of the test set.

###  3.4 Results and Analysis

Table 1 summarizes the translated speech quality, where we compare our results
with direct S2UT, together with ground truth target speech in CVSS-C and
CVSS-T for reference. We can see that compared to S2UT, our model achieves a
noticeable improvement of 0.11 and 0.13 on MOS, while having only slight
declines of 0.44 and 0.37 in BLEU scores on the two language pairs. This
indicates that the $S_{2}$ stage in our method causes only minimal error in
semantic content but enhances the quality of the resulting speech a lot.
Meanwhile, the direct S2UT pipeline with a unit-based HiFi-GAN vocoder lacks a
mechanism for modeling various acoustic conditions and can only generate
speeches of a single speaker. We also train a multi-speaker semantic vocoder
(ms-vocoder in Table 1) for the S2UT semantic output to verify if semantic
units contain timbre information. However, it produces speeches with a mixed
timbre and low quality, along with low Cos scores. This indicates that
semantic units lack sufficient acoustic information for style maintenance. On
the other hand, our model achieves scores of 0.73 and 0.75 for speaker
similarity, which even surpasses the CVSS-T target, demonstrating that our
model’s mechanism achieves outstanding performance in zero-shot cross-lingual
style transfer.

To further evaluate our model’s style transfer capability, we conduct
comparisons with three voice conversion models, which are PPG-VC[17],
NANSY[18] and YourTTS[19]. We use them to conduct voice conversion on the
vocoder output of direct S2UT and source speech. We also provide the results
of target speech in CVSS-T for reference. Table 2 summarizes the results. It
can be seen that our model achieves a MOS of 3.86, which significantly
outperforms the three baselines. This indicates that in comparison to cascaded
voice conversion, the style transfer based on discrete intermediate
representations used by our model can mitigate quality losses during the
transfer process and produce higher-quality audio. Our model also achieves
superior values on style similarity metrics, with SMOS of 3.69 and Cos of
0.74, which surpasses all other results. This can be attributed to the larger
model size and use of large training data. Through a language model with
larger parameters and extensive training data, our model acquires strong zero-
shot style transfer capability and can generalize effectively to unseen source
languages.

###  3.5 Ablation Studies

To further investigate the impact of training data volume and model size on
the model’s performance, we conduct ablation experiments. Table 3 summarizes
the model’s performance under two different training data volumes. LibriTTS
comprises 585.5 hours of audio with 2,456 speakers, while Libri-Light
unlab-60k consists of 57.7k hours of audio with 7,439 speakers. We observe
that when using the small-scale LibriTTS dataset, there is a significant
decrease in SMOS and Cos scores with reductions of 0.14 and 0.07, indicating a
deterioration in style transfer performance. This suggests that the duration
and speaker number of the training data are essential for the model’s style
transfer capability. On the other hand, the small-scale dataset has a
relatively minor impact on MOS, resulting in only a 0.02 decrease. This
suggests that the acoustic language model can achieve the ability to generate
highly natural speech without requiring an extensive amount of data.
Meanwhile, we try to add part of French and Spanish speeches from CVSS source
to the training data, obtaining a marginal improvement of 0.02 on both Cos and
SMOS. This indicates that our model’s voice conversion performance on unseen
source languages is close to that on seen languages, which is attributed to
the use of extensive training data.

Table 4 summarizes the audio quality and style similarity of the model under
different model sizes. All three metrics indicate that as the model’s
parameter size decreases, both audio quality and similarity decline. This
illustrates that the superior performance of our acoustic language model is
closely linked to its large parameter size.

##  4 Conclusions

Table 3: Ablation on Training Data of $S_{2}$ Training Data |  MOS ($\uparrow$) |  SMOS ($\uparrow$) |  Cos ($\uparrow$)
---|---|---|---
LibriTTS |  3.84 $\pm$ 0.05 |  3.55 $\pm$ 0.05 | 0.67
Libri-Light unlab-60k |  3.86 $\pm$ 0.05 |  3.69 $\pm$ 0.05 | 0.74
\+ CVSS source |  3.85 $\pm$ 0.05 |  3.71 $\pm$ 0.05 | 0.76
Table 4: Ablation on Model Size of $S_{2}$ Model Size |  MOS ($\uparrow$) |  SMOS ($\uparrow$) |  Cos ($\uparrow$)
---|---|---|---
Small (160M) |  3.73 $\pm$ 0.06 |  3.58 $\pm$ 0.05 | 0.70
Base (430M) |  3.81 $\pm$ 0.05 |  3.64 $\pm$ 0.05 | 0.73
Large (760M) |  3.86 $\pm$ 0.05 |  3.69 $\pm$ 0.05 | 0.74

In this work, we propose a direct S2ST approach with style transfer based on
two distinct types of discrete representations. We adopt an acoustic language
model that acquires the ability of style transfer through in-context learning.
By adopting self-supervised training, our method addresses the scarcity of
speaker-parallel data. And by leveraging large-scale training data, our model
achieves cross-lingual style transfer with unseen source languages.
Experimental results indicate that our approach achieves good results in terms
of speech quality and style similarity, with only a minimal loss in
translation quality. In future work, we plan to introduce more diverse prompt
information into the acoustic language model to achieve a greater variety of
translated speech results.

## References

  * [1] Ann Lee, Peng-Jen Chen, Changhan Wang, Jiatao Gu, Sravya Popuri, Xutai Ma, Adam Polyak, Yossi Adi, Qing He, Yun Tang, et al.,  “Direct speech-to-speech translation with discrete units,”  arXiv preprint arXiv:2107.05604, 2021.
  * [2] Ann Lee, Hongyu Gong, Paul-Ambroise Duquenne, Holger Schwenk, Peng-Jen Chen, Changhan Wang, Sravya Popuri, Yossi Adi, Juan Pino, Jiatao Gu, et al.,  “Textless speech-to-speech translation on real data,”  arXiv preprint arXiv:2112.08352, 2021.
  * [3] Rongjie Huang, Jinglin Liu, Huadai Liu, Yi Ren, Lichao Zhang, Jinzheng He, and Zhou Zhao,  “Transpeech: Speech-to-speech translation with bilateral perturbation,”  arXiv preprint arXiv:2205.12523, 2022.
  * [4] Sravya Popuri, Peng-Jen Chen, Changhan Wang, Juan Pino, Yossi Adi, Jiatao Gu, Wei-Ning Hsu, and Ann Lee,  “Enhanced direct speech-to-speech translation using self-supervised pre-training and data augmentation,”  arXiv preprint arXiv:2204.02967, 2022.
  * [5] Wei-Ning Hsu, Benjamin Bolte, Yao-Hung Hubert Tsai, Kushal Lakhotia, Ruslan Salakhutdinov, and Abdelrahman Mohamed,  “Hubert: Self-supervised speech representation learning by masked prediction of hidden units,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 29, pp. 3451–3460, 2021.
  * [6] Ye Jia, Michelle Tadmor Ramanovich, Tal Remez, and Roi Pomerantz,  “Translatotron 2: Robust direct speech-to-speech translation,”  2021\.
  * [7] Kun Song, Yi Ren, Yi Lei, Chunfeng Wang, Kun Wei, Lei Xie, Xiang Yin, and Zejun Ma,  “Styles2st: Zero-shot style transfer for direct speech-to-speech translation,”  arXiv preprint arXiv:2305.17732, 2023.
  * [8] Zalán Borsos, Raphaël Marinier, Damien Vincent, Eugene Kharitonov, Olivier Pietquin, Matt Sharifi, Dominik Roblek, Olivier Teboul, David Grangier, Marco Tagliasacchi, et al.,  “Audiolm: a language modeling approach to audio generation,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2023.
  * [9] Chengyi Wang, Sanyuan Chen, Yu Wu, Ziqiang Zhang, Long Zhou, Shujie Liu, Zhuo Chen, Yanqing Liu, Huaming Wang, Jinyu Li, et al.,  “Neural codec language models are zero-shot text to speech synthesizers,”  arXiv preprint arXiv:2301.02111, 2023.
  * [10] Rongjie Huang, Chunlei Zhang, Yongqi Wang, Dongchao Yang, Luping Liu, Zhenhui Ye, Ziyue Jiang, Chao Weng, Zhou Zhao, and Dong Yu,  “Make-a-voice: Unified voice synthesis with discrete representation,”  arXiv preprint arXiv:2305.19269, 2023.
  * [11] Neil Zeghidour, Alejandro Luebs, Ahmed Omran, Jan Skoglund, and Marco Tagliasacchi,  “Soundstream: An end-to-end neural audio codec,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 30, pp. 495–507, 2021.
  * [12] Sang-gil Lee, Wei Ping, Boris Ginsburg, Bryan Catanzaro, and Sungroh Yoon,  “Bigvgan: A universal neural vocoder with large-scale training,”  arXiv preprint arXiv:2206.04658, 2022.
  * [13] Ye Jia, Michelle Tadmor Ramanovich, Quan Wang, and Heiga Zen,  “Cvss corpus and massively multilingual speech-to-speech translation,”  arXiv preprint arXiv:2201.03713, 2022.
  * [14] Jacob Kahn, Morgane Rivière, Weiyi Zheng, Evgeny Kharitonov, Qiantong Xu, Pierre-Emmanuel Mazaré, Julien Karadayi, Vitaliy Liptchinsky, Ronan Collobert, Christian Fuegen, et al.,  “Libri-light: A benchmark for asr with limited or no supervision,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 7669–7673.
  * [15] Heiga Zen, Viet Dang, Rob Clark, Yu Zhang, Ron J Weiss, Ye Jia, Zhifeng Chen, and Yonghui Wu,  “Libritts: A corpus derived from librispeech for text-to-speech,”  arXiv preprint arXiv:1904.02882, 2019.
  * [16] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli,  “fairseq: A fast, extensible toolkit for sequence modeling,”  in Proceedings of NAACL-HLT 2019: Demonstrations, 2019.
  * [17] Songxiang Liu, Yuewen Cao, Disong Wang, Xixin Wu, Xunying Liu, and Helen Meng,  “Any-to-many voice conversion with location-relative sequence-to-sequence modeling,”  IEEE/ACM Transactions on Audio, Speech, and Language Processing, vol. 29, pp. 1717–1728, 2021.
  * [18] Hyeong-Seok Choi, Juheon Lee, Wansoo Kim, Jie Lee, Hoon Heo, and Kyogu Lee,  “Neural analysis and synthesis: Reconstructing speech from self-supervised representations,”  Advances in Neural Information Processing Systems, vol. 34, pp. 16251–16265, 2021.
  * [19] Edresson Casanova, Julian Weber, Christopher D Shulby, Arnaldo Candido Junior, Eren Gölge, and Moacir A Ponti,  “Yourtts: Towards zero-shot multi-speaker tts and zero-shot voice conversion for everyone,”  in International Conference on Machine Learning. PMLR, 2022, pp. 2709–2720.