# Subsets of Cayley graphs that induce many edges

W.T. Gowers  Department of Pure Mathematics and Mathematical Statistics,
Wilberforce Road, Cambridge CB3 0WB, UK<EMAIL_ADDRESS>and  O.
Janzer<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a regular graph of degree $d$ and let $A\subset V(G)$. Say that $A$
is _$\eta$ -closed_ if the average degree of the subgraph induced by $A$ is at
least $\eta d$. This says that if we choose a random vertex $x\in A$ and a
random neighbour $y$ of $x$, then the probability that $y\in A$ is at least
$\eta$. The work of this paper was motivated by an attempt to obtain a
qualitative description of closed subsets of the Cayley graph $\Gamma$ whose
vertex set is
$\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$ with two
vertices joined by an edge if their difference is of the form
$u_{1}\otimes\cdots\otimes u_{d}$. For the matrix case (that is, when $d=2$),
such a description was obtained by Khot, Minzer and Safra, a breakthrough that
completed the proof of the 2-to-2 conjecture. In this paper, we formulate a
conjecture for higher dimensions, and prove it in an important special case.
Also, we identify a statement about $\eta$-closed sets in Cayley graphs on
arbitrary finite Abelian groups that implies the conjecture and can be
considered as a “highly asymmetric Balog-Szemerédi-Gowers theorem” when it
holds. We conclude the paper by showing that this statement is not true for an
arbitrary Cayley graph. It remains to decide whether the statement can be
proved for the Cayley graph $\Gamma$.

The first author is supported by a Royal Society 2010 Anniversary Research
Professorship. He also held a Research Chair of the Fondation Sciences
Mathématiques de Paris while this research was carried out.

##  1\. Introduction

The Unique Games Conjecture, formulated by Khot [5] in 2002, is a central
conjecture in theoretical computer science. If true, it implies that for a
wide class of natural problems it is NP-hard to find even a very crude
approximate solution in polynomial time. Recently, a weakening of the
conjecture known as the 2-to-2 Games Conjecture, where the approximation is
required to be less crude (so it is easier to prove hardness) was proved by
Khot, Minzer and Safra [6], a result that is considered as a major step
towards the Unique Games Conjecture itself. More precisely, after work by
various authors, the problem had been reduced to a statement about a certain
Cayley graph, and Khot, Minzer and Safra proved that statement.

The Cayley graph $\Gamma$ in question has as its vertex set the set of all
$m\times n$ matrices over $\mathbb{F}_{2}$, with two vertices joined by an
edge if their difference has rank 1. Let us say that a subset
$\mathcal{A}\subset\mathrm{M}_{m,n}(\mathbb{F}_{2})$ is _$\eta$ -closed_ if
the probability that $A+B\in\mathcal{A}$, when $A$ is chosen uniformly from
$\mathcal{A}$ and $B$ is chosen uniformly from all rank-1 matrices, is at
least $\eta$. In graph terms, this is the probability that a random neighbour
of a random point in $\mathcal{A}$ is itself in $\mathcal{A}$.

A simple example of an $\eta$-closed set is the set
$\\{A\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):Ax=y\\}$, for some pair of vectors
$x\in\mathbb{F}_{2}^{n},y\in\mathbb{F}_{2}^{m}$. Indeed, if $Ax=y$ and $B$ is
a random matrix of rank 1, then $x\in\ker B$ with probability roughly 1/2. But
if $x\in\ker B$, then $(A+B)x=y$, so $A+B\in\mathcal{A}$ as well. A very
similar, but distinct, example is the set
$\\{A\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):A^{T}x=y\\}$. Let us call sets of one
of these two kinds _basic sets_.

We can form further examples by taking intersections of a small number of
basic sets. For example, if $x_{1},\dots,x_{k}$ are linearly independent and
we take a set of the form

$\\{A\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):Ax_{1}=y_{1},\dots,Ax_{k}=y_{k}\\},$

then with probability approximately $2^{-k}$ each $x_{i}$ belongs to $\ker B$,
so for any $A$ in the set, $A+B$ belongs to the set with probability
approximately $2^{-k}$. The result of Khot, Minzer and Safra is the following.

######  Theorem 1.1.

For every $\eta>0$ there exist $\delta>0$ and a positive integer $k$ such that
if $\mathcal{A}$ is any $\eta$-closed subset of
$\mathrm{M}_{m,n}(\mathbb{F}_{2})$, then there exists an intersection
$\mathcal{C}$ of at most $k$ basic sets such that
$|\mathcal{A}\cap\mathcal{C}|\geq\delta|\mathcal{C}|$ and
$\mathcal{C}\neq\emptyset$.

In other words, every closed set is dense inside some intersection of a small
number of basic sets.

It is well known and not hard to see that this in fact leads to a
characterization (at least qualitatively) of closed sets. Indeed, observe
first that if $\mathcal{A}$ is $\eta$-closed, then the subgraph induced by
$\mathcal{A}$ has average degree at least $\eta|\mathcal{B}|$, where
$\mathcal{B}$ is the set of rank-1 matrices, and maximal degree at most
$|\mathcal{B}|$. Therefore, any subset of $\mathcal{A}$ of size at least
$(1-\eta/4)|\mathcal{A}|$ has average degree at least $\eta|\mathcal{B}|/2$.
It follows from this observation and Theorem 1.1 that we can find disjoint
subsets $\mathcal{A}_{1},\dots,\mathcal{A}_{r}$ of $\mathcal{A}$, subsets
$\mathcal{C}_{1},\dots,\mathcal{C}_{r}$ of $\mathrm{M}_{m,n}(\mathbb{F}_{2})$,
a positive real number $\delta=\delta(\eta)$ and a positive integer
$k=k(\eta)$ with the following properties.

  1. (1)

The sets $\mathcal{A}_{i}$ are disjoint.

  2. (2)

Each $\mathcal{C}_{i}$ is an intersection of at most $k$ basic sets.

  3. (3)

For each $i$,
$|\mathcal{A}_{i}\cap\mathcal{C}_{i}|\geq\delta|\mathcal{C}_{i}|$.

  4. (4)

$|\bigcup_{i}\mathcal{A}_{i}|\geq\eta|\mathcal{A}|/4$.

Conversely, if such sets exist, then the probability that a random matrix
$A\in\mathcal{A}$ belongs to some $\mathcal{A}_{i}$ is at least $\eta/4$. If
it belongs to $\mathcal{A}_{i}$, then we can use the following lemma. We write
$u\otimes v$ for the rank-1 matrix $M$ with $M_{ij}=u_{i}v_{j}$, which sends a
vector $x$ to the vector $\langle x,v\rangle u$. Note also that $(u\otimes
v)^{T}$ sends $x$ to $\langle x,u\rangle v$.

######  Lemma 1.2.

Let $\mathcal{C}$ be an intersection of at most $k$ basic sets and let
$\mathcal{A}\subset\mathcal{C}$ be a subset of relative density at least
$\delta$. Then $\mathcal{A}$ is $2^{-k}(\delta-2^{-(m-k)})$-closed.

###### Proof.

Let us set $\mathcal{C}(x,y)=\\{A\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):Ax=y\\}$,
and
$\mathcal{C}^{\prime}(x,y)=\\{A\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):A^{T}x=y\\}$.
Let $x_{1},\dots,x_{k},y_{1},\dots,y_{k}$ be non-zero vectors such that
$\mathcal{C}=\bigcap_{i=1}^{r}\mathcal{C}(x_{i},y_{i})\cap\bigcap_{i=r+1}^{k}\mathcal{C}^{\prime}(x_{i},y_{i})$.

Let $u\otimes v$ be a rank-1 matrix. If there exists $i\leq r$ such that
$\langle x_{i},v\rangle\neq 0$, then $(A+u\otimes v)(x_{i})=y_{i}+u$, so
$A+u\otimes v\notin\mathcal{C}_{i}$ and hence $A+u\otimes v\notin\mathcal{C}$.
Similarly, if there exists $i>r$ such that $\langle x_{i},u\rangle\neq 0$,
then $(A+u\otimes v)^{T}(x_{i})=y_{i}+v$ and again $A+u\otimes
v\notin\mathcal{C}$.

We shall now bound from below the probability that $A+u\otimes
v\in\mathcal{A}$ given that $A\in\mathcal{A}$ and that $\langle
x_{i},v\rangle=0$ for every $i\leq r$ and $\langle x_{i},u\rangle=0$ for every
$r<i\leq k$, noting that the condition on $u\otimes v$ states that $(u,v)\in
U\times V$ for a pair of subspaces $U$ and $V$ with codimensions that add up
to at most $k$, a condition that occurs with probability $2^{-k}$.

Let us now condition further on the choice of $v\in V$. That means that we fix
$v$, choose a random $u\in U$, and add $u\otimes v$ to $A$. If we allow $u$ to
take the value 0, then the resulting matrix is uniformly distributed in the
affine subspace $A+U\otimes v$, so the probability that it is in $\mathcal{A}$
is equal to the relative density of $\mathcal{A}$ inside this affine subspace.

The translates of $U\otimes v$ by matrices in $\mathcal{C}$ partition
$\mathcal{C}$. Let us write them as $\mathcal{W}_{1},\dots,\mathcal{W}_{s}$,
and let the relative density of $\mathcal{A}$ inside $\mathcal{W}_{i}$ be
$\delta_{i}$. Then, still fixing $v$, we have that

$\mathbb{P}[A+u\otimes
v\in\mathcal{A}]=\sum_{i}\,\mathbb{P}[A\in\mathcal{W}_{i}]\,\mathbb{P}[A+u\otimes
v\in\mathcal{A}|A\in\mathcal{W}_{i}]=\sum_{i}\frac{\delta_{i}^{2}}{s\delta}\geq\delta.$

This statement is true regardless of $v$, so we deduce that the probability
that $A+u\otimes v\in\mathcal{A}$ given that $A\in\mathcal{A}$ and $(u,v)\in
U\times(V\setminus\\{0\\})$ is at least $\delta$. If we now insist that $u\neq
0$, we reduce this probability by at most $2^{-(m-k)}$, so the result is
proved. ∎

Let $B\in\mathcal{B}$ be chosen uniformly at random. Given the lemma above,
applied to the sets $\mathcal{A}_{i}$ and $\mathcal{C}_{i}$, we deduce that
the conditional probability that $A+B\in\mathcal{A}_{i}$ given that
$A\in\mathcal{A}_{i}$ is at least $c(\delta,k)$, and from that it follows that
$\mathcal{A}$ is $c(\delta,k)\eta/4$-closed.

Thus, a set $\mathcal{A}$ is $\eta$-closed for some not too small $\eta$ if
and only if an appreciable fraction of $\mathcal{A}$ is efficiently covered by
disjoint intersections of few basic sets.

Barak, Kothari and Steurer suggest in [1] that establishing a higher
dimensional analogue of Theorem 1.1 may be a useful step in obtaining a proof
of the full Unique Games Conjecture, though they do not actually provide a
formal reduction. The main purpose of this paper is to formulate a suitable
conjecture and prove some partial results towards it. We say that
$\mathcal{A}\subset\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$
is $\eta$-closed if with probability at least $\eta$, we have
$A+u_{1}\otimes\dots\otimes u_{d}\in\mathcal{A}$, when $A\in\mathcal{A}$ and
vectors $u_{i}\in\mathbb{F}_{2}^{n_{i}}\setminus\\{0\\}$ are chosen
independently and uniformly at random.

######  Problem 1.3.

Give a qualitative description of $\eta$-closed sets
$\mathcal{A}\subset\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$.

To see that this is indeed a generalization of the problem about matrices
considered above, we identify $\mathrm{M}_{m,n}(\mathbb{F}_{2})$ with
$\mathbb{F}_{2}^{m}\otimes\mathbb{F}_{2}^{n}$ in the usual way, which leads to
a slight reformulation of Theorem 1.1 in terms of tensor products. Note first
that under this identification, the set
$\\{M\in\mathrm{M}_{m,n}(\mathbb{F}_{2}):Mx_{1}=\dots=Mx_{a}=M^{T}y_{1}=\dots=M^{T}y_{b}=0\\}$
becomes the set $H\otimes K$, where $H=\langle
y_{1},\dots,y_{b}\rangle^{\perp}$ and $K=\langle
x_{1},\dots,x_{a}\rangle^{\perp}$. It follows that an intersection of at most
$k$ basic sets is either empty or a translate of $H\otimes K$ for some pair of
subspaces $H\subset\mathbb{F}_{2}^{m},K\subset\mathbb{F}_{2}^{n}$ with ${\rm
codim}(H)+{\rm codim}(K)\leq k$.

In the higher-dimensional case, there is a richer class of sets
$\mathcal{A}\subset\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$
that are $\eta$-closed. To describe them, we introduce the following piece of
notation, which we shall use repeatedly in the rest of the paper. Given a non-
empty subset $I\subset[d]$, write $\mathbb{F}_{2}^{I}$ for $\bigotimes_{i\in
I}\mathbb{F}_{2}^{n_{i}}$, so that we naturally have
$\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}=\mathbb{F}_{2}^{I}\otimes\mathbb{F}_{2}^{I^{c}}$.
Here and elsewhere in the paper, $I^{c}$ stands for $[d]\setminus I$.

Now we say that $\mathcal{C}$ is $k$-_simple_ if there exists a collection of
subspaces $H_{I}\subset\mathbb{F}_{2}^{I}$ of codimension at most $k$, one for
each non-empty subset $I\subset[d]$, such that $\mathcal{C}$ is a translate of
the set
$\bigcap_{I\subset[d],I\neq\emptyset}(H_{I}\otimes\mathbb{F}_{2}^{I^{c}})$
(where $H_{[d]}\otimes\mathbb{F}_{2}^{\emptyset}$ is just $H_{[d]}$), which is
a subspace of
$\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$. It is not
hard to see that this subspace contains at least a proportion $c(d,k)>0$ of
all rank-1 tensors $u_{1}\otimes\dots\otimes u_{d}$ (provided that
$n_{1},\dots,n_{d}$ are sufficiently large), so it is $c(d,k)$-closed. It
follows that any translate of it is $c(d,k)$-closed too.

We now make the following conjecture.

######  Conjecture 1.4.

For any $\eta>0$ and any positive integer $d$, there exist $k=k(d,\eta)$ and
$\rho=\rho(d,\eta)>0$ with the following property. Let
$\mathcal{A}\subset\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$
be $\eta$-closed. Then there is a $k$-simple set $\mathcal{C}$ such that
$|\mathcal{A}\cap\mathcal{C}|\geq\rho|\mathcal{C}|$.

Note that in the $d=2$ case, we allow translates of sets $(H_{\\{1\\}}\otimes
H_{\\{2\\}})\cap H_{\\{1,2\\}}$ rather than just translates of
$H_{\\{1\\}}\otimes H_{\\{2\\}}$, so Conjecture 1.4 might seem to be weaker
than Theorem 1.1. However, this actually makes no difference, since when
intersecting with $H_{\\{1,2\\}}$, the cardinality of the set drops by a
factor at most $2^{k}$.

The main result of this paper, stated later in this section, is a proof of
Conjecture 1.4 in an important special case.

###  1.1. What can be said about more general Cayley graphs?

It is tempting to try to prove Conjecture 1.4 by identifying and proving a
statement that applies to a much wider class of Cayley graphs, of which
Conjecture 1.4 would be a special case. We would begin with an Abelian (or
even non-Abelian) group $G$ and a pair of subsets $A,B\subset G$, where we
think of $B$ as the set of generators, satisfying the hypothesis that
$|\\{(a,b)\in A\times B:a+b\in A\\}|\geq\eta|A||B|$. We shall say in this
situation that $A$ is $(B,\eta)$-_closed_ (in $G$).

Another way of writing the condition is

$\langle\mathbbm{1}_{A}*\mu_{B},\mathbbm{1}_{A}\rangle\geq\eta\alpha,$

where $\alpha$ is the density of $A$, $\mu_{B}$ is the characteristic measure
of $B$ (that is, the function that takes the value $|G|/|B|$ on $B$ and 0
elsewhere) and we define $f*g(x)$ to be $\mathbb{E}_{y+z=x}f(y)g(z)$. By the
Cauchy-Schwarz inequality the left-hand side is at most
$\|\mathbbm{1}_{A}*\mu_{B}\|_{2}\|\mathbbm{1}_{A}\|_{2}=\|\mathbbm{1}_{A}*\mu_{B}\|_{2}\alpha^{1/2}$,
where inner products and $L_{p}$ norms are defined using expectations, so our
hypothesis implies that
$\|\mathbbm{1}_{A}*\mu_{B}\|_{2}^{2}\geq\eta^{2}\alpha$. It is easy to see
that this “mixed energy” $\|\mathbbm{1}_{A}*\mu_{B}\|_{2}^{2}$ can be at most
$\alpha$, with equality if and only if $a+b-b^{\prime}\in A$ for every $a\in
A,b,b^{\prime}\in B$.

At this point let us recall the so-called asymmetric Balog-Szemerédi-Gowers
theorem, which can be found in [8] as Theorem 2.35. (For a useful alternative
presentation of the theorem, see also [3].) The main assumption of the theorem
is that $A,B$ are two finite subsets of an Abelian group, with densities
$\alpha$ and $\beta$, such that
$\|\mathbbm{1}_{A}*\mathbbm{1}_{B}\|_{2}^{2}\geq\eta\alpha\beta^{2}$ (which is
equivalent to saying that
$\|\mathbbm{1}_{A}*\mu_{B}\|_{2}^{2}\geq\eta\alpha$), but there is also an
assumption that $A$ is not too much bigger than $B$. The precise statement is
as follows.

######  Theorem 1.5.

For every $\epsilon>0$ there exists a constant $C=C(\epsilon)$ with the
following property. Let $G$ be a finite Abelian group, let $L\geq 1$, let
$0<\eta\leq 1$ and let $A$ and $B$ be finite subsets of $G$ with densities
$\alpha$ and $\beta$, such that $\alpha\leq L\beta$ and
$\|\mathbbm{1}_{A}*\mathbbm{1}_{B}\|_{2}^{2}\geq 2\eta\alpha\beta^{2}$. Then
there exist a subset $H\subset G$ such that $|H+H|\leq
C\eta^{-C}L^{\epsilon}|H|$, a subset $X\subset G$ of size at most
$C\eta^{-C}L^{\epsilon}|A|/|H|$ such that $|A\cap(X+H)|\geq
C^{-1}\eta^{C}L^{-\epsilon}|A|$, and some $x\in G$ such that $|B\cap(x+H)|\geq
C^{-1}\eta^{C}L^{-\epsilon}|B|$.

More qualitatively speaking, if $A$ is not too much larger than $B$ and
$\|\mathbbm{1}_{A}*\mathbbm{1}_{B}\|_{2}^{2}$ is within a constant of its
largest possible value, then there is a set $H$ of small doubling such that a
small number of translates of $H$ cover a substantial proportion of $A$, and
some translate of $H$ covers a substantial proportion of $B$. It is not hard
to see that the converse holds as well.

This theorem cannot be used to prove Conjecture 1.4 because of the condition
that $\alpha\leq L\beta$, which does not apply here since the set
$\mathcal{A}$ in Conjecture 1.4 can be much bigger than the set $\mathcal{B}$.
That raises the following question, which generalizes Problem 1.3.

######  Question 1.6.

Let $G$ be a finite Abelian group, let $\eta>0$, and let $A,B\subset G$ be
subsets such that $A$ is $(B,\eta)$-closed in $G$. What can be said about $A$,
$B$ and the relationship between them?

A similar question can of course be asked with the slightly weaker hypothesis
that $\|\mathbbm{1}_{A}*\mathbbm{1}_{B}\|_{2}^{2}\geq\eta^{2}\alpha\beta^{2}$,
but we shall concentrate on the question as stated, since it is more closely
related to Conjecture 1.4.

An immediate observation is that we cannot hope to say anything interesting
about the structure of $B$, even if $\eta=1$. For example, $\eta=1$ if $A=G$
and $B$ is an arbitrary subset of $G$. For a more general example, one can let
$A$ be an arbitrary union of cosets of some subgroup $H$ and let $B$ be an
arbitrary subset of $H$. For a slightly different example, let
$G=\mathbb{F}_{2}^{n}$, let $B$ be the set $\\{e_{1},\dots,e_{n}\\}$ of
standard basis vectors, and let $A$ be a union of $n/3$-dimensional affine
subspaces $V_{i}$, such that each $V_{i}$ is a random translate of the
subspace generated by $n/3$ randomly chosen $e_{j}$. Then if $x\in V_{i}$ and
$b\in B$, the probability that $x+b\in V_{i}$ is 1/3, so $A$ is 1/3-closed.

Any general statement will have to be weak enough to allow for examples like
these. The last example shows that we cannot hope to find a single set $H$ of
small doubling and cover a large portion of $A$ efficiently with translates of
$H$, unless $H$ is of constant size, in which case the conclusion becomes
trivial. To sketch briefly why not, observe first that by Freiman’s theorem we
can assume that $H$ is a subspace. Next, note that for each vector $x$, the
probability that it belongs to the span of a random $n/3$ standard basis
vectors is exponentially small in the size of the support of $x$. We can also
use the following simple lemma.

######  Lemma 1.7.

Let $H$ be a subspace of dimension $d$ and let $k\leq d$. Then the number of
vectors in $H$ of support size at most $k$ is at most the number of vectors of
support size at most $k$ in the subspace generated by the first $d$ standard
basis vectors $e_{1},\dots,e_{d}$, namely $\sum_{i=0}^{k}\binom{d}{i}$.

###### Proof.

Let $u_{1},\dots,u_{d}$ be a basis for $d$. By Gaussian elimination, we can
convert $u_{1},\dots,u_{d}$ into a basis $v_{1},\dots,v_{d}$ and find
coordinates $t_{1},\dots,t_{d}$ such that $v_{i}(t_{j})=\delta_{ij}$. Then the
support size of $\sum_{i}\lambda_{i}v_{i}$ is at least the number of non-zero
$\lambda_{i}$, which proves the result. ∎

When $d$ is large, it follows that the proportion of vectors in $H$ of small
support is very small. Combining these observations, one can show that for
every $\eta$ there exists $d$ such that if $H$ is a $d$-dimensional subspace,
then the probability that a random subspace $V$ of dimension $n/3$ is
$(H,\eta/2)$-closed is at most $\eta/2$. This in turn can be used to prove
that with high probability the set $A$ described above (for a suitable number
of $V_{i}$) is not $(H,\eta)$-closed for any $H$ of dimension $d$ or above.

However, these examples do not rule out a weakening along the following lines.

######  Question 1.8.

Let $G$ be a finite Abelian group, let $\eta>0$, and let $A,B$ be subsets of
$G$ such that $A$ is $(B,\eta)$-closed in $G$. Does it follow that $A$ has a
non-empty subset $A^{\prime}$ such that $A^{\prime}$ is
$(B,\eta^{\prime})$-closed in $G$, and $|A^{\prime}+A^{\prime}|\leq
C|A^{\prime}|$, where $\eta^{\prime}>0$ and $C$ are constants that depend on
$\eta$ only?

An argument similar to the one we mentioned just after the statement of
Theorem 1.1 shows that if the answer is yes, then we can find a collection of
disjoint subsets $A_{1},\dots,A_{m}$ that cover a substantial proportion of
$A$, each one with small doubling and each one $(B,\eta^{\prime})$-closed
(with a slightly smaller $\eta^{\prime}$). Thus, we would be able to obtain a
conclusion similar to that of Theorem 1.5 but without the requirement that the
structured sets are all translates of one another.

A positive answer would also imply Conjecture 1.4. Indeed, by Freiman’s
theorem $A_{i}$ is contained in a subspace $V_{i}$ not much larger than
$A_{i}$. This reduces the conjecture to the case where $\mathcal{A}$ is a
subspace. In that case, a very simple corollary of our main result, Corollary
1.12 (stated later) proves the conjecture.

However, the answer to Question 1.8 is easily seen to be negative (which
implies that it is also negative if we assume the weaker mixed-energy
hypothesis instead). The example we are about to give was communicated to us
privately by Boaz Barak as a counterexample to a related but slightly
different statement.

For convenience let $n$ be odd, let $A\subset\mathbb{F}_{2}^{n}$ be the set of
all vectors with $(n\pm 1)/2$ coordinates equal to 1, and let $B$ be the set
of standard basis vectors. Then it is easy to see that $A$ is $\eta$-closed
for $\eta=(n+1)/2n\approx 1/2$. Suppose now that we could find a subset
$A^{\prime}\subset A$ such that $|A^{\prime}+A^{\prime}|\leq C|A^{\prime}|$,
and $A^{\prime}$ is $(B,\eta^{\prime})$-closed. By Freiman’s theorem,
$A^{\prime}$ is contained in a subspace $V$ that is not much bigger than
$A^{\prime}$, which implies that $V$ is $c$-closed for some positive constant
$c=c(\eta)$. That implies that at least $cn$ of the standard basis vectors
belong to $V$. Let $W$ be the subspace spanned by these basis vectors. The
maximum number of elements of $A$ that can belong to a translate $x+W$ of $W$
is $2(cn)^{-1/2}|W|$, and therefore $|A^{\prime}|\leq 2(cn)^{-1/2}|V|$. This
contradicts the fact that $V$ is not much bigger than $A^{\prime}$.

In this paper we formulate a yet weaker conjecture and prove that it still
implies Conjecture 1.4. Unfortunately, we also give a counterexample to the
weaker conjecture. The counterexample does not make the implication vacuous,
however, because the implication depends on a non-trivial theorem that is true
and of some interest: it is just that for a general Cayley graph (on a finite
Abelian group) one cannot deduce the hypotheses of the theorem from the
assumption that a set is $\eta$-closed. It is conceivable that one might be
able to prove Conjecture 1.4 (and thereby also give a different proof of the
theorem of Khot, Minzer and Safra) by using additional properties of the
particular Cayley graph that that conjecture is about.

How, then, might one try to find a conjecture that would not be contradicted
by the “two-layers” example just discussed? One observation that suggests a
possible way forward is the following. Suppose that we extend the set by
adding a few more layers. If, say, we take not just the middle two layers but
the middle $\epsilon^{-1}$ layers (or thereabouts), then we obtain a new set
inside which the first set has relative density approximately $2\epsilon$, and
this new set is $(1-2\epsilon)$-closed, since a random element of the set will
be in one of the interior layers with probability approximately (and in fact
slightly bigger than) $1-2\epsilon$, and adding an arbitrary basis vector to
such an element will give another element of the set.

So perhaps we could hope that if $A$ is $(B,\eta)$-closed, then there is a set
$C$ that is $(B,1-\epsilon)$-closed such that $|A\cap C|\geq\delta|C|$ for
some $\delta$ that depends on $\eta$ and $\epsilon$ only.

However, simple modifications of the example show that this is too much to
ask. For instance, we can take as our set $A$ the set of all
$x\in\mathbb{F}_{2}^{n}$ such that $m$ or $m+1$ coordinates are equal to 1 and
all but the first $2m$ coordinates are zero. If $m$ is around $n/4$, say, then
the resulting set is $(B,1/4)$-closed, but there is no prospect of $A$ living
densely in a set that is almost perfectly closed, because of the need to add
basis vectors corresponding to coordinates beyond $2m$.

A further example to consider is the set of all $x\in\mathbb{F}_{2}^{n}$ such
that at most $n/3$ coordinates are equal to 1. This set is $(B,1/3)$-closed
(at least – in fact it is more like $(B,2/3)$-closed because the probability
that a random element of the set has exactly $\lfloor n/3\rfloor$ coordinates
equal to 1 is approximately 1/2), but for similar reasons to the previous
example, one cannot find an almost perfectly closed set with a significant
proportion of its elements in the set.

However, the picture changes if we ask for slightly less. Let us informally
call a set $C$ _good_ if there is a proportional-sized subset
$B^{\prime}\subset B$ such that $C$ is $(B^{\prime},1-\epsilon)$-good for some
small constant $\epsilon$. Thus, now we ask only that $C$ should be almost
closed for a _large subset_ of $B$ rather than for the whole set.

It is not immediately clear how to use this definition, because the statement
that $|A\cap C|\geq\delta|C|$ for a good set $C$ can be true for uninteresting
reasons. For example, we could take $C$ to be the union of a subspace $V$
generated by $n/5$ basis vectors together with an arbitrary subset of $A$ of
cardinality $2\delta|V|$. To remedy this, we insist that $C$ is “related to
$A$” in the graph in a different sense from that of $A$ being dense in $C$.

Here, then, is a question that replaces Question 1.8.

######  Question 1.9.

Is it true that for every $\eta,\epsilon>0$ there exist $c>0,\delta>0$ and
positive integer $l$ with the following property? Let $G$ be a finite Abelian
group and let $A,B\subset G$ be subsets such that $A$ is $(B,\eta)$-closed.
Then there is a subset $B^{\prime}\subset B$ and a non-empty subset $C\subset
G$ with the following properties.

  1. (1)

$|B^{\prime}|\geq\delta|B|$.

  2. (2)

$C$ is $(B^{\prime},1-\epsilon)$-closed.

  3. (3)

$C\subset\bigl{\\{}x\in
G:\mathbbm{1}_{A}*\mu_{B}*\dots*\mu_{B}*\mu_{-B}*\dots*\mu_{-B}(x)\geq
c\bigr{\\}}$ where the number of $\mu_{B}$s and $\mu_{-B}$s in the convolution
is $l$.

Condition (3) is saying that for any $x\in C$, the probability that
$x-b_{1}-\dots-b_{l}+b_{l+1}+\dots+b_{2l}\in A$, when the $b_{i}$ are chosen
uniformly and independently at random from $B$, is at least $c$. When the
group $G$ is $\mathbb{F}_{2}^{n}$ for some $n$, we can and will simplify it,
since $B=-B$.

To see that this question improves on Question 1.8, let us consider the two
problematic examples for that question. If $m$ is odd and
$A\subset\mathbb{F}_{2}^{n}$ consists of all sequences with $(m\pm 1)/2$ 1s
and with no 1s after the $m$th coordinate, then let $C$ be the set of all
sequences with no 1s after the $m$th coordinate that have between
$(m-1)/2-\epsilon^{-1}$ and $(m+1)/2+\epsilon^{-1}$ 1s. If $l=\epsilon^{-1}$,
then for any $x\in C$, the probability that $x-b_{1}-\dots-b_{l}\in A$ is at
least $(\frac{m}{2n})^{l}$. (This is because conditional on
$b_{i}\in\\{e_{1},\dots,e_{m}\\}$ this probability is at least
$\frac{1}{2^{l}}$.) Moreover, if $B^{\prime}=\\{e_{1},\dots,e_{m}\\}$, then
for every $b\in B^{\prime}$ and every $c\in C$ that is not on the boundary (in
the obvious sense), we have that $b+c\in C$, so $C$ is
$(B^{\prime},1-\epsilon)$-closed.

Now let us look at the example where $A$ is the set of all sequences with at
most $n/3$ 1s. This time let $C$ be the set of all sequences that are 0 after
the first $2n/3$ coordinates and have at most $n/3+\epsilon^{-1}$ 1s, and let
$B^{\prime}=\\{e_{1},\dots,e_{2n/3}\\}$. Then for any $x\in C$, the
probability that $x-b_{1}-\dots-b_{l}\in A$ is at least $(\frac{1}{3})^{l}$,
where $l=\epsilon^{-1}$. Moreover, $C$ is $(1-\epsilon)$-closed, again because
adding an element of $B^{\prime}$ to a non-boundary element of $C$ gives an
element of $C$.

###  1.2. Our main result

Let us now see why a positive answer to Question 1.9 would imply Conjecture
1.4. The deduction will be easy once we have established the following
theorem, which is the main result of this paper. In the statement of the
theorem, and in the rest of this paper, $\mathcal{G}$ denotes
$\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$ and
$\mathcal{B}$ denotes the multiset $\\{u_{1}\otimes\dots\otimes
u_{d}:u_{i}\in\mathbb{F}_{2}^{n_{i}}\text{ for all }i\\}$ (which is a multiset
only because some of the $u_{i}$ can be zero). Note that the notion of
$(B,\eta)$-closedness can be generalized in an obvious way to multisets.

######  Theorem 1.10.

For any $\theta>0$, there exists $\epsilon=\epsilon(d,\theta)>0$ with the
following property. Let $\delta>0$. Then there exists a positive integer
$k=k(d,\delta)$ with the following property. For any
$\mathcal{B}^{\prime}\subset\mathcal{B}$ with
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$ and any
$\mathcal{A}\subset\mathcal{G}$ which is
$(\mathcal{B}^{\prime},1-\epsilon)$-closed, there exists a $k$-simple set
$\mathcal{D}\subset\mathcal{G}$ such that
$|\mathcal{D}\cap\mathcal{A}|\geq(1-\theta)|\mathcal{D}|$.

It is convenient to state the following corollary separately, which follows
from Theorem 1.10 by taking $\theta=1/2$.

######  Corollary 1.11.

There exists $\epsilon=\epsilon(d)>0$ such that for any $\delta>0$, there
exists a positive integer $k=k(d,\delta)$ with the following property. For any
$\mathcal{B}^{\prime}\subset\mathcal{B}$ with
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$ and any
$\mathcal{A}\subset\mathcal{G}$ which is
$(\mathcal{B}^{\prime},1-\epsilon)$-closed, there exists a $k$-simple set
$\mathcal{D}\subset\mathcal{G}$ which has
$|\mathcal{D}\cap\mathcal{A}|\geq\frac{1}{2}|\mathcal{D}|$.

Let us see why Conjecture 1.4 follows from Corollary 1.11 and a positive
answer to Question 1.9 in the case of the group $\mathcal{G}$ and the subset
$B\subset\mathcal{G}$ of rank-1 tensors. Let $\eta>0$. Pick
$\epsilon=\epsilon(d)$ so that the conclusion of Corollary 1.11 holds. If the
answer to Question 1.9 is positive for $\mathcal{G}$ and $B$, then we can
choose $c>0,\delta>0$, and a positive integer $l$ such that the conclusion of
the question is true. Now let $\mathcal{A}\subset\mathcal{G}$ be
$\eta$-closed. This is saying that $\mathcal{A}$ is $(B,\eta)$-closed. By the
conclusion of Question 1.9, there exist a set $B^{\prime}\subset B$ with
$|B^{\prime}|\geq\delta|B|$ , and a non-empty subset
$\mathcal{C}\subset\mathcal{G}$ such that $\mathcal{C}$ is
$(B^{\prime},1-\epsilon)$-closed and
$\mathcal{C}\subset\bigl{\\{}x\in\mathcal{G}:\mathbbm{1}_{\mathcal{A}}*\mu_{B}*\dots*\mu_{B}(x)\geq
c\bigr{\\}}$, where the number of $\mu_{B}$s in the convolution is $l$. Define
$\mathcal{B}^{\prime}$ to be the multiset that consists of the set
$B^{\prime}$ together with the multiset of all $u_{1}\otimes\dots\otimes
u_{d}$ with $u_{i}\in\mathbb{F}_{2}^{n_{i}}$ for each $i$ and with at least
one $u_{i}$ equal to $0$. Note that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$ and $\mathcal{C}$ is
$(\mathcal{B}^{\prime},1-\epsilon)$-closed. By Corollary 1.11, there exists a
$k$-simple set $\mathcal{D}\subset\mathcal{G}$, for some $k=k(d,\delta)$,
which has $|\mathcal{D}\cap\mathcal{C}|\geq\frac{1}{2}|\mathcal{D}|$. Now pick
$x\in\mathcal{D}$ and $b_{1},\dots,b_{l}\in B$ uniformly and independently at
random. The probability that $x-b_{1}-\dots-b_{l}\in\mathcal{A}$ is at least
$c/2$. Therefore, there exists some $y\in\mathcal{G}$ such that when
$x\in\mathcal{D}$ is randomly chosen, the probability that $x-y\in\mathcal{A}$
is at least $c/2$. That is,
$|(\mathcal{D}-y)\cap\mathcal{A}|\geq\frac{1}{2}c|\mathcal{D}|=\frac{1}{2}c|\mathcal{D}-y|$.
But $\mathcal{D}-y$ is a $k$-simple set, which finishes the proof of
Conjecture 1.4.

Another simple corollary of Theorem 1.10 is the following result, which is
Conjecture 1.4 in the case where $\mathcal{A}$ is a subspace.

######  Corollary 1.12.

For any $\eta>0$ and any positive integer $d$, there exists some $k=k(d,\eta)$
with the following property. If $V\subset\mathcal{G}$ is a subspace which is
$\eta$-closed, then $V$ contains a $k$-simple subspace. That is,
$V\supset\bigcap_{I\subset[d],I\neq\emptyset}(H_{I}\otimes\mathbb{F}_{2}^{I^{c}})$
for some collection of subspaces $H_{I}\subset\mathbb{F}_{2}^{I}$ of
codimension at most $k$.

###### Proof.

Since $V$ is a vector space, the condition that $V$ is $\eta$-closed says that
$u_{1}\otimes\dots\otimes u_{d}\in V$ for at least a proportion of $\eta$ of
all rank-1 tensors $u_{1}\otimes\dots\otimes u_{d}$. Thus, there exists some
$\mathcal{B}^{\prime}\subset\mathcal{B}$ with
$|\mathcal{B}^{\prime}|\geq\eta|\mathcal{B}|$ such that $V$ is
$(\mathcal{B}^{\prime},1)$-closed. Taking $\theta$ sufficiently close to $0$
in Theorem 1.10, it follows that $V\supset\mathcal{D}$ for a $k$-simple set
$\mathcal{D}$, where $k$ depends only on $d$ and $\eta$. Then $\mathcal{D}$ is
a translate of
$\bigcap_{I\subset[d],I\neq\emptyset}(H_{I}\otimes\mathbb{F}_{2}^{I^{c}})$ for
some $H_{I}\subset\mathbb{F}_{2}^{I}$ of codimension at most $k$. Since $V$ is
a vector space, it follows that
$V\supset\bigcap_{I\subset[d],I\neq\emptyset}(H_{I}\otimes\mathbb{F}_{2}^{I^{c}})$.
∎

In the next section, we shall prove Theorem 1.10. In the last section, we show
that the answer to Question 1.9 is negative.

##  2\. The proof of Theorem 1.10

Note that
$\mathcal{G}=\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$
can be viewed as the set of $d$-dimensional $(n_{1},\dots,n_{d})$-arrays over
$\mathbb{F}_{2}$ which in turn can be viewed as
$\mathbb{F}_{2}^{n_{1}n_{2}\dots n_{d}}$, equipped with the entry-wise dot
product.

The proof of Theorem 1.10 will be reasonably simple once we have established
the following result. In the statement of this lemma, and in the rest of this
section, we write $kB$ to mean the set of elements of $\mathcal{G}$ that can
be written as a sum of at most $k$ elements of $B$, where $B$ is some fixed
(multi)subset of $\mathcal{G}$.

######  Lemma 2.1.

For all $\delta>0$ and $d\in\mathbb{N}$ there exist $f_{1}(d),f_{3}(d)>0$ and
$f_{2}(d,\delta)\in\mathbb{N}$ with the following property. Let
$\mathcal{B}^{\prime}\subset\mathcal{B}$ be a multiset such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Then there exists a multiset
$Q$ whose elements are chosen from $f_{1}(d)\mathcal{B}^{\prime}$ (but with
arbitrary multiplicity) with the following property. The set of arrays
$r\in\mathcal{G}$ with $r.q=0$ for at least $(1-f_{3}(d))|Q|$ choices $q\in Q$
is contained in
$\sum_{I\subset[d],I\neq\emptyset}V_{I}\otimes\mathbb{F}_{2}^{I^{c}}$ for a
collection of subspaces $V_{I}\subset\mathbb{F}_{2}^{I}$ that each have
dimension at most $f_{2}(d,\delta)$.

In order to deduce Theorem 1.10 from this lemma, we shall use Fourier
analysis. Recall that if $A$ is a subset of $\mathcal{G}$ of density $\alpha$,
then by Parseval’s identity we have
$\alpha=\sum_{r}|\widehat{\mathbbm{1}_{A}}(r)|^{2}$. Also, if $B$ is a
multiset in $\mathcal{G}$, then by Parseval’s identity and the convolution
law,
$\langle\mathbbm{1}_{A}*\mu_{B},\mathbbm{1}_{A}\rangle=\sum_{r}|\widehat{\mathbbm{1}_{A}}(r)|^{2}\widehat{\mu}_{B}(r)$
(for a multiset $B$, we define $\mu_{B}(x)=\frac{|G|}{|B|}B(x)$ where $B(x)$
is the multiplicity of $x$ in $B$). Thus, the condition that $A$ is
$(B,\eta)$-closed can be rewritten as the inequality

$\sum_{r}|\widehat{\mathbbm{1}_{A}}(r)|^{2}\widehat{\mu}_{B}(r)\geq\eta\sum_{r}|\widehat{\mathbbm{1}_{A}}(r)|^{2}.$

Another fact we shall use later is that if $W$ is a subspace of $\mathcal{G}$,
then $\widehat{\mu_{W}}(r)$ equals $\mathbb{E}_{w\in W}(-1)^{r.w}$, which is 1
if $r$ belongs to the orthogonal complement of $W$ and 0 otherwise.

######  Lemma 2.2.

Let $G$ be an Abelian group, let $A\subset G$ be a finite subset, let
$\eta_{1},\eta_{2}>0$, and let $b_{1},b_{2}\in G$. Suppose that $A$ is
$(\\{b_{1}\\},1-\eta_{1})$-closed and $(\\{b_{2}\\},1-\eta_{2})$-closed in
$G$. Then $A$ is $(\\{b_{1}+b_{2}\\},1-\eta_{1}-\eta_{2})$-closed in $G$.

###### Proof.

Let $A_{\text{bad}}=\\{a\in A:a+b_{2}\not\in A\\}$. Then
$|A_{\text{bad}}|\leq\eta_{2}|A|$, by hypothesis. So when $a\in A$ is chosen
randomly, we have that

$\mathbb{P}[a+b_{1}+b_{2}\not\in A]\leq\mathbb{P}[a+b_{1}\not\in
A]+\mathbb{P}[a+b_{1}\in A_{\text{bad}}]\leq\eta_{1}+\eta_{2}.$

The result follows. ∎

We are now in a position to deduce Theorem 1.10 from Lemma 2.1. In the proof,
and in the rest of this section, whenever a new function $g_{i}$ appears, we
mean that there exists a function $g_{i}$ with the claimed property.

###### Proof of Theorem 1.10.

Let $\theta,\delta>0$, $\mathcal{B}^{\prime}\subset\mathcal{B}$ with
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$, and suppose that
$\mathcal{A}\subset\mathcal{G}$ is $(\mathcal{B}^{\prime},1-\epsilon)$-closed,
where $\epsilon$ is to be specified. Let
$\mathcal{B}^{\prime\prime}=\\{b\in\mathcal{B}^{\prime}:\mathcal{A}\text{ is
}(\\{b\\},1-2\epsilon)\text{-closed}\\}$. Clearly,
$|\mathcal{B}^{\prime\prime}|\geq\frac{1}{2}|\mathcal{B}^{\prime}|$. Using
Lemma 2.1, we can find a multiset $Q$ with elements chosen from
$g_{1}(d)\mathcal{B}^{\prime\prime}$ such that the set of arrays
$r\in\mathcal{G}$ with $r.q=0$ for at least $(1-g_{2}(d))|Q|$ choices $q\in Q$
(where $g_{2}(d)>0$) is contained in
$\sum_{I\subset[d],I\neq\emptyset}V_{I}\otimes\mathbb{F}_{2}^{I^{c}}$ for
subspaces $V_{I}\subset\mathbb{F}_{2}^{I}$ of dimension at most
$g_{3}(d,\delta)$. Then, by Lemma 2.2, $\mathcal{A}$ is
$(\\{b\\},1-2g_{1}(d)\epsilon)$-closed for every $b\in Q$, since each such $b$
is an element of $g_{1}(d)\mathcal{B}^{\prime\prime}$. In particular,
$\mathcal{A}$ is $(Q,1-2g_{1}(d)\epsilon)$-closed, and therefore

$\sum_{r}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}\widehat{\mu}_{Q}(r)\geq(1-2g_{1}(d)\epsilon)\sum_{r}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}.$

By Markov’s inequality, it follows that

$\sum_{r:\widehat{\mu}_{Q}(r)<1-2g_{2}(d)}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}\leq\frac{g_{1}(d)\epsilon}{g_{2}(d)}\sum_{r}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}.$

Choosing $\epsilon=\epsilon(d,\theta)>0$ to be at most $\theta
g_{2}(d)/g_{1}(d)$, we therefore have

$\sum_{r:\widehat{\mu}_{Q}(r)\geq
1-2g_{2}(d)}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}\geq(1-\theta)\sum_{r}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}.$

Now if $\widehat{\mu}_{Q}(r)\geq 1-2g_{2}(d)$ then $r.q=0$ for at least
$(1-g_{2}(d))|Q|$ choices $q\in Q$. Thus, we have

$\sum_{r\in
T}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}\geq(1-\theta)\sum_{r\in\mathcal{G}}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}$
(1)

where $T=\sum_{I\subset[d],I\neq\emptyset}V_{I}\otimes\mathbb{F}_{2}^{I^{c}}$.
Let
$R=T^{\perp}=\bigcap_{I\subset[d],I\neq\emptyset}V_{I}^{\perp}\otimes\mathbb{F}_{2}^{I^{c}}$.
Because $\widehat{\mu_{R}}$ is the characteristic function of $T$, (1) is
equivalent to the inequality

$\sum_{r\in\mathcal{G}}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2}\widehat{\mu_{R}}(r)\geq(1-\theta)\sum_{r\in\mathcal{G}}|{\widehat{\mathbbm{1}_{\mathcal{A}}}}(r)|^{2},$

which in physical space is the inequality

$\langle\mathbbm{1}_{\mathcal{A}}*\mathbbm{1}_{\mathcal{A}},\mu_{R}\rangle\geq(1-\theta)\|\mathbbm{1}_{\mathcal{A}}\|_{2}^{2}=(1-\theta)\alpha,$

where $\alpha$ is the density of $\mathcal{A}$. Equivalently,

$\langle\mu_{\mathcal{A}}*\mu_{R},\mathbbm{1}_{\mathcal{A}}\rangle\geq
1-\theta,$

which tells us that if a random element of $\mathcal{A}$ is added to a random
element of $R$, then the sum belongs to $\mathcal{A}$ with probability at
least $1-\theta$. The number of triples
$(a_{1},a_{2},r)\in\mathcal{A}\times\mathcal{A}\times R$ with $a_{1}+a_{2}=r$
is therefore at least $(1-\theta)|\mathcal{A}||R|$, and therefore, by
averaging, there exists $a\in\mathcal{A}$ such that
$|(R-a)\cap\mathcal{A}|\geq(1-\theta)|R|=(1-\theta)|R-a|$. But $R-a$ is
$g_{3}(d,\delta)$-simple, so we can take $k=g_{3}(d,\delta)$ and
$\mathcal{D}=R-a$. ∎

It remains to prove Lemma 2.1.

###  2.1. The proof of Lemma 2.1 in the matrix case

For the reader’s convenience, in this subsection we give the proof of Lemma
2.1 in the matrix case: that is, the case when $d=2$. Accordingly, in this
subsection, $\mathcal{G}$ will be the group
$\mathbb{F}_{2}^{n_{1}}\otimes\mathbb{F}_{2}^{n_{2}}$ and $\mathcal{B}$ will
be the multiset that consists of all rank-1 matrices $u_{1}\otimes u_{2}$ with
$u_{1}\in\mathbb{F}_{2}^{n_{1}}$ and $u_{2}\in\mathbb{F}_{2}^{n_{2}}$, with
multiplicity. (As already remarked, the non-trivial multiplicity comes from
when $u_{1}$ or $u_{2}$ is zero.)

######  Lemma 2.3.

Let $\mathcal{B}^{\prime}\subset\mathcal{B}$ be such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Then there exist $k$
depending only on $\delta$, a subspace $U\subset\mathbb{F}_{2}^{n_{1}}$, and a
subspace $V_{u}\subset\mathbb{F}_{2}^{n_{2}}$ for each $u\in U$, such that all
these subspaces have codimension at most $k$, and such that every $u\otimes v$
with $u\in U,v\in V_{u}$ belongs to $16\mathcal{B}^{\prime}$. Moreover, we can
insist that all $V_{u}$ have the same codimension.

###### Proof.

For each $u\in\mathbb{F}_{2}^{n_{1}}$, let
$\mathcal{B}_{u}^{\prime}=\\{v\in\mathbb{F}_{2}^{n_{2}}:u\otimes
v\in\mathcal{B}^{\prime}\\}$ and let
$T=\\{u\in\mathbb{F}_{2}^{n_{1}}:|\mathcal{B}_{u}^{\prime}|\geq\frac{\delta}{2}2^{n_{2}}\\}$.
By averaging, we have that $|T|\geq\frac{\delta}{2}2^{n_{1}}$.

If $u\in T$, then $\mathcal{B}_{u}^{\prime}$ has density at least
$\frac{\delta}{2}$ in $\mathbb{F}_{2}^{n_{2}}$, so by Bogolyubov’s lemma (see
for example Proposition 4.39 of [8])
$4\mathcal{B}_{u}^{\prime}=2\mathcal{B}_{u}^{\prime}-2\mathcal{B}_{u}^{\prime}$
contains a subspace $W_{u}$ of codimension at most $k_{1}=k_{1}(\delta)$. By
Bogolyubov’s lemma again, there is a subspace $U$ of codimension at most
$k_{1}$ contained in $4T$. Let $u\in U$. Then pick $t_{1},t_{2},t_{3},t_{4}\in
T$ arbitrarily such that $u=t_{1}+t_{2}+t_{3}+t_{4}$ and set
$V_{u}=\bigcap_{i=1}^{4}W_{t_{i}}$. Note that $V_{u}$ has codimension at most
$4k_{1}$ for every $u\in U$. If $v\in V_{u}$, then $t_{i}\otimes v\in
4\mathcal{B}^{\prime}$ for $i=1,\dots,4$, therefore $u\otimes v\in
16\mathcal{B}^{\prime}$. Thus, we can take $k=4k_{1}$.

For the last assertion, note that we may replace $V_{u}$ with any subspace of
it, and we still have $u\otimes V_{u}\subset 16\mathcal{B}^{\prime}$. ∎

We shall now prove that we may take $Q=\bigcup_{u\in U}(u\otimes V_{u})$ in
Lemma 2.1.

######  Lemma 2.4.

There exists an absolute constant $\epsilon>0$ with the following property.
Let $U$ be a subspace of $\mathbb{F}_{2}^{n_{1}}$ and for each $u\in U$ let
$V_{u}$ be a subspace of $\mathbb{F}_{2}^{n_{2}}$ such that all these
subspaces have codimension at most $k$ and all the $V_{u}$ have the same
codimension. Let $Q$ be the multiset $\bigcup_{u\in U}(u\otimes V_{u})$. Then
the set of arrays $r\in\mathcal{G}$ with $r.q=0$ for at least
$(1-\epsilon)|Q|$ choices $q\in Q$ is contained in
$W_{12}+W_{1}\otimes\mathbb{F}_{2}^{n_{2}}+\mathbb{F}_{2}^{n_{1}}\otimes
W_{2}$ where
$W_{12}\subset\mathbb{F}_{2}^{n_{1}}\otimes\mathbb{F}_{2}^{n_{2}},W_{1}\subset\mathbb{F}_{2}^{n_{1}}$
and $W_{2}\subset\mathbb{F}_{2}^{n_{2}}$ are subspaces of dimension at most
$f(k)$.

Before we prove this lemma, we need to establish the following result. In the
statement, and in the rest of this section, we use the following convention
for the multiplication of arrays
$r\in\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{a+b}}$ and
$s\in\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{a}}$. Define
$rs\in\mathbb{F}_{2}^{n_{a+1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{a+b}}$ to
be the array with
$(rs)_{i_{a+1},\dots,i_{a+b}}=\sum_{j_{1},\dots,j_{a}}r_{j_{1},\dots,j_{a},i_{a+1},\dots,i_{a+b}}s_{j_{1},\dots,j_{a}}$.
Note that in the case when $r$ is a matrix and $s$ is a vector, this is not
quite the same as the standard convention since we sum over the first
coordinate of the matrix instead of the second. If $r$ and $s$ are arrays of
the same size, then we use the notation $r.s$ for the product of $r$ and $s$,
since then it coincides with the obvious notion of dot product, and it is
useful to think of it that way.

######  Lemma 2.5.

Let $U$ be a subspace of $\mathbb{F}_{2}^{n_{1}}$ and for each $u\in U$ let
$V_{u}$ be a subspace of $\mathbb{F}_{2}^{n_{2}}$ such that all these
subspaces have codimension at most $k$ and all the $V_{u}$ have the same
codimension. Let $Q=\bigcup_{u\in U}(u\otimes V_{u})$ and for $m=2^{k+3}$, let
$r_{1},\dots,r_{m}\in\mathcal{G}$ be such that for every $i\leq m$ there are
at least $\frac{3}{4}|Q|$ choices of $q\in Q$ such that $r_{i}.q=0$. Then
there exist $i\neq j$ such that $(r_{i}-r_{j})w=0$ for at least
$\rho(k)2^{n_{1}}$ choices $w\in\mathbb{F}_{2}^{n_{1}}$, for some positive
function $\rho(k)$. Thus, there exist $i\neq j$ such that $r_{i}-r_{j}$ has
rank at most $l(k)$.

###### Proof of Lemma 2.5.

For each $i$, there are at least $|U|/2$ choices of $u\in U$ such that
$r_{i}.(u\otimes v)=0$ for more than $|V_{u}|/2$ choices of $v\in V_{u}$. But
$r_{i}.(u\otimes v)=(r_{i}u).v$, so this implies that $r_{i}u\in
V_{u}^{\perp}$.

It follows that for at least $|U|/4$ choices of $u\in U$ we have $r_{i}u\in
V_{u}^{\perp}$ for at least $m/4$ choices of $i\leq m$. Since
$m/4>|V_{u}^{\perp}|$, for every such $u$ there exist $i\neq j$ with
$r_{i}u=r_{j}u$. Thus, for some $i\neq j$, there are at least
$\frac{|U|}{4m^{2}}$ choices of $u\in U$ with $r_{i}u=r_{j}u$. The result
follows. ∎

Lemma 2.5 reduces Lemma 2.4 to the following.

######  Lemma 2.6.

There exists an absolute constant $\epsilon^{\prime}>0$ with the following
property. Let $U$ be a subspace of $\mathbb{F}_{2}^{n_{1}}$ and for each $u\in
U$ let $V_{u}$ be a subspace of $\mathbb{F}_{2}^{n_{2}}$ such that all these
subspaces have codimension at most $k$ and all the $V_{u}$ have the same
codimension. Let $Q$ be the multiset $\bigcup_{u\in U}(u\otimes V_{u})$. Then
the set of arrays $r\in\mathcal{G}$ of rank at most $l$ such that $r.q=0$ for
at least $(1-\epsilon^{\prime})|Q|$ choices $q\in Q$ is contained in
$W_{1}\otimes\mathbb{F}_{2}^{n_{2}}+\mathbb{F}_{2}^{n_{1}}\otimes W_{2}$ where
$W_{1}\subset\mathbb{F}_{2}^{n_{1}}$ and $W_{2}\subset\mathbb{F}_{2}^{n_{2}}$
are subspaces of codimension at most $f(k,l)$.

Indeed, take $\epsilon^{\prime}$ as given by Lemma 2.6 and let
$\epsilon=\min(\epsilon^{\prime}/2,1/4)$. We claim that $\epsilon$ is suitable
for Lemma 2.4. By Lemma 2.5, we can find $x_{1},\dots,x_{m}\in\mathcal{G}$ ,
with $m\leq 2^{k+3}$, as follows. For every $i$, $x_{i}.q=0$ for at least
$(1-\epsilon)|Q|$ choices $q\in Q$, and if $r.q=0$ for at least
$(1-\epsilon)|Q|$ choices $q\in Q$, then $r-x_{i}$ has rank at most $g_{1}(k)$
for some $i\leq m$. But then $(r-x_{i}).q=0$ for at least
$(1-\epsilon^{\prime})|Q|$ choices $q\in Q$, and by Lemma 2.6, $r-x_{i}$ is
contained in $W_{1}\otimes\mathbb{F}_{2}^{n_{2}}+\mathbb{F}_{2}^{n_{1}}\otimes
W_{2}$ where $W_{1},W_{2}$ have codimension at most $g_{2}(k)$ and do not
depend on $r$. So we may take $W_{12}$ to be the span of all the $x_{i}$.

###### Proof of Lemma 2.6.

We shall prove that we can take $\epsilon^{\prime}$ to be $1/8$, $W_{1}$ to be
$U^{\perp}$ and $W_{2}$ to be a subspace that we define as follows. Let
$X=\\{x\in\mathbb{F}_{2}^{n_{2}}:x\in V_{u}^{\perp}\text{ for at least
}\frac{|U|}{10\cdot 2^{l}}\text{ choices }u\in U\\}$. Since
$|V_{u}^{\perp}|\leq 2^{k}$ for every $u\in U$, we have $|X|\leq\frac{|U|\cdot
2^{k}}{{|U|}/{10\cdot 2^{l}}}=10\cdot 2^{k+l}$. Let $W_{2}=\text{span}(X)$.

Now let $r$ be a matrix of rank at most $l$ such that $r.q=0$ for at least
$7|Q|/8$ choices of $q\in Q$. Then $ru\in V_{u}^{\perp}$ for at least $3|U|/4$
choices of $u\in U$. Since $r$ has rank at most $l$, we have
$r\in\mathbb{F}_{2}^{n_{1}}\otimes H_{2}(r)$ for some subspace
$H_{2}(r)\subset\mathbb{F}_{2}^{n_{2}}$ with $\dim(H_{2}(r))\leq l$. By
definition, for any $v\not\in W_{2}$, the number of $u\in U$ with $v\in
V_{u}^{\perp}$ is at most $\frac{|U|}{10\cdot 2^{l}}$. Since $|H_{2}(r)|\leq
2^{l}$ and $ru\in H_{2}(r)$ for every $u\in U$, the number of $u\in U$ with
$ru\in V_{u}^{\perp}\setminus W_{2}$ is at most $\frac{|U|}{10}$. It follows
that for more than $|U|/2$ choices $u\in U$ we have $ru\in W_{2}$. This in
fact implies that $ru\in W_{2}$ for all $u\in U$, which implies that $r\in
U^{\perp}\otimes\mathbb{F}_{2}^{n_{2}}+\mathbb{F}_{2}^{n_{1}}\otimes W_{2}$. ∎

###  2.2. The proof of Lemma 2.1 in the general case

It is convenient to introduce a few definitions.

######  Definition 2.7.

Let $k$ be a positive integer and let $\epsilon>0$. Let $Q$ be a multiset with
elements chosen from $\mathcal{G}$ (with arbitrary multiplicity). We say that
$Q$ is $(k,\alpha)$-_forcing_ if the set of all arrays $r\in\mathcal{G}$ with
$r.q=0$ for at least $\alpha|Q|$ choices $q\in Q$ is contained in a set of the
from $\sum_{I\subset[d],I\neq\emptyset}V_{I}\otimes\mathbb{F}_{2}^{I^{c}}$ for
some choice of subspaces $V_{I}\subset\mathbb{F}_{2}^{I}$ of dimension at most
$k$.

Note that the conclusion of Lemma 2.1 is that the multiset $Q$ is
$(f_{2}(d,\delta),1-f_{3}(d))$-forcing.

######  Definition 2.8.

We say that the hypothesis (H) holds for $d$ if the following is true. For
every $\delta>0$ there exist $f_{1}(d),f_{2}(d,\delta)$ and $f_{3}(d)>0$ such
that if $\mathcal{B}^{\prime}\subset\mathcal{B}$ is such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$, then there exists a multiset
$Q$, with elements chosen from $f_{1}(d)\mathcal{B}^{\prime}$, that is
$(f_{2}(d,\delta),1-f_{3}(d))$-forcing.

Hypothesis (H) is the one that really interests us, since if it holds for
every $d$ then Lemma 2.1 is proved. However, in order to get an induction to
work we shall need a slight strengthening that says that we can ask for the
elements of $Q$ to belong to a large subspace of a suitable form.

######  Definition 2.9.

We say that the hypothesis (H’) holds for $d$ if the following is true. For
every $\delta>0$ and every positive integer $l$ there exist
$f_{1}(d),f_{2}(d,\delta,l)$ and $f_{3}(d)>0$ such that if
$\mathcal{B}^{\prime}\subset\mathcal{B}$ is such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$, and for every non-empty
$I\subset[d]$, $L_{I}\subset\mathbb{F}_{2}^{I}$ is a subspace of codimension
at most $l$, then there exists a multiset $Q$, with elements chosen from
$(f_{1}(d)\mathcal{B}^{\prime})\cap\bigcap_{I}(L_{I}\otimes\mathbb{F}_{2}^{I^{c}})$,
that is $(f_{2}(d,\delta,l),1-f_{3}(d))$-forcing.

In what follows, we shall prove that if (H) holds for $d$, then so does (H’),
and that if (H’) holds for all $d^{\prime}<d$, then (H) holds for $d$. This
completes the proof since (H) holds for $d=1$. Indeed, if
$\mathcal{B}^{\prime}\subset\mathbb{F}_{2}^{n_{1}}$ has
$|\mathcal{B}^{\prime}|\geq\delta\cdot 2^{n_{1}}$, then by Bogolyubov’s lemma,
$4\mathcal{B}^{\prime}=2\mathcal{B}^{\prime}-2\mathcal{B}^{\prime}$ contains a
subspace $U\subset\mathbb{F}_{2}^{n_{1}}$ of codimension at most $g(\delta)$.
If $x.u=0$ for over half the elements of $U$, then the set of $u\in U$ with
$x.u=0$ is not contained in a proper subspace, so $x\in U^{\perp}$, which has
dimension at most $g(\delta)$. This implies that $U$ is
$(g(\delta),3/4)$-forcing.

The next few results are needed for technical reasons. The set introduced in
the next definition behaves well under certain algebraic operations, such as
intersecting with a dense subspace. It is a generalization of the set
$\bigcup_{u\in U}(u\otimes V_{u})$ used in the previous subsection.

######  Definition 2.10.

Suppose that we build a collection of subspaces as follows. We begin with a
subspace $U\subset\mathbb{F}_{2}^{n_{1}}$. Then for each $u_{1}\in U$ we take
a subspace $U_{u_{1}}\subset\mathbb{F}_{2}^{n_{2}}$, for each $u_{1}\in U$ and
$u_{2}\in U_{u_{1}}$ we take a subspace
$U_{u_{1},u_{2}}\subset\mathbb{F}_{2}^{n_{2}}$, and so on up to subspaces
$U_{u_{1},\dots,u_{d-1}}$. Now let $Q$ be the multiset that consists of all
tensors $u_{1}\otimes\dots\otimes u_{d}$ such that $u_{1}\in U,u_{2}\in
U_{u_{1}},\dots,u_{d}\in U_{u_{1},\dots,u_{d-1}}$. If all the subspaces in the
collection have codimension at most $l$, then we say that $Q$ is an _$l$
-system_.

######  Lemma 2.11.

Let $Q$ be an $l$-system and let $Q^{\prime}$ be a $l^{\prime}$-system. Then
$Q\cap Q^{\prime}$ contains an $(l+l^{\prime})$-system.

###### Proof.

Let $Q$ have spaces as in Definition 2.10 and let $Q^{\prime}$ have spaces
$U^{\prime}_{u^{\prime}_{1},\dots,u^{\prime}_{k-1}}$. We define an
$(l+l^{\prime})$-system $P$ contained in $Q\cap Q^{\prime}$ as follows. Let
$V=U\cap U^{\prime}$. Suppose we have defined $V_{v_{1},\dots,v_{j-1}}$ for
all $j\leq k$. Let $v_{1}\in V,v_{2}\in V_{v_{1}},\dots,v_{k-1}\in
V_{v_{1},\dots,v_{k-2}}$. We let
$V_{v_{1}\dots,v_{k-1}}=U_{v_{1}\dots,v_{k-1}}\cap
U^{\prime}_{v_{1}\dots,v_{k-1}}$. This is well-defined and has codimension at
most $l+l^{\prime}$ in $\mathbb{F}_{2}^{n_{k}}$. Let $P$ be the corresponding
$(l+l^{\prime})$-system. ∎

######  Lemma 2.12.

Let $\mathcal{B}^{\prime}\subset\mathcal{B}$ be a multiset such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Then there exists an
$f_{1}(d,\delta)$-system with elements chosen from
$f_{2}(d)\mathcal{B}^{\prime}$.

###### Proof.

The proof is by induction on $d$. The case $d=1$ is an easy application of
Bogolyubov’s lemma. Suppose that the lemma has been proved for all
$d^{\prime}<d$ and let $\mathcal{B}^{\prime}\subset\mathcal{B}$ be a multiset
such that $|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Let $\mathcal{D}$
be the multiset $\\{v_{2}\otimes\dots\otimes
v_{d}:v_{2}\in\mathbb{F}_{2}^{n_{2}},\dots,v_{d}\in\mathbb{F}_{2}^{n_{d}}\\}$.
For each $u\in\mathbb{F}_{2}^{n_{1}}$, let
$\mathcal{B}_{u}^{\prime}=\\{s\in\mathcal{D}:u\otimes
s\in\mathcal{B}^{\prime}\\}$ and let
$T=\\{u\in\mathbb{F}_{2}^{n_{1}}:|\mathcal{B}_{u}^{\prime}|\geq\frac{\delta}{2}|\mathcal{D}|\\}$.
By averaging, we have that $|T|\geq\frac{\delta}{2}2^{n_{1}}$. Now by the
induction hypothesis, for every $t\in T$, there exists an
$f_{1}(d-1,\delta/2)$-system $P_{t}$ in
$\mathbb{F}_{2}^{n_{2}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d}}$ (the
definition is analogous to the definition of a system in
$\mathbb{F}_{2}^{n_{1}}\otimes\dots\mathbb{F}_{2}^{n_{d}}$), which is
contained in $f_{2}(d-1)\mathcal{B}^{\prime}_{t}$. By Bogolyubov’s lemma,
$4T=2T-2T$ contains a subspace $U\subset\mathbb{F}_{2}^{n_{1}}$ of codimension
at most $g_{1}(\delta)$. For each $u\in U$, write $u=t_{1}+t_{2}+t_{3}+t_{4}$
arbitrarily, and let $Q_{u}=P_{t_{1}}\cap P_{t_{2}}\cap P_{t_{3}}\cap
P_{t_{4}}$, which is a $4f_{1}(d-1,\delta/2)$-system, by Lemma 2.11. Now
$Q=\bigcup_{u\in U}(u\otimes Q_{u})$ is an $f_{1}(d,\delta)$-system provided
that $f_{1}(d,\delta)\geq\max(4f_{1}(d-1,\delta/2),g_{1}(\delta))$. Moreover,
for any $u\in U,s\in Q_{u}$, we have $u\otimes s\in
4f_{2}(d-1)\mathcal{B}^{\prime}$, so $Q$ is suitable provided that
$f_{2}(d)\geq 4f_{2}(d-1)$. ∎

The next lemma is the last ingredient needed to prove that (H’) follows from
(H).

######  Lemma 2.13.

Let $Q$ be a $k$-system, and for each non-empty $I\subset[d]$ let
$L_{I}\subset\mathbb{F}_{2}^{I}$ be a subspace of codimension at most $l$. Let
$T=\bigcap_{I}(L_{I}\otimes\mathbb{F}_{2}^{I^{c}})$. Then $Q\cap T$ contains
an $f(d,k,l)$-system.

###### Proof.

Let the spaces of $Q$ be $U_{u_{1},\dots,u_{j-1}}$. It suffices to prove that
for every $1\leq j\leq d$, and every $u_{1}\in U,\ \dots,\ u_{j-1}\in
U_{u_{1},\dots,u_{j-2}}$, the codimension of $(u_{1}\otimes\dots\otimes
u_{j-1}\otimes U_{u_{1},\dots,u_{j-1}})\cap\bigcap_{I\subset[j],j\in
I}(L_{I}\otimes\mathbb{F}_{2}^{[j]\setminus I})$ in $u_{1}\otimes\dots\otimes
u_{j-1}\otimes U_{u_{1},\dots,u_{j-1}}$ is at most $g_{1}(d,l)$. Thus, it
suffices to prove that for every $I\subset[j]$ with $j\in I$, the codimension
of $(u_{1}\otimes\dots\otimes u_{j-1}\otimes
U_{u_{1},\dots,u_{j-1}})\cap(L_{I}\otimes\mathbb{F}_{2}^{[j]\setminus I})$ in
$u_{1}\otimes\dots\otimes u_{j-1}\otimes U_{u_{1},\dots,u_{j-1}}$ is at most
$g_{2}(l)$. But this is equivalent to the statement that
$\big{(}(\bigotimes_{i\in I\setminus\\{j\\}}u_{i})\otimes
U_{u_{1},\dots,u_{j-1}}\big{)}\cap L_{I}$ has codimension at most $g_{2}(l)$
in $(\bigotimes_{i\in I\setminus\\{j\\}}u_{i})\otimes
U_{u_{1},\dots,u_{j-1}}$, which clearly holds with $g_{2}(l)=l$. ∎

######  Lemma 2.14.

If (H) holds for $d$, then so does (H’).

###### Proof.

Let $\mathcal{B}^{\prime}$ and $L_{I}$ be given as in (H’). By Lemma 2.12, we
can choose a $g_{1}(d,\delta)$-system in $g_{2}(d)\mathcal{B}^{\prime}$. Thus,
by Lemma 2.13,
$(g_{2}(d)\mathcal{B}^{\prime})\cap\bigcap_{I}(L_{I}\otimes\mathbb{F}_{2}^{I^{c}})$
contains a $g_{3}(d,\delta,l)$-system $\mathcal{B}^{\prime\prime}$. Note that
$\mathcal{B}^{\prime\prime}\subset\mathcal{B}$ with
$|\mathcal{B}^{\prime\prime}|\geq g_{4}(d,\delta,l)|\mathcal{B}|$, where
$g_{4}(d,\delta,l)>0$. By hypothesis (H) applied to
$\mathcal{B}^{\prime\prime}$ in place of $\mathcal{B}^{\prime}$, it follows
that there is a multiset $Q$, with elements chosen from
$g_{5}(d)\mathcal{B}^{\prime\prime}\subset
g_{5}(d)g_{2}(d)\mathcal{B}^{\prime}$, which is
$(g_{6}(d,\delta,l),1-g_{7}(d))$-forcing. Now
$Q\subset\bigcap_{I}(L_{I}\otimes\mathbb{F}_{2}^{I^{c}})$, finishing the
proof. ∎

The next result generalizes Lemma 2.5. To state it, we need to find the
equivalent of low-rank matrices in the higher dimensional case. The definition
we use is essentially the same as that of the _partition rank_ of a tensor
(see for example [7] for a discussion of this notion). Indeed, if a tensor has
partition rank at most $k$, then it is $k$-degenerate (in the sense of the
next definition), and conversely if a tensor is $k$-degenerate, then it has
partition rank is at most $2^{d-1}k$. The second author has shown that the
partition rank is also related to the _analytic rank_ of a tensor [4], which
we do not define here (but again see [7]), with a tower-type dependence,
improving on the previously known Ackermann dependence. In this section we use
a very similar argument, but since we do not care about bounds, we present it
in qualitative form for ease of reading and for the sake of completeness.

######  Definition 2.15.

Let $k$ be a positive integer. We say that $r\in\mathcal{G}$ is
$k$-_degenerate_ if there is a collection of subspaces
$H_{I}\subset\mathbb{F}_{2}^{I}$, one for each non-empty proper subset
$I\subset[d]$ and each one of dimension at most $k$, such that
$r\in\sum_{I\subset[d-1],I\neq\emptyset}H_{I}\otimes H_{I^{c}}$.

If $r\in H_{I}\otimes\mathbb{F}_{2}^{I^{c}}$ with $\dim(H_{I})\leq k$, then
$r\in H_{I}\otimes H_{I^{c}}$ for some
$H_{I^{c}}\subset\mathbb{F}_{2}^{I^{c}}$ of dimension at most $k$. (This
follows by writing $r$ as $\sum_{j\leq m}s_{j}\otimes t_{j}$ with
$\\{s_{j}\\}$ a basis for $H_{I}$ and letting $H_{I^{c}}$ be the span of all
$t_{j}$.) Thus, $r$ is $k$-degenerate if and only if we have the apparently
weaker condition that
$r\in\sum_{I\subset[d-1],I\neq\emptyset}H_{I}\otimes\mathbb{F}_{2}^{I^{c}}$
for some collection of subspaces $H_{I}\subset\mathbb{F}_{2}^{I}$ of dimension
at most $k$, or equivalently the condition that
$r\in\sum_{I\subset[d-1],I\neq\emptyset}\mathbb{F}_{2}^{I}\otimes H_{I^{c}}$
for some collection of subspaces $H_{I^{c}}\subset\mathbb{F}_{2}^{I^{c}}$ of
dimension at most $k$.

######  Lemma 2.16.

Suppose that (H) holds for $d-1$. Let $\mathcal{D}$ be the multiset
$\\{u_{1}\otimes\dots\otimes
u_{d-1}:u_{1}\in\mathbb{F}_{2}^{n_{1}},\dots,u_{d-1}\in\mathbb{F}_{2}^{n_{d-1}}\\}$.

  1. (i)

Let $\mathcal{D}^{\prime}\subset\mathcal{D}$, and for each
$t\in\mathcal{D}^{\prime}$, let $U_{t}$ be a subspace of
$\mathbb{F}_{2}^{n_{d}}$ of codimension at most $k$ with the codimensions of
the $U_{t}$ all equal. Let $Q$ be the multiset
$\bigcup_{t\in\mathcal{D}^{\prime}}(t\otimes U_{t})$. If $m=2^{k+3}$, and
$r_{1},\dots,r_{m}\in\mathcal{G}$ have the property that for every $i$,
$r_{i}.q=0$ holds for at least $\frac{3}{4}|Q|$ choices of $q\in Q$, then
there exist $i\neq j$ such that $(r_{i}-r_{j})(v_{1}\otimes\dots\otimes
v_{d-1})=0$ for at least $f_{1}(k)|\mathcal{D}^{\prime}|$ choices of
$v_{1}\otimes\dots\otimes v_{d-1}\in\mathcal{D}^{\prime}$, where $f_{1}(k)>0$
depends only on $k$.

  2. (ii)

Let $c>0$ and let $r\in\mathcal{G}$ be such that $r(v_{1}\otimes\dots\otimes
v_{d-1})=0$ for at least $c|\mathcal{D}|$ choices $v_{1}\otimes\dots\otimes
v_{d-1}\in\mathcal{D}$. Then $r$ is $f_{2}(d,c)$-degenerate.

  3. (iii)

Let $\delta>0$ and let $\mathcal{B}^{\prime}\subset\mathcal{B}$ be such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Then there exists $Q\subset
4\mathcal{B}^{\prime}$ with the following property. If $m\geq f_{3}(\delta)$
and $r_{1},\dots,r_{m}\in\mathcal{G}$ are such that for each $i$, $r_{i}.q=0$
for at least $\frac{3}{4}|Q|$ choices $q\in Q$, then there exist $i\neq j$
such that $r_{i}-r_{j}$ is $f_{4}(d,\delta)$-degenerate.

  4. (iv)

Let $\delta>0$ and let $\mathcal{B}^{\prime}\subset\mathcal{B}$ be such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Then there exist $Q\subset
4\mathcal{B}^{\prime}$ and a subspace $V_{[d]}\subset\mathbb{F}_{2}^{[d]}$ of
dimension at most $f_{3}(\delta)$ with the following property. Any array $r$
with $r.q=0$ for at least $\frac{3}{4}|Q|$ choices $q\in Q$ can be written as
$r=x+y$ where $x\in V_{[d]}$ and $y$ is $f_{4}(d,\delta)$-degenerate.

###### Proof.

  1. (i)

By averaging, for every $i\leq m$ there are at least
$|\mathcal{D}^{\prime}|/2$ choices of $t\in\mathcal{D}^{\prime}$ such that
$r_{i}.(t\otimes u)=0$ for more than half the $u\in U_{t}$. But
$r_{i}.(t\otimes u)=(r_{i}t).u$, so for these $t$ we have that $r_{i}t\in
U_{t}^{\perp}$. By further averaging, it follows that for at least
$|\mathcal{D}^{\prime}|/4$ choices of $t\in\mathcal{D}^{\prime}$ we have that
$r_{i}t\in U_{t}^{\perp}$ for at least $m/4$ choices of $i\leq m$. Since
$m/4>|U_{t}^{\perp}|$, for every such $t$, there exist $i\neq j$ with
$r_{i}t=r_{j}t$. Thus, for some $i\neq j$, there are at least
$\frac{|\mathcal{D}^{\prime}|}{4m^{2}}$ choices of $t\in\mathcal{D}^{\prime}$
with $r_{i}t=r_{j}t$, which implies the statement we wish to prove.

  2. (ii)

Write $r=\sum_{i}s_{i}\otimes w_{i}$ where
$s_{i}\in\mathbb{F}_{2}^{n_{1}}\otimes\dots\otimes\mathbb{F}_{2}^{n_{d-1}}$
and $\\{w_{i}\\}$ is a basis for $\mathbb{F}_{2}^{n_{d}}$. Note that
$r(v_{1}\otimes\dots\otimes v_{d-1})=0$ if and only if
$s_{i}.(v_{1}\otimes\dots\otimes v_{d-1})=0$ for every $i$. Let
$\mathcal{D}^{\prime}$ be the multiset consisting of all
$v_{1}\otimes\dots\otimes v_{d-1}$ with $s_{i}.(v_{1}\otimes\dots\otimes
v_{d-1})=0$ for every $i$. By assumption, $|\mathcal{D}^{\prime}|\geq
c|\mathcal{D}|$. Since (H) holds for $d-1$, there exists a multiset $Q$, with
elements chosen from $g_{1}(d)\mathcal{D}^{\prime}$, which is
$(g_{2}(d,c),1-g_{3}(d))$-forcing. Since $s_{i}.q=0$ for every $q\in Q$, it
follows that there exist subspaces $V_{I}\subset\mathbb{F}_{2}^{I}$ for every
$I\subset[d-1],I\neq\emptyset$, of dimension at most $g_{2}(d,c)$ such that
$s_{i}\in\sum_{I}V_{I}\otimes\mathbb{F}_{2}^{[d-1]\setminus I}$ for all $i$.
In particular,
$r\in\sum_{I\subset[d-1],I\neq\emptyset}V_{I}\otimes\mathbb{F}_{2}^{I^{c}}$.
Thus, $r$ is $g_{2}(d,c)$-degenerate.

  3. (iii)

Let $\mathcal{D}^{\prime}=\\{t\in\mathcal{D}:t\otimes
u\in\mathcal{B}^{\prime}\text{ for at least }\frac{\delta}{2}2^{n_{d}}\text{
choices }u\in\mathbb{F}_{2}^{n_{d}}\\}$. Clearly, we have
$|\mathcal{D}^{\prime}|\geq\frac{\delta}{2}|\mathcal{D}|$. Moreover, by
Bogolyubov’s lemma, for every $t\in\mathcal{D}^{\prime}$, there exists a
subspace $U_{t}\subset\mathbb{F}_{2}^{n_{d}}$ of codimension at most
$g_{4}(\delta)$ such that $t\otimes U_{t}\subset 4\mathcal{B}^{\prime}$. After
passing to suitable subspaces, we may assume that all $U_{t}$ have the same
codimension. Now let $Q=\bigcup_{t\in\mathcal{D}^{\prime}}(t\otimes U_{t})$.
By (i), if $f_{3}(\delta)\geq 2^{g_{4}(\delta)+3}$, then there exist $i\neq j$
such that $(r_{i}-r_{j})t=0$ for at least
$g_{5}(\delta)|\mathcal{D}^{\prime}|$ choices $t\in\mathcal{D}^{\prime}$
(where $g_{5}(\delta)>0$) and therefore also for at least
$g_{6}(\delta)|\mathcal{D}|$ choices $t\in\mathcal{D}$ (where
$g_{6}(\delta)>0$). By (ii), it follows that $r_{i}-r_{j}$ is
$g_{7}(d,\delta)$-degenerate.

  4. (iv)

Choose $Q$ as in (iii) and let $r_{1},\dots,r_{m}$ be a maximal set such that
for all $i$ we have $r_{i}.q=0$ for at least $\frac{3}{4}|Q|$ choices $q\in
Q$, and for all $i\neq j$, $r_{i}-r_{j}$ is not $f_{4}(d,\delta)$-degenerate.
Then, by (iii), we have $m<f_{3}(\delta)$. Let $V_{[d]}$ be the span of all
the $r_{i}$. The result follows by the maximality of
$\\{r_{1},\dots,r_{m}\\}$.

∎

The next lemma is the key step to complete the proof of Lemma 2.1. In order to
state it, we need to introduce a total ordering $\prec$ of the non-empty
subsets of $[d-1]$. It does not matter exactly what the ordering is, but we
require it to have the property that if $J\subsetneq I$ then $J\prec I$.

To understand the point of the next lemma, observe that we take an array $r$
that belongs to the sum of a certain set of subspaces, some of which depend on
$r$, and we show, using the hypothesis that $r.q=0$ for almost all $q\in Q$,
that it is contained in a similar sum, but with the subspace corresponding to
$I^{c}$ no longer depending on $r$. By applying this lemma repeatedly, we
shall remove all dependence on $r$ from the right-hand side.

######  Lemma 2.17.

Suppose that (H’) holds for every $d^{\prime}<d$. Let $\delta>0$ and let
$\mathcal{B}^{\prime}\subset\mathcal{B}$ be such that
$|\mathcal{B}^{\prime}|\geq\delta|\mathcal{B}|$. Let
$I\subset[d-1],I\neq\emptyset$ and for each $J\prec I$ let
$W_{J}\subset\mathbb{F}_{2}^{J},W_{J^{c}}\subset\mathbb{F}_{2}^{J^{c}}$ be
subspaces of dimension at most $k$. In addition, let
$W_{[d]}\subset\mathbb{F}_{2}^{[d]}$ be a subspace of dimension at most $k$.
Then there exists a multiset $Q$ with elements chosen from
$f_{1}(d)\mathcal{B}^{\prime}$ with the following property. Any array

$r\in W_{[d]}+\sum_{J\prec
I}(W_{J}\otimes\mathbb{F}_{2}^{J^{c}}+\mathbb{F}_{2}^{J}\otimes
W_{J^{c}})+\sum_{J\succeq I}\mathbb{F}_{2}^{J}\otimes H_{J^{c}}(r)$

with $\dim(H_{J^{c}}(r))\leq k$ and the property that $r.q=0$ for at least
$(1-f_{2}(d))|Q|$ choices $q\in Q$ is contained in a subspace

$W_{[d]}+\sum_{J\preceq
I}(U_{J}\otimes\mathbb{F}_{2}^{J^{c}}+\mathbb{F}_{2}^{J}\otimes
U_{J^{c}})+\sum_{J\succ I}\mathbb{F}_{2}^{J}\otimes K_{J^{c}}(r)$

for some
$U_{J}\subset\mathbb{F}_{2}^{J},U_{J^{c}}\subset\mathbb{F}_{2}^{J^{c}}$ not
depending on $r$ and some $K_{J^{c}}(r)\subset\mathbb{F}_{2}^{J^{c}}$ possibly
depending on $r$, all of dimension at most $f_{3}(d,\delta,k)$.

###### Proof.

After reordering if necessary, we may assume that $I=[a]$ for some $1\leq
a\leq d-1$. The next claim gives us a multiset $Q$ with certain properties.
Once we have it, we shall use those properties to show that $Q$ satisfies the
conclusion of the lemma.

_Claim._ There exist a multiset $Q^{\prime}$ with elements chosen from
$\bigcap_{J\subset I,J\neq
I,J\neq\emptyset}(W_{J}^{\perp}\otimes\mathbb{F}_{2}^{I\setminus J})$ which is
$(h_{1}(d,\delta,k),1-h_{2}(d))$-forcing (with $h_{2}(d)>0$), and for each
$s\in Q^{\prime}$, a multiset $Q_{s}$ with elements chosen from
$\mathbb{F}_{2}^{I^{c}}$ which is $(h_{3}(d,\delta),1-h_{4}(d))$-forcing (with
$h_{4}(d)>0$) such that $\max_{s\in Q^{\prime}}|Q_{s}|\leq 2\min_{s\in
Q^{\prime}}|Q_{s}|$ and setting $Q$ to be the multiset $\\{s\otimes t:s\in
Q^{\prime},t\in Q_{s}\\}=\cup_{s\in Q^{\prime}}(s\otimes Q_{s})$, the elements
of $Q$ belong to $h_{5}(d)\mathcal{B}^{\prime}$

_Proof of Claim._ Let $\mathcal{C}$ be the multiset
$\\{u_{1}\otimes\dots\otimes u_{a}:u_{i}\in\mathbb{F}_{2}^{n_{i}}\\}$ and let
$\mathcal{D}$ be the multiset $\\{u_{a+1}\otimes\dots\otimes
u_{d}:u_{i}\in\mathbb{F}_{2}^{n_{i}}\\}$. For each $s\in\mathcal{C}$, let
$\mathcal{D}_{s}=\\{t\in\mathcal{D}:s\otimes t\in\mathcal{B}^{\prime}\\}$.
Also, let
$\mathcal{C}^{\prime}=\\{s\in\mathcal{C}:|\mathcal{D}_{s}|\geq\frac{\delta}{2}|\mathcal{D}|\\}$.
Clearly, $|\mathcal{C}^{\prime}|\geq\frac{\delta}{2}|\mathcal{C}|$. By Lemma
2.12, for every $s\in\mathcal{C}^{\prime}$ there exists a
$g_{1}(d,\delta)$-system $R_{s}$ in $g_{2}(d)\mathcal{D}_{s}$. By (H’) applied
to $a$, there exists a multiset $Q^{\prime}$ with elements chosen from
$(g_{3}(d)\mathcal{C}^{\prime})\cap\bigcap_{J\subset I,J\neq
I,J\neq\emptyset}(W_{J}^{\perp}\otimes\mathbb{F}_{2}^{I\setminus J})$ which is
$(g_{4}(d,\delta,k),1-g_{5}(d))$-forcing for some $g_{5}(d)>0$. For every
$s\in Q^{\prime}$, choose $s_{1},\dots,s_{l}\in\mathcal{C}^{\prime}$ with
$l\leq g_{3}(d)$ such that $s=s_{1}+\dots+s_{l}$, and let
$P_{s}=\bigcap_{i\leq l}R_{s}$. By Lemma 2.11, $P_{s}$ contains a
$g_{6}(d,\delta)$-system, therefore $|P_{s}|\geq g_{7}(d,\delta)|\mathcal{D}|$
for some $g_{7}(d,\delta)>0$. By (H) for $d-a$, for every $s\in Q^{\prime}$
there exists a multiset $Q_{s}$ with elements chosen from $g_{8}(d)P_{s}$
which is $(g_{9}(d,\delta),1-g_{10}(d))$-forcing for some $g_{10}(d)>0$.
Notice that if we repeat every element of $Q_{s}$ the same number of times,
then the multiset we obtain is still $(g_{9}(d,\delta),1-g_{10}(d))$-forcing,
so we may assume that $\max_{s\in Q^{\prime}}|Q_{s}|\leq 2\min_{s\in
Q^{\prime}}|Q_{s}|$. Define $Q=\\{s\otimes t:s\in Q^{\prime},t\in
Q_{s}\\}=\bigcup_{s\in Q^{\prime}}(s\otimes Q_{s})$. Note that as
$R_{s}\subset g_{2}(d)\mathcal{D}_{s}$ for all $s\in\mathcal{C}^{\prime}$, we
have $s\otimes R_{s}\subset g_{2}(d)\mathcal{B}^{\prime}$ for all
$s\in\mathcal{C}^{\prime}$. But the elements of $Q^{\prime}$ are chosen from
$g_{3}(d)\mathcal{C}^{\prime}$, so $s\otimes P_{s}\subset
g_{3}(d)g_{2}(d)\mathcal{B}^{\prime}$ for all $s\in Q^{\prime}$. Finally, the
elements of $Q_{s}$ are chosen from $g_{8}(d)P_{s}$, so the elements of
$s\otimes Q_{s}$ are chosen from
$g_{8}(d)g_{3}(d)g_{2}(d)\mathcal{B}^{\prime}$ for every $s\in Q^{\prime}$.
This completes the proof of the claim.

Now let us show that $Q$ does indeed satisfy the conclusion of the lemma.
Since for every $s\in Q^{\prime}$, $Q_{s}$ is
$(h_{3}(d,\delta),1-h_{4}(d))$-forcing, there exist subspaces
$V_{J}(s)\subset\mathbb{F}_{2}^{J}$ for every $J\subset I^{c},J\neq\emptyset$,
with dimension at most $h_{3}(d,\delta)$ such that the set of arrays
$t\in\mathbb{F}_{2}^{I^{c}}$ with $t.q=0$ for at least $(1-h_{4}(d))|Q_{s}|$
choices $q\in Q_{s}$ is contained in $\sum_{J\subset
I^{c},J\neq\emptyset}V_{J}(s)\otimes\mathbb{F}_{2}^{I^{c}\setminus J}$. Let
$f_{2}(d)=\frac{1}{4}h_{2}(d)h_{4}(d)$. Now if $r\in\mathcal{G}$ has $r.q=0$
for at least $(1-f_{2}(d))|Q|$ choices $q\in Q$, then by averaging, for at
least $(1-\frac{1}{2}h_{2}(d))|Q^{\prime}|$ choices $s\in Q^{\prime}$, we have
$r.(s\otimes t)=0$ for at least $(1-h_{4}(d))|Q_{s}|$ choices $t\in Q_{s}$.
Therefore (noting that $r.(s\otimes t)=(rs).t$), $rs\in\sum_{J\subset
I^{c},J\neq\emptyset}V_{J}(s)\otimes\mathbb{F}_{2}^{I^{c}\setminus J}$ for at
least $(1-\frac{1}{2}h_{2}(d))|Q^{\prime}|$ choices $s\in Q^{\prime}$.

Now let $g_{11}(d,k)=\frac{h_{2}(d)}{2\cdot 2^{k}}$ and
$g_{12}(d,\delta,k)=h_{3}(d,\delta)+2^{d+1}k$. Let $X$ be the subset of
$\mathbb{F}_{2}^{I^{c}}$ consisting of those arrays $x$ such that for at least
$g_{11}(d,k)|Q^{\prime}|$ choices $s\in Q^{\prime}$, there exists some
$t(s)\in V_{I^{c}}(s)+\sum_{J\subset I,J\neq I}((\mathbb{F}_{2}^{J}\otimes
W_{J^{c}})s)$ for which $x-t(s)$ is $g_{12}(d,\delta,k)$-degenerate. (Here and
below, for a subspace $L\subset\mathcal{G}$ and an array
$s\in\mathbb{F}_{2}^{I}$, we write $Ls$ for the subspace $\\{rs:r\in
L\\}\subset\mathbb{F}_{2}^{I^{c}}$.) Choose a maximal subset
$\\{x_{1},\dots,x_{m}\\}\subset X$ such that no $x_{i}-x_{j}$ with $i\neq j$
is $2g_{12}(d,\delta,k)$-degenerate. Then there do not exist $i\neq j$, $s\in
Q^{\prime}$ and $t\in V_{I^{c}}(s)+\sum_{J\subset I,J\neq
I}((\mathbb{F}_{2}^{J}\otimes W_{J^{c}})s)$ with $x_{i}-t$ and $x_{j}-t$ both
$g_{12}(d,\delta,k)$-degenerate. It follows, by the definition of $X$ and the
fact that the dimension of $V_{I^{c}}(s)+\sum_{J\subset I,J\neq
I}((\mathbb{F}_{2}^{J}\otimes W_{J^{c}})s)$ is at most
$h_{3}(d,\delta)+2^{d}k$, that $mg_{11}(d,k)|Q^{\prime}|\leq|Q^{\prime}|\cdot
2^{h_{3}(d,\delta)+2^{d}k}$, and therefore that $m\leq g_{13}(d,\delta,k)$.
Thus, there exists a set $Y\subset X$ of size at most $g_{13}(d,\delta,k)$
such that for any $x\in X$, there exists some $y\in Y$ such that $x-y$ is
$2g_{12}(d,\delta,k)$-degenerate. Let $Z=\text{span}(Y)$. Then $\dim(Z)\leq
g_{13}(d,\delta,k)$, and for every $x\in X$ there is some $z\in Z$ such that
$x-z$ is $2g_{12}(d,\delta,k)$-degenerate.

Let $r\in W_{[d]}+\sum_{J\prec
I}(W_{J}\otimes\mathbb{F}_{2}^{J^{c}}+\mathbb{F}_{2}^{J}\otimes
W_{J^{c}})+\sum_{J\succeq I}\mathbb{F}_{2}^{J}\otimes H_{J^{c}}(r)$ with
$\dim(H_{J^{c}}(r))\leq k$ and the property that $r.q=0$ for at least
$(1-f_{2}(d))|Q|$ choices $q\in Q$. Let $Q^{\prime}(r)$ be the submultiset of
$Q^{\prime}$ consisting of those $s\in Q^{\prime}$ for which
$rs\in\sum_{J\subset
I^{c},J\neq\emptyset}V_{J}(s)\otimes\mathbb{F}_{2}^{I^{c}\setminus J}$. As we
have seen two paragraphs above,
$|Q^{\prime}(r)|\geq(1-\frac{1}{2}h_{2}(d))|Q^{\prime}|$.

Note that we can write $r=r_{1}+r_{2}+r_{3}+r_{4}$ where
$r_{1}\in\sum_{J\subset I,J\neq
I,J\neq\emptyset}W_{J}\otimes\mathbb{F}_{2}^{J^{c}}$, $r_{2}\in\sum_{J\prec
I,J\not\subset I}(W_{J}\otimes\mathbb{F}_{2}^{J^{c}}+\mathbb{F}_{2}^{J}\otimes
W_{J^{c}})+\sum_{J\succ I}\mathbb{F}_{2}^{J}\otimes H_{J^{c}}(r)$, $r_{3}\in
W_{[d]}+\sum_{J\subset I,J\neq I,J\neq\emptyset}\mathbb{F}_{2}^{J}\otimes
W_{J^{c}}$ and $r_{4}\in\mathbb{F}_{2}^{I}\otimes H_{I^{c}}(r)$. Since the
elements of $Q^{\prime}$ belong to $\bigcap_{J\subset I,J\neq
I,J\neq\emptyset}(W_{J}^{\perp}\otimes\mathbb{F}_{2}^{I\setminus J})$, we have
$r_{1}s=0$ for every $s\in Q^{\prime}$. Since
$\dim(W_{J}),\dim(W_{J^{c}}),\dim(H_{J^{c}}(r))\leq k$, $r_{2}s$ is
$2^{d+1}k$-degenerate. Also, $r_{3}s\in\sum_{J\subset I,J\neq
I}((\mathbb{F}_{2}^{J}\otimes W_{J^{c}})s)$. It follows that for every $s\in
Q^{\prime}(r)$, there exists some $t(s)\in V_{I^{c}}(s)+\sum_{J\subset I,J\neq
I}((\mathbb{F}_{2}^{J}\otimes W_{J^{c}})s)$ such that $r_{4}s-t(s)$ is
$g_{12}(d,\delta,k)=(h_{3}(d,\delta)+2^{d+1}k)$-degenerate (we have used that
$\dim(V_{J}(s))\leq h_{3}(d,\delta)$). In particular, if $t\not\in X$, then
the number of choices $s\in Q^{\prime}(r)$ for which $r_{4}s=t$ is at most
$g_{11}(d,\delta,k)|Q^{\prime}|$. On the other hand, notice that $r_{4}s\in
H_{I^{c}}(r)$ for every $s\in Q^{\prime}$. Since $|H_{I^{c}}(r)|\leq 2^{k}$,
it follows that $r_{4}s\in X$ for at least
$|Q^{\prime}(r)|-2^{k}g_{11}(d,\delta,k)|Q^{\prime}|=|Q^{\prime}(r)|-\frac{1}{2}h_{2}(d)|Q^{\prime}|\geq(1-h_{2}(d))|Q^{\prime}|$
choices $s\in Q^{\prime}$.

Let $X(r)=X\cap H_{I^{c}}(r)$. Let $t_{1},\dots,t_{\alpha}$ be a maximal
linearly independent subset of $X(r)$ and extend it to a basis
$t_{1},\dots,t_{\alpha},t^{\prime}_{1},\dots,t^{\prime}_{\beta}$ for
$H_{I^{c}}(r)$. Now if a linear combination of
$t_{1},\dots,t_{\alpha},t^{\prime}_{1},\dots,t^{\prime}_{\beta}$ is in $X$,
then the coefficients of $t^{\prime}_{1},\dots,t^{\prime}_{\beta}$ are all
zero. Write $r_{4}=\sum_{i\leq\alpha}s_{i}\otimes
t_{i}+\sum_{j\leq\beta}s^{\prime}_{j}\otimes t^{\prime}_{j}$ for some
$s_{i},s^{\prime}_{j}\in\mathbb{F}_{2}^{I}$. Since $r_{4}q\in X$ for at least
$(1-h_{2}(d))|Q^{\prime}|$ choices $q\in Q^{\prime}$, we have, for all $j$,
that $s^{\prime}_{j}.q=0$ for at least $(1-h_{2}(d))|Q^{\prime}|$ choices
$q\in Q^{\prime}$. Thus, as $Q^{\prime}$ is
$(h_{1}(d,\delta,k),1-h_{2}(d))$-forcing, there exist subspaces
$L_{J}\subset\mathbb{F}_{2}^{J}$ ($J\subset I,J\neq\emptyset$), not depending
on $r$ and of dimension at most $h_{1}(d,\delta,k)$, such that
$s^{\prime}_{j}\in\sum_{J\subset
I,J\neq\emptyset}L_{J}\otimes\mathbb{F}_{2}^{I\setminus J}$ for all $j$. Thus,
$r_{4}\in\sum_{i\leq\alpha}s_{i}\otimes t_{i}+\sum_{J\subset
I,J\neq\emptyset}L_{J}\otimes\mathbb{F}_{2}^{J^{c}}$. Moreover, for every
$i\leq\alpha$, we have $t_{i}\in X$, so there exist $z_{i}\in Z$ such that
$t_{i}-z_{i}$ is $2g_{12}(d,\delta,k)$-degenerate. It follows that
$r_{4}\in\mathbb{F}_{2}^{I}\otimes Z+\sum_{J\supset I,J\neq
I,J\subset[d-1]}\mathbb{F}_{2}^{J}\otimes K^{\prime}_{J^{c}}(r)+\sum_{J\subset
I,J\neq\emptyset}L_{J}\otimes\mathbb{F}_{2}^{J^{c}}$ for some
$K^{\prime}_{J^{c}}(r)\subset\mathbb{F}_{2}^{J^{c}}$ of dimension at most
$\alpha\cdot 2g_{12}(d,\delta,k)\leq 2^{k}\cdot 2g_{12}(d,\delta,k)$. This
finishes the proof of the lemma. ∎

We are now in a position to complete the proof of Lemma 2.1.

###### Proof of Lemma 2.1.

As remarked earlier, it suffices to prove that (H) holds for all $d$. But (H)
implies (H’), and (H) holds for $d=1$, therefore it suffices to prove,
assuming that (H’) holds for all $d^{\prime}<d$, that (H) holds for $d$.

Let $\mathcal{B}^{\prime}$ given as in the definition of (H). By Lemma 2.16
(iv), there exist $Q_{\emptyset}\subset 4\mathcal{B}^{\prime}$ and
$V_{[d]}\subset\mathbb{F}_{2}^{[d]}$ of dimension at most $g_{1}(\delta)$ such
that if $r.q=0$ for at least $\frac{3}{4}|Q_{\emptyset}|$ choices $q\in
Q_{\emptyset}$, then $r$ can be written as $r=x+y$, where $x\in V_{[d]}$ and
$y$ is $g_{2}(d,\delta)$-degenerate. By repeated application of Lemma 2.17,
for all $I\subset[d-1]$ with $I\neq\emptyset$, in the order given by $\prec$,
we obtain for each such $I$ a multiset $Q_{I}$ with elements chosen from
$g_{3}(d)\mathcal{B}^{\prime}$, subspaces $V_{I}\subset\mathbb{F}_{2}^{I}$,
$V_{I^{c}}\subset\mathbb{F}_{2}^{I^{c}}$ of dimension at most
$g_{4}(d,\delta)$, and we also obtain a constant $g_{5}(d)>0$ such that the
following statement holds. If $r\in\mathcal{G}$ is such that for each
$I\subset[d-1]$ we have that $r.q=0$ for at least $(1-g_{5}(d))|Q_{I}|$
choices of $q\in Q_{I}$, then $r\in
V_{[d]}+\sum_{I\subset[d-1],I\neq\emptyset}(V_{I}\otimes\mathbb{F}_{2}^{I^{c}}+\mathbb{F}_{2}^{I}\otimes
V_{I^{c}})$. Moreover, after taking several copies of each $Q_{I}$, we may
assume that $\max_{I}|Q_{I}|\leq 2\min_{I}|Q_{I}|$. Now let
$g_{6}(d)=\frac{g_{5}(d)}{2\cdot 2^{d-1}}$, let $Q=\bigcup_{I}Q_{I}$, and
suppose that $r.q=0$ for at least $(1-g_{6}(d))|Q|$ choices $q\in Q$. Then, by
averaging, for every $I\subset[d-1]$ we have $r.q=0$ for at least
$(1-g_{5}(d))|Q_{I}|$ choices of $q\in Q_{I}$. Thus, $Q$ is
$(g_{7}(d,\delta),1-g_{6}(d))$-forcing, where
$g_{7}(d,\delta)=\max(g_{1}(\delta),g_{4}(d,\delta))$. ∎

##  3\. The counterexample to Question 1.9

We shall now present an example that gives a negative answer to Question 1.9.
The example is easy to define, but it takes a little work to prove that it has
the properties we require. In what follows, let $G=\mathbb{F}_{2}^{n}$. For a
vector $v\in G$ write $|v|$ for the number of entries equal to 1 in $v$. Then
our set $A$ will be $\\{v\in\mathbb{F}_{2}^{n}:|v|\leq n/2-10^{20}n^{3/4}\\}$,
and our set $B$ will be $\\{v\in\mathbb{F}_{2}^{n}:|v|=n^{1/2}\\}$.

Note first that $A$ is $\eta$-closed with respect to $B$ where $\eta>0$ is
some absolute constant. Indeed, by the central limit theorem, when $n$
sufficiently large, the probability that a random element $u\in A$ has
$|u|\leq n/2-10^{20}n^{3/4}-n^{1/4}$ is at least some absolute constant
$\eta_{1}$, and conditional on this, the probability that $|u+v|\in A$ for a
random element $v\in B$ is at least some other absolute constant $\eta_{2}$,
so we may take $\eta=\eta_{1}\eta_{2}$. What we shall prove is that for this
$\eta$, with $\epsilon=0.99$, say, there do not exist $c,\delta$ and $l$ with
the properties described in Question 1.9. In fact, we shall prove the slightly
stronger statement that for any $\delta>0$ and positive integer $l$, if $n$ is
sufficiently large then there do not exist $C\subset A+lB$ and
$B^{\prime}\subset B$ with $|B^{\prime}|\geq\delta|B|$ such that $C$ is
$(B^{\prime},0.99)$-closed. Since for sufficiently large $n$, we have
$A+lB\subset A^{\prime}=\\{v\in\mathbb{F}_{2}^{n}:|v|\leq
n/2-10^{15}n^{3/4}\\}$, it suffices to prove the same statement but with
$A+lB$ replaced by $A^{\prime}$. From now on, we always assume that $n$ is
sufficiently large.

The proof relies on two lemmas and a definition.

######  Lemma 3.1.

If $B^{\prime}\subset B$ has $|B^{\prime}|\geq\delta|B|$, then
$\widehat{\mu_{B^{\prime}}}(u)\geq 0.98$ for at most $\exp(n^{2/3})$ vectors
$u\in\mathbb{F}_{2}^{n}$.

######  Definition 3.2.

Given $B^{\prime}\subset B$, we say $u\in A^{\prime}$ is _$B^{\prime}$
-compatible_ if the number of $w\in B^{\prime}$ with $|u+w|\leq|u|$ is at
least $|B^{\prime}|/3$.

######  Lemma 3.3.

Let $B^{\prime}\subset B$ have $|B^{\prime}|\geq\delta|B|$. Then the number of
those $u\in A^{\prime}$ which are $B^{\prime}$-compatible is at most
$\exp(-n^{3/4})|A^{\prime}|$.

Let us see why these two lemmas are sufficient. Suppose that $C\subset
A^{\prime}$ is $(B^{\prime},0.99)$-closed for some $B^{\prime}\subset B$ with
$|B^{\prime}|\geq\delta|B|$. Let $w\in B^{\prime}$ be chosen at random. Then
the expected number of $u\in C$ such that $u+w\in C$ is at least $0.99|C|$, so
by considering all such pairs $\\{u,u+w\\}$ and noting that $(u+w)+w=u$, we
see that there are on average at least $\frac{0.99}{2}|C|$ choices of $u\in C$
such that $|u+w|\leq|u|$. Therefore, if $u\in C$ is chosen at random, the
average number of $w\in B^{\prime}$ such that $|u+w|\leq|u|$ is at least
$\frac{0.99}{2}|B^{\prime}|$. It follows that for at least $|C|/10$ elements
of $C$ the number of such $w$ is at least $|B^{\prime}|/3$, so at least
$|C|/10$ elements of $A^{\prime}$ are $B^{\prime}$-compatible. Lemma 3.3 then
implies that $C$ has density at most $10\exp(-n^{3/4})$ in $G$. Let us write
$\gamma$ for this density.

On the other hand, since $C$ is $(B^{\prime},0.99)$-closed, we have the
inequality

$\sum_{u\in G}\widehat{\mu_{B^{\prime}}}(u)|{\hat{C}}(u)|^{2}\geq
0.99\sum_{u\in G}|{\hat{C}}(u)|^{2},$

which implies that

$\sum_{u\in G:\widehat{\mu_{B^{\prime}}}(u)\geq
0.98}\widehat{\mu_{B^{\prime}}}(u)|{\hat{C}}(u)|^{2}\geq 0.01\sum_{u\in
G}|{\hat{C}}(u)|^{2}.$

Using Lemma 3.1, together with the observations that
$\widehat{\mu_{B^{\prime}}}(u)\leq 1$ and $|{\hat{C}}(u)|\leq\gamma$ for every
$u\in G$ and that $\sum_{u\in G}|{\hat{C}}(u)|^{2}=\gamma$, we deduce that
$\exp(n^{2/3})\gamma^{2}\geq 0.01\gamma$, so $\gamma\geq 0.01\exp(-n^{2/3})$.
For sufficiently large $n$, this contradicts the upper bound for $\gamma$ that
we obtained a few lines above.

It remains to prove the two lemmas. The next two results are preparation for
the proof of Lemma 3.1.

######  Lemma 3.4.

Let $V$ be a subspace of $\mathbb{F}_{2}^{n}$ of dimension $d$ such that every
$v\in V$ has $|v|\geq n^{8/15}$. Then $V$ has a basis
$\\{v_{1},\dots,v_{d}\\}$ such that for every $i$, the set $I_{i}=\\{k\leq
n:v_{i}(k)=1,v_{j}(k)=0\text{ for all }j\neq i\\}$ has size at least
$n^{8/15}/2^{d-1}$. Here and below, the $k$th entry of a vector $v$ is denoted
by $v(k)$.

###### Proof.

We use induction on $d$. The case $d=1$ easily follows from the assumption on
$V$. Let $V^{\prime}$ have dimension $d+1$ and suppose that for a
$d$-dimensional subspace $V\subset V^{\prime}$, $v_{1},\dots,v_{d}$ and
$I_{1},\dots,I_{d}$ have been chosen satisfying the requirements. Choose some
$v\in V^{\prime}\setminus V$. Replacing $v$ by $v-v_{1}$ if necessary, we may
assume that $v(k)=0$ for at least $|I_{1}|/2$ choices $k\in I_{1}$. Similarly,
we may assume that $v(k)=0$ for at least $|I_{i}|/2$ choices $k\in I_{i}$ for
every $i\leq d$. Thus, there exist subsets $J_{1},\dots,J_{d}$ of
$\\{1,\dots,n\\}$ of size at least $n^{8/15}/2^{d}$ each such that for every
$i\leq d$ and every $k\in J_{i}$ we have $v_{i}(k)=1$ but $v_{j}(k)=0$ for all
$j$ with $j\neq i,j\leq d$, and $v(k)=0$. Let $J=\\{k\leq n:v(k)=1\\}$. By the
assumption on $V^{\prime}$, we have $|J|\geq n^{8/15}$. Now it is easy to see
that we can define $v_{1}^{\prime}$ to be $v_{1}$ or $v_{1}-v$ and achieve
that $v_{1}^{\prime}(k)=0$ for at least $|J|/2$ choices of $k\in J$.
Similarly, we can define $v_{2}^{\prime},\dots,v_{d}^{\prime}$ such that each
$v_{i}^{\prime}$ is $v_{i}$ or $v_{i}-v$ and
$v_{1}^{\prime}(k)=\dots=v_{d}^{\prime}(k)=0$ for at least $|J|/2^{d}$ choices
$k\in J$. Then for any $i,j\leq d$, we have $v_{i}^{\prime}(k)=v_{i}(k)$ for
every $k\in J_{j}$, and it follows that for any $i\leq d$ and $k\in J_{i}$, we
have $v_{i}^{\prime}(k)=1$ but $v_{j}^{\prime}(k)=0$ for all $j\neq i$, and
$v(k)=0$. Thus, the set $\\{v_{1}^{\prime},\dots,v_{d}^{\prime},v\\}$ is
suitable so the lemma is proved. ∎

######  Corollary 3.5.

Let $t$ be a positive integer not depending on $n$ and let $V$ be a subspace
of $\mathbb{F}_{2}^{n}$ of dimension $t$ such that every $v\in V$ has $|v|\geq
n^{8/15}$. Then the density of those $w\in B$ with $w\cdot v=0$ for all $v\in
V$ is less than $(1.9)^{-(t-1)}$.

###### Proof.

We shall be slightly sketchy about the some of the details when they are very
standard. As always, we assume that $n$ is sufficiently large. Let
$v_{1},\dots,v_{t}$ be a basis given by Lemma 3.4 with $d=t$. Let $w$ be a
random vector in $B$, let $i<t$, and let us consider the probability that
$w.v_{i}=0$ given that $w.v_{j}=0$ for every $j<i$.

The expected number of non-zero coordinates of $w$ in the union of the two
intervals $I_{i}$ and $I_{i+1}$ is at least $n^{1/30}/2^{t-1}$, which tends to
infinity, and the probability that it is at least half this number tends to 1
(very rapidly). If we condition further on this number, and if it is indeed at
least $n^{1/30}/2^{t}$, then the probability that the number of non-zero
coordinates of $w$ in $I_{i}$ is even is almost exactly 1/2. Therefore, the
probability that $w.v_{i}=0$ given that $w.v_{j}=0$ for every $j<i$ is less
than $1/(1.9)$.

Since this is true for every $i\leq t-1$, we obtain the result. ∎

###### Proof of Lemma 3.1.

Suppose that the result is not true. Let $r$ be a positive integer to be
specified later and pick $R=\\{u_{1},\dots,u_{r}\\}$ such that
$\widehat{\mu_{B^{\prime}}}(u_{i})\geq 0.98$ for $i=1,2,\dots,r$. Then for
each $i$, we have $u_{i}\cdot w=0$ for at least 99% of all $w\in B^{\prime}$.
Therefore there is a subset $B^{\prime\prime}\subset B^{\prime}$ with
$|B^{\prime\prime}|\geq|B^{\prime}|/2$ such that each $w\in B^{\prime\prime}$
has $u_{i}\cdot w=0$ for at least 98% of the $u_{i}$. The number of subsets of
$R$ of size $\frac{49}{50}r$ is at most ${r\choose 49r/50}={r\choose
r/50}\leq(50e)^{r/50}\leq(1.8)^{49r/50}$. Let $t=49r/50$. Then there exists a
subset $T$ of $R$ of size $t$ such that the number of $w\in B$ with $w\cdot
u=0$ for all $u\in T$ is at least
$\frac{|B^{\prime\prime}|}{(1.8)^{t}}\geq\frac{\delta}{2\cdot(1.8)^{t}}|B|$.
Choose the smallest positive integer $t$ with
$\frac{\delta}{2\cdot(1.8)^{t}}\geq(1.9)^{-(t-1)}$ (and with $r=50t/49$ an
integer). Then the density of those $w\in B$ with $w\cdot u=0$ for all $u\in
T$ is at least $(1.9)^{-(t-1)}$.

Now let $Q$ be the set of all $u\in\mathbb{F}_{2}^{n}$ with
$\hat{\mu}_{B^{\prime}}(u)\geq 0.98$ and assume that $|Q|\geq\exp(n^{2/3})$.
Let $t$ and $r$ be as above and choose $u_{1},\dots,u_{r}\in Q$ such that for
every $j$, the (Hamming) distance of $u_{j}$ from
$\text{span}(u_{1},\dots,u_{j-1})$ is at least $n^{8/15}$. (This is possible
because the number of $u\in\mathbb{F}_{2}^{n}$ with Hamming distance at most
$n^{8/15}$ from an $r$-dimensional vector space is at most
$2^{r}\exp(O(n^{8/15}\log n))<\exp(n^{2/3})$.) Applying Corollary 3.5 to
$V=\text{span}(T)$, where $T$ is a subset of $\\{u_{1},\dots,u_{r}\\}$ of size
$t$, we find that the density of those $w\in B$ with $w\cdot u=0$ for all
$u\in T$ is less than $(1.9)^{-(t-1)}$, which is a contradiction. ∎

###### Proof of Lemma 3.3.

In this proof, unless specified otherwise, we will view $\mathbb{F}_{2}^{n}$
as a subset of $\mathbb{R}^{n}$ and accordingly, the dot product is defined as
$u\cdot w=\sum_{i}u(i)w(i)$ where the summation is in $\mathbb{R}$. Then
$|u+w|\leq|u|$ is equivalent to $u\cdot w\geq|w|/2$. Hence $u$ is
$B^{\prime}$-compatible if $u\cdot w\geq|w|/2$ for at least $|B^{\prime}|/3$
vectors $w\in B^{\prime}$.

Let $t$ be a fixed positive integer, not depending on $n$, to be specified
later. For a multiset $T=\\{u_{1},\dots,u_{t}\\}\subset A^{\prime}$ write
$s_{T}=\sum_{i=1}^{t}u_{i}-\frac{t}{2}q$ where $q$ is the vector in
$\mathbb{F}_{2}^{n}$ consisting of ones. Let $a_{k}=s_{T}(k)$ and
$\sigma_{T}^{2}=\sum_{k=1}^{n}a_{k}^{2}$. We say that $T$ is _bad_ if
$\sigma_{T}^{2}\geq 1000tn$.

_Claim 1._ If $T$ is not bad, then the number of $w\in B$ with $u_{i}\cdot
w\geq|w|/2$ for all $i$ is at most $\frac{|B|}{100^{t}}$.

_Proof of Claim 1._ If $u_{i}\cdot w\geq|w|/2$ for all $i$, then $s_{T}\cdot
w\geq 0$. Note that $s_{T}\cdot w=\sum_{k\leq n}a_{k}w(k)$. We shall view $w$
as a random variable, chosen uniformly of all elements of $B$. What we need to
prove is that $\mathbb{P}[\sum_{k\leq n}a_{k}w(k)\geq
0]\leq\frac{1}{100^{t}}$.

Let $m=n^{1/2}$ and let $w_{1},\dots,w_{m}$ be standard basis vectors of
$\mathbb{F}_{2}^{n}$, chosen independently and uniformly at random. Note that
the expected number of $i\neq j$ such that $w_{i}=w_{j}$ is at most 1, so
almost surely this number is at most $\log n$. In particular, almost surely we
have $n^{1/2}-2\log n\leq|w_{1}+\dots+w_{m}|\leq n^{1/2}$. Choose uniformly
randomly an element $w\in B$ with minimal Hamming distance from
$w_{1}+\dots+w_{m}\in\mathbb{F}_{2}^{n}$. This algorithm defines a uniformly
random element of $w\in B$ such that almost surely we have $\sum_{k\leq
n}|\sum_{i\leq m}w_{i}(k)-w(k)|\leq\sum_{k\leq n}|\sum_{i\leq
m}w_{i}(k)-(\sum_{i\leq m}w_{i})(k)|+\sum_{k\leq n}|(\sum_{i\leq
m}w_{i})(k)-w(k)|\leq 2\log n+2\log n=4\log n$, where all the summations are
taken in $\mathbb{R}$, except $\sum_{i\leq m}w_{i}$, which is taken in
$\mathbb{F}_{2}^{n}$.

At this point, we apply the following version of Chernoff’s inequality, which
appears as Theorem 3.4 in [2].

Let $X_{i}$ ($1\leq i\leq m$) be independent random variables satisfying
$X_{i}\leq\mathbb{E}[X_{i}]+M$, for $1\leq i\leq m$. We consider the sum
$X=\sum_{i}X_{i}$ with expectation $\mathbb{E}[X]=\sum_{i}\mathbb{E}[X_{i}]$
and variance $\text{Var}(X)=\sum_{i}\text{Var}(X_{i})$. Then, we have
$\mathbb{P}(X\geq\mathbb{E}[X]+\lambda)\leq\exp(-\frac{\lambda^{2}}{2(\text{Var}(X)+M\lambda/3)})$.

We now take $X_{i}=\sum_{k\leq n}a_{k}w_{i}(k)$ for $1\leq i\leq m$. Since
$|a_{k}|\leq t$, the conditions of the theorem hold with $M=2t$. As $u_{i}\in
A^{\prime}$ for all $i$, we have $\sum_{k\leq n}a_{k}\leq
t(n/2-10^{15}n^{3/4})-tn/2=-10^{15}tn^{3/4}$. Then
$\mathbb{E}[X]=m\frac{\sum_{k\leq n}a_{k}}{n}\leq-\frac{1}{2}10^{15}tn^{1/4}$,
and by the assumption that $T$ is not bad, $\text{Var}(X)\leq
m\frac{\sum_{k\leq n}a_{k}^{2}}{n}\leq 1000tn^{1/2}$. Thus, taking
$\lambda=10^{14}tn^{1/4}$ in the above theorem it follows that

$\mathbb{P}[\sum_{i\leq m}\sum_{k\leq
n}a_{k}w_{i}(k)\geq-10^{14}tn^{1/4}]\leq\exp\bigg{(}-\frac{10^{28}t^{2}n^{1/2}}{2(1000tn^{1/2}+2t\cdot
10^{14}tn^{1/4}/3)}\bigg{)}\leq\frac{1}{2\cdot 100^{t}}$

But

$\displaystyle\sum_{k\leq n}a_{k}w(k)$ $\displaystyle=\sum_{i\leq m,k\leq
n}a_{k}w_{i}(k)+\sum_{k\leq n}a_{k}(w(k)-\sum_{i\leq m}w_{i}(k))$
$\displaystyle\leq\sum_{i\leq m,k\leq n}a_{k}w_{i}(k)+t\sum_{k\leq
n}|(w(k)-\sum_{i\leq m}w_{i}(k))|,$

and $\sum_{k\leq n}|(w(k)-\sum_{i\leq m}w_{i}(k))|\leq 4\log n$ almost surely,
it follows that $\mathbb{P}[\sum_{k\leq n}a_{k}w(k)\geq
0]\leq\frac{1}{100^{t}}$ and Claim 1 is proved.

_Claim 2._ If $u_{1},u_{2},\dots,u_{t}$ are independently and uniformly
randomly chosen elements of $A^{\prime}$ then the probability that
$T=\\{u_{1},\dots,u_{t}\\}$ is bad is $o(\exp(-n^{7/8}))$.

_Proof of Claim 2._ Recall that $T$ is bad if and only if $\sum_{k\leq
n}(\sum_{i\leq t}u_{i}(k)-t/2)^{2}\geq 1000tn$. $u_{1},\dots,u_{t}$ are
randomly chosen from $A^{\prime}$ but with probability $1-o(\exp(n^{-7/8}))$
all of them have $|u_{i}|\geq n/2-n^{99/100}$ so we may assume that
$u_{1},\dots,u_{t}$ are randomly chosen from the set
$A^{\prime\prime}=\\{v\in\mathbb{F}_{2}^{n}:n/2-n^{99/100}\leq|v|\leq
n/2-10^{15}n^{3/4}\\}$. It is not hard to see that we can write
$u_{i}=x_{i}+y_{i}$ where $x_{i}$ and $y_{i}$ are random variables taking
values in $\mathbb{F}_{2}^{n}$ and having the property that $x_{i}(k)$ are
independent Bernoulli with parameter $1/2$ and $|y_{i}|\leq 2n^{99/100}$ with
probability $1-o(\exp(-n^{7/8}))$. Then it suffices to prove that

$\mathbb{P}[\sum_{k\leq n}(\sum_{i\leq t}x_{i}(k)-t/2)^{2}\geq
500tn]=o(\exp(-n^{7/8}))$

Let $X_{i}=(\sum_{i\leq t}x_{i}(k)-t/2)^{2}$ for $1\leq k\leq n$. Then the
$X_{i}$ are iid random variables with $\mathbb{E}[X_{i}]=t/4$ and
$\text{Var}(X_{i})=O(1)$. Thus, by Theorem 3.4 from [2] (which is the theorem
stated above), taking $\lambda=100tn$ and $M=t^{2}$, it follows that

$\mathbb{P}[\sum_{k\leq n}(\sum_{i\leq t}x_{i}(k)-t/2)^{2}\geq
500tn]\leq\exp\bigg{(}-\frac{(100tn)^{2}}{2(nO(1)+t^{2}\cdot
100tn/3)}\bigg{)}=o(\exp(-n^{7/8})),$

finishing the proof of Claim 2.

We are now in a position to complete the proof of the lemma. Let $t$ be the
smallest positive integer with $\frac{1}{100^{t}}<\frac{\delta}{100(6e)^{t}}$.
Let the density of $B^{\prime}$-compatible elements in $A^{\prime}$ be
$\alpha$. Pick $v_{1},\dots,v_{6t}$ independently and uniformly randomly from
$A^{\prime}$. Then with probability $\alpha^{6t}$, every $v_{i}$ is
$B^{\prime}$-compatible. If that is the case, then for every $i$, there are at
least $|B^{\prime}|/3$ vectors $w\in B^{\prime}$ with $v_{i}\cdot w\geq|w|/2$.
It follows that there is some $B^{\prime\prime}\subset B^{\prime}$ with
$|B^{\prime\prime}|\geq|B^{\prime}|/100$ such that for every $w\in
B^{\prime\prime}$ we have $v_{i}\cdot w\geq|w|/2$ for at least $t$ choices of
$i$. The number of $t$-sets in $\\{v_{1},\dots,v_{6t}\\}$ is at most
$(6e)^{t}$ so there must exist a $t$-set
$T=\\{u_{1},\dots,u_{t}\\}\subset\\{v_{1},\dots,v_{6t}\\}$ (multisets are
allowed) such that the number of $w\in B$ with $u_{i}\cdot w\geq|w|/2$ for
each $i$ is at least
$|B^{\prime\prime}|/(6e)^{t}\geq\frac{\delta|B|}{100(6e)^{t}}>\frac{|B|}{100^{t}}$.
By Claim 1, it follows that $T$ is bad. Thus, the probability that
$T=\\{u_{1},\dots,u_{t}\\}$ is bad when $u_{1},\dots,u_{t}$ are independently
and uniformly randomly chosen from $A^{\prime}$, is at least
$\frac{\alpha^{6t}}{{6t\choose t}}$. Hence, by Claim 2, we have
$\frac{\alpha^{6t}}{{6t\choose t}}=o(\exp(-n^{7/8}))$, and we get
$\alpha=o(\exp(-n^{3/4}))$. ∎

## References

  * [1] B. Barak, P. K. Kothari and D. Steurer, _Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture_ , arXiv preprint, arXiv:1804.08662
  * [2] F. Chung and L. Lu, _Concentration inequalities and martingale inequalities: a survey_ , Internet Mathematics, 3(1), pp.79-127. (2006)
  * [3] B. J. Green, _The asymmetric Balog-Szemerédi-Gowers theorem_ , unpublished lecture notes
  * [4] O. Janzer, _Low analytic rank implies low partition rank for tensors_ , arXiv preprint
  * [5] S. Khot, _On the power of unique 2-prover 1-round games_ , STOC ’02 Proceedings of the thirty-fourth annual ACM symposium on theory of computing (2002), pp. 767-775.
  * [6] S. Khot, D. Minzer and M. Safra, _Pseudorandom sets in Grassman graph have near-perfect expansion_ , Electronic Colloquium on Computational Complexity, Report no. 6 (2018).
  * [7] S. Lovett, _The analytic rank of tensors and its applications_ , arXiv:1806.09179
  * [8] T. C. Tao and V. Vu, _Additive combinatorics_ , Cambridge studies in advanced mathematics 105, CUP 2006.