50 1. Higher order Fourier analysis

a common factor that divides the order of G). This count would then be

given by

|G|dΛΨ(1A,...,

1A)

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

L∞(G)

. . . ft

L∞(G)

where

f

L∞(G)

:= sup

x∈G

|f(x)|.

Remark 1.3.1. One can replace the

L∞

norm on fi in (1.25) with an

Lpi

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

L∞(G)

. . . ft

L∞(G)

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

L∞(G)

. . . 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 ∈

L∞(G)

with

|ΛΨ(f1,...,ft)| = f1

L∞(G)

. . . ft

L∞(G)