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

L2([N])

to

L2(B),

where

L2([N])

is the space of functions f : [N] → C with the inner product

f, g

L2([N])

:= En∈[N]f(n)g(n)

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

L2(B)

⊂

L2(B

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

L2([N])

(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

V

⊥;

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

f(n) =

M

m=1

cme(αmn)

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);

informally4,

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

4We

will be able to formalise this statement after we take ultralimits.