34 1. Higher order Fourier analysis
where B(x) is the unique atom of B that contains x. One can view the map
f → E(f|B) as the orthogonal projection from
is the space of functions f : [N] → C with the inner product
and L2(B) is the subspace of functions in L2([N]) which are measurable with
respect to B, or equivalently are constant on each atom of B.
We say that one factor B refines another B if B ⊂ B , or equivalently if
every atom of B is a union of atoms of B , or if every atom of B is contained
in an atom of B , or equivalently again if
). Given two factors
B, B , one can define their join B ∨ B to be their least common refinement,
thus the atoms in B ∨B are the non-empty intersections of atoms in B with
atoms in B .
The idea is to split a given function f in
(and specifically, an
indicator function 1A) into a projection E(f|B) onto a “structured factor”
B to obtain a “structured component” E(f|B), together with a “pseudoran-
dom component” f − E(f|B) that is essentially orthogonal to all structured
functions. This decomposition is related to the classical decomposition of a
vector in a Hilbert space into its orthogonal projection onto a closed sub-
space V , plus the complementary projection to the orthogonal complement
we will see the relationship between the two decompositions later when
we pass to the ultralimit.
We need to make the notion of “structured” more precise. We begin
with some definitions. We say that a function f : [N] → C has Fourier
complexity at most M if it can be expressed as
for some M ≤ M and some complex numbers c1,...,cM of magnitude at
most 1, and some real numbers α1,...,αM . Note that from the Fourier in-
version formula that every function will have some finite Fourier complexity,
but typically one expects the complexity to grow with N; only a few special
functions will have complexity bounded uniformly in N. Also note that if
f, g have Fourier complexity M, then f + g, f − g, f, or fg all have Fourier
complexity at most OM (1);
the space of bounded complexity
functions forms an algebra.
Ideally, we would like to take “functions of bounded Fourier complexity”
as our class of structured functions. For technical reasons (related to our
desire to use indicator functions as structured functions), we need to take
will be able to formalise this statement after we take ultralimits.