82 1. Higher order Fourier analysis

Now let φ be a classical polynomial of degree less than

2d−1.

By Lemma

1.5.5, we can partition F2

n

into aﬃne coordinate subspaces W of dimension

at least ωd(n) such that φ is a linear combination of S0,...,S2d−1−1 on each

such subspace. By the pigeonhole principle, we thus can find such a W such

that

|f, e(φ) L2(Fn)|

2

≤ |f, e(φ)

L2(W

)|.

On the other hand, from Exercise 1.5.4, the function φ on W depends only

on L mod

2d−1.

Now, as dim(W ) → ∞, the function L mod

2d

(which is es-

sentially the distribution function of a simple random walk of length dim(V )

on

Z/2dZ)

becomes equidistributed; in particular, for any a ∈

Z/2dZ,

the

function f will take the values

e(a/2d)

and

−e(a/2d)

with asymptotically

equal frequency on W , whilst φ remains unchanged. As such we see that

|f, e(φ)

L2(W

)

| → 0 as dim(W ) → ∞, and thus as n → ∞, and the claim

follows.

Exercise 1.5.5. With the same setup as the previous proposition, show that

e(S2d−1 /2)

Ud+1(Fn)

2

1, but that

e(S2d−1

/2),e(φ)

L2(Fn)

2

= on→∞;d(1)

for all classical polynomials φ of degree less than

2d−1.

1.5.3. The 1% inverse theorem: sketches of a proof. The proof of

Theorem 1.5.3 is rather diﬃcult once d ≥ 2; even the d = 2 case is not

particularly easy. However, the arguments still have the same cohomological

flavour encountered in the 99% theory. We will not give full proofs of this

theorem here, but indicate some of the main ideas.

We begin by discussing (quite non-rigorously) the significantly simpler

(but still non-trivial) d = 2 case, under the assumption of odd characteris-

tic, in which case we can use the arguments from [Go1998], [GrTa2008].

Unsurprisingly, we will take advantage of the d = 1 case of the theorem as

an induction hypothesis.

Let V =

Fn

for some field F of characteristic greater than 2, and let

f be a function with f

L∞(V

)

≤ 1 and f

U 3(V )

1. We would like to

show that f correlates with a quadratic phase function e(φ) (due to the

characteristic hypothesis, we may take φ to be classical), in the sense that

|f, e(φ)

L2(V

)| 1.

We expand f

8

U 3(V )

as Eh∈V Δhf

4

U 2(V )

. By the pigeonhole principle,

we conclude that

Δhf

U

2(V

)

1

for “many” h ∈ V , where by “many” we mean “a proportion of 1”.

Applying the U

2

inverse theorem, we conclude that for many h, that there

exists a linear polynomial φh : V → F (which we may as well take to be

classical) such that

|Δhf, e(φh)

L2(V

)| 1.