106 1. Higher order Fourier analysis

Theorem 1.6.14 (Inverse conjecture for the Gowers norms on Z). (See

[GrTaZi2010b].) Let f : [N] → C be such that f

L∞[N]

≤1 and f

Us+1[N]

≥ δ. Then |f, ψ L2([N])|

s,δ

1 for some degree ≤ s nilsequence of complex-

ity Os,δ(1).

An extensive heuristic discussion of how this conjecture is proven can

be found in [GrTaZi2010]; for the purposes of this text, we shall simply

accept this theorem as a black box. For a discussion of the history of the

conjecture, including the cases s ≤ 3; see [GrTaZi2009]. An alternate proof

to Theorem 1.6.14 was recently also established in [CaSz2010], [Sz2010b].

These methods are based on the proof of an analogous ergodic-theory result

to Theorem 1.6.14, namely the description of the characteristic factors for

the Gowers-Host-Kra semi-norms in [HoKr2005], which we will not discuss

here, except to say that one of the main ideas is to construct, and then study,

spaces analogous to the Host-Kra groups

HKk(G)

and Host-Kra nilmanifolds

HKk(G)/HKk(Γ)

associated to an arbitrary function f on a (limit-finite)

interval [N] (or of a function f on an ergodic measure-preserving system).

Exercise 1.6.21 (99% inverse theorem).

(i) (Straightening an approximately linear function) Let ε, κ 0. Let

ξ : [−N, N] → R/Z be a function such that |ξ(a+b)−ξ(a)−ξ(b)| ≤

κ for all but εN

2

of all a, b ∈ [−N, N] with a + b ∈ [−N, N]. If ε

is suﬃciently small, show that there exists an aﬃne linear function

n → αn + β with α, β ∈ R/Z such that |ξ(n) − αn − β|

ε

κ for

all but δ(ε)N values of n ∈ [−N, N], where δ(ε) → 0 as ε → 0.

(Hint: One can take κ to be small. First find a way to lift ξ in a

nice manner from R/Z to R.)

(ii) Let f : [N] → C be such that f

L∞[N]

≤ 1 and f

Us+1[N]

≥ 1−ε.

Show that there exists a polynomial P : Z → R/Z of degree ≤ s

such that f − e(P )

L2([N])

≤ δ, where δ = δs(ε) → 0 as ε → 0

(holding s fixed). Hint: Adapt the argument of the analogous

finite field statement. One cannot exploit the discrete nature of

polynomials any longer; and so one must use the preceding part of

the exercise as a substitute.

The inverse conjecture for the Gowers norms, when combined with the

equidistribution theory for nilsequences that we will turn to next, has a

number of consequences, analogous to the consequences for the finite field

analogues of these facts; see [GrTa2010b] for further discussion.

1.6.4. Equidistribution of nilsequences. In the subject of higher order

Fourier analysis and, in particular, in the proof of the inverse conjecture for

the Gowers norms, as well as in several of the applications of this conjecture,