# On the independence number of
sparser random Cayley graphs

Marcelo Campos and Gabriel Dahia and João Pedro Marciano  IMPA, Estrada Dona
Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil
{gabriel.dahia<EMAIL_ADDRESS>Department of Pure Mathematics and
Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge,
CB3 0WA, UK<EMAIL_ADDRESS>
###### Abstract.

The Cayley sum graph $\Gamma_{A}$ of a set $A\subseteq\mathbb{Z}_{n}$ is
defined to have vertex set $\mathbb{Z}_{n}$ and an edge between two distinct
vertices $x,y\in\mathbb{Z}_{n}$ if $x+y\in A$. Green and Morris proved that if
the set $A$ is a $p$-random subset of $\mathbb{Z}_{n}$ with $p=1/2$, then the
independence number of $\Gamma_{A}$ is asymptotically equal to
$\alpha(G(n,1/2))$ with high probability. Our main theorem is the first
extension of their result to $p=o(1)$: we show that, with high probability,

$\alpha(\Gamma_{A})=(1+o(1))\alpha(G(n,p))$

as long as $p\geq(\log n)^{-1/80}$.

One of the tools in our proof is a geometric-flavoured theorem that
generalises Freĭman’s lemma, the classical lower bound on the size of high
dimensional sumsets. We also give a short proof of this result up to a
constant factor; this version yields a much simpler proof of our main theorem
at the expense of a worse constant.

##  1\. Introduction

Let $n\in\mathbb{N}$ be a large prime. The Cayley sum graph $\Gamma_{A}$ of a
set $A\subseteq\mathbb{Z}_{n}$ is defined to have $\mathbb{Z}_{n}$ as its
vertices and an edge between two distinct $x,y\in\mathbb{Z}_{n}$ if $x+y\in
A$. Alon [1, Conjecture 4.4] conjectured that for each $t\in\\{1,\dots,n\\}$,
there exists a set $A\subseteq\mathbb{Z}_{n}$ such that $|A|=t$ and
$\Gamma_{A}$ has independence number at most $\frac{n}{t}(\log n)^{O(1)}$, and
moreover remarked that “the conjecture may well hold for a random choice of
$A$.”

Green more generally asked (see [17, Question 2]) which parameters of
$\Gamma_{A}$ match those of the random graph $G(n,p)$ when $A$ is a random
subset of $\mathbb{Z}_{n}$. In that same work, he showed that if $A$ is chosen
uniformly at random over all subsets of $\mathbb{Z}_{n}$, then with high
probability the size of the largest independent set111Green actually states
this for the clique number, but this is equivalent to what we state since a
${1/2}$-random subset of $\mathbb{Z}_{n}$ has the same distribution of its
complement. of $\Gamma_{A}$ is at most $\alpha(G(n,1/2))$, up to a constant
factor.

This result is in fact a consequence of a theorem in additive combinatorics.
Recall that the sumset $X+Y$ and the restricted sumset $X\mathbin{\hat{+}}X$
are defined as

$X+Y=\\{x+y:x\in X,y\in Y\\},\qquad
X\mathbin{\hat{+}}X=\\{x_{1}+x_{2}:x_{1},x_{2}\in X,x_{1}\neq x_{2}\\},$

and observe that $X\subseteq\mathbb{Z}_{n}$ is independent in $\Gamma_{A}$
exactly when $X\mathbin{\hat{+}}X\subseteq A^{\mathsf{c}}$. Green deduced his
bound on the typical size of $\alpha(\Gamma_{A})$ from estimates on the number
of sets $X\subseteq\mathbb{Z}_{n}$ such that $|X|=k$ and $|X+X|\leq\sigma k$,
where $\sigma$ is some upper bound on the doubling of $X$. When referring to
the doubling of the set itself, we will use $\sigma[X]$, i.e.
$\sigma[X]=|X+X|/|X|$.

Later, Green and Morris [18] showed that better estimates on the number of
such sets are possible if one handles ranges of $\sigma[X]$ differently. When
$\sigma[X]$ is constant, they used an arithmetic regularity lemma to obtain a
tighter bound. Leveraging the isoperimetric inequality on $\mathbb{Z}^{d}$,
they obtain a bound on the number of “quasi-random” elements in sets with
doubling close to maximum, thus refining Green’s estimate for the number of
such sets. As a consequence, they determined the correct constant for the
independence number of $\Gamma_{A}$ when $A\subseteq\mathbb{Z}_{n}$ is uniform
random, showing that $\alpha(\Gamma_{A})$ asymptotically matches
$\alpha(G(n,1/2))$ with high probability [18].

Our main theorem extends the above result of Green and Morris to the more
challenging setting when $A$ is a sparse random subset of $\mathbb{Z}_{n}$,
and can be seen as progress towards Alon’s aforementioned conjecture. To state
our result, it is useful to denote by $\Gamma_{p}$ the (random) Cayley sum
graph $\Gamma_{A}$ when $A$ is a $p$-random subset of $\mathbb{Z}_{n}$ for
$p=p(n)$.

######  Theorem 1.1.

Let $n$ be a prime number and let $p=p(n)$ satisfy $p\geq(\log n)^{-1/80}$.
The random Cayley sum graph $\Gamma_{p}$ of $\mathbb{Z}_{n}$ satisfies

$\alpha(\Gamma_{p})=\big{(}2+o(1)\big{)}\log_{\frac{1}{1-p}}n$ (1)

with high probability as $n\to\infty$.

If $p=o(1)$, then this bound is asymptotically equal to $(2+o(1))(\log n)/p$;
it also matches $\alpha(G(n,p))$ in the corresponding range of $p$ [4, 21]. We
remark that we do not believe the lower bound on $p$ in Theorem 1.1 to be
close to optimal, so we do not optimize the constant in the exponent of the
$\log$. Nonetheless, there is a natural barrier for our methods when proving
upper bounds at around $p\approx(\log n)^{-1}$ (see Section 10).

The lower bound in (1) follows from a second moment computation together with
a simple combinatorial argument (see Section 9). The proof of the upper bound,
on the other hand, is much more challenging, even though it has the same broad
outline pioneered by Green [17]. In fact, we use his bounds on the number of
sets with given doubling for the “middle” range $k^{\beta}<\sigma[X]=o(k)$,
and a minor extension (that follows from the same proof) of the theorem of
Green and Morris [18] for the “upper” range $\sigma[X]=\Theta(k)$. Our
contribution is therefore in the “lower” doubling range, $\sigma[X]\leq
k^{\beta}$ for a small constant $\beta>0$, where even the correct count of
such sets would not be enough to prove our main theorem.

To overcome this obstacle, we show that each of those sets contains a much
smaller subset $F$ – we call it a “fingerprint” of $X$ – so that, after
determining that $F$ possesses some special properties, it suffices to count
the fingerprints to deduce Theorem 1.1. This idea is inspired by the
application of the asymmetric container method of Morris, Samotij, and Saxton
[23] to the problem of counting sets with small sumset by the first author
[9]. Indeed, we could also use asymmetric containers as a tool to prove our
main theorem, but we prefer this simpler approach as it results in better
bounds and a more self-contained proof.

The special property we require of each fingerprint $F\subseteq X$ is having a
sufficiently large sumset. Ideally, we would like $F+F$ to be as large as
$X+X$; this obviously imposes a lower bound of $|F|\geq|X+X|^{1/2}$. Bollobás,
Leader, and Tiba recently studied the question of finding such sets for
general Abelian groups: they obtain $F\subseteq X$ satisfying
$|F+F|\approx|X+X|$ when $X$ has bounded doubling [7, Theorem 2]. However,
their result does not serve our needs because it does not handle the case of
$\sigma[X]$ being $k^{\beta}$ for fixed, small $\beta>0$.

We pursue a different approach to obtain our collection of fingerprints, one
that is able to handle sets with doubling that is polynomial in their size.
This approach yields fingerprints such that $|F|\approx|X+X|^{1/2}\log|X|$,
which is only a logarithmic factor away from the ideal bound, but $|F+F|$ is
in general far from $|X+X|$. What we can show is that the size of the sumset
is as large as in Freĭman’s lemma, which is just enough for our application.

It is therefore useful to recall Freĭman’s lemma, and to do so we need a
definition. We will write $\operatorname{rank}(X)$ for the minimum dimension
of a hyperplane that contains a set $X\subseteq\mathbb{R}^{d}$; if
$\operatorname{rank}(X)=d$, then we say $X$ has full rank. The statement of
the lemma is then:

######  Lemma 1.2 (Freĭman [15]).

Let $X\subseteq\mathbb{R}^{d}$ be a finite set of full rank. Then,

$|X+X|\geq(d+1)|X|-\binom{d+1}{2}.$

Observe that Lemma 1.2 is a statement about subsets of $\mathbb{R}^{d}$ rather
than $\mathbb{Z}_{n}$. To amend this, we can use the (by now) standard
machinery of Freĭman isomorphisms (see, for example, [27, Chapter 5.3]) to
reach similar conclusions for subsets of the integers modulo $n$, changing
rank for Freĭman dimension when appropriate. We therefore change the setting
to $\mathbb{R}^{d}$ for the rest of this informal discussion.

Like applications of the hypergraph container method, the way to show that
$F+F$ is almost as large as $(d+1)|X|$ is by proving a suitable
supersaturation result (see Theorem 2.2, below). In fact, from this result we
will be able to show that picking a fingerprint randomly inside $X$ works.
Theorem 2.2 informally says the following: if a set $Y$ approximates $X+X$ in
terms of its popular sums, then it is (almost) as large as the bound in
Freĭman’s lemma.

This key step in the proof of Theorem 2.2 is a result stating that we can find
some small $T\subseteq X$ such that $X+T$ almost attains the bound in
Freĭman’s lemma. Proving this theorem is the most difficult part of our proof,
and we consider it to be of independent interest.

######  Theorem 1.3.

Let $d,r\in\mathbb{N}$, let $\gamma>r^{-1/3}$ and let
$X\subseteq\mathbb{R}^{d}$ be a finite set with $\operatorname{rank}(X)\geq
r$. There exists $T\subseteq X$ such that $|T|\leq 4(r+1)/\gamma$ and

$|X+T|\geq(1-5\gamma)\frac{(r+1)|X|}{2}.$

The proof of this theorem is technical; however, we will also show that if we
were satisfied with $1/6$ being the leading constant instead of
$(1-5\gamma)/2$, then a much simpler approach would suffice. This weaker
version would also be enough to prove the upper bound in Theorem 1.1 with 6
being the leading constant instead of 2.

Recently, Jing and Mudgal [22] proved the following theorem that is closely
related to Theorem 1.3. It obtains the correct leading constant, i.e. without
the $(1-5\gamma)/2$ or $1/6$ loss in our bound, at the expense of a worse
relationship between the number of translates and the dimension of the set:

######  Theorem 1.4 ([22, Theorem 1.2]).

Given $d\in\mathbb{N}$, there exists a constant $C=C(d)>0$ such that, for
every finite set of full rank $X\subseteq\mathbb{R}^{d}$, there exist
$x_{1},\ldots,x_{C}\in X$ satisfying

$|X+\\{x_{1},...,x_{C}\\}|\geq(d+1)|X|-5(d+1)^{3}.$

Theorem 1.4 is part of a recent line of work [6, 13] that relies on a
beautiful theorem of Bollobás, Leader, and Tiba [6, Theorem 8] to obtain
sumset lower bounds via few-translates. Unfortunately, the proof of this
theorem uses Shao’s [26] almost-all Balog–Szemerédi–Gowers theorem, and, as a
consequence, the dependency of the number of translates $C$ on the dimension
$d$ is of tower-type [6, 26].

A related result, which avoids super-polynomial dependencies between its
parameters, is the following elegant theorem proved by Fox, Luo, Pham, and
Zhou [13]. Its proof relies on a clever path counting argument akin to Gowers’
proof of the Balog–Szemerédi theorem. Note that we state a specialized version
of their much more general result.

######  Theorem 1.5 ([13, Theorem 1.1]).

There exists $c>0$ such that the following holds. Let
$X\subseteq\mathbb{R}^{d}$ with $|X|=k$. For every $s\in\\{1,\ldots,k\\}$,
there exists $T\subseteq X$ such that $|T|\leq s$ and

$|X+T|\geq c\min\big{\\{}\sigma[X]^{1/3},s\big{\\}}|X|.$ (2)

This result would work for our needs if we could ensure
$\sigma[X]>c^{-1}d^{3}$, but we cannot. Alas, Fox, Luo, Pham, and Zhou also
exhibit a construction [13, Proposition 2.4] which shows that we cannot even
replace $\sigma[X]^{1/3}$ in (2) by $\sigma[X]^{1/1.29}$; this means that our
requirement for the rank of the set in Theorem 1.3 is essential.

In the next section, we give a detailed sketch of our proof strategy, and a
proof of our fingerprint theorem. Then, in Section 3, we give a simple proof
of a weaker version of our “Freĭman’s lemma via few translates” theorem that
nevertheless contains some of the main ideas required for the full proof of
Theorem 1.3. Section 4 is dedicated to improving the constant to
$(1-5\gamma)/2$, assuming two additional technical lemmas, which we prove in
Sections 5 and 6. In Section 7, we derive our supersaturation result from
Theorem 1.3, and in Sections 8 and 9 we complete the proof of our main
theorem. Finally, in Section 10, we discuss future work and open problems.

##  2\. Overview of the proof

Throughout, $n\in\mathbb{N}$ will always be a sufficiently large prime number;
we will also adopt the standard convention of omitting floors and ceilings
whenever they are not essential. Let $k\in\mathbb{N}$ be the bound that we
want to show for the independence number and let $A_{p}$ be a $p$-random
subset of $\mathbb{Z}_{n}$. Denoting $\mathcal{X}:={\mathbb{Z}_{n}\choose k}$,
we will show that

$\mathbb{P}\left(\exists\,X\in\mathcal{X}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}\right)\to 0$

as $n\to\infty$, which is equivalent to proving that $\alpha(\Gamma_{p})<k$
_w.h.p_.

We will follow Green’s general approach of partitioning
$\mathcal{X}=\mathcal{X}_{1}\cup\mathcal{X}_{2}\cup\mathcal{X}_{3}$ where each
sub-collection is defined based on the doubling $\sigma[X]$,

$\displaystyle\mathcal{X}_{1}$
$\displaystyle=\left\\{X\in\mathcal{X}:\sigma[X]\leq k^{\beta}\right\\},$
$\displaystyle\mathcal{X}_{2}$
$\displaystyle=\left\\{X\in\mathcal{X}:k^{\beta}<\sigma[X]\leq\delta
k/10\right\\},\text{ and}$ $\displaystyle\mathcal{X}_{3}$
$\displaystyle=\left\\{X\in\mathcal{X}:\delta k/10<\sigma[X]\right\\},$

for $\beta=1/40$ and some $\delta=o(1)$, and handle each one differently.
Explicitly, we use the union bound to deduce

$\mathbb{P}\left(\exists\,X\in\mathcal{X}:X\mathbin{\hat{+}}X\subseteq
A^{\mathsf{c}}\right)\leq\sum_{i=1}^{3}\mathbb{P}\left(\exists\,X\in\mathcal{X}_{i}:X\mathbin{\hat{+}}X\subseteq
A^{\mathsf{c}}\right).$

It turns out that we can bound the terms related to $\mathcal{X}_{2}$ and
$\mathcal{X}_{3}$ using the same techniques of Green [17] and Green and Morris
[18]; we therefore defer working out the details regarding these terms to
Section 8. For the remaining term, we could try to follow the methods in [18]
and take a union bound over the sets in $\mathcal{X}_{1}$:

$\mathbb{P}(\exists\,X\in\mathcal{X}_{1}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}})\leq\sum_{X\in\mathcal{X}_{1}}\mathbb{P}(X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}).$ (3)

Observe that, for each $X\subseteq\mathbb{Z}_{n}$, the probability in the
summand is

$\mathbb{P}(X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}})=(1-p)^{|X\mathbin{\hat{+}}X|}.$

Since there are more than ${m/2\choose k}$ sets $X$ such that
$|X\mathbin{\hat{+}}X|=m$, the right-hand side of (3) is at least

$\sum_{m=2k-1}^{k^{1+\beta}}{m/2\choose k}(1-p)^{m}\geq{2k\choose
k}\exp(-5kp)\to\infty,$ (4)

as $n\to\infty$, whenever $p=o(1)$ and $k\to\infty$. The conclusion is that
any approach that uses the union bound over all sets with small doubling
cannot give the optimal upper bound on the independence number for $p$ smaller
than some explicit constant, like $1/5$.

As we mentioned in the introduction, one of the key new ideas in this paper is
to show that there exists a family $\mathcal{F}$ of fingerprints such that it
suffices to consider only the events $\\{F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}}\\}_{F\in\mathcal{F}}$ instead of the collection
$\\{X\mathbin{\hat{+}}X\subseteq A_{p}^{\mathsf{c}}\\}_{X\in\mathcal{X}_{1}}$.
Trivially, $\mathcal{F}=\mathcal{X}_{1}$ is such a family, so, to make this
strategy work and improve upon taking the union bound over all $X$, we must
choose $\mathcal{F}$ in a more clever way.

The first property of these fingerprints that we require is that
$|\mathcal{F}|$ is sufficiently small, where small vaguely means that a union
bound over all $F\in\mathcal{F}$ works. One direct way to achieve that is
picking each fingerprint $F$ to be small, but there is a subtle trade-off
between the size of $F$ and the upper bound on the probability term
$(1-p)^{|F\mathbin{\hat{+}}F|}$. To circumvent this issue, we can use the fact
that we have a bound (even if a polynomially large one) on the doubling of
each $X\in\mathcal{X}_{1}$. In this setting, Freĭman’s theorem [14] says that
$X$ is contained in a generalised arithmetic progression $P$ such that both
the size $s$ and dimension $d$ of $P$ are small. Recall that a $d$-dimensional
generalised arithmetic progression is a set of the form

$\bigg{\\{}a_{0}+\sum_{i=1}^{d}w_{i}a_{i}:w_{i}\in\mathbb{Z},\,0\leq
w_{i}<\ell_{i}\bigg{\\}}$

for some differences $a_{0},\ldots,a_{d}\in\mathbb{Z}_{n}$ and side-lengths
$\ell_{1},\ldots,\ell_{d}\in\mathbb{N}$, and $P$ is proper when every possible
choice of $\\{w_{1},\ldots,w_{d}\\}$ corresponds to a distinct element of $P$.
Therefore, instead of choosing $F$ directly from $\mathbb{Z}_{n}$, we first
choose $P$ and then select $F$ inside $P$.

Now we can state the first requirement for $F\in\mathcal{F}$ in more detail.
Let $P$ be the generalised arithmetic progression given by Freĭman’s theorem
for $X$. Then, $F$ should be small enough compared to $|F\mathbin{\hat{+}}F|$
for a union bound over choices of $F\subseteq P$ to work:

$\mathbb{P}\big{(}\exists\,F\subseteq P:F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}}\big{)}\leq{s\choose|F|}(1-p)^{|F\mathbin{\hat{+}}F|}\to 0$
(5)

as $n\to\infty$. To get to this point, however, we must also choose this
generalised arithmetic progression in a previous union bound. Hence, our
second requirement for each $F$ is that $F\mathbin{\hat{+}}F$ is sufficiently
large to pay for the number of choices for the generalised arithmetic
progression $P$.

As we can count generalised arithmetic progressions with dimension $d$ and
size $s$ by choosing the $a_{0},a_{1},\ldots,a_{d}$ and $l_{1},\ldots,l_{d}$,
there are at most $(ns)^{d+1}$ of them. Temporarily ignoring the number of
choices for the fingerprint inside the progression (which we already dealt
with in (5)), this amounts to requiring that $F$ satisfies

$(ns)^{d+1}(1-p)^{|F\mathbin{\hat{+}}F|}\to 0$

as $n\to\infty$. While these conditions may seem too strict – small $F$ with
large $F\mathbin{\hat{+}}F$ for every $X$ – this is exactly what we are able
to do.

To state the actual theorem, we need to relate the dimension of the
progression to some notion of dimension for $X$. The notion that we use is the
Freĭman dimension of $X$, but to state its definition, we must first define
what are Freĭman homomorphisms and Freĭman isomorphisms. A Freĭman
homomorphism is a function ${\phi:X\to Y}$ such that for every
$a_{1},a_{2},b_{1},b_{2}\in X$,

$a_{1}+b_{1}=a_{2}+b_{2}\quad\text{ implies
}\quad\phi(a_{1})+\phi(b_{1})=\phi(a_{2})+\phi(b_{2}).$

A Freĭman isomorphism is a bijection $\phi$ such that both $\phi$ and its
inverse $\phi^{-1}$ are Freĭman homomorphisms. The Freĭman dimension of $X$,
$\dim_{\mathrm{F}}(X)$, is then defined to be the largest $d\in\mathbb{N}$ for
which there is a full rank subset of $\mathbb{Z}^{d}$ that is Freĭman
isomorphic to $X$.

It is furthermore useful to define the robustness of the Freĭman dimension of
$X$: we say that $X$ has $\varepsilon$-robust Freĭman dimension $d$ if
$\dim_{\mathrm{F}}(X)\geq d$ and there is no $X^{\prime}\subseteq X$ such that
$|X^{\prime}|\geq(1-\varepsilon)|X|$ and $\dim_{\mathrm{F}}(X^{\prime})<d$. In
words, this means that the Freĭman dimension of $X$ is at least $d$ even if we
remove an $\varepsilon$ proportion of its elements.

With these definitions, we can state our fingerprint theorem:

######  Theorem 2.1.

Let $n$ be a large enough prime and let $k,d\in\mathbb{N}$. For every
$0<\gamma<1/2$, there exists $C=C(\gamma)>0$ such that the following holds for
all $m\geq(d+1)k/2$ and $C/k<\varepsilon<\gamma$. For each $d$-dimensional
generalised arithmetic progression $P\subseteq\mathbb{Z}_{n}$, there exists a
collection $\mathcal{F}=\mathcal{F}_{k,m,\varepsilon}(P)$ of subsets of $P$
satisfying:

  1. (a)

For every $F\in\mathcal{F}$, we have

$|F|\leq C\varepsilon^{-1}\sqrt{m\log m}\quad\text{ and
}\quad|F\mathbin{\hat{+}}F|\geq\frac{(1-\gamma)(d+1)k}{2}.$ (6)

  2. (b)

For all $X\in\binom{P}{k}$ with $|X\mathbin{\hat{+}}X|\leq m$ and
$\varepsilon$-robust Freĭman dimension $d$, there exists $F\in\mathcal{F}$
such that $F\subseteq X$.

We will deduce this theorem from the following supersaturation result.

######  Theorem 2.2.

For every $0<\gamma<1$, there exists a constant ${c=c(\gamma)>0}$ such that,
for every sufficiently large set $X\subseteq\mathbb{Z}_{n}$, every
$d\in\mathbb{N}$ and every $0<\varepsilon<\gamma$, the following holds. If $X$
has $\varepsilon$-robust Freĭman dimension $d$ and $Y\subseteq X+X$ satisfies

$\big{|}\big{\\{}(x_{1},x_{2})\in X^{2}:x_{1}+x_{2}\not\in
Y\big{\\}}\big{|}\leq c\varepsilon|X|^{2},$ (7)

then $|Y|\geq(1-\gamma)(d+1)|X|/2$.

In words, whenever $Y\approx X+X$ in the sense of (7), then it also (almost)
satisfies the lower bound given by Freĭman’s lemma (Lemma 1.2), up to a factor
of 1/2. Once we have this theorem, the proof of Theorem 2.1 is substantially
simpler than usual for a similarly strong container theorem. In fact, it is
also the only part of the proof that we could omit by using the container
theorem for sumsets [9, Theorem 4.2]. The self-contained proof is so simple
that we include it here in the overview to motivate the usefulness of Theorem
2.2.

###### Proof of Theorem 2.1 assuming Theorem 2.2.

Our aim is to show that, for every $X\in\binom{P}{k}$ with
$|X\mathbin{\hat{+}}X|\leq m$ and $\varepsilon$-robust Freĭman dimension $d$,
there exists a subset $F\subseteq X$ such that (6) holds. We will show that a
$q$-random subset $F$ of $X$ satisfies the first inequality by a suitable
choice of $q$, and the second one via an application of Theorem 2.2 with
$Y=F\mathbin{\hat{+}}F$.

In order to apply Theorem 2.2 to $Y=F\mathbin{\hat{+}}F$, we need to show that
$Y$ satisfies (7). To this end, we will first prove that a random choice of
$F$ makes it unlikely for $F\mathbin{\hat{+}}F$ to miss any $y$ such that

$\rho_{X\mathbin{\hat{+}}X}(y)\geq\frac{2\varepsilon k^{2}}{Cm},$ (8)

where

$\rho_{X\mathbin{\hat{+}}X}(y)=\big{|}\big{\\{}(x_{1},x_{2})\in
X^{2}:x_{1}\neq x_{2},\,x_{1}+x_{2}=y\big{\\}}\big{|}$

is the number of pairs of distinct elements of $X$ that sum to a given $y\in
X\mathbin{\hat{+}}X$. Hereon, we will refer to the $y$ satisfying (8) as the
popular elements of $X\mathbin{\hat{+}}X$. We will take a $q$-random subset
where either

$q=\frac{C\sqrt{m\log m}}{2\varepsilon k}$ (9)

if the right-hand side is at most 1, and $q=1$ otherwise (a trivial case which
we will ignore).

Notice that we can upper bound the number of missing pairs by:

$\big{|}\\{(x_{1},x_{2})\in X^{2}:x_{1}+x_{2}\not\in
F\mathbin{\hat{+}}F\\}\big{|}\leq|X|+\sum_{y\in(X\mathbin{\hat{+}}X)\setminus(F\mathbin{\hat{+}}F)}\rho_{X\mathbin{\hat{+}}X}(y)$
(10)

where the term $|X|$ comes from the pairs $(x,x)$ for $x\in X$. Once we have
proved that $F\mathbin{\hat{+}}F$ contains all popular $y\in
X\mathbin{\hat{+}}X$, we will have an upper bound on
$\rho_{X\mathbin{\hat{+}}X}(y)$ for every
$y\in(X\mathbin{\hat{+}}X)\setminus(F\mathbin{\hat{+}}F)$. Inserting this into
(10), we deduce that the number of missing pairs is at most

$|X|+\sum_{y\in(X\mathbin{\hat{+}}X)\setminus(F\mathbin{\hat{+}}F)}\rho_{X\mathbin{\hat{+}}X}(y)<|X|+\frac{2\varepsilon
k^{2}}{Cm}|X\mathbin{\hat{+}}X|\leq c\varepsilon|X|^{2},$ (11)

if we take $C\geq 3/c$, where $c=c(\gamma)$ is the constant in Theorem 2.2,
since $|X|=k$, $|X\mathbin{\hat{+}}X|\leq m$ and $\varepsilon k>C$. The upper
bound in (11) is what we need to apply Theorem 2.2; doing so gives

$|F\mathbin{\hat{+}}F|\geq\frac{(1-\gamma)(\dim_{\mathrm{F}}(X)+1)k}{2},$

from which we can use our assumption that $\dim_{\mathrm{F}}(X)\geq d$ to
complete the proof.

It therefore only remains to prove our claim that with positive probability
$F$ contains all popular elements of $X\mathbin{\hat{+}}X$ while also being
sufficiently small. Notice that our choice of $F$ as a $q$-random subset of
$X$ implies, for each $y\in X\mathbin{\hat{+}}X$, that

$\mathbb{P}(y\not\in
F\mathbin{\hat{+}}F)=(1-q^{2})^{\rho_{X\mathbin{\hat{+}}X}(y)/2}$ (12)

because (i) each pair $(x_{1},x_{2})\in X^{2}$ that satisfies $x_{1}+x_{2}=y$
and $x_{1}\neq x_{2}$ is counted twice in $\rho_{X\mathbin{\hat{+}}X}(y)$ and
(ii) the probability that such a pair is chosen in $F$ is $q^{2}$.

Take $B_{F}$ to be the random variable counting the number of $y\in
X\mathbin{\hat{+}}X$ such that

$\rho_{X\mathbin{\hat{+}}X}(y)\geq\frac{2\varepsilon k^{2}}{Cm}\quad\text{ and
}\quad y\not\in F\mathbin{\hat{+}}F.$

By linearity of expectation and (12), we have

$\displaystyle\mathbb{E}[B_{F}]=\sum_{\begin{subarray}{c}y\in
X\mathbin{\hat{+}}X\\\ \rho_{X\mathbin{\hat{+}}X}(y)\geq 2\varepsilon
k^{2}/Cm\end{subarray}}\mathbb{P}(y\not\in F\mathbin{\hat{+}}F)\leq
m(1-q^{2})^{\varepsilon k^{2}/Cm}\leq m\exp\left(-\frac{\varepsilon
q^{2}k^{2}}{Cm}\right),$

where we used $|X\mathbin{\hat{+}}X|\leq m$ to bound the number of terms in
the sum.

Since $\varepsilon q^{2}k^{2}/(Cm)=(C/4\varepsilon)\log m$ by our choice (9)
of $q$, it follows by Markov’s inequality that

$\mathbb{P}(B_{F}>0)\leq m^{-1},$

where we also used that $\varepsilon<1$ and $C\geq 8$. Using Chernoff’s
inequality to bound the probability that $|F|>2qk$, we deduce that

$\mathbb{P}(|F|>2qk)+\mathbb{P}(B_{F}>0)<1,$

which proves that there exists a fingerprint $F\subseteq X$ satisfying (6), as
required. ∎

Before moving on with the overview, let us briefly discuss the robustness
property in Theorem 2.2. This condition may at first seem unnatural, but the
following simple construction shows that some form of robustness is necessary:
take $X$ to be the union of $d-1$ random points with a progression $P$, and
define $Y=P+P$. We have simultaneously _w.h.p_. that $\dim_{\mathrm{F}}(X)=d$,
$|Y|\approx 2|X|$ and the sum of almost all pairs of elements of $X$ are in
$Y$.

With Theorem 2.1 in hand, we can now check that for the family $\mathcal{F}$
of all sets satisfying (6), our requirements for the fingerprints $F$ are
satisfied. Recall that what we need from the size of the sumset is

$(ns)^{d+1}(1-p)^{|F\mathbin{\hat{+}}F|}\to 0,$

where $s=|P|$ and $d=\dim(P)$. Modern formulations of Freĭman’s theorem tells
us that we can take $s\leq\exp(\sigma^{1+o(1)})k$, which in our range of
$\sigma$ and $k$ corresponds to $n^{o(1)}$. However, we can only apply Theorem
2.1 to sets $X\subseteq P$ such that $\dim_{\mathrm{F}}(X)\geq\dim(P)$
(ignoring the robustness for the moment). Standard formulations of Freĭman’s
theorem only guarantee that $\dim(P)$ is at most $\sigma[X]$, which would not
be good enough for us.

Fortunately, Chang [10] proved a version of Freĭman’s theorem that guarantees
that $\dim(P)$ is at most $\dim_{\mathrm{F}}(X)$, at the cost of a weaker
bound on the size of $P$ as compared to the more recent results of Schoen [25]
and Sanders [24]. The impact of the suboptimal size of the progression is a
slight reduction in the range of $p$ for which our proof works.

######  Theorem 2.3 (Chang [10], see [19, Proposition 1.3]).

There exists $C^{\prime}>0$ such that for all finite subsets
$X\subseteq\mathbb{Z}$ with $|X|\geq 2$ and $\sigma[X]\leq\sigma$, there is a
$d$-dimensional generalised arithmetic progression $P$ such that $X\subseteq
P$,

$|P|\leq\exp\big{(}C^{\prime}\sigma^{2}(\log\sigma)^{3}\big{)}|X|$

and ${d\leq\dim_{\mathrm{F}}(X)}$.

Now, we can use the lower bound on $|F\mathbin{\hat{+}}F|$ given by Theorem
2.1 to obtain

$(1-p)^{|F\mathbin{\hat{+}}F|}\leq\exp\big{(}-(1-\gamma)(d+1)kp/2\big{)},$

which, choosing $k=(2+o(1))\log_{1/(1-p)}n$ (a little larger than $(2\log
n)/p$), is at most

$\exp\big{(}-(1+\gamma)(d+1)\log n\big{)}.$ (13)

Replacing this back in the previous equation, and recalling that $s=n^{o(1)}$,
thus yields

$(ns)^{d+1}(1-p)^{|F\mathbin{\hat{+}}F|}\leq n^{-\gamma}\to 0.$

The attentive reader may have noticed that Chang’s theorem is stated for
subsets of $\mathbb{Z}$ instead of $\mathbb{Z}_{n}$. To use it for subsets of
$\mathbb{Z}_{n}$, we will use instead a version of Green–Ruzsa’s theorem
(Freĭman’s theorem for Abelian groups) due to Cwalina and Schoen [12]. It does
not bound $\dim(P)\leq\dim_{\mathrm{F}}(X)$ directly, though, but it yields a
proper progression, which we can combine with a theorem by Tao and Vu [28] to
obtain what we need (see Corollary 8.4).

Moreover, it is not true that every $X$ has $\varepsilon$-robust Freĭman
dimension equal to $\dim_{\mathrm{F}}(X)$. This is not a problem, however,
since it is straightforward to prove (see Proposition 8.3) that every set $X$
has a large enough subset $X^{\prime}$ with $\varepsilon$-robust Freĭman
dimension $d^{\prime}\in\mathbb{N}$.

Finally, let us check that the size of $F$ given to us by Theorem 2.1 is
compatible with the range of $p$ in Theorem 1.1. To do so, we need to show
that, as $n\to\infty$,

${s\choose|F|}(1-p)^{|F\mathbin{\hat{+}}F|}\to 0.$

As we already know from (13) that the second term is at most $n^{-d}$, we need

${s\choose|F|}\leq s^{|F|}\leq\exp\big{(}C\varepsilon^{-1}(m\log m)^{1/2}\log
s\big{)}=n^{o(1)}.$ (14)

The second inequality in (14) follows from (6) in Theorem 2.1, while the third
is a consequence of our choice of $k$ and the bound on $s$ given by Theorem
2.3. Indeed, we have

$C\varepsilon^{-1}(m\log m)^{1/2}\log s\ll k^{3/4}=o(\log n),$ (15)

because $m\leq k^{1+\beta}$ for $X\in\mathcal{X}_{1}$, which implies that
$\log s\leq k^{3\beta}$, and we can take $\varepsilon=k^{-2\beta}$ and $C$ to
be a constant. Our choice of $\beta=1/40$ is therefore more than sufficient to
prove (15).

At this point, one might ask why we decided to keep track of the constant $C$
up to the final computation. Note that it is crucial that the value of $C$
does not increase too quickly with $d$ growing, since otherwise (15) would not
hold for large $d$. Recall that in the proof of Theorem 2.1, we took $C\approx
c^{-1}$. The constant $c$ is essentially given to us by our supersaturation
result and its value is tied to how many translates we need in our approximate
bound for Freĭman’s lemma (Theorem 1.3).

To see where the dependency of $c$ on the number of translates comes from,
consider the contrapositive of Theorem 2.2: if the set $Y$ is small, then it
misses many pairs $(x_{1},x_{2})\in X^{2}$. By Theorem 1.3, we can find a
small $T\subseteq X$ such that

$|X+T|-|Y|\geq\gamma(d+1)|X|.$

The pigeonhole principle then ensures us that there is some $x\in T$
satisfying

$\big{|}(X+x)\setminus Y\big{|}\geq\frac{\gamma(d+1)|X|}{|T|}=c|X|$

for $c=\gamma(d+1)/|T|$. Now, if we add the $c|X|$ pairs determined by
$(X+x)\setminus Y$ to our collection of missing pairs $(x_{1},x_{2})\in X^{2}$
such that $x_{1}+x_{2}\not\in Y$, remove $x$ from $X$ and repeat this
procedure $t$ times, we would have at least $c|X|t$ missing pairs in total.
Recalling that $X$ has $\varepsilon$-robust Freĭman dimension $d$, we can take
$t=\varepsilon|X|$ while maintaining $\dim_{\mathrm{F}}(X)\geq d$, and hence
obtain $c\varepsilon|X|^{2}$ missing pairs, as required.

The above sketch proof of Theorem 2.2 shows that to prove our supersaturation
result with $c$ being an absolute constant, we really need the size of $T$ to
be a linear function of $d$, as in Theorem 1.3. In fact, for (15), a bound of
the form $d^{O(1)}$ would suffice. Unfortunately, the theorem of Jing and
Mudgal (Theorem 1.4) gives a super-polynomial dependency on $d$. Nevertheless,
we use their result to prove Theorem 2.2 in the range $d=O(1)$.

The only missing part in this overview is a proof of Theorem 1.3 itself.
Instead of sketching it, we complete the picture with the (short) proof of its
weaker version in the next section.

##  3\. A simple proof of a weaker Freĭman’s lemma via few translates

This section is dedicated to proving a weaker form of Theorem 1.3. Although it
is not strong enough to prove the upper bound in our main theorem, it does
imply a weaker version where the constant $2$ in (1) is replaced by a $6$. The
deduction of this weaker result is the same as that of Theorem 1.1 (see
Sections 7 and 8) simply replacing Theorem 1.3 by Theorem 3.1.

######  Theorem 3.1.

Let $d,r\in\mathbb{N}$ and let $X\subseteq\mathbb{R}^{d}$ be a finite set with
$\operatorname{rank}(X)\geq r$. There exists a set $T\subseteq X$ such that
$|T|\leq r/2+1$ and

$|X+T|\geq\frac{r|X|}{6}.$

The idea of the proof is to add elements of $X$ to $T$ one by one, picking in
each step a new translate that adds a substantial number of new elements to
the sumset. This suggests a greedy argument, picking $x\in X\setminus T$ that
increases the size of the sumset the most. However, it is not clear how to
show that we can make substantial progress for a sufficient number of steps.
Previous arguments, such as the one by Fox, Luo, Pham, and Zhou [13, Theorem
1.1], show that if progress stops, then $X$ must have small doubling; as we
must handle polynomially large $\sigma[X]$, such strategies do not work in our
case. Instead, we adopt a variation of this idea that incorporates the
geometry of the set, allowing us to reach conclusions that do not rely on the
doubling of the set and depend only on its rank.

Roughly speaking, in the proof of Proposition 3.2 below, we will show that we
can add a new element to $T$ so that it increases the size of $X+T$ by a
factor proportional to $|X\setminus\operatorname{span}(T)|$. Notice that, as
long as $|T|<\operatorname{rank}(X)$, we can take a non-trivial step.

Now, if we have enough steps that add $|X|/3$ elements to the sumset, then
after $r/2$ steps we will have both the bound for the sumset and for $|T|$ in
Theorem 3.1. Otherwise, as we will show that every step makes at least
$|X\setminus\operatorname{span}(T)|/2$ “progress”, it follows that, after the
last “good” step, we must have $|X\cap\operatorname{span}(T)|\geq|X|/3$. In
this scenario, we define

$X^{*}=X\cap\operatorname{span}(T)\qquad\text{ and }\qquad
X^{\prime}=X\setminus\operatorname{span}(T),$

and observe that

$\operatorname{rank}(X^{\prime})\geq\operatorname{rank}(X)-\operatorname{rank}(T)\geq
r-r/2=r/2,$ (16)

since $|T|\leq r/2$. At this point, we now discard our old $T$ and greedily
choose elements of a new set of translates $Z\subseteq X^{\prime}$ each
increasing the rank of $X^{*}\cup Z$ by one. Each new element that we add
yields a disjoint, translated copy of $X^{*}$ in the sumset. We then obtain

$|X+Z|\geq|X^{*}+Z|=\frac{r|X^{*}|}{2}\geq\frac{r|X|}{6},$

because, by (16), we can greedily add $r/2$ elements to $Z$, and
$|X^{*}|\geq|X|/3$.

We proceed by formalizing the notion that either the greedy argument suffices,
or a significant part of $X$ lies in the span of the elements already in $T$.
The version we state below is more general than we need to prove Theorem 3.1
because we will reuse it when proving Theorem 1.3.

######  Proposition 3.2.

Let $d,r\in\mathbb{N}$, let $\gamma>0$ and let $X\subseteq\mathbb{R}^{d}$ be a
finite set with $\operatorname{rank}(X)\geq r$. If $T\subseteq\mathbb{R}^{d}$
satisfies $0\in T$, $\operatorname{rank}(T)<r$ and
$|X\cap\operatorname{span}(T)|\leq\gamma|X|$, then there exists an element
$x_{*}\in X$ such that

$\big{|}X+\big{(}T\cup\\{x_{*}\\}\big{)}\big{|}\geq|X+T|+\frac{(1-\gamma)|X|}{2}.$
(17)

The key idea here is to find a co-dimension 1 hyperplane $\mathcal{H}$ which
intersects $X$ exactly in $X\cap\operatorname{span}(T)$. We can find such a
hyperplane because $X$ is finite and
$\operatorname{rank}(T)<\operatorname{rank}(X)$. Note that the two open half-
spaces defined by $\mathcal{H}$ induce a partition $X^{\prime}=X_{+}\cup
X_{-}$. Without loss of generality, we assume that $|X_{+}|\geq|X_{-}|$, and
our goal is now to add, for each point in $X_{+}$, a new element to the
sumset. To achieve this, we let $u$ be a normal vector of $\mathcal{H}$,
choose $y_{+}\in X_{+}$ to maximise $\left\langle y_{+},u\right\rangle$, and
observe that $y_{+}+X_{+}$ is disjoint from $X+T$.

###### Proof.

First, choose a vector $u\in\mathbb{R}^{d}$ to be the normal of the hyperplane
$\mathcal{H}$ discussed above. It should satisfy the following properties

  1. (1)

$u\neq 0$,

  2. (2)

${\left\langle z,u\right\rangle=0}$, for all $z\in\operatorname{span}(T)$, and

  3. (3)

$\left\langle z,u\right\rangle\neq 0$, for all $z\in
X\setminus\operatorname{span}(T)$.

There is a $u$ satisfying items 1 and 2 since $0\in T$ and
$\operatorname{rank}(T)<r$. We can furthermore find a $u$ for which item 3
also holds because there are only finitely many elements in
$X\setminus\operatorname{span}(T)$, as $X$ itself is finite.

We partition $X=X_{+}\cup X_{*}\cup X_{-}$ according to the position of its
elements relative to the hyperplane defined by $\left\langle
x,u\right\rangle=0$, i.e.

$\displaystyle X_{+}=\\{x\in X:\left\langle x,u\right\rangle>0\\},$
$\displaystyle X_{*}=\\{x\in X:\left\langle x,u\right\rangle=0\\},$
$\displaystyle X_{-}=\\{x\in X:\left\langle x,u\right\rangle<0\\}.$

Assume without loss of generality that $|X_{+}|\geq|X_{-}|$ by swapping the
sign of $u$ if necessary, and take $y_{+}\in X_{+}$ to be a maximiser of
$f(y)=\left\langle y,u\right\rangle$.

We claim that $X_{+}+y_{+}$ is disjoint from $X+T$. In fact, if we let $a\in
X_{+},b\in X$ and $c\in T$, then:

$\displaystyle\left\langle a+y_{+},u\right\rangle$ $\displaystyle>\left\langle
y_{+},u\right\rangle,$ $\displaystyle\text{as }a\in X_{+},$
$\displaystyle\geq\left\langle b,u\right\rangle,$ $\displaystyle\text{by the
maximality of }y_{+},$ $\displaystyle=\left\langle b+c,u\right\rangle,$
$\displaystyle\text{as we chose }u\text{ with }c\perp u.$

Therefore, if $|X_{+}|\geq(1-\gamma)|X|/2$, we can pick $x_{*}=y_{+}$ and
prove the proposition:

$\displaystyle|X+(T\cup\\{x_{*}\\})|$ $\displaystyle\geq|X+T|+|X_{+}+x_{*}|$
$\displaystyle\geq|X+T|+\frac{(1-\gamma)|X|}{2}.$

Otherwise, since we took $|X_{+}|\geq|X_{-}|$ and $X_{+}\cup X_{*}\cup X_{-}$
partition $X$, we have

$|X_{*}|=|X|-|X_{-}|-|X_{+}|>\gamma|X|.$ (18)

By our choice of $u$ and the definition of $X_{*}$, we have
$X_{*}=X\cap\operatorname{span}(T)$, which, by (18), contradicts our
assumption that $|X\cap\operatorname{span}(T)|\leq\gamma|X|$. ∎

The 1-dimensional perspective we took in this proof suggests that instead of
adding a single maximiser $y_{+}$ to $T$ at each step, we should pick both the
maximiser $y_{+}$ and the minimiser $y_{-}$. Unfortunately, if we add
$\\{y_{+},y_{-}\\}$ to $T$, then we could increase $\operatorname{rank}(T)$ by
two instead of one, causing the greedy argument to run for only half as many
steps.

We need the following simple lemma to handle the case when
$|X\cap\operatorname{span}(T)|$ is large.

######  Lemma 3.3.

Let $d,r,s\in\mathbb{N}$, let $\gamma>0$ and let $X\subseteq\mathbb{R}^{d}$ be
a finite set with $\operatorname{rank}(X)\geq r$. If $X_{*}\subseteq X$ with
$\operatorname{rank}(X_{*})<s$, then there exists a set $Z\subseteq X\setminus
X_{*}$ such that

$|X_{*}+Z|\geq(r-s)|X_{*}|$

and $|Z|\leq r-s$.

###### Proof.

First, note that for any set $S\subseteq\mathbb{R}^{d}$ such that
$\operatorname{rank}(S)<s$, we have
$\operatorname{rank}(\operatorname{span}(S))\leq s$. That is, taking the
$\operatorname{span}$ of a set that does not contain $0$ may increase its rank
by 1.

We will construct $Z=\\{z_{1},\ldots,z_{r-s}\\}\subseteq X\setminus X_{*}$ one
element at a time, also defining

$Z_{i}=\\{z_{1},\ldots,z_{i}\\}\quad\text{ and }\quad
W_{i}=\operatorname{span}(X_{*}\cup Z_{i})$

for $i\in\\{0,\ldots,r-s\\}$. Notice that if $i<r-s$, then
$\operatorname{rank}(W_{i})\leq s+i<r$, by our assumption on $X^{*}$ and the
definition of $W_{i}$. Therefore, there exists $z_{i+1}\in X\setminus W_{i}$,
as $\operatorname{rank}(X)\geq r$. Since $X^{*}\subseteq W_{i}$, this implies
that $X^{*}+z_{i+1}$ and $W_{i}$ are disjoint, and hence that $X^{*}+z_{i+1}$
is disjoint from $X^{*}+Z_{i}$. This readily implies the lemma because

$|X_{*}+Z|=\sum_{i=1}^{r-s}|X_{*}+z_{i}|=(r-s)|X_{*}|,$

where in the first equality we repeatedly used that $X_{*}+z_{i+1}$ and
$X_{*}+Z_{i}$ are disjoint. ∎

The proof of Theorem 3.1 now follows easily from Proposition 3.2 and Lemma
3.3:

###### Proof of Theorem 3.1.

We may assume that $0\in X$; notice that this translation does not change
$\operatorname{rank}(X)$. First, we construct sets
$T_{i}=\\{x_{0},\ldots,x_{i}\\}\subseteq X$ by choosing $x_{0}=0$ and
$x_{i+1}$ as given by Proposition 3.2. In details, let $t$ be the first index
for which

$|X\cap\operatorname{span}(T_{t})|>\frac{|X|}{3}.$ (19)

Note that while (19) does not hold, we have
$\operatorname{rank}(T_{i})<\operatorname{rank}(X)$ since $T_{i}\subseteq X$.
We may therefore apply Proposition 3.2 to $T_{i}$ with $\gamma=1/3$ to define
$x_{i}$, which then implies that

$|X+T_{i}|\geq\frac{|T_{i}|\,|X|}{3}=\frac{(i+1)|X|}{3}$ (20)

for all $i\leq t$. Hence, if $t\geq r/2$, then, by (20), we have

$|X+T_{t}|\geq\frac{(t+1)|X|}{3}\geq\frac{r|X|}{6},$

and taking $T=T_{t}$ concludes the proof. We may therefore assume that
$t<r/2$.

In this case, we want to apply Lemma 3.3 with
$X_{*}=X\cap\operatorname{span}(T_{t})$ and $s=r/2$. Note that, as
$\operatorname{rank}(T_{t})\leq t$ and $0\in T_{t}$, we have

$\operatorname{rank}(X_{*})\leq\operatorname{rank}(\operatorname{span}(T_{t}))\leq
t<r/2,$

where in the last inequality we used our assumption that $t<r/2$. This
application yields a set $Z\subseteq X\setminus X_{*}$ such that $|Z|\leq
r-s=r/2$ and

$\displaystyle|X+Z|$ $\displaystyle\geq|X_{*}+Z|$ $\displaystyle\text{ because
}X_{*}\subseteq X,$ $\displaystyle\geq\frac{r|X_{*}|}{2}$ $\displaystyle\text{
by \lx@cref{creftypecap~refnum}{stmt:disjoint-translates-with-X*}},$
$\displaystyle\geq\frac{r|X|}{6}$ $\displaystyle\text{ since
}|X_{*}|\geq|X|/3\text{ by \eqref{eq:greedy-condition-for-weaker-freiman}}.$

Taking $T=Z$ concludes the proof. ∎

##  4\. Improving the bound for Freĭman’s lemma via few-translates

To obtain the sharp upper bound for $\alpha(\Gamma_{p})$, the bound $|X+T|\geq
r|X|/6$ is not enough; we need at least $|X+T|\geq(1-5\gamma)(r+1)|X|/2$ for
small $\gamma>0$. In this section, we describe the overall approach and state
the intermediate results we require to improve the bound. Once we have stated
these results, we will show that assuming them is sufficient to prove Theorem
1.3 – this will motivate their statements, since neither they nor their proofs
are straightforward. We will prove that these results hold in subsequent
sections.

To discuss the methods that we will use to improve the bound, it will be
convenient to first make some definitions.

######  Definition 4.1.

For finite sets $X,W\subseteq\mathbb{R}^{d}$, we define

$Z(X,W)=\Pi_{W^{\perp}}(X),$

where $\Pi_{U}(V)$ denotes the orthogonal projection of $V$ onto $U$. We also
partition $\mathbb{R}^{d}$ into equivalence classes in that projection,
denoting these222To avoid confusion between the equivalence class $[z]$ for
$z\in\mathbb{R}^{d}$ and $[m]=\\{1,\ldots,m\\}$ for $m\in\mathbb{N}$, we avoid
using the latter notation. by

$[z]_{W}=\big{\\{}x\in\mathbb{R}^{d}:\Pi_{W^{\perp}}(x)=z\big{\\}},$

and partition X into equivalence classes in the same way:

$\llbracket z\rrbracket_{W,X}=[z]_{W}\cap X.$

It will be convenient to omit the dependency of those definitions on $X$ and
$W$ whenever these sets are clear from context, leaving us with the notation
$Z,[z],\llbracket z\rrbracket$. We also refer to $[z]$ as a “fibre”, and say
that a fibre $[z]$ is “empty” if $z\not\in Z$.

The start of the proof follows the same idea as in Section 3: to obtain
$T_{i+1}$ from $T_{i}$, at each step we add the element provided by
Proposition 3.2. We do this for $t$ steps, where $t$ is the first index for
which ${|X\cap\operatorname{span}(T_{t})|>\gamma|X|}$. If $t\geq r$, then, by
Proposition 3.2, we have $|X+T_{t}|\geq(1-\gamma)(t+1)|X|/2$, and we are done.
Otherwise, we define

$T^{*}=T_{t-1}\qquad\text{ and }\qquad W=\operatorname{span}(T_{t}),$ (21)

and we look into the set of non-empty fibres $Z=Z(X,W)$. Notice that $W$ is
neither $\mathbb{R}^{d}$ nor $\\{0\\}$ since $0<t<r$. The rest of the argument
is divided into two different cases.

If there are many distinct non-empty fibres in $Z=\\{z_{1},\ldots,z_{m}\\}$,
then we use the following generalisation of Lemma 3.3. Whereas for that
previous result we needed one point per dimension, in Proposition 4.2 we take
one point $y_{i}\in\llbracket z_{i}\rrbracket$ per non-empty fibre to be our
set $T$, and show that such a choice yields disjoint translates $y_{i}+X_{*}$
for $X_{*}=X\cap W$.

######  Proposition 4.2.

Let $d,r\in\mathbb{N}$, let $\gamma>0$, and let $X\subseteq\mathbb{R}^{d}$ be
a finite set with $\operatorname{rank}(X)\geq r$. If
$W\subseteq\mathbb{R}^{d}$ is such that $|X\cap W|\geq\gamma|X|$ and
$|Z|\geq(r+1)/\gamma$, where $Z=Z(X,W)$, then there exists $T\subseteq X$ such
that

$|X+T|\geq(r+1)|X|$

and $|T|=(r+1)/\gamma$.

###### Proof.

Define $m=(r+1)/\gamma$. Take $\\{z_{1},\ldots,z_{m}\\}\subseteq Z$ and, for
each $z_{i}$, pick some arbitrary $y_{i}\in\llbracket z_{i}\rrbracket$. Note
that $X\cap W\subseteq\llbracket 0\rrbracket$. As we have chosen
$y_{i}\in[z_{i}]$, we have $\llbracket 0\rrbracket+y_{i}\subseteq[z_{i}].$
Doing the same with $i\neq j$ shows that

$\big{(}\llbracket 0\rrbracket+y_{i}\big{)}\cap\big{(}\llbracket
0\rrbracket+y_{j}\big{)}\subseteq[z_{i}]\cap[z_{j}]=\emptyset.$ (22)

We can therefore conclude that taking $T=\\{y_{1},\ldots,y_{m}\\}\subseteq X$
satisfies

$\displaystyle|X+T|$ $\displaystyle\geq\big{|}\llbracket 0\rrbracket+T\big{|}$
$\displaystyle\text{as }\llbracket 0\rrbracket\subseteq X\text{ by
definition},$ $\displaystyle\geq\sum_{i=1}^{m}\big{|}\llbracket
0\rrbracket+y_{i}\big{|}$ $\displaystyle\text{by \eqref{eq:y_i-y_j-
disjoint}},$ $\displaystyle\geq m\gamma|X|$ $\displaystyle\text{as
}\big{|}\llbracket 0\rrbracket\big{|}\geq\gamma|X|,\text{ by assumption,}$
$\displaystyle=(r+1)|X|,$

as required. ∎

The case when there are few non-empty fibres, i.e. $Z=Z(X,W)$ is small, is
more complex. Letting $r_{W}=\operatorname{rank}(W)$ and recalling (21), we
have

$|X+T^{*}|\geq(1-\gamma)\frac{(r_{W}+1)|X|}{2}.$

Therefore, to obtain a final set of translates $T$ such that
$|X+T|\geq(1-5\gamma)(r+1)|X|/2$, we need to find a set $T^{\prime}$ that
roughly satisfies

$|X+T^{\prime}|\geq\frac{(r-r_{W})|X|}{2}.$ (23)

To combine $T^{*}$ and $T^{\prime}$, though, we must take care not to count
overlaps between the sumsets $X+T^{\prime}$ and $X+T^{*}$ more than once.

The content of the next proposition shows that choosing $T^{\prime}$ as
discussed above is possible. It says that we can choose a $T^{\prime}$ which
almost attains (23) while avoiding not only $X+T^{*}$, but the whole of
$X+\llbracket 0\rrbracket$ – recall that $T^{*}\subseteq W\cap
X\subseteq\llbracket 0\rrbracket$.

######  Proposition 4.3.

Let $d,r,r_{W}\in\mathbb{N}$, $\eta>0$, and let $X\subseteq\mathbb{R}^{d}$ be
a finite set with $\operatorname{rank}(X)\geq r$. Let also
$W\subseteq\mathbb{R}^{d}$ be a subspace with dimension $r_{W}$, and
$Z=Z(X,W)$. If $\big{|}\llbracket z\rrbracket\big{|}\leq\eta|X|$ for every
$z\in Z\setminus\\{0\\}$, then there exists $T^{\prime}\subseteq X$ such that

$\Big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}\geq\frac{r-r_{W}}{2}\Big{(}\big{|}X\big{|}-\big{|}\llbracket
0\rrbracket\big{|}\Big{)}-\eta|Z||X|$ (24)

and $|T^{\prime}|\leq|Z|$.

To gain some intuition for why Proposition 4.3 is true, consider the
following. Applying Freĭman’s lemma in the projected world $W^{\perp}$, if we
could obtain a lower bound depending on $|X|$, instead of $|Z|$ – which is
what we actually get – then we would be done. Notice, however, that this naive
application considers every non-empty fibre $\llbracket z\rrbracket$ as a
single element to avoid repeated counts. That is, for each $z_{1}+z_{2}\in
Z+Z$, this approach counts only $x+y$ for a single choice of $x\in\llbracket
z_{1}\rrbracket$ and $y\in T^{\prime}\cap\llbracket z_{2}\rrbracket$.

In the proof of Proposition 4.3, we will show that we can instead consider
$\llbracket z_{1}\rrbracket+y$ and not overcount. To achieve that, we assign
to each $z\in Z$ a weight that encodes the size of the corresponding fibre
$\llbracket z\rrbracket$, and incorporate this weight into the proof of
Freĭman’s lemma in the projected world. Although considering $\llbracket
z_{1}\rrbracket+y$ is still not enough to replace $|Z|$ with $|X|$ in the
bound, we can crucially choose $z_{1},z_{2}\in Z$ whichever way we want, as
long as $y\in\llbracket z_{2}\rrbracket$. We therefore choose the
representation that maximises $\big{|}\llbracket z_{1}\rrbracket\big{|}$ and
show that this modification is enough to obtain the bound in Proposition 4.3.

The above discussion overlooks the removal of the zero fibre from the sumset,
i.e. it gives a lower bound for $|X+T^{\prime}|$ instead of one for
$\big{|}(X+T^{\prime})\setminus(X+\llbracket 0\rrbracket)\big{|}$. To
incorporate it, we must take into account our choice maximizing
$\big{|}\llbracket z_{1}\rrbracket\big{|}$, which imposes the (technical)
requirement that every non-zero fibre has size at most $\eta|X|$. As this is
not always the case, in order to apply Proposition 4.3, we will change $W$
slightly to make it so: we will “add” to $W$ the large non-zero fibres until
we have $\big{|}\llbracket z\rrbracket\big{|}\leq\eta|X|$ for all remaining
$z\in Z$. As we will do this economically, using this new $W$ will not hurt
our bound too much.

Nevertheless, combining $T^{\prime}$ and $T^{*}$ had another unanticipated
cost: it incurred a negative $(r-r_{W})\big{|}\llbracket 0\rrbracket\big{|}/2$
term in the bound of Proposition 4.3. The following proposition shows that a
simple change suffices to offset this loss: we add two extra points from each
non-empty fibre to our final $T$.

######  Proposition 4.4.

Let $d\in\mathbb{N}$, and let $X\subseteq\mathbb{R}^{d}$ be a finite set. For
every $W\subseteq\mathbb{R}^{d}$ and $u^{*}\in\mathbb{R}^{d}$, there is
$T^{\prime\prime}\subseteq X$ satisfying $|T^{\prime\prime}|\leq 2|Z|$ and

$\Big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\Big{|}\geq|Z|\Big{(}\big{|}\llbracket
0\rrbracket\big{|}-\big{|}\llbracket 0\rrbracket_{*}\big{|}\Big{)},$

where $Z=Z(X,W)$ and $\llbracket 0\rrbracket_{*}=\\{x\in\llbracket
0\rrbracket:\left\langle x,u^{*}\right\rangle=0\\}$.

It is not immediate that Proposition 4.4 is really enough to make up for what
we lost in Proposition 4.3, as we are removing $X+\llbracket 0\rrbracket_{*}$
instead of $X+T^{*}$, and $\llbracket 0\rrbracket_{*}$ is determined by $W$
and $u^{*}$. What we need is that, for our choice of $u^{*}$, both
$\big{|}\llbracket 0\rrbracket_{*}\big{|}\leq\gamma|X|$ and
$T_{t-1}=T^{*}\subseteq\llbracket 0\rrbracket_{*}$. This condition, combined
with the following observation, is enough to prove Theorem 1.3. The proof of
the observation is a simple (but slightly tedious) manipulation of set
relations.

######  Observation 4.5.

For every $T^{\prime},T^{\prime\prime}\subseteq X$, we have

$\big{|}\big{(}X+\hat{T}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\big{|}\geq\big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\big{|}+\big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\big{|}$ (25)

where $\hat{T}=T^{\prime}\cup T^{\prime\prime}$.

###### Proof.

Note first that $\llbracket 0\rrbracket+T^{\prime\prime}$ is a subset of
$X+\hat{T}$: this follows easily from

$\llbracket 0\rrbracket\subseteq X\quad\text{ and }\quad
T^{\prime\prime}\subseteq\hat{T}.$

We therefore have

$\big{|}X+\hat{T}\big{|}\geq|S|+\big{|}\llbracket
0\rrbracket+T^{\prime\prime}\big{|}$ (26)

where $S=\big{(}X+T^{\prime}\big{)}\setminus\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}$, and moreover,

$\big{|}(X+\hat{T})\setminus(X+\llbracket
0\rrbracket_{*})\big{|}\geq\big{|}S\setminus(X+\llbracket
0\rrbracket_{*})\big{|}+\big{|}(\llbracket
0\rrbracket+T^{\prime\prime})\setminus(X+\llbracket 0\rrbracket_{*})\big{|}.$
(27)

As the last term in (27) already matches what appears in (25), the proof is
reduced to showing that

$\big{|}S\setminus(X+\llbracket
0\rrbracket_{*})\big{|}\geq\big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\big{|},$ (28)

where, recall,

$S\setminus(X+\llbracket
0\rrbracket_{*})=\big{(}X+T^{\prime}\big{)}\setminus\big{(}(\llbracket
0\rrbracket+T^{\prime\prime})\cup(X+\llbracket 0\rrbracket_{*})\big{)}.$

It is enough, therefore, to prove that

$\llbracket 0\rrbracket+T^{\prime\prime}\subseteq\llbracket
0\rrbracket+X\quad\text{ and }\quad X+\llbracket 0\rrbracket_{*}\subseteq
X+\llbracket 0\rrbracket.$

Both inclusions are trivial, as $T^{\prime\prime}\subseteq X$ by assumption,
and $\llbracket 0\rrbracket_{*}\subseteq\llbracket 0\rrbracket$ by definition.
∎

We are now ready to put the pieces together and prove Theorem 1.3.

###### Proof of Theorem 1.3 assuming Propositions 4.4 and 4.3.

By translating if necessary, we may assume that $0\in X$; note that this does
not change $\operatorname{rank}(X)$. As in the proof of the weaker version,
Theorem 3.1, we start by defining $T_{0}=\\{0\\}$: observe that
$\operatorname{rank}(T_{0})=0$ and

$|X+0|=|X|.$ (29)

The next steps consist of taking $T_{i+1}=T_{i}\cup\\{x_{i+1}\\}$, where
$x_{i+1}\in X$ is defined to be the $x^{*}$ given by Proposition 3.2 applied
to $T_{i}$. We can do so as long as
$|X\cap\operatorname{span}(T_{i})|<\gamma|X|$ and $i<r$, because $|T_{i}|=i+1$
implies that $\operatorname{rank}(T_{i})\leq i$. We also stop this process for
the first $t$ such that

$|X\cap\operatorname{span}(T_{t})|\geq\gamma|X|.$ (30)

By (29) and our choice of $x_{i+1}$ via Proposition 3.2, we have, for all
$i\leq t$,

$|X+T_{i}|\geq|X|+(1-\gamma)\frac{i|X|}{2}\geq(1-\gamma)\frac{(i+2)|X|}{2},$
(31)

and $|T_{i}|\leq i+1$.

Now, if $t\geq r$, then we can take $T=T_{t}$, and we have completed the proof
by (31). Otherwise, we may assume that $t<r$ and define
$W_{1}=\operatorname{span}(T_{t}).$ We would like to use $W_{1}$ for the rest
of the proof, but Proposition 4.3 requires that all non-zero fibres have size
at most $\eta|X|$. To continue, then, we need to define a subspace $W$ such
that for every $z\in Z(W,X)\setminus\\{0\\}$ and given $\eta>0$,

$\big{|}\llbracket z\rrbracket_{W,X}\big{|}\leq\eta|X|.$

We will do so by iteratively projecting these large fibres onto the 0 fibre
until none remain. With foresight, we set $\eta=\gamma^{2}$. Formally, our
process is:

  1. (1)

Start with $\ell=1$ and $W_{1}=\operatorname{span}(T_{t})$.

  2. (2)

If there exists $z_{\ell}\in Z(W_{\ell},X)\setminus\\{0\\}$ such that
$\big{|}\llbracket z_{\ell}\rrbracket\big{|}\geq\eta|X|$, then we let

$W_{\ell+1}=\operatorname{span}(W_{\ell}\cup\\{z_{\ell}\\}).$

  3. (3)

If there is no such $z_{\ell}$, we stop with output $W_{\ell}$.

A simple and important observation is that $\ell\leq 1/\eta$, since
$\eta<\gamma$ and

$|X|\geq|W_{\ell}\cap X|\geq\ell\eta|X|.$

Noting that $\dim(W_{1})\leq t$, since $|T_{t}|\leq t+1$ and $0\in T_{t}$, it
follows that

$r_{W}:=\dim(W_{\ell})\leq\dim(W_{1})+1/\eta\leq t+1/\eta.$ (32)

Take $W$ to be the output of the above process. Moreover, let $Z=Z(W,X)$ and
divide the rest of the proof into two cases depending on $|Z|$. The first case
is if $|Z|\geq(r+1)/\gamma$. Here, we claim that applying Proposition 4.2
completes the proof. The set $T\subseteq X$ provided by this application
satisfies

$|X+T|\geq(r+1)|X|\geq(1-5\gamma)\frac{(r+1)|X|}{2},$

and

$|T|=\frac{r+1}{\gamma}\leq\frac{4(r+1)}{\gamma},$

as required.

It remains to deal with the other case, and we may thus assume that
$|Z|<(r+1)/\gamma$. In this scenario, our set $T$ will be the union of three
sets: the second to last set $T_{t-1}$, the set $T^{\prime}$ given by
Proposition 4.3, and $T^{\prime\prime}$, the output of Proposition 4.4 for a
suitable choice of $u^{*}\in\mathbb{R}^{d}$. Note that it consists of few
translates:

$|T|\leq|T_{t-1}|+|T^{\prime}|+|T^{\prime\prime}|\leq
t+|Z|+2|Z|\leq\frac{4(r+1)}{\gamma},$

where the last inequality follows from our assumptions that $t<r$ and
$|Z|<(r+1)/\gamma$. It remains to show that $X+T$ has the appropriate size.

First, we separate the contributions of $T_{t-1}$ and $\hat{T}=T^{\prime}\cup
T^{\prime\prime}$ to the sumset

$|X+T|\geq|X+T_{t-1}|+\big{|}\big{(}X+\hat{T}\big{)}\setminus\big{(}X+T_{t-1}\big{)}\big{|},$
(33)

and we would like to apply Observation 4.5 to bound the second term in the
right-hand side. To do this, we need to show that $T_{t-1}\subseteq\llbracket
0\rrbracket_{*}$ for some $u^{*}\in\mathbb{R}^{d}$, as that would imply

$\big{(}X+\hat{T}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\subseteq\big{(}X+\hat{T}\big{)}\setminus\big{(}X+T_{t-1}\big{)}.$
(34)

Besides $T_{t-1}\subseteq\llbracket 0\rrbracket_{*}$, our choice of $u^{*}$
will also need to satisfy

$\big{|}\llbracket 0\rrbracket_{*}\big{|}<\gamma|X|.$ (35)

To achieve that, we define the subspace $W_{0}=\operatorname{span}(T_{t-1})$
and claim that we can pick $u^{*}\in\mathbb{R}^{d}$ such that

$\llbracket 0\rrbracket_{*}=\\{x\in\llbracket 0\rrbracket:\left\langle
x,u^{*}\right\rangle=0\\}=X\cap W_{0}.$ (36)

As we have stopped the greedy process at $t$, we must have $|X\cap
W_{0}|<\gamma|X|$, so this choice also satisfies (35). We can choose $u^{*}\in
W_{0}^{\perp}$ satisfying (36) because $X$ is finite and

$\dim(W_{0})\leq t<r\leq d,$

since $|T_{t-1}|\leq t$ and $0\in T_{t-1}$. Notice that this choice of $u^{*}$
mimics that of $u$ in the proof of Proposition 3.2.

With this choice of $u^{*}$, we have $T_{t-1}\subseteq\llbracket
0\rrbracket_{*}$, as required, and so combining (34) with Observation 4.5
yields, in (33),

$|X+T|\geq|X+T_{t-1}|+\big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\big{|}+\big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\big{|}$ (37)

for $T=T_{t-1}\cup T^{\prime}\cup T^{\prime\prime}$, and $T^{\prime}$ and
$T^{\prime\prime}$ as given by Proposition 4.3 and Proposition 4.4,
respectively. As $T^{\prime}$ originates from Proposition 4.3, we have

$\big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\big{|}\geq\frac{(r-r_{W})}{2}\big{(}|X|-\big{|}\llbracket
0\rrbracket\big{|}\big{)}-\eta|Z||X|,$ (38)

where, recall, $r_{W}\leq t+1/\eta$, by (32). Moreover, by Proposition 4.4, we
have

$\big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\big{|}\geq|Z|\big{(}\big{|}\llbracket
0\rrbracket\big{|}-\big{|}\llbracket 0\rrbracket_{*}\big{|}\big{)},$ (39)

which, by (35), implies that

$\big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\big{|}\geq|Z|\big{(}\big{|}\llbracket
0\rrbracket\big{|}-\gamma|X|\big{)}.$ (40)

Recall that, by (31), we have

$|X+T_{t-1}|\geq(1-\gamma)\frac{(t+1)|X|}{2},$

which, replaced alongside (38) and (40) in (37), yields

$\displaystyle|X+T|$ $\displaystyle\geq(1-\gamma)\frac{(t+1)}{2}|X|$
$\displaystyle+\frac{(r-r_{W})}{2}\Big{(}|X|-\big{|}\llbracket
0\rrbracket\big{|}\Big{)}$ (41) $\displaystyle-\eta|Z||X|$
$\displaystyle+|Z|\Big{(}\big{|}\llbracket
0\rrbracket\big{|}-\gamma|X|\Big{)}.$ (42)

The rest of the proof is dedicated to showing that this expression is at least
the bound we need.

To this end, observe that

$|Z|\geq\operatorname{rank}(Z)\geq\operatorname{rank}(X)-\operatorname{rank}(W)\geq
r-r_{W}.$ (43)

Another important observation is that

$\big{|}\llbracket 0\rrbracket\big{|}\geq|X\cap W_{1}|\geq\gamma|X|,$ (44)

since $X\cap W_{1}\subseteq\llbracket 0\rrbracket$.

It follows from (43) and (44) that the sum of (41) and (42) is at least

$\frac{r-r_{W}}{2}\Big{(}|X|-\big{|}\llbracket
0\rrbracket\big{|}\Big{)}+|Z|\Big{(}\big{|}\llbracket
0\rrbracket\big{|}-\gamma|X|\Big{)}\geq(1-\gamma)\frac{(r-r_{W})}{2}|X|.$ (45)

Replacing (45) in our lower bound for the size of $X+T$, we obtain

$|X+T|\geq(1-\gamma)\frac{(t+1)}{2}|X|+(1-\gamma)\frac{(r-r_{W})}{2}|X|-\eta|Z||X|$

and using that $r_{W}\leq t+1/\eta$ by (32), yields

$|X+T|\geq(1-\gamma)\frac{(r+1)}{2}|X|-\frac{(1-\gamma)}{2\eta}|X|-\eta|Z||X|.$
(46)

It is now enough to determine that

$(1-\gamma)\frac{1}{2\eta}+\eta|Z|\leq 2\gamma(r+1)$ (47)

as replacing it in (46) gives the desired bound:

$|X+T|\geq(1-5\gamma)\frac{r+1}{2}|X|.$

To obtain (47), observe that

$\eta|Z|\leq\gamma(r+1)$ (48)

follows from our choice of $\eta=\gamma^{2}$ and our assumption that, in the
current case, ${|Z|\leq(r+1)/\gamma}$. Moreover, the following holds

$\frac{1}{2\eta}<\gamma(r+1)$ (49)

since $\gamma^{3}r\geq 1$ by assumption. The proof is complete by substituting
(48) and (49) in (47). ∎

##  5\. Offsetting the loss of the zero fibre: proof of Proposition 4.4

As we remarked in the previous section, we offset the loss of the zero fibre
by adding two carefully selected points from each non-empty fibre to the final
set of translates. These points are the maximiser and minimiser of the linear
function $x\mapsto\left\langle x,u^{*}\right\rangle$ in each fibre. Let
$Z=\\{z_{1},\ldots,z_{m}\\}$. For each $z_{i}\in Z$, we choose
$y_{i}^{+},y_{i}^{-}\in\llbracket z_{i}\rrbracket$ to be, respectively, a
maximiser and a minimiser of $y\mapsto\left\langle y,u^{*}\right\rangle$ in
$\llbracket z_{i}\rrbracket$, and set $Y_{i}:=\\{y_{i}^{+},y_{i}^{-}\\}$.

Recall that $Z=Z(X,W)$ is now defined as the projection of $X$ onto
$W^{\perp}$, where $X$ and $W$ come from the statement of the proposition.
Similarly to the proof of Proposition 3.2, we will define “positive” and
“negative” parts of $\llbracket 0\rrbracket$ as

$\displaystyle\llbracket 0\rrbracket_{+}=\big{\\{}x\in\llbracket
0\rrbracket:\left\langle
x,u^{*}\right\rangle>0\big{\\}}\quad\text{and}\quad\llbracket
0\rrbracket_{-}=\big{\\{}x\in\llbracket 0\rrbracket:\left\langle
x,u^{*}\right\rangle<0\big{\\}},$

which complement the “null part” $\llbracket 0\rrbracket_{*}=\\{x\in\llbracket
0\rrbracket:\left\langle x,u^{*}\right\rangle=0\\}$ defined in the statement
and complete a partition of the zero fibre.

Each pair of minimiser and maximiser we put in the set of translates will add
to the sumset a translated copy of the sets $\llbracket 0\rrbracket_{+}$ and
$\llbracket 0\rrbracket_{-}$. As they form a partition of $\llbracket
0\rrbracket\setminus\llbracket 0\rrbracket_{*}$, this will correspond to
adding $\big{|}\llbracket 0\rrbracket\big{|}-\big{|}\llbracket
0\rrbracket_{*}\big{|}$ elements to the sumset for each of the $m=|Z|$ non-
empty fibres. Showing this only requires the following simple geometric
observations. The first says that the translates $\llbracket
0\rrbracket+Y_{i}$ and $\llbracket 0\rrbracket+Y_{j}$ are disjoint if $Y_{i}$
and $Y_{j}$ lie in distinct fibres.

######  Observation 5.1.

For all $i,j\in\\{1,\ldots,m\\}$, if $i\neq j$, then

$\big{(}\llbracket 0\rrbracket+Y_{i}\big{)}\cap\big{(}\llbracket
0\rrbracket+Y_{j}\big{)}=\emptyset.$

###### Proof.

Note that $\llbracket 0\rrbracket+Y_{i}\subseteq[z_{i}]$, and recall from (22)
that $[z_{i}]\cap[z_{j}]=\emptyset$. ∎

The second observation says that the positive part of $\llbracket 0\rrbracket$
translated by the fibre maximiser $y_{i}^{+}$ is disjoint from its negative
part translated by the corresponding fibre minimiser. Its proof is essentially
contained in the proof of Proposition 3.2.

######  Observation 5.2.

For all $i\in\\{1,\ldots,m\\}$, we have

$\big{(}y_{i}^{+}+\llbracket
0\rrbracket_{+}\big{)}\cap\big{(}y_{i}^{-}+\llbracket
0\rrbracket_{-}\big{)}=\emptyset.$ (50)

###### Proof.

Note that for any $a\in\llbracket 0\rrbracket_{+},b\in\llbracket
0\rrbracket_{-}$, we have

$\displaystyle\left\langle y_{i}^{+}+a,u^{*}\right\rangle>\left\langle
y_{i}^{+},u^{*}\right\rangle\geq\left\langle
y_{i}^{-},u^{*}\right\rangle>\left\langle y_{i}^{-}+b,u^{*}\right\rangle.$

Hence, $y_{i}^{+}+a\neq y_{i}^{-}+b$ for every $a\in\llbracket
0\rrbracket_{+}$ and $b\in\llbracket 0\rrbracket_{-}$, which implies (50). ∎

The final observation says that the original set translated by the “null part”
of $\llbracket 0\rrbracket$ does not intersect the positive part of
$\llbracket 0\rrbracket$ translated by the fibre maximiser $y_{i}^{+}$, and
that the analogous statement holds for the negative part and the fibre
minimiser $y_{i}^{-}$.

######  Observation 5.3.

For all $i\in\\{1,\ldots,m\\}$, we have

$\big{(}X+\llbracket 0\rrbracket_{*}\big{)}\cap\big{(}y_{i}^{+}+\llbracket
0\rrbracket_{+}\big{)}=\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\cap\big{(}y_{i}^{-}+\llbracket
0\rrbracket_{-}\big{)}=\emptyset.$

###### Proof.

Recall that $X=\bigcup_{j=1}^{m}\llbracket z_{j}\rrbracket$ is a partition.
Whenever $\llbracket z_{j}\rrbracket$ and $y_{i}^{+}$ are in distinct fibres,
we have that $\llbracket z_{j}\rrbracket+\llbracket 0\rrbracket_{*}$ and
$y_{i}^{+}+\llbracket 0\rrbracket_{+}$ are disjoint by (22),

$\llbracket z_{j}\rrbracket+\llbracket
0\rrbracket_{*}\subseteq[z_{j}]\quad\text{and}\quad y_{i}^{+}+\llbracket
0\rrbracket_{+}\subseteq[z_{i}].$

We now consider the case when they are in the same fibre. Take $a\in\llbracket
0\rrbracket_{+}$, $c\in\llbracket 0\rrbracket_{*}$ and $y\in\llbracket
z_{i}\rrbracket$. Note that $\left\langle a,u^{*}\right\rangle>0$ since
$a\in\llbracket 0\rrbracket_{+}$, and $\left\langle c,u^{*}\right\rangle=0$ as
$c\in\llbracket 0\rrbracket_{*}$. Then $c+y\neq a+y_{i}^{+}$, because

$\displaystyle\left\langle a+y_{i}^{+},u^{*}\right\rangle>\left\langle
c+y_{i}^{+},u^{*}\right\rangle\geq\left\langle c+y,u^{*}\right\rangle,$

and this completes the proof in the $y_{i}^{+}$ case. The proof in the
$y_{i}^{-}$ case is analogous. ∎

We are now ready to prove Proposition 4.4.

###### Proof of Proposition 4.4.

Recall that $m=|Z|$, where $Z=Z(X,W)$, and $Y_{i}=\\{y_{i}^{+},y_{i}^{-}\\}$
consists of a maximiser and minimiser of $y\mapsto\left\langle
y,u^{*}\right\rangle$ in $\llbracket z_{i}\rrbracket$ for each $z_{i}\in Z$.
$Y_{i}$ is well-defined because $Z$ is the set of non-empty fibres, although
it may be a singleton for example if $\big{|}\llbracket
z_{i}\rrbracket\big{|}=1$. We define $T^{\prime\prime}$ to be the following
set with (trivially) at most $2m$ elements

$T^{\prime\prime}=\bigcup_{i=1}^{m}Y_{i}.$

To avoid cumbersome notation, we will first prove the weaker inequality

$\big{|}\llbracket
0\rrbracket+T^{\prime\prime}\big{|}\geq\sum_{i=1}^{m}\big{|}y_{i}^{+}+\llbracket
0\rrbracket_{+}\big{|}+\big{|}y_{i}^{-}+\llbracket 0\rrbracket_{-}\big{|},$
(51)

and then show that the same steps can be applied removing the set
$X+\llbracket 0\rrbracket_{*}$ in the left-hand side to obtain the desired
bound.

As $T^{\prime\prime}$ is the union of the $Y_{i}$, we use Observation 5.1 to
obtain

$\big{|}\llbracket
0\rrbracket+T^{\prime\prime}\big{|}=\sum_{i=1}^{m}\big{|}\llbracket
0\rrbracket+Y_{i}\big{|}.$ (52)

Now, because $\llbracket 0\rrbracket_{+}$, $\llbracket 0\rrbracket_{*}$ and
$\llbracket 0\rrbracket_{-}$ partition $\llbracket 0\rrbracket$, we may
decompose, for each $Y_{i}$, the term in (52) as

$\big{|}\llbracket 0\rrbracket+Y_{i}\big{|}=\big{|}\big{(}\llbracket
0\rrbracket_{+}+Y_{i}\big{)}\cup\big{(}\llbracket
0\rrbracket_{*}+Y_{i}\big{)}\cup\big{(}\llbracket
0\rrbracket_{-}+Y_{i}\big{)}\big{|},$ (53)

which, ignoring the term corresponding to $\llbracket 0\rrbracket_{*}$ and the
“mixed-sign” terms, $\llbracket 0\rrbracket_{-}+y_{+}$ and $\llbracket
0\rrbracket_{+}+y_{-}$, yields

$\big{|}\llbracket 0\rrbracket+Y_{i}\big{|}\geq\big{|}\big{(}\llbracket
0\rrbracket_{+}+y_{i}^{+}\big{)}\cup\big{(}\llbracket
0\rrbracket_{-}+y_{i}^{-}\big{)}\big{|}.$ (54)

We can now apply Observation 5.2, which implies that the right-hand side of
(54) is at least

$\big{|}\big{(}\llbracket
0\rrbracket_{+}+y_{i}^{+}\big{)}\cup\big{(}\llbracket
0\rrbracket_{-}+y_{i}^{-}\big{)}\big{|}=\big{|}\llbracket
0\rrbracket_{+}+y_{i}^{+}\big{|}+\big{|}\llbracket
0\rrbracket_{-}+y_{i}^{-}\big{|},$ (55)

hence establishing (51) via (52).

To obtain the desired bound, we now show that the same steps can be applied
removing the set $X+\llbracket 0\rrbracket_{*}$ in the left-hand side of (51).
First, (52) holds if we remove $X+\llbracket 0\rrbracket_{*}$ from the set in
the left-hand side and those in the sum in the right-hand side because
removing a set cannot create intersections in disjoint sets. We then repeat
the steps in (53) and (54) – they are also possible regardless of the set
removal – and, upon reaching (55), we again use that disjointness is preserved
under set removal. This gives us

$\Big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\Big{|}\geq\sum_{i=1}^{m}\Big{|}\big{(}y_{i}^{+}+\llbracket
0\rrbracket_{+}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\Big{|}+\Big{|}\big{(}y_{i}^{-}+\llbracket
0\rrbracket_{-}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\Big{|}.$

We are now in a position to use Observation 5.3 to deduce that the set we
removed is disjoint from the ones in the right-hand side above, and recover
the lower bound prior to the removal

$\displaystyle\Big{|}\big{(}\llbracket
0\rrbracket+T^{\prime\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket_{*}\big{)}\Big{|}$
$\displaystyle\geq\sum_{i=1}^{m}\big{|}y_{i}^{+}+\llbracket
0\rrbracket_{+}\big{|}+\big{|}y_{i}^{-}+\llbracket 0\rrbracket_{-}\big{|}$
$\displaystyle=m\Big{(}\big{|}\llbracket
0\rrbracket_{+}\big{|}+\big{|}\llbracket 0\rrbracket_{-}\big{|}\Big{)}.$

Again using that $\llbracket 0\rrbracket_{-}\cup\llbracket
0\rrbracket_{*}\cup\llbracket 0\rrbracket_{+}$ is a partition of $\llbracket
0\rrbracket$, we get

$m\Big{(}\big{|}\llbracket 0\rrbracket_{+}\big{|}+\big{|}\llbracket
0\rrbracket_{-}\big{|}\Big{)}=m\Big{(}\big{|}\llbracket
0\rrbracket\big{|}-\big{|}\llbracket 0\rrbracket_{*}\big{|}\Big{)},$

as required to complete the proof. ∎

##  6\. Weighted Freĭman’s lemma: proof of Proposition 4.3

The final piece we need to prove Theorem 1.3 is detailing how to choose
$T^{\prime}\subseteq X$ such that $|T^{\prime}|\leq|Z|$ and (24) holds, and
how to prove a variant of Freĭman’s lemma where the size of the original,
unprojected set $X$ appears in the lower bound, instead of simply $|Z|$.

We will first prove a weaker, insufficient statement to make the reader
comfortable with the notation and ideas in the proof of Proposition 4.3. Our
goal here is to show that we can choose $T^{\prime}\subseteq X$ such that
$|T^{\prime}|\leq|Z|$ and333Notice that $(w-Z)\cap Z=\\{z\in Z:\exists
z^{\prime}\in Z\,\text{ such that }z+z^{\prime}=w\\}$.

$|X+T^{\prime}|\geq\sum_{w\in Z+Z}\max_{z\in(w-Z)\cap Z}\big{|}\llbracket
z\rrbracket\big{|}.$ (56)

Before proceeding, it will be useful to let $Z=\\{z_{1},\ldots,z_{m}\\}$. Here
(and in the proof itself), we will take

$T^{\prime}=\\{y_{1},\ldots,y_{m}\\},$

where, for each $i\in\\{1,\ldots,m\\}$, $y_{i}\in\llbracket z_{i}\rrbracket$
is arbitrary. It is immediate that the size of $T^{\prime}$ is appropriate,
that is,

$|T^{\prime}|\leq|Z|,$

so we must show that it also satisfies (24).

Having defined $T^{\prime}$, we start this warm-up by partitioning
$X+T^{\prime}$ into fibres of $Z+Z$:

$X+T^{\prime}=\bigcup_{w\in Z+Z}[w]\cap(X+T^{\prime}).$ (57)

As (57) defines a partition, we also have

$\left|\bigcup_{w\in Z+Z}\Big{(}[w]\cap(X+T^{\prime})\Big{)}\right|=\sum_{w\in
Z+Z}\left|\Big{(}[w]\cap(X+T^{\prime})\Big{)}\right|.$

Note also that if $w=z_{i}+z_{j}\in Z+Z$, then

$\llbracket z_{i}\rrbracket+y_{j}\subseteq\big{(}[w]\cap(X+T^{\prime})\big{)}$
(58)

since $\llbracket z_{i}\rrbracket\subseteq X$ and $y_{j}\in\llbracket
z_{j}\rrbracket\cap T^{\prime}$.

Our approach will be to count only the elements in a single (translated) fibre
$\llbracket z_{i}\rrbracket+y_{j}$ and ignore the rest of
$[z_{i}+z_{j}]\cap(X+T^{\prime})$ – by (57) and (58), this is a valid lower
bound for $|X+T^{\prime}|$. As the union in (57) ranges over all $w\in Z+Z$,
we can pick any possible representation $z_{i}+z_{j}$ for $w$. Our choice will
be the one for which $\big{|}\llbracket z_{i}\rrbracket\big{|}$ is as large as
possible, resulting in

$\sum_{w\in Z+Z}\left|\Big{(}[w]\cap(X+T^{\prime})\Big{)}\right|\geq\sum_{w\in
Z+Z}\max_{z\in(w-Z)\cap Z}\big{|}\llbracket z\rrbracket\big{|},$

since $\big{|}\llbracket z\rrbracket+y\big{|}=\big{|}\llbracket
z\rrbracket\big{|}$. This completes the proof of (56).

In the proof of Proposition 4.3, the statement that is analogous to (56) is

$\Big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}\geq\sum_{w\in(Z^{*}+Z^{*})\setminus
Z}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket z\rrbracket\big{|},$ (59)

where $Z^{*}=Z\setminus\\{0\\}$ – in words, we “remove the $0$ from $Z$”
before doing the sumset. The proof of (59) is essentially the same as the
warm-up above, but that is still not enough. We must have a good lower bound
for its right-hand side in order to complete a proof of Proposition 4.3.

Lemma 6.1, below, is the lower bound we need for the right-hand side of (59):
when applying it to prove Proposition 4.3, we will set $U=Z^{*}$ and
$f(z)=\big{|}\llbracket z\rrbracket\big{|}$. The proof of the lemma is similar
to traditional proofs of Freĭman’s lemma, but we must take into account the
weight $f(u)$ of each $u\in U$ when selecting vertices of
$\operatorname{conv}(U)$, the convex hull of $U$, instead of choosing an
arbitrary vertex444Hence the name “weighted Freĭman’s lemma”..

######  Lemma 6.1.

Let $d\in\mathbb{N}$. For every finite $U\subseteq\mathbb{R}^{d}$ and
$f:U\to\mathbb{R}_{+}$, we have

$\sum_{w\in U+U}\max_{u\in(w-U)\cap
U}f(u)\geq\frac{\operatorname{rank}(U)+1}{2}\sum_{u\in U}f(u).$ (60)

We will also need a simple observation to repeat one of the steps in the proof
of Freĭman’s lemma and prove Lemma 6.1.

######  Observation 6.2.

Let $U\subseteq\mathbb{R}^{d}$ be a finite set. If $v\in U$ is a vertex of
$\operatorname{conv}(U)$ and $U^{\prime}=U\setminus\\{v\\}$, then there exists
a hyperplane $\mathcal{H}$ such that $v$ and $U^{\prime}\setminus\mathcal{H}$
are on different sides of $\mathcal{H}$. Moreover, $|\mathcal{H}\cap
U^{\prime}|\geq\operatorname{rank}(U^{\prime})$.

###### Proof.

Write
$\operatorname{conv}(U^{\prime})=\bigcap_{\mathcal{H}\in\mathbf{H}}\mathcal{H}^{-}$,
where $\mathbf{H}$ is the collection of hyperplanes supporting the facets of
$\operatorname{conv}(U^{\prime})$ and $\mathcal{H}^{-}$ denotes a closed half-
space defined by $\mathcal{H}$. Since
$v\not\in\operatorname{conv}(U^{\prime})$, there exists
$\mathcal{H}\in\mathbf{H}$ such that $v\not\in\mathcal{H}^{-}$, so $v$ and
$U^{\prime}\setminus\mathcal{H}$ are on different sides of $\mathcal{H}$. The
second part of the statement follows from $\mathcal{H}$ intersecting a facet
of $\operatorname{conv}(U^{\prime})$ and the fact that every facet contains at
least $\operatorname{rank}(U^{\prime})$ vertices. ∎

Now, we can prove Lemma 6.1.

###### Proof of Lemma 6.1.

We prove the lemma by induction on $|U|$. In the base case, we have an empty
set, so the left-hand side of (60) is equal to 0, as is the right-hand side.
We can therefore assume that for every $U^{\prime}\subsetneq U$, we have (60).

For the induction step, we proceed similarly to the standard proof of
Freĭman’s lemma. The main difference is that instead of choosing an arbitrary
element from $V$, the vertices of $\operatorname{conv}(U)$, we must choose a
vertex considering the weight function $f$. To be precise, we choose a vertex
$v\in V$ such that

$f(v)\leq\frac{1}{s+1}\sum_{u\in U}f(u),$ (61)

where $s=\operatorname{rank}(U)$, noting that such a choice exists by the
pigeonhole principle,

$(s+1)\min_{v\in V}f(v)\leq|V|\min_{v\in V}f(v)\leq\sum_{v\in
V}f(v)\leq\sum_{u\in U}f(u).$

We fix one such $v\in V$, define $U^{\prime}=U\setminus\\{v\\}$ and divide the
remainder of the proof based on whether ${\operatorname{rank}(U^{\prime})=s}$.

Consider first the case $\operatorname{rank}(U^{\prime})=s$. The induction
hypothesis implies that

$\sum_{w\in U^{\prime}+U^{\prime}}\max_{u\in(w-U)\cap U}f(u)\geq\sum_{w\in
U^{\prime}+U^{\prime}}\max_{u\in(w-U^{\prime})\cap
U^{\prime}}f(u)\geq\frac{s+1}{2}\sum_{u^{\prime}\in U^{\prime}}f(u^{\prime})$
(62)

since $U^{\prime}\subseteq U$. Therefore, by (62), we can accomplish our goal
by finding a set $S\subseteq(U+U)\setminus(U^{\prime}+U^{\prime})$ such that

$\sum_{w\in S}\max_{u\in(w-U)\cap U}f(u)\geq\frac{s+1}{2}f(v).$ (63)

In order to define our candidate set for $S$, let $\mathcal{H}$ be the
hyperplane given by Observation 6.2 for $U$ and $v$, and take
$\overline{N}(v)=\big{(}\mathcal{H}\cap\operatorname{conv}(U^{\prime})\big{)}\cup\\{v\\}$.
We claim that $\overline{N}(v)+v$ is a suitable choice for $S$ because it is
disjoint from $U^{\prime}+U^{\prime}$ and satisfies (63).

To see that $\overline{N}(v)+v$ and $U^{\prime}+U^{\prime}$ are disjoint,
first notice that $2v\not\in U^{\prime}+U^{\prime}$ follows from $v$ being a
vertex of $\operatorname{conv}(U)$. For the remaining elements of
$\overline{N}(v)$, i.e.
$v^{\prime}\in\mathcal{H}\cap\operatorname{conv}(U^{\prime})$, $v^{\prime}+v$
is not in $U^{\prime}+U^{\prime}$ because $(v^{\prime}+v)/2$ is a midpoint of
the segment connecting $v$ and $v^{\prime}$, and this midpoint clearly lies
outside $\operatorname{conv}(U^{\prime})$ by our choice of $\mathcal{H}$.

It remains to show that (63) holds with $S=\overline{N}(v)+v$. Observe that if
$w=v^{\prime}+v$ for some $v^{\prime}\in\overline{N}(v)$, then $v\in(w-U)\cap
U$. Hence,

$\sum_{w\in\overline{N}(v)+v}\max_{u\in(w-U)\cap
U}f(u)\geq\sum_{w\in\overline{N}(v)+v}f(v)=\big{|}\overline{N}(v)\big{|}\,f(v)\geq(s+1)f(v),$
(64)

where in the last inequality we used that

$|\overline{N}(v)|=|\mathcal{H}\cap
U^{\prime}|+1\geq\operatorname{rank}(U^{\prime})+1=s+1$

which is due to our choice of $\mathcal{H}$ by Observation 6.2 and our
assumption that $\operatorname{rank}(U^{\prime})=s$. Combining (62) and (64),
this completes the induction step when
$\operatorname{rank}(U^{\prime})=\operatorname{rank}(U)$.

We may therefore assume that $\operatorname{rank}(U^{\prime})=s-1$; that is,
the removal of the vertex $v$ decreases the rank of $U$. It will be useful for
this case to recall (61), our criterion for the choice of $v$, in the
following (trivially) equivalent form:

$\sum_{u\in U}f(u)\geq(s+1)f(v).$ (65)

Applying our induction hypothesis to $U^{\prime}$ yields

$\sum_{w\in U^{\prime}+U^{\prime}}\max_{u\in(w-U^{\prime})\cap
U^{\prime}}f(u)\geq\frac{s}{2}\sum_{u^{\prime}\in U^{\prime}}f(u^{\prime}),$
(66)

so, to deduce the bound (60), it is enough to add to (66) the term

$\Big{(}\frac{1}{2}\sum_{u^{\prime}\in
U^{\prime}}f(u^{\prime})\Big{)}+\frac{s+1}{2}f(v)$ (67)

using elements of $(U+U)\setminus(U^{\prime}+U^{\prime})$.

In order to add (67) to (66), we argue that $U^{\prime}+U^{\prime}$,
$\\{2v\\}$ and $U^{\prime}+v$ are disjoint. This follows from our assumption
that $\operatorname{rank}(U^{\prime})<\operatorname{rank}(U)$, which implies
that $v\not\in\mathcal{U}$, where $\mathcal{U}$ is an affine subspace with
dimension $\operatorname{rank}(U^{\prime})$ containing $U^{\prime}$. We can
therefore conclude that

$\sum_{w\in U+U}\max_{u\in(w-U)\cap U}f(u)\geq\frac{s}{2}\sum_{u^{\prime}\in
U^{\prime}}f(u^{\prime})+f(v)+\sum_{w\in U^{\prime}+v}\max_{u\in(w-U)\cap
U}f(u).$ (68)

Our first observation towards bounding the right-hand side of (68) is that

$\sum_{w\in U^{\prime}+v}\max_{u\in(w-U)\cap U}f(u)\geq\sum_{u^{\prime}\in
U^{\prime}}f(u^{\prime})$ (69)

because if $w=u^{\prime}+v$ for some $u^{\prime}\in U^{\prime}$, then
$u^{\prime}\in(w-U)\cap U$. It will therefore suffice to show that

$f(v)+\sum_{u^{\prime}\in
U^{\prime}}f(u^{\prime})\geq\Big{(}\frac{1}{2}\sum_{u^{\prime}\in
U^{\prime}}f(u^{\prime})\Big{)}+\frac{s+1}{2}f(v),$

or, equivalently,

$2f(v)+\sum_{u^{\prime}\in U^{\prime}}f(u^{\prime})\geq(s+1)f(v).$

We now use that our choice of $v$ satisfies (65), which implies that

$2f(v)+\sum_{u^{\prime}\in U^{\prime}}f(u^{\prime})\geq\sum_{u\in
U}f(u)\geq(s+1)f(v),$ (70)

and hence completes the proof of the induction step. ∎

With Lemma 6.1, we are now ready to prove Proposition 4.3.

###### Proof of Proposition 4.3.

Our first claim is that finding a $T^{\prime}\subseteq X$ such that
$|T^{\prime}|\leq|Z|$ and

$\Big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}\geq\sum_{w\in(Z^{*}+Z^{*})\setminus
Z}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket z\rrbracket\big{|},$ (71)

where $Z^{*}=Z\setminus\\{0\\}$, is enough to complete the proof. To see that,
apply Lemma 6.1 with $U=Z^{*}$ and $f(z)=\big{|}\llbracket z\rrbracket\big{|}$
to get the lower bound

$\sum_{w\in Z^{*}+Z^{*}}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket
z\rrbracket\big{|}\geq\frac{\operatorname{rank}(Z^{*})+1}{2}\sum_{z\in
Z^{*}}\big{|}\llbracket
z\rrbracket\big{|}\geq\frac{r-r_{W}}{2}\big{(}|X|-\big{|}\llbracket
0\rrbracket\big{|}\big{)},$ (72)

where in the last equality we have used that

$Z^{*}=Z\setminus\\{0\\},\quad X=\bigcup_{z\in Z}\llbracket
z\rrbracket\quad\text{and}\quad\operatorname{rank}(Z^{*})\geq r-r_{W}-1,$

by our assumptions that $Z=\Pi_{W^{\perp}}(X)$, $\operatorname{rank}(X)\geq r$
and $r_{W}=\operatorname{rank}(W)$.

However, the left-hand side of (72) is considering elements $w\in Z$ that are
not in the sum in (71). This is not an issue because

$\sum_{w\in Z}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket
z\rrbracket\big{|}\leq\eta|Z||X|$ (73)

follows from our assumption that $\big{|}\llbracket
z\rrbracket\big{|}\leq\eta|X|$ for all $z\in Z^{*}$. We obtain the claim that
$T^{\prime}$ as specified finishes the proof by substituting (73) and (72)
into (71):

$\sum_{w\in(Z+Z)\setminus Z}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket
z\rrbracket\big{|}\geq\frac{r-r_{W}}{2}\big{(}|X|-\big{|}\llbracket
0\rrbracket\big{|}\big{)}-\eta|Z||X|.$

As it now suffices to find $T^{\prime}\subseteq X$ such that
$|T^{\prime}|\leq|Z|$ and (71) holds, we simply need to repeat the proof of
(56) given in the warm-up, but with the set $X+\llbracket 0\rrbracket$
removed. That is, let $Z^{*}=\\{z_{1},\ldots,z_{m}\\}$, and define

$T^{\prime}=\\{y_{1},\ldots,y_{m}\\}$ (74)

where each $y_{i}$ is an arbitrary element of $\llbracket z_{i}\rrbracket$ for
$i\in\\{1,\ldots,m\\}$. The first step to show that $T^{\prime}$ satisfies
(71) is partitioning $X+T^{\prime}$ into fibres of $Z+Z$ to obtain

$\Big{|}\big{(}X+T^{\prime}\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}=\sum_{w\in
Z+Z}\Big{|}\big{(}[w]\cap(X+T^{\prime})\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}.$ (75)

In order to handle the set removal, we claim that if $w\not\in Z$, then the
sets $[w]$ and $X+\llbracket 0\rrbracket$ are disjoint, and therefore

$\sum_{w\in
Z+Z}\Big{|}\big{(}[w]\cap(X+T^{\prime})\big{)}\setminus\big{(}X+\llbracket
0\rrbracket\big{)}\Big{|}\geq\sum_{w\in(Z+Z)\setminus
Z}\big{|}[w]\cap(X+T^{\prime})\big{|}.$ (76)

To see this, simply note that if $x\in X$ and $x^{\prime}\in\llbracket
0\rrbracket$, then

$\Pi_{W^{\perp}}(x+x^{\prime})=\Pi_{W^{\perp}}(x)+\Pi_{W^{\perp}}(x^{\prime})\in
Z+0=Z$

by the definitions of $\llbracket 0\rrbracket$ and $Z$, and therefore
$\Pi_{W^{\perp}}(X+\llbracket 0\rrbracket)\subseteq Z$.

Having established (76), we can proceed (almost) like in the warm-up.
Restricting our attention to $Z^{*}+Z^{*}\subseteq Z+Z$, observe that every
$w\in Z^{*}+Z^{*}$ can be written as

$w=z+z^{\prime}\quad\text{where}\quad z,z^{\prime}\in(w-Z^{*})\cap Z^{*}.$
(77)

For each $w\in Z^{*}+Z^{*}$, then, we pick the pair
$(z,z^{\prime})\in(Z^{*})^{2}$ satisfying (77) that maximises
$\big{|}\llbracket z\rrbracket\big{|}$. Let $y$ be the (unique) element of
$T^{\prime}\cap[z^{\prime}]$, and note that, as $\llbracket
z\rrbracket+y\subseteq[w]\cap(X+T^{\prime})$, we can conclude that

$\big{|}[w]\cap(X+T^{\prime})\big{|}\geq\max_{z\in(w-Z^{*})\cap
Z^{*}}\big{|}\llbracket z\rrbracket\big{|}.$ (78)

Replacing (78) into (76) yields that (71) holds for $T^{\prime}$

$\sum_{w\in(Z+Z)\setminus
Z}\big{|}[w]\cap(X+T^{\prime})\big{|}\geq\sum_{w\in(Z^{*}+Z^{*})\setminus
Z}\max_{z\in(w-Z^{*})\cap Z^{*}}\big{|}\llbracket z\rrbracket\big{|},$

and the proof therefore follows from our first claim. ∎

##  7\. The supersaturation result

This section is dedicated to the proof of the following theorem, restated for
convenience: See 2.2

Now that we have Theorem 1.3, proving Theorem 2.2 is simple. Assume that $Y$
is small, that is, $|Y|\leq(1-\gamma)(d+1)|X|/2$; our goal is to show that it
misses many pairs of $X^{2}$. If we can find $\varepsilon|X|$ elements
$x^{(i)}\in X$ such that $Y$ contains at most a $1-c$ proportion of
$X+x^{(i)}$, we are done. To do that, we will use Theorem 1.3 to find a small
set $T\subseteq X$ such that $|X+T|-|Y|\gtrsim\gamma(d+1)|X|$. By the
pigeonhole principle, it follows that there exists an $x^{(i)}\in T$ such that
$Y$ misses many elements of $X+x^{(i)}$. We can then remove $x^{(i)}$ from $X$
and repeat the process until the dimension of $X$ drops below its original
value (removing the $x^{(i)}$ is a simple way to avoid using the same element
twice while keeping our working set large). As we assumed that $X$ has
$\varepsilon$-robust Freĭman dimension $d$, this can only happen after we have
removed $\varepsilon|X|$ translates.

This is essentially the proof except for the fact that Theorem 1.3 requires
$X\subseteq\mathbb{R}^{d}$, and the set in Theorem 2.2 is a subset of
$\mathbb{Z}_{n}$. To handle this, we use Freĭman isomorphisms, relying on the
fact that if $\phi$ is a Freĭman isomorphism, then
$|X_{1}+X_{2}|=|\phi(X_{1})+\phi(X_{2})|$.

###### Proof of Theorem 2.2.

Assume that555We use $\gamma^{\prime}$ instead of $\gamma$ because its value
is (slightly) less than the $\gamma$ in the application of Theorem 1.3.
$|Y|\leq(1-\gamma^{\prime})(d+1)|X|/2$. We claim that there exists a sequence
of distinct elements $x^{(1)},\dots,x^{(t)}\in X$, where $t=\varepsilon|X|/4$,
such that the sets $X_{i}=X\setminus\\{x^{(1)},\dots,x^{(i)}\\}$ have the
following two properties

$d_{i}=\dim_{\mathrm{F}}(X_{i})\geq d\quad\text{ and
}\quad\big{|}(X_{i}+x^{(i+1)})\setminus Y\big{|}\geq 4c|X|.$ (79)

The first property holds because, for all $i\leq t$,

$|X_{i}|\geq|X|-i\geq|X|-t=\left(1-\frac{\varepsilon}{4}\right)|X|,$ (80)

so we still have $\dim_{\mathrm{F}}(X_{i})\geq d$, since $X$ has
$\varepsilon$-robust Freĭman dimension $d$.

To prove that $X_{i}$ satisfies the second property in (79), we will show how
to select each $x^{(i+1)}$. That is, assume that we have distinct translates
$\\{x^{(1)},\dots,x^{(i)}\\}$ such that the set $X_{i}$ satisfies (79). Since
$\dim_{\mathrm{F}}(X_{i})=d_{i}\geq d$, there exists a Freĭman isomorphism
${\phi_{i}:X_{i}\to X_{i}^{\prime}}$ such that
${X_{i}^{\prime}\subseteq\mathbb{R}^{d_{i}}}$ has full rank. If
$\gamma^{\prime}>2^{6}d^{-1/3}$, then we can apply Theorem 1.3 to the set
$X_{i}^{\prime}$ with $r=d$ and $\gamma=2^{-6}\gamma^{\prime}$, to obtain a
set $T_{i}^{\prime}\subseteq X_{i}^{\prime}$ such that

$|T_{i}^{\prime}|\leq\frac{2^{6}(d+1)}{\gamma^{\prime}}\quad\text{ and
}\quad|X_{i}^{\prime}+T_{i}^{\prime}|\geq\left(1-\frac{\gamma^{\prime}}{4}\right)\frac{(d+1)|X_{i}^{\prime}|}{2}.$

Otherwise, we have $\gamma^{\prime}\leq 2^{6}d^{-1/3}$, i.e. $d\leq
2^{18}\gamma^{\prime-3}$. In this case, we can666As it is stated, Theorem 1.4
can only be used for $d=d_{i}$, but that could result in too many translates.
To circumvent this issue, we can randomly project the set to $\mathbb{R}^{d}$,
and apply Theorem 1.4 to the projected set instead, using the randomness to
avoid collisions. apply Theorem 1.4 and obtain
$T_{i}^{\prime}=\\{x_{1},\ldots,x_{C}\\}\subseteq X_{i}^{\prime}$ such that

$|X_{i}^{\prime}+T_{i}^{\prime}|\geq(d+1)|X_{i}^{\prime}|-5(d+1)^{3}\geq\frac{(d+1)|X_{i}^{\prime}|}{2},$

for some constant $C=C(\gamma^{\prime})$, since $X_{i}$ satisfies (80), $X$ is
sufficiently large and $d\leq 2^{18}\gamma^{\prime-3}$. Therefore, it follows
that we have a set of translates $T_{i}^{\prime}$ of size at most
$2^{-6}\gamma^{\prime}(d+1)/c$ for some constant $c=c(\gamma^{\prime})>0$, in
either case.

As $\phi_{i}$ is a Freĭman isomorphism, we know that the preimage
$T_{i}=\phi_{i}^{-1}(T_{i}^{\prime})$ satisfies

$|X_{i}+T_{i}|\geq\left(1-\frac{\gamma^{\prime}}{4}\right)\frac{(d+1)|X_{i}|}{2}=\left(1-\frac{\gamma^{\prime}}{4}\right)\frac{(d+1)(|X|-i)}{2}$

and ${|T_{i}|\leq 2^{-6}\gamma^{\prime}(d+1)/c}$. Since $i\leq
t=\varepsilon|X|/4<\gamma^{\prime}|X|/4,$ this is at least

$|X_{i}+T_{i}|\geq\left(1-\frac{\gamma^{\prime}}{4}\right)^{2}\frac{(d+1)|X|}{2}\geq\left(1-\frac{\gamma^{\prime}}{2}\right)\frac{(d+1)|X|}{2}.$

Recalling our assumption $|Y|\leq(1-\gamma^{\prime})(d+1)|X|/2$, it follows
that

$|(X_{i}+T_{i})\setminus
Y|\geq|X_{i}+T_{i}|-|Y|\geq\frac{\gamma^{\prime}(d+1)|X|}{4}.$

Thus, by the pigeonhole principle, there exists $x^{(i+1)}\in T_{i}$ such that

$|(X_{i}+x^{(i+1)})\setminus
Y|\geq\frac{\gamma^{\prime}(d+1)|X|}{4}\left(\frac{\gamma^{\prime}(d+1)}{2^{6}c}\right)^{-1}>4c|X|,$

since $|T_{i}|\leq 2^{-6}\gamma^{\prime}(d+1)/c$ and $T_{i}\subseteq X_{i}$.
Repeating this for each $i$ from 1 to $t$ thus yields the sets $X_{i}$ and
$\\{x^{(1)},\ldots,x^{(t)}\\}$ satisfying (79).

Now that we have the sets $X_{i}$, note that each $X+x^{(i)}$ contributes
$4c|X|$ ordered pairs whose sum are not in $Y$. This gives us a total of

$4c|X|t\geq c\varepsilon|X|^{2}$

such pairs, because $t=\varepsilon|X|/4$. ∎

##  8\. An upper bound for the independence number

In this section, we prove the upper bound part of our main result, Theorem
1.1:

######  Theorem 8.1.

Let $n$ be a prime number and let $p=p(n)$ satisfy $p\geq(\log n)^{-1/80}$.
The random Cayley sum graph $\Gamma_{p}$ of $\mathbb{Z}_{n}$ satisfies

$\alpha(\Gamma_{p})\leq\big{(}2+o(1)\big{)}\log_{\frac{1}{1-p}}n$

with high probability as $n\to\infty$.

Throughout, we fix a small enough $\delta>0$ and
$k=(2+4\delta)\log_{\frac{1}{1-p}}n$. We will also follow the outline
presented in Section 2 and use the notation defined there. Each sub-collection
$\mathcal{X}_{i}$ requires different techniques to bound the probability that
$\alpha(\Gamma_{p})>k$, so we handle each separately and show all three go to
0 as $n\to\infty$.

###  8.1. Bounding the probability over choices in $\mathcal{X}_{1}$

A brief recap: in this doubling range, there are far too many choices for
$X\in\mathcal{X}_{1}$ for a union bound to work. The key observation is that
we do not need to count every such $X$: if somehow going to a smaller subset
$\Lambda\subseteq X$ reduces our choices considerably, this would also be
enough, since the event $\\{\Lambda\mathbin{\hat{+}}\Lambda\subseteq
A_{p}^{\mathsf{c}}\\}$ contains $\\{X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}\\}$. As a matter of fact, we will use this idea twice.

The first time we use this idea is in order to replace each set
$X\in\mathcal{X}_{1}$ by a large subset $X^{\prime}\subseteq X$ whose Freĭman
dimension is robust in the sense required by Theorem 2.2, our supersaturation
result. We build the set $X^{\prime}$ from $X$ by greedily removing small,
“bad” subsets $B\subseteq X$ such that removing them from $X$ reduces its
Freĭman dimension. Each such removal reduces $\dim_{\mathrm{F}}(X)$ by at
least one, so we finish in at most $\dim_{\mathrm{F}}(X)$ steps. A step
reduces the size of the working set by at most $\varepsilon|X|$, which would
already give $|X^{\prime}|\geq(1-\dim_{\mathrm{F}}(X)\varepsilon)|X|$. To get
a bound that depends on $\sigma$ instead of on $\dim_{\mathrm{F}}(X)$, we use
the following trivial consequence of Freĭman’s lemma, Lemma 1.2, which we
record for ease of reference later.

######  Observation 8.2.

Let $X\subseteq\mathbb{Z}_{n}$ with $\sigma[X]\leq\sigma$. Then,
$\dim_{\mathrm{F}}(X)+1\leq 2\sigma$.

###### Proof.

Let $d=\dim_{\mathrm{F}}(X)$, and take $X^{\prime}\subseteq\mathbb{Z}^{d}$ of
full rank to be the image of $X$ under a Freĭman isomorphism $\phi$. Applying
Freĭman’s lemma to $X^{\prime}$ yields

$|X^{\prime}+X^{\prime}|\geq(d+1)|X^{\prime}|-\binom{d+1}{2}$

but $|X^{\prime}+X^{\prime}|\leq\sigma|X^{\prime}|$ and $|X^{\prime}|=|X|$ by
our choice of $\phi$. Dividing both sides by $|X|$ yields

$\sigma\geq d+1-\frac{d+1}{2}$

where we used $|X|\geq d$ to simplify the right-hand side. The proof follows
by rearranging. ∎

The proof of the following proposition is just formalizing the sketch using
Observation 8.2.

######  Proposition 8.3.

Let $X\subseteq\mathbb{Z}_{n}$ with $\sigma[X]\leq\sigma$ and let
$\varepsilon<1/2\sigma$. There exists $d\in\mathbb{N}$ and
$X^{\prime}\subseteq X$ such that $|X^{\prime}|>(1-2\varepsilon\sigma)|X|$ and
$X^{\prime}$ has $\varepsilon$-robust Freĭman dimension $d$.

###### Proof.

We start an iterative process with $X_{0}=X$ and $i=0$. While there exists
$B\subseteq X_{i}$ such that

$|B|\leq\varepsilon|X|\quad\text{ and }\quad\dim_{\mathrm{F}}(X_{i}\setminus
B)<\dim_{\mathrm{F}}(X_{i}),$

we define $X_{i+1}=X_{i}\setminus B$. Let $t$ be the number of steps in this
process, and let $X^{\prime}=X_{t}$.

First, notice that $t\leq\dim_{\mathrm{F}}(X)$ since each step reduces
$\dim_{\mathrm{F}}(X_{i})$ by at least one. We argue that $X^{\prime}$ has
$\varepsilon$-robust Freĭman dimension by considering two cases. If
$t<\dim_{\mathrm{F}}(X)$, then $X_{t}$ has $\varepsilon$-robust Freĭman
dimension $\dim_{\mathrm{F}}(X_{t})$. Otherwise, we have stopped when
$\dim_{\mathrm{F}}(X^{\prime})=1$, and such sets trivially have
$\varepsilon$-robust dimension 1.

Since $|X_{i}|\geq|X|-i\varepsilon|X|$, it follows that

$|X^{\prime}|\geq(1-\varepsilon
t)|X|\geq(1-\varepsilon\dim_{\mathrm{F}}(X))|X|>(1-2\varepsilon\sigma)|X|,$

where in the last inequality we used Observation 8.2. ∎

The second time we employ the idea of going to smaller subsets is when we use
the fingerprints given by Theorem 2.1, whose statement we repeat here for
convenience. See 2.1

As we remarked in the overview, applying the previous theorem to the (trivial)
generalised arithmetic progression $\mathbb{Z}_{n}$ would result in too many
fingerprints. To overcome this, we will use Corollary 8.4 below. We will
obtain said corollary by combining a strengthening of the Green–Ruzsa theorem
due to Cwalina and Schoen [12], Theorem A.1, with the discrete John’s theorem
of Tao and Vu [28], Theorem A.3. We defer the details to Appendix A.

######  Corollary 8.4.

There exists $C>0$ such that the following holds. Let $n\in\mathbb{N}$ be a
prime, and let $\kappa\geq 2$. If $X\subseteq\mathbb{Z}_{n}$ satisfies

$\sigma[X]\leq\kappa\qquad\text{ and }\qquad
C\kappa^{3}(\log\kappa)^{2}<|X|<\exp(-C\kappa^{4}(\log\kappa)^{2})n,$ (81)

then there is a generalised arithmetic progression $P\subseteq\mathbb{Z}_{n}$
such that

$X\subseteq P,\qquad|P|\leq\exp(C\kappa^{4}(\log\kappa)^{2})|X|\qquad\text{
and }\qquad\dim(P)\leq\dim_{\mathrm{F}}(X).$ (82)

We are now ready to prove that

$\mathbb{P}(\exists\,X\in\mathcal{X}_{1}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}})\to 0\quad\text{ as }\quad n\to\infty.$ (83)

###### Proof of (83).

Recall that $k=(2+4\delta)\log_{\frac{1}{1-p}}n$, and that for all
$X\in\mathcal{X}_{1}$, we know that $|X|=k$ and $\sigma[X]\leq k^{1/40}$.
Fixing $\varepsilon=k^{-1/20}$, we can apply Proposition 8.3 to $X$ with
$\varepsilon$ and $\sigma=k^{1/40}$ to conclude that every such set contains a
$X^{\prime}$ of size at least

$|X^{\prime}|\geq(1-2\varepsilon\sigma)k\geq(1-2k^{-1/40})k$ (84)

with $\varepsilon$-robust Freĭman dimension $d_{X}$, for some
$d_{X}\in\mathbb{N}$. Observe that (84) implies that the doubling of
$X^{\prime}$ is at most $2\sigma$:

$\sigma[X^{\prime}]=\frac{|X^{\prime}+X^{\prime}|}{|X^{\prime}|}\leq\frac{|X+X|}{|X^{\prime}|}\leq
2\sigma,$ (85)

for all sufficiently large $k$. We fix777Abusing notation to denote such a
mapping via the ′ symbol. one $X^{\prime}$ for each $X\in\mathcal{X}_{1}$, and
denote by $\mathcal{X}_{1}^{\prime}$ the collection of all such $X^{\prime}$.

As we remarked before, $X^{\prime}\mathbin{\hat{+}}X^{\prime}\subseteq
A_{p}^{\mathsf{c}}$ is implied by $X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}$ for each $X\in\mathcal{X}_{1}$. Therefore, we have the
bound

$\mathbb{P}\big{(}\exists\,X\in\mathcal{X}_{1}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}\big{)}\leq\mathbb{P}\big{(}\exists\,X^{\prime}\in\mathcal{X}_{1}^{\prime}:X^{\prime}\mathbin{\hat{+}}X^{\prime}\subseteq
A_{p}^{\mathsf{c}}\big{)}.$

Moreover, let $\mathcal{Y}(P)$ be the collection of subsets $Y\subseteq P$
with

$(1-2k^{-1/40})k\leq|Y|\leq k\qquad\text{and}\qquad\sigma[Y]\leq 2\sigma$ (86)

such that $Y$ has $\varepsilon$-robust Freĭman dimension $d_{Y}$ for some
$d_{Y}\geq\dim(P)$. We claim that we can take another union bound:

$\mathbb{P}(\exists\,X^{\prime}\in\mathcal{X}_{1}^{\prime}:X^{\prime}\mathbin{\hat{+}}X^{\prime}\subseteq
A_{p}^{\mathsf{c}})\leq\sum_{P\in\mathcal{P}(\mathbb{Z}_{n})}\mathbb{P}(\exists\,Y\in\mathcal{Y}(P):Y\mathbin{\hat{+}}Y\subseteq
A_{p}^{\mathsf{c}})$ (87)

where $\mathcal{P}(\mathbb{Z}_{n})$ is the collection of generalised
arithmetic progressions $P\subseteq\mathbb{Z}_{n}$ such that

$|P|\leq\exp(k^{1/5}).$ (88)

In order to prove (87), it is enough to show that, for every
$X^{\prime}\in\mathcal{X}_{1}^{\prime}$, there exists a generalised arithmetic
progression $P\in\mathcal{P}(\mathbb{Z}_{n})$ such that
$X^{\prime}\in\mathcal{Y}(P)$; we will do so by applying Corollary 8.4 with
$\kappa=2\sigma$. From this application, we will obtain a generalised
arithmetic progression $P\in\mathcal{P}(\mathbb{Z}_{n})$ such that

$\dim(P)\leq\dim_{\mathrm{F}}(X^{\prime})=d_{X}\qquad\text{ and }\qquad
X^{\prime}\subseteq P.$ (89)

The property $P\in\mathcal{P}(\mathbb{Z}_{n})$ follows from (82), as

$|P|\leq\exp(C^{\prime}\sigma^{4}(\log\sigma)^{2})k\leq\exp\big{(}C^{\prime}k^{1/10}(\log
k)^{2}\big{)}k\leq\exp\big{(}k^{1/5}\big{)},$ (90)

where we used that $\sigma=k^{1/40}$ in the second inequality, and in the last
one we used that $k$ is sufficiently large. We now confirm that we can apply
Corollary 8.4 as we want, by verifying that every
$X^{\prime}\in\mathcal{X}_{1}^{\prime}$ satisfies (81). The lower bound holds
because

$|X^{\prime}|\geq(1-2k^{-1/40})k\geq k^{1/10}\geq
C^{\prime}\sigma^{3}(\log\sigma)^{2},$

by (84) and using that $k$ is sufficiently large, whereas the upper bound in
(81) follows from

$\exp(C^{\prime}\sigma^{4}(\log\sigma)^{2})|X^{\prime}|\leq\exp(k^{1/5})\leq\exp((\log
n)^{2/5})<n,$

where we used (90), and that $k\leq(\log n)^{2}$ and $n$ is sufficiently
large.

We now claim that $X^{\prime}\in\mathcal{Y}(P)$, where
$P\in\mathcal{P}(\mathbb{Z}_{n})$ is the generalised arithmetic progression
given by applying Corollary 8.4 to $X^{\prime}\in\mathcal{X}_{1}^{\prime}$. To
see this, simply note that the conditions in (86) follow from (84) and (85),
and the $\varepsilon$-robust Freĭman dimension bound $d_{X}\geq\dim(P)$
follows from (89) and Proposition 8.3, so this completes the proof of (87).

In order to bound the term in the right-hand side of (87), we analyse the
contribution of each fixed $P\in\mathcal{P}(\mathbb{Z}_{n})$. Notice that if
$\mathcal{Y}(P)$ is empty, then the probability term is equal to 0, so we may
assume that $\mathcal{Y}(P)$ is non-empty. Rather than directly taking a union
bound over choices of $Y\in\mathcal{Y}(P)$, our final union bound is over a
collection of fingerprints $\mathcal{F}(P)$:

$\displaystyle\mathbb{P}(\exists\,Y\in\mathcal{Y}(P):Y\mathbin{\hat{+}}Y\subseteq
A_{p}^{\mathsf{c}})$
$\displaystyle\leq\mathbb{P}(\exists\,F\in\mathcal{F}(P):F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}})$ (91)
$\displaystyle\leq|\mathcal{F}(P)|\max_{F\in\mathcal{F}(P)}\mathbb{P}(F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}}).$ (92)

That is true as long as, for each $Y\in\mathcal{Y}(P)$, there exists
$F\in\mathcal{F}(P)$ such that $F\subseteq Y$; again we are using that
$F\mathbin{\hat{+}}F\subseteq Y\mathbin{\hat{+}}Y$. We claim that applying
Theorem 2.1 to $P$ with $\gamma=\gamma(\delta)$ (to be determined later) and
$m=2\sigma k$ yields such a collection of fingerprints $\mathcal{F}(P)$.

First, we define a candidate for $\mathcal{F}(P)$ which proves our claim, and
later we show that we can construct this candidate. Our candidate for
$\mathcal{F}(P)$ is defined as

$\mathcal{F}(P)=\bigcup_{Y\in\mathcal{Y}(P)}\mathcal{F}_{|Y|,m,\varepsilon}(P)$
(93)

where $\mathcal{F}_{|Y|,m,\varepsilon}(P)$ is the collection of fingerprints
given by Theorem 2.1. For $\mathcal{F}(P)$ to prove our claim, we must thus
show that, for each $Y\in\mathcal{Y}(P)$, there is an
$F\in\mathcal{F}_{|Y|,m,\varepsilon}(P)$ such that $F\subseteq Y$. By property
b of Theorem 2.1, it suffices for each $Y$ to have $\varepsilon$-robust
Freĭman dimension $d_{Y}\geq\dim(P)$ and $|Y+Y|\leq m=2\sigma k$. These,
however, hold for $Y$ by (86), and so we have that $\mathcal{F}(P)$ is a valid
candidate of fingerprints for $P$.

To confirm that we can apply Theorem 2.1 to $P$ as in (93), we need to check
that

$m\geq\frac{|Y|(\dim(P)+1)}{2}$ (94)

for all $Y\in\mathcal{Y}(P)$. (94) follows from

$\frac{|Y|(\dim(P)+1)}{2}\leq\frac{|Y|(\dim_{\mathrm{F}}(Y)+1)}{2}\leq|Y+Y|\leq
2\sigma k=m$

where the first inequality uses that $\dim(P)\leq\dim_{\mathrm{F}}(Y)$ by
definition of $\mathcal{Y}(P)$, the second inequality relies on Observation
8.2 and the third one on (86). Therefore, (93) is a valid definition for
$\mathcal{F}(P)$.

We proceed to give an upper bound to the right-hand side of (92). With the
goal of first bounding the size of $\mathcal{F}(P)$, define
$\Phi(P)=\max\\{|F|:F\in\mathcal{F}(P)\\}$ and note that, trivially,

$|\mathcal{F}(P)|\leq\sum_{q=0}^{\Phi(P)}{|P|\choose q}\leq(|P|+1)^{\Phi(P)}.$

Since, by (6) in Theorem 2.1, $|F|\leq C\varepsilon^{-1}\sqrt{m\log m}$ for
all $F\in\mathcal{F}(P)$, we can use that $m=2\sigma k$,
$\varepsilon=k^{-1/20}$ and $\sigma=k^{1/40}$ to obtain

$|\mathcal{F}(P)|\leq\exp(2Ck^{3/5}\,\log|P|)\leq\exp\big{(}k^{4/5}\big{)}$
(95)

where in the first inequality we used that $k$ is sufficiently large, and in
the last we used (90).

To obtain an upper bound on $\mathbb{P}(F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}})$ for all $F\in\mathcal{F}(P)$, we use (6), the lower bound
on $|F\mathbin{\hat{+}}F|$ given by Theorem 2.1:

$|F\mathbin{\hat{+}}F|\geq\frac{(1-\gamma)(\dim(P)+1)}{2}\min_{Y\in\mathcal{Y}(P)}|Y|.$

Since $\gamma=\gamma(\delta)$ is a constant and
$|Y|\geq(1-2\varepsilon\sigma)k$ for all $Y\in\mathcal{Y}(P)$ by (86), we
obtain

$\max_{F\in\mathcal{F}(P)}\mathbb{P}(F\mathbin{\hat{+}}F\subseteq
A_{p}^{\mathsf{c}})\leq(1-p)^{(1-2\gamma)(\dim(P)+1)k/2},$ (96)

as $k$ is sufficiently large. Replacing (95) and (96) back into (92) yields

$\mathbb{P}(\exists\,Y\in\mathcal{Y}(P):Y\mathbin{\hat{+}}Y\subseteq
A_{p}^{\mathsf{c}})\leq\exp(k^{4/5})(1-p)^{(1-2\gamma)(\dim(P)+1)k/2}.$ (97)

This will be our bound for each term in the right-hand side of (87).

Observe that (97) does not depend on the specific choice of $P$, only on its
size and dimension. Recalling that $|P|\leq\exp(k^{1/5})=:s$ for every
$P\in\mathcal{P}(\mathbb{Z}_{n})$ by (90), we can group terms in the right-
hand side of (87) based on $d=\dim(P)$ to deduce that, by (97), we have

$\mathbb{P}(\exists\,X\in\mathcal{X}_{1}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}})\leq\sum_{d=1}^{\infty}s(ns)^{d+1}\exp(k^{4/5})(1-p)^{(1-2\gamma)(d+1)k/2},$
(98)

where we have bounded the number of $d$-dimensional generalised arithmetic
progressions in $\mathbb{Z}_{n}$ with size at most $s$ by $s(ns)^{d+1}$.

It is therefore enough to prove that the right-hand side of (98) goes to $0$
as $n\to\infty$. Note that, as $k=(2+4\delta)\log_{\frac{1}{1-p}}n$, we have

$(1-p)^{k/2}=n^{-(1+2\delta)},$

which combined with a suitably small choice of $\gamma=\gamma(\delta)$,
implies that

$n^{d+1}(1-p)^{(1-2\gamma)(d+1)k/2}=n^{d+1-(1-2\gamma)(1+2\delta)(d+1)}\leq
n^{-\delta(d+1)}.$ (99)

The final observation is that it follows from $s=\exp(k^{1/5})$ that there is
$1>\nu>0$ such that

$s^{d+2}\exp(k^{4/5})\leq\exp\big{(}(d+1)(\log n)^{1-\nu}\big{)}$ (100)

since $k\leq 3(\log n)/p$ for $\delta<1/4$. The value of $\nu$ depends on the
specific exponent of the $\log n$ term in our choice of $p$. For instance,
$\nu=0.18$ works for $p\geq(\log n)^{-1/80}$.

Combining (99) with (100), we obtain, for sufficiently large $n$, the
following bound for (98):

$\sum_{d=1}^{\infty}s(ns)^{d+1}\exp(k^{4/5})(1-p)^{(1-2\gamma)(d+1)k/2}\leq\sum_{d=1}^{\infty}n^{-\delta
d/2}$

which goes to 0 as $n\to\infty$, as we wanted to show. ∎

###  8.2. Bounding the probability over choices in $\mathcal{X}_{2}$

Our goal is to show that the term corresponding to choices in
$\mathcal{X}_{2}$ tends to $0$ as $n\to\infty$. We emphasize that, in this
section, no new ideas, or even modification of previous, existing results, are
needed. We just need to use the following result of Green [17].

######  Proposition 8.5 ([17], see [18, Proposition 6.1]).

For every $k\in\mathbb{N}$ and $m\geq 2k-1$, there exists $r\in\mathbb{N}$
with

$r\leq\min\\{4m/k,k\\}\quad\text{ and }\quad
r\leq\frac{2m}{k}+\frac{1}{k}\binom{r}{2},$ (101)

such that

$\big{|}\mathcal{X}_{2}^{(m)}\big{|}\leq n^{r}k^{4k},$ (102)

where
$\mathcal{X}_{2}^{(m)}=\\{X\in\mathcal{X}_{2}:|X\mathbin{\hat{+}}X|=m\\}$.

With Proposition 8.5, we can take a union bound over each
$X\in\mathcal{X}_{2}$ to obtain

$\mathbb{P}\left(\exists\,X\in\mathcal{X}_{2}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}\right)\leq\sum_{m=k^{1+1/40}}^{\delta
k^{2}/10}\big{|}\mathcal{X}_{2}^{(m)}\big{|}\,(1-p)^{m}\to 0\quad\text{ as
}n\to\infty,$ (103)

and we prove the last step below.

###### Proof of (103).

First, we bound the $r$ in Proposition 8.5 using (101):

$r\leq\frac{2m}{k}+\frac{1}{k}\left(\frac{4m}{k}\right)^{2}\leq\frac{m}{k}\left(2+2\delta\right)$

since sets $X\in\mathcal{X}_{2}^{(m)}\subseteq\mathcal{X}_{2}$ satisfy
$m/k=\sigma[X]\leq\delta k/10$. Now, applying Proposition 8.5 to each
$\mathcal{X}_{2}^{(m)}$, we obtain that

$\big{|}\mathcal{X}_{2}^{(m)}\big{|}\leq n^{r}k^{4k}\leq
n^{(2+2\delta)m/k+(\log n)^{1/50}\log\log n}$ (104)

and the last inequality follows from $k\leq(\log n)^{51/50}$, which is implied
by $p\geq(\log n)^{-1/80}$.

Notice that it follows from $k=(2+4\delta)\log_{\frac{1}{1-p}}n$ that

$(1-p)^{m}=n^{-(2+4\delta)m/k}.$ (105)

Together with (104) and the fact that $m/k=\sigma[X]\geq k^{1/40}\geq(\log
n)^{1/40}$, (105) yields

$\big{|}\mathcal{X}_{2}^{(m)}\big{|}\,(1-p)^{m}\leq n^{-\delta m/k}$

from which the result follows by summing over all $k^{1+1/40}\leq m\leq\delta
k^{2}/10$. ∎

###  8.3. Bounding the probability over choices in $\mathcal{X}_{3}$

Similarly to the previous case, we start with a union bound

$\mathbb{P}\left(\exists\,X\in\mathcal{X}_{3}:X\mathbin{\hat{+}}X\subseteq
A_{p}^{\mathsf{c}}\right)\leq\sum_{m=\delta
k^{2}/10}^{k^{2}}\big{|}\mathcal{X}_{3}^{(m)}\big{|}\,(1-p)^{m},$ (106)

letting $\mathcal{X}_{3}^{(m)}$ be the sub-collection of $\mathcal{X}_{3}$
consisting of subsets $X\subseteq\mathbb{Z}_{n}$ with
$|X\mathbin{\hat{+}}X|=m$. We will need the following slight strengthening of
Proposition 5.1 of [18], here stated in a way that matches our notation:

######  Proposition 8.6.

Let $\delta>0$ be sufficiently small and let $\eta>0$. If $k\leq(\log
n)^{2-\eta}$ and $m\geq\delta k^{2}/10$, then

$\big{|}\mathcal{X}_{3}^{(m)}\big{|}\leq n^{(2+\delta+o(1))m/k},$

as $k\to\infty$, where
$\mathcal{X}_{3}^{(m)}=\\{X\in\mathcal{X}_{3}:|X\mathbin{\hat{+}}X|=m\\}$.

The proof of Proposition 8.6 is the same as the one given in [18]; we only
optimize constants and exponents. Therefore, we defer its presentation to
Appendix B.

###### Proof that (106) $\to 0$ as $n\to\infty$.

Observe that

$k\leq\frac{3\log n}{p}\leq(\log n)^{41/40}\leq(\log n)^{2-\eta},$

by our choice of $p\geq(\log n)^{-1/80}$. Hence, we can apply Proposition 8.6
to bound, for every $m\geq\delta k^{2}/10$, the size of
$\mathcal{X}_{3}^{(m)}$ by

$\big{|}\mathcal{X}_{3}^{(m)}\big{|}\leq n^{(2+\delta+o(1))m/k}\leq
n^{(2+2\delta)m/k}$

where the last inequality holds for large $k$. We can bound each term of (106)
by:

$\big{|}\mathcal{X}_{3}^{(m)}\big{|}\,(1-p)^{m}\leq
n^{(2+2\delta)m/k}n^{-(2-4\delta)m/k}\leq n^{-\delta m/k}.$

Summing over $m\geq\delta k^{2}/10$ yields the desired result. ∎

##  9\. The lower bound

In this section, we prove the lower bound in Theorem 1.1.

######  Theorem 9.1.

Let $n$ be a prime number and let $p=p(n)$ satisfy $1/2\geq p\geq n^{-o(1)}$.
The random Cayley sum graph $\Gamma_{p}$ of $\mathbb{Z}_{n}$ satisfies

$\alpha(\Gamma_{p})\geq\big{(}2+o(1)\big{)}\log_{\frac{1}{1-p}}n$

with high probability as $n\to\infty$.

The proof of this result is significantly easier than the upper bound. In
fact, using only the pseudorandom properties of $\Gamma_{p}$ is enough to
obtain $\alpha(\Gamma_{p})\geq\big{(}1/2+o(1)\big{)}(\log n)/p$ (see [1] and
[2, Corollary 2.2]). To improve the leading constant to $2$, we use both the
randomness (as opposed to only the pseudorandomness) and the fact that we can
restrict our attention to any sub-collection of potential independent sets in
$\Gamma_{p}$.

More precisely, for each $k\in\mathbb{N}$, we define $Z_{k}$ to be the random
variable counting all independent $k$-sets in $\Gamma_{p}$ with maximal
doubling, that is

$Z_{k}=\left|\left\\{X\in\mathcal{Z}_{k}:X\mathbin{\hat{+}}X\subset
A_{p}^{c}\right\\}\right|$ (107)

where

$\mathcal{Z}_{k}=\left\\{X\subseteq\mathbb{Z}_{n}:|X|=k,\,|X\mathbin{\hat{+}}X|=\binom{k}{2}\right\\}.$
(108)

If $Z_{k}>0$, then $\alpha(\Gamma_{p})\geq k$ regardless of the potential
independent $k$-sets that $Z_{k}$ overlooks.

In order to prove the lower bound, it is enough to show that
$\operatorname{Var}(Z_{k})=o(\mathbb{E}[Z_{k}]^{2})$ since

$\mathbb{P}(\alpha(\Gamma_{p})\geq k)\geq\mathbb{P}(Z_{k}>0)\geq
1-\frac{\operatorname{Var}(Z_{k})}{\mathbb{E}[Z_{k}]^{2}},$

by Chebyshev’s inequality. The first step is to estimate $\mathbb{E}[Z_{k}]$,
which we do by showing that $\mathcal{Z}_{k}$ is large and using linearity of
expectation.

######  Lemma 9.2.

For each $k\in\mathbb{N}$ such that $k=o(n^{1/4})$, we have

$|\mathcal{Z}_{k}|=\big{(}1-o(1)\big{)}\binom{n}{k}.$

###### Proof.

We will (equivalently) show that almost all $X\subseteq\mathbb{Z}_{n}$ with
$|X|=k$ satisfy ${|X\mathbin{\hat{+}}X|=\binom{k}{2}}$. Observe that if
$|X\mathbin{\hat{+}}X|<\binom{k}{2}$, then there are distinct
$x_{1},x_{2},x_{1}^{\prime},x_{2}^{\prime}\in X$ such that

$x_{1}+x_{2}=x_{1}^{\prime}+x_{2}^{\prime}.$

Motivated by that observation, define

$\mathcal{Q}=\big{\\{}\\{x_{1},x_{2},x_{1}^{\prime},x_{2}^{\prime}\\}\subseteq\mathbb{Z}_{n}:x_{1}+x_{2}=x_{1}^{\prime}+x_{2}^{\prime},\,\text{
and }x_{1},x_{2},x_{1}^{\prime},x_{2}^{\prime}\text{ are distinct}\big{\\}},$

and let $Y$ be a uniformly random $k$-set in $\mathbb{Z}_{n}$. Taking a union
bound over $\mathcal{Q}$ yields

$\mathbb{P}(Y\not\in\mathcal{Z}_{k})\leq\sum_{Q\in\mathcal{Q}}\mathbb{P}(Q\subseteq
Y)\leq n^{3}\bigg{(}\frac{k}{n}\bigg{)}^{4}=\frac{k^{4}}{n},$

where the second inequality is due to the choices of $x_{1},x_{2}$ and
$x_{1}^{\prime}$ determining $x_{2}^{\prime}=x_{1}+x_{2}-x_{1}^{\prime}$ for
$\\{x_{1},x_{2},x_{1}^{\prime},x_{2}^{\prime}\\}\in\mathcal{Q}$. Since
$k=o(n^{1/4})$, the lemma follows. ∎

The second lemma that we need to prove Theorem 9.1 gives a bound on
$\operatorname{Var}(Z_{k})$.

######  Lemma 9.3.

For every $k\in\mathbb{N}$ and $p=p(n)\in(0,1)$, we have

$\operatorname{Var}(Z_{k})\leq\mathbb{E}[Z_{k}]+\binom{n}{k}\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2}.$

The main step in the proof of Lemma 9.3 is to show, for every
$X\in\mathcal{Z}_{k}$, that

$\sum_{\begin{subarray}{c}Y\in\mathcal{Z}_{k}\\\ Y\sim
X\end{subarray}}(1-p)^{|(X\mathbin{\hat{+}}X)\cup(Y\mathbin{\hat{+}}Y)|}\leq\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2}$
(109)

where $Y\sim X$ if

$Y\neq X\qquad\text{ and
}\qquad(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\neq\emptyset.$ (110)

In order to do that, define

$\mathcal{I}(X,Y)=\big{\\{}Y^{\prime}\subseteq
Y:(X\mathbin{\hat{+}}X)\cap(Y^{\prime}\mathbin{\hat{+}}Y^{\prime})=\emptyset\big{\\}},$

and

$\mathcal{I}^{*}(X,Y)=\big{\\{}Y^{\prime}\in\mathcal{I}(X,Y):(y+Y^{\prime})\cap(X\mathbin{\hat{+}}X)\neq\emptyset\,\text{
for all }\,y\in Y\setminus Y^{\prime}\big{\\}}.$ (111)

The definition of $\mathcal{I}^{*}(X,Y)$ is motivated by the following lemma,
which gives an upper bound on
$\big{|}(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\big{|}$:

######  Lemma 9.4.

Let $k\in\mathbb{N}$ and $X,Y\in\mathcal{Z}_{k}$. If $Y\sim X$, then

$\big{|}(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\big{|}\leq\frac{k(k-t)}{2},$
(112)

where
$t=\min\big{\\{}|Y^{\prime}|:Y^{\prime}\in\mathcal{I}^{*}(X,Y)\big{\\}}.$

To prove Lemma 9.4, we will need the following simple observation about
graphs.

######  Observation 9.5.

Let $G$ be a graph with $k$ vertices. If all maximal independent sets of $G$
have at least $t$ vertices, then $G$ has at most $k(k-t)/2$ edges.

###### Proof.

Take $v\in V(G)$ to be a vertex of maximum degree, and $I_{v}\subseteq V(G)$
to be a maximal independent set containing $v$. Then,

$t\leq|I_{v}|\leq k-d(v)=k-\Delta(G).$

Thus, $\Delta(G)\leq k-t$, and the claimed bound follows. ∎

To deduce Lemma 9.4, we will apply Observation 9.5 to
$\Gamma_{X\mathbin{\hat{+}}X}[Y]$, the Cayley sum graph over
$X\mathbin{\hat{+}}X$ restricted to the vertex set $Y$.

###### Proof of Lemma 9.4.

We claim that

$\big{|}(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\big{|}=e(\Gamma_{X\mathbin{\hat{+}}X}[Y]),$
(113)

which not only implies that the collection $\mathcal{I}^{*}(X,Y)$ is exactly
the collection of maximal independent sets in
$\Gamma_{X\mathbin{\hat{+}}X}[Y]$, but also reduces the proof to applying
Observation 9.5 with $t$ to $\Gamma_{X\mathbin{\hat{+}}X}[Y]$. Therefore, we
first establish (113), and then the characterization of
$\mathcal{I}^{*}(X,Y)$.

To show (113), recall that, by the definition of the Cayley sum graph,
$y_{1}y_{2}\in\binom{\,Y}{2}$ is an edge of $\Gamma_{X\mathbin{\hat{+}}X}[Y]$
if and only if $y_{1}+y_{2}\in X\mathbin{\hat{+}}X$. We obtain equality by
observing that each sum in $Y\mathbin{\hat{+}}Y$ corresponds to exactly one
pair $y_{1}y_{2}\in\binom{\,Y}{2}$, since $|Y\mathbin{\hat{+}}Y|=\binom{k}{2}$
by $Y\in\mathcal{Z}_{k}$.

It follows from (113) that $\mathcal{I}(X,Y)$ corresponds to independent sets
in $\Gamma_{X\mathbin{\hat{+}}X}[Y]$. Moreover, for every
$Y^{*}\in\mathcal{I}^{*}(X,Y)$, we know that there are no
$Y^{\prime}\in\mathcal{I}(X,Y)$ such that $Y^{*}\subsetneq Y^{\prime}$ by the
condition in (111). Our definition of $t$ then corresponds to all maximal
independent sets in $\Gamma_{X\mathbin{\hat{+}}X}[Y]$ having at least $t$
vertices, so we can apply Observation 9.5 as desired. ∎

With Lemma 9.4 in hand, the proof of (109) now relies on an efficient count of
$Y\in\mathcal{Z}_{k}$ with $Y\sim X$, for each fixed $X\in\mathcal{Z}_{k}$.
Notice that $\mathcal{I}^{*}(X,Y)$ is not empty, as every graph has at least
one maximal independent set, so we can fix a set
$Y^{*}\in\mathcal{I}^{*}(X,Y)$ of minimum size. Our counting strategy is to
consider the choices for elements in $Y^{*}$ and then the choices for
$Y\setminus Y^{*}$; in fact, a trivial count of all sets
$Y^{*}\subseteq\mathbb{Z}_{n}$ suffices, so we only need to count the possible
elements in $Y\setminus Y^{*}$ efficiently.

In order to bound the choices for $Y\setminus Y^{*}$, notice that for every
$y\in Y\setminus Y^{*}$, we have
$(y+Y^{*})\cap(X\mathbin{\hat{+}}X)\neq\emptyset$ by (111). It follows that
there are $y^{*}\in Y^{*}$ and distinct $x_{1},x_{2}\in X$ such that
$y+y^{*}=x_{1}+x_{2}$, or, equivalently,

$Y\setminus Y^{*}\subseteq X\mathbin{\hat{+}}X-Y^{*}.$

We can therefore choose the elements of $Y\setminus Y^{*}$ from a set of size
at most

$|X\mathbin{\hat{+}}X-Y^{*}|\leq|X|^{2}|Y^{*}|\leq k^{3},$

so there are at most $k^{3s}$ choices for $Y\setminus Y^{*}$ if $s=|Y\setminus
Y^{*}|$. Bounding the number of choices for $Y^{*}$ by $\binom{n}{k-s}$ yields
the bound in (109), except for the $(1-p)^{2\binom{k}{2}-ks/2}$ term, which we
obtain by using Lemma 9.4.

We now have all the ingredients to prove Lemma 9.3.

###### Proof of Lemma 9.3.

Observe that, via standard calculations, we have that

$\operatorname{Var}(Z_{k})\leq\mathbb{E}[Z_{k}]+\sum_{X\in\mathcal{Z}_{k}}\sum_{\begin{subarray}{c}Y\in\mathcal{Z}_{k}\\\
Y\sim
X\end{subarray}}(1-p)^{|(X\mathbin{\hat{+}}X)\cup(Y\mathbin{\hat{+}}Y)|},$
(114)

where, recall, $Y\sim X$ was defined in (110). We therefore need to show that

$\sum_{\begin{subarray}{c}Y\in\mathcal{Z}_{k}\\\ Y\sim
X\end{subarray}}(1-p)^{|(X\mathbin{\hat{+}}X)\cup(Y\mathbin{\hat{+}}Y)|}\leq\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2}$
(115)

for each $X\in\mathcal{Z}_{k}$.

To prove (115), fix $X\in\mathcal{Z}_{k}$ and, for each $Y\in\mathcal{Z}_{k}$
with $Y\sim X$, choose a set $Y^{*}=Y^{*}(X,Y)$ of minimum size. If we group
the sets $Y$ by the size of their corresponding $Y^{*}$, we can count them by
first enumerating the choices for $Y^{*}$ and then the choices for $Y\setminus
Y^{*}$. For fixed $s=|Y\setminus Y^{*}|=k-|Y^{*}|$, there are at most
$\binom{n}{k-s}$ choices for $Y^{*}$, and there are at most $k^{3s}$ choices
for $Y\setminus Y^{*}$ since $Y\setminus Y^{*}\subseteq
X\mathbin{\hat{+}}X-Y^{*}$.

We then bound the size of the union in (115) by applying Lemma 9.4 to the pair
$(X,Y)$

$\big{|}(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\big{|}\leq\frac{ks}{2}$

which means that we can ignore the case $s=0$ because it would contradict
$Y\sim X$. A trivial inclusion-exclusion now yields the bound we need for the
size of the union:

$\big{|}(X\mathbin{\hat{+}}X)\cup(Y\mathbin{\hat{+}}Y)\big{|}=2\binom{k}{2}-\big{|}(X\mathbin{\hat{+}}X)\cap(Y\mathbin{\hat{+}}Y)\big{|}\geq
2\binom{k}{2}-\frac{ks}{2}.$ (116)

Replacing (116) and the above count of $Y$ for fixed $s$ into the left-hand
side of (115) gives

$\sum_{X\in\mathcal{Z}_{k}}\sum_{\begin{subarray}{c}Y\in\mathcal{Z}_{k}\\\
Y\sim
X\end{subarray}}(1-p)^{|(X\mathbin{\hat{+}}X)\cup(Y\mathbin{\hat{+}}Y)|}\leq\sum_{X\in\mathcal{Z}_{k}}\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2}.$

Trivially bounding the number of choices for $X\in\mathcal{Z}_{k}$ by
$\binom{n}{k}$ and plugging the result into (114) completes the proof. ∎

With Lemma 9.2 and Lemma 9.3, the proof of Theorem 9.1 is just checking that
the bounds match those of the statement.

###### Proof of Theorem 9.1.

Fix $p=p(n)$ satisfying $1/2\geq p\geq n^{-\delta/8}$ for some $\delta>0$, and
let $k=(2-2\delta)\log_{\frac{1}{1-p}}n$. It suffices to show that

$\frac{\operatorname{Var}(Z_{k})}{\mathbb{E}[Z_{k}]^{2}}\to 0\qquad\text{ as
}\qquad n\to\infty.$ (117)

First, we compute the expected value of $Z_{k}$ using Lemma 9.2 and linearity
of expectation:

$\mathbb{E}[Z_{k}]=\big{(}1-o(1)\big{)}\binom{n}{k}(1-p)^{\binom{k}{2}}\geq\frac{1}{2}\binom{n}{k}n^{-(1-\delta)(k-1)}\to\infty$
(118)

as $n\to\infty$, by our choice of $k$. Now, if we assume that

$\mathbb{E}[Z_{k}]\geq\binom{n}{k}\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2},$
(119)

then, by Lemma 9.3, we have $\operatorname{Var}(Z_{k})\leq 2\mathbb{E}[Z_{k}]$
and

$\frac{\operatorname{Var}(Z_{k})}{\mathbb{E}[Z_{k}]^{2}}\leq\frac{2}{\mathbb{E}[Z_{k}]}\to
0\qquad\text{ as }\qquad n\to\infty,$

by (118). We therefore assume that the converse of (119) holds.

Before we proceed, observe that applying the standard binomial inequality

$\binom{n}{k-s}\leq\left(\frac{k}{n}\right)^{s}\binom{n}{k}$

to the right-hand side of (119) yields

$\displaystyle\binom{n}{k}\sum_{s=1}^{k}k^{3s}\binom{n}{k-s}(1-p)^{2\binom{k}{2}-ks/2}$
$\displaystyle\leq\binom{n}{k}^{2}(1-p)^{2\binom{k}{2}}\sum_{s=1}^{k}k^{3s}\left(\frac{k}{n}\right)^{s}(1-p)^{-ks/2}$
$\displaystyle\leq
4\mathbb{E}[Z_{k}]^{2}\sum_{s=1}^{k}\left(\frac{k^{4}}{n^{\delta}}\right)^{s},$
(120)

where in the last inequality we used (118) with $n$ sufficiently large and
also

$(1-p)^{-ks/2}=n^{(1-\delta)s}$

because $k=(2-2\delta)\log_{\frac{1}{1-p}}n$.

By Lemma 9.3, our assumption that the converse of (119) holds, and (120), we
have

$\operatorname{Var}(Z_{k})\leq
8\mathbb{E}[Z_{k}]^{2}\sum_{s=1}^{k}\left(\frac{k^{4}}{n^{\delta}}\right)^{s}.$
(121)

Replacing (121) into (117), we conclude that the proof is complete if we show
that

$\sum_{s=1}^{k}\left(\frac{k^{4}}{n^{\delta}}\right)^{s}\to 0\qquad\text{ as
}\qquad n\to\infty.$

This is easily seen to be true when $k=o(n^{\delta/4})$, which holds for our
choice of $p\geq n^{-\delta/8}$. ∎

##  10\. Concluding remarks

The most important open question left by our work is extending the upper bound
in Theorem 1.1 to $p$ as small as possible. However, already when $p\leq(\log
n)^{-1}$, there is an obstacle that prevents any approach similar to ours from
working. To understand the barrier, consider the following approximate summary
of our strategy. We find a family
$\mathcal{S}=\\{F(X)+F(X):X\in{\mathbb{Z}_{n}\choose k}\\}$ of subsets of
$\mathbb{Z}_{n}$ of size $s$ (for some $s\in\mathbb{N}$) with the following
two properties:

  1. (1)

For each set $X\in{\mathbb{Z}_{n}\choose k}$, there exists $S\in\mathcal{S}$
with $S\subseteq X+X$.

  2. (2)

The family is small, that is, $\left|\mathcal{S}\right|\leq(1-p)^{-s}$.

Observe that each $S\in\mathcal{S}$ is of the form $F(X)+F(X)$ and has size
$s$, so we must trivially have $|F(X)|\geq\sqrt{s}$ for all
$X\in{\mathbb{Z}_{n}\choose k}$. Naively counting every set
$F\subseteq\mathbb{Z}_{n}$ with $|F|=\sqrt{s}$ when bounding the size of
$\mathcal{S}$, we obtain

$|\mathcal{S}|\geq\binom{n}{\sqrt{s}}\approx\exp(\sqrt{s}\log n).$ (122)

In our proof, we show that we can choose $F$ inside a small generalised
arithmetic progression $P$, thus replacing the $\log n$ term in (122) with
$\log|P|$. However, even if we could find such a set $P$ with
$|P|=O(\sqrt{s})$, we could not improve the bound in (122) beyond
$\exp(\sqrt{s})$.

Combining this lower bound on the size of $\mathcal{S}$ with the upper bound
that we require in property (2) gives

$\exp(\sqrt{s})\leq|\mathcal{S}|\leq(1-p)^{-s},$

which implies that $s\geq p^{-2}$. Now, consider any
$X\in{\mathbb{Z}_{n}\choose k}$ with $\sigma[X]=O(1)$: the corresponding set
$S\in\mathcal{S}$ satisfies $S\subseteq X+X$ and therefore

$p^{-2}\leq s=|S|\leq|X+X|\leq O(k).$

As $k$ is the upper bound we are trying to prove for $\alpha(\Gamma_{p})$, it
follows that the best we can hope for this approach is, for some constant
$C>2$,

$\alpha(\Gamma_{p})\leq C\max\\{p^{-2},p^{-1}\log n\\},$ (123)

where the second term in the maximum is the lower bound that we proved in
Section 9.

While (123) would still be far from what we believe is true for $p$ much
smaller than $(\log n)^{-1}$, proving it would still be very interesting; even
if we optimized our approach, we could not get close to proving (123) for all
$p\geq(\log n)^{-1}$.

Improving the upper bound is related to the following problem due to Shachar
Lovett: is there a list of $2^{n^{O(1)}}$ subsets of $\mathbb{F}_{2}^{n}$ with
density at least $1/100$ such that, whenever $X\subseteq\mathbb{F}_{2}^{n}$
has density at least $1/3$, $X+X$ contains one of these sets? This question is
relevant because we can embed sets $X\subseteq\mathbb{Z}_{n}$ with
$\sigma[X]=O(1)$ as dense subsets of an Abelian group using Ruzsa’s model
lemma. Now, if the positive answer to this problem does not rely too much on
the details of the setting (the structure of $\mathbb{F}_{2}^{n}$ and the
particular densities of the subsets) and a similar list exists for any Abelian
group, then we could take a union bound over its elements and hope to
circumvent (123) in the bounded doubling setting.

We would also like to highlight that for very small $p$, close to $n^{-1}\log
n$, upper and lower bounds for $\alpha(\Gamma_{p})$ follow from a theorem of
Bourgain [8]; this is the only other result that we are aware of in the regime
$p=o(1)$. Another way to obtain an upper bound in this range is as follows:
observe that the first eigenvalue of $\Gamma_{p}$ is highly concentrated
around $np$, and that we can use elementary Fourier analysis to show that its
second eigenvalue is, with high probability, at most $O(\sqrt{np\log n})$
(see, for example, [1, Sections 3.1 and 3.2]). Using Hoffman’s ratio bound, we
then obtain

$\alpha(\Gamma_{p})\leq\bigg{(}\frac{Cn\log n}{p}\bigg{)}^{1/2},$

which matches $\alpha(G(n,p))$ up to a logarithmic factor if $p\approx
n^{-1}\log n$.

Another interesting open question is to determine the minimum number of
translates necessary to obtain the correct leading constant of $d+1$ in
Freĭman’s lemma. This is closely related to the question asked (and partially
settled) by Bollobás, Leader, and Tiba [6] on whether three translates suffice
to obtain the Cauchy–Davenport lower bound for two sets
$A,B\subseteq\mathbb{Z}_{n}$. Even though their question was recently resolved
by Fox, Luo, Pham, and Zhou [13] in the affirmative, it is not clear what is
the truth in higher dimensions, even in the simpler case of $A=B$. We
conjecture the following:

######  Conjecture 10.1.

There exists $C>0$ such that the following holds. For all $d\in\mathbb{N}$ and
all finite sets $X\subseteq\mathbb{R}^{d}$ of full rank, $X$ contains a subset
$T$ such that $|T|\leq Cd$ and

$|X+T|\geq(d+1)|X|-d^{C}.$ (124)

The best negative result we have for this problem is given by the following
simple construction. Let $d\geq 3$, and let $\\{e_{1},e_{2},\ldots,e_{d}\\}$
be the canonical basis of $\mathbb{R}^{d}$. Consider

$X=P+\\{0,e_{1},\ldots,e_{d-1}\\}\qquad\text{ where }\qquad
P=\\{0,e_{d},2e_{d},\ldots,ke_{d}\\}$

for some $k\in\mathbb{N}$. It is not hard to show that the following holds for
this example: for every $\gamma>0$, there is $c=c(\gamma)>0$ such that if
$T\subseteq X$ with $|T|<(2-\gamma)d$, then

$|X+T|\leq(1-c)(d+1)|X|.$

Theorem 1.3 is actually not the best result that we know towards 10.1. While
we were finishing the writing of this paper, Gowers, Green, Manners, and Tao
[16] made a breakthrough and proved Marton’s conjecture, also known as the
Polynomial Freĭman–Ruzsa conjecture for finite fields. In a previous work,
Green, Manners, and Tao [20, Corollary 1.12] proved that a positive answer to
Marton’s conjecture would imply what is known as the “weak” Polynomial
Freĭman–Ruzsa conjecture for $\mathbb{Z}^{d}$: for every
$X\subseteq\mathbb{Z}^{d}$ with $\sigma[X]\leq\sigma$, there exists
$X^{\prime}\subseteq X$ such that

$\operatorname{rank}(X^{\prime})\leq C\log\sigma\qquad\text{ and
}\qquad|X^{\prime}|\geq\sigma^{-C}|X|$

for some absolute constant $C>0$.

Combining this weak version of PFR in $\mathbb{Z}^{d}$ with a variation of the
argument we developed in Section 6, we can prove a version of Theorem 1.3 that
attains a bound of the form $|X+T|\geq(d+1-O(\log d))|X|$ at the cost of
$d^{C}$ translates, for $C>0$ an absolute constant. We develop these ideas in
a separate work, dedicated to answering a question of Green and Morris [18]
about the number of subsets of $\\{1,\ldots,n\\}$ with prescribed doubling,
where we require that both the number of translates is a polynomial in $d$,
and the leading constant is at least $1-o(1)$. Nonetheless, we think that 10.1
should not depend on results as deep as variants of PFR.