The final future research direction we would like to highlight is the
extension of our result to other groups. During the preparation of this paper,
it came to our knowledge that Conlon, Fox, Pham, and Yepremyan [11] proved an
upper bound of $O(\log N\log\log N)$ for the clique/independence number in the
uniform random Cayley graph of any group $G$, where $N$ is the order of $G$.
As there are some groups, like $\mathbb{F}_{2}^{n}$, where this is tight up to
the constant factor, their result can be seen as a generalisation of Green’s
theorem [17] about $\alpha(\Gamma_{1/2})$.

Moreover, over certain groups, like $\mathbb{F}_{5}^{n}$, they can show that
there exist Cayley graphs which have both clique and independence number
$(2+o(1))\log N$, even though a uniform random Cayley graph has clique number
$O(\log N\log\log N)$. It would be interesting if our methods, combined with
their techniques, can extend these results to sparser graphs.

## Acknowledgements

We would like to greatly thank Rob Morris for carefully reading the paper, and
for the many improvements and corrections he suggested. Without his support,
this work would not have its current form. We would also like to thank Zach
Hunter for carefully reading the paper, pointing out mistakes and giving
suggestions. Finally, we are grateful to Lucas Aragão for helpful discussions,
and to David Conlon, Huy Tuan Pham and Shachar Lovett for comments on the
manuscript.

This study was financed in part by the Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior, Brasil (CAPES).

## References

  * Alon [2007] N. Alon.  Large sets in finite fields are sumsets.  _J. Number Theory_ , 126(1):110–118, 2007.
  * Alon, Krivelevich, and Sudakov [1999] N. Alon, M. Krivelevich, and B. Sudakov.  List coloring of random and pseudo-random graphs.  _Combinatorica_ , 19(4):453–472, 1999.
  * Berg and Henk [2019] S. Lennart Berg and M. Henk.  Discrete analogues of John’s theorem.  _Mosc. J. Comb. Number Theory_ , 8:367–378, 2019.
  * Bollobás [1985] B. Bollobás.  _Random graphs_.  Academic Press, Inc., London, 1985.
  * Bollobás and Leader [1991] B. Bollobás and I. Leader.  Compressions and isoperimetric inequalities.  _J. Combin. Theory Ser. A_ , 56(1):47–62, 1991\.
  * Bollobás, Leader, and Tiba [2022a] B. Bollobás, I. Leader, and M. Tiba.  Large sumsets from small subsets, 2022a.  arXiv:2204.07559.
  * Bollobás, Leader, and Tiba [2022b] B. Bollobás, I. Leader, and M. Tiba.  Large sumsets from medium-sized subsets, 2022b.  arXiv:2206.09366.
  * Bourgain [1987] J. Bourgain.  Ruzsa’s problem on sets of recurrence.  _Israel J. Math._ , 59(2):150–166, 1987.
  * Campos [2020] M. Campos.  On the number of sets with a given doubling constant.  _Israel J. Math._ , 236(2):711–726, 2020.
  * Chang [2002] M. Chang.  A polynomial bound in Freiman’s theorem.  _Duke Math. J._ , 113(3):399–419, 2002.
  * [11] D. Conlon, J. Fox, H. T. Pham, and L. Yepremyan.  On the clique number of random Cayley graphs and related topics.  Manuscript.
  * Cwalina and Schoen [2013] K. Cwalina and T. Schoen.  A linear bound on the dimension in Green–Ruzsa’s theorem.  _J. Number Theory_ , 133:1262–1269, 2013.
  * Fox, Luo, Pham, and Zhou [2024] J. Fox, S. Luo, H. T. Pham, and Y. Zhou.  Small subsets with large sumset: Beyond the Cauchy–Davenport bound.  _Comb. Probab. Comput._ , pages 1–21, 2024.
  * Freĭman [1959] G. A. Freĭman.  The addition of finite sets. I.  _Izv. Vysš. Učebn. Zaved. Matematika_ , (6):202–213, 1959.
  * Freĭman [1999] G. A. Freĭman.  Structure theory of set addition.  _Astérisque_ , (258):xi, 1–33, 1999.
  * Gowers, Green, Manners, and Tao [2023] W. T. Gowers, B. Green, F. Manners, and T. Tao.  On a conjecture of Marton, 2023.  arXiv:2311.05762.
  * Green [2005] B. Green.  Counting sets with small sumset, and the clique number of random Cayley graphs.  _Combinatorica_ , 25(3):307–326, 2005.
  * Green and Morris [2016] B. Green and R. Morris.  Counting sets with small sumset and applications.  _Combinatorica_ , 36(2):129–159, 2016.
  * Green and Tao [2006] B. Green and T. Tao.  Compressions, convex geometry and the Freiman-Bilu theorem.  _Q. J. Math._ , 57(4):495–504, 2006.
  * Green, Manners, and Tao [2023] B. Green, F. Manners, and T. Tao.  Sumsets and entropy revisited, 2023.  arXiv:2306.13403.
  * Janson, Łuczak, and Rucinski [2000] S. Janson, T. Łuczak, and A. Rucinski.  _Random graphs_.  Wiley-Interscience, New York, 2000.
  * Jing and Mudgal [2023] Y. Jing and A. Mudgal.  Kemperman’s inequality and Freiman’s lemma via few translates, 2023\.  arXiv:2307.03066.
  * Morris, Samotij, and Saxton [2024] R. Morris, W. Samotij, and D. Saxton.  An asymmetric container lemma and the structure of graphs with no induced $4$-cycle.  _J. Eur. Math. Soc. (JEMS)_ , 26(5):1655–1711, 2024.
  * Sanders [2013] T. Sanders.  The structure theory of set addition revisited.  _Bull. Am. Math. Soc._ , 50(1):93–127, 2013.
  * Schoen [2011] T. Schoen.  Near optimal bounds in Freiman’s theorem.  _Duke Math. J._ , 158(1):1–12, 2011.
  * Shao [2019] X. Shao.  On an almost all version of the Balog-Szemerédi-Gowers theorem.  _Discrete Anal._ , 2019.  Paper No. 12, 18.
  * Tao and Vu [2006] T. Tao and V. Vu.  _Additive combinatorics_ , volume 105.  Cambridge University Press, Cambridge, 2006.
  * Tao and Vu [2008] T. Tao and V. Vu.  John-type theorems for generalized arithmetic progressions and iterated sumsets.  _Adv. Math._ , 219:428–449, 2008.
  * van Hintum and Keevash [2024] P. van Hintum and P. Keevash.  Sharp bounds for a discrete John’s theorem.  _Combinatorics, Probability and Computing_ , page 1–3, 2024.
  * Wang and Wang [1977] D. L. Wang and P. Wang.  Discrete isoperimetric problems.  _SIAM J. Appl. Math._ , 32(4):860–870, 1977.

##  Appendix A Chang’s theorem for $\mathbb{Z}_{n}$

This appendix is devoted to the proof of Corollary 8.4, the variant of Chang’s
theorem that we used in the proof of Theorem 1.1. See 8.4

We rely on two theorems to prove Corollary 8.4: Cwalina and Schoen’s
strengthening of the Green–Ruzsa theorem (Freĭman’s theorem for general
Abelian groups) [12] and the discrete John’s theorem of Tao and Vu [28]. To
state these two results, we need some auxiliary definitions. As in [12],
define a coset progression to be a set of the form $P+H$, where $H$ is a
subgroup of $G$ and $P$ is a generalised arithmetic progression. Moreover, the
dimension of $P+H$ is $\dim(P)$, we say that a coset progression is proper if
(a) $P$ is proper, and (b) $|P+H|=|P|\,|H|$. We say that $P+H$ is $2$-proper
if $(P+P)+H$ is proper.

######  Theorem A.1 (Cwalina and Schoen [12, Theorem 4]).

There exists $C^{\prime}>0$ such that the following holds. Let $G$ be an
Abelian group, and let $X\subseteq G$ be a finite set with
$\sigma[X]\leq\kappa$. Either there exists a proper coset progression $P+H$
such that

$X\subseteq P+H,\quad\dim(P+H)\leq 2\kappa+1\quad\text{ and
}\quad|P+H|\leq\exp(C^{\prime}\kappa^{4}(\log(\kappa+2))^{2})|X|,$

or $X$ is fully contained in at most $C^{\prime}\kappa^{3}(\log\kappa)^{2}$
cosets, whose total cardinality is bounded by
$\exp(C^{\prime}\kappa^{4}(\log(\kappa+2))^{2})|X|$, of some subgroup of $G$.

As our group of interest is $\mathbb{Z}_{n}$, a proper coset progression $P+H$
is either all of $\mathbb{Z}_{n}$, or simply a proper generalised arithmetic
progression $P+0=P$. We also need a lemma by the same authors to obtain, from
a $d$-dimensional coset progression $P+H$, a $2$-proper coset progression that
contains $P+H$, has dimension at most $d$, and whose size is not much larger
than $|P+H|$.

######  Lemma A.2 (Cwalina and Schoen [12, Lemma 6]).

There exists $C^{\prime}>0$ such that the following holds. Suppose that $P+H$
is a $d$-dimensional coset progression in an Abelian group $G$. Then there
exists a $2$-proper coset progression $P^{\prime}+H^{\prime}$ such that

$P+H\subseteq P^{\prime}+H^{\prime},\qquad\dim(P^{\prime}+H)\leq
d,\qquad\text{ and }\qquad|P^{\prime}+H^{\prime}|\leq
d^{C^{\prime}d^{2}}|P+H|.$

These two results enable us to give an overview of the (somewhat standard)
proof of Corollary 8.4. First, we apply Theorem A.1 to $X$. Using (81) and
Lemma A.2, we will show that this application yields a small $2$-proper
generalised arithmetic progression $P\subseteq\mathbb{Z}_{n}$ such that
$X\subseteq P$. However, the bound on $d=\dim(P)$ is not strong enough for our
purposes, so we use it instead to define a Freĭman isomorphism $\phi:P\to
P_{d}\subseteq\mathbb{Z}^{d}$ in the natural way.

Restricting $P_{d}$ to an $r=\dim_{\mathrm{F}}(X)$ dimensional subspace, then,
yields an $r$-dimensional _convex_ progression, which is a set of the form
$\mathcal{C}=K\cap\mathbb{Z}^{d}$. In this definition,
$K\subseteq\mathbb{R}^{d}$ is a convex set of rank $r\leq d$. At this point,
we use Tao and Vu’s discrete John’s theorem [28] (Theorem A.3 below) to obtain
a small generalised arithmetic progression $P^{\prime}\subseteq\mathbb{Z}^{d}$
such that $\mathcal{C}\subseteq P^{\prime}$ and $\dim(P^{\prime})\leq r$. We
complete the proof by taking the progression
$\phi^{-1}(P^{\prime})\subseteq\mathbb{Z}_{n}$.

The above sketch is not quite right for two reasons. The first is that
$\phi^{-1}$ may not be defined for every element in $P^{\prime}$, but the
linearity of the mapping allows us to extend it to all of $\mathbb{Z}^{d}$.
The second reason is that the statement of Theorem A.3 requires the convex
progression to be (centrally) symmetric, i.e. $\mathcal{C}=-\mathcal{C}$. We
amend this by applying it instead to $\mathcal{C}-\mathcal{C}$, bounding its
size by $|P-P|\leq 2^{d}|P|$, and its dimension by that of the same
$d^{\prime}$-dimensional subspace that contains $\mathcal{C}$.

######  Theorem A.3 (Tao and Vu [28, Theorem 1.6, Lemma 3.3]).

There exists $C^{\prime}>0$ such that the following holds. Let
$d,r\in\mathbb{N}$ with $r\leq d$. For any $r$-dimensional symmetric convex
progression $\mathcal{C}\subseteq\mathbb{Z}^{d}$, there exists a generalised
arithmetic progression $P\subseteq\mathbb{Z}^{d}$ such that

$\mathcal{C}\subseteq P,\qquad|P|\leq
r^{C^{\prime}r^{2}}|\mathcal{C}|\qquad\text{ and }\qquad\dim(P)\leq
r=\dim(\mathcal{C}).$

The bound for the size of the generalised arithmetic progression in Theorem
A.3 has since been improved [3, 29], but the one by Tao and Vu [28] suffices
for our purposes. Their statement crucially defines the convex progression on
an arbitrary lattice $\Lambda$ over $\mathbb{R}^{d}$, rather than
$\mathbb{Z}^{d}$. This allows us to avoid the full rank requirement $r=d$ in
their original result, and take $r\leq d$ as in Theorem A.3 by first setting
$\Lambda=\mathcal{H}\cap\mathbb{Z}^{d}$, where $\mathcal{H}$ is an
$r$-dimensional subspace containing $\mathcal{C}$. With this lattice, we then
take a suitable linear isomorphism $f$ and apply their original result to
$\mathcal{C}^{\prime}=f(\mathcal{C})$ with $\Lambda^{\prime}=f(\Lambda)$ and
$\mathbb{R}^{r}=f(\mathcal{H})$.

Using these results, we can now prove Corollary 8.4.

###### Proof of Corollary 8.4.

As all the subgroups of $\mathbb{Z}_{n}$ are trivial when $n$ is a prime, we
claim that we cannot obtain the second case when applying Theorem A.1 to $X$.
Observe that none of the cosets obtained in the second outcome can be
$\mathbb{Z}_{n}$ itself. The reason for that is that a single one of those
cosets would, by (81), exceed the total cardinality bound given in Theorem A.1
if $C>C^{\prime}$ is sufficiently large:

$|\mathbb{Z}_{n}|=n>\exp(C^{\prime}\kappa^{4}(\log(\kappa+2))^{2})|X|.$

The claim follows by noting that the cosets also cannot all be of the form
$a\in\mathbb{Z}_{n}$, since their total number is bounded by
$C^{\prime}\kappa^{3}(\log\kappa)^{2}$, and, by (81), this is insufficient to
cover $X$.

We have shown that we always get the first outcome of Theorem A.1 under our
assumptions, so applying it to $X$ yields a proper coset progression
$P^{\prime\prime}+H\subseteq\mathbb{Z}_{n}$ such that

$X\subseteq P^{\prime\prime}+H,\qquad\dim(P^{\prime\prime})\leq
2\kappa+1\qquad\text{ and
}\qquad|P^{\prime\prime}+H|\leq\exp(C\kappa^{4}(\log\kappa)^{2})|X|,$

where we used that $\kappa\geq 2$ and that $C>C^{\prime}$ is appropriately
large. Applying now Lemma A.2 to $P^{\prime\prime}+H$ gives a $2$-proper coset
progression $P^{\prime}+H^{\prime}\subseteq\mathbb{Z}_{n}$ such that

$X\subseteq P^{\prime}+H^{\prime},\quad d=\dim(P^{\prime})\leq
2\kappa+1\quad\text{ and
}\quad|P^{\prime}+H^{\prime}|\leq\exp(C\kappa^{4}(\log\kappa)^{2})|X|,$ (125)

again by $C>C^{\prime}$. Moreover, $H^{\prime}=\\{0\\}$ because
$H^{\prime}=\mathbb{Z}_{n}$ is impossible by (81):

$\exp(C\kappa^{4}(\log\kappa)^{2})|X|<n=|P^{\prime}+\mathbb{Z}_{n}|,$

so we will write simply $P^{\prime}$ for $P^{\prime}+H^{\prime}$.

Let $\phi:P^{\prime}\to P^{\prime}_{d}\subseteq\mathbb{Z}^{d}$ be the function
defined by

$\phi(y)=(w^{(y)}_{1},\ldots,w^{(y)}_{d})\quad\text{ where }\quad
y=a_{0}+\sum_{i=1}^{d}w_{i}^{(y)}a_{i}$

and

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

Since $P^{\prime}$ is $2$-proper, we know that $\phi$ is a Freĭman
isomorphism; this and $X\subseteq P^{\prime}$ imply that so is
$\phi|_{X}:X\to\phi(X)$. Let $X_{d}=\phi(X)$ and assume without loss of
generality (by translating $\phi$ if necessary) that $0\in X_{d}$. If we
define $\mathcal{H}$ to be the minimal subspace that contains $X_{d}$, then
$\mathcal{C}^{\prime}=\mathcal{H}\cap P^{\prime}_{d}$ is a convex progression
and $\mathcal{C}=\mathcal{C}^{\prime}-\mathcal{C}^{\prime}$ is a symmetric
convex progression satisfying $\mathcal{C}^{\prime}\subseteq\mathcal{C}$. We
can therefore apply Theorem A.3 to $\mathcal{C}$ and obtain a generalised
arithmetic progression $P_{d}\subseteq\mathbb{Z}^{d}$ which, we claim,
satisfies

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

The containment $X_{d}\subseteq P_{d}$ follows from
$X_{d}\subseteq\mathcal{C}^{\prime}\subseteq\mathcal{C}\subseteq P_{d}$, where
the last step is given by Theorem A.3. In order to bound the dimension of
$P_{d}$, let $d_{\mathcal{C}}=\dim(\mathcal{C})$ and observe that

$\dim(P_{d})\leq d_{\mathcal{C}}\leq\dim(\mathcal{H})\leq\dim_{\mathrm{F}}(X)$
(127)

by Theorem A.3, $\mathcal{C}\subseteq\mathcal{H}$ and the definition of
$\mathcal{H}$ as the minimal subspace containing $X_{d}$. Finally, to obtain
the claimed bound on the size of $P_{d}$, we first use that, by Theorem A.3,

$|P_{d}|\leq
d_{\mathcal{C}}^{C^{\prime}d_{\mathcal{C}}^{2}}|\mathcal{C}|\leq\exp(C\kappa^{2}\log\kappa)|\mathcal{C}|$
(128)

where we used that $d_{\mathcal{C}}\leq d\leq 2\kappa+1$ by (125) and that
$C>C^{\prime}$ is sufficiently large. The second step is showing that the size
of $\mathcal{C}$ is at most

$|\mathcal{C}|=|\mathcal{C}^{\prime}-\mathcal{C}^{\prime}|\leq|P_{d}^{\prime}-P_{d}^{\prime}|\leq
2^{d}|P_{d}^{\prime}|\leq\exp(C\kappa^{4}(\log\kappa)^{2})|X|,$ (129)

which is due first to $\mathcal{C}^{\prime}\subseteq P_{d}^{\prime}$, and then
by taking a slightly larger $C$ than previous occurrences and using (125).
Combining (128) and (129) yields the desired bound on $|P_{d}|$ for a yet
slightly larger value of $C$, and completes the proof of (126).

It remains to define a generalised arithmetic progression
$P\subseteq\mathbb{Z}_{n}$ from $P_{d}\subseteq\mathbb{Z}^{d}$. Observe that
$\phi^{-1}$ is linear (or affine), so we can extend it to obtain a
$\psi:\mathbb{Z}^{d}\to\mathbb{Z}_{n}$ which satisfies

$\psi|_{X_{d}}=(\phi|_{X})^{-1}.$ (130)

Hence, $P=\psi(P_{d})$ is a (not necessarily proper) generalised arithmetic
progression 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),$

by (126), the linearity of $\psi$ and (130). This is exactly (82), so the
proof is complete. ∎

##  Appendix B Counting sets with large doubling

Recall that $n$ is a large prime and that we are dealing with sets
$X\subseteq\mathbb{Z}_{n}$ of size $k$. We restate the result which we aim to
prove for the reader’s convenience: See 8.6

The proof of Proposition 8.6 is essentially identical to that of [18,
Proposition 5.1], and to obtain the statement above we only need to optimize
the dependencies between the parameters. Before proceeding, we recall a key
definition from [18]:

######  Definition B.1.

A set $\\{x_{1},\ldots,x_{d}\\}\subseteq\mathbb{Z}_{n}$ is $M$-dissociated if
$\sum_{i=1}^{d}\lambda_{i}x_{i}\neq 0$ for every
$(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}^{d}\setminus\\{0\\}$ such that
$\sum_{i=1}^{d}|\lambda_{i}|\leq M$.

It is useful to understand this notion as an analogue of linear independence
for elements of $\mathbb{Z}_{n}$ taking coefficients in $\mathbb{Z}$, with a
restriction on the sum of their magnitudes. The first result that we need to
optimize is Lemma B.2, a slight strengthening of [18, Lemma 5.3].

######  Lemma B.2.

For every sufficiently small $\delta>0$ and $\eta>0$, the following holds. Fix
a large prime $n$ and $M=(\log n)/(\log\log n)^{4}$. If $k\leq(\log
n)^{2-\eta}$ and $m\geq\delta k^{2}/10$, then any $M$-dissociated subset of
$X\in\mathcal{X}_{3}^{(m)}$ has size at most $\big{(}2+\delta+o(1)\big{)}m/k$,
as $k\to\infty$.

We will begin by giving an overview of the proof from [18], alongside some
useful definitions of our own. Whenever there is
$(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{Z}^{d}$ such that
$x=\sum_{i=1}^{d}\lambda_{i}x_{i}$ and $\sum_{i=1}^{d}|\lambda_{i}|\leq M$, we
will say that $x$ is in the $M$-span of $\\{x_{1},\dots,x_{d}\\}$. In that
same situation, we will say that $x$ can be written as an $M$-bounded
combination of $\\{x_{1},\ldots,x_{d}\\}$.

The proof starts by fixing the value of $M=(\log n)/(\log\log n)^{4}$ and any
$M$-dissociated set $D=\\{x_{1},\ldots,x_{d}\\}\subseteq X$. We define
$G^{\prime}$ to be the graph with vertex set $\mathbb{Z}_{n}$ and edges
between a pair of vertices if their difference can be written as $\pm x_{i}\pm
x_{j}$ for some $i,j\in\\{1,\ldots,d\\}$. The graph $G^{\prime}$ is useful
because of the following observation:

######  Observation B.3.

For each $a\in\mathbb{Z}_{n}$, let $V_{a}\subseteq V(G^{\prime})$ denote its
connected component in $G^{\prime}$. Every element $b\in V_{a}$ can be
expressed as $b=a+\sum_{j=1}^{d}\lambda_{j}x_{j}$ with
$\sum_{j=1}^{d}|\lambda_{j}|\leq 2\operatorname{diam}(V_{a})$.

###### Proof.

Take $b\in V_{a}$, and consider any shortest path $P$ connecting $a$ to $b$ in
$G^{\prime}$. Observe that

$b-a=\sum_{j=1}^{d}(\lambda_{j}^{+}-\lambda_{j}^{-})x_{j}$

where $\lambda_{j}^{+},\lambda_{j}^{-}$ count respectively the number of times
$x_{j},-x_{j}$ appear as terms in $P$. Then,

$\sum_{j=1}^{d}\big{(}|\lambda_{j}^{+}|+|\lambda_{j}^{-}|\big{)}\leq 2|P|\leq
2\operatorname{diam}(V_{a})$

where the last step follows from $P$ being a shortest path in $V_{a}$. ∎

Having thus related the span of $D$ with the diameter of connected components
in $G^{\prime}$, we will decompose $G=G^{\prime}[X]$ using the following
lemma, also from [18], with $\Delta=k^{1/2}\log k$:

######  Lemma B.4 ([18, Lemma 5.4]).

Let $G$ be a graph with vertex set $V(G)$ and let $\Delta>1$. There exists a
partition $V(G)=X_{*}\cup X_{1}\cup\cdots\cup X_{t}$ such that

  1. (1)

$|X_{*}|\leq 32(v(G)/\Delta)^{2}$.

  2. (2)

$e(X_{i},X_{j})=0$ for every $i\neq j$.

  3. (3)

The diameter of $G[X_{i}]$ is at most $\Delta$ for every
$i\in\\{1,\ldots,t\\}$.

Applying Lemma B.4 to $G$ yields a partition $X=X_{*}\cup X_{1}\cup\cdots\cup
X_{t}$ such that

  1. (i)

if $X_{i}\neq X_{j}$, then $X_{i}+D$ and $X_{j}+D$ are disjoint, and

  2. (ii)

every $X_{i}$ has a $y_{i}\in X_{i}$ such that $X_{i}-y_{i}$ is contained in
the $2\Delta$-span of $D$.

To see that property (i) holds, notice that if $X_{i}+D$ and $X_{j}+D$
intersect, then there is an edge of $G$ connecting $X_{i}$ and $X_{j}$,
contradicting item (2) of Lemma B.4. Property (ii), on the other hand, follows
directly from an application of Observation B.3 to $X_{i}$, the diameter of
which is bounded by item (3) in Lemma B.4.

To combine these two properties into a proof of Lemma B.2, notice that the
disjointness given by property (i) yields a lower bound for $X+X$ in terms of
each $X_{i}$:

$|X+X|\geq\sum_{i}|X_{i}+D|.$

We now want a lower bound for each $|X_{i}+D|$ in terms of $d$. Towards that
goal, we will define, for every $i\in\\{1,\ldots,t\\}$, a Freĭman isomorphism
$\phi_{i}:X_{i}\to X_{i}^{\prime}\subseteq\mathbb{Z}^{d}$. Each will map (a
translate of) $D$ to a structured set, where structured only means that we
have a lower bound for its sumset with any sufficiently small set. These
isomorphisms are naturally defined by the $2\Delta$-bounded decomposition of
$X_{i}-y_{i}$ given by property (ii).

######  Observation B.5.

The function $\phi_{i}:X_{i}\to X_{i}^{\prime}\subseteq\mathbb{Z}^{d}$ defined
by $\phi_{i}(x)=(\lambda_{1},\ldots,\lambda_{d})$, where
$x-y_{i}=\sum_{j=1}^{d}\lambda_{j}x_{j}$ is a $2\Delta$-bounded decomposition
of $x-y_{i}$, is a Freĭman isomorphism.

###### Proof.

The fact that $\phi^{-1}:X_{i}^{\prime}\to X_{i}$ is a Freĭman homomorphism
follows from its linearity, so we focus on the other direction of the
implication. Take $a_{1},a_{2},a_{3},a_{4}\in X_{i}$ such that

$a_{1}+a_{2}=a_{3}+a_{4},$ (131)

and we want to show that
$\phi_{i}(a_{1})+\phi_{i}(a_{2})=\phi_{i}(a_{3})+\phi_{i}(a_{4})$. For
$\ell\in\\{1,\ldots,4\\}$, write

$a_{\ell}-y_{i}=\sum_{i=1}^{d}x_{i}\lambda^{(\ell)}_{i},$ (132)

a $2\Delta$-bounded combination of $D$. We now replace (132) in (131) and
rearrange to obtain

$\sum_{j=1}^{d}x_{j}(\lambda_{j}^{(1)}+\lambda_{j}^{(2)}-\lambda_{j}^{(3)}-\lambda_{j}^{(4)})=0.$

Using the fact that each (132) is $2\Delta$-bounded yields, as $k\to\infty$,

$\sum_{\ell=1}^{4}\sum_{j=1}^{d}|\lambda_{j}^{(\ell)}|\leq 4(2\Delta)\leq
8k^{1/2}\log k\leq(\log n)^{1-\eta/3}\leq M,$

where the inequalities follow by the definitions/assumptions which we now
recall

$\Delta=k^{1/2}\log k,\qquad k\leq(\log n)^{2-\eta}\qquad\text{ and }\qquad
M=(\log n)/(\log\log n)^{4}.$

However, $D$ is $M$-dissociated, so we conclude that, for all
$j\in\\{1,\ldots,d\\}$,

$(\lambda_{j}^{(1)}+\lambda_{j}^{(2)})-(\lambda_{j}^{(3)}+\lambda_{j}^{(4)})=0,$

which, by the definition of $\phi_{i}$, is just another way to write
$\phi_{i}(a_{1})+\phi_{i}(a_{2})=\phi_{i}(a_{3})+\phi_{i}(a_{4})$. ∎

Observe that $\phi_{i}(D+y_{i})=\\{e_{1},\ldots,e_{d}\\}$, where
$\\{e_{1},\ldots,e_{d}\\}$ is the canonical basis of $\mathbb{Z}^{d}$. Hence,
to obtain a lower bound for the size of $X_{i}+D$ in terms of $d$ and complete
the proof of Lemma B.2, we will bound $|\phi_{i}(X_{i})+\phi_{i}(D+y_{i})|$
using the isoperimetric inequality of Wang and Wang [30], as stated in [18]
(see also [5]).

######  Proposition B.6 ([30], see [18, “The Isoperimetric Inequality”]).

For every $\gamma>0$ and $C>0$, there exists $d_{0}=d_{0}(\gamma,C)$ such that
the following holds for every $d\geq d_{0}$. If $S\subseteq\mathbb{Z}^{d}$ is
a set of size at most $Cd$, then

$\big{|}S+\\{e_{1},\ldots,e_{d}\\}\big{|}\geq\left(\frac{1}{2}-\gamma\right)d|S|.$

###### Proof of Lemma B.2.

Fix $X\in\mathcal{X}_{3}^{(m)}$ and let $D=\\{x_{1},\ldots,x_{d}\\}$ be any
$M$-dissociated subset of $X$. Towards our aim of showing that
$|D|=d\leq\big{(}2+\delta+o(1)\big{)}m/k$, recall the definition of the graph
$G^{\prime}$: its vertices are $\mathbb{Z}_{n}$ and there are edges between
vertices $a,b\in\mathbb{Z}_{n}$ only when some of $\pm(a-b)$ can be written as
either $x_{i}-x_{j}$ or $x_{i}+x_{j}$ for $i,j\in\\{1,\ldots,d\\}$.

We apply Lemma B.4 to $G=G^{\prime}[X]$ with $\Delta=k^{1/2}\log k$ and obtain
$X_{*}\cup X_{1}\cup\cdots\cup X_{t}$, a partition of $X$ such that
$e(X_{i},X_{j})=0$ for all $i\neq j$,

$\operatorname{diam}(G[X_{i}])\leq k^{1/2}\log k$ (133)

and

$|X_{*}|\leq 32\left(\frac{k}{k^{1/2}\log k}\right)^{2}=o(k).$ (134)

In order to obtain a lower bound for $X+X$, we use property (i) of $G$ to show
that

$|X+X|\geq\sum_{i=1}^{t}|X_{i}+D|.$ (135)

Now, we define, for each $i\in\\{1,\ldots,t\\}$, the function $\phi_{i}$; by
property (ii) and Observation B.5, we have that $\phi_{i}$ is a Freĭman
isomorphism from $X_{i}$ to $X_{i}^{\prime}\subseteq\mathbb{Z}^{d}$. By the
definition of Freĭman isomorphisms, we obtain

$|X_{i}+D|=|X_{i}+(D+y_{i})|=|X_{i}^{\prime}+\phi_{i}(D+y_{i})|.$ (136)

Recall that the definition of $\phi_{i}$ implies that
$\phi_{i}(D+y_{i})=\\{e_{1},\ldots,e_{d}\\}$. Hence, to apply Proposition B.6
to the right-hand side of (136), we need to bound $|X_{i}^{\prime}|$ in terms
of $d$ and show that $d$ is sufficiently large. We will show both of these by
observing that if $k>10d/\delta$, then we are already done, since

$d\leq\frac{\delta
k}{10}\leq\frac{m}{k}\leq\big{(}2+\delta+o(1)\big{)}\frac{m}{k},$

which is what we wanted to show. We can therefore assume that $d\geq\delta
k/10$, which simultaneously implies that $d$ is large when $k\to\infty$, and
that $|X_{i}^{\prime}|\leq k\leq 10d/\delta$. Applying Proposition B.6 to
$X_{i}^{\prime}$ with $\gamma=\delta^{2}$ and $C=10/\delta$, we obtain

$\big{|}X_{i}^{\prime}+\\{e_{1},\ldots,e_{d}\\}\big{|}\geq\left(\frac{1}{2}-\delta^{2}\right)d|X_{i}^{\prime}|$
(137)

for each $i\in\\{1,\ldots,t\\}$.

Replacing (137) in (135), and using (136), we conclude that

$|X+X|\geq
d\left(\frac{1}{2}-\delta^{2}\right)\sum_{i=1}^{t}|X_{i}^{\prime}|.$

Thus, using the fact that $|X_{i}^{\prime}|=|X_{i}|$, which follows from each
$\phi_{i}$ being a Freĭman isomorphism, and that $X=X_{*}\cup X_{1}\cup\cdots
X_{t}$ is a partition, we have

$d\left(\frac{1}{2}-\delta^{2}\right)\sum_{i=1}^{t}|X_{i}^{\prime}|=d\left(\frac{1}{2}-\delta^{2}\right)\big{(}|X|-|X_{*}|\big{)}=d\left(\frac{1}{2}-\delta^{2}\right)(1-o(1))k$

where we used (134) to bound $|X_{*}|$. Finally, it follows from $|X+X|\leq m$
and $\delta$ being sufficiently small that
$d\leq\big{(}2+\delta+o(1)\big{)}m/k$ as $k\to\infty$. ∎

With Lemma B.2, we need only one more piece, the following lemma. It is a
simple count of the number of choices for coefficients in a dissociated set,
and we will use it to repeat the proof of Proposition 5.1 in Green and Morris
[18] and obtain Proposition 8.6.

######  Lemma B.7 ([18, Lemma 5.5]).

For every $M,d\in\mathbb{N}$, the number of choices for
$\lambda_{1},\ldots,\lambda_{d}\in\mathbb{Z}$ such that
$\sum_{i=1}^{d}|\lambda_{i}|\leq M$ is at most $(4d)^{M}$.

###### Proof of Proposition 8.6.

Fix $M=(\log n)/(\log\log n)^{4}$ and take $X\in\mathcal{X}_{3}^{(m)}$. We
will count the choices for $X$ by first choosing a maximal $M$-dissociated
subset $D=\\{x_{1},\ldots,x_{d}\\}\subseteq X$ and then choosing the remaining
elements of $X\setminus D$ using the properties of $D$.

First, we count the choices for $D$ naively, and rely on Lemma B.2 to bound
its size. That is, we apply Lemma B.2 to $D$, obtain ${|D|\leq
d\leq\big{(}2+\delta+o(1)\big{)}m/k}$, and thus deduce that the number of
choices for $D$ is at most:

$\sum_{t=1}^{d}\binom{n}{t}\leq(n+1)^{d}\leq n^{(2+\delta+o(1))m/k}.$ (138)

The second step is counting the choices for $X\setminus D$, and we do so by
counting the possible ways to write each of its elements as an $M$-bounded
combination of $D$. Fix $x^{\prime}\in X\setminus D$, and note that the
maximality of $D$ implies that there is
$\Lambda=\\{\lambda_{0},\lambda_{1},\ldots,\lambda_{d}\\}\subseteq\mathbb{Z}$
such that

$\lambda_{0}x^{\prime}+\sum_{j=1}^{d}\lambda_{j}x_{j}=0$

and the elements of $\Lambda$ satisfy

$\sum_{j=0}^{d}|\lambda_{j}|\leq M,\qquad\lambda_{0}\neq 0\qquad\text{ and
}\qquad\lambda_{i}\neq 0\text{ for some }i>0.$

We can therefore use Lemma B.7 to count the number of choices for $\Lambda$
and observe that

$(4d+4)^{M}\leq\exp(3M\log k)\leq\exp\left(\frac{\log n}{(\log\log
n)^{2}}\right)\leq n^{1/\log k}$

where the first inequality follows from the (trivial) observation that $d\leq
k$, and the rest is a consequence of our choice of $M=(\log n)/(\log\log
n)^{4}$ and our assumption that $k\leq(\log n)^{2-\eta}$.

We can now choose each of the $k-d$ elements of $X\setminus D$ by the above
procedure, and obtain that there are at most

$n^{(k-d)/(\log k)}=n^{o(k)}$ (139)

such elements. Combining (138) and (139) with $m\geq\delta k^{2}/10$ thus
yields

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

as required. ∎