Bilinear Bogolyubov Argument in Abelian Groups
Luka Milićević†

00footnotetext: † Mathematical Institute of the Serbian Academy of Sciences
and Arts
† Email<EMAIL_ADDRESS>
  * Abstract

a Bilinear Bogolyubov argument states that if we start with a dense set
$A\subseteq\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}$ and carry out
sufficiently many steps where we replace every row or every column of $A$ by
the set difference of it with itself, then inside the resulting set we obtain
a bilinear variety of codimension bounded in terms of density of $A$. In this
paper, we generalize the bilinear Bogolyubov argument to arbitrary finite
abelian groups. Namely, if $G$ and $H$ are finite abelian groups and
$A\subseteq G\times H$ is a subset of density $\delta$, then the procedure
above applied to $A$ results in a set that contains a bilinear analogue of a
Bohr set, with the appropriately defined codimension bounded above by
$\log^{O(1)}(O(\delta^{-1}))$.

## §1 Introduction

Let us begin by recalling the following classical fact due to Bogolyubov.
Whenever $A\subset\mathbb{Z}/N\mathbb{Z}$ is a subset of density $\alpha$,
then the set $2A-2A$ contains a Bohr set of bounded codimension and large
radius. (We are being deliberately informal at the moment, we shall define
Bohr sets properly slightly later in the introduction.) This fundamental fact
was generalized to the bilinear setting in the case of vector spaces over
finite fields by Bienvenu and Lê [2] and, independently, by Gowers and the
author [7]. Hosseini and Lovett [11] improved the bounds to the nearly optimal
ones. Before stating their result, which we refer to as the bilinear
Bogolyubov argument, we need to set up some notation. Let
$A\subseteq\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}$ be a subset. We write
$\mathsf{D}_{\mathsf{hor}}A$ for the _horizontal difference set_ of $A$ which
is defined as
$\mathsf{D}_{\mathsf{hor}}A=\\{(x_{1}-x_{2},y)\colon(x_{1},y),(x_{2},y)\in
A\\}$. Similarly, we write $\mathsf{D}_{\mathsf{ver}}A$ for the _vertical
difference set_ of $A$ which is defined as
$\mathsf{D}_{\mathsf{ver}}A=\\{(x,y_{1}-y_{2})\colon(x,y_{1}),(x,y_{2})\in
A\\}$. In other words, horizontal difference set is obtained by taking the
difference set inside each row and the vertical difference set is obtained by
taking the difference set inside each column. Iterated directional difference
sets are obtained by the obvious compositions, as $\mathsf{D}_{\mathsf{hor}}$
and $\mathsf{D}_{\mathsf{ver}}$ are simply maps from the power-set
$\mathcal{P}(\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n})$ to itself.

######  Theorem 1.1 (Bilinear Bogolyubov argument in $\mathbb{F}_{p}^{n}$).

Let $A\subseteq\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}$ be a set of density
$\delta>0$. Then there exist subspaces $U,V\leq\mathbb{F}_{p}^{n}$ of
codimension at most $O(\log^{80}\delta^{-1})$, a positive integer $r\leq
O(\log^{80}\delta^{-1})$ and a bilinear map $\beta\colon U\times
V\to\mathbb{F}_{p}^{r}$ such that

$\\{(x,y)\in U\times
V\colon\beta(x,y)=0\\}\subseteq\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{hor}}A.$

Sets of the form in the conclusion of the theorem above are called _bilinear
varieties_. Let us note that the bounds in [2] and [7] were towers of two or
three exponentials in $\log^{O(1)}\delta^{-1}$, but had fewer applications of
the directional difference sets.

Theorem 1.1 was used by Bienvenu and Lê [3] to show that the Mőbius function
does not have significant correlation with quadratic phases. In [6], Gowers
and the author used a more analytic version of the theorem above as an
important ingredient in a proof of a quantitative inverse theorem for the
$\|\cdot\|_{\mathsf{U}^{4}}$ uniformity norm in finite dimensional vector
spaces over $\mathbb{F}_{p}$ for $p\geq 5$. Finally, Theorem 1.1 was
generalized to the multilinear setting by the same authors in [8].

The goal of this paper is to prove a version of bilinear Bogolyubov argument
in arbitrary finite abelian groups with nearly optimal bounds. In order to
state it, we need a couple of (mostly standard) definitions. For a finite
abelian group $G$, its _dual group_ is defined as the additive group of
_characters_ on $G$, where a character is a homomorphism from $G$ to the unit
circle $\mathbb{T}=\mathbb{R}/\mathbb{Z}$. We also make use of a function
$|\cdot|_{\mathbb{T}}\colon\mathbb{T}\to[0,1/2]$ that maps elements of the
unit circle to their distance to $0+\mathbb{Z}$. For a set of characters
$\Gamma\subseteq\hat{G}$ and a non-negative real $\rho$, we define a Bohr set
$B(\Gamma;\rho)$ as the set of all elements $x\in G$ such that
$|\gamma(x)|_{\mathbb{T}}\leq\rho$ for all $\gamma\in\Gamma$. The set $\Gamma$
is called the _frequency set_ and $\rho$ is the _radius_ of the Bohr set. We
also say that the _codimension_ of $B(\Gamma;\rho)$ is at most $|\Gamma|$.
Finally, given a map $\phi\colon A\to H$ from a subset $A$ of an abelian group
$G$ to another abelian group $H$, we say that it is _Freiman-linear_ if
$\phi(a-b)=\phi(a)-\phi(b)$ whenever $a,b,a-b\in A$. Freiman-linearity is
simply a linearized version of the property of being a Freiman homomorphism.
We are now ready to state the main result of this paper.

######  Theorem 1.2 (Bilinear Bogolyubov argument in finite abelian groups).

Let $G$ and $H$ be finite abelian groups and let $A\subseteq G\times H$ be a
set of density $\delta$. Then there exist a positive quantity
$\rho\geq\exp\Big{(}-\log^{O(1)}(10\delta^{-1})\Big{)}$, sets
$\Gamma\subseteq\hat{G},\Psi\subseteq\hat{H}$ of size at most
$\log^{O(1)}(10\delta^{-1})$ and Freiman-linear maps $L_{1},\dots,$
$L_{r}\colon B(\Psi;\rho)\to\hat{G}$ for some positive integer
$r\leq\log^{O(1)}(10\delta^{-1})$ such that the bilinear Bohr variety

$\Big{\\{}(x,y)\in B(\Gamma;\rho)\times B(\Psi;\rho)\colon x\in
B(L_{1}(y),\dots,L_{r}(y);\rho)\Big{\\}}$

is contained inside
$\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{hor}}A$.

Remark on logarithms. In this paper, logarithms appear exclusively in upper
bounds (even in $\exp\Big{(}-\log^{O(1)}(10\delta^{-1})\Big{)}$ there is an
upper bound in the argument of $\exp$). To ease the notational burden in the
bounds that appear quite frequently, from now on $\log x$ for $x\geq 1$ stands
for $\log x+2$. The main reason for doing so is that it guarantees that $\log$
is sufficiently larger than 1.

Remark on bounds. In the vector space case, Theorem 1.1 gives a bound of the
form $\log_{p}(p^{n}/|U|)+\log_{p}(p^{n}/|V|)+r\leq
O_{p}(\log^{O(1)}\delta^{-1})$. Since the the size of the Bohr set
$B(\Gamma;\rho)$ is comparable to $\rho^{|\Gamma|}|G|$, a corresponding bound
in the general case would be $(|\Gamma|+|\Psi|)\log\rho^{-1}+r\leq
O(\log^{O(1)}\delta^{-1})$, which is indeed the case in Theorem 1.2.

Let us compare the conclusions of Theorems 1.1 and 1.2. As usual, we think of
Bohr sets as replacement for subgroups in general finite abelian groups, so
having $B(\Gamma;\rho)\times B(\Psi;\rho)$ in Theorem 1.2 instead of $U\times
V$ in Theorem 1.1 is expected. When it comes to the bilinear map $\beta\colon
U\times V\to\mathbb{F}_{p}^{r}$ in Theorem 1.1, if we fix a dot product
$\cdot$ on $\mathbb{F}_{p}^{n}$, then linear forms on $\mathbb{F}_{p}^{n}$ are
exactly the maps $v\mapsto a\cdot v$ for some fixed $a\in\mathbb{F}_{p}^{n}$.
In particular, for each $i\in[r]$, we can find a linear map
$L_{i}\colon\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$ such that
$\beta_{i}(x,y)=x\cdot L_{i}(y)$. Let us interpret expressions
$\frac{\lambda}{p}$ for $\lambda\in\mathbb{F}_{p}$ as elements of
$\mathbb{T}$, namely as $\frac{k}{p}+\mathbb{Z}$ where
$k\in\\{0,1,\dots,p-1\\}\subseteq\mathbb{Z}$ is the integer in the given
interval corresponding to $\lambda$. With these conventions we see that

$\\{(x,y)\in U\times V\colon\beta(x,y)=0\\}=\Big{\\{}(x,y)\in U\times
V\colon\Big{|}\frac{x\cdot L_{i}(y)}{p}\Big{|}_{\mathbb{T}}\leq 0\Big{\\}}.$

Finally, noting that $v\mapsto\frac{a\cdot v}{p}$ is a character on
$\mathbb{F}_{p}^{n}$ we see that Theorem 1.2 implies Theorem 1.1 (though with
somewhat weaker bounds as the implicit constant in $\log^{O(1)}\delta^{-1}$ is
probably higher than 80, but we are mainly interested in the same form of
bounds).
As a final comment on the relationship between the two results, Freiman-linear
maps on Bohr sets seem to be the right generalization of linear maps in this
context.111See Theorem 3.4. We use coset progressions as domain, but coset
progressions and Bohr sets are very closely related, see also Proposition 4.8.

A comparison with earlier works and an outline. Let us briefly compare the
previous works on the bilinear Bogolyubov argument [2], [7] and [11]. Let us
fix a dense set $A\subseteq\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}$. Very
roughly speaking, all three proofs have the following structure.

  * Step 1.

Apply Bogolyubov argument in all dense rows, to find a dense subset
$Y\subseteq\mathbb{F}_{p}^{n}$ such that for each $y\in Y$, after taking
double difference set in the row indexed by $y$, we obtain a bounded
codimension vector space $V_{y}$.

  * Step 2.

Take difference sets in columns and rows sufficient number of times to find a
further dense subset $Y^{\prime}\subseteq\mathbb{F}_{p}^{n}$ and a bounded
number of linear maps
$L_{1},\dots,L_{r}\colon\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}^{n}$ such that for
each $y\in Y^{\prime}$ we now obtain the subspace $\langle
L_{1}(y),\dots,L_{r}(y)\rangle^{\perp}$ in the row indexed by $y$.

  * Step 3.

Apply Bogolyubov argument to $Y^{\prime}$ to obtain a subspace $U\subseteq
2Y^{\prime}-2Y^{\prime}$ and use this subspace to induce the desired structure
in columns of the iterated difference set of $A$.

The way this strategy is carried out is different in each of the three papers.
However, due to its simplicity, Step 1 is essentially the same in all three
works. Furthermore, in Step 2 all three papers use the fact that the maps that
respect many additive quadruples coincide on a large set with affine maps (see
Theorem 3.4 for a precise statement).

When it comes to differences, which are most obvious in Step 3, the work of
Bienvenu and Lê [2] uses arithmetic regularity lemma, Gowers and the author
use a direct Fourier analytic argument to conclude the proof, while Hosseini
and Lovett perform a careful algebraic manipulation of the resulting subspaces
in the rows of the iterated difference set and use a significant amount of
linear algebra. There is also an important difference in how Hosseini and
Lovett find the linear maps in Step 2 without a loss in efficiency; we shall
discuss their idea when we reach the corresponding step in the proof in this
paper. Overall, papers [7] and [11] are more similar in their organization and
this paper is builds upon ideas in those two, so we focus on them in the rest
of the outline.

Our argument will follow that of Hosseini and Lovett in the first two steps,
but we shall need to diverge in order to complete Step 3. Their argument
involves a consideration of rank of linear combinations of linear maps
$L_{1},\dots,L_{r}$ produced in Step 2, which is not readily available in our
more general setting. However, the high-rank condition on the system of linear
maps is essentially equivalent to the bilinear variety

$\Big{\\{}(x,y)\in\mathbb{F}_{p}^{n}\times\mathbb{F}_{p}^{n}\colon(\forall
i\in[r])x\cdot L_{i}(y)=0\Big{\\}}$

being quasirandom (see Corollary 5.2 and Lemma 5.4 in [6]). With this in mind,
we prove an algebraic regularity lemma for bilinear Bohr varieties.
Recall that a _coset progression_ in an abelian group $G$, introduced by Green
and Ruzsa in their generalization of Freiman’s theorem to arbitrary abelian
groups [9], is a set $C$ of the form $L_{1}+\dots+L_{r}+H$, where $L_{i}$ are
arithmetic progressions and $H\leq G$ is a subgroup. We refer to the number
$r$ as the _rank_ of the coset progression. We say that a coset progression
$C$ is _proper_ if $|C|=|L_{1}|\cdots|L_{r}||H|$, (thus all sums of
$(r+1)$-tuples are distinct), and we say that $C$ is _symmetric_ if all
$L_{i}$ are symmetric, i.e. $L_{i}=-L_{i}$. We use coset progressions instead
of Bohr sets as domains of Freiman-linear maps in the statement as the coset
progressions have nicer partitions than Bohr sets, but this is of minor
importance.

######  Theorem 1.3 (Algebraic regularity lemma for bilinear Bohr varieties).

Let $G$ and $H$ be finite abelian groups. Let $C$ be a symmetric proper coset
progression of rank $d$ inside the group $H$, let $\Gamma\subseteq\hat{G}$ and
let $L_{1},\dots,L_{r}\colon C\to\hat{G}$ be Freiman-linear maps. Let $\rho>0$
and $\eta>0$ be given. We may partition $C$ into further proper coset
progressions $C_{1},\dots,C_{m}$ of rank at most $d$, where

$m\leq\exp\Big{(}d^{O(1)}r^{O(1)}|\Gamma|^{O(1)}\log^{O(1)}(\eta^{-1})\log^{O(1)}(\rho^{-1})\Big{)},$

such that for each $i\in[m]$ there exist positive reals $\delta_{i}$ and
$\rho_{i}\in[\rho/2,\rho]$ such that the following two quasirandomness
properties hold.

  * (i)

For at least $1-\eta$ proportion of all elements $y\in C_{i}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i})|-\delta_{i}|B(\Gamma;\rho_{i})|\Big{|}\leq\eta|G|.$

  * (ii)

For at least $1-\eta$ proportion of all pairs $(y,y^{\prime})\in C_{i}\times
C_{i}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y),L_{1}(y^{\prime}),\dots,L_{r}(y^{\prime})\\};\rho_{i})|-\delta^{2}_{i}|B(\Gamma;\rho_{i})|\Big{|}\leq\eta|G|.$

Using this result, we may finish Step 3 using the well-known quasirandomness
properties of bipartite graphs.

Let us note that Theorem 1.3 is another important ingredient of the proof [6]
of the inverse theorem for the $\|\cdot\|_{\mathsf{U}^{4}}$ uniformity norm in
$\mathbb{F}_{p}^{n}$ that is generalized in this paper. With this in mind,
Theorems 1.2 and 1.3, along with other auxiliary results proved here, open up
the possibility of extending the mentioned inverse theorem to arbitrary finite
abelian groups. In fact, it is likely that the other arguments from the proof
in [6], which are of a more combinatorial nature, could be combined with the
results of this paper to understand Freiman bihomomorphisms222For finite
abelian groups $G,H$ and $K$, and a subset $A\subseteq G\times H$, a _Freiman
bihomomorphism_ is a map $\phi\colon A\to K$ with the property that the map
$y\mapsto\phi(x,y)$ is a Freiman homomorphism for each $x\in G$ (with domain
$\\{y\in H\colon(x,y)\in A\\}$) and the map $x\mapsto\phi(x,y)$ is a Freiman
homomorphism for each $y\in H$ (again with an appropriate domain). in general
finite abelian groups. In the case of the $\mathbb{F}_{p}^{n}$, it is possible
to deduce the inverse theorem for the $\|\cdot\|_{\mathsf{U}^{4}}$ norm from
an inverse theorem for Freiman bihomomorphisms (see [6] for $p\geq 5$ and a
recent work of Tidor [17] for the cases $p\in\\{2,3\\}$).

‘Linear algebra’ in finite abelian groups. Since we are no longer working with
vector spaces, we need to be able to generalize several linear-algebraic facts
to setting of finite abelian groups. Let us mention a few examples.

For instance, the vector space identity

$(U\cap V)^{\perp}=U^{\perp}+V^{\perp}$ (1)

plays a crucial role in the proof of bilinear Bogolyubov argument. In the
setting of general finite abelian groups, where $U$ and $V$ are no longer
subspaces but are Bohr sets instead, we prove the following result.
For a set $\Gamma=\\{\gamma_{1},\dots,\gamma_{k}\\}$ of elements of an abelian
group and a nonnegative integer $R$, we write $\langle\Gamma\rangle_{R}$ for
the set of all linear combinations
$\lambda_{1}\gamma_{1}+\dots+\lambda_{k}\gamma_{k}$, where
$\lambda_{1},\dots,\lambda_{k}\in[-R,R]\subseteq\mathbb{Z}$.

######  Theorem 1.4.

Let $G$ be a finite abelian group. Let $\Gamma_{1},\Gamma_{2}\subset\hat{G}$
and $\rho_{1},\rho_{2}\in(0,1)$. Then there is a positive integer
$R\leq(2\rho_{1}^{-1})^{O(|\Gamma_{1}|)}+(2\rho_{2}^{-1})^{O(|\Gamma_{2}|)}$
such that

$B(\langle\Gamma_{1}\rangle_{R}\cap\langle\Gamma_{2}\rangle_{R},1/4)\subseteq
B(\Gamma_{1},\rho_{1})+B(\Gamma_{2},\rho_{2}).$

One way to think about the Bohr set $B(\Gamma;\rho)$ is to view it as an
analogue of $\Gamma^{\perp}$ in finite abelian groups; by this analogy Theorem
1.4 is a meaningful generalization of linear-algebraic identity (1).

Another important notion is the linear independence of elements in a vector
space. We may still talk about independent elements in finite abelian groups,
but in our case we need a quantitative version of that notion. To that end, we
prove the following theorem.

######  Theorem 1.5.

Let $G$ be a finite abelian group, let $a_{1},\dots,a_{k}\in G$ and let $R$ be
a positive integer. Suppose that $B\subset\langle
a_{1},\dots,a_{k}\rangle_{R}$ is a non-empty set. Then, there exist positive
integers $\ell\leq O(k^{2}(\log k+\log R))$, $S\leq O((2Rk)^{k+3})$ and
elements $b_{1},\dots,b_{\ell}\in B$ such that $B\subseteq\langle
b_{1},\dots,b_{\ell}\rangle_{S}$.

To relate it to the linear-algebraic setting, we think of $\langle
a_{1},\dots,a_{k}\rangle_{R}$ as a subspace $V$ of dimension $k$, and $B$ a
subspace inside $V$. The usual conclusion then is that $B$ has a spanning set
of size at most $k$. In the general setting we have to pay a modest price and
allow a slightly larger spanning set, but we still have control over the
coefficients of the required linear combinations.

As a final example, in order to prove Theorem 1.3, we need strong control over
sizes of Bohr sets. To that end, we prove an approximate formula for the size
of Bohr sets that are somewhat well-behaved.

######  Proposition 1.6 (Size of Bohr sets).

Let $k\in\mathbb{N}$ and let $\rho,\eta,\varepsilon>0$. Then, there exist a
positive integer $K\leq O(k\varepsilon^{-1}\eta^{-1})$ and quantities
$c_{i}\in\mathbb{D}$ for $i\in[-K,K]$ for which the following holds.
Let $G$ be a finite abelian group. Suppose that
$\gamma_{1},\dots,\gamma_{k}\in\hat{G}$ and that

$|B(\gamma_{1},\dots,\gamma_{k};\rho+\eta)\setminus
B(\gamma_{1},\dots,\gamma_{k};\rho)|\leq\varepsilon|G|.$

Then

$\Big{|}|B(\gamma_{1},\dots,\gamma_{k};\rho)|-\sum_{a_{1},\dots,a_{k}\in[-K,K]}\mathbbm{1}(a_{1}\gamma_{1}+\dots+a_{k}\gamma_{k}=0)c_{a_{1}}\dots
c_{a_{k}}|G|\Big{|}\leq 2\varepsilon|G|.$

For this proposition, the linear-algebraic analogue is the formula

$|\langle
u_{1},\dots,u_{k}\rangle^{\perp}|\,=\Big{|}\Big{\\{}(a_{1},\dots,a_{k})\in\mathbb{F}_{p}^{k}\colon
a_{1}u_{1}+\dots+a_{k}u_{k}=0\Big{\\}}\Big{|}\,p^{-k}\,|\mathbb{F}_{p}^{n}|\,=|\mathbb{F}_{p}^{n}|/|\langle
u_{1},\dots,u_{k}\rangle|$

which holds for any $u_{1},\dots,u_{k}\in\mathbb{F}_{p}^{n}$, or, put more
concisely, $|U^{\perp}|=p^{n}/|U|$ for all subspaces
$U\leq\mathbb{F}_{p}^{n}$. Note also that we typically use the notion of
regular Bohr sets when we need nice behaviour; in our case the weaker
assumption above is sufficient. Finally, let us also remark that the constants
$c_{i}$ do not depend on the ambient group $G$.

Organization of the paper. The first four sections are somewhat preliminary in
the sense that we recall some basic properties and well-known results
regarding the topic of each section, and then proceed to derive some new ones
that are required in order to prove Theorem 1.2. Section 2 is devoted mainly
to coset progressions and Freiman homomorphisms, Section 3 to Freiman’s
theorem, Section 4 to Bohr sets and Section 5 to lattices. Following those
four section, in Section 6 we study quasirandomness properties of bilinear
Bohr varieties and prove Theorem 1.3. Finally, in Section 7 we combine all
ingredients to complete the proof of Theorem 1.2. There are also two
appendices, the first one on the robust version of the Bogolyubov-Rusza lemma
due to Schoen and Sisask [15], and the second one where we briefly recall the
theory of quasirandom bipartite graphs.

Acknowledgements. This work was supported by the Serbian Ministry of
Education, Science and Technological Development through Mathematical
Institute of the Serbian Academy of Sciences and Arts.

## §2 Coset progressions and Freiman homomorphisms

Coset progressions. We begin the preliminary section by repeating the
definition of coset progressions for completeness. A _coset progression_ in an
abelian group $G$ is a set $C$ of the form $L_{1}+\dots+L_{r}+H$, where
$L_{i}$ are arithmetic progressions and $H\leq G$ is a subgroup. We say that
$L_{1}+\dots+L_{r}+H$ is a _canonical form_ of $C$. The number $r$ as known as
the _rank_ of the coset progression. We say that a coset progression $C$ is
_proper_ if $|C|=|L_{1}|\cdots|L_{r}||H|$, (thus all sums of $(r+1)$-tuples
are distinct), and we say that $C$ is _symmetric_ if all $L_{i}$ are
symmetric, i.e. $L_{i}=-L_{i}$. Coset progressions were introduced by Green
and Ruzsa in their generalization of Freiman’s theorem to general abelian
groups [9], and, as their theorem confirms, these objects are a correct
generalization of (cosets of) subgroups from an additive-combinatorial
perspective.

We say that $A\subseteq B$ is a _Freiman-subgroup_ of $B$ if whenever $a,b\in
A$ and $a-b\in B$ then $a-b\in A$. The next lemma show that Freiman-sbugroups
of a coset progression $C$ are closely related to $C$.

######  Lemma 2.1.

Let $G$ be a finite abelian group. Let $C=[-N_{1},N_{1}]\cdot
v_{1}+\dots+[-N_{d},N_{d}]\cdot v_{d}+H$ be a proper symmetric coset
progression of rank $d$ in its canonical form. Let $A\subseteq C$ be a
Freiman-subgroup of size $|A|\geq\alpha|C|$ in $G$. Then $A$ contains
$[-M_{1},M_{1}]\cdot\ell_{1}v_{1}+\dots+[-M_{d},M_{d}]\cdot\ell_{d}v_{d}+H^{\prime}$
for some positive integers $\ell_{1},\dots,\ell_{d}\leq 20\alpha^{-1}$,
$M_{i}=\lfloor N_{i}/\ell_{i}\rfloor$ and a subgroup $H^{\prime}\leq H$ of
size $|H^{\prime}|\geq\alpha|H|$.

###### Proof.

We claim that for each $i\in[d]$ the Freiman-subgroup $A$ contains an element
of the form $\ell_{i}v_{i}$ for some $\ell_{i}\in[2\lceil\alpha^{-1}\rceil]$,
unless $N_{i}\leq 10\alpha^{-1}$. Without loss of generality $i=1$. Suppose
that $N_{1}\geq 10\alpha^{-1}$. Average over
$x_{2}\in[-N_{2},N_{2}],\dots,x_{d}\in[-N_{d},N_{d}]$ and $h\in H$ to find a
choice of $x_{2},\dots,x_{k},h$ such that $|A\cap([-N_{1},N_{1}]\cdot
v_{1}+x_{2}v_{2}+\dots+x_{d}v_{d}+h)|\geq\alpha(2N_{1}+1)$. Let
$A^{\prime}=\\{x_{1}\in[-N_{1},N_{1}]\colon
x_{1}v_{1}+x_{2}v_{2}+\dots+x_{d}v_{d}+h\in A\\}$ which has size at least
$\alpha(2N_{1}+1)$.
Let $L=2\lceil\alpha^{-1}\rceil$. We split the interval $[-N_{1},N_{1}]$ into
disjoint intervals of the form $[-N_{1}+jL,-N_{1}+(j+1)L)$, except possibly
the last one which looks like $[-N_{1}+jL,N_{1}]$ but still has length at most
$L$. The number of intervals is $\Big{\lceil}\frac{2N_{1}+1}{L}\Big{\rceil}$
which is smaller than the size of $A^{\prime}$, so there are two indices
$v_{1}<v^{\prime}_{1}<v_{1}+L$ in $A^{\prime}$. Since $A$ is a Freiman-
subgroup of $C$, we obtain the desired element.
Take $\ell_{i}$ we obtained above for each $N_{i}\geq 10\alpha^{-1}$. When
$N_{i}<10\alpha^{-1}$, we simply put $\ell_{i}=\lfloor 20\alpha^{-1}\rfloor$,
which makes $M_{i}=0$. To finish the proof we need to find an appropriate
subgroup $H^{\prime}\leq H$. Take $z\in[-N_{1},N_{1}]\cdot
v_{1}+\dots+[-N_{d},N_{d}]\cdot v_{d}$ such that $|A\cap z+H|\geq\alpha|z+H|$
and fix arbitrary $h_{0}\in H\cap(A-z)$. For each $z+h\in A\cap z+H$ we have
that $(z+h)-(z+h_{0})=h-h_{0}\in H\subseteq C$ and thus $h-h_{0}\in A$. Thus
$|A\cap H|\geq\alpha|H|$ and $A\cap H$ is a Freiman-subgroup $H$. Since $H$ is
a group in the usual sense, so is $A\cap H$, so we set $H^{\prime}=A\cap H$.∎

Later in this section, we shall prove an inverse theorem for approximate
Freiman homomorphisms (Theorem 3.4). Similarly to the case when $G$ and $H$
are vector spaces over some field (for example, see [7]), this theorem will
follow from Freiman’s theorem and Balog-Szemerédi-Gowers theorem. However, in
the more general setting we need an additional algebraic ingredient, which is
the following result.
Recall that a module $P$ over a ring is _projective_ if for every surjective
module homomorphism $f\colon N\to M$ and every module homomorphism $g\colon
P\to M$, there exists a module homomorphism $h\colon P\to N$ such that $f\circ
h=g$. In the case of the category of finite abelian groups, there are no
projective objects. However, if we allow Freiman homomorphism on coset
progressions, we may recover projectivity to some extent.

######  Theorem 2.2 (Partial projectivity in abelian groups).

Let $G$ and $H$ be finite abelian groups. Let $K\leq H$ be a subgroup. Suppose
that $\phi\colon G\to H/K$ is a homomorphism. Let $s\geq 2$. Then there exist
a proper coset progression $C\subseteq G$ of rank at most $\log_{2}|K|$ and
size $|C|\geq s^{-\log_{2}|K|}|G|$ and a Freiman $s$-homomorphism $\psi\colon
C\to H$ such that for all $x\in C$ we have $\phi(x)=\psi(x)+K$.

We say that a sequence of elements $x_{1},\dots,x_{r}$ in a finite abelian
group $G$ is a _basis_ if the equality
$\lambda_{1}x_{1}+\dots+\lambda_{r}x_{r}=0$ for integers
$\lambda_{1},\dots,\lambda_{r}$ implies that $n_{i}|\lambda_{i}$ for each
$i\in[r]$, where $n_{i}$ stands for the order of the element $x_{i}$, and we
also have $n_{1}\cdots n_{r}=|G|$, so elements $x_{1},\dots,x_{r}$ span $G$.
As in linear algebra, we may perform some linear manipulations to the sequence
above without affecting the property of being a basis.

######  Lemma 2.3 (Change of basis in abelian groups).

Suppose that $n_{1}|n_{2}|\dots|n_{r}$.

  * (i)

Let $i<j$. Then replacing $x_{i}$ by $x_{i}-\lambda\frac{n_{j}}{n_{i}}x_{j}$
preserves the property of being a basis, with orders of elements in the
sequence unchanged.

  * (ii)

Let $i>j$. Then replacing $x_{i}$ by $x_{i}-\lambda x_{j}$ preserves the
property of being a basis, with orders of elements in the sequence unchanged.

  * (iii)

Let $\lambda$ be an integer coprime to $n_{i}$. Replacing $x_{i}$ by $\lambda
x_{i}$ preserves the property of being a basis, with orders of elements in the
sequence unchanged.

###### Proof.

Proof of (i). Let $m$ be the order of $x_{i}-\lambda\frac{n_{j}}{n_{i}}x_{j}$.
Then $mx_{i}-\lambda m\frac{n_{j}}{n_{i}}x_{j}=0$. Since $x_{1},\dots,x_{r}$
is a basis, we have that $n_{i}|m$. On the other hand,
$n_{i}\Big{(}x_{i}-\lambda\frac{n_{j}}{n_{i}}x_{j}\Big{)}=n_{i}x_{i}-\lambda
n_{j}x_{j}=0$, so $m=n_{i}$.
Since the orders of elements in the new basis are the same as in the old one,
we just need to show independence. Let $\lambda_{1},\dots,\lambda_{r}$ be
integers such that

$\lambda_{i}\Big{(}x_{i}-\lambda\frac{n_{j}}{n_{i}}x_{j}\Big{)}+\sum_{\ell\in[r]\setminus\\{i\\}}\lambda_{\ell}x_{\ell}=0.$

The coefficients of elements $x_{\ell}$ for $\ell\not=j$ are $\lambda_{\ell}$,
so $n_{\ell}|\lambda_{\ell}$. On the other hand, the element $x_{j}$ has
$\lambda_{j}-\lambda_{i}\lambda\frac{n_{j}}{n_{i}}$ as its coefficient, so
$n_{j}|\lambda_{j}-\lambda_{i}\lambda\frac{n_{j}}{n_{i}}$. But
$n_{i}|\lambda_{i}$, so it follows that $n_{j}|\lambda_{j}$, as desired.
Proof of (ii). As in the proof of the property (i), one easily sees that the
order of $x_{i}-\lambda x_{j}$ is divisible by $n_{i}$. On the other hand,
$n_{i}\lambda x_{j}=0$ since $n_{j}|n_{i}$, so $n_{i}(x_{i}-\lambda x_{j})=0$.
Again, we just check independence. Let $\lambda_{1},\dots,\lambda_{r}$ be
integers such that

$\lambda_{i}\Big{(}x_{i}-\lambda
x_{j}\Big{)}+\sum_{\ell\in[r]\setminus\\{i\\}}\lambda_{\ell}x_{\ell}=0.$

As before, $n_{\ell}|\lambda_{\ell}$ holds for all $\ell\not=j$. The element
$x_{j}$ has $\lambda_{j}-\lambda_{i}\lambda$ as its coefficient, which has to
be divisible by $n_{j}$. We know that $n_{j}|n_{i}|\lambda_{i}$ so it follows
that $n_{j}|\lambda_{j}$, as desired.
Proof of (iii). An easy check.∎

###### Proof of Theorem 2.2.

Using the invariant factors decomposition, we know that $G$ is a direct sum
$\mathbb{Z}/{n_{1}\mathbb{Z}}\oplus\dots\oplus\mathbb{Z}/{n_{r}\mathbb{Z}}$
for some positive integers $n_{1}|\dots|n_{r}$. In our terminology, this means
that $G$ has a basis $x_{1},\dots,x_{r}$ where $x_{i}$ has order $n_{i}$. For
each $x_{i}$, pick an element $h_{i}\in H$ such that $\phi(x_{i})=h_{i}+K$.
Since $\phi$ is a homomorphism, we have that
$K=\phi(n_{i}x_{i})=n_{i}\phi(x_{i})=n_{i}h_{i}+K$, so $n_{i}h_{i}\in K$.
Furthermore, for any integers $\lambda_{1},\dots,\lambda_{r}$ we have

$\phi(\lambda_{1}x_{1}+\dots+\lambda_{r}x_{r})=\lambda_{1}h_{1}+\dots+\lambda_{r}h_{r}+K.$

Let us now perform the following procedure. We shall go through the sequence
$x_{1},\dots,x_{r}$ in the reverse order and define a new basis
$y_{1},\dots,y_{r}$ of $G$ with orders $n_{1},\dots,n_{r}$, and new elements
$k_{1},\dots,k_{r}\in H$ so that $n_{i}k_{i}=0$ instead of merely
$n_{i}k_{i}\in K$ for all but at most $\log_{2}|K|$ of indices $i\in[r]$ (for
the rest of them, we only guarantee that $n_{i}k_{i}\in K$).
At each step, assuming that $y_{r},\dots,y_{i+1}$ and $k_{r},\dots,k_{i+1}$
have been defined, we check whether the element $n_{i}h_{i}$ belongs to the
subgroup $S$ of $K$ generated by elements $n_{r}k_{r},\dots,n_{i+1}k_{i+1}$.
If $n_{i}h_{i}\notin S$, then we simply put $y_{i}=x_{i}$ and $k_{i}=h_{i}$.
On the other hand, if $n_{i}h_{i}\in S$, that means that we can find integers
$\lambda_{i+1},\dots,\lambda_{r}$ such that

$n_{i}h_{i}=\lambda_{i+1}n_{i+1}k_{i+1}+\dots+\lambda_{r}n_{r}k_{r}.$

Let us put

$y_{i}=x_{i}-\sum_{j\in[i+1,r]}\lambda_{j}\frac{n_{j}}{n_{i}}y_{j}$ (2)

and

$k_{i}=h_{i}-\sum_{j\in[i+1,r]}\lambda_{j}\frac{n_{j}}{n_{i}}k_{j}.$ (3)

######  Claim 2.4.

At the end of each step, the sequence $y_{r},\dots,y_{i},x_{i-1},\dots,x_{1}$
is a basis with orders $n_{r},\dots,n_{1}$. Moreover, for any choice of
integers $\mu_{1},\dots,\mu_{r}$ we have

$\phi\Big{(}\mu_{1}x_{1}+\dots+\mu_{i-1}x_{i-1}+\mu_{i}y_{i}+\dots+\mu_{r}y_{r}\Big{)}=\mu_{1}h_{1}+\dots+\mu_{i-1}h_{i-1}+\mu_{i}k_{i}+\dots+\mu_{r}k_{r}+K.$
(4)

###### Proof of the claim.

We prove the claim by downwards induction on $i$. The base case is $i=r+1$,
where we consider the basis $x_{r},x_{r-1},\dots,x_{1}$, for which the claim
holds. Suppose that the claim holds for some $i\geq 2$. By Lemma 2.3 we see
that the order of $y_{i-1}$ is the same as the order of $x_{i-1}$ and that
$y_{r},\dots,y_{i-1},x_{i-2},\dots,x_{1}$ is still a basis.
To prove the equality (4), since $\phi\colon G\to H/K$ is a homomorphism, we
just need to show that $\phi(y_{i})=k_{i}+K$ for each $i\in[r]$, which we
again do by downwards induction on $i$. But, we either have that $y_{i}=x_{i}$
and $k_{i}=h_{i}$, so we are done, or $y_{i}$ and $h_{i}$ are given by (2) and
(3), so

$\phi(y_{i})=\phi\Big{(}x_{i}-\sum_{j\in[i+1,r]}\lambda_{j}\frac{n_{j}}{n_{i}}y_{j}\Big{)}=\phi(x_{i})-\sum_{j\in[i+1,r]}\lambda_{j}\frac{n_{j}}{n_{i}}\phi(y_{j})=h_{i}-\sum_{j\in[i+1,r]}\lambda_{j}\frac{n_{j}}{n_{i}}k_{j}+K=k_{i}+K,$

as desired.∎

Observe that whenever $y_{i}$ and $k_{i}$ are given by (2) and (3), we have
that $n_{i}k_{i}=0$; namely

$n_{i}k_{i}=n_{i}h_{i}-\sum_{j\in[i+1,r]}\lambda_{j}n_{j}k_{j}=0,$

by the choice of coefficients $\lambda_{j}$. On the other hand, any time we
have $n_{i}k_{i}\not=0$, that means that subgroup $\langle
n_{r}k_{r},\dots,n_{i}k_{i}\rangle\leq K$ is larger than before, and since it
a group, it is at least twice as large as its predecessor. Thus, this can
happen at most $\log_{2}|K|$ times.

Let $I\subset[r]$ be the set of indices $i$ such that $n_{i}k_{i}\not=0$. For
$i\in I$ let $n^{\prime}_{i}=\lceil n_{i}/s\rceil$. Consider the coset
progression $C=\bigoplus_{i\in I}[0,n^{\prime}_{i}-1]\cdot y_{i}+G^{\prime}$,
where $G^{\prime}=\bigoplus_{i\in[r]\setminus I}[0,n_{i}-1]\cdot y_{i}$, with
$G^{\prime}$ being a subgroup of $G$. The rank of $C$ is $|I|\leq\log_{2}|K|$
and the size is $|C|=\Big{(}\prod_{i\in
I}n^{\prime}_{i}\Big{)}\Big{(}\prod_{i\in[r]\setminus I}n_{i}\Big{)}\geq
s^{-\log_{2}|K|}|G|$, as desired. We now show that $C$ has the claimed
property.

Let us define a map $\psi\colon C\to H$ by

$\psi\Big{(}\sum_{i\in[r]}\lambda_{i}y_{i}\Big{)}=\sum_{i\in[r]}\lambda_{i}k_{i}$

for $\lambda_{i}\in\mathbb{Z}$, with the restriction that
$\lambda_{i}\in[0,n^{\prime}_{i}-1]$ for $i\in I$. We claim that $\psi$ is a
Freiman $s$-homomorphism.
To that end, for each $i\in[r]$, let
$\mu^{1}_{i},\dots,\mu^{s}_{i},\nu^{1}_{i},\dots,\nu^{s}_{i}$ be integers,
with the requirement that they belong to the interval $[0,n^{\prime}_{i}-1]$
when $i\in I$. Suppose that for each $i$ we have
$n_{i}|\sum_{j\in[s]}\mu^{j}_{i}-\sum_{j\in[s]}\nu^{j}_{i}$. However, when
$i\in I$, using the fact that $n^{\prime}_{i}=\lceil n_{i}/s\rceil$, we have
the bound

$\Big{|}\sum_{j\in[s]}\mu^{j}_{i}-\sum_{j\in[s]}\nu^{j}_{i}\Big{|}<n_{i}.$

Thus, we have the exact equality
$\sum_{j\in[s]}\mu^{j}_{i}=\sum_{j\in[s]}\nu^{j}_{i}$. Proceeding further, we
have

$\sum_{j\in[s]}\psi\Big{(}\sum_{i\in[r]}\mu^{j}_{i}y_{i}\Big{)}-\sum_{j\in[s]}\psi\Big{(}\sum_{i\in[r]}\nu^{j}_{i}y_{i}\Big{)}=\sum_{j\in[s]}\sum_{i\in[r]}\mu^{j}_{i}k_{i}-\sum_{j\in[s]}\sum_{i\in[r]}\nu^{j}_{i}k_{i}=\sum_{i\in[r]}\Big{(}\sum_{j\in[s]}\mu^{j}_{i}-\sum_{j\in[s]}\nu^{j}_{i}\Big{)}k_{i}.$

When $i\in I$, the equality
$\sum_{j\in[s]}\mu^{j}_{i}=\sum_{j\in[s]}\nu^{j}_{i}$ implies that the
contribution to the sum above from $i$th term is 0. When $i\notin I$, we have
$n_{i}|\sum_{j\in[s]}\mu^{j}_{i}-\sum_{j\in[s]}\nu^{j}_{i}$, but
$n_{i}k_{i}=0$, so the contribution is $0$ as well. Hence, $\psi$ is a Freiman
$s$-homomorphism.

Finally, by Claim 2.4, we see that for each $x\in C$ we have
$\phi(x)=\psi(x)+K$, as required.∎

As a corollary, we deduce that somewhat injective Freiman homomorphisms on
coset progressions have a large injective piece.

######  Corollary 2.5.

Let $G$ and $H$ be finite abelian groups and let $C\subseteq G$ be a proper
coset progression with canonical form $C=P+K$ where $P=v_{0}+[0,N_{1}-1]\cdot
v_{1}+\dots+[0,N_{r}-1]\cdot v_{r}$ and $K\leq G$. Let $\phi\colon C\to H$ be
a Freiman homomorphism such that $|\phi(C)|\geq\alpha|C|$. Then there exist a
further proper coset progression $D\subseteq K$ of rank $\log_{2}\alpha^{-1}$
and size $\alpha^{2}|K|$, a positive integer $m\leq(8r\alpha^{-1})^{r}$ and a
partition $P=P_{1}\cup\dots\cup P_{m}$ into proper progressions such that
$\phi$ is injective on each proper coset progression of the form $k+P_{i}+D$
for $i\in[m]$ and $k\in K$.

###### Proof.

Let us begin by defining an auxiliary map $\psi\colon K\to H$ by setting
$\psi(k)=\phi(x+k)-\phi(x)$ for any $x\in C$. Note that $x\in C$ implies
$x+k\in C$ and that $\phi$ being a Freiman homomorphism implies that $\psi$ is
a homomorphism (in the usual group-theoretic sense). Furthermore, for each
$x\in C$ we also have that $|\phi(x+K)|=|\psi(K)|$ so
$|\psi(K)|\geq\alpha|K|$. In particular, if $S=\operatorname{ker}\psi$, we
have $|S|\leq\alpha^{-1}$.
Now define a homomorphism $\nu\colon\psi(K)\to K/S$ by sending every
$y\in\psi(K)$ to $x+S$ for $x\in K$ such that $\psi(x)=y$. Since $S$ is the
kernel of $\psi$, we see that $\nu$ is well-defined. The fact that $\nu$ is a
homomorphism follows from $\psi$ being a homomorphism. Apply Theorem 2.2 to
find a proper coset progression $\tilde{D}\subseteq\psi(K)$ of rank at most
$\log_{2}\alpha^{-1}$ and size at least $|\tilde{D}|\geq\alpha|\psi(K)|$ and a
Freiman homomorphism $\theta\colon\tilde{D}\to K$ such that

$(\forall z\in\tilde{D})\,\,\nu(z)=\theta(z)+S.$ (5)

We claim that $\theta$ is injective. Suppose that there exist elements
$z_{1},z_{2}\in\tilde{D}$ such that $\theta(z_{1})=\theta(z_{2})$. Since
$z_{1},z_{2}\in\psi(K)$, there $x_{1},x_{2}\in K$ such that
$\psi(x_{1})=z_{1}$ and $\psi(x_{2})=z_{2}$. By definition of $\nu$ we have
$\nu(z_{1})=x_{1}+S$ and $\nu(z_{2})=x_{2}+S$. But,

$x_{1}+S=\nu(z_{1})=\theta(z_{1})+S=\theta(z_{2})+S=\nu(z_{2})=x_{2}+S$

so $x_{1}-x_{2}\in S$, giving $z_{1}=\psi(x_{1})=\psi(x_{2})=z_{2}$, proving
the injectivity of $\theta$.
Write $D=\theta(\tilde{D})$. It follows that $D$ is a proper coset progression
in $K$ and that $\theta^{-1}\colon D\to H$ is also a Freiman homomorphism.
Furthermore, for each $x\in D$ we have $\theta_{y}^{-1}(x)\in\tilde{D}$ so by
property (5) we get $\nu(\theta^{-1}(x))=\theta(\theta^{-1}(x))+S=x+S$. The
definition of $\nu$ gives $\psi(x)=\theta^{-1}(x)$. Since $\theta^{-1}$ is
injective, it follows that $\psi$ is injective on $D$.
For $i\in[r]$ set $N^{\prime}_{i}=\lceil\alpha N_{i}/(4r)\rceil$. We claim
that $\phi$ is injective on each coset progression

$v_{0}+[a_{1},a_{1}+N^{\prime}_{1}-1]\cdot
v_{1}+\dots+[a_{r},a_{r}+N^{\prime}_{r}-1]\cdot v_{r}+D,$ (6)

for any choice of $a_{i}\in[0,N_{i}-N^{\prime}_{i}]$. Suppose on the contrary
that $\phi$ was not injective on the set above. Then we obtain
$a_{1},b_{1}\in[a_{1},a_{1}+N^{\prime}_{1}-1],\dots,a_{r},b_{r}\in[a_{r},a_{r}+N^{\prime}_{r}-1],k,l\in
D$ such that

$\phi\Big{(}v_{0}+a_{1}v_{1}+\dots+a_{r}v_{r}+k\Big{)}=\phi\Big{(}v_{0}+b_{1}v_{1}+\dots+b_{r}v_{r}+l\Big{)},$

with arguments of $\phi$ being different elements. If we had
$a_{1}v_{1}+\dots+a_{r}v_{r}=b_{1}v_{1}+\dots+b_{r}v_{r}$, that would have
implied

$\displaystyle\psi(k)=$
$\displaystyle\phi\Big{(}v_{0}+a_{1}v_{1}+\dots+a_{r}v_{r}+k\Big{)}-\phi\Big{(}v_{0}+a_{1}v_{1}+\dots+a_{r}v_{r}\Big{)}$
$\displaystyle=$
$\displaystyle\phi\Big{(}v_{0}+b_{1}v_{1}+\dots+b_{r}v_{r}+l\Big{)}-\phi\Big{(}v_{0}+b_{1}v_{1}+\dots+b_{r}v_{r}\Big{)}=\psi(l)$

which would be in contradiction with the fact that $\psi$ is injective on $D$.
Thus $a_{1}v_{1}+\dots+a_{r}v_{r}\not=b_{1}v_{1}+\dots+b_{r}v_{r}$.
Write $w=(a_{1}-b_{1})v_{1}+\dots+(a_{r}-b_{r})v_{r}+(k-l)\in G$. Since $\phi$
is a Freiman homomorphism, we have that $\phi(x)=\phi(x+w)$ whenever $x,x+w\in
C$. Note that $|a_{i}-b_{i}|\leq N^{\prime}_{i}-1$. Observe that for every
element $x\in C$, there is some $\lambda\in\mathbb{Z}$ such that $x+\lambda w$
is of the form $v_{0}+\mu_{1}v_{1}+\dots+\mu_{r}v_{r}+k\in P+K$ where at least
one $\mu_{i}$ satisfies $\mu_{i}\leq N^{\prime}_{i}-2$ or $\mu_{i}\geq
N_{1}-N^{\prime}_{i}+1$. In particular, $\phi(x+\lambda w)=\phi(x)$, so the
total number of values attained by $\phi$ is at most

$\sum_{i\in[r]}2(N_{i}^{\prime}-1)\Big{(}\prod_{j\in[r]\setminus\\{i\\}}N_{j}\Big{)}|K|\leq
2r(\alpha/4r)|C|<\alpha|C|$

which is a contradiction.
To finish the proof, partition $P+D$ into proper coset progressions of the
form (6) by taking $a_{i}$ to be multiples of $N^{\prime}_{i}$. The total
number of coset progressions is at most $(8r\alpha^{-1})^{r}$, as claimed.∎

Another way to phrase the additional algebraic obstacle arising in the setting
of general finite abelian groups that was not present in vector space setting
is that whenever $U$ is a subspace of a vector space $V$ we may find a further
subspace $W\leq V$ such that $U\oplus W=V$. Such decompositions are not
available this time. Still, we may obtain a partial decomposition using a
coset progression when the given subgroup is small.

######  Corollary 2.6.

Let $G$ be a finite abelian group with a subgroup $H$. Then there exists a
coset progression $C$ of rank at most $\log_{2}|H|$ and size at least
$|H|^{-2}|G|$ such that $|C+H|=|C||H|$.

###### Proof.

Let $\pi\colon G\to G/H$ be the natural projection sending $x$ to $x+H$. Since
$|\pi(G)|=|H|^{-1}|G|$, Corollary 2.5 gives a coset progression $C$ of rank
$\log_{2}|H|$ and size at least $|H|^{-2}|G|$ on which $\pi$ is injective and
so $|C+H|=|C||H|$.∎

To see the need for coset progressions, look at $G=\mathbb{Z}/2^{n}\mathbb{Z}$
and $H=\\{0,2^{n-1}\\}$. There is no decomposition using subgroups only as
every non-trivial subgroup of $G$ contains $H$.

## §3 Variants of Freiman’s theorem

In this section we gather various results related to Freiman’s theorem. Let us
first state the Bogolyubov-Rusza lemma of Sanders [14], which plays a very
important role in this work, as is the case with previous works on the
bilinear Bogolyubov argument.

######  Theorem 3.1 (Bogolyubov-Rusza lemma, Theorem 1.1 [14]).

Suppose that $G$ is a finite abelian group and that $A,B\subseteq G$ are
subsets such that $|A+B|\leq K\min\\{|A|,|B|\\}$. Then there exists a
symmetric proper coset progression $C\subseteq A-A+B-B$ of rank at most
$\log^{O(1)}(K)$ and size $|C|\geq\exp\Big{(}-\log^{O(1)}(K)\Big{)}|A+B|$.

Furthermore, we need a robust version of the Bogolyubov-Rusza lemma due to
Schoen and Sisask [15]. The following formulation follows rather
straightforwardly from their results and a quick deduction is presented in
Appendix A.

######  Theorem 3.2.

Let $G$ be a finite abelian group. Let $A\subset G$ be a set such that
$|A+A|\leq K|A|$. Then there exists a symmetric proper coset progression $C$
of rank at most $\log^{O(1)}(K)$ and size at least
$|C|\geq\exp(-\log^{O(1)}(K))|A|$ such that for each $x\in C$ there are at
least $\frac{1}{64K}|A|^{3}$ quadruples $(a_{1},a_{2},a_{3},a_{4})\in A^{4}$
such that $x=a_{1}+a_{2}-a_{3}-a_{4}$.

In particular, when $A$ is a dense subset of a coset progression $C$ of
bounded rank then $A$ has small doubling so the theorem above applies and
gives the following corollary. It is important that the actual size of $C$
does not play a role.

######  Corollary 3.3.

Let $G$ be a finite abelian group and let $C$ be a coset progression of rank
$d$. Suppose that $A\subseteq C$ has size $|A|\geq\alpha|C|$. Then there
exists a symmetric proper coset progression $C^{\prime}$ of rank at most
$(d\log(\alpha^{-1})^{O(1)}$ and size at least
$|C^{\prime}|\geq\exp\Big{(}-(d\log(\alpha^{-1}))^{O(1)}\Big{)}|C|$ such that
for each $x\in C^{\prime}$ there are at least $\frac{\alpha}{2^{d+6}}$
quadruples $(a_{1},a_{2},a_{3},a_{4})\in A^{4}$ such that
$x=a_{1}+a_{2}-a_{3}-a_{4}$.

###### Proof.

The doubling of $A$ is at most $2^{d}\alpha^{-1}$. Apply Theorem 3.2.∎

Next, we need an inverse theorem for approximate Freiman homomorphisms. Recall
that a quadruple $(a,b,c,d)$ of elements of an abelian group is said to be
_additive_ if $a+b=c+d$ holds, and that it is _respected_ by a map $\phi$ if
the codomain of $\phi$ is an abelian group, the elements $a,b,c,d$ belong to
the domain of $\phi$ and $\phi(a)+\phi(b)=\phi(c)+\phi(d)$ holds.

######  Theorem 3.4.

Let $G$ and $H$ be finite abelian groups, let $A\subset G$ be a subset and let
$\phi\colon A\to H$ be a function. Suppose that the number of additive
quadruples respected by $\phi$ is at least $\delta|G|^{3}$. Then there exist a
proper coset progression $Q\subseteq G$ of rank at most
$\log^{O(1)}(\delta^{-1})$ and a Freiman homomorphism $\Phi\colon Q\to H$ such
that $\Phi(x)=\phi(x)$ holds for at least $\exp(-\log^{O(1)}(\delta^{-1}))|G|$
elements $x\in A\cap Q$.

Such a result for cyclic groups is due to Gowers [5], while a similar
statement for general finite abelian groups (with weaker bounds than the ones
above) can be extracted from the work of Green and Tao on the inverse question
for $\|\cdot\|_{\mathsf{U}^{3}}$ norm [10]. However, since we need nearly
optimal bounds and must use Sanders’s Bogolyubov-Ruzsa lemma rather than
Freiman’s theorem, we need to give a proof.

###### Proof.

We consider the graph $\Gamma=\\{(a,\phi(a))\colon a\in A\\}$ of the mapping
$\phi$ which is a subset of the abelian group $G\times H$. Every additive
quadruple $(a,b,c,d)\in A^{4}$ which is respected by $\phi$ produces an
additive quadruple
$\Big{(}(a,\phi(a)),(b,\phi(b)),(c,\phi(c)),(d,\phi(d))\Big{)}$ in $\Gamma$.
Thus, there are at least $\delta|\Gamma|^{3}$ additive quadruples in $\Gamma$.
Applying Balog-Szemerédi-Gowers theorem ([1], [5]; we use the version stated
as Theorem 2.29 in [16]), we may find subsets
$\Gamma^{\prime},\Gamma^{\prime\prime}\subseteq\Gamma$ of size
$|\Gamma^{\prime}|,|\Gamma^{\prime\prime}|\geq\Omega(\delta^{O(1)}|\Gamma|)$
with $|\Gamma^{\prime}+\Gamma^{\prime\prime}|\leq O(\delta^{-O(1)}|\Gamma|)$.
By Plünnecke-Ruzsa inequality (Theorem 6.29 in [16], see also [13] and an
alternative proof due to Petridis [12]), we see hat
$|\Gamma^{\prime}+\Gamma^{\prime}|\leq O(\delta^{-O(1)}|\Gamma^{\prime}|)$. By
Theorem 3.2 we find a proper coset progression $C^{\prime}\subseteq
2\Gamma^{\prime}-2\Gamma^{\prime}$ of size
$|C^{\prime}|\geq\exp(-\log^{O(1)}(\delta^{-1}))|\Gamma|$ and rank at most
$\log^{O(1)}(\delta^{-1})$ such that for each $x\in C^{\prime}$ there exist at
least $\Omega(\delta^{O(1)})|\Gamma|^{3}$ quadruples
$(a,b,c,d)\in{\Gamma^{\prime}}^{4}$ such that $a+b-c-d=x$. Averaging over
$b,c,d\in\Gamma^{\prime}$ we obtain an element $t\in G\times H$ such that
$|\Gamma^{\prime}\cap
C^{\prime}-t|\geq\exp(-\log^{O(1)}(\delta^{-1}))|\Gamma|$. Note also that
$|C^{\prime}|\leq|2\Gamma^{\prime}-2\Gamma^{\prime}|\leq
O(\delta^{-O(1)}|\Gamma|)$, by another application of the Plünnecke-Ruzsa
inequality. Returning to $\Gamma$ which contains the set $\Gamma^{\prime}$, we
conclude that there is proper coset progression $C=C^{\prime}-t$ of rank
$\log^{O(1)}(\delta^{-1})$ and $|\Gamma\cap C|=\alpha(|\Gamma|+|C|)$ for some
$\alpha\geq\exp(-\log^{O(1)}(\delta^{-1}))$.
Let $\pi\colon G\times H\to G$ be the projection onto the first coordinate.
Using Corollary 2.5, we may pass to a proper coset progression
$\tilde{C}\subseteq C$ on which $\pi$ is injective and which satisfies
$|\Gamma\cap\tilde{C}|\geq\exp(-\log^{O(1)}(\delta^{-1}))(|\Gamma|+|\tilde{C}|)$.
Let $Q=\pi(\tilde{C})$, which is a proper coset progession in $G$. Define the
map $\Phi\colon Q\to H$ by setting $\Phi(x)$ to be the unique element of $H$
such that $(x,\Phi(x))\in\tilde{C}$. Explicitly, we know that
$\tilde{C}=(x_{0},y_{0})+[M_{1}]\cdot(x_{1},y_{1})+\dots+[M_{r}]\cdot(x_{r},y_{r})+K^{\prime}$
for a subgroup $K^{\prime}\leq G\times H$. If $K^{\prime}$ is isomorphic to
$\mathbb{Z}/L_{1}\mathbb{Z}\oplus\dots\oplus\mathbb{Z}/L_{s}\mathbb{Z}$ for
suitable $L_{1},\dots,L_{s}$, we take arbitrary generator $(g_{i},h_{i})$ of
the summand $\mathbb{Z}/L_{i}\mathbb{Z}$. Thus

$\tilde{C}=(x_{0},y_{0})+[M_{1}]\cdot(x_{1},y_{1})+\dots+[M_{r}]\cdot(x_{r},y_{r})+[L_{1}]\cdot(g_{1},h_{1})+\dots+[L_{s}]\cdot(g_{s},h_{s}),$

which we use to define

$\Phi(x_{0}+\lambda_{1}x_{1}+\dots+\lambda_{r}x_{r}+\mu_{1}g_{1}+\dots+\mu_{s}g_{s})=y_{0}+\lambda_{1}y_{1}+\dots+\lambda_{r}y_{r}+\mu_{1}h_{1}+\dots+\mu_{s}h_{s},$

for $\lambda_{i}\in[M_{i}]$ and $\mu_{i}\in[L_{i}]$. This is a Freiman
homomorphism on $Q$ and $\Phi(x)=\phi(x)$ holds for at least
$\exp(-\log^{O(1)}(\delta^{-1}))|G|$ elements $x\in A\cap Q$, as desired.∎

Next, we use Freiman’s theorem to prove that intersections of coset
progressions are essentially still coset progressions. It is likely that this
fact can proved without using Freiman’s theorem, but given the negligible loss
in efficiency we opted to rely on it in order to simplify the proof.

######  Proposition 3.5.

Let $C_{1},\dots,C_{r}\subseteq G$ be proper coset progressions of rank at
most $d$. Suppose that we are given a set $X\subseteq C_{1}\cap\dots\cap
C_{r}$ of size $|X|\geq\delta|G|$. Then there is a proper coset progression
$C\subseteq C_{1}\cap\dots\cap C_{r}$ of rank at most
$(2dr\log\delta^{-1})^{O(1)}$ such that $|C\cap
X|\geq\exp(-(2dr\log\delta^{-1})^{O(1)})|G|$.

###### Proof.

Let $C_{i}=a_{i}+[0,N^{(i)}_{1}-1]\cdot
v^{(i)}_{1}+\dots+[0,N^{(i)}_{d}-1]\cdot v^{(i)}_{d}+H_{i}$ be $i$th proper
coset progression its canonical form for each $i\in[r]$. For $i\in[r]$,
$j\in[d]$, let $M^{(i)}_{j}=\Big{\lceil}\frac{\delta
N^{(i)}_{j}}{100dr}\Big{\rceil}$ and let $T^{(i)}_{j}=\lceil
N^{(i)}_{j}/M^{(i)}_{j}\rceil$. Consider the following sub-coset progressions
for each $i\in[r]$. For each $\ell\in[d]$, let $j_{\ell}$ range over
$[4,T^{(i)}_{\ell}-4]$ when $T^{(i)}_{\ell}\geq 50\delta^{-1}dr$. On the other
hand, when $T^{(i)}_{\ell}<50\delta^{-1}dr$, we redefine $M^{(i)}_{\ell}$ to
be 1, and also set $T^{(i)}_{\ell}$ to $N^{(i)}_{\ell}$ instead, which
satisfies $N^{(i)}_{\ell}\leq 100\delta^{-1}dr$ in this case, and we let
$j_{\ell}$ range over $[0,T^{(i)}_{\ell}]$. Let $\mathcal{J}_{i}$ be the set
of all $d$-tuples of indices $(j_{1},\dots,j_{d})$ that arise in this way.
Note also that in either case $T^{(i)}_{\ell}\leq 200\delta^{-1}dr$.
Given $(j_{1},\dots,j_{d})\in\mathcal{J}_{i}$, we define the coset progression

$C_{i,j_{1},\dots,j_{d}}=a_{i}+j_{1}M^{(i)}_{1}v^{(i)}_{1}+\dots+j_{d}M^{(i)}_{d}v^{(i)}_{d}+[0,M^{(i)}_{1}-1]\cdot
v^{(i)}_{1}+\dots+[0,M^{(i)}_{d}-1]\cdot v^{(i)}_{d}+H_{i}.$ (7)

For fixed $i$, the coset progressions $C_{i,j_{1},\dots,j_{d}}$ with different
indices $(j_{1},\dots,j_{d})$ are disjoint and they almost cover $C_{i}$ in
the sense that

$\Big{|}C_{i}\setminus\Big{(}\bigcup_{(j_{1},\dots,j_{d})\in\mathcal{J}_{i}}C_{i,j_{1},\dots,j_{d}}\Big{)}\Big{|}\leq\frac{\delta}{2r}|G|.$

Thus, we obtain

$\Big{|}X\cap\bigcap_{i\in[r]}\Big{(}\bigcup_{(j_{1},\dots,j_{r})\in\mathcal{J}_{i}}C_{i,j_{1},\dots,j_{r}}\Big{)}\Big{|}\geq\frac{\delta}{2}|G|.$

By averaging, we may find a coset progression $C^{\prime}_{i}$ of the form
$C_{i,j_{1},\dots,j_{r}}$ for each $i\in[r]$ such that

$|X\cap C^{\prime}_{1}\cap\dots\cap
C^{\prime}_{r}|\geq\frac{1}{2}\,\frac{\delta^{dr+1}}{(200rd)^{rd}}|G|.$

Write $Y=X\cap C^{\prime}_{1}\cap\dots\cap C^{\prime}_{r}$ and
$K=2\delta^{-(dr+1)}(200rd)^{rd}$, and let $y_{0}\in Y$ be an arbitrary
element. We claim that $y_{0}+4Y-4Y\subset C_{i}$ for each $i\in[r]$ and
therefore $y_{0}+4Y-4Y\subset C_{1}\cap\dots\cap C_{r}$. To that end, fix an
index $i\in[r]$. We have that $Y\subseteq C^{\prime}_{i}$ and $C^{\prime}_{i}$
is of the form (7) and in particular

$4Y-4Y\subseteq
4C^{\prime}_{i}-4C^{\prime}_{i}\subseteq[-4(M^{(i)}_{1}-1),4(M^{(i)}_{1}-1)]\cdot
v^{(i)}_{1}+\dots+[-4(M^{(i)}_{d}-1),4(M^{(i)}_{d}-1)]\cdot
v^{(i)}_{d}+H_{i}.$

By the way we defined the indices set $\mathcal{J}_{i}$ we conclude that
$y_{0}+4Y-4Y$ is indeed a subset of $C_{i}$, as claimed. Hence, given any
$y_{1},\dots,y_{8}\in Y$ we have that
$y_{0}+y_{1}+y_{2}+y_{3}+y_{4}-y_{5}-y_{6}-y_{7}-y_{8}\in C_{i}$.

Apply Theorem 3.2 to find a proper coset progression $C$ of rank at most
$(2\log K)^{O(1)}$ and size $|C|\geq\exp\Big{(}-(2\log K)^{O(1)}\Big{)}|G|$
such that for each $x\in C$ there are at least $\frac{1}{64K}|G|^{3}$
quadruples $(y_{1},y_{2},y_{3},y_{4})\in Y^{4}$ such that
$x=y_{1}+y_{2}-y_{3}-y_{4}$. By averaging, we may find $y_{2},y_{3},y_{4}\in
Y$ such that

$|C-y_{2}+y_{3}+y_{4}\cap Y|\geq\exp\Big{(}-(2\log K)^{O(1)}\Big{)}|G|.$

Finally, we have

$C-y_{2}+y_{3}+y_{4}\subseteq 2Y-2Y-Y+2Y=4Y-3Y\subseteq y_{0}+4Y-4Y\subseteq
C_{1}\cap\dots\cap C_{r},$

so we can take $C-y_{2}+y_{3}+y_{4}$ to be the desired coset progression.∎

Linear maps covering lemma. The vector space version of the following fact
plays an important role in the previous proofs of the bilinear Bogolyubov
argument. It essentially says that if we are given sets of bounded size that
have many linear relationships between them, then we can hit significant
proportion of the sets by images of a single linear function. The formulation
below is a generalization of Lemma 2.1 in [11].

######  Lemma 3.6.

Let $G$ and $H$ be finite abelian groups and let $A\subseteq G$. For each
$a\in A$, let $U_{a}\subseteq H$ be a set of size at most $K$. Let
$L_{1}\colon C_{1}\to H,\dots,L_{m}\colon C_{m}\to H$ be Freiman homomorphisms
with domains $C_{1},\dots,C_{m}\subseteq G$ which are proper coset
progressions. Assume that one of these maps is the zero map $g\mapsto 0$
defined for all $g\in G$. Suppose that for each $a\in A$ we have chosen a
subset of these maps denoted by
$\mathcal{L}_{a}\subseteq\\{L_{1},\dots,L_{m}\\}$ so that the zero map belongs
to all subsets, i.e $0\in\mathcal{L}_{a}$. Write
$\mathcal{L}_{a}(a)=\\{L(a)\colon L\in\mathcal{L}_{a}\\}$. Suppose that the
properties $z,w,y+z,y+w\in A$ and

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\not\subseteq(\mathcal{L}_{y+z}(y+z)-\mathcal{L}_{z}(z))+(\mathcal{L}_{y+w}(y+w)-\mathcal{L}_{w}(w))$

hold for at least $\varepsilon|G|^{3}$ choices of $y,z,w\in G$. Then, provided
$|G|\geq 100K^{4}\varepsilon^{-1}$, there exists a Freiman homomorphism
$L\colon C\to H$ defined on a proper coset progression $C$ of rank at most
$\log^{O(1)}(\varepsilon^{-1}K)$ such that $L(y)\in
U_{y}\setminus\mathcal{L}_{y}(y)$ holds for at least
$\exp\Big{(}-\log^{O(1)}(\varepsilon^{-1}K)\Big{)}|G|$ elements $y\in C\cap
A$.

We do not use the facts that $C_{1},\dots,C_{m}$ are coset progressions and
that $L_{1},\dots,L_{m}$ are Freiman homomorphisms in the proof of the lemma,
but we opted for this formulation as the relevant maps will have this
structure when the lemma is applied.

###### Proof.

Consider a choice of $y,z,w\in G$ such that $z,w,y+z,y+w\in A$ and

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\not\subseteq(\mathcal{L}_{y+z}(y+z)-\mathcal{L}_{z}(z))+(\mathcal{L}_{y+w}(y+w)-\mathcal{L}_{w}(w)).$

Thus, there are elements $a\in U_{y+z},b\in U_{z},c\in U_{y+w},d\in U_{w}$
such that
$a-b=c-d\notin(\mathcal{L}_{y+z}(y+z)-\mathcal{L}_{z}(z))+(\mathcal{L}_{y+w}(y+w)-\mathcal{L}_{w}(w))$.
Since $0\in\mathcal{L}_{t}(t)$ for all $t$, we see that we cannot have
$a\in\mathcal{L}_{y+z}(y+z)$ and $b\in\mathcal{L}_{z}(z)$ simultaneously.
Similarly, we cannot have $c\in\mathcal{L}_{y+w}(y+w)$ and
$d\in\mathcal{L}_{w}(w)$ simultaneously. Thus

$\Big{(}a\notin\mathcal{L}_{y+z}(y+z)\,\text{OR}\,b\notin\mathcal{L}_{z}(z)\Big{)}\,\text{AND}\,\Big{(}c\notin\mathcal{L}_{y+w}(y+w)\,\text{OR}\,d\notin\mathcal{L}_{w}(w)\Big{)}.$

This implies one of the four possibilities:

  * •

$a\notin\mathcal{L}_{y+z}(y+z)$ AND $c\notin\mathcal{L}_{y+w}(y+w)$,

  * •

$a\notin\mathcal{L}_{y+z}(y+z)$ AND $d\notin\mathcal{L}_{w}(w)$,

  * •

$b\notin\mathcal{L}_{z}(z)$ AND $c\notin\mathcal{L}_{y+w}(y+w)$,

  * •

$b\notin\mathcal{L}_{z}(z)$ AND $d\notin\mathcal{L}_{w}(w)$.

Without loss of generality, the last possibility occurs most frequently.
Therefore, we obtain a set $T\subseteq G^{3}$ of size
$|T|\geq\frac{\varepsilon}{4}|G|^{3}$ consisting of triples $(y,z,w)\in G^{3}$
such that $z,w,y+z,y+w\in A$,

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\not\subseteq(\mathcal{L}_{y+z}(y+z)-\mathcal{L}_{z}(z))+(\mathcal{L}_{y+w}(y+w)-\mathcal{L}_{w}(w)),$

and there are elements $a=a(y,z,w)\in U_{y+z},b=b(y,z,w)\in
U_{z}\setminus\mathcal{L}_{z}(z),c=c(y,z,w)\in U_{y+w},d=d(y,z,w)\in
U_{w}\setminus\mathcal{L}_{w}(w)$ that satisfy $a-b=c-d$.

For each $y\in A$, pick a random value $f(y)\in U_{y}$ uniformly and
independently. For each $(y,z,w)\in T$ such that the elements $z,w,y+z,y+w$
are distinct we have

$\mathbb{P}\Big{(}f(y+z)=a(y,z,w),f(z)=b(y,z,w),f(y+w)=c(y,z,w),f(w)=d(y,z,w)\Big{)}\geq
K^{-4}.$

By linearity of expectation, there is a choice of $f$ such that the equalities
$f(y+z)=a(y,z,w)$, $f(z)=b(y,z,w)$, $f(y+w)=c(y,z,w)$ and $f(w)=d(y,z,w)$ hold
for at least $\frac{\varepsilon}{4K^{4}}|G|^{3}-6|G|^{2}$ choices of
$(y,z,w)\in T$. Let $T^{\prime}$ be the subset of such triples. Let
$A^{\prime}=\\{x\in A\colon f(x)\in U_{x}\setminus\mathcal{L}_{x}(x)\\}$.
Recalling that $b(y,z,w)\in U_{z}\setminus\mathcal{L}_{z}(z)$ and that
$d(y,z,w)\in U_{w}\setminus\mathcal{L}_{w}(w)$ hold for all triples
$(y,z,w)\in T$, we conclude that $(y,z,w)\in T^{\prime}$ implies $z,w\in
A^{\prime}$.
Recalling also that $a(y,z,w)-b(y,z,w)=c(y,z,w)-d(y,z,w)$ holds for all
$(y,z,w)\in T$, it follows that there are at least
$\frac{\varepsilon}{4K^{4}}|G|^{3}-6|G|^{2}\geq\frac{\varepsilon}{8K^{4}}|G|^{3}$
quadruples $(a^{\prime},b^{\prime},c^{\prime},d^{\prime})\in A\times
A^{\prime}\times A\times A^{\prime}$ such that
$a^{\prime}-b^{\prime}=c^{\prime}-d^{\prime}$ and
$f(a^{\prime})-f(b^{\prime})=f(c^{\prime})-f(d^{\prime})$, which can be
rewritten as $a^{\prime}-c^{\prime}=b^{\prime}-d^{\prime}$ and
$f(a^{\prime})-f(c^{\prime})=f(b^{\prime})-f(d^{\prime})$. (We used the
assumption $|G|\geq 100K^{4}\varepsilon^{-1}$ to simplify the inequality
above.) By Cauchy-Scwarz inequality, it follows that the restriction
$f|_{A^{\prime}}$ respects at least
$\Omega\Big{(}\varepsilon^{2}K^{-8}|G|^{3}\Big{)}$ additive quadruples.
Apply Theorem 3.4 to obtain a proper coset progression $C$ of rank
$\log^{O(1)}(\varepsilon^{-1}K)$ and a Freiman homomorphism $L\colon C\to H$
such that $L(x)=f(x)$ holds for at least
$\exp\Big{(}-\log^{O(1)}(\varepsilon^{-1}K)\Big{)}|G|$ of $x\in C\cap
A^{\prime}$. In particular, such an element $x$ also satisfies $L(x)\in
U_{x}\setminus\mathcal{L}_{x}(x)$, as desired.∎

Applying the lemma iteratively gives the following corollary.

######  Corollary 3.7.

Let $G$ and $H$ be finite abelian groups. Let $A\subset G$ be a subset of
density $\alpha$. For each $a\in A$, let $U_{a}\subseteq H$ be a set of size
at most $K$ containing 0. Assume $|G|\geq 2000K^{4}\alpha^{-4}$. Then there
exist a positive integer $m\leq\exp\Big{(}\log^{O(1)}(\alpha^{-1}K)\Big{)}$,
proper coset progressions $C_{1},\dots,C_{m}$ of rank at most
$\log^{O(1)}(\alpha^{-1}K)$ and Freiman homomorphisms $L_{1}\colon C_{1}\to
H,\dots,L_{m}\colon C_{m}\to H$ such that, writing
$U^{\prime}_{a}=\\{L_{i}(a)\colon i\in[m],a\in C_{i}\\}\cap U_{a}$ for each
$a\in A$, we have $y+z,z,y+w,w\in A$ and

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\subseteq(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w})$

for at least $\frac{\alpha^{4}}{2}|G|^{3}$ of $y,z,w\in G$.

###### Proof.

We begin with defining $L_{1}\colon G\to H$ to be the zero map $x\mapsto 0$.
We iteratively find further maps $L_{2},L_{3},\dots$ as long as the conclusion
is not satisfied.
Suppose therefore that so far we have found Freiman homomorphisms $L_{1}\colon
C_{1}\to H,\dots,L_{s}\colon C_{s}\to H$ such that for at least
$\frac{\alpha^{4}}{2}|G|^{3}$ triples $(y,z,w)\in G^{3}$ we have
$y+z,z,y+w,w\in A$ but

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\not\subseteq(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w}),$

where we used the basic fact that the number of additive quadruples in $A$ is
at least $\alpha^{4}|G|^{3}$. We may use Lemma 3.6, where we set
$\mathcal{L}_{a}$ to consist of those maps $L_{i}$ such that $a\in C_{i}$ and
$L_{i}(a)\in U_{a}$. Note that since $0\in U_{a}$ we have
$L_{1}\in\mathcal{L}_{a}$ as required by the lemma and that $|G|\geq
2000K^{4}\alpha^{-4}$ ensure the requirement on the size of $G$ is met. The
lemma produces a proper coset progression $C_{s+1}$ of rank at most
$\log^{O(1)}(\alpha^{-1}K)$ and a Freiman homomorphism $L_{s+1}\colon
C_{s+1}\to H$ such that $L_{s+1}(y)\in U_{y}\setminus U^{\prime}_{y}$ for at
least $\exp\Big{(}-\log^{O(1)}(\alpha^{-1}K)\Big{)}|G|$ of $y\in C_{s+1}\cap
A$. The procedure necessarily terminates after at most
$\exp\Big{(}\log^{O(1)}(\alpha^{-1}K)\Big{)}$ steps as each time we cover at
least $\exp\Big{(}-\log^{O(1)}(\alpha^{-1}K)\Big{)}|G|$ pairs of the form
$(y,h)$ for some $y\in A$ and $h\in U_{y}\setminus U^{\prime}_{y}$ by pairs of
the form $(y,L_{s+1}(y))$ and the total number of pairs that we start with is
at most $\sum_{y\in A}|U_{y}|\leq K|G|$.∎

## §4 Behaviour of Bohr sets

In this section we recall the definition of Bohr sets, study their properties
motivated by linear algebra and in particular derive an approximate formula
that controls their size.

Bohr sets. Let $G$ be a finite abelian group. By the fundamental theorem for
finitely generated abelian groups, we know that $G$ can without loss of
generality be taken to be of the form
$G=\mathbb{Z}/q_{1}\mathbb{Z}\,\oplus\,\mathbb{Z}/q_{2}\mathbb{Z}\,\oplus\,\dots\,\oplus\,\mathbb{Z}/q_{d}\mathbb{Z}$
for some natural numbers $q_{1},\dots,q_{d}$ such that
$q_{1}|q_{2}|\dots|q_{k}$. The dual group of $G$, denoted by $\hat{G}$,
consists of characters of $G$, which we view as homomorphisms between abelian
groups $G$ and $\mathbb{T}=\mathbb{R}/\mathbb{Z}$. We may put $\hat{G}$ in the
following, explicit form. The dual group $\hat{G}$ has the structure
$\mathbb{Z}/q_{1}\mathbb{Z}\,\oplus\,\mathbb{Z}/q_{2}\mathbb{Z}\,\oplus\,\dots\,\oplus\,\mathbb{Z}/q_{d}\mathbb{Z}$
as well. To see this, notice that for each $\chi\in\hat{G}$, there exist
unique elements $\chi_{i}\in\mathbb{Z}/q_{i}\mathbb{Z}$ for each $i\in[d]$
such that

$\chi(x)=\sum_{i\in[d]}\frac{|\chi_{i}x_{i}|_{q_{i}}}{q_{i}}+\mathbb{Z},$

where
$|\cdot|_{q}\colon\mathbb{Z}/q\mathbb{Z}\to\\{0,1,\dots,q-1\\}\subseteq\mathbb{Z}$
is a map which maps each residue to the unique integer among
$\\{0,1,\dots,q-1\\}$ that projects to it inside $\mathbb{Z}/q\mathbb{Z}$.
Write $\operatorname{e}(t)=\exp(2\pi it)$ for $t\in\mathbb{R}$. For
$x\in\mathbb{R}/\mathbb{Z}$ let $|x|_{\mathbb{T}}$ be the element
$d\in[0,1/2]$ such that $x\in\\{-d,d\\}+\mathbb{Z}$, i.e. the distance from 0.
Given a set of characters $\Gamma\subseteq\hat{G}$ and a positive real $\rho$
we define the _Bohr set_ with _frequency set_ $\Gamma$ and _width_ $\rho$ as
$B(\Gamma;\rho)=\\{x\in
G\colon\max_{\chi\in\Gamma}|\chi(x)|_{\mathbb{T}}\leq\rho\\}$.

The most basic fact about Bohr sets is that they are necessarily dense and of
small doubling.

######  Lemma 4.1 (Lemma 4.20 in [16]).

For $\Gamma\subseteq\hat{G}$ and $\rho>0$ we have

$|B(\Gamma;\rho)|\geq\rho^{|\Gamma|}|G|$

and

$|B(\Gamma;2\rho)|\leq 4^{|\Gamma|}|B(\Gamma;\rho)|.$

The following elementary lemma shows that very dense subsets of Bohr sets
contain large Bohr sets in their difference set.

######  Lemma 4.2.

Let $A\subset B(\Gamma;\rho)$ be a set of size at least
$(1-4^{-k-1})|B(\Gamma;\rho)|$ where $k=|\Gamma|$. Then $A-A\supseteq
B(\Gamma;\rho/2)$.

###### Proof.

Let $x\in B(\Gamma;\rho/2)$ be arbitrary. Then $x+B(\Gamma;\rho/2)\subseteq
B(\Gamma;\rho)$ so we have

$|A\cap x+B(\Gamma;\rho/2)|\geq|B(\Gamma;\rho/2)|-|B(\Gamma;\rho)\setminus
A|\geq|B(\Gamma;\rho/2)|-4^{-k-1}|B(\Gamma;\rho)|\geq\frac{3}{4}|B(\Gamma;\rho/2)|,$

where we used Lemma 4.1 in the last inequality.
Specializing to $x=0$, we see that $|A\cap
B(\Gamma;\rho/2)|\geq\frac{3}{4}|B(\Gamma;\rho/2)|$. Thus, there is $a\in
B(\Gamma;\rho/2)\cap A\cap(A-x)$, so we obtain $a,a+x\in A$, as required.∎

Fourier analysis on Bohr sets. The following proposition determines the
behaviour of size of Bohr sets.

######  Proposition 4.3 (Size of Bohr sets).

Let $k\in\mathbb{N}$ and let $\rho,\eta,\varepsilon>0$. Then, there exist a
positive integer $K\leq O(k\varepsilon^{-1}\eta^{-1})$ and quantities
$c_{i}\in\mathbb{D}$ for $i\in[-K,K]$ for which the following holds.
Let $G$ be a finite abelian group. Suppose that
$\gamma_{1},\dots,\gamma_{k}\in\hat{G}$ and that

$|B(\gamma_{1},\dots,\gamma_{k};\rho+\eta)\setminus
B(\gamma_{1},\dots,\gamma_{k};\rho)|\leq\varepsilon|G|.$ (8)

Then

$\Big{|}|B(\gamma_{1},\dots,\gamma_{k};\rho)|-\sum_{a_{1},\dots,a_{k}\in[-K,K]}\mathbbm{1}(a_{1}\gamma_{1}+\dots+a_{k}\gamma_{k}=0)c_{a_{1}}\dots
c_{a_{k}}|G|\Big{|}\leq 2\varepsilon|G|.$

Remark. The proof gives explicit coefficients

$c_{a}=\eta^{-1}\frac{\Big{(}\operatorname{e}(a(\rho+\eta/2))-\operatorname{e}(-a(\rho+\eta/2))\Big{)}\Big{(}\operatorname{e}(a\eta/2)-\operatorname{e}(-a\eta/2)\Big{)}}{4\pi^{2}a^{2}},$

which do not depend on the ambient abelian group $G$, but we shall not need
this fact.

We refer to property (8) as _weak-regularity_. We opted for this notion
instead of that of a regular Bohr set, which is usually used, since the weak-
regularity condition is precisely what we need and it is easy to obtain an
abundance of parameters $\eta$ and $\rho$ that satisfy (8).

###### Proof.

Let $I,J\subseteq\mathbb{T}$ be the intervals
$I=[-(\rho+\eta/2),(\rho+\eta/2)]$ and $J=[-\eta N/2,\eta N/2]$. The function
$f(x)=\eta^{-1}I*J(x)$ satisfies $f(x)=1$ when $x\in[-\rho,\rho]$,
$f(x)=\frac{\rho+\eta-|x|_{\mathbb{T}}}{\eta}\in[0,1]$ when
$|x|_{\mathbb{T}}\in[\rho,\rho+\eta]$ and $f(x)=0$ when
$x\notin[-(\rho+\eta),\rho+\eta]$. It follows that

$|G|^{-1}|B(\gamma_{1},\dots,\gamma_{k};\rho)|\leq\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{k}(x))\leq|G|^{-1}|B(\gamma_{1},\dots,\gamma_{k};\rho+\eta)|.$

By assumption on the sizes of Bohr sets, we obtain

$\Big{|}|B(\gamma_{1},\dots,\gamma_{k};\rho)|-|G|\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{k}(x))\Big{|}\leq\varepsilon|G|.$

We use Fourier analysis on $\mathbb{T}$ to estimate the expectation
$\mathop{\mathbb{E}}_{x\in|G|}f(\gamma_{1}x)\dots f(\gamma_{k}x)$. To simplify
the notation, we use integers directly instead of continuous characters on
$\mathbb{T}$, but we still use small greek letters to denote frequencies. The
key property of $f$ is that it can be well-approximated in the $L^{\infty}$
sense by a finite sum coming from the truncation of its inverse Fourier
transform. An important and standard fact is that the large spectrum of an
interval consists of small values.

######  Claim 4.4.

Let $\xi\in\mathbb{Z}\setminus\\{0\\}$. Then
$|\hat{f}(\xi)|\leq\eta^{-1}/\xi^{2}$.

###### Proof of the claim.

The Fourier coefficient at $\xi$ of an arbitrary interval $[-t,t]$ is given by

$\int_{-t}^{t}\operatorname{e}(-\xi x)dx=\frac{\operatorname{e}(\xi
t)-\operatorname{e}(-\xi t)}{2\pi i\xi},$

which is at most $\frac{1}{\pi|\xi|}$ in absolute value. Since
$\hat{f}(\xi)=\eta^{-1}\hat{I}(\xi)\hat{J}(\xi)$, the claim follows.∎

This rapid decay of Fourier coefficients allows us to deduce the desired
approximation property for $f$.

######  Claim 4.5.

Let $S\subseteq\mathbb{Z}$ be a finite set that contains the interval $[-L,L]$
for some $L>0$ (and possibly some other elements). Then

$\Big{|}f(x)-\sum_{\xi\in S}\hat{f}(\xi)\operatorname{e}(\xi x)\Big{|}\leq
2\eta^{-1}/L$

for all $x\in\mathbb{T}$.

###### Proof of the claim.

Using the inverse Fourier transform (which converges to $f(x)$ by Dirichlet’s
theorem, as $f$ is piecewise smooth) and Claim 4.4, we obtain

$\displaystyle\Big{|}f(x)-\sum_{\xi\in S}\hat{f}(\xi)\operatorname{e}(\xi
x)\Big{|}=\,$ $\displaystyle\Big{|}\sum_{\xi\notin
S}\hat{f}(\xi)\operatorname{e}(\xi x)\Big{|}\leq\sum_{\gamma\notin
S}|\hat{f}(\xi)|\leq\,2\eta^{-1}\sum_{\xi=L+1}^{\infty}\frac{1}{\xi^{2}}\leq\frac{2\eta^{-1}}{L}.\qed$

Let $K=2ek\eta^{-1}\varepsilon^{-1}$. Write
$s(x)=\sum_{\xi\in[-K,K]}\hat{f}(\xi)\operatorname{e}(\xi x)$. Thus,
$\|f-s\|_{L^{\infty}}\leq\frac{\varepsilon}{ek}$. In particular,
$\|s\|_{L^{\infty}}\leq 1+\frac{1}{k}$. Using this, we obtain

$\displaystyle\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{k}(x))-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}s(\gamma_{1}(x))\dots
s(\gamma_{k}(x))\Big{|}$ $\displaystyle\hskip
56.9055pt\leq\sum_{i\in[k]}\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{i-1}(x))\,(f(\gamma_{i}(x))-s(\gamma_{i}(x)))\,s(\gamma_{i+1}(x))\dots
s(\gamma_{k}(x))\Big{|}$ $\displaystyle\hskip 56.9055pt\leq
k\Big{(}1+\frac{1}{k}\Big{)}^{k}\|f-s\|_{L^{\infty}}\leq\varepsilon.$ (9)

By our work so far, we have

$\bigg{|}|G|^{-1}|B(\gamma_{1},\dots,\gamma_{k};\rho)|-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}\Big{(}\sum_{a_{1}\in[-K,K]}\hat{f}(a_{1})\operatorname{e}(a_{1}\gamma_{1}(x))\Big{)}\cdots\Big{(}\sum_{a_{k}\in[-K,K]}\hat{f}(a_{k})\operatorname{e}(a_{k}\gamma_{k}(x))\Big{)}\bigg{|}\leq
2\varepsilon.$

Finally,

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}\Big{(}\sum_{a_{1}\in[-K,K]}\hat{f}(a_{1})\operatorname{e}\Big{(}a_{1}\gamma_{1}(x)\Big{)}\Big{)}\cdots\Big{(}\sum_{a_{k}\in[-K,K]}\hat{f}(a_{k})\operatorname{e}\Big{(}a_{k}\gamma_{k}(x)\Big{)}\Big{)}$
$\displaystyle\hskip
56.9055pt=\sum_{a_{1},\dots,a_{k}\in[-K,K]}\hat{f}(a_{1})\cdots\hat{f}(a_{k})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}\operatorname{e}\Big{(}(a_{1}\gamma_{1}+\dots+a_{k}\gamma_{k})(x)\Big{)}$
$\displaystyle\hskip
56.9055pt=\sum_{a_{1},\dots,a_{k}\in[-K,K]}\mathbbm{1}(a_{1}\gamma_{1}+\dots+a_{k}\gamma_{k}=0)\hat{f}(a_{1})\cdots\hat{f}(a_{k}).$

The Fourier coefficients $\hat{f}(a)$ are the desired quantities $c_{a}$, thus

$\displaystyle c_{a}=\int_{0}^{1}f(x)\operatorname{e}(-ax)dx=$
$\displaystyle\eta^{-1}\int_{y=-\rho-\eta/2}^{\rho+\eta/2}\int_{z=-\eta/2}^{\eta/2}\operatorname{e}(-a(y+z))dydz$
$\displaystyle=$
$\displaystyle\eta^{-1}\frac{\Big{(}\operatorname{e}(a(\rho+\eta/2))-\operatorname{e}(-a(\rho+\eta/2))\Big{)}\Big{(}\operatorname{e}(a\eta/2)-\operatorname{e}(-a\eta/2)\Big{)}}{4\pi^{2}a^{2}}.$

Since $\|f\|_{L^{\infty}}\leq 1$ we also have $c_{a}\in\mathbb{D}$.∎

For a sequence $s_{1},\dots,s_{k}$ of elements of an abelian group, we define
its _annihilator lattice_ $\Lambda_{\perp}(s_{1},\dots,$
$s_{k})\subset\mathbb{Z}^{k}$ as
$\Lambda_{\perp}(s_{1},\dots,s_{k})=\\{(\lambda_{1},\dots,\lambda_{k})\in\mathbb{Z}^{k}\colon\sum_{i\in[k]}\lambda_{i}s_{i}=0\\}$.
Previous proposition tells us that the size of a Bohr set
$B(\gamma_{1},\dots,\gamma_{k};\rho)$ is essentially determined by the
intersection of the annihilator lattice
$\Lambda_{\perp}(\gamma_{1},\dots,\gamma_{k})$ with a bounded box in
$\mathbb{Z}^{k}$.

We may reuse most of the proof above to prove that the large Fourier
coefficients of a weakly-regular Bohr set come from linear combinations of the
defining characters.

######  Proposition 4.6 (Large Spectrum of Bohr sets).

Let $k\in\mathbb{N}$ and let $\rho,\eta,\varepsilon>0$. Then, there exist a
positive integer $K\leq O(k\varepsilon^{-1}\eta^{-1})$ for which the following
holds.
Suppose that $\gamma_{1},\dots,\gamma_{k}\in\hat{G}$ and that

$|B(\gamma_{1},\dots,\gamma_{k};\rho+\eta)\setminus
B(\gamma_{1},\dots,\gamma_{k};\rho)|\leq\varepsilon|G|/2.$

Let $\chi\in\hat{G}$ be such that
$\Big{|}[B(\gamma_{1},\dots,\gamma_{k};\rho)]^{\wedge}(\chi)\Big{|}\geq\varepsilon$.
Then $\chi=a_{1}\gamma_{1}+\dots+a_{k}\gamma_{k}$ for some integers
$a_{1},\dots,a_{k}$ such that $|a_{i}|\leq K$.

###### Proof.

Let $f$ be as in the previous proof. Then

$\Big{|}[B(\gamma_{1},\dots,\gamma_{k};\rho)]^{\wedge}(\chi)-\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{k}(x))\operatorname{e}(-\chi x)\Big{|}\leq\varepsilon/2$

so we have

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}f(\gamma_{1}(x))\dots
f(\gamma_{k}(x))\operatorname{e}(-\chi x)\Big{|}\geq\varepsilon/2.$

Using Claims 4.4 and 4.5 as in the previous proof in inequality (9) we see
that for $K=8ek\eta^{-1}\varepsilon^{-1}$ (the only difference is that $K$ is
slightly larger this time) one has

$\Big{|}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}\Big{(}\sum_{a_{1}\in[-K,K]}\hat{f}(a_{1})\operatorname{e}(a_{1}\gamma_{1}(x))\Big{)}\dots\Big{(}\sum_{a_{k}\in[-K,K]}\hat{f}(a_{k})\operatorname{e}(a_{k}\gamma_{k}(x))\Big{)}\operatorname{e}(-\chi(x))\Big{|}\geq\varepsilon/4.$

In particular

$\displaystyle 0\not=$
$\displaystyle\sum_{a_{1}\in[-K,K],\dots,a_{k}\in[-K,K]}\hat{f}(a_{1})\dots\hat{f}(a_{k})\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in
G}\operatorname{e}\Big{(}(a_{1}\gamma_{1}+\dots
a_{k}\gamma_{k}-\chi)(x)\Big{)}$ $\displaystyle\hskip
56.9055pt=\sum_{a_{1}\in[-K,K],\dots,a_{k}\in[-K,K]}\hat{f}(a_{1})\dots\hat{f}(a_{k})\mathbbm{1}\Big{(}a_{1}\gamma_{1}+\dots
a_{k}\gamma_{k}=\chi\Big{)}.$

Thus there are $a_{1},\dots,a_{k}\in[-K,K]$ such that $a_{1}\gamma_{1}+\dots
a_{k}\gamma_{k}=\chi$.∎

Our next result about Bohr sets is a generalization of the fact that the dual
of the sum of two subspaces of a vector space is given by the intersection of
their duals. For a set $\Gamma=\\{\gamma_{1},\dots,\gamma_{k}\\}$ of elements
of an abelian group and a nonnegative integer $R$, we write
$\langle\Gamma\rangle_{R}$ for the set of all linear combinations
$\lambda_{1}\gamma_{1}+\dots+\lambda_{k}\gamma_{k}$, where
$\lambda_{1},\dots,\lambda_{k}\in[-R,R]\subseteq\mathbb{Z}$.

######  Theorem 4.7.

Let $\Gamma_{1},\Gamma_{2}\subset\hat{G}$ and $\rho_{1},\rho_{2}\in(0,1)$.
Then there is a positive integer
$R\leq(2\rho_{1}^{-1})^{O(|\Gamma_{1}|)}+(2\rho_{2}^{-1})^{O(|\Gamma_{2}|)}$
such that

$B(\langle\Gamma_{1}\rangle_{R}\cap\langle\Gamma_{2}\rangle_{R},1/4)\subseteq
B(\Gamma_{1},\rho_{1})+B(\Gamma_{2},\rho_{2}).$

###### Proof.

The proof is based on the Bogolyubov argument. Let
$\sigma_{1}\in[\rho_{1}/8,\rho_{1}/4]$ and
$\sigma_{2}\in[\rho_{2}/8,\rho_{2}/4]$, which we shall specify later. We need
some flexibility in the choice of radii in order to satisfy the weak-
regularity hypothesis for the resulting Bohr sets. Write
$B_{1}=B(\Gamma_{1},\sigma_{1})$ and $B_{2}=B(\Gamma_{2},\sigma_{2})$. Let
$f=B_{1}\ast B_{2}$. Hence, $f(x)\in[0,1]$ for all $x$ and
$\delta=\mathop{\mathbb{E}}_{x}f(x)$ satisfies
$\delta\geq\Big{(}\frac{\rho_{1}}{8}\Big{)}^{|\Gamma_{1}|}\Big{(}\frac{\rho_{2}}{8}\Big{)}^{|\Gamma_{2}|}$.
Observe that

$\operatorname{supp}f\ast f\ast f\ast f\subseteq
B(\Gamma_{1},\rho_{1})+B(\Gamma_{2},\rho_{2}).$

Using the inverse Fourier transform, we obtain

$f\ast f\ast f\ast
f(x)=\sum_{\gamma\in\hat{G}}\hat{f}(\gamma)^{4}\operatorname{e}(\gamma(x)).$

Let $\Gamma$ be the set of all characters $\gamma\in\hat{G}$ such that
$|\hat{f}(\gamma)|\geq\delta^{2}/10$. Then

$\Big{|}f\ast f\ast f\ast
f(x)-\sum_{\gamma\in\Gamma}\hat{f}(\gamma)^{4}\operatorname{e}(\gamma(x))\Big{|}\leq\sum_{\gamma\in\hat{G}\setminus\Gamma}\Big{|}\hat{f}(\gamma)^{4}\operatorname{e}(\gamma(x))\Big{|}\leq\max_{\gamma\notin\Gamma}|\hat{f}(\gamma)|^{2}\cdot\sum_{\gamma\in\hat{G}}|\hat{f}(\gamma)|^{2}\leq\frac{\delta^{4}}{100}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits_{x\in G}|f(x)|^{2}\leq\frac{\delta^{4}}{100}.$

Note that $\hat{f}(\gamma)\in\mathbb{R}$ for all $\gamma\in\hat{G}$ since $f$
is a symmetric function. Furthermore, we have
$\operatorname{Re}\operatorname{e}(\gamma(x))\geq 0$ for $\gamma\in\Gamma$ and
$x\in B(\Gamma;1/4)$, and $\hat{f}(0)^{4}=\delta^{4}$. Therefore, $x\in
B(\Gamma;1/4)$ gives $f\ast f\ast f\ast f(x)\not=0$, which further implies
that $x\in B(\Gamma_{1},\rho_{1})+B(\Gamma_{2},\rho_{2})$.

Finally, since $\hat{f}=\hat{B}_{1}\hat{B}_{2}$, we have that every
$\gamma\in\Gamma$ satisfies
$|\hat{B}_{1}(\gamma)|,|\hat{B}_{2}(\gamma)|\geq\delta^{2}/10$. We now pick
$\sigma_{1}$ and $\sigma_{2}$. Start with $\sigma_{1}=\rho_{1}/4$ and move
towards $\rho_{1}/8$ in steps of $\rho_{1}\delta^{2}/200$ each time we have

$\Big{|}B(\Gamma_{1},\sigma_{1})\setminus
B(\Gamma_{1};\sigma_{1}-\rho_{1}\delta^{2}/200)\Big{|}\geq\frac{\delta^{2}}{20}|G|.$

At the end of the procedure we obtain $\sigma_{1}\geq\rho_{1}/8$ and the
required weak regularity of $B_{1}$. The same arguments applies to
$\sigma_{2}$. Proposition 4.6 implies that
$\gamma\in\langle\Gamma_{1}\rangle_{R}\cap\langle\Gamma_{2}\rangle_{R}$ for
some $R\leq
O((|\Gamma_{1}|\rho^{-1}_{1}+|\Gamma_{2}|\rho^{-1}_{2})\delta^{-4})\leq(2\rho_{1}^{-1})^{O(|\Gamma_{1}|)}+(2\rho_{2}^{-1})^{O(|\Gamma_{2}|)}$,
completing the proof.∎

Bohr sets inside coset progressions. A fundamental fact about Bohr sets is
that they contain dense coset progressions of bounded rank. We now prove the
opposite statement, namely that dense bounded rank coset progressions contain
Bohr sets of relatively large radius and relatively small frequency set.

######  Proposition 4.8.

Let $C$ be a symmetric coset progression of rank $r$ and density $\alpha$
inside $G$. Then there is a positive integer
$R\leq(r\log(\alpha^{-1}))^{O(1)}$ and characters
$\chi_{1},\dots,\chi_{R}\in\hat{G}$ such that
$B(\chi_{1},\dots,\chi_{R};1/(4R))\subseteq C$.

###### Proof.

Let $C=[-N_{1},N_{1}]\cdot x_{1}+\dots+[-N_{r},N_{r}]\cdot x_{r}+H$ be the
canonical form of $C$. Let $d$ be a positive integer to be chosen later.
Ignore those $N_{i}$ that satisfy $N_{i}\leq d^{3}$ by setting them to 0
instead. This allows us to assume $N_{i}\geq d^{3}$ without loss of
generality, at the cost of decreasing the density of $C$ to $\alpha d^{-3r}$.
Consider another symmetric coset progression of rank $r$ given by shrinking
$C$ by a factor of roughly $d$, namely
$Q=[-N^{\prime}_{1},N^{\prime}_{1}]\cdot
x_{1}+\dots+[-N^{\prime}_{r},N^{\prime}_{r}]\cdot x_{r}$, where
$N^{\prime}_{i}=\lfloor\frac{N_{i}}{d}\rfloor$. Since $N_{i}\geq d^{3}$ for
all $i\in[r]$, we have $dQ\subseteq C\subseteq(d+1)Q$.

Using the inverse Fourier transform, we have

$\underbrace{Q\ast Q\ast\dots\ast
Q}_{d}(x)=\sum_{\gamma\in\hat{G}}\hat{Q}(\gamma)^{d}\operatorname{e}(\gamma(x)).$

Let $\delta$ be the density of $Q$. Thus $\delta\geq d^{-4r}\alpha$. Let
$\Gamma$ be the set of $\gamma\in\hat{G}$ such that
$|\hat{Q}(\gamma)|\geq\xi$, for some $\xi$ to be chosen. Then

$\Big{|}\underbrace{Q\ast Q\ast\dots\ast
Q}_{d}(x)-\Big{(}\delta^{d}+\sum_{\gamma\in\Gamma\setminus\\{0\\}}\hat{Q}(\gamma)^{d}\operatorname{e}(\gamma(x))\Big{)}\Big{|}\leq\xi^{d-2}\delta.$

Note that $Q$ is symmetric and thus $\hat{Q}(\gamma)^{d}\in\mathbb{R}_{\geq
0}$ when $d$ is an even integer. Hence, provided we take
$\xi=\frac{1}{2}\delta^{1+\frac{1}{d-2}}$, $B(\Gamma,1/4)\subseteq P$. By
Chang’s theorem [4] (see also Lemma 4.36 in [16]), there exists a set
$\Psi\subseteq\hat{G}$ of size

$R\leq O(\delta^{-2/(d-2)}\log(\delta^{-1}))$

such that every element of $\Gamma$ is a $\\{-1,0,1\\}$-linear combination of
elements in $\Psi$. In particular,

$B(\Psi;1/(4R))\subseteq B(\Gamma,1/4)\subseteq P.$

Recall that $\delta\geq\alpha d^{-4r}$. Thus,

$R\leq O(\delta^{-2/(d-2)}\log(\delta^{-1}))\leq
O\Big{(}\alpha^{-2/(d-2)}d^{8r/(d-2)}(\log\alpha^{-1}+4r\log d)\Big{)}.$

We may pick an even integer $d\leq(r\log\alpha^{-1})^{O(1)}$ to finish the
proof.∎

We may use this proposition to get a conclusion of Theorem 3.1 which involves
Bohr sets rather than coset progressions.

######  Corollary 4.9.

Suppose that $A\subset G$ is a set of density $\delta$. Then $2A-2A$ contains
a Bohr set of codimension at most $\log^{O(1)}\delta^{-1}$ and radius at least
$\Big{(}\log^{O(1)}\delta^{-1}\Big{)}^{-1}$.

## §5 Quantitative fundamental theorem of lattices

Recall that the fundamental theorem of lattices (Lemma 3.4 in [16]) states
that lattices of rank $k$ (meaning the maximal linearly independent subset is
of size $k$) are precisely of the form $\mathbb{Z}\cdot
v_{1}+\dots+\mathbb{Z}\cdot v_{k}$ for some independent $v_{1},\dots,v_{k}$.
Our goal is to prove a quantitative variant of this result. We need a
preliminary lemma that says that nested sequences of lattices inside a fixed
box terminate quickly.

######  Lemma 5.1.

Let $k$ and $K$ be positive integers. Suppose that
$\Lambda_{1}\subseteq\Lambda_{2}\subseteq\dots\subseteq\Lambda_{r}\subseteq\mathbb{Z}^{k}$
are lattices such that for each $i\in[r-1]$ the set-difference
$\Lambda_{i+1}\setminus\Lambda_{i}$ contains an element of the box
$[-K,K]^{k}$. Then $r\leq O(k^{2}(\log k+\log K))$.

This lemma will be used later in the paper as well, so we opted to state it
outside the proof of the main result on lattices.

###### Proof.

Without loss of generality we may assume that the given lattices are generated
by elements in the box $[-K,K]^{k}$. Note that the ranks of lattices
$\Lambda_{1},\dots$ are non-decreasing and at most $k$, so it suffices to show
that $m\leq O(k(\log k+\log K))$ when $\Lambda_{1},\dots,\Lambda_{m}$ all have
the same rank. By passing to a suitable subset of coordinates, we may in fact
assume that the ranks are $k$. The fact that $\Lambda_{1}$ is generated by $k$
independent vectors with coordinates bounded by $K$ in absolute value implies
the covolume bound $\det\Lambda_{1}\leq k!K^{k}$. We have
$\det\Lambda_{i+1}\leq\frac{1}{2}\det\Lambda_{i}$, so $m\leq O(k(\log k+\log
K))$.∎

The following theorem is a quantitative version of the fundamental theorem of
lattices. Instead of the full group $\mathbb{Z}^{m}$, we consider a truncated
version, namely the set $\langle a_{1},\dots,a_{k}\rangle_{R}$. We claim that
every subset $B\subseteq\langle a_{1},\dots,a_{k}\rangle_{R}$ is covered by
bounded linear combinations of a bounded number of elements
$b_{1},\dots,b_{\ell}$ in $B$. In comparison, the fundamental theorem of
lattices tells us that $B$ is contained in $\langle
b_{1},\dots,b_{\ell}\rangle$ for some $b_{1},\dots,b_{\ell}\in\langle
B\rangle$, where $\ell$ is exactly determined (it is the size of a maximal
independent set). We need more flexibility in the choice of $\ell$ in the
quantitative version as the example $B=\\{2,3\\}\subseteq\mathbb{Z}$ shows.
The main difference is that in our case we need elements from the original set
$B$ rather than its span $\langle B\rangle$.

######  Theorem 5.2.

Let $G$ be a finite abelian group, let $a_{1},\dots,a_{k}\in G$ and let $R$ be
a positive integer. Suppose that $B\subset\langle
a_{1},\dots,a_{k}\rangle_{R}$ is a non-empty set. Then, there exist positive
integers $\ell\leq O(k^{2}(\log k+\log R))$, $S\leq O((2Rk)^{k+3})$ and
elements $b_{1},\dots,b_{\ell}\in B$ such that $B\subseteq\langle
b_{1},\dots,b_{\ell}\rangle_{S}$.

###### Proof.

We pass to $\mathbb{Z}^{k}$ by choosing an arbitrary $k$-tuple
$(x_{1},\dots,x_{k})\in\mathbb{Z}^{k}$ such that
$b=x_{1}a_{1}+\dots+x_{k}a_{k}$ and $\|x\|_{L^{\infty}}\leq R$ for each $b\in
B$. Let $X\subseteq\mathbb{Z}^{k}$ be the set of the chosen $k$-tuples. We
iteratively find elements $x^{1},x^{2},\dots\in X$ by adding arbitrary
$x^{i+1}\in X\setminus\langle x^{1},\dots,x^{i}\rangle_{\mathbb{Z}}$ to the
list every time $X\not\subseteq\langle x^{1},\dots,x^{i}\rangle_{\mathbb{Z}}$.
By Lemma 5.1 this procedure terminates after $m\leq O(k^{2}(\log k+\log R))$
steps. It turns out that elements of $X$ are necessarily $\mathbb{Z}$-linear
combinations of $x^{1},x^{2},\dots$ with all coefficients bounded. This is the
content of the next lemma.

######  Lemma 5.3.

Suppose that $w\in\langle z^{1},\dots,z^{r}\rangle_{\mathbb{Z}}$ for some
$z^{1},\dots,z^{r}\in\mathbb{Z}^{k}$ with $\|z^{i}\|_{L^{\infty}}\leq K_{1}$
for $i\in[r]$ and $\|w\|_{L^{\infty}}\leq K_{2}$. Then there are
$\lambda_{1},\dots,\lambda_{r}\in\mathbb{Z}$ such that $|\lambda_{i}|\leq
k!K_{1}^{k+1}(K_{2}+r)$ for $i\in[r]$ and $w=\sum_{i\in[r]}\lambda_{i}z^{i}$.

###### Proof of the lemma..

Without loss of generality, $z^{1},\dots,z^{m}$ form a maximal
$\mathbb{Q}$-linearly independent subset of $z^{1},\dots,z^{r}$. Reordering
the coordinates if necessary, we may assume that $z^{1},\dots,z^{m}$ are still
independent when restricted to the first $m$ coordinates. Thus, we may assume
without loss of generality that $m=k$.
Consider the $m\times m$ matrix $Z=(z^{1}\,\,z^{2}\,\,\dots\,\,z^{m})$, which
is integral and invertible. For any $t\in\mathbb{Z}^{m}$ we have unique
$\mu_{1},\dots,\mu_{m}\in\mathbb{Q}$ such that $t=\sum_{i\in[m]}\mu_{i}z^{i}$.
In the matrix notation, $\mu\in\mathbb{Q}^{m}$ is the unique solution of the
equation $t=Z\mu$. Using the the adjugate matrix we obtain

$\det Z\,\mu=\operatorname{adj}Z\,t.$

In particular, $\det Z\,\mu$ is an integral vector. Using this observation for
$z^{m+1},\dots,z^{r}$ in place of $t$, it follows that $\det Zz^{j}$ is a
$\mathbb{Z}$-linear combination of $z^{1},\dots,z^{m}$ for every
$j\in[m+1,r]$. In particular, this means that we may find
$\lambda_{1},\dots,\lambda_{r}\in\mathbb{Z}$ such that
$|\lambda_{m+1}|,\dots,|\lambda_{r}|\leq|\det Z|$ and
$w=\sum_{i\in[r]}\lambda_{i}z^{i}$. It remains to bound the coefficients
$\lambda_{1},\dots,\lambda_{m}$. Using the equality

$w-\sum_{i\in[m+1,r]}\lambda_{i}z^{i}=Z(\lambda_{1}\,\,\dots\,\,\lambda_{m})^{T}$

and the invertibility of $Z$ we have

$(\lambda_{1}\,\,\dots\,\,\lambda_{m})^{T}=\frac{1}{\det
Z}\operatorname{adj}Z\Big{(}w-\sum_{i\in[m+1,r]}\lambda_{i}z^{i}\Big{)}.$

The bounds so far and the fact that $|\det Z|\geq 1$ imply that

$|\lambda_{1}|,\dots,|\lambda_{m}|\leq\frac{1}{|\det
Z|}m!K_{1}^{m}\Big{(}K_{2}+r|\det Z|K_{1}\Big{)}\leq m!K_{1}^{m+1}(K_{2}+r),$

concluding the proof.∎

Thus, $X\subset\langle x^{1},\dots,x^{m}\rangle_{S}$ for some $S\leq
k!R^{k+1}(R+m)$. Finally, we return from $\mathbb{Z}^{k}$ to the group $G$.
Let $b_{i}=\sum_{j\in[k]}x^{i}_{j}a_{j}$ for $i\in[m]$. Let $b\in B$ be an
arbitrary element. Then $b=\sum_{i\in[k]}\lambda_{i}a_{i}$ for some
$\lambda\in X$. Thus, there are coefficients $\mu_{1},\dots,\mu_{m}\in[-S,S]$
such that $\lambda=\sum_{i\in[m]}\mu_{i}x^{i}$. In particular

$b=\sum_{i\in[k]}\lambda_{i}a_{i}=\sum_{i\in[k],j\in[m]}\mu_{j}x^{j}_{i}a_{i}=\sum_{j\in[m]}\mu_{j}b_{j},$

proving that $B\subseteq\langle b_{1},\dots,b_{m}\rangle_{S}$.∎

## §6 Quasirandomness of Bilinear Bohr Varieties

Let $C$ be a symmetric proper coset progression of rank $d$ inside $H$, let
$\Gamma\subseteq\hat{G}$ be a set of characters and let
$L_{1},\dots,L_{r}\colon C\to\hat{G}$ be Freiman-linear maps on the coset
progression $C$. Define the _bilinear Bohr variety_

$W=(B(\Gamma;\rho)\times C)\cap\Big{(}\cup_{y\in
C}B(L_{1}(y),\dots,L_{r}(y);\rho)\times\\{y\\}\Big{)}.$

We view $W$ as a bipartite graph between the vertex classes $B(\Gamma;\rho)$
and $C$. In this section we study quasirandomness properties of bilinear Bohr
varieties, generalizing the results in [6] and [8]. The main result is an
algebraic regularity lemma which essentially enables us to partition $W$ into
quasirandom pieces of the form $W\cap(G\times C_{i})$, where
$C=C_{1}\cup\dots\cup C_{m}$ is a partition of the vertex class $C$ into
further coset progressions. There is a minor caveat that we might need to
decrease the radius $\rho$ slightly on each piece.
The particular choice of $B(\Gamma;\rho)\times C$ instead of a product of two
Bohr sets or two coset progressions is of minor importance, given that Bohr
sets and coset progressions are essentially equivalent, but it seems to give
the cleanest statement of the algebraic regularity lemma.

######  Theorem 6.1.

Let $G$ and $H$ be finite abelian groups. Let $C$ be a symmetric proper coset
progression of rank $d$ inside the group $H$, let $\Gamma\subseteq\hat{G}$ and
let $L_{1},\dots,L_{r}\colon C\to\hat{G}$ be Freiman-linear maps. Let $\rho>0$
and $\eta>0$ be given. We may partition $C$ into further proper coset
progressions $C_{1},\dots,C_{m}$ of rank at most $d$, where

$m\leq\exp\Big{(}d^{O(1)}r^{O(1)}|\Gamma|^{O(1)}\log^{O(1)}\eta^{-1}\log^{O(1)}\rho^{-1}\Big{)},$

such that for each $i\in[m]$ there exist reals $\delta_{i}>0$ and
$\rho_{i}\in[\rho/2,\rho]$ such that the following two quasirandomness
properties hold.

  * (i)

For at least $1-\eta$ proportion of all elements $y\in C_{i}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i})|-\delta_{i}|B(\Gamma;\rho_{i})|\Big{|}\leq\eta|G|.$

  * (ii)

For at least $1-\eta$ proportion of all pairs $(y,y^{\prime})\in C_{i}\times
C_{i}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y),L_{1}(y^{\prime}),\dots,L_{r}(y^{\prime})\\};\rho_{i})|-\delta^{2}_{i}|B(\Gamma;\rho_{i})|\Big{|}\leq\eta|G|.$

Properties (i) and (ii) are sufficient to guarantee that the corresponding
bipartite graph is quasirandom, see Appendix B for a brief discussion of
quasirandom bipartite graphs.

###### Proof.

Let $C=[-N_{1},N_{1}]\cdot v_{1}+\dots+[-N_{d},N_{d}]\cdot v_{d}+H_{0}$ be a
canonical form of $C$. We iteratively find further proper coset progressions
$C=Q_{0}\supseteq Q_{1}\supseteq Q_{2}\supseteq\dots$ such that each $Q_{i}$
is of the form

$Q_{i}=[-N^{(i)}_{1},N^{(i)}_{1}]\cdot\ell^{(i)}_{1}v_{1}+\dots+[-N^{(i)}_{d},N^{(i)}_{d}]\cdot\ell^{(i)}_{d}v_{d}+H_{i}$

for suitable integers $N^{(i)}_{j},\ell^{(i)}_{j}$ and subgroups $H_{j}$. The
bounds

$\frac{2N_{1}+1}{2N^{(i)}_{1}+1},\dots,\frac{2N_{d}+1}{2N^{(i)}_{d}+1},\frac{|H_{0}|}{|H_{i}|}\leq\Big{(}\eta^{-2}100^{d+2}(2K+1)^{4r+2|\Gamma|}\Big{)}^{i}$

will hold at each step $i$, where $K$ is a parameter that will be defined
later, but shall satisfy $K=O((|\Gamma|+r)\eta^{-3}\rho^{-1})$ and it shall
not depend on $i$. Along the way, we shall also construct an increasing
sequence of lattices
$\\{0\\}=\Lambda_{0}\subseteq\Lambda_{1}\subseteq\Lambda_{2}\subseteq\dots$ in
$\mathbb{Z}^{r}$ such that for each $y\in Q_{i}$ and $\lambda\in\Lambda_{i}$
we have $\lambda_{1}L_{1}(y)+\dots+\lambda_{r}L_{r}(y)=0$.
Let $M\subset\mathbb{Z}^{\Gamma}$ be the annihilator lattice for the set
$\Gamma$, which is the lattice of those tuples
$(\nu_{\gamma})_{\gamma\in\Gamma}$ that satisfy
$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma=0$.

Suppose that we have completed the $s$th step and thus constructed the proper
coset progression $Q_{s}$ and the lattice $\Lambda_{s}$. Let

$Q^{\prime}_{s}=[-N^{(s)}_{1}/2,N^{(s)}_{1}/2]\cdot\ell^{(s)}_{1}v_{1}+\dots+[-N^{(s)}_{d}/2,N^{(s)}_{d}/2]\cdot\ell^{(s)}_{d}v_{d}+H_{s}$

which is a slightly shrunk version of $Q_{s}$, chosen so that
$Q^{\prime}_{s}-Q^{\prime}_{s}\subseteq Q_{s}$. Let us partition the initial
coset progression $C$ into proper coset progressions $S_{1},\dots,S_{m}$ by
intersecting it with translates of $Q^{\prime}_{s}$. It is possible to achieve
so that $|S_{i}|\geq 100^{-d}|Q_{s}|$ for all $i\in[m]$. For each $i\in[m]$,
we first find a suitable $\rho_{i}\in[\rho/2,\rho]$. Consider
$\rho-\frac{j\eta^{2}\rho}{1000}$ for $j\in[500\eta^{-2}]$ as candidates for
$\rho_{i}$. There is such a value of $\rho_{i}$ such that for at least
$1-\frac{\eta}{10}$ proportion of $y\in S_{i}$ we have

$\displaystyle\Big{|}B\Big{(}\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i}+\frac{\eta^{2}\rho}{1000}\Big{)}\setminus
B\Big{(}\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i}\Big{)}\Big{|}\leq\frac{\eta}{10}|G|,$
(10)

for at least $1-\frac{\eta}{10}$ proportion of the pairs $(y,y^{\prime})\in
S_{i}\times S_{i}$ we have

$\displaystyle\Big{|}B\Big{(}\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y),L_{1}(y^{\prime}),\dots,L_{r}(y^{\prime})\\};\rho_{i}+\frac{i\eta^{2}\rho}{1000}\Big{)}$
$\displaystyle\hskip 56.9055pt\setminus
B\Big{(}\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y),L_{1}(y^{\prime}),\dots,L_{r}(y^{\prime})\\};\rho_{i}\Big{)}\Big{|}\leq\frac{\eta}{10}|G|$
(11)

and

$\Big{|}B\Big{(}\Gamma;\rho_{i}+\frac{\eta^{2}\rho}{1000}\Big{)}\setminus
B(\Gamma;\rho_{i})\Big{|}\leq\frac{\eta}{10}|G|.$ (12)

Let us fix some $S_{i}$. The next claim shows that $S_{i}$ gives rise to a
quasirandom piece unless we obtain new vanishing linear combinations of
characters given by values of maps $L_{1},\dots,L_{r}$. Let
$K=O((|\Gamma|+r)\eta^{-3}\rho^{-1})$ be the quantity and $c_{i}\in\mathbb{D}$
for $i\in[-K,K]$ the constants provided by Proposition 4.3 such that whenever
$\gamma_{1},\dots,\gamma_{\ell}\in\hat{G}$ are characters for $\ell\leq
2r+|\Gamma|$ with the weak regularity property

$\Big{|}|B(\gamma_{1},\dots,\gamma_{\ell};\rho_{i}+\eta^{2}\rho/1000)|-|B(\gamma_{1},\dots,\gamma_{\ell};\rho_{i})|\Big{|}\leq\frac{\eta}{10}|G|$
(13)

then

$\Big{|}|B(\gamma_{1},\dots,\gamma_{\ell};\rho_{i})|-\sum_{a_{1},\dots,a_{\ell}\in[-K,K]}\mathbbm{1}(a_{1}\gamma_{1}+\dots+a_{\ell}\gamma_{\ell}=0)c_{a_{1}}\dots
c_{a_{\ell}}|G|\Big{|}\leq\frac{\eta}{5}|G|.$ (14)

######  Claim 6.2.

Suppose that at least $1-\frac{\eta}{10}$ proportion of all elements $y\in
S_{i}$ have the property that if the equality

$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+\lambda_{1}L_{1}(y)+\dots+\lambda_{r}L_{r}(y)=0$
(15)

holds for some $\nu_{\gamma},\lambda_{j}\in[-K,K]$ then $\nu\in M$ and
$\lambda\in\Lambda_{s}$. Suppose also that at least $1-\frac{\eta}{10}$
proportion of all pairs $(y,y^{\prime})\in S_{i}\times S_{i}$ have the
property that if the equality

$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+\lambda_{1}L_{1}(y)+\dots+\lambda_{r}L_{r}(y)+\lambda^{\prime}_{1}L_{1}(y^{\prime})+\dots+\lambda^{\prime}_{r}L_{r}(y^{\prime})=0$

holds for some $\nu_{\gamma},\lambda_{j},\lambda^{\prime}_{j}\in[-K,K]$ then
$\nu\in M$ and $\lambda,\lambda^{\prime}\in\Lambda_{s}$. Then the properties
(i) and (ii) hold.

###### Proof.

Define $\delta_{i}$ to be the quantity

$\sum_{\lambda\in\Lambda_{s}\cap[-K,K]^{r}}c_{\lambda_{1}}\dots
c_{\lambda_{r}}$

and define $\delta_{0}$ as

$\sum_{\nu\in M\cap[-K,K]^{\Gamma}}\prod_{\gamma\in\Gamma}c_{\nu_{\gamma}}.$

From inequalities (12) and (14) we conclude that

$\Big{|}|B(\Gamma;\rho_{i})|-\delta_{0}|G|\Big{|}\leq\frac{\eta}{5}|G|.$

Note that at least $1-\eta/5$ proportion of all $y\in S_{i}$ obey (10) and the
property involving (15) described in the claim. Then the Bohr set
$B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i})$ satisfies the condition
(13) so the inequality (14) gives

$\displaystyle\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i})|\,-\sum_{\begin{subarray}{c}a\in[-K,K]^{r}\\\
\nu\in[-K,K]^{\Gamma}\end{subarray}}$
$\displaystyle\mathbbm{1}\Big{(}\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+a_{1}L_{1}(y)+\dots+a_{r}L_{r}(y)=0\Big{)}$
$\displaystyle\hskip
113.81102pt\Big{(}\prod_{\gamma\in\Gamma}c_{\nu_{\gamma}}\Big{)}c_{a_{1}}\dots
c_{a_{r}}|G|\Big{|}\leq\frac{\eta}{5}|G|,$

while we have the equality

$\sum_{\begin{subarray}{c}a\in[-K,K]^{r}\\\
\nu\in[-K,K]^{\Gamma}\end{subarray}}\mathbbm{1}\Big{(}\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+a_{1}L_{1}(y)+\dots+a_{r}L_{r}(y)=0\Big{)}\Big{(}\prod_{\gamma\in\Gamma}c_{\nu_{\gamma}}\Big{)}c_{a_{1}}\dots
c_{a_{r}}=\delta_{0}\delta_{i}.$

Thus,

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho_{i})|-\delta_{i}|B(\Gamma;\rho_{i})|\Big{|}\leq
2\frac{\eta}{5}|G|,$

proving the first part of the claim. The second property follows similarly.∎

Suppose that $S_{i}$ is not quasirandom in the sense that the properties (i)
and (ii) do not hold simultaneously for the radius $\rho_{i}$. Then at least
one of the two assumptions in Claim 6.2 fail, but in either case, we conclude
that there are at least $\frac{\eta}{10}|S_{i}|^{2}$ pairs $(y,y^{\prime})\in
S_{i}\times S_{i}$ for which we have an equality

$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+\lambda_{1}L_{1}(y)+\dots+\lambda_{r}L_{r}(y)+\lambda^{\prime}_{1}L_{1}(y^{\prime})+\dots+\lambda^{\prime}_{r}L_{r}(y^{\prime})=0$

where at least one of $\nu\in
M,\lambda\in\Lambda_{s},\lambda^{\prime}\in\Lambda_{s}$ fails and all
coefficients belong to $[-K,K]$. By averaging, we obtain such a linear
combination that holds for at least
$\frac{\eta}{10(2K+1)^{2r+|\Gamma|}}|S_{i}|^{2}$ pairs $(y,y^{\prime})$ of
elements in $S_{i}$ which we now fix.

Suppose first that $\lambda,\lambda^{\prime}\in\Lambda_{s}$. Then
$\lambda_{1}L_{1}(y)+\dots+\lambda_{r}L_{r}(y)+\lambda^{\prime}_{1}L_{1}(y^{\prime})+\dots+\lambda^{\prime}_{r}L_{r}(y^{\prime})=0$
so $\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma=0$, which means that $\nu\in M$
which is a contradiction. Therefore, without loss of generality, we may assume
that $\lambda\notin\Lambda_{s}$. By Cauchy-Schwarz inequality we may find at
least $\frac{\eta^{2}}{100(2K+1)^{4r+2|\Gamma|}}|S_{i}|^{3}$ triples
$(y_{1},y_{2},y^{\prime})$ such that

$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+\lambda_{1}L_{1}(y_{1})+\dots+\lambda_{r}L_{r}(y_{1})+\lambda^{\prime}_{1}L_{1}(y^{\prime})+\dots+\lambda^{\prime}_{r}L_{r}(y^{\prime})=0$

and

$\sum_{\gamma\in\Gamma}\nu_{\gamma}\gamma+\lambda_{1}L_{1}(y_{2})+\dots+\lambda_{r}L_{r}(y_{2})+\lambda^{\prime}_{1}L_{1}(y^{\prime})+\dots+\lambda^{\prime}_{r}L_{r}(y^{\prime})=0.$

Subtracting these equalities from one another and fixing a suitable
$y^{\prime}$, using the facts that $y_{1},y_{2},y_{1}-y_{2}\in C$ and the maps
$L_{i}$ are Freiman-linear we obtain

$\lambda_{1}L_{1}(y_{1}-y_{2})+\dots+\lambda_{r}L_{r}(y_{1}-y_{2})=0$

for at least $\frac{\eta^{2}}{100(2K+1)^{4r+2|\Gamma|}}|S_{i}|^{2}$ pairs
$y_{1},y_{2}\in S_{i}$. By the way we defined $S_{i}$, we have
$S_{i}-S_{i}\subseteq Q_{s}$ so we see that
$\lambda_{1}L_{1}(z)+\dots+\lambda_{r}L_{r}(z)=0$ holds for at least

$\frac{\eta^{2}}{100(2K+1)^{4r+2|\Gamma|}}|S_{i}|\geq\frac{\eta^{2}}{100^{d+1}(2K+1)^{4r+2|\Gamma|}}|Q_{s}|$

of $z\in Q_{s}$. But the map
$z\mapsto\lambda_{1}L_{1}(z)+\dots+\lambda_{r}L_{r}(z)$ is a Freiman-linear
map on $Q_{s}$ so the subset consisting of $z$ such that
$\lambda_{1}L_{1}(z)+\dots+\lambda_{r}L_{r}(z)=0$ is a Freiman-subgroup $F$ of
$Q_{s}$. Apply Lemma 2.1 to find a further proper symmetric coset progression
$Q_{s+1}\subseteq F$ with

$\frac{2N^{(i)}_{1}+1}{2N^{(i+1)}_{1}+1},\dots,\frac{2N^{(i)}_{d}+1}{2N^{(i+1)}_{d}+1},\frac{|H_{i}|}{|H_{i+1}|}\leq\eta^{-2}100^{d+2}(2K+1)^{4r+2|\Gamma|}$

and let $\Lambda_{s+1}=\Lambda_{s}+\langle\lambda\rangle_{\mathbb{Z}}$.
Since the set $(\Lambda_{s+1}\setminus\Lambda_{s})\cap[-K,K]^{r}$ is non-empty
for every $s$ (as it contains the $r$-tuple $\lambda$ chosen above), Lemma 5.1
bounds the number of steps in the proof by $O(r^{2}(\log r+\log K))$.∎

## §7 Bilinear Bogolyubov argument

In this section we prove our main result which is stated slightly differently
compared to the introduction. This time we use coset progressions in one
variable and Bohr sets in the second.

######  Theorem 7.1.

Let $G$ and $H$ be finite abelian groups and let $A\subseteq G\times H$ be a
set of density $\delta$. Then there exist a proper symmetric coset progression
$C\subseteq H$ of rank at most $\log^{O(1)}\delta^{-1}$ and size
$|C|\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}|H|$, a set
$\Gamma\subseteq\hat{G}$ of size at most $\log^{O(1)}\delta^{-1}$, Freiman-
linear maps $L_{1},\dots,L_{r}\colon C\to\hat{G}$ for some positive integer
$r\leq\log^{O(1)}\delta^{-1}$ and a positive quantity
$\rho\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$ such that the bilinear
Bohr variety

$\Big{\\{}(x,y)\in B(\Gamma;\rho)\times C\colon x\in
B(L_{1}(y),\dots,L_{r}(y);\rho)\Big{\\}}$

is contained inside
$\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{hor}}A$.

Throughout the proof we use the following slice notation for subsets $A$ of
$G\times H$. For $x\in G$, we write

$A_{x\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}=\\{y\in
H\colon(x,y)\in A\\}$

which stands for the set of elements of $H$ lying in the column indexed by the
element $x$, and analogously we write for a given $y\in H$

$A_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}=\\{x\in
G\colon(x,y)\in A\\}$

for the set of elements of $G$ in the row indexed by $y$.

###### Proof.

The proof consists of 5 steps, where we take appropriate directional
difference sets in each one (sometimes we take a double difference set which
explains the discrepancy between the number of steps and the number of
operator applications in the theorem). As we complete the steps of the proof
we obtain an increasingly algebraically structured set in the iterated
directional difference set.

Step 1. By averaging, there is a set $Y^{1}\subseteq H$ of density $\delta/2$
such that
$A_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}$
has size
$|A_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}|\geq\frac{\delta}{2}|G|$
for each $y\in Y^{1}$. Perform a double horizontal convolution which results
in the set $A^{1}=\mathsf{D}_{\mathsf{hor}}\mathsf{D}_{\mathsf{hor}}A$.
Applying Corollary 4.9 for each $y\in Y^{1}$ we obtain a Bohr set
$B(\Gamma_{y},\rho)$ inside
$A^{1}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}$
of codimension at most $\log^{O(1)}\delta^{-1}$ and radius
$\rho\geq\Big{(}\log^{O(1)}\delta^{-1}\Big{)}^{-1}\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$.333We
may take $\rho$ to be independent of $y$ as Corollary 4.9 gives a lower bound
in terms of $\delta$ only and decreasing $\rho$ does not cause any harm. Thus,
the work in the first step of the proof results in inclusion

$\bigcup_{y\in Y^{1}}B(\Gamma_{y},\rho)\times\\{y\\}\subseteq A^{1}.$

Step 2. Let us now perform a single vertical convolution. We obtain
$A^{2}=\mathsf{D}_{\mathsf{ver}}A^{1}$ which satisfies

$A^{2}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}=\bigcup_{\begin{subarray}{c}z\in
Y^{1}\text{ s.t.}\\\ y+z\in
Y^{1}\end{subarray}}\,\Big{(}B(\Gamma_{y+z},\rho)\cap
B(\Gamma_{z},\rho)\Big{)}\times\\{y\\}$

for all $y\in H$.

Step 3. In the third step, we make a horizontal convolution, thus obtaining
$A^{3}=\mathsf{D}_{\mathsf{hor}}A^{2}$. We see that

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}=\bigcup_{\begin{subarray}{c}z,w\in
Y^{1}\text{ s.t.}\\\ y+z,y+w\in
Y^{1}\end{subarray}}\,\Big{(}B(\Gamma_{y+z},\rho)\cap
B(\Gamma_{z},\rho)\Big{)}-\Big{(}B(\Gamma_{y+w},\rho)\cap
B(\Gamma_{w},\rho)\Big{)}$

for all $y\in H$.

Bohr sets are symmetric, thus

$\Big{(}B(\Gamma_{y+z},\rho)\cap
B(\Gamma_{z},\rho)\Big{)}-\Big{(}B(\Gamma_{y+w},\rho)\cap
B(\Gamma_{w},\rho)\Big{)}=B(\Gamma_{y+z}\cup\Gamma_{z},\rho)+B(\Gamma_{y+w}\cup\Gamma_{w},\rho).$

If we were in a vector space rather than an arbitrary abelian group, the sum
of Bohr sets above would become a sum of ‘orthogonal complements’
$\langle\Gamma_{y+z}\cup\Gamma_{z}\rangle^{\perp}+\langle\Gamma_{y+w}\cup\Gamma_{w}\rangle^{\perp}$
which would be equal to
$(\langle\Gamma_{y+z}\cup\Gamma_{z}\rangle\cap\langle\Gamma_{y+w}\cup\Gamma_{w}\rangle)^{\perp}$.
We therefore use Theorem 4.7 which generalizes this fact to arbitrary abelian
groups and provides us with a positive integer
$R\leq\exp\Big{(}\log^{O(1)}\delta^{-1}\Big{)}$ such that444Again, $R$ can be
taken to be independent of $y,z,w$ as increasing $R$ is allowed and the bound
Theorem 4.7 is uniform.

$B(\langle\Gamma_{y+z}\cup\Gamma_{z}\rangle_{R}\cap\langle\Gamma_{y+w}\cup\Gamma_{w}\rangle_{R};1/4)\subseteq
B(\Gamma_{y+z}\cup\Gamma_{z};\rho)+B(\Gamma_{y+w}\cup\Gamma_{w},\rho).$

Define $U_{y}=\langle\Gamma_{y}\rangle_{R}$ for each $y\in Y^{1}$. In
conclusion, for each $y\in H$ we have

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}\supseteq\bigcup_{\begin{subarray}{c}z,w\in
Y^{1}\text{ s.t.}\\\ y+z,y+w\in
Y^{1}\end{subarray}}B\Big{(}(U_{y+z}+U_{z})\cap(U_{y+w}+U_{w});1/4\Big{)}.$

Apply Corollary 3.7 (with choices $G=H$, $H=\hat{G}$, $A=Y^{1}$, where the
objects on the left sides of these three equalities are the ones in the
statement of the corollary555There is a technical condition that $|G|\geq
2000K^{4}\alpha^{-4}$. If the condition fails, that means that
$|H|\leq\exp\Big{(}O(\delta^{-O(1)})\Big{)}$ in which case Theorem 7.1 reduces
to the one-dimensional variant, i.e. Theorem 3.1.) we obtain a positive
integer $m\leq\exp(\log^{O(1)}\delta^{-1})$, proper coset progressions
$C_{1},\dots,C_{m}$ of rank at most $\log^{O(1)}\delta^{-1}$ and Freiman
homomorphisms $L_{1}\colon C_{1}\to\hat{G},\dots,L_{m}\colon C_{m}\to\hat{G}$
such that, writing $U^{\prime}_{a}=\\{L_{i}(a)\colon i\in[m],a\in C_{i}\\}\cap
U_{a}$ for each $a\in Y^{1}$, we have $y+z,z,y+w,w\in Y^{1}$ and

$(U_{y+z}-U_{z})\cap(U_{y+w}-U_{w})\subseteq(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w})$

for at least $\Omega(\delta^{4}|H|^{3})$ of $y,z,w\in H$. Thus, we get a
collection $T$ of triples $(y,z,w)\in H^{3}$ of size at least
$\Omega(\delta^{4}|H|^{3})$ such that $y+z,z,y+w,w\in Y^{1}$ and

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}\supseteq
B\Big{(}(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w});1/4\Big{)}.$

By Theorem 5.2 for each $y\in Y^{1}$, we may find elements
$\gamma_{1},\dots,\gamma_{\ell}\in U^{\prime}_{y}$ such that
$U^{\prime}_{y}\subseteq\langle\gamma_{1},\dots,\gamma_{\ell}\rangle_{S}$, for
some $\ell\leq\log^{O(1)}\delta^{-1}$ and
$S\leq\exp\Big{(}\log^{O(1)}\delta^{-1}\Big{)}$. In particular, there is a set
of indices $I_{y}=\\{i_{1},\dots,i_{\ell}\\}\subseteq[m]$ such that
$\gamma_{j}=L_{i_{j}}(y)$ and $y\in C_{i_{j}}$. Let $\ell_{0}$ and $S_{0}$ be
the maximal values attained by $\ell$ and $S$ as $y$ ranges over $Y^{1}$ which
still satisfy $\ell_{0}\leq\log^{O(1)}\delta^{-1}$ and
$S_{0}\leq\exp\Big{(}\log^{O(1)}\delta^{-1}\Big{)}$.
We have now reached the point in the argument where we need an idea of
Hosseini and Lovett [11] in order to prevent the loss of efficiency in the
argument. Observe that bounds we are after have two forms: one is
$\log^{O(1)}\delta^{-1}$, which we want for quantities such as the rank of
coset progressions and number of Freiman homomorphisms, and the other is
$\exp\Big{(}\log^{O(1)}\delta^{-1}\Big{)}$ which is typically the inverse of
the density of relevant sets in $G\times H$. Corollary 3.7 has the problem
that it provides us with the exponential number of Freiman homomorphisms.
Hosseini and Lovett use the fact that only $\log^{O(1)}\delta^{-1}$ of these
maps are needed to cover any of the sets $U_{y}$, and instead average over
these small subsets of Freiman homomorphisms. This turns the exponential bound
into the inverse of the density of the relevant set rather than being a bound
on the number of maps, as desired.
Let us now return to the argument. By averaging, we may find four sets
$J_{1},J_{2},J_{3},J_{4}\subseteq[m]$ such that for at least
$\Omega\Big{(}\frac{1}{\binom{m}{\ell_{0}}^{4}}\delta^{4}|H|^{3}\Big{)}$ of
triples $(y,z,w)\in T$ we have
$I_{y+z}=J_{1},I_{z}=J_{2},I_{y+w}=J_{3},I_{w}=J_{4}$. Furthermore, by
averaging we may find $z,w\in Y^{1}$ and a set $Y^{2}$ of size at least
$\Omega\Big{(}\frac{1}{\binom{m}{\ell_{0}}^{4}}\delta^{4}|H|\Big{)}$ whose
elements $y$ satisfy $(y,z,w)\in T$ and
$I_{y+z}=J_{1},I_{z}=J_{2},I_{y+w}=J_{3},I_{w}=J_{4}$. We claim that we may
find the following structure inside $A^{3}$.

######  Claim 7.2.

For each $y\in Y^{2}$ we have

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}\supseteq
B\Big{(}\\{L_{i}(y+z)\colon i\in J_{1}\\}\cup\\{L_{i}(z)\colon i\in
J_{2}\\}\cup\\{L_{i}(y+w)\colon i\in J_{3}\\}\cup\\{L_{i}(w)\colon i\in
J_{4}\\};1/(16\ell_{0}S_{0})\Big{)}$

and all points in the arguments of maps $L_{i}$ defining the displayed Bohr
set lie in the relevant coset progressions $C_{i}$.

###### Proof.

Let $y\in Y^{2}$ and suppose that $x$ is an element of the Bohr set

$B\Big{(}\\{L_{i}(y+z)\colon i\in J_{1}\\}\cup\\{L_{i}(z)\colon i\in
J_{2}\\}\cup\\{L_{i}(y+w)\colon i\in J_{3}\\}\cup\\{L_{i}(w)\colon i\in
J_{4}\\};1/(16\ell_{0}S_{0})\Big{)}.$

By assumptions, we have $I_{y+z}=J_{1}$ which implies
$U^{\prime}_{y+z}\subseteq\langle L_{i}(y+z)\colon i\in J_{1}\rangle_{S_{0}}$
and $y+z\in C_{i}$ for $i\in J_{1}$. Thus, for each $\chi\in
U^{\prime}_{y+z}$, we have $\chi=\sum_{i\in J_{1}}\lambda_{i}L_{i}(y+z)$ for
integers $\lambda_{i}$ such that $|\lambda_{i}|\leq S_{0}$ for $i\in J_{1}$ so

$|\chi(x)|_{\mathbb{T}}\leq\sum_{i\in
J_{1}}|\lambda_{i}|\Big{|}L_{i}(y+z)(x)\Big{|}_{\mathbb{T}}\leq
S_{0}|J_{1}|\frac{1}{16\ell_{0}S_{0}}\leq\frac{1}{16}.$

Thus, if
$\theta\in(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w})$
then we have $|\theta(x)|_{\mathbb{T}}\leq 1/4$, so

$x\in
B\Big{(}(U^{\prime}_{y+z}-U^{\prime}_{z})+(U^{\prime}_{y+w}-U^{\prime}_{w});1/4\Big{)}\subseteq
A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}.\qed$

Let $\Gamma=\\{L_{i}(z)\colon i\in J_{2}\\}\cup\\{L_{i}(w)\colon i\in
J_{4}\\}\subseteq\hat{G}$. For each $y\in Y^{2}$ we have that $y\in C_{i}-z$
for $i\in J_{1}$ and $y\in C_{i}-w$ for $i\in J_{3}$. Thus,
$Y^{2}\subseteq\Big{(}\cap_{i\in J_{1}}C_{i}-z\Big{)}\cap\Big{(}\cap_{i\in
J_{3}}C_{i}-w\Big{)}$. Applying Proposition 3.5 we obtain a proper coset
progression $C\subseteq\Big{(}\cap_{i\in
J_{1}}C_{i}-z\Big{)}\cap\Big{(}\cap_{i\in J_{3}}C_{i}-w\Big{)}$ of rank
$d\leq\log^{O(1)}\delta^{-1}$ such that $|C\cap
Y^{2}|\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}|H|$. Furthermore, we may
define Freiman homomorphisms $L^{\prime}_{i}\colon C\to\hat{G}$ for $i\in
J_{1}$ by $L^{\prime}_{i}(y)=L_{i}(y+z)$ and $L^{\prime\prime}_{i}\colon
C\to\hat{G}$ for $i\in J_{3}$ by $L^{\prime\prime}_{i}(y)=L_{i}(y+w)$. Write
$Y^{3}=Y^{2}\cap C$.
Misusing the notation by writing $L_{1},\dots,L_{r}$ instead of
$L^{\prime}_{i}$ for $i\in J_{1}$ and $L^{\prime\prime}_{i}$ for $i\in J_{3}$,
we get Freiman homomorphisms $L_{i}\colon C\to\hat{G}$ for $i\in[r]$, where
$r\leq\log^{O(1)}\delta^{-1}$, a subset $\Gamma\subseteq\hat{G}$ of size
$|\Gamma|\leq\log^{O(1)}\delta^{-1}$, a subset $Y^{3}\subseteq C$ of size
$|Y^{3}|\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}|H|$ and a positive
quantity $\rho\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$ such that for
each $y\in Y^{3}$ we have

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}\supseteq
B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho)$

using Claim 7.2.

Linearization. For technical reasons, we need to assume that the coset
progression $C$ is symmetric and that maps $L_{i}$ are defined on $2C-2C$
instead of just on $C$ and that are Freiman-linear rather than merely Freiman
homomorphisms. We now make a slight digression from the main argument in order
to achieve this.

Let $C=a+[0,N_{1}]\cdot v_{1}+\dots+[0,N_{d}]\cdot v_{d}+H_{0}$ be a canonical
form of $C$ and let $\delta_{3}=|Y^{3}|/|H|$. Let
$D_{j}=\Big{\lfloor}\frac{\delta_{3}N_{j}}{100d}\Big{\rfloor}$ for $j\in[d]$,
when $N_{j}\geq 200d{\delta_{3}}^{-1}$ (so that $D_{j}\geq 2$), and $D_{j}=0$
otherwise. Using the canonical form, sub-coset progression

$a+[4D_{1},N_{1}-4D_{1}]\cdot v_{1}+\dots+[4D_{d},N_{d}-4D_{d}]\cdot
v_{d}+H_{0}$

of $C$ can be partitioned into further proper coset progressions666The old
coset progressions denoted by $C_{i}$ no longer play a role in the proof, and
we need the new coset progressions $C_{1},\dots,C_{M}$ only temporarily, so we
opted for this misuse of notation. $C_{1},\dots,C_{M}$ for
$M\leq(200{\delta_{3}}^{-1}d+1)^{d}$ such that every $C_{i}$ has canonical
form

$C_{i}=a+[s_{1},t_{1}]\cdot v_{1}+\dots+[s_{d},t_{d}]\cdot v_{d}+H_{0}$

for suitable integers $s_{1},t_{1},\dots,s_{d},t_{d}$ that satisfy

$4D_{j}\leq s_{j}\leq t_{j}\leq N_{j}-4D_{j},\,\,D_{j}/2\leq t_{j}-s_{j}\leq
D_{j}\,\,\text{ and }\,\,t_{j}-s_{j}\,\,\text{ is even (possibly zero if
$D_{j}=0$).}$ (16)

We then have $|C\setminus(\cup_{j\in[M]}C_{j})|\leq\delta_{3}/2|C|$ so by
averaging, there is $j\in[M]$ such that $|C_{j}\cap
Y^{3}|\geq\delta_{3}/(2M)|H|$. Since $t_{\ell}-s_{\ell}$ is even for all
$\ell$, we may find an element $t\in C_{j}$ such that $\tilde{C}=C_{j}-t$ is a
symmetric proper coset progression. Due to requirements (16) we also know that
$4\tilde{C}+t\subseteq C$. Define maps
$\tilde{L}_{1},\dots,\tilde{L}_{r}\colon C-t\to\hat{G}$ by
$\tilde{L}_{i}(x)=L_{i}(x+t)-L_{i}(t)$, which are Freiman-linear. Finally, set

$\tilde{A}=\Big{(}G\times((Y^{3}-t)\cap\tilde{C})\Big{)}\cap\Big{(}\bigcup_{y\in\tilde{C}}B(\Gamma\cup\\{L_{1}(t),\dots,L_{r}(t)\\}\cup\\{\tilde{L}_{1}(y),\dots,\tilde{L}_{r}(y)\\};\rho/2)\Big{)}.$

We prove the following claim.

######  Claim 7.3.

We have $\tilde{A}+(0,t)\subset A^{3}$.

###### Proof.

Suppose that $(x,y)\in\tilde{A}$. Then $y+t\in Y^{3}$ and $x\in
B(\Gamma;\rho)$. Furthermore, for $\ell\in[r]$, we have

$|L_{i}(y+t)(x)|_{\mathbb{T}}\leq|L_{i}(t)(x)|_{\mathbb{T}}+|L_{i}(y+t)(x)-L_{i}(t)(x)|_{\mathbb{T}}=|L_{i}(t)(x)|_{\mathbb{T}}+|\tilde{L}_{i}(y)(x)|_{\mathbb{T}}\leq\rho,$

showing that $x\in
B(\Gamma\cup\\{L_{1}(y+t),\dots,L_{r}(y+t)\\};\rho)\subseteq
A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y+t}$.∎

In particular,
$\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}\tilde{A}\subseteq\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}A^{3}$,
so we may focus our attention on $\tilde{A}$ instead of $A^{3}$. We misuse the
notation again, writing $A^{3}$ instead of $\tilde{A}$, $C$ instead of
$\tilde{C}$, $Y^{3}$ instead of $(Y^{3}-t)\cap\tilde{C}$, $L_{i}$ instead of
$\tilde{L}_{i}$, $\Gamma$ instead of
$\Gamma\cup\\{L_{1}(t),\dots,L_{r}(t)\\}$, etc. Thus, we may assume that
$Y^{3}\subseteq C$ for a symmetric proper coset progression $C$ of rank
$d\leq\log^{O(1)}\delta^{-1}$ with Freiman-linear maps
$L_{1},\dots,L_{r}\colon 4C\to\hat{H}$ for $r\leq\log^{O(1)}\delta^{-1}$ and
that

$A^{3}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}\supseteq
B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho)$ (17)

for all $y\in Y^{3}$. We also have bounds
$|Y^{3}|\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}|H|$,
$|\Gamma|\leq\log^{O(1)}\delta^{-1}$ and
$\rho\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$.

Step 4. Let $\alpha$ be the density of $Y^{3}$ inside $C$ and recall that $d$
is the rank of $C$. We have
$\alpha\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$. Let $\eta>0$ be a
parameter to be chosen later. Apply Theorem 6.1 to the bilinear Bohr variety
(note the somewhat smaller radius)

$W=G\times C\cap\Big{(}\bigcup_{y\in
C}B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho/4)\times\\{y\\}\Big{)}$

to obtain a partition of $C=C_{1}\cup\dots\cup C_{m}$ into further proper
coset progressions of rank at most $d$ such that the intersection with each
$G\times C_{i}$ is quasirandom with parameter $\eta$ in the sense of Theorem
6.1, where $m\leq\exp\Big{(}\log^{O(1)}(\delta^{-1}\eta^{-1})\Big{)}$. By
averaging, we may find a piece $C^{\prime}=C_{i}$ such that
$|C^{\prime}|\geq\frac{\alpha}{2m}|C|$ and $|C^{\prime}\cap
Y^{3}|\geq\frac{\alpha}{2}|C^{\prime}|$. By Corollary 3.3 applied to the set
$Y^{\prime}=Y^{3}\cap C^{\prime}$ inside the progression $C^{\prime}$, there
is a proper symmetric coset progression $D\subseteq H$ of rank at most
$\log^{O(1)}(\alpha^{-1}2^{d+1})\leq\log^{O(1)}\delta^{-1}$ and size
$|D|=\beta|C^{\prime}|$ for some
$\beta\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$ such that for each $y\in
D$ there are at least $\frac{\alpha}{2^{d+6}}|Y^{\prime}|^{3}$ quadruples
$(y_{1},y_{2},y_{3},y_{4})$ of elements in $Y^{\prime}$ such that
$y_{1}+y_{2}-y_{3}-y_{4}=y$. For $y\in H$, write $Q_{y}$ for the set of
triples $(y_{1},y_{2},y_{3})$ of elements in $Y^{\prime}$ such that
$y_{1}+y_{2}-y_{3}-y\in Y^{\prime}$. Thus, whenever $y\in D$ we have
$|Q_{y}|\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}|C^{\prime}|^{3}$.
By the conclusion of Theorem 6.1 we have that the bilinear Bohr variety
$(G\times C^{\prime})\cap W^{\prime}$ where

$W^{\prime}=\Big{(}\bigcup_{y\in
C}B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho^{\prime})\times\\{y\\}\Big{)}$

is quasirandom in the sense of Theorem 6.1 with parameter $\eta$ and density
$\delta^{\prime}$, for some $\delta^{\prime}\in[0,1]$ and radius
$\rho^{\prime}\in[\rho/8,\rho/4]$.
Write $A^{4}=\mathsf{D}_{\mathsf{ver}}\mathsf{D}_{\mathsf{ver}}A^{3}$.

######  Claim 7.4.

Suppose that $(x,y)\in W^{\prime}$. Assume also that
$Q_{y}\cap\Big{(}W^{\prime}_{x\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\Big{)}^{3}\not=\emptyset$.
Then $(x,y)\in A^{4}$.

###### Proof of the claim.

Let $(y_{1},y_{2},y_{3})\in
Q_{y}\cap\Big{(}W_{x\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}\Big{)}^{3}$.
Write $y_{4}=y_{1}+y_{2}-y_{3}-y$ which we know to belong to $Y^{\prime}$.
Note that $y=y_{1}+y_{2}-y_{3}-y_{4}\in 4C$. We also know that $x\in
B(\Gamma;\rho)$. Let $i\in[r]$. Then

$\displaystyle|L_{i}(y_{4})(x)|_{\mathbb{T}}=$
$\displaystyle|L_{i}(y_{1}+y_{2}-y_{3}-y)(x)|_{\mathbb{T}}$ $\displaystyle=$
$\displaystyle|L_{i}(y_{1}+y_{2}-y_{3})(x)-L_{i}(y)(x)|_{\mathbb{T}}$
$\displaystyle=$
$\displaystyle|L_{i}(y_{1}+y_{2})(x)-L_{i}(y_{3})(x)-L_{i}(y)(x)|_{\mathbb{T}}$
$\displaystyle=$
$\displaystyle|L_{i}(y_{1})(x)+L_{i}(y_{2})(x)-L_{i}(y_{3})(x)-L_{i}(y)(x)|_{\mathbb{T}}$
$\displaystyle\leq$
$\displaystyle|L_{i}(y_{1})(x)|_{\mathbb{T}}+|L_{i}(y_{2})(x)|_{\mathbb{T}}+|L_{i}(y_{3})(x)|_{\mathbb{T}}+|L_{i}(y)(x)|_{\mathbb{T}}\leq\rho,$

where we used the fact that the Freiman-linear map $L_{i}$ is defined on $4C$
so that all the points appearing as arguments of $L_{i}$ above belong to its
domain. Thus $|L_{i}(y_{4})(x)|_{\mathbb{T}}\leq\rho$, so $(x,y_{4})\in A^{3}$
by (17). Since we already know that $(x,y_{1}),(x,y_{2}),(x,y_{3})\in A^{3}$,
we are done.∎

Recall that $\rho^{\prime}\geq\rho/8$ and thus
$|B(\Gamma;\rho^{\prime})|\geq(\rho/8)^{|\Gamma|}|G|$ by Lemma 4.1. Let us
also recall what the conclusion of Theorem 6.1 implies about the structure of
the bilinear Bohr variety $(G\times C^{\prime})\cap W^{\prime}$, namely the
following.

  * (i)

For at least $1-\eta$ proportion of all elements $y\in C^{\prime}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho^{\prime})|-\delta^{\prime}|B(\Gamma;\rho^{\prime})|\Big{|}\leq\eta(8\rho^{-1})^{|\Gamma|}|B(\Gamma;\rho^{\prime})|.$

  * (ii)

For at least $1-\eta$ proportion of all pairs $(y,y^{\prime})\in
C^{\prime}\times C^{\prime}$ we have

$\Big{|}|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y),L_{1}(y^{\prime}),\dots,L_{r}(y^{\prime})\\};\rho^{\prime})|-{\delta^{\prime}}^{2}|B(\Gamma;\rho^{\prime})|\Big{|}\leq\eta(8\rho^{-1})^{|\Gamma|}|B(\Gamma;\rho^{\prime})|.$

Now we use quasirandomness theory described in Appendix B. First of all, using
Lemma B.4 we deduce that the bipartite graph on vertex classes
$B(\Gamma;\rho^{\prime})$ and $C^{\prime}$ whose edges are given by pairs in
$W^{\prime}$ is $\eta^{\prime}$-quasirandom for
$\eta^{\prime}=3\sqrt[8]{\eta(8\rho^{-1})^{|\Gamma|}+\eta}$ with density
$\delta_{\text{qr}}$ that obeys
$|\delta_{\text{qr}}-\delta^{\prime}|\leq\eta(8\rho^{-1})^{|\Gamma|}+\eta$.
Provided $\eta\leq\frac{1}{100}(\rho/8)^{2|\Gamma|+r}$, using Lemma 4.1 for
the Bohr set $|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho^{\prime})|$ this
time, we see that $\delta_{\text{qr}}\geq\frac{1}{4}(\rho/8)^{|\Gamma|+r}$.

There is a positive quantity
$\xi\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$ such that
$|Q_{y}|\geq\xi|C^{\prime}|^{3}$ holds for all $y\in D$. Take any $y\in D$.
Apply Lemma B.3 to $Q_{y}$ to conclude that

$\Big{|}|(W^{\prime}_{x\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}})^{3}\cap
Q_{y}|-\delta_{\text{qr}}^{3}|Q_{y}|\Big{|}\leq\frac{1}{2}\delta_{\text{qr}}^{3}\xi|C^{\prime}|^{3}\leq\frac{1}{2}\delta_{\text{qr}}^{3}|Q_{y}|$

holds for all but at most $50\delta_{\text{qr}}^{-6}\xi^{-2}\eta^{\prime}$
proportion of elements $x\in B(\Gamma;\rho^{\prime})$. Lemma 4.1 tells us that
$|W^{\prime}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}|\geq(\rho/8)^{|\Gamma|+r}|G|\geq(\rho/8)^{|\Gamma|+r}|B(\Gamma;\rho^{\prime})|$.
Therefore,
$(W^{\prime}_{x\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}})^{3}\cap
Q_{y}\not=\emptyset$ for all but at most
$\eta^{\prime\prime}|W^{\prime}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}|$
elements $x\in
W^{\prime}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}$,
where

$\eta^{\prime\prime}=50\delta_{\text{qr}}^{-6}\xi^{-2}(8/\rho)^{|\Gamma|+r}\eta^{\prime}.$

Combining this fact with Claim 7.4, we conclude that for each $y\in D$ the row
$A^{4}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}$
has size

$|A^{4}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}|\,\geq(1-\eta^{\prime\prime})|B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho^{\prime})|.$

Step 5. Let $A^{5}=\mathsf{D}_{\mathsf{hor}}A^{4}$. To finish the proof, we
apply Lemma 4.2 for each $y\in D$. In order to make the set
$A^{4}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}y}$
sufficiently dense in the Bohr set above, we may pick
$\eta\geq\exp\Big{(}-\log^{O(1)}\delta^{-1}\Big{)}$ (where the new implicit
constants hidden in the $O(1)$ notation are sufficiently large in terms of the
previous ones) to guarantee $\eta^{\prime\prime}\leq 4^{-|\Gamma|-r-1}$. We
conclude that

$\bigcup_{y\in
D}\Big{(}B(\Gamma\cup\\{L_{1}(y),\dots,L_{r}(y)\\};\rho^{\prime}/2)\times\\{y\\}\Big{)}\subseteq
A^{5},$

completing the proof of the theorem.∎

##  Appendix A Robust Bogolyubov-Ruzsa lemma

In this appendix we provide a quick proof of the robust version of the
Bogolyubov-Ruzsa lemma, which was stated as Theorem 3.2. We recall its
statement here.

######  Theorem A.1 (Theorem 3.2).

Let $G$ be a finite abelian group. Let $A\subset G$ be a set such that
$|A+A|\leq K|A|$. Then there exists a symmetric proper coset progression $C$
of rank at most $O(\log^{O(1)}(2K))$ and size
$|C|\geq\exp(-O(\log^{O(1)}(2K)))|A|$ such that for each $x\in C$ there are at
least $\frac{1}{64K}|A|^{3}$ quadruples $(a_{1},a_{2},a_{3},a_{4})\in A^{4}$
such that $x=a_{1}+a_{2}-a_{3}-a_{4}$.

We deduce this theorem from the following result of Schoen and Sisask (see
Theorem 5.1 in [15] which is applied with the choice $M=S=A$ in their notation
to yield the formulation below).

######  Theorem A.2.

Let $G$ be a finite abelian group and let $\varepsilon>0$. Suppose that
$A,L\subseteq G$ are two sets and that $|A+A|\leq K|A|$. Assume also that
$\eta=|A|/|L|\leq 1$. Then there exists a set $T\subseteq A$ of size

$|T|\geq\exp(-O(\varepsilon^{-2}\log(2K)\log(2\eta^{-1})))|A|$

such that

$\Big{|}\mathbbm{1}_{A}\ast\mathbbm{1}_{A}\ast\mathbbm{1}_{L}(x+t)-\mathbbm{1}_{A}\ast\mathbbm{1}_{A}\ast\mathbbm{1}_{L}(x)\Big{|}\leq\varepsilon|G|^{-2}|A|^{2}$

holds for all $x\in G$ and $t\in 2T-2T$.

###### Proof of Theorem A.1.

Let $S$ be the set of all elements $s\in A+A$ such that $s=a+b$ for at least
$\frac{1}{2K}|A|$ pairs $(a,b)\in A^{2}$. Since $|A+A|\leq K|A|$, the number
of pairs $(a,b)\in A^{2}$ such that $a+b\notin S$ is at most
$\frac{1}{2}|A|^{2}$. Thus, $|\\{(a,b)\in A^{2}\colon a+b\in
S\\}|\geq\frac{1}{2}|A|^{2}$, so by averaging, there is an element $a\in A$
such that $|a+A\cap S|\geq\frac{1}{2}|A|$, implying in particular that
$|S|\geq|A|/2$.
Let $A^{\prime}\subseteq A$ be a subset of size $\lfloor|A|/2\rfloor$ chosen
randomly and uniformly among all subsets of that size. Then

$\displaystyle\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits\mathbbm{1}_{A^{\prime}}*\mathbbm{1}_{A^{\prime}}*\mathbbm{1}_{-S}(0)=$
$\displaystyle|G|^{-2}\mathop{\mathchoice{\vbox{\hbox{$\mathbb{E}$}}}{\kern
0.0pt\mathbb{E}}{\kern 0.0pt\mathbb{E}}{\kern
0.0pt\mathbb{E}}}\displaylimits|\\{(a,b)\in A^{\prime}\times A^{\prime}\colon
a+b\in S\\}|$ $\displaystyle=$
$\displaystyle|G|^{-2}\sum_{\begin{subarray}{c}(a,b)\in A\times A\\\ a+b\in