1.3. Linear patterns 57
This phenomenon extends beyond the “100% world” of exact equalities.
For any f : G → C and d ≥ 1, we define the Gowers uniformity norm
f
Ud(G)
by the formula
(1.32) f
Ud(G)
:= (Eh1,...,hd,x∈GΔh1 . . . Δhd
f(x))1/2d
;
note that this is equivalent to (1.22). Using the identity
Eh,x∈GΔhf(x) =
Ex∈Gf(x)2
we easily verify that the expectation in the definition of (1.32) is a non
negative real. We also have the recursive formula
(1.33) f
Ud(G)
:= (Eh∈G Δhf
2d−1
Ud−1(G)
)1/2d
for all d ≥ 1.
The U
1
norm is essentially just the mean:
(1.34) f
U 1(G)
= Ex∈Gf(x).
As such, it is actually a seminorm rather than a norm.
The U
2
norm can be computed in terms of the Fourier transform:
Exercise 1.3.18 (Fourier representation of U
2).
Define the Pontryagin dual
ˆ
G of a finite abelian group G to be the space of all homomorphisms ξ : G →
R/Z. For each function f : G → C, define the Fourier transform
ˆ:
f
ˆ
G → C
by the formula
ˆ(ξ)
f := Ex∈Gf(x)e(−ξ(x)). Establish the identity
f
U 2(G)
=
ˆ
f
4(
ˆ)
G
:= (
ξ∈
ˆ
G

ˆ(ξ)4)1/4.
f
In particular, the U
2
norm is a genuine norm (thanks to the norm prop
erties of
4(G),
and the injectivity of the Fourier transform).
For the higher Gowers norms, there is not nearly as nice a formula known
in terms of things like the Fourier transform, and it is not immediately obvi
ous that these are indeed norms. But this can be established by introducing
the more general Gowers inner product
(fω)ω∈{0,1}d
Ud(G)
:= Ex,h1,...,hd∈G
ω1,...,ωd∈{0,1}d
Cω1+···+ωd
fω1,...,ωd (x + ω1h1 + · · · + ωdhd)
for any
2dtuple
(fω)ω∈{0,1}d of functions fω : G → C, thus, in particular,
(f)ω∈{0,1}d
Ud(G)
= f
2d
Ud(G)
.
The relationship between the Gowers inner product and the Gowers unifor
mity norm is analogous to that between a Hilbert space inner product and