1.5. Inverse conjecture over finite fields 75
to the “99% inverse problem” and “1% inverse problem”. For the former,
we will soon show:
Proposition 1.5.1 (99% inverse theorem for U
d+1(V
)). Let f : V → C be
such that f
L∞(V )
and f
Ud+1(V
)
≥ 1 − ε for some ε 0. Then there
exists φ ∈ Poly≤d(V → R/Z) such that f − e(φ)
L1(V )
=
Od,F(εc),
where
c = cd 0 is a constant depending only on d.
Thus, for the Gowers norm to be almost completely saturated, one must
be very close to a polynomial. The converse assertion is easily established:
Exercise 1.5.1 (Converse to 99% inverse theorem for U
d+1(V
)). If f
L∞(V )
≤ 1 and f − e(φ)
L1(V )
≤ ε for some φ ∈ Poly≤d(V → R/Z), then
F
Ud+1(V
)
≥ 1 −
Od,F(εc),
where c = cd 0 is a constant depending
only on d.
In the 1% world, one no longer expects to be close to a polynomial.
Instead, one expects to correlate with a polynomial. Indeed, one has
Lemma 1.5.2 (Converse to the 1% inverse theorem for U
d+1(V
)). If f : V →
C and φ ∈ Poly≤d(V → R/Z) are such that f, e(φ)
L2(V
) ≥ ε, where
f, g
L2(V
)
:= Ex∈Gf(x)g(x), then f
Ud+1(V )
≥ ε.
Proof. From the definition (1.34) of the U
1
norm, the monotonicity of the
Gowers norms (Exercise 1.3.19), and the polynomial phase modulation in
variance of the Gowers norms (Exercise 1.3.21), one has
f, e(φ) = fe(−φ)
U 1(V )
≤ fe(−φ)
Ud+1(V
)
= f
Ud+1(V )
and the claim follows.
It is a diﬃcult but known fact that Lemma 1.5.2 can be reversed:
Theorem 1.5.3 (1% inverse theorem for U
d+1(V
)). Suppose that char(F)
d ≥ 0. If f : V → C is such that f
L∞(V )
≤ 1 and f
Ud+1(V )
≥ ε, then
there exists φ ∈ Poly≤d(V → R/Z) such that f, e(φ)
L2(V
)
ε,d,F
1.
This result is sometimes referred to as the inverse conjecture for the
Gowers norm (in high, but bounded, characteristic). For small d, the claim
is easy:
Exercise 1.5.2. Verify the cases d = 0, 1 of this theorem. (Hint: To verify
the d=1 case, use the Fourieranalytic identities f
U 2(V )
=(
∑
ξ∈
ˆ
V

ˆ(ξ)4)1/4
f