76 1. Higher order Fourier analysis
and f
L2(V )
= (
∑
ξ∈
ˆ
V

ˆ(ξ)2)1/2,
f where
ˆ
V is the space of all homomor
phisms ξ : x → ξ · x from V to R/Z, and
ˆ(ξ)
f := Ex∈V f(x)e(−ξ · x) are the
Fourier coeﬃcients of f.)
This conjecture for larger values of d are more diﬃcult to establish.
The d = 2 case of the theorem was established in [GrTa2008]; the low
characteristic case char(F) = d = 2 was independently and simultaneously
established in [Sa2007]. The cases d 2 in the high characteristic case
was established in two stages: first, using a modification of the Furstenberg
correspondence principle in [TaZi2010], and then using a modification of
the methods of Host and Kra [HoKr2005] and Ziegler [Zi2007] to solve
that counterpart, as done in [BeTaZi2010]; an alternate proof was also
obtained in [Sz2010c]. Finally, the low characteristic case was recently
achieved in [TaZi2011].
In the high characteristic case, we saw from Section 1.4 that one could
replace the space of nonclassical polynomials Poly≤d(V → R/Z) in the
above conjecture with the essentially equivalent space of classical polyno
mials Poly≤d(V → F). However, as we shall see below, this turns out not
to be the case in certain low characteristic cases (a fact first observed in
[LoMeSa2008], [GrTa2009]), for instance, if char(F) = 2 and d ≥ 3; this
is ultimately due to the existence in those cases of nonclassical polynomials
which exhibit no significant correlation with classical polynomials of equal
or lesser degree. This distinction between classical and nonclassical poly
nomials appears to be a rather nontrivial obstruction to understanding the
low characteristic setting; it may be necessary to obtain a more complete
theory of nonclassical polynomials in order to fully settle this issue.
The inverse conjecture has a number of consequences. For instance, it
can be used to establish the analogue of Szemer´ edi’s theorem in this setting:
Theorem 1.5.4 (Szemer´ edi’s theorem for finite fields). Let F = Fp be
a finite field, let δ 0, and let A ⊂
Fn
be such that A ≥
δFn.
If
n is suﬃciently large depending on p, δ, then A contains an (aﬃne) line
{x, x + r, . . . , x + (p − 1)r} for some x, r ∈
Fn
with r = 0.
Exercise 1.5.3. Use Theorem 1.5.4 to establish the following generalisation:
with the notation as above, if k ≥ 1 and n is suﬃciently large depending on
p, δ, then A contains an aﬃne kdimensional subspace.
We will prove this theorem in two different ways, one using a density
increment method, and the other using an energy increment method. We
discuss some other applications below the fold.
1.5.1. The 99% inverse theorem. We now prove Proposition 1.5.1. Re
sults of this type for general d appear in [AlKaKrLiRo2003] (see also