# A generalization of the Kelley–Meka theorem
to binary systems of linear forms

Yuval Filmus The Henry & Marilyn Taub Faculty of Computer Science and Faculty
of Mathematics, Technion. Email<EMAIL_ADDRESS>Hamed Hatami School
of Computer Science, McGill University. Email<EMAIL_ADDRESS>Kaave
Hosseini Department of Computer Science, University of Rochester. Email:
<EMAIL_ADDRESS>Esty Kelman Boston University and MIT. Email:
<EMAIL_ADDRESS>
###### Abstract

Kelley and Meka (FOCS’23) recently proved strong bounds on the size of subsets
of $\mathbb{Z}_{N}$ or $\mathbb{F}_{q}^{n}$ that do not contain 3-term
arithmetic progression. We use their techniques to prove similar bounds for
subsets of $\mathbb{F}_{q}^{n}$ that do not contain non-degenerate instances
of affine binary linear systems whose underlying graph is $2$-degenerate.

We show that if a subset of $\mathbb{F}_{q}^{n}$ contains an atypical number
of instances of an affine binary linear 2-degenerate system, then it has a
constant density increment inside an affine subspace of polylogarithmic
codimension. We give a counterexample showing that this kind of result does
not hold for linear systems whose true complexity exceeds $1$.

Using the same techniques, we obtain a counting lemma for sparse quasirandom
graphs, improving on the classical result of Chung, Graham, and Wilson
(Combinatorica 1989), which is only nontrivial for dense graphs.

##  1 Introduction

In a recent breakthrough in additive combinatorics, Kelley and Meka [KM23]
proved a quasi-polynomial upper bound on the density of sets of integers
without non-trivial three-term arithmetic progressions (3-progressions for
short). The key _counting lemma_ that lies at the heart of Kelley and Meka’s
proof is based on a notion of regularity called _spreadness_. It states that
the number of $3$-progressions in a sufficiently spread set cannot
significantly deviate from what is expected from a random set of the same
density.

In this paper, we investigate to what extent Kelley and Meka’s theorem and
counting lemma generalize beyond $3$-progressions to other linear patterns. We
will focus on the group $G=\mathbb{F}^{n}$, where $\mathbb{F}=\mathbb{F}_{q}$
for a fixed small prime $q$, and the asymptotics are as $n$ grows to infinity.
This is the setting that is most relevant to applications in combinatorics and
theoretical computer science, and also serves as an elegant model for tackling
additive problems concerning the integers.

Roth [Rot53] was the first who proved (in 1953) that a set of integers without
non-trivial 3-progressions must have density $o(1)$. Later, Meshulam [Mes95]
carried out Roth’s argument in the case of $\mathbb{F}_{q}^{n}$ for odd prime
$q$. Similar to many proofs in extremal combinatorics and additive
combinatorics, Roth’s argument exploits the dichotomy between structure and
pseudo-randomness. Broadly speaking, a mathematical object $A$ is considered
to be pseudo-random if it mimics the behavior of random objects in certain key
statistics. One class of statistics to consider is the count of certain
patterns in the object (e.g., the number of $3$-progressions in a set of
integers, the number of $4$-cycles in a graph). For example, a random subset
of $\mathbb{F}_{q}^{n}$ with density $\alpha$ is expected to contain
$\alpha^{3}q^{n}$ triples of the form $x,x+d,x+2d$, and therefore, one might
consider a set $A\subseteq\mathbb{F}_{q}^{n}$ of density $\alpha$ pseudo-
random if it contains approximately $\alpha^{3}q^{n}$ such triples.

The dichotomy between pseudo-randomness and structure refers to a general
phenomenon that if such counts indicate a _non-pseudo-random_ behavior in $A$,
then $A$ must have some resemblance to a highly structured object. In other
words, non-pseudo-random objects must correlate with highly structured
objects. For example, Roth’s argument shows that if the number of
$3$-progressions in $A\subseteq\mathbb{F}_{q}^{n}$ significantly deviates from
what is expected from a random set of density $\alpha$, then $A$ has a large
non-principal Fourier coefficient. Equivalently, it has a notable positive
correlation with an affine subspace $V\subseteq\mathbb{F}_{q}^{n}$ of
codimension $1$, meaning that the density of $A$ in $V$ is notably larger than
the original density $\alpha$. More rigorously [Mes95], if

$|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{d}}\left[\mathbf{1}_{A}(\mathbf{x})\mathbf{1}_{A}(\mathbf{x}+\mathbf{d})\mathbf{1}_{A}(\mathbf{x}+2\mathbf{d})\right]-\alpha^{3}|\geq\epsilon\alpha^{3},$

then there exists an affine subspace $V$ of codimension $1$, such that
$\operatorname{\mathbb{E}}_{\mathbf{x}\sim
V}[\mathbf{1}_{A}(\mathbf{x})]\geq\alpha+\epsilon\alpha^{2}$. This conclusion,
unfortunately, has the caveat that restricting to the subspace increases the
density by a factor of $1+\epsilon\alpha$, which can be insubstantial when
$\alpha$ is small. Kelley and Meka obtained a much more substantial density
increment by restricting to a slightly smaller subspace. They proved that
there must exist an affine subspace $V$ of codimension
$\lesssim\log^{8}(1/\alpha)$ such that111This was later improved by Bloom and
Sisask [BS23a] to $\lesssim\log^{6}(1/\alpha)$.

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim
V}[\mathbf{1}_{A}(\mathbf{x})]\geq(1+\Omega(\epsilon))\alpha.$

Restricting to this subspace increases the density by a factor of
$1+\Omega(\epsilon)$, which does not depend on $\alpha$. Kelley and Meka’s
quasi-polynomial upper bound on the density of $3$-progression-free sets
easily follows by repeatedly applying this density increment to reach the
contradiction that the density of $A$ in some affine subspace must be larger
than $1$.

Kelley and Meka’s proof motivates a notion of regularity that we call
_algebraic spreadness_. We will also be concerned with a stronger
combinatorial notion of spreadness that is somewhat implicit in the ideas of
[KM23], and is explicitly defined in the more recent work of Kelley, Lovett,
and Meka [KLM23].

######  Definition 1.1 (Spreadness [KM23, KLM23]).

Let $r\geq 1$ and $\delta>0$. A set $A\subseteq\mathbb{F}^{n}$ of density
$\alpha$ is $(\delta,r)$-_algebraically spread_ if for every affine subspace
$V$ of codimension at most $r$, we have

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim
V}[\mathbf{1}_{A}(\mathbf{x})]\leq(1+\delta)\alpha.$

It is called $(\delta,r)$-_combinatorially spread_ if, for all subsets $S$ and
$T$ of size at least $|\mathbb{F}|^{n-r}$, we have

$\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}\sim S\\\
\mathbf{y}\sim
T\end{subarray}}[\mathbf{1}_{A}(\mathbf{x}+\mathbf{y})]\leq(1+\delta)\alpha.$

Regarding the parameters $\delta$ and $r$, we will consider a set
$A\subseteq\mathbb{F}^{n}$ reasonably spread, if it is $(\delta,r)$-spread for
some $r=\log^{O(1)}(1/\alpha)$ and a sufficiently small $\delta=\Omega(1)$.

######  Remark 1.2.

Note that $(\delta,r)$-combinatorial spreadness implies $(\delta,r)$-algebraic
spreadness. Consider an affine subspace $V=W+a$, where $W$ is a linear
subspace of codimension at most $r$ and $a\in\mathbb{F}^{n}$. Taking
$S\coloneqq W$ and $T\coloneqq V$ recovers the condition of algebraic
spreadness for $V$.

To state our results, we need to specify what we mean by a linear pattern. A
_linear form_ in $d$ variables is a map
$L\colon(\mathbb{F}^{n})^{d}\to\mathbb{F}^{n}$ of the form
$L(x_{1},\ldots,x_{d})=\sum_{i}\lambda_{i}x_{i}$, where the coefficients
$\lambda_{i}$ are elements of $\mathbb{F}$. A tuple
$\mathcal{L}=(L_{1},\ldots,L_{m})$ of _distinct_ linear forms in $d$ variables
is called a _system of linear forms_. A tuple
$(a_{1},\ldots,a_{m})\in(\mathbb{F}^{n})^{m}$ is called an _instance_ of
$\mathcal{L}$ if there exists $x\in(\mathbb{F}^{n})^{d}$ with
$\mathcal{L}(x)\coloneqq(L_{1}(x),\ldots,L_{m}(x))=(a_{1},\ldots,a_{m})$. It
is called a _non-degenerate instance_ if additionally $a_{1},\ldots,a_{m}$ are
all distinct.

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$ be a system of linear forms in $d$
variables and let $A\subseteq\mathbb{F}^{n}$. Let
$\mathbf{x}_{1},\ldots,\mathbf{x}_{d}$ be independent random variables taking
values in $\mathbb{F}^{n}$ uniformly at random. The probability that the
instance $\mathcal{L}(\mathbf{x}_{1},\ldots,\mathbf{x}_{d})$ of $\mathcal{L}$
is in $A^{m}$ is given by the expectation

$t_{\mathcal{L}}(A)\coloneqq\operatorname{\mathbb{E}}\left[\prod_{i=1}^{m}\mathbf{1}_{A}(L_{i}(\mathbf{x}_{1},\ldots,\mathbf{x}_{d}))\right].$

If $\mathbf{A}$ is a random subset of $\mathbb{F}^{n}$, where each element is
picked to be in $\mathbf{A}$ with probability $\alpha$, then with high
probability, we have $t_{\mathcal{L}}(\mathbf{A})\approx\alpha^{m}$. The
central questions studied in the present paper are the following:

######  Question 1.3.

Let $\alpha$ denote the density of $A\subseteq\mathbb{F}^{n}$ and let $m$ be
the number of linear forms in $\mathcal{L}$.

  * (i)

For which systems of linear forms $\mathcal{L}$, combinatorial spreadness
implies $t_{\mathcal{L}}(A)\approx\alpha^{m}$?

  * (ii)

For which systems of linear forms $\mathcal{L}$, algebraic spreadness implies
$t_{\mathcal{L}}(A)\approx\alpha^{m}$?

  * (iii)

For which systems of linear forms $\mathcal{L}$, every set $A$ without non-
degenerate instances of $\mathcal{L}$ has density at most
$|\mathbb{F}|^{n^{-\Omega(1)}}$?

##### Affine systems of linear forms:

1.3 (iii) is only interesting for the systems of linear forms whose instances
are invariant under translations. A system of linear form is called _affine_
if for every instance $(a_{1},\ldots,a_{m})$ of $\mathcal{L}$ and every $c$,
the tuple $(c+a_{1},\ldots,c+a_{m})$ is also an instance of $\mathcal{L}$.
Note that, by linearity, $\mathcal{L}$ is affine if and only if
$(c,\ldots,c)\in(\mathbb{F}^{n})^{m}$ is an instance of $\mathcal{L}$ for
every $c\in\mathbb{F}^{n}$. For example, $(a,a+b,a+2b)$, which represents
$3$-progressions, is affine.

######  Proposition 1.4.

If a system of linear form $\mathcal{L}=(L_{1},\ldots,L_{m})$ is not affine,
then there exists a subset $A\subseteq\mathbb{F}^{n}$ of size
$|\mathbb{F}|^{n-1}$ that does not contain any instances of $\mathcal{L}$.

###### Proof.

Let $\mathcal{L}$ be over variables $x_{1},\ldots,x_{d}$. Since $\mathcal{L}$
is not affine, there exists $c\in\mathbb{F}^{n}$ such that
$\vec{c}=(c,\ldots,c)\in(\mathbb{F}^{n})^{m}$ is not an instance of
$\mathcal{L}$. Let $V$ be a linear subspace of $\mathbb{F}^{n}$ of dimension
$n-1$ that does not contain $c$. Then $A\coloneqq V+c$ is of size
$|\mathbb{F}|^{n-1}$, but it contains no instance of $\mathcal{L}$. Indeed,
suppose there is an assignment $x=(x_{1},\ldots,x_{d})\in(\mathbb{F}^{n})^{d}$
with $L(x)\in A$ for every $L\in\mathcal{L}$. Let
$x_{i}=x_{i}^{\prime}+x_{i}^{\prime\prime}$ be the unique decomposition of
$x_{i}$ as a sum of an element $x_{i}^{\prime}\in V$ and an element
$x_{i}^{\prime\prime}\in\mathrm{span}(\\{c\\})$. Since $V$ is a linear
subspace, for every $L\in\mathcal{L}$ we have
$L(x_{1}^{\prime},\ldots,x_{k}^{\prime})\in V$, and so
$L(x_{1}^{\prime\prime},\ldots,x_{k}^{\prime\prime})=c$. This contradicts the
assumption that $\vec{c}$ is not an instance of $\mathcal{L}$. ∎

##### Binary systems of linear forms:

As we discuss in detail in Section 1.1.5, for most systems of linear forms
(e.g., $k$-term arithmetic progressions for $k>3$), the answers to 1.3 (i) and
(ii) are negative. Briefly speaking, Gowers and Wolf defined a notion of _true
complexity_ for systems of linear forms, and as we show in 1.14, if the true
complexity of $\mathcal{L}$ is larger than $2$, then combinatorial (and
algebraic) spreadness does not suffice to guarantee
$t_{\mathcal{L}}(A)\approx\alpha^{m}$.

Therefore, we restrict our attention to the systems of linear forms of true
complexity at most $2$. Arguably, the most natural class of systems of linear
forms of true complexity $\leq 2$ is the class of _binary systems of linear
forms_. As we describe below, they correspond to linear patterns that are
amenable to graph theoretic tools such as graph removal lemma.

In [RS78], Ruzsa and Szemerédi proved an influential result called the
triangle removal lemma, which states that when a graph contains few triangles,
then all of its triangles can be eliminated by removing a small number of
edges. As an application, Ruzsa and Szemerédi showed that Roth’s $o(1)$ bound
on the density of $3$-progression-free sets easily follows from the triangle
removal lemma. Their reduction is based on a one-to-one correspondence between
$3$-progressions in $A$ and the triangles in a graph $G_{A}$ constructed from
$A$.

It is instructive to describe the construction of $G_{A}$. Let
$\mathbb{F}=\mathbb{F}_{q}$ for an odd prime $q$. One can apply the change of
variables $a=x-y$ and $b=y-\frac{x}{2}-\frac{z}{2}$ to $(a,a+b,a+2b)$ and
capture $3$-progressions in $\mathbb{F}^{n}$ with the system of linear forms
$\mathcal{L}=(x-y,\frac{x-z}{2},y-z)$. For $A\subseteq\mathbb{F}^{n}$, the
graph $G_{A}$ is the $3$-partite graph $(X\cup Y\cup Z,E)$, with
$X=Y=Z=\mathbb{F}^{n}$, where we include an edge between $x\in X$ and $y\in Y$
if $x-y\in A$, between $x\in X$ and $z\in Z$ if $\frac{x-z}{2}\in A$, and
between $y\in Y$ and $z\in Z$ if $y-z\in A$. Note that we have the desired
correspondence that $(x,y,z)$ is a triangle in $G_{A}$ if and only if
$(x-y,\frac{x-z}{2},y-z)$ is a $3$-progression in $A$.

The triangle removal lemma was extended by Erdős, Frankl, and Rödl [EFR86] to
the graph removal lemma, which applies to all graphs $H$. The graph removal
lemma generalizes Ruzsa and Szemerédi’s proof of Roth’s theorem to a large
class of systems of linear forms, namely all affine _binary_ systems of linear
forms.

######  Definition 1.5 (Binary Systems of Linear forms).

A system of linear forms $\mathcal{L}=(L_{1},\ldots,L_{m})$ in the $d$
variables $x_{1},\ldots,x_{d}$ is _binary_ if every linear form in
$\mathcal{L}$ is supported on exactly two variables, and moreover no two
linear forms in $\mathcal{L}$ are supported on the same two variables.

In other words, every $L_{i}$ is of the form
$\lambda_{i}x_{a_{i}}+\eta_{i}x_{b_{i}}$ with nonzero
$\lambda_{i},\eta_{i}\in\mathbb{F}$ and distinct
$a_{i},b_{i}\in\\{1,\ldots,d\\}$, and moreover,
$\\{a_{i},b_{i}\\}\neq\\{a_{j},b_{j}\\}$ if $i\neq j$.

The binary system of linear forms $\mathcal{L}$ in Definition 1.5 naturally
defines an undirected graph $H$ with vertex set $\\{1,\ldots,d\\}$ and an edge
$\\{a_{i},b_{i}\\}$ for each linear form
$\lambda_{i}x_{a_{i}}+\eta_{i}x_{b_{i}}$ in $\mathcal{L}$. We say that $H$ is
the _underlying graph_ of $\mathcal{L}$.

###  1.1 Our Contributions

In the remainder of the introduction, we will concretely state our main
theorems toward answering 1.3.

####  1.1.1 Counting lemma under combinatorial spreadness

In regard to 1.3 (i), we prove a positive answer for all binary systems of
linear forms.

######  Theorem 1.6 (Combinatorial counting lemma).

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$ be a binary system of linear forms and
let $0<\epsilon<1$. For $\delta=\epsilon^{2}2^{-4m-11}$ and some
$r=O_{m,\epsilon}(\log^{2}(1/\alpha))$, every $(\delta,r)$-combinatorially
spread set $A\subseteq\mathbb{F}^{n}$ with density $\alpha$ satisfies

$|t_{\mathcal{L}}(A)-\alpha^{m}|\leq\epsilon\alpha^{m}.$

######  Remark 1.7.

Note that here, $\delta$ does not depend on the density parameter $\alpha$,
and for example, if $\epsilon=\Omega(1)$ and $m=O(1)$, then
$\delta=\Omega(1)$.

####  1.1.2 Counting lemma under algebraic spreadness

1.6 shows that a combinatorially spread set $A\subseteq\mathbb{F}^{n}$ of
density $\alpha$ must contain roughly the expected number of instances of any
binary system of linear forms. Unfortunately, for applications such as proving
an upper bound on the density of sets without a given linear pattern, such a
theorem does not seem to provide a density increment argument that can be
applied repeatedly, since the sets $S,T$ provided by the violation of
combinatorial spreadness are merely subsets of $\mathbb{F}^{n}$ without any
guaranteed algebraic structure. To be able to repeat the density increment in
the same manner as in Kelley and Meka’s proof, one needs a counting lemma that
achieves a density increment in a subset with an algebraic structure, such as
a subspace.

Our algebraic counting lemma only applies to a restricted class of binary
systems. To state it, we need one more definition: an undirected graph $H$ is
called _$k$ -degenerate_ if every subgraph of $H$ has a vertex of degree at
most $k$. In the next theorem, we show that algebraic spreadness suffices to
guarantee $t_{\mathcal{L}}(A)\approx\alpha^{m}$ for all binary systems
$\mathcal{L}$ whose underlying graph is $2$-degenerate.

######  Theorem 1.8 (Algebraic counting lemma).

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$ be a binary system of linear forms
whose underlying graph $H$ is $2$-degenerate, and let $0<\epsilon<1$. For
$\delta=\epsilon^{2}2^{-4m-14}$ and some
$r=O_{\epsilon,m}(\log^{6}\frac{1}{\alpha})$, every $(\delta,r)$-algebraically
spread set $A\subseteq\mathbb{F}^{n}$ with density $\alpha$ satisfies

$|t_{\mathcal{L}}(A)-\alpha^{m}|\leq\epsilon\alpha^{m}.$

####  1.1.3 Generalized Kelley–Meka Theorem

As an application of LABEL:{thm:algebraic-counting}, we consider the problem
of establishing strong upper bounds on the density of sets that do not contain
any non-degenerate instance of certain systems of linear forms.

As mentioned earlier, Roth used a Fourier-analytic approach to show that a set
without $3$-progressions must have density $o(1)$. It was not until 1975 that
Szemerédi [Sze75] extended Roth’s $o(1)$ bound using a completely new approach
to arithmetic progressions of arbitrary length. Shortly after, Furstenberg and
Katznelson [FK78] found an approach based on Ergodic theory to establish a
multidimensional Szemerédi theorem, which generalized Szemerédi’s theorem to
all systems of linear forms.

In contrast to Roth’s Fourier-analytic proof, the techniques used in the
various known proofs of the Szemerédi theorem and the multidimensional
Szemerédi theorem give extremely poor bounds. For example, it was a major
breakthrough when Gowers [Gow01] in 2001 proved an upper bound of $1/(\log\log
N)^{2^{-2^{k+9}}}$ on the density of sets of integers without $k$-term
arithmetic progressions. However, for general linear systems of linear forms,
no upper bound better than Ackermann type is known [Gow07, MS19].

In the following theorem, we give Kelley–Meka-type bounds for a large class of
linear systems.

######  Theorem 1.9 (Generalized Kelley–Meka Theorem).

Let $\mathcal{L}$ be an affine binary system of linear forms whose underlying
graph $H$ is $2$-degenerate. If $A\subseteq\mathbb{F}^{n}$ is free of non-
degenerate instances of $\mathcal{L}$, then

$|A|\leq|\mathbb{F}|^{n-\Omega(n^{1/7})}.$

######  Remark 1.10.

Kelley and Meka’s proof provides a density upper bound of
$e^{-\Omega(\log^{1/12}N)}$ for Roth’s theorem in $\mathbb{Z}_{N}$, and in the
case of $\mathbb{F}^{n}$ it proves an upper bound of
$|\mathbb{F}|^{-\Omega(n^{1/9})}$. Subsequently, these bounds were improved by
[BS23a] to $e^{-\Omega(\log^{1/9}N)}$ and $|\mathbb{F}|^{-\Omega(n^{1/7})}$.
We should remark that in $\mathbb{F}^{n}$, the stronger bound of
$|\mathbb{F}|^{-\Omega(n)}$ was already known via the polynomial method
[EG17]. However, the polynomial method does not seem to generalize to other
systems of linear forms or to $\mathbb{Z}_{N}$, nor does it provide any
structural information about the sets that, say, contain few 3-progressions.

####  1.1.4 Subgraph counting lemma

1.6 is a consequence of a stronger result (1.11) that is applicable in the
more general setting of binary relations
$A\subseteq\mathcal{X}\times\mathcal{X}$, where $\mathcal{X}$ is a finite set.

Recall that a directed graph is an _oriented graph_ if it contains no opposite
pairs of directed edges, or equivalently, it does not contain any $2$-cycles.
Let $H=(V_{H},E_{H})$ be a fixed oriented graph with vertex set
$V_{H}=\\{1,\ldots,d\\}$. For every $A\subseteq\mathcal{X}\times\mathcal{X}$,
define

$t_{H}(A)\coloneqq\operatorname{\mathbb{E}}\left[\prod_{uv\in
E_{H}}\mathbf{1}_{A}(\mathbf{x}_{u},\mathbf{x}_{v})\right],$

where $\mathbf{x}_{v}$ for $v\in V_{H}$ are independent random variables
taking values in $\mathcal{X}$ uniformly at random. One can interpret $A$ as a
directed graph with vertex set $\mathcal{X}$ and edges $(u,v)\in A$. Then
$t_{H}(A)$ is the probability that a random map from the vertices of $H$ to
the vertices of $A$ is a graph morphism, i.e., it maps every edge of $H$ to an
edge in $A$. Also note that more generally, one can define $t_{H}(f)$ for a
function $f\colon\mathcal{X}\times\mathcal{X}\to[0,1]$.

The following counting lemma states that if $A$ satisfies a condition
analogous to combinatorial spreadness, then $t_{H}(A)\approx\alpha^{m}$ for
all oriented graphs $H$ on $m$ edges.

######  Theorem 1.11 (A counting lemma for graphs).

Let $H$ be an oriented graph with $m$ edges, and let $0<\epsilon<1$. There
exists $\delta=\delta(\epsilon,H)>0$ such that for every
$A\subseteq\mathcal{X}\times\mathcal{X}$ of density $\alpha$, if

$\left|t_{H}(A)-\alpha^{m}\right|\geq\epsilon\alpha^{m},$

then at least one of the following two cases holds:

  1. 1.

There exist $S,T\subseteq\mathcal{X}$ of densities at least
$2^{-O_{m,\epsilon}(\log^{2}(1/\alpha))}$

such that

$\operatorname{\mathbb{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\sim
S\times T\end{subarray}}[1_{A}(\mathbf{x},\mathbf{y})]\geq(1+\delta)\alpha;$

  2. 2.

There exists $S\subseteq\mathcal{X}$ of density at least
$2^{-O_{m,\epsilon}(\log(1/\alpha))}$ such that

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}}[1_{A}(z,\mathbf{x})]\leq(1-\delta)\alpha\qquad\forall
z\in S,$

or

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}}[1_{A}(\mathbf{x},z)]\leq(1-\delta)\alpha\qquad\forall
z\in S.$

In other words, if $\left|t_{H}(A)-\alpha^{m}\right|\geq\epsilon\alpha^{m}$,
then either $A$ contains a large subgraph that is significantly denser, or it
contains many vertices whose outdegrees or indegrees are significantly smaller
than the average. Nevertheless, in both cases, one obtains sets
$S,T\subseteq\mathcal{X}$ of densities at least
$2^{-O_{m,\epsilon}(\log^{2}(1/\alpha))}$ such that

$\left|\operatorname{\mathbb{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\sim
S\times
T\end{subarray}}[1_{A}(\mathbf{x},\mathbf{y})]-\alpha\right|\geq\delta\alpha$

One may compare 1.11 with previously known counting lemmas, most notably the
seminal result of Chung, Graham, and Wilson [CGW89]. Their result is usually
phrased for undirected (labeled) graphs, i.e., when $H$ is undirected and
$A\subseteq\mathcal{X}\times\mathcal{X}$ is symmetric. In this case, $t_{H}$
is defined as

$t_{H}(A)\coloneqq\operatorname{\mathbb{E}}\left[\prod_{\\{u,v\\}\in
E_{H}}\mathbf{1}_{A}(\mathbf{x}_{u},\mathbf{x}_{v})\right],$

######  Theorem 1.12 ([CGW89]).

Let $H$ be an undirected graph with $m$ edges, and let $0<\epsilon<1$. There
exists $\delta=\delta(\epsilon,H)>0$ such that for every undirected graph $A$
of density $\alpha$ on vertex set $\mathcal{X}$, if

$\left|t_{H}(A)-\alpha^{m}\right|\geq\epsilon,$

then there exist $S,T\subseteq\mathcal{X}$ of densities at least
$\Omega_{m,\epsilon}(1)$ such that

$\left|\operatorname{\mathbb{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\sim
S\times
T\end{subarray}}[1_{A}(\mathbf{x},\mathbf{y})]-\alpha\right|\geq\delta.$

The following immediate corollary of 1.11 is a way to salvage Theorem 1.12 in
the sparse setting.

######  Corollary 1.13.

Let $H$ be an undirected graph with $m$ edges, and let $0<\epsilon<1$. There
exists $\delta=\delta(\epsilon,H)>0$ such that for every undirected graph $A$
of density $\alpha$ on vertex set $\mathcal{X}$, if

$\left|t_{H}(A)-\alpha^{m}\right|\geq\epsilon\alpha^{m},$

then there exist $S,T\subseteq\mathcal{X}$ of densities at least
$2^{-O_{m,\epsilon}(\log^{2}(1/\alpha))}$ such that

$\left|\operatorname{\mathbb{E}}_{\begin{subarray}{c}(\mathbf{x},\mathbf{y})\sim
S\times
T\end{subarray}}[1_{A}(\mathbf{x},\mathbf{y})]-\alpha\right|\geq\delta\alpha$

####  1.1.5 True complexity of systems of linear forms and resilience to
spreadness

1.6 and 1.8 show that the densities of certain systems of linear forms in a
set $A$ are “controlled” by combinatorial and algebraic spreadness. In this
section, we discuss negative results. We show that for most systems of linear
forms, combinatorial spreadness is not sufficient to guarantee
$t_{\mathcal{L}}(A)\approx\alpha^{m}$.

Gowers, in his proof of Szemerédi’s theorem, introduced a hierarchy of
increasingly stronger notions of pseudo-randomness based on the so-called
Gowers uniformity norms $\|\cdot\|_{U^{k}}$ for $k\geq 1$. He used iterated
applications of the classical Cauchy–Schwarz inequality to prove

$\left|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}}\left[\mathbf{1}_{A}(\mathbf{x})\mathbf{1}_{A}(\mathbf{x}+\mathbf{y})\cdots\mathbf{1}_{A}(\mathbf{x}+(k-1)\mathbf{y})\right]-\alpha^{k}\right|\leq
k\|\mathbf{1}_{A}-\alpha\|_{U^{k-1}},$

showing that the density of $k$-progressions in $A$ is controlled by the
pseudo-randomness condition $\|\mathbf{1}_{A}-\alpha\|_{U^{k-1}}=o(1)$.

In a series of articles [GW11, GW10], Gowers and Wolf initiated a systematic
study of classifying the systems of linear forms that are controlled by $k$-th
Gowers uniformity norm. They defined the _true complexity_ of a system of
linear forms $L=(L_{1},\ldots,L_{m})$ as the smallest $k$ such that the
pseudo-randomness condition of $\|\mathbf{1}_{A}-\alpha\|_{U^{k+1}}=o(1)$
implies $|t_{\mathcal{L}}(A)-\alpha^{m}|=o(1)$, and fully characterized the
true complexity provided that the field size is large enough.

It is known that the true complexity of the linear system identifying
$4$-progressions is 2. Moreover, it is well-known that there is a set $A$ of
density $\alpha$ such that $\|\mathbf{1}_{A}-\alpha\|_{U^{2}}=o(1)$ (hence,
combinatorially spread) but the count of $4$-progressions in $A$ is far from
what is expected from a random set of density $\alpha$. Here, we generalize
this result. We show that if the true complexity of a linear system
$\mathcal{L}$ is larger than $1$, then there are sets $A$ with density
$\alpha$ that are combinatorially spread with extremely good parameters, and
yet, $t_{\mathcal{L}}(A)\not\approx\alpha^{m}$.

######  Theorem 1.14.

Suppose that $\mathcal{L}=(L_{1},\ldots,L_{m})$ is a system of linear forms of
CS-complexity at most $|\mathbb{F}|$ and of true complexity $k>1$. There
exists a set $A\subseteq\mathbb{F}^{n}$ with density $\alpha\geq\frac{1}{3}$
that is $(e^{-\Omega(n)},\Omega(n))$-combinatorially spread, yet

$t_{\mathcal{L}}(A)>(1+\Omega(1))\alpha^{m}.$

As the proof makes clear, the constant $\tfrac{1}{3}$ can be replaced by any
constant strictly smaller than $1$.

We explain the meaning of CS-complexity in Definition 3.5. For now, the reader
can think of it as a technical condition that holds if we fix $\mathcal{L}$
(thinking of the coefficients as fixed integers) and take $\mathbb{F}$ large
enough.

##### Acknowledgement

We wish to thank Tsun-Ming Cheung for his valuable feedback on an earlier
draft of this paper.

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 802020-ERC-
HARMONIC.

This project was partially carried out at Simons Institute for Theory of
Computing, UC Berkeley, while the authors were participating in the program
Analysis and TCS in Summer 2023.

##  2 Preliminaries

##### Notation.

As mentioned in the introduction, throughout the paper,
$\mathbb{F}\coloneqq\mathbb{F}_{q}$ for a fixed prime $q$. The function $\log$
is the base $2$ logarithm. We denote random variables with bold font. For a
finite set $S$, the notation $\mathbf{x}\sim S$ means that $\mathbf{x}$ is a
random variable taking values uniformly at random from $S$. Given a function
$f\colon\mathbb{F}^{n}\to\mathbb{R}$, and $p\in[1,\infty)$, let
$\|f\|_{p}=\left(\operatorname{\mathbb{E}}[|f(\mathbf{x})|^{p}]\right)^{1/p}$,
and let $\|f\|_{\infty}=\max_{x}|f(x)|$. For a positive integer $m$, we denote
$[m]\coloneqq\\{1,\ldots,m\\}$.

We use the standard Bachmann–Landau asymptotic notation:
$O(\cdot),\Omega(\cdot),\Theta(\cdot),o(\cdot)$, and $\omega(\cdot)$.
Sometimes, we will use these notations in combination with subscripts to
indicate that the hidden constants may depend on the parameters in the
subscript. For example, $O_{m}(1)$ means bounded by a constant $c$ that may
depend on $m$.

###  2.1 Grid norms

In one of the cornerstones of the area of pseudo-randomness, Chung, Graham and
Wilson [CGW89] proved a striking result that if an undirected graph with edge
density $\alpha$ has approximately the same number of $4$-cycles as the Erdős-
Renyi random graph $G(n,\alpha)$, then it shares several structural, spectral
and statistical properties with $G(n,\alpha)$.

The pseudo-randomness theorem of [CGW89] naturally generalizes to binary
relations $A\subseteq\mathcal{X}\times\mathcal{Y}$. A set
$A\subseteq\mathcal{X}\times\mathcal{Y}$ exhibits any of several pseudo-random
properties if

$t_{C_{4}}(A)\coloneqq\operatorname{\mathbb{E}}[\mathbf{1}_{A}(\mathbf{x}_{1},\mathbf{y}_{1})\mathbf{1}_{A}(\mathbf{x}_{2},\mathbf{y}_{1})\mathbf{1}_{A}(\mathbf{x}_{2},\mathbf{y}_{1})\mathbf{1}_{A}(\mathbf{x}_{2},\mathbf{y}_{2})]=\alpha^{4}+o(1).$

One of the key ideas used in the work of Kelley and Meka, and more explicitly
in the follow-up work of Kelley, Lovett, and Meka [KLM23], is to consider a
certain generalization of $t_{C_{4}}(A)$.

######  Definition 2.1 (Grid semi-norms).

For a function $f\colon\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$, and
$p,k\in\mathbb{N}$, let

$\displaystyle U_{k,p}(f)$
$\displaystyle\coloneqq\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}\sim\mathcal{X}^{k}\\\
\mathbf{y}\sim\mathcal{Y}^{p}\end{subarray}}\left[\prod_{i=1}^{k}\prod_{j=1}^{p}f(\mathbf{x}_{i},\mathbf{y}_{j})\right].$

Also define $\|f\|_{U(k,p)}\coloneqq|U_{k,p}(f)|^{1/pk}$ and
$\|f\|_{|U(k,p)|}\coloneqq U_{k,p}(|f|)^{1/pk}$.

Note that with the notation of the following definition,
$t_{C_{4}}(A)=U_{2,2}(\mathbf{1}_{A})$. Lemma 2.2 below is the analogue of the
so-called Gowers–Cauchy–Schwarz inequality for $U(k,p)$ norms.

######  Lemma 2.2.

(Gowers–Cauchy–Schwarz inequality) Let $p,k\in\mathbb{N}$, and for $i\in[k]$
and $j\in[p]$, and let
$f_{ij}\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$. Suppose that either
$k,p$ are both even numbers, or the functions $f_{ij}$ take only non-negative
values. Then

$\operatorname{\mathbb{E}}_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}}\operatorname{\mathbb{E}}_{\mathbf{y}_{1},\ldots,\mathbf{y}_{p}}\left[\prod_{i=1}^{k}\prod_{j=1}^{p}f_{ij}(\mathbf{x}_{i},\mathbf{y}_{j})\right]\leq\prod_{i=1}^{k}\prod_{j=1}^{p}\|f_{ij}\|_{U(k,p)}.$
(1)

###### Proof.

Recall the generalized Hölder inequality:

$\operatorname{\mathbb{E}}_{\mathbf{z}}\left|\prod_{j=1}^{p}g_{j}(\mathbf{z})\right|\leq\prod_{j=1}^{p}\left(\operatorname{\mathbb{E}}_{\mathbf{z}}|g_{j}(\mathbf{z})|^{p}\right)^{1/p}.$

Choosing $z=(x_{1},\dots,x_{k})$ and
$g_{j}(x_{1},\dots,x_{k})=\operatorname{\mathbb{E}}_{\mathbf{y}_{j}}\prod_{i}f_{ij}(x_{i},\mathbf{y}_{j})$,
we obtain

$\text{L.H.S.\ of \lx@cref{creftype~refnum}{eq:Gowers-
CS}}\leq\prod_{j=1}^{p}\left(\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}^{k}}\left(\operatorname{\mathbb{E}}_{\mathbf{y}\sim\mathcal{Y}}\prod_{i=1}^{k}f_{ij}(\mathbf{x}_{i},\mathbf{y})\right)^{p}\right)^{1/p}.$
(2)

Next, note that for every fixed $j$, we can apply the generalized Hölder
inequality to the variable $\mathbf{y}\sim\mathcal{Y}^{p}$ and obtain

$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}^{k}}\left(\operatorname{\mathbb{E}}_{\mathbf{y}\sim\mathcal{Y}}\prod_{i=1}^{k}f_{ij}(\mathbf{x}_{i},\mathbf{y})\right)^{p}$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}^{k}}\operatorname{\mathbb{E}}_{\mathbf{y}\sim\mathcal{Y}^{p}}\prod_{i=1}^{k}\prod_{t=1}^{p}f_{ij}(\mathbf{x}_{i},\mathbf{y}_{t})$
$\displaystyle\leq\prod_{i=1}^{k}\left(\operatorname{\mathbb{E}}_{\mathbf{y}\sim\mathcal{Y}^{p}}\left(\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}}\prod_{t=1}^{p}f_{ij}(\mathbf{x},\mathbf{y}_{t})\right)^{k}\right)^{1/k}=\prod_{i=1}^{k}\|f_{ij}\|_{U(k,p)}^{p}.$

Substituting these in Equation 2, we obtain the desired inequality. ∎

Applying Lemma 2.2 to the expansion of $U_{k,p}(f+g)$ easily implies that
$\|\cdot\|_{|U(k,p)|}$ is a norm, and that when $p$ and $k$ are both even,
$\|\cdot\|_{U(k,p)}$ is a semi-norm.

######  Corollary 2.3 ([KLM23, Claim 4.2]).

If $f\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{\geq 0}$ then
$\|f\|_{U(k,p)}$ is monotone in both $k$ and $p$.

###### Proof.

We will prove monotonicity for $k$; the same argument can be applied to $p$.
Let $k^{\prime}\geq k$, and define
$f_{ij}\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{\geq 0}$ for $1\leq
i\leq k^{\prime}$ and $1\leq j\leq p$ as

$f_{ij}=\begin{cases}f&i\leq k\\\ 1&i>k\\\ \end{cases}.$

Applying Equation 1 to these functions, we have

$\|f\|_{U(k,p)}^{kp}=\operatorname{\mathbb{E}}_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}}\operatorname{\mathbb{E}}_{\mathbf{y}_{1},\ldots,\mathbf{y}_{p}}\left[\prod_{i=1}^{k}\prod_{j=1}^{p}f(\mathbf{x}_{i},\mathbf{y}_{j})\right]\leq\|f\|_{U(k^{\prime},p)}^{kp}\|1\|_{U(k^{\prime},p)}^{k^{\prime}p-kp}=\|f\|_{U(k^{\prime},p)}^{kp},$

as desired. ∎

###  2.2 From large grid-norms to structural irregularity

As we shall see in Section 3, to prove 1.8 and 1.11, we will first show that
if $|t_{H}(A)-\alpha^{m}|=\Omega(\alpha^{m})$, then for some $k=O_{m}(1)$ and
$p\approx\log(1/\alpha)$, we have
$\|\mathbf{1}_{A}\|_{U(k,p)}\geq(1+\Omega(1))\alpha$. In this section, we
state some results from [KM23, KLM23, BS23b, BS23a] that allow us to deduce
the desired structural facts about $A$ from the assumption
$\|\mathbf{1}_{A}\|_{U(k,p)}\geq(1+\Omega(1))\alpha$.

######  Lemma 2.4 (Sifting a rectangle [KLM23]).

Let $f\colon\mathcal{X}\times\mathcal{Y}\rightarrow[0,1]$ satisfy
$\operatorname{\mathbb{E}}[f]=\alpha$. Let $p,k\in\mathbb{N}$. If

$\|f\|_{U(k,p)}\geq(1+\epsilon)\alpha,$

then there exist $S\subseteq\mathcal{X}$ and $T\subseteq\mathcal{Y}$ with

$\operatorname{\mathbb{E}}_{(\mathbf{x},\mathbf{y})\in S\times
T}f(\mathbf{x},\mathbf{y})\geq\bigg{(}1+\frac{\epsilon}{2}\bigg{)}\alpha,$

and

$\frac{|S||T|}{|\mathcal{X}||\mathcal{Y}|}\geq\frac{1}{2}\cdot\epsilon\cdot\alpha^{pk+1}.$

Let $A\subseteq\mathbb{F}^{n}$ have density $\alpha$. Lemma 2.4 shows that if
$f(x,y)\coloneqq\mathbf{1}_{A}(x+y)$ satisfy
$\|f\|_{U(2,p)}\geq(1+\epsilon)\alpha$, then there exist large
$S,T\subseteq\mathbb{F}^{n}$ such that
$\operatorname{\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim S\times
T}\mathbf{1}_{A}(\mathbf{x}+\mathbf{y})\geq(1+\Omega(1))\alpha$. We next show
that if $k=2$, then one can conclude a significant positive correlation with
an affine subspace, thus violating algebraic spreadness. This was first proved
by Kelley and Meka [KM23] and then improved by Bloom and Sisask [BS23b, BS23a]
in the following two lemmas, the combination of which gives us the desired
subspace in Lemma 2.7 below.

######  Lemma 2.5 (Dependent random choice [BS23b, Corollary 8]).

Let $p>1$ be an integer and $\epsilon>0$. If $A\subseteq\mathbb{F}^{n}$ is a
set with density $\alpha$ such that
$\|f\|_{U(2,p)}^{2}\geq(1+\epsilon)\alpha^{2}$, where
$f(x,y)\coloneqq\mathbf{1}_{A}(x+y)$, and
$S=\\{x:\operatorname{\mathbb{E}}_{\mathbf{y}\sim
A}[\mathbf{1}_{A}(x+\mathbf{y})]>(1+\epsilon/2)\alpha\\}$, then there are
$A_{1},A_{2}\subseteq\mathbb{F}^{n}$, both of density
$\Omega\left(\alpha^{p+O_{\epsilon}(1)}\right)$, such that

$\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}\sim A_{1}\times
A_{2}}[\mathbf{1}_{S}(\mathbf{x}-\mathbf{y})]\geq 1-\epsilon/8.$

######  Lemma 2.6 (Almost periodicity [BS23a, Lemma 6]).

Let $\epsilon\in(0,1/8)$. Let $S\subseteq\mathbb{F}^{n}$ and
$A,A_{1},A_{2}\subseteq\mathbb{F}^{n}$ be sets with densities
$\alpha,\alpha_{1},\alpha_{2}$, respectively, such that

  1. 1.

$\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}\sim A_{1}\times
A_{2}}[\mathbf{1}_{S}(\mathbf{x}-\mathbf{y})]\geq 1-\epsilon$ and

  2. 2.

$\operatorname{\mathbb{E}}_{\mathbf{y}\sim
A}[\mathbf{1}_{A}(x+\mathbf{y})]\geq(1+4\epsilon)\alpha$ for any $x\in S$.

There exists a subspace $V\leq\mathbb{F}^{n}$ of codimension
$O_{\epsilon}\left(\log^{2}(2/\alpha)\log(2/\alpha_{1})\log(2/\alpha_{2})\right)$
and $x\in F^{n}$ such that

$\operatorname{\mathbb{E}}_{\mathbf{y}\sim
V+x}[\mathbf{1}_{A}(\mathbf{y})]\geq\left(1+\frac{\epsilon}{2}\right)\alpha.$

The following lemma is an improved version of [KM23, Theorem 4.6] and is an
easy corollary of the combination of Lemma 2.5 and Lemma 2.6.

######  Lemma 2.7 (Sifting a subspace).

Let $p>1$ be an integer, $\epsilon>0$ and $A\subseteq\mathbb{F}^{n}$ of
density $\alpha$. If $f(x,y)=\mathbf{1}_{A}(x+y)$ satisfies

$\|f\|_{U(2,p)}^{2}\geq(1+\epsilon)\alpha^{2},$

then there exists an affine subspace $V\subseteq\mathbb{F}^{n}$ of codimension
at most $O_{\epsilon}(p^{2}\log^{4}(1/\alpha))$ such that

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim
V}\mathbf{1}_{A}(\mathbf{x})\geq\left(1+\frac{\epsilon}{16}\right)\alpha.$

The reason behind the $2$-degeneracy assumption in 1.8 is that we do not know
whether Lemma 2.7 is true for $U(k,p)$ norms with $k>2$. In fact, we show in
Proposition 4.1 that Lemma 2.6 generalizes to $U(k,p)$ norms. However, we do
not know whether an analogue of Lemma 2.7 holds in the more general setting
(see 4.2).

Finally, we will also need the following simple lemma that deduces some
structural facts about $f$ from the assumption
$\|f-\operatorname{\mathbb{E}}[f]\|_{p}\geq\epsilon\alpha$.

######  Lemma 2.8.

Let $p\geq 1$ and let $f\colon\mathcal{X}\to[0,1]$ satisfy
$\operatorname{\mathbb{E}}[f]=\alpha$ and
$\|f-\alpha\|_{p}\geq\epsilon\alpha$. Then one of the following two cases
holds:

  * (i)

$\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\mathbf{1}_{[f(\mathbf{x})>\alpha(1+\frac{\epsilon}{4})]}\right]\geq\epsilon^{p}\alpha^{p}/4$.

  * (ii)

$\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\mathbf{1}_{[f(\mathbf{x})<\alpha(1-\frac{\epsilon}{4})]}\right]\geq\epsilon^{p}/4$.

###### Proof.

From the assumption,

$\operatorname{\mathbb{E}}_{\mathbf{x}}|f(\mathbf{x})-\alpha|^{p}=\|f-\alpha\|_{p}^{p}\geq\epsilon^{p}\alpha^{p}.$

We have

$\operatorname{\mathbb{E}}\left[|f(\mathbf{x})-\alpha|^{p}\mathbf{1}_{[|f(\mathbf{x})-\alpha|\leq\frac{\epsilon\alpha}{4}]}\right]\leq(\epsilon/4)^{p}\alpha^{p}\leq\frac{\epsilon^{p}}{4}\alpha^{p},$

and therefore,

$\displaystyle\frac{3\epsilon^{p}}{4}\alpha^{p}$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[|f(\mathbf{x})-\alpha|^{p}\mathbf{1}_{[f(\mathbf{x})>\alpha(1+\frac{\epsilon}{4})]}\right]+\operatorname{\mathbb{E}}\left[|f(\mathbf{x})-\alpha|^{p}\mathbf{1}_{[f(\mathbf{x})<\alpha(1-\frac{\epsilon}{4})]}\right]$
$\displaystyle\leq\operatorname{\mathbb{E}}\left[\mathbf{1}_{[f(\mathbf{x})>\alpha(1+\frac{\epsilon}{4})]}\right]+\alpha^{p}\operatorname{\mathbb{E}}\left[\mathbf{1}_{[f(\mathbf{x})<\alpha(1-\frac{\epsilon}{4})]}\right],$

which implies that one of the two cases (i) or (ii) must hold. ∎

##  3 Proofs

Recall that an undirected graph is called $k$-degenerate if each of its
subgraphs has a vertex of degree at most $k$. We extend this notion to
oriented graphs by defining the degree of a vertex in a directed graph as the
sum of its in-degree and out-degree.

######  Theorem 3.1 (Main Technical Theorem).

Suppose $H=(V,E)$ is a $k$-degenerate oriented graph with $m$ edges. For every
$0<\epsilon<1$, there exists
$\delta=\delta(\epsilon,H)\geq\epsilon^{2}2^{-4m-10}$ such that the following
holds. Suppose that for every $uv\in E$, we have a function
$f_{uv}\colon\mathcal{X}\times\mathcal{X}\to\\{0,1\\}$ with
$\operatorname{\mathbb{E}}[f_{uv}]=\alpha$, such that

$\left|\operatorname{\mathbb{E}}\prod_{uv\in
E}f_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-\alpha^{m}\right|\geq\epsilon\alpha^{m}.$
(3)

Then for some $uv\in E$ and $p\leq\frac{8}{\epsilon}\log\frac{2}{\alpha}$, at
least one of the following holds:

  * (i)

$\max(\|f_{uv}\|_{U(2(k-1),p)},\|f_{uv}\|_{U(p,2(k-1))})\geq(1+\delta)\alpha;$
(4)

  * (ii)

$\max(\|\operatorname{\mathbb{E}}_{\mathbf{y}}\left[f_{uv}(\cdot,\mathbf{y})\right]-\alpha\|_{p},\|\operatorname{\mathbb{E}}_{\mathbf{x}}\left[f_{uv}(\mathbf{x},\cdot)\right]-\alpha\|_{p})\geq\delta\alpha.$
(5)

######  Remark 3.2.

The orientations of the edges in $H$ are not important. Indeed, for every edge
$uv\in E$, we can change the orientation of the edge and use the transpose
function $f_{vu}(x,y)=f^{T}_{uv}(x,y)=f_{uv}(y,x)$ instead of the function
$f_{uv}$. This will not affect (3) nor the conclusion of the theorem.

###  3.1 Proof of Theorem 3.1

We will prove the theorem by induction on the quantity $\kappa(H)\coloneqq
2|E|-d_{1}(H)$, where $d_{1}(H)$ is the number of vertices of degree $1$ in
$H$. More precisely, the induction hypothesis states that the theorem holds
with $\delta(\epsilon,H)=\epsilon^{2}2^{-2\kappa(H)-10}$.

To verify the base case $\kappa(H)=0$, note that in this case, $H$ consists of
$|E|$ isolated edges. For such a graph, the L.H.S. of (3) is always $0$, and
the statement is trivially true.

We normalize the functions
$f_{uv}\colon\mathcal{X}\times\mathcal{X}\to\\{0,1\\}$ by defining
$F_{uv}\colon\mathcal{X}\times\mathcal{X}\to\\{0,\alpha^{-1}\\}$ as
$F_{uv}\coloneqq\alpha^{-1}\cdot f_{uv}$. We can rephrase the assumption,
Equation 3, as

$\left|\operatorname{\mathbb{E}}\prod_{uv\in
E}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-1\right|\geq\epsilon.$ (6)

Since $H$ is $k$-degenerate, it contains a vertex $s$ of degree at most $k$.
By Remark 3.2, we can change the orientation of the edges incident to $s$ if
necessary and assume, without loss of generality, that $s$ is a sink. Let
$u_{1},\ldots,u_{\ell}$ be the neighbors of $s$, where $1\leq\ell\leq k$.

Let $H^{\prime}=(V\setminus\\{s\\},E^{\prime})$ where $E^{\prime}\subsetneq E$
is the set of the edges that do not involve $s$. Assume $u_{1}s$ is not an
isolated edge, as otherwise, one can remove $u_{1}s$ without loss of
generality. Therefore, $d_{1}(H^{\prime})\geq d_{1}(H)-\ell$ and we have

$\kappa(H^{\prime})=2|E^{\prime}|-d_{1}(H^{\prime})\leq
2(|E|-\ell)-(d_{1}(H)-\ell)=\kappa(H)-\ell.$

By applying the induction hypothesis to $H^{\prime}$, we may assume

$\left|\operatorname{\mathbb{E}}\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-1\right|\leq\frac{\epsilon}{2},$
(7)

as otherwise, we are done with

$\delta=\delta(\epsilon/2,H^{\prime})=(\epsilon/2)^{2}2^{-2{\kappa(H^{\prime})}-10}\geq\epsilon^{2}2^{-2{\kappa(H)}-10}=\delta(\epsilon,H)$

as desired. In particular, we may assume

$\operatorname{\mathbb{E}}\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\leq 2.$

Therefore, using $F_{uv}\in\\{0,\alpha^{-1}\\}$, we have for every $q\geq 1$,

$\operatorname{\mathbb{E}}\left[\left(\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)^{q}\right]\leq\operatorname{\mathbb{E}}\left[(\alpha^{-1})^{q-1}\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\leq 2\alpha^{1-q}.$
(8)

We will single out the edge $u_{1}s$ and set $E^{\prime\prime}\coloneqq
E\setminus\\{u_{1}s\\}$.

If $\ell=1$, then $E^{\prime\prime}=E^{\prime}$. Combining Equation 7 and
Equation 6, we have

$\left|\operatorname{\mathbb{E}}\left[(F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{x}_{s})-1)\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\right|=\left|\operatorname{\mathbb{E}}\prod_{uv\in
E}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-\operatorname{\mathbb{E}}\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right|\geq\frac{\epsilon}{2}.$

Consequently, we may apply Hölder’s inequality over the variables
$\mathbf{x}\coloneqq\\{\mathbf{x}_{u}\\}_{u\in V\setminus\\{s\\}}$ with the
even integer $p=2\lceil\log(\alpha^{-1})\rceil\geq 2\log(\alpha^{-1})$, and
$\frac{1}{p}+\frac{1}{q}=1$, obtaining

$\displaystyle\frac{\epsilon}{2}\leq$
$\displaystyle\left|\operatorname{\mathbb{E}}\left[(F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{x}_{s})-1)\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\right|$
$\displaystyle\leq\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)^{q}\right]^{1/q}\times\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}(F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{x}_{s})-1)\right)^{p}\right]^{1/p}$
$\displaystyle\leq
3\cdot\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}(F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{x}_{s})-1)\right)^{p}\right]^{1/p},$

where the last inequality follows from

$(2\alpha^{1-q})^{1/q}\leq 2\alpha^{\frac{1}{q}-1}=2\alpha^{-\frac{1}{p}}\leq
2\alpha^{-\frac{1}{2\log(\alpha^{-1})}}\leq 3.$ (9)

We conclude that

$\|\operatorname{\mathbb{E}}_{\mathbf{y}}F_{u_{1}s}(\cdot,\mathbf{y})-1\|_{p}\geq\epsilon/6\geq\delta,$

which verifies Equation 5.

For $\ell\geq 2$, consider the graph $H^{\prime\prime}$ obtained from $H$ by
“detaching” the edge $u_{1}s$ from the node $s$. More formally, to obtain
$H^{\prime\prime}$, we add a new vertex $s^{\prime}$ to $H$, remove the edge
$u_{1}s$, and add the edge $u_{1}s^{\prime}$ instead. Note that
$\kappa(H^{\prime\prime})\leq\kappa(H)-1$. By applying the induction
hypothesis to $H^{\prime\prime}$ with parameter $\epsilon/2$, we may assume
that

$\left|\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}^{V}}\left[\left(\prod_{uv\in
E^{\prime\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)\cdot\left(\operatorname{\mathbb{E}}_{\mathbf{z}\sim\mathcal{X}}F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{z})\right)\right]-1\right|\leq\frac{\epsilon}{2},$
(10)

as otherwise, the assertion of the theorem follows from the induction
hypothesis with parameter
$\delta=\delta(\epsilon/2,H^{\prime\prime})\geq\delta(\epsilon,H)$ as desired.

Set $J(x,y)\coloneqq
F_{u_{1}s}(x,y)-\operatorname{\mathbb{E}}_{\mathbf{z}\sim\mathcal{X}}F_{u_{1}s}(x,\mathbf{z})$.
We have

$\operatorname{\mathbb{E}}\left[J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\prod_{uv\in
E^{\prime\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]=\operatorname{\mathbb{E}}\prod_{uv\in
E}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}^{V}}\left[\left(\prod_{uv\in
E^{\prime\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)\cdot\operatorname{\mathbb{E}}_{\mathbf{z}\sim\mathcal{X}}F_{u_{1}s}(\mathbf{x}_{u_{1}},\mathbf{z})\right].$

Combining the above equation with Equation 6 and Equation 10, we obtain

$\left|\operatorname{\mathbb{E}}\left[J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\prod_{uv\in
E^{\prime\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\right|\geq\frac{\epsilon}{2}.$

We may apply Hölder’s inequality over the variables
$\mathbf{x}\coloneqq\\{\mathbf{x}_{u}\\}_{u\in V\setminus\\{s\\}}$ with the
even integer $p=2\lceil\log(\alpha^{-1})\rceil\geq 2\log(\alpha^{-1})$, and
$\frac{1}{p}+\frac{1}{q}=1$, obtaining

$\displaystyle\left|\operatorname{\mathbb{E}}\left[J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\prod_{uv\in
E^{\prime\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\right|$
$\displaystyle=\left|\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)\cdot\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}\left[J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\cdot\prod_{uv\in
E^{\prime\prime}\setminus
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right]\right]\right|$
$\displaystyle\leq\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\prod_{uv\in
E^{\prime}}F_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})\right)^{q}\right]^{1/q}\times$
$\displaystyle\qquad\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\cdot\prod_{i=2}^{\ell}F_{u_{i}s}(\mathbf{x}_{u_{i}},\mathbf{x}_{s})\right)^{p}\right]^{1/p}$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{\leq}}3\cdot\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\cdot\prod_{i=2}^{\ell}F_{u_{i}s}(\mathbf{x}_{u_{i}},\mathbf{x}_{s})\right)^{p}\right]^{1/p},$

where $(\ast)$ follows from Equation 8 and Equation 9. We conclude that

$\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\prod_{i=2}^{\ell}F_{u_{i}s}(\mathbf{x}_{u_{i}},\mathbf{x}_{s})\right)^{p}\right]^{1/p}\geq\frac{\epsilon}{6}.$
(11)

On the other hand, by Cauchy–Schwarz and then Equation 1, we have

$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{s}}J(\mathbf{x}_{u_{1}},\mathbf{x}_{s})\prod_{i=2}^{\ell}F_{u_{i}s}(\mathbf{x}_{u_{i}},\mathbf{x}_{s})\right)^{p}\right]$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{y}_{1},\ldots,\mathbf{y}_{p}}\operatorname{\mathbb{E}}_{\mathbf{x}_{u_{1}}}\prod_{j=1}^{p}J(\mathbf{x}_{u_{1}},\mathbf{y}_{j})\operatorname{\mathbb{E}}_{\mathbf{x}_{u_{2}},\ldots,\mathbf{x}_{u_{\ell}}}\prod_{i=2}^{\ell}\prod_{j=1}^{p}F_{u_{i}s}(\mathbf{x}_{u_{i}},\mathbf{y}_{j})$
$\displaystyle\leq\|J\|^{p}_{U(2,p)}\cdot\left[\operatorname{\mathbb{E}}_{\mathbf{y}_{1},\ldots,\mathbf{y}_{p}}\left(\operatorname{\mathbb{E}}_{\mathbf{x}_{2},\ldots,\mathbf{x}_{\ell}}\prod_{i=2}^{\ell}\prod_{j=1}^{p}F_{u_{i}s}(\mathbf{x}_{i},\mathbf{y}_{j})\right)^{2}\right]^{1/2}$
$\displaystyle\leq\|J\|^{p}_{U(2,p)}\prod_{i=2}^{\ell}\|F_{u_{i}s}\|_{U(2(\ell-1),p)}^{p}.$

Taking the $p$-th root of this upper-bound and combining it with Equation 11,
we get

$\|J\|_{U(2,p)}\prod_{i=2}^{\ell}\|F_{u_{i}s}\|_{U(2(\ell-1),p)}\geq\frac{\epsilon}{6}.$

If there exists $i\in\\{2,\ldots,\ell\\}$ with
$\|F_{u_{i}s}\|_{U(2(\ell-1),p)}\geq 2$, we are done by monotonicity of grid
norms (Corollary 2.3) with $2(k-1)\geq 2(\ell-1)$, and otherwise,

$\|J\|_{U(2,p)}\geq\frac{\epsilon}{6\cdot 2^{\ell-1}}.$

Note that $\operatorname{\mathbb{E}}_{\mathbf{z}}J(x,\mathbf{z})=0$ for every
$x\in\mathcal{X}$. Therefore, we can apply Lemma 3.3 below to $J$ and obtain
that for $p^{\prime}=2p\lceil 1/\varepsilon\rceil$, we have

$\|1+J\|_{U(2,p^{\prime})}\geq 1+\frac{\epsilon^{2}}{45\cdot 2^{2\ell}}\geq
1+2\delta.$

The last inequality is true because $\kappa(H)=\sum_{v\in
V\colon\deg(v)>1}\deg(v)\geq\deg(s)=\ell$. Since
$J(x,y)=F_{u_{1}s}(x,y)-D(x,y)$ with
$D(x,y)\coloneqq\operatorname{\mathbb{E}}_{\mathbf{z}\sim\mathcal{X}}F_{u_{1}s}(x,\mathbf{z})$,
applying the triangle inequality, we have

$\|F_{u_{1}s}\|_{U(2,p^{\prime})}+\|D-1\|_{U(2,p^{\prime})}\geq 1+2\delta.$

Now either

$\|F_{u_{1}s}\|_{U(2,p^{\prime})}\geq 1+\delta,$

in which case, we are done, or

$\|D-1\|_{U(2,p^{\prime})}\geq\delta.$

Since $D(x,y)-1$ does not depend on $y$, we have
$\|D-1\|_{U(2,p^{\prime})}=\|D-1\|_{2}$, and thus in this latter case, we get

$\|D-1\|_{2}\geq\delta,$

which verifies Equation 5. It remains to prove Lemma 3.3 below.

######  Lemma 3.3.

If $g\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ satisfies
$\|g\|_{U(2,p)}^{2}\geq\epsilon$ for some even $p$ and some
$\epsilon\in(0,1/2]$ and

$\operatorname{\mathbb{E}}_{\mathbf{z}}g(x,\mathbf{z})=0\qquad\forall
x\in\mathcal{X},$

then for every even $p^{\prime}\geq\frac{2p}{\epsilon}$, we have
$\|1+g\|_{U(2,p^{\prime})}\geq 1+\epsilon/5$.

The proof will make use of the following result of Kelly and Meka.

######  Proposition 3.4 ([KM23, Proposition 5.7]).

Suppose $f\colon\Omega\to\mathbb{R}$ is such that

  * •

$\operatorname{\mathbb{E}}(f-1)^{k}\geq 0$ for all odd $k\in\mathbb{N}$, and

  * •

$\|f-1\|_{k_{0}}\geq\varepsilon$ for some even $k_{0}\geq 2$ and some
$\epsilon\in[0,1/2]$.

Then, for any integer $k^{\prime}\geq 2k_{0}/\varepsilon$,

$\|f\|_{k^{\prime}}\geq 1+\frac{\epsilon}{2}.$

###### Proof of Lemma 3.3.

Let $g\circ g\colon\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ be defined as
$(g\circ
g)(x_{1},x_{2})\coloneqq\operatorname{\mathbb{E}}_{\mathbf{y}}g(x_{1},\mathbf{y})g(x_{2},\mathbf{y})$.
Note that

$\|g\|_{U(2,p)}^{2}=\|g\circ g\|_{p}.$

Moreover, for every $q\in\mathbb{N}$,

$\operatorname{\mathbb{E}}(g\circ
g)^{q}=\operatorname{\mathbb{E}}_{\mathbf{y}_{1},\ldots,\mathbf{y}_{q}}\left(\operatorname{\mathbb{E}}_{\mathbf{x}}\prod_{i=1}^{q}g(\mathbf{x},\mathbf{y}_{i})\right)^{2}\geq
0.$

It follows from Proposition 3.4 that for every integer
$p^{\prime}\geq\frac{2p}{\epsilon}$,

$\|g\circ g+1\|_{p^{\prime}}\geq 1+\frac{\epsilon}{2}.$

Moreover, $\operatorname{\mathbb{E}}_{\mathbf{y}}g(\cdot,\mathbf{y})\equiv 0$
implies that $(g+1)\circ(g+1)=(g\circ g)+1$, and thus

$\|1+g\|_{U(2,p^{\prime})}=\|(g+1)\circ(g+1)\|_{p^{\prime}}^{1/2}\geq\sqrt{1+\frac{\epsilon}{2}}\geq
1+\frac{\epsilon}{5}.\qed$

###  3.2 Proof of 1.11

See 1.11

###### Proof.

To prove the theorem, we will first apply Theorem 3.1, and then apply Lemma
2.4 or Lemma 2.8 to deduce the desired structural result about $A$.

Let $H=(V,E)$. We define the functions
$f_{uv}\colon\mathcal{X}\times\mathcal{X}\to\\{0,1\\}$ to be the same and
equal to $\mathbf{1}_{A}$ for all edges $uv\in E$. Note that
$\operatorname{\mathbb{E}}[f_{uv}]=\operatorname{\mathbb{E}}[1_{A}]=\alpha$,
and

$t_{\mathcal{L}}(A)=\operatorname{\mathbb{E}}\prod_{uv\in
E}f_{uv}(\mathbf{x}_{u},\mathbf{x}_{v}).$

If $\left|t_{\mathcal{L}}(A)-\alpha^{m}\right|\geq\epsilon\alpha^{m}$, we can
apply Theorem 3.1 and conclude that for some
$p\leq\frac{8}{\epsilon}\log\frac{2}{\alpha}$ and
$\delta=\epsilon^{2}2^{-4m-10}$, at least one of the following holds:

  * (i)

$\max\left(\|\mathbf{1}_{A}\|_{U(2(k-1),p)},\|\mathbf{1}_{A}\|_{U(p,2(k-1))}\right)\geq(1+\delta)\alpha;$

  * (ii)

$\max\left(\|\operatorname{\mathbb{E}}_{\mathbf{y}}\left[\mathbf{1}_{A}(\cdot,\mathbf{y})\right]-\alpha\|_{p},\|\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\mathbf{1}_{A}(\mathbf{x},\cdot)\right]-\alpha\|_{p}\right)\geq\delta\alpha.$

  * Case (i)

Using $2m\geq 2(k-1)$ and monotonicity of grid norms, we have

$\max\\{\|\mathbf{1}_{A}\|_{U(2m,p)},\|\mathbf{1}_{A}\|_{U(p,2m)}\\}\geq(1+\delta)\alpha.$

In this case, Lemma 2.4 implies the existence of $S,T\subseteq\mathcal{X}$

with

$\min\left(\frac{|S|}{|\mathcal{X}|},\frac{|T|}{|\mathcal{X}|}\right)\geq\frac{|S||T|}{|\mathcal{X}|^{2}}\geq\frac{1}{2}\delta\alpha^{2pm+1}\geq
2^{-O\left(\frac{m}{\epsilon}\log^{2}(1/\alpha)\right)},$

which shows that Item 1 of 1.11 holds.

  * Case (ii)

Assume that
$\|\operatorname{\mathbb{E}}_{\mathbf{y}}\left[\mathbf{1}_{A}(\cdot,\mathbf{y})\right]-\alpha\|_{p}\geq\delta\alpha$.
The other case is similar. By applying Lemma 2.8 to the function
$f\colon\mathcal{X}\to[0,1]$ given by
$f(x)\coloneqq\operatorname{\mathbb{E}}_{\mathbf{y}}[\mathbf{1}_{A}(x,\mathbf{y})]$,
we conclude that one of the following two cases holds:

    * a)

$\operatorname{\mathbb{E}}\left[\mathbf{1}_{[f(x)>\alpha(1+\frac{\delta}{4})]}\right]\geq(\delta\alpha)^{p}/4=2^{-O\left(\frac{m}{\epsilon^{2}}\log^{2}(1/\alpha)\right)}$.

    * b)

$\operatorname{\mathbb{E}}\left[\mathbf{1}_{[f(x)<\alpha(1-\frac{\delta}{4})]}\right]=\delta^{p}/4\geq\alpha^{O(m/\varepsilon^{2})}$.

In case (a), let
$S\coloneqq\\{x\in\mathcal{X}:\operatorname{\mathbb{E}}_{\mathbf{y}}[\mathbf{1}_{A}(x,\mathbf{y})]>\alpha(1+\delta)\\}$
and $T=\mathcal{X}$ and conclude Item 1 of 1.11:

$\operatorname{\mathbb{E}}_{(\mathbf{x},\mathbf{y})\in S\times
T}\mathbf{1}_{A}(\mathbf{x},\mathbf{y})\geq(1+\delta)\alpha.$

In case (b), let
$S=\\{x\in\mathcal{X}:\operatorname{\mathbb{E}}_{\mathbf{y}}[\mathbf{1}_{A}(x,\mathbf{y})]<\alpha(1-\delta)\\}$
and conclude Item 2 of 1.11:

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim\mathcal{X}}[1_{A}(z,\mathbf{x})]\leq(1-\delta)\alpha\qquad\text{for
all }z\in S.\qed$

###  3.3 Proof of 1.6

See 1.6

###### Proof.

The proof is similar to the first part of the proof of 1.11. Suppose
$|t_{\mathcal{L}}(A)-\alpha^{m}|\geq\epsilon\alpha^{m}$.

Let $H=(V,E)$ be the underlying graph of $\mathcal{L}$, and let $k\leq m$
denote the degeneracy of $H$. We turn $H$ into an oriented graph by directing
every edge from the vertex with the smaller index to the larger one. For
$i\in[m]$, suppose that $L_{i}=\lambda_{i}x_{a_{i}}+\eta_{i}x_{b_{i}}$ with
$a_{i}<b_{i}$. Define
$f_{a_{i}b_{i}}\colon\mathbb{F}^{n}\times\mathbb{F}^{n}\to\\{0,1\\}$ as
$f_{a_{i}b_{i}}(x,y):=\mathbf{1}_{A}(\lambda_{i}x+\eta_{i}y)$. Note that
$\operatorname{\mathbb{E}}[f_{a_{i}b_{i}}]=\alpha$ for all $i$, and moreover,

$t_{\mathcal{L}}(A)=\operatorname{\mathbb{E}}\prod_{uv\in
E}f_{uv}(\mathbf{x}_{u},\mathbf{x}_{v}),$

hence

$\left|\operatorname{\mathbb{E}}\prod_{uv\in
E}f_{uv}(\mathbf{x}_{u},\mathbf{x}_{v})-\alpha^{m}\right|\geq\epsilon\alpha^{m}.$

By Theorem 3.1, there exist $i\in[m]$ and
$p\leq\frac{8}{\epsilon}\log\frac{2}{\alpha}$ such that for
$\delta=\epsilon^{2}2^{-4m-10}$, at least one of (4) or (5) holds. Note that
(5) cannot hold as for every $i\in[m]$ and every $x\in\mathbb{F}^{n}$,

$\operatorname{\mathbb{E}}_{\mathbf{y}}[f_{a_{i}b_{i}}(x,\mathbf{y})]=\operatorname{\mathbb{E}}_{\mathbf{y}}[\mathbf{1}_{A}(\lambda_{i}x+\eta_{i}\mathbf{y})]=\alpha,$

and similarly, for every $y\in\mathbb{F}^{n}$,
$\operatorname{\mathbb{E}}_{\mathbf{x}}[f_{a_{i}b_{i}}(\mathbf{x},y)]=\alpha$.
Thus, we may assume that (4) holds, i.e., for some $i\in[m]$,

$\max\\{\|f_{a_{i}b_{i}}\|_{U(2(k-1),p)},\|f_{a_{i}b_{i}}\|_{U(p,2(k-1))}\\}\geq(1+2\delta)\alpha.$
(12)

Using $2(k-1)\leq 2m$ and the monotonicity of grid norms, we have

$\max\\{\|f_{a_{i}b_{i}}\|_{U(2m,p)},\|f_{a_{i}b_{i}}\|_{U(p,2m)}\\}\geq(1+2\delta)\alpha.$

Now, we can apply Lemma 2.4 to deduce the existence of
$S^{\prime},T^{\prime}\subseteq\mathbb{F}^{n}$ with

$\min\left(\frac{|S^{\prime}|}{|\mathbb{F}^{n}|},\frac{|T^{\prime}|}{|\mathbb{F}^{n}|}\right)\geq\frac{|S^{\prime}||T^{\prime}|}{|\mathbb{F}|^{2n}}\geq\delta\alpha^{2pm+1}\geq
2^{-O\left(\frac{m}{\epsilon}\log^{2}(1/\alpha)\right)},$

and

$\operatorname{\mathbb{E}}_{(\mathbf{x},\mathbf{y})\in S^{\prime}\times
T^{\prime}}[\mathbf{1}_{A}(\lambda_{i}\mathbf{x}+\eta_{i}\mathbf{y})]\geq(1+\delta)\alpha.$

We conclude 1.6 for $S=\\{\lambda_{i}x\ |\ x\in S^{\prime}\\}$ and
$T=\\{\eta_{i}x\ |\ x\in T^{\prime}\\}$. ∎

###  3.4 Proof of 1.8

See 1.8

###### Proof.

The proof is essentially the same as the proof of 1.6 except that now we start
from the assumption that the degeneracy is $k=2$. Therefore, following the
proof of 1.6, we can recover Equation 12 with $k=2$: There exists $i\in[m]$
and $p\leq\frac{8}{\epsilon}\log\frac{2}{\alpha}$ such that for
$\delta=\epsilon^{2}2^{-4m-14}$, we have

$\max\\{\|f_{a_{i}b_{i}}\|_{U(2,p)},\|f_{a_{i}b_{i}}\|_{U(p,2)}\\}\geq(1+16\delta)\alpha.$

In particular, recalling the definition of $f_{a_{i}b_{i}}$, we conclude that
there exist nonzero $\lambda,\eta\in\mathbb{F}$ such that

$(1+16\delta)\alpha\leq\left(\operatorname{\mathbb{E}}\prod_{i=1}^{2}\prod_{j=1}^{p}\mathbf{1}_{A}(\lambda
x_{i}+\eta
y_{j})\right)^{1/2p}=\left(\operatorname{\mathbb{E}}\prod_{i=1}^{2}\prod_{j=1}^{p}\mathbf{1}_{A}(x_{i}+y_{j})\right)^{1/2p}=\|\mathbf{1}_{A}\|_{U(2,p)}.$

Now, we can apply Lemma 2.7 to conclude the existence of an affine subspace
$V\subseteq\mathbb{F}^{n}$ of
$\operatorname{codim}(V)=O_{\epsilon,m}\left(\log^{6}\frac{1}{\alpha}\right)$
such that

$\operatorname{\mathbb{E}}_{x\sim
V}[\mathbf{1}_{A}(x)]\geq(1+\delta)\alpha.\qed$

###  3.5 Proof of 1.9

See 1.9

The proof is the same density increment argument that is sketched in the
introduction. If $A$ does not have any non-degenerate instances of
$\mathcal{L}$, then by 1.8, there exists a large affine subspace $W+c$ on
which the density of $A$ increases by a multiplicative factor of
$1+\Omega(1)$. Since $\mathcal{L}$ is affine, we can restrict $A$ to this
subspace and repeat the argument until we reach a contradiction by showing
that the density of $A$ in some affine subspace is larger than $1$.

###### Proof.

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$, and let $A$ be a set without any non-
degenerate instances of $\mathcal{L}$. Denote the density of $A$ by $\alpha$.
Let $\eta=\eta(m)>0$ be a sufficiently small constant, and assume towards a
contradiction that $\alpha>|\mathbb{F}|^{-\eta n^{1/7}}$.

Recall that the linear forms in a system of linear forms must be distinct.
Therefore, by applying the union bound to all pairs of linear forms, the
probability that a random $\mathbf{x}\sim(\mathbb{F}^{n})^{d}$ induces a
degenerate instance is at most

$\Pr_{\mathbf{x}}[\exists i,j\in[m],\ \text{s.t. }i\neq j\text{ and
}L_{i}(\mathbf{x})=L_{j}(\mathbf{x})]\leq\sum_{i\neq
j\in[m]}\Pr_{\mathbf{x}\in(\mathbb{F}^{n})^{d}}[L_{i}(\mathbf{x})=L_{j}(\mathbf{x})]\leq
m^{2}|\mathbb{F}|^{-n}.$

Since $A$ is free of non-degenerate instances of $\mathcal{L}$, for
sufficiently large $n$ we have

$\Pr_{\mathbf{x}}[\mathcal{L}(\mathbf{x})\in A^{m}]\leq
m^{2}|\mathbb{F}|^{-n}\leq\frac{\alpha^{m}}{2}.$ (13)

Now we can apply 1.8 to deduce the existence of $c\in\mathbb{F}^{n}$ and a
linear subspace $W\leq\mathbb{F}^{n}$ of codimension
$O\left(\log^{6}(1/\alpha)\right)$ such that
$\operatorname{\mathbb{E}}_{\mathbf{x}\sim W+c}[\mathbf{x}\in
A]\geq(1+\delta)\alpha$ for some $\delta\geq 2^{-20m}$. We wish to restrict
$A$ to $W+c$ and repeat this argument, or more precisely, restrict $A-c$ to
$W$. Let

$A_{1}=\\{x\in W:x+c\in A\\}.$

Note that $A\subseteq W\cong\mathbb{F}^{n_{1}}$ for
$n_{1}=n-\operatorname{codim}(W)\geq n-O\left(\log^{6}(1/\alpha)\right)$; We
have $\frac{|A_{1}|}{|\mathbb{F}^{n_{1}}|}\geq(1+\delta)\alpha$, and since
$\mathcal{L}$ is an _affine_ system of linear forms, $A_{1}$ does not contain
any non-degenerate instances of $\mathcal{L}$.

We can repeat this argument $t=O(\log 1/\alpha)$ times and obtain a sequence
of $A_{i}\subseteq\mathbb{F}^{n_{i}}$ for $i=1,\ldots,t$ such that each
$A_{i}$ is free of non-degenerate instances of $\mathcal{L}$, and whose
density is larger than the density of the previous $A_{i}$ by a factor of
$1+\delta$. Note also that

$n_{i}\geq n-O\left(t\log^{6}(1/\alpha)\right))\geq
n-O\left(\log^{7}(1/\alpha)\right))>n/2,$

and therefore, Equation 13 remains valid throughout the argument. We reach a
contradiction since

$\frac{|A_{t}|}{|\mathbb{F}^{n_{t}}|}\geq(1+\delta)^{t}\alpha>1,$

for some $t=O(\log(1/\alpha))$. ∎

###  3.6 Proof of 1.14

Before proving the theorem, we provide some background on true complexity and
on related notions of complexity.

Green and Tao [GT10], in their study of solutions of linear equations in the
primes, worked out the most general class of systems of linear forms that can
be handled by Gowers’ iterated Cauchy–Schwarz argument.

######  Definition 3.5 (The Cauchy–Schwarz Complexity).

Let $\mathcal{L}=\\{L_{1},\ldots,L_{m}\\}$ be a system of linear forms. The
_Cauchy–Schwarz complexity_ of $\mathcal{L}$ is the minimal $k$ such that the
following holds. For every $1\leq i\leq m$, we can partition
$\\{L_{j}\\}_{j\in[m]\setminus\\{i\\}}$ into $k+1$ subsets, such that $L_{i}$
does not belong to the linear span of each such subset.

In particular, Green and Tao [GT10] showed that if the Cauchy–Schwarz
complexity of $\mathcal{L}$ is $k$, then

$\left|t_{\mathcal{L}}(A)-\alpha^{m}\right|\leq
m\|\mathbf{1}_{A}-\alpha\|_{U^{k+1}}.$ (14)

######  Example 3.6.

The system of linear forms $(x,x+y,\ldots,x+(k-1)y)$, which represents
$k$-term arithmetic progressions, has CS-complexity $k-2$. It is also
straightforward to verify that binary systems of linear forms have CS-
complexity $1$.

As we sketch below, one can apply Roth’s argument to every affine system of
linear forms of CS-complexity $1$. Indeed, it is easy to see [GT08,
Proposition 2.2] that if $\|f\|_{\infty}\leq 1$ then

$\|\widehat{f}\|_{\infty}\leq\|f\|_{U^{2}}\leq\sqrt{\|\widehat{f}\|_{\infty}}.$

Therefore, if $\mathcal{L}$ has CS-complexity $1$ and
$|t_{\mathcal{L}}(\mathbf{1}_{A})-\alpha^{m}|\geq\epsilon\alpha^{m}$, then by
(14), we have
$\|\widehat{\mathbf{1}_{A}-\alpha}\|_{\infty}\geq\frac{\epsilon^{2}\alpha^{2m}}{m^{2}}$.
In particular, there is a non-principal Fourier character $\chi$ such that
$|\widehat{\mathbf{1}_{A}}(\chi)|\geq\frac{\epsilon^{2}\alpha^{2m}}{m^{2}}$.
This large Fourier coefficient allows a density increment of
$\frac{\epsilon^{2}\alpha^{2m}}{m^{2}}$ in a subspace of co-dimension $1$. If
$\mathcal{L}$ is affine, one can repeat the argument. It seems that in regards
to generalizing 1.8, the most general class one can hope for is the systems of
linear forms of CS-complexity $1$.

######  Problem 3.7 (Open Problem).

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$ be a system of linear forms of
Cauchy–Schwarz complexity $1$ and let $0<\epsilon<1$. Are there constants
$C>0$ and $\delta>0$ such that for every
$(\delta,\log^{C}(1/\alpha))$-algebraically spread $A\subseteq\mathbb{F}^{n}$
with density $\alpha$, we have
$|t_{\mathcal{L}}(A)-\alpha^{m}|\leq\epsilon\alpha^{m}$?

In a series of articles [GW11, GW10], Gowers and Wolf initiated a systematic
study of classifying the systems of linear forms that are controlled by $k$-th
Gowers uniformity norm. They defined the _true complexity_ of a system of
linear forms $L=(L_{1},\ldots,L_{m})$ as the smallest $k$ such that the
pseudo-randomness condition of $\|\mathbf{1}_{A}-\alpha\|_{U^{k+1}}=o(1)$
implies $|t_{\mathcal{L}}(A)-\alpha^{m}|=o(1)$. Note that by (14), the true
complexity is at most the CS-complexity. Gowers and Wolf [GW11] fully
characterized the true complexity of systems of linear forms, provided that
the field size is not too small. Let
$L=\lambda_{1}x_{1}+\ldots+\lambda_{d}x_{d}$ be a linear form in $d$
variables. We identify
$L\equiv(\lambda_{1},\ldots,\lambda_{d})\in\mathbb{F}^{d}$, and define the
$k$-th tensor power of $L$ by

$L^{k}=\left(\prod_{j=1}^{k}\lambda_{i_{j}}:i_{1},\ldots,i_{k}\in[d]\right)\in\mathbb{F}^{d^{k}}.$

######  Theorem 3.8 ([GW11]).

Let $\mathcal{L}=(L_{1},\ldots,L_{m})$ be a system of linear forms of CS-
complexity at most $|\mathbb{F}|$. The _true complexity_ of $\mathcal{L}$ is
the least integer $k\geq 1$ such that the forms
$L_{1}^{k+1},\ldots,L_{m}^{k+1}$ are linearly independent.

1.14 shows that if the true complexity of $\mathcal{L}$ is larger than $1$,
then there are sets $A$ with density $\alpha$ that are combinatorially spread
with extremely good parameters, and yet,
$t_{\mathcal{L}}(A)\not\approx\alpha^{m}$.

See 1.14

###### Proof.

Let $\mathbf{e}_{\mathbb{F}}\colon\mathbb{F}\to\mathbb{C}$ be an arbitrary
non-trivial character of the additive group of $\mathbb{F}$. Concretely, if we
identify $\mathbb{F}$ with $\\{0,\dots,q-1\\}$, then we can take
$\mathbf{e}_{\mathbb{F}}(x)=e^{\frac{2\pi i}{|\mathbb{F}|}x}$. For a given
$\rho=(\rho_{1},\ldots,\rho_{m})\in\mathbb{F}^{m}$, let

$\Delta_{\rho}\coloneqq\left|\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}\sim\mathbb{F}^{d}\\\
\mathbf{y}\sim\mathbb{F}^{d}\end{subarray}}\mathbf{e}_{\mathbb{F}}\left(\sum_{i=1}^{m}\rho_{i}L_{i}(\mathbf{x})L_{i}(\mathbf{y})\right)\right|.$

##### Estimating $\Delta_{\rho}$.

Let $\Gamma$ be the set of all
$\rho=(\rho_{1},\ldots,\rho_{m})\in\mathbb{F}^{m}$ such that

$\sum_{i=1}^{m}\rho_{i}L_{i}^{2}\equiv 0.$

Hence, if $\rho\in\Gamma$, we have $\Delta_{\rho}=1$. Next, we show that if
$\rho\in\mathbb{F}^{m}\backslash\Gamma$, then
$\Delta_{\rho}\leq\frac{1}{\sqrt{|\mathbb{F}|}}$. Note that,

$\displaystyle\sum_{i=1}^{m}\rho_{i}L_{i}(x)L_{i}(y)=$
$\displaystyle\sum_{i=1}^{m}\rho_{i}\sum_{a,b=1}^{d}\lambda_{ia}\lambda_{ib}x_{a}y_{b}$
$\displaystyle=$
$\displaystyle\sum_{a,b=1}^{d}\left(\sum_{i=1}^{m}\rho_{i}\lambda_{ia}\lambda_{ib}\right)x_{a}y_{b}$

For $\rho\in\mathbb{F}^{m}\backslash\Gamma$, since

$0\not\equiv\sum_{i=1}^{m}\rho_{i}L_{i}^{2}=\left(\sum_{i=1}^{m}\rho_{i}\lambda_{ia}\lambda_{ib}:a,b\in[d]\right),$

there are $a,b$ such that

$\alpha\coloneqq\sum_{i=1}^{m}\rho_{i}\lambda_{ia}\lambda_{ib}\not\neq 0.$

Therefore, for every fixed assignment to the variables
$\\{x_{i}:i\in[d]\backslash\\{a\\}\\}\cup\\{y_{i}:i\in[d]\backslash\\{b\\}\\}$,
there exist $\beta,\gamma,\psi\in\mathbb{F}$ such that

$\sum_{i=1}^{m}\rho_{i}L_{i}(x)L_{i}(y)=\alpha x_{a}y_{b}+\beta x_{a}+\gamma
y_{b}+\psi.$

By the standard Gauss sum estimate [GW11, Lemma 3.1], we have

$\left|\operatorname{\mathbb{E}}_{\mathbf{x}_{a},\mathbf{x}_{b}\in\mathbb{F}}\mathbf{e}_{\mathbb{F}}\Bigg{(}\alpha\mathbf{x}_{a}\mathbf{x}_{b}+\beta\mathbf{x}_{a}+\gamma\mathbf{x}_{b}+\psi\Bigg{)}\right|\leq\frac{1}{\sqrt{|\mathbb{F}|}}.$

Averaging over all assignments to
$\\{x_{i}:i\in[d]\backslash\\{a\\}\\}\cup\\{y_{i}:i\in[d]\backslash\\{b\\}\\}$,
we obtain

$\displaystyle\Delta_{\rho}\leq\frac{1}{\sqrt{|\mathbb{F}|}}.$

##### Constructing a spread function $f$.

Define $f\colon\mathbb{F}^{n}\to[0,1]$, as

$f(x)\coloneqq G(Q(x)).$

where $G\colon\mathbb{F}\to[0,1]$ is defined as

$G(z)\coloneqq\frac{1}{2}+\sum_{0\neq\gamma\in\mathbb{F}}\frac{1}{2|\mathbb{F}|}\mathbf{e}_{\mathbb{F}}(\gamma
z),$

and $Q\colon\mathbb{F}^{n}\to\mathbb{F}$ as
$Q(y)=y_{1}y_{2}+y_{3}y_{4}+\cdots+y_{n-1}y_{n}$, where $n$ is some even
number. The distribution of $Q(\mathbf{x})$ approaches the uniform
distribution as $n\to\infty$, and in particular,
$\operatorname{\mathbb{E}}[f]$ approaches
$\operatorname{\mathbb{E}}[G]\geq\frac{1}{2}$. Using the Fourier transform of
$G$, we have

$f(x)=\sum_{\gamma\in\mathbb{F}}\widehat{G}(\gamma)\mathbf{e}_{\mathbb{F}}(\gamma
Q(x)).$

For $x_{1},\ldots,x_{d}\in\mathbb{F}^{n}$, we have

$\prod_{i=1}^{m}f\left(L_{i}(x_{1},\ldots,x_{d})\right)=\prod_{i=1}^{m}f\left(\sum_{j=1}^{d}\lambda_{ij}x_{j}\right).$

By substituting the Fourier transform of $G$ and expanding it, the above
equals

$\sum_{\rho\in\mathbb{F}^{m}}\widehat{G}(\rho_{1})\cdots\widehat{G}(\rho_{m})\mathbf{e}_{\mathbb{F}}\left(\sum_{i=1}^{m}\rho_{i}Q\left(\sum_{j=1}^{d}\lambda_{ij}x_{j}\right)\right).$

By the definition of $Q$, we have

$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{x}_{1},\ldots,\mathbf{x}_{d}\sim\mathbb{F}^{n}}\mathbf{e}_{\mathbb{F}}\left(\sum_{i=1}^{m}\rho_{i}Q\left(\sum_{j=1}^{d}\lambda_{ij}\mathbf{x}_{j}\right)\right)$
$\displaystyle=\left(\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}_{1},\ldots,\mathbf{x}_{d}\sim\mathbb{F}\\\
\mathbf{y}_{1},\ldots\mathbf{y}_{d}\sim\mathbb{F}\end{subarray}}\mathbf{e}_{\mathbb{F}}\left(\sum_{i=1}^{m}\rho_{i}\left(\sum_{j=1}^{d}\lambda_{ij}\mathbf{x}_{j}\right)\left(\sum_{j=1}^{d}\lambda_{ij}\mathbf{y}_{j}\right)\right)\right)^{n/2}$
$\displaystyle=\Delta_{\rho}^{n/2}=\begin{cases}1&\text{if }\rho\in\Gamma,\\\
\leq\left(\frac{1}{\sqrt{|\mathbb{F}|}}\right)^{n/2}&\text{if
}\rho\not\in\Gamma,\end{cases}$

which shows that

$t_{\mathcal{L}}(f)\coloneqq\operatorname{\mathbb{E}}\left[\prod_{i=1}^{m}f(L_{i}(\mathbf{x}_{1},\ldots,\mathbf{x}_{d}))\right]=\sum_{\rho\in\Gamma}\widehat{G}(\rho_{1})\cdots\widehat{G}(\rho_{m})\pm
O\left(|\mathbb{F}|^{-n/4}\right).$

Note that $\widehat{G}(\gamma)\geq\frac{1}{2|\mathbb{F}|}$ for all
$\gamma\in\mathbb{F}$. Moreover, since the true complexity of $\mathcal{L}$ is
at least $2$, $L_{1}^{2},\ldots L_{m}^{2}$ are linearly _dependent_ and so
$\Gamma$ contains at least one non-zero element. Therefore, the positivity of
$\widehat{G}$ implies that for large enough $n$,

$t_{\mathcal{L}}(f)=\operatorname{\mathbb{E}}[G]^{m}+\sum_{\rho\in\Gamma\backslash\\{0\\}}\widehat{G}(\rho_{1})\cdots\widehat{G}(\rho_{m})\pm
O\left(|\mathbb{F}|^{-n/4}\right)=\operatorname{\mathbb{E}}[f]^{m}+\Omega(1).$
(15)

Next, note that for every non-zero $\chi\in\mathbb{F}^{n}$, by the standard
Gauss sum estimate [GW11, Lemma 3.1],

$|\widehat{f}(\chi)|=\left|\sum_{\gamma\in\mathbb{F}}\widehat{G}(\gamma)\operatorname{\mathbb{E}}_{\mathbf{x}}\mathbf{e}_{\mathbb{F}}\left(\gamma
Q(\mathbf{x})-\chi(\mathbf{x})\right)\right|\leq e^{-\Omega(n)}.$

Hence, denoting $\beta\coloneqq\operatorname{\mathbb{E}}[f]=\widehat{f}(0)$,

$\max_{\chi\neq 0}|\widehat{f}(\chi)|=\|\widehat{f-\beta}\|_{\infty}\leq
e^{-\Omega(n)},$

which implies that for $S,T\subseteq\mathbb{F}^{n}$, we have

$\displaystyle\left|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}}\mathbf{1}_{S}(\mathbf{x})(f(\mathbf{x}+\mathbf{y})-\beta)\mathbf{1}_{T}(\mathbf{y})\right|$
$\displaystyle=\left|\sum_{\chi\neq
0}\widehat{\mathbf{1}_{S}}(\chi)\widehat{f}(-\chi)\widehat{\mathbf{1}_{T}}(\chi)\right|\leq\left(\max_{\chi\neq
0}|\widehat{f}(\chi)|\right)\sum_{\chi}|\widehat{\mathbf{1}_{S}}(\chi)\widehat{\mathbf{1}_{T}}(\chi)|$
$\displaystyle\leq\|\widehat{f-\beta}\|_{\infty}\|\mathbf{1}_{S}\|_{2}\|\mathbf{1}_{T}\|_{2}\leq
e^{-\Omega(n)}\|\mathbf{1}_{S}\|_{2}\|\mathbf{1}_{T}\|_{2}=\frac{e^{-\Omega(n)}\sqrt{|S||T|}}{|\mathbb{F}|^{n}}.$

For an appropriate constant $c>0$, if $|S|,|T|\geq|\mathbb{F}|^{n-cn}$, then

$\left|\beta-\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}\sim S\\\
\mathbf{y}\sim
T\end{subarray}}f(\mathbf{x}+\mathbf{y})\right|\leq\frac{|\mathbb{F}|^{2n}}{|S||T|}\times\frac{e^{-\Omega(n)}\sqrt{|S||T|}}{|\mathbb{F}|^{n}}=\frac{e^{-\Omega(n)}|\mathbb{F}|^{n}}{\sqrt{|S||T|}}=e^{-\Omega(n)}.$

##### Converting $f$ to a set $A\subset\mathbb{F}^{n}$.

To convert $f$ to a subset $A\subseteq\mathbb{F}^{n}$, we pick a random subset
$\mathbf{A}\subseteq\mathbb{F}^{n}$ by including every element
$x\in\mathbf{A}$ with probability $f(x)$. Note that

$|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}}\mathbf{1}_{S}(\mathbf{x})(f(\mathbf{x}+\mathbf{y})-\mathbf{1}_{\mathbf{A}}(\mathbf{x}+\mathbf{y}))\mathbf{1}_{T}(\mathbf{y})|\leq\|\mathbf{1}_{S}\|_{2}\|\mathbf{1}_{T}\|_{2}\|\widehat{f-\mathbf{1}_{\mathbf{A}}}\|_{\infty}=\frac{|\mathbb{F}|^{2n}}{|S||T|}\|\widehat{f-\mathbf{1}_{\mathbf{A}}}\|_{\infty}.$
(16)

For every $\chi\in\mathbb{F}^{n}$, we have

$\widehat{\mathbf{1}_{\mathbf{A}}}(\chi)=\frac{1}{|\mathbb{F}^{n}|}\sum_{x\in\mathbb{F}^{n}}\mathbf{1}_{\mathbf{A}}(x)\mathbf{e}_{\mathbb{F}}(x\cdot\chi),$

and

$\operatorname{\mathbb{E}}_{\mathbf{A}}\widehat{\mathbf{1}_{\mathbf{A}}}(\chi)=\widehat{f}(\chi).$

Set $t\coloneqq|\mathbb{F}|^{2n/3}$. By Hoeffding’s inequality,

$\Pr_{\mathbf{A}}\left[\left|\widehat{\mathbf{1}_{\mathbf{A}}}(\chi)-\widehat{f}(\chi)\right|\geq\frac{t}{|\mathbb{F}|^{n}}\right]\leq
2\exp(-\frac{2t^{2}}{4|\mathbb{F}|^{n}}),$

and so, by the union bound,

$\Pr_{\mathbf{A}}\left[\|\widehat{f-\mathbf{1}_{\mathbf{A}}}\|_{\infty}\geq\frac{t}{|\mathbb{F}|^{n}}\right]\leq
2\exp(-\frac{2t^{2}}{4|\mathbb{F}|^{n}})|\mathbb{F}|^{n}=o(1).$

In particular, by (16) and the choice of $t$, with probability $1-o(1)$, the
set $\mathbf{A}$ has the following two properties:

  * (i)

$\operatorname{\mathbb{E}}[\mathbf{1}_{\mathbf{A}}]=\operatorname{\mathbb{E}}[f]\pm
e^{-\Omega(n)}$, and in particular
$\operatorname{\mathbb{E}}[\mathbf{1}_{\mathbf{A}}]\geq 1/3$.

  * (ii)

For every $|S|,|T|\geq|\mathbb{F}|^{n-cn}$, we have

$\left|\operatorname{\mathbb{E}}[f]-\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}\sim
S\\\ \mathbf{y}\sim
T\end{subarray}}\mathbf{1}_{A}(\mathbf{x}+\mathbf{y})\right|\leq
e^{-\Omega(n)}.$

Next, we consider $|t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)|$. First,
note that by the definition of $\mathbf{A}$, we have

$\displaystyle|\operatorname{\mathbb{E}}_{\mathbf{A}}\left[t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right]|$
$\displaystyle=\left|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{A}}\left[\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(\mathbf{x}))\right]-\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\prod_{i=1}^{m}f(L_{i}(\mathbf{x}))\right]\right|$

Observe that if, for a given $x$, all $L_{i}(x)$’s are distinct, then

$\operatorname{\mathbb{E}}_{\mathbf{A}}\left[\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(x))\right]-\prod_{i=1}^{m}f(L_{i}(x))=0.$

Hence,

$\displaystyle|\operatorname{\mathbb{E}}_{\mathbf{A}}\left[t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right]|$
$\displaystyle=\left|\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{A}}\left[\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(\mathbf{x}))\right]-\operatorname{\mathbb{E}}_{\mathbf{x}}\left[\prod_{i=1}^{m}f(L_{i}(\mathbf{x}))\right]\right|$
$\displaystyle\leq\Pr_{\mathbf{x}}\left[\exists i\neq j\text{ s.t.
}L_{i}(\mathbf{x})=L_{j}(\mathbf{x})\right]\leq m^{2}|\mathbb{F}|^{-n}.$

Moreover,

$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{A}}\left|t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right|^{2}$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{A}}\left[t_{\mathcal{L}}(\mathbf{A})^{2}-t_{\mathcal{L}}(\mathbf{A})t_{\mathcal{L}}(f)\right]-t_{\mathcal{L}}(f)\operatorname{\mathbb{E}}_{\mathbf{A}}\left[t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right]$
$\displaystyle\leq\left|\operatorname{\mathbb{E}}_{\mathbf{A}}\operatorname{\mathbb{E}}_{\mathbf{x},\mathbf{y}}\left[\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(\mathbf{x}))\mathbf{1}_{\mathbf{A}}(L_{i}(\mathbf{y}))-\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(\mathbf{x}))f(L_{i}(\mathbf{y}))\right]\right|+m^{2}|\mathbb{F}|^{-n}.$

Note that for $x,y\in(\mathbb{F}^{n})^{d}$, if
$L_{1}(x),\ldots,L_{m}(x),L_{1}(y),\ldots,L_{m}(y)$ are distinct, then

$\operatorname{\mathbb{E}}_{\mathbf{A}}\left[\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(x))\mathbf{1}_{\mathbf{A}}(L_{i}(y))-\prod_{i=1}^{m}\mathbf{1}_{\mathbf{A}}(L_{i}(x))f(L_{i}(y))\right]=0.$

Hence,

$\displaystyle\operatorname{\mathbb{E}}_{\mathbf{A}}\left|t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right|^{2}$
$\displaystyle\leq\Pr_{\mathbf{x},\mathbf{y}}[L_{1}(\mathbf{x}),\ldots,L_{m}(\mathbf{x}),L_{1}(\mathbf{y}),\ldots,L_{m}(\mathbf{y})\text{
are not distinct}]+m^{2}|\mathbb{F}|^{-n}$ $\displaystyle\leq
4m^{2}|\mathbb{F}|^{-n}.$

Therefore, Markov’s inequality implies that

$\Pr_{\mathbf{A}}[\left|t_{\mathcal{L}}(\mathbf{A})-t_{\mathcal{L}}(f)\right|\geq|\mathbb{F}|^{-n/3}]=o(1),$

which, in combination with (15), shows that, with probability $1-o(1)$, the
set $\mathbf{A}$ satisfies

  * (iii)

$t_{\mathcal{L}}(\mathbf{A})=\operatorname{\mathbb{E}}[f]^{m}+\Omega(1)$.

Since with high probability the random set $\mathbf{A}$ satisfies (i), (ii),
(iii), there exists a set satisfying these three properties. ∎

##  4 Concluding remarks

The most natural problem left open by our work is whether one can remove the
requirement of $2$-degeneracy from 1.8. We needed to assume $2$-degeneracy
since we do not know whether in Lemma 2.7 it is possible to sift a subspace
from the assumption that the $U(k,p)$ norm is large for some $k>2$. The key
novel element in Kelley and Meka’s proof of Lemma 2.7 is a dependent random
choice argument. Afterwards, one can easily apply the almost-periodicity
results of [SS16] to sift a subspace. We show in Proposition 4.1 below (proved
in Section 4.1) that their dependent random choice argument generalizes to all
$U(k,p)$ norms. What remains unclear is whether it is possible to apply the
almost periodicity argument for $k>2$ to sift a subspace from the assertion of
Proposition 4.1.

######  Proposition 4.1 (Dependent Random Choice).

Suppose $A\subseteq\mathbb{F}^{n}$ satisfies
$\operatorname{\mathbb{E}}\mathbf{1}_{A}=\alpha$ and the function
$f\colon\mathbb{F}^{n}\times\mathbb{F}^{n}\to\\{0,1\\}$ defined as
$f(x,y)=\mathbf{1}_{A}(x+y)$ satisfies

$\|f\|_{U(k,p)}\geq(1+\epsilon)\alpha,$

where $0<\epsilon<1$ and $p\geq\Omega(\log(1/\epsilon))$.

Then there exists a set $B\subseteq\mathbb{F}^{n}$ with density
$\beta\geq\frac{\alpha^{p}}{2}$ such that

$\Pr_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\sim
B}\left[\operatorname{\mathbb{E}}_{\mathbf{y}}\mathbf{1}_{A}(\mathbf{x}_{1}+\mathbf{y})\cdots\mathbf{1}_{A}(\mathbf{x}_{k}+\mathbf{y})>\left(1+\frac{\epsilon}{2}\right)\alpha^{k}\right]\geq
1-\frac{\epsilon}{100}.$

To remove the $2$-degeneracy requirement from 1.8, it suffices to give a
positive answer to the following question.

######  Question 4.2.

Let $k$ be a fixed constant, and let $A$ and $B$ be subsets of
$\mathbb{F}^{n}$ with densities $\alpha$ and $\beta$, respectively. Suppose
that

$\Pr_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\sim
B}\left[\operatorname{\mathbb{E}}_{\mathbf{y}}\mathbf{1}_{A}(\mathbf{x}_{1}+\mathbf{y})\cdots\mathbf{1}_{A}(\mathbf{x}_{k}+\mathbf{y})>\left(1+\frac{\epsilon}{2}\right)\alpha^{k}\right]\geq
1-\frac{\epsilon}{100}.$

Is there an affine subspace $V\subseteq\mathbb{F}^{n}$ of codimension
$\lesssim\log^{O(1)}(1/\alpha\beta)$ such that

$\operatorname{\mathbb{E}}_{\mathbf{x}\sim
V}\mathbf{1}_{A}(\mathbf{x})\geq(1+\Omega(\epsilon))\alpha?$

###  4.1 Proof of Proposition 4.1

By the assumption $\|f\|_{U(k,p)}\geq(1+\epsilon)\alpha$, we have

$\|f\|_{U(k,p)}^{kp}=\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\\\
\mathbf{y}_{1},\ldots,\mathbf{y}_{p}\end{subarray}}\prod_{i=1}^{k}\prod_{j=1}^{p}\mathbf{1}_{A}(\mathbf{x}_{i}+\mathbf{y}_{j})\geq(1+\epsilon)^{pk}\alpha^{pk}.$

Denote $\vec{x}=(x_{1},\ldots,x_{k})$ and $\vec{y}=(y_{1},\ldots,y_{p})$, and
let

$\mathcal{A}(\vec{x},\vec{y})\coloneqq\prod_{i=1}^{k}\prod_{j=1}^{p}\mathbf{1}_{A}(x_{i}+y_{j}).$

Define

$B_{\vec{y}}\coloneqq\\{x:x+y_{1},\dots,x+y_{k}\in
A\\}=\bigcap_{i=1}^{k}(A-y_{i}),$

and denote the density of $B_{\vec{y}}$ by
$\beta_{\vec{y}}\coloneqq\Pr_{\mathbf{x}}[\mathbf{x}\in B_{\vec{y}}]$. We have

$(1+\epsilon)^{pk}\alpha^{pk}\leq\operatorname{\mathbb{E}}_{\vec{\mathbf{x}},\vec{\mathbf{y}}}\mathcal{A}(\vec{x},\vec{y})=\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}\left(\operatorname{\mathbb{E}}_{\mathbf{x}}\prod_{j=1}^{p}\mathbf{1}_{A}(\mathbf{x}+\mathbf{y}_{j})\right)^{k}=\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}[\beta_{\vec{\mathbf{y}}}^{k}].$

We will only be interested in those $\vec{y}$ where $B_{\vec{y}}$ is not very
small. Let

$\Gamma=\left\\{\vec{y}\in(\mathbb{F}^{n})^{p}:\beta_{\vec{y}}>\frac{\alpha^{p}}{2}\right\\}.$

We have

$\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}\left[\mathbf{1}_{\Gamma}(\vec{\mathbf{y}})\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\left[\mathcal{A}(\vec{\mathbf{x}},\vec{\mathbf{y}})\right]\right]=\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}\mathbf{1}_{\Gamma}(\vec{\mathbf{y}})\beta_{\vec{\mathbf{y}}}^{k}\geq(1+\epsilon)^{pk}\alpha^{pk}-\frac{\alpha^{pk}}{2^{k}}\geq\frac{(1+\epsilon)^{pk}\alpha^{pk}}{2}.$
(17)

Next, define

$\mathbf{1}_{A}^{\circ
k}(\vec{x})=\operatorname{\mathbb{E}}_{\mathbf{y}}\mathbf{1}_{A}(x_{1}+\mathbf{y})\cdots\mathbf{1}_{A}(x_{k}+\mathbf{y}),$

and let

$S\coloneqq\left\\{\vec{x}\in\mathbb{F}^{k}:\mathbf{1}_{A}^{\circ
k}(\vec{x})<\left(1+\frac{2\epsilon}{3}\right)\alpha^{k}\right\\}.$

Note that

$\operatorname{\mathbb{E}}_{\vec{\mathbf{x}},\vec{\mathbf{y}}}\mathcal{A}(\vec{x},\vec{y})=\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\left[\mathbf{1}_{A}^{\circ
k}(\vec{\mathbf{x}})^{p}\right],$

and

$\operatorname{\mathbb{E}}_{\vec{\mathbf{x}},\vec{\mathbf{y}}}\mathcal{A}(\vec{x},\vec{y})\mathbf{1}_{S}(\vec{\mathbf{x}})=\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\left[\mathbf{1}_{S}(\vec{\mathbf{x}})\cdot\mathbf{1}_{A}^{\circ
k}(\vec{\mathbf{x}})^{p}\right]\leq\left(1+\frac{2\epsilon}{3}\right)^{p}\alpha^{pk}.$
(18)

Putting (17) and (18) together gives

$\frac{\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{\mathbf{y}})\mathbf{1}_{S}(\vec{\mathbf{x}})}{\operatorname{\mathbb{E}}_{\vec{\mathbf{y}}}\mathbf{1}_{\Gamma}(\vec{\mathbf{y}})\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{\mathbf{y}})}\leq\frac{2(1+\frac{2\epsilon}{3})^{p}}{(1+\epsilon)^{kp}}$

In particular, there exists a choice of $\vec{y}\in\Gamma$ such that

$\frac{\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{y})\mathbf{1}_{S}(\vec{\mathbf{x}})}{\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{y})}\leq\frac{2(1+\frac{2\epsilon}{3})^{p}}{(1+\epsilon)^{kp}}\leq\frac{\epsilon}{100},$

for sufficiently large $p=O(1)$. Now note that
$\mathcal{A}(\vec{x},\vec{y})=1$ iff $x_{1},\ldots,x_{k}\in B_{\vec{y}}$, and
thus

$\frac{\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{y})\mathbf{1}_{S}(\vec{\mathbf{x}})}{\operatorname{\mathbb{E}}_{\vec{\mathbf{x}}}\mathcal{A}(\vec{\mathbf{x}},\vec{y})}=\Pr_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\sim
B_{\vec{y}}}[\vec{x}\in S].$

We set $B\coloneqq B_{\vec{y}}$. Since $\vec{y}\in\Gamma$, the density of $B$
is $\beta\coloneqq\beta_{\vec{y}}\geq\alpha^{p}/2$, as desired. Moreover,

$\displaystyle\operatorname{\mathbb{E}}_{\begin{subarray}{c}\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\sim
B\\\
\mathbf{y}\sim\mathbb{F}^{n}\end{subarray}}\prod_{i}^{k}\mathbf{1}_{A}(\mathbf{x}_{i}+\mathbf{y})$
$\displaystyle=\operatorname{\mathbb{E}}_{\mathbf{x}_{1},\ldots,\mathbf{x}_{k}\sim
B}\mathbf{1}_{A}^{\circ k}(\vec{\mathbf{x}})\geq\Pr_{\vec{\mathbf{x}}\sim
B}[\vec{\mathbf{x}}\not\in S]\left(1+\frac{2\epsilon}{3}\right)\alpha^{k}$
$\displaystyle\geq\left(1-\frac{\epsilon}{100}\right)\left(1+\frac{2\epsilon}{3}\right)\alpha^{k}\geq\left(1+\frac{\epsilon}{2}\right)\alpha^{k}.\qed$

## References

  * [BS23a] Thomas F. Bloom and Olof Sisask.  An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, 2023.
  * [BS23b] Thomas F. Bloom and Olof Sisask.  The Kelley–Meka bounds for sets free of three-term arithmetic progressions, 2023.
  * [CGW89] Fan R. K. Chung, Ronald L. Graham, and Richard M. Wilson.  Quasi-random graphs.  Combinatorica, 9:345–362, 1989.
  * [EFR86] P. Erdős, P. Frankl, and V. Rödl.  The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.  Graphs Combin., 2(2):113–121, 1986.
  * [EG17] Jordan S. Ellenberg and Dion Gijswijt.  On large subsets of $\mathbb{F}^{n}_{q}$ with no three-term arithmetic progression.  Ann. of Math. (2), 185(1):339–343, 2017.
  * [FK78] Hillel Furstenberg and Yitzhak Katznelson.  An ergodic Szemerédi theorem for commuting transformations.  Journal d’Analyse Mathématique, 34(1):275–291, 1978.
  * [Gow01] W. T. Gowers.  A new proof of Szemerédi’s theorem.  Geom. Funct. Anal., 11(3):465–588, 2001.
  * [Gow07] W. T. Gowers.  Hypergraph regularity and the multidimensional Szemerédi theorem.  Ann. of Math. (2), 166(3):897–946, 2007.
  * [GT08] Ben Green and Terence Tao.  An inverse theorem for the Gowers $U^{3}(G)$ norm.  Proc. Edinb. Math. Soc. (2), 51(1):73–153, 2008.
  * [GT10] Benjamin Green and Terence Tao.  Linear equations in primes.  Annals of mathematics, pages 1753–1850, 2010.
  * [GW10] W. T. Gowers and J. Wolf.  The true complexity of a system of linear equations.  Proc. Lond. Math. Soc. (3), 100(1):155–176, 2010.
  * [GW11] W. T. Gowers and J. Wolf.  Linear forms and higher-degree uniformity for functions on $\mathbb{F}^{n}_{p}$.  Geom. Funct. Anal., 21(1):36–69, 2011.
  * [KLM23] Zander Kelley, Shachar Lovett, and Raghu Meka.  Explicit separations between randomized and deterministic number-on-forehead communication, 2023.
  * [KM23] Zander Kelley and Raghu Meka.  Strong bounds for 3-progressions.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023.
  * [Mes95] Roy Meshulam.  On subsets of finite abelian groups with no 3-term arithmetic progressions.  Journal of Combinatorial Theory, Series A, 71(1):168–172, 1995\.
  * [MS19] Guy Moshkovitz and Asaf Shapira.  A tight bound for hypergraph regularity.  Geom. Funct. Anal., 29(5):1531–1578, 2019.
  * [Rot53] Klaus F Roth.  On certain sets of integers.  J. London Math. Soc, 28(104-109):3, 1953.
  * [RS78] I. Z. Ruzsa and E. Szemerédi.  Triple systems with no six points carrying three triangles.  In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloq. Math. Soc. János Bolyai, pages 939–945. North-Holland, 1978.
  * [SS16] Tomasz Schoen and Olof Sisask.  Roth’s theorem for four variables and additive structures in sums of sparse sets.  Forum Math. Sigma, 4:Paper No. e5, 28, 2016.
  * [Sze75] Endre Szemerédi.  On sets of integers containing no $k$ elements in arithmetic progression.  Acta Arith, 27(199-245):2, 1975.


##  1 Materials & Methods

###  1.1 Materials

The MRS dataset used in this study was obtained by St. George’s University
London and consisted of a single-voxel MRS training and testing set. Both the
test and training sets were acquired using a GE Signa Horizon 1.5T MR system
with a Repetition Time (TR) and a short Echo Time (TE) of 2000ms and 30ms
respectively. A Point-Resolved spectroscopic sequence protocol was used to
acquire the training and test dataset. The World Health Organization
classifies tumours into 4 grades (WHO)
[centre_international_de_recherche_sur_le_cancer_pathology_2004]: Grades I -
IV, with GI and GII being deemed low grade tumors and GIII and GIV said to be
high grade, malignant tumors. The composition of the training and test dataset
was 137 samples. Of the training set 70 were classified as healthy tissue, 20
as GII (low grade), 10 as GIII and 20 GIV (high grade). The test set consisted
of 9 healthy, 3 low grade and 5 high grade which were taken through random
sampling of the entire dataset prior to training. Due to the similarity
between GIII and GIV tumour tissue in MRS imaging, the GIII data was merged
with the GIV data by labelling each as high grade. Figure 1 illustrates MRS
spectra of different grades.

Healthy Data.  Low Grade Data.  High Grade Data.

Figure 1: Illustration of the MRS spectra grouped into 1 healthy (green), 1
low grade (blue) and 1 high grade (red) tumor tissue. Peaks correspond to
metabolites in the region of interest.

The positioning for every scan captured in the dataset was placed on a
homogeneous, representative tumor region determined by an expert using post-Gd
contrast T1w, T2w and FLAIR structural contrast images alongside the relevant
histopathological information. This was to ensure accuracy within the training
data and that there was a heterogeneity of MRS characteristics represented
within each voxel scanned. The individual labels for the data were achieved
via the diagnosis of a biopsy by a practiced physician in which the clinical,
radiological and histopathological information of each patient was
incorporated to the diagnosis.

The nature of MRS data is high-dimensional (of roughly 1,024 dimensions) thus
a reduction with Principal Component Analysis (PCA) was applied to explore the
data, see Figure 2. Clustering with k-means results in a good separation of
the classes, especially between healthy and high grade tissue (Figure 2).

PCA applied with two components.  K-means clustering applied.

Figure 2: Application of PCA to the MRS dataset with the first two components
used 2 followed by k-means clustering 2.

###  1.2 Methods

This study took a three step approach. First, three different models (GAN,
DCGAN and a generative adaptation of PMM) were used to generated synthetic MRS
images based off of the training -MRS- dataset. Second, these samples were
then each used to train a Random Forest to be able to classify MRS images as
either healthy, low or high grade tissue. Finally, the results from the Random
Forest classifiers were then analyzed and the synthetic data from the
generative models were compared against the mean signal of the training
dataset classes.

The GAN model used in this study, based on [goodfellow_generative_2014], had a
generator comprised of a fully connected input layer which accepted a random
value vector of size 100, with a hidden layer of 1,024 nodes in size using
rectified exponential linear (ReLU) [nair_rectified_2010] as the activation
function with the output layer having 1,024 nodes but utilizing TanH
[agostinelli_learning_2014] as the activation function. The discriminator
consisted of a linear input layer which took in an MRS image of 1,024 values,
followed by a hidden layer consisting of 1,024 nodes using LeakyReLU
[agostinelli_learning_2014] as the activation function, the output layer was a
singular sigmoidal node [rumelhart_learning_1986] activation. The full model
was trained on each class of tissue for over 150,000 epochs using the Adam
optimizer [kingma_adam:_2014].

Compared to GANs, DCGANs use a deeper learning architecture which normally
requires more data. To try and generate more expressive and domain accurate
data, alterations were required to the training of the network to accommodate
the limited data. The training process was modified to not take random batch
samples but to deliberately take the full set of the data available for
training at each epoch. The samples were then normalized with batch
normalization. The architecture for the generator used in the study was a
fully connected input layer comprised of 2048 nodes followed by four
transposed one-dimensional convolutional layers using LeakyReLU as the
activation function for all but the output layer which used TanH. The
discriminator was the inverse with the first four layers being one-dimensional
convolutions (using LeakyReLU as the activation function) followed by a single
Sigmodial output node. Similar to the GAN model the DCGAN model was trained
for at least 250,000 epochs on each tissue class.

GANs are a non-linear method for the generation of data which, theoretically,
should lead to more expressive data over that of more linear methods but to do
so requires larger amounts of training data. To test the benefits, a
comparison to a linear based generator in the study was required. For medical
imaging data, factors such as patient orientation and relationship between
values matters. Therefore, testing requires a method which can generate data
that adheres to the domain. The selected method for this study was the
Pairwise Mixture Model.

The Pairwise Mixture Model (PMM) [olliverre_pairwise_2017] is a model for
representing different brain tissue from MRS images and based on the work by
asad_supervised_2016 asad_supervised_2016, the purpose of which was to solve
the problem of the heterogeneity of tissue types found within multi-voxel MRS
images. The possible types were defined as normal, low (GI and GII type brain
tumour tissue) and high (GIII and GIV brain tumour tissue). Each tissue model
is expressed as a mean signal and the variation around the mean, calculated
from applying PCA to a labelled dataset of homogeneous MRS images each
relating to a specific grade. The models could then be as defined:

$m_{i}(t)=\mu_{i}(t)+\sum\alpha_{i}e_{ik}(t),$ (1)

where $\mu_{i}$ is the mean signal, $\alpha_{i}$ and $e_{i}$ respectively are
the alpha weight coefficients and eigenvectors - which encode the variation
around the mean signal - with K representing the number of eigenvectors
determined for model $m_{i}$. To calculate the amount of each tissue type
found within a certain voxel the assumption that each voxel was a weighted sum
of the possible tissue types gives the following:

$s(t)=w_{n}m_{n}(t)+w_{l}m_{l}(t)+w_{h}m_{h}(t),$ (2)

which can then be viewed as an optimization problem where:

$\displaystyle E=\int[x(t)-s(t)]^{2}dt+\int[\sum_{j}s(t)-s_{j}(t)]^{2}dt,$ (3)
with $j$ representing the available surrounding model signals of $s(t)$.

The estimated coefficients can be considered to represent the amount of each
tissue type (normal, low or high) found within a voxel.

By taking the models of the various tissue types from the PMM, it is
straightforward to see how by varying the value of the coefficients of the
models it is possible to create data that holds to the original domain. There
is a limit to the amount of possibly created data ($c^{3}$ where $c$
represents the coefficients) but it is still enough to train a classifier
model with a deep learning architecture, based on the generated data alone.

The testing of the generated data from each network used a set of simple,
shallow Random Forest classifiers which were constructed and trained on the
generated data from the GAN, DCGAN and the PMM generation method. A Random
Forest was also trained on the training dataset alone as a control set. The
Random Forest classifiers were then tested on the MRS image test set with the
classification accuracy results recorded and examined. Furthermore the
generated MRS images were compared to the mean signal from the training
dataset for comparison to determine the adherence to the domain and
possibility of expressiveness.