50 1. Higher order Fourier analysis
a common factor that divides the order of G). This count would then be
where ΛΨ is the d-linear form
ΛΨ(f1,...,fd) := Ex∈Gd f1(ψ1(x)) . . . ft(ψt(x)).
For instance, the task of counting arithmetic progressions n, n + r, . . . , n +
(k−1)r corresponds to the case d = 2,t = k, and ψi(x1,x2) := x1 +(i−1)x2.
We have the trivial bound
(1.25) |ΛΨ(f1,...,ft)| ≤ f1
. . . ft
Remark 1.3.1. One can replace the
norm on fi in (1.25) with an
norm for various values of p1,...,pt. The set of all admissible p1,...,pt is de-
scribed by the Brascamp-Lieb inequality; see, for instance, [BeCaChTa2008]
for further discussion. We will not need these variants of (1.25).
Improving this trivial bound turns out to be a key step in the theory
of counting general linear patterns. In particular, it turns out that for any
ε 0, one usually has
|ΛΨ(f1,...,ft)| ε f1
. . . ft
except when f1,...,ft take a very special form (or at least correlate with
functions of a very special form, such as linear or higher order characters).
To reiterate: the key to the subject is to understand the inverse problem
of characterising those functions f1,...,fd for which one has
|ΛΨ(f1,...,ft)| ≥ ε f1
. . . ft L∞(G).
This problem is of most interest (and the most diﬃcult) in the “1% world”
when ε is small (e.g. ε = 0.01), but it is also instructive to consider the
simpler cases of the “99% world” when ε is very close to one (e.g. ε = 0.99),
or the “100% world” when ε is exactly equal to one. In these model cases
one can use additional techniques (error-correction and similar techniques
(often of a theoretical computer science flavour) in the 99% world, or exact
algebraic manipulation in the 100% world) to understand this expression.
Let us thus begin with analysing the 100% situation. Specifically, we
assume that we are given functions f1,...,ft ∈
|ΛΨ(f1,...,ft)| = f1
. . . ft