92 1. Higher order Fourier analysis

The above regularity lemma (or more precisely, a close relative of this

lemma) was also used in [GoWo2010b]:

Theorem 1.5.12 (Gowers-Wolf theorem [GoWo2010b]). Let Ψ =

(ψ1,...,ψt) be a collection of linear forms with integer coeﬃcients, with

no two forms being linearly dependent. Let F have suﬃciently large char-

acteristic, and suppose that f1,...,ft :

Fn

→ C are functions bounded in

magnitude by 1 such that

|ΛΨ(f1,...,ft)| ≥ δ

where ΛΨ was the form defined in Section 1.3. Then for each 1 ≤ i ≤ t

there exists a classical polynomial φi of degree at most d such that

|fi,e(φi) L2(Fn)|

d,Ψ,δ

1,

where d is the true complexity of the system Ψ as defined in Section 1.3.

This d is best possible.

1.6. The inverse conjecture for the Gowers norm II. The

integer case

In Section 1.5, we saw that the Gowers uniformity norms on vector spaces

Fn

were controlled by classical polynomial phases e(φ).

Now we study the analogous situation on cyclic groups Z/NZ. Here,

there is an unexpected surprise: the polynomial phases (classical or other-

wise) are no longer suﬃcient to control the Gowers norms U

s+1(Z/NZ)

once

s exceeds 1. To resolve this problem, one must enlarge the space of poly-

nomials to a larger class. It turns out that there are at least three closely

related options for this class: the local polynomials, the bracket polynomials,

and the nilsequences. Each of the three classes has its own strengths and

weaknesses, but in my opinion the nilsequences seem to be the most natural

class, due to the rich algebraic and dynamical structure coming from the

nilpotent Lie group undergirding such sequences. For reasons of space we

shall focus primarily on the nilsequence viewpoint here.

Traditionally, nilsequences have been defined in terms of linear orbits

n →

gnx

on nilmanifolds G/Γ; however, in recent years it has been realised

that it is convenient for technical reasons (particularly for the quantitative

“single-scale” theory) to generalise this setup to that of polynomial orbits

n → g(n)Γ, and this is the perspective we will take here.

A polynomial phase n → e(φ(n)) on a finite abelian group H is formed

by starting with a polynomial φ: H → R/Z to the unit circle, and then

composing it with the exponential function e: R/Z → C. To create a

nilsequence n → F (g(n)Γ), we generalise this construction by starting with