1.4. Equidistribution in finite fields 59

The main utility for the Gowers norms in this subject comes from the

fact that they control many other expressions of interest. Here is a basic

example:

Exercise 1.3.22. Let f : G → C be a function, and for each 1 ≤ i ≤

s + 1, let gi :

Gs+1

→ C be a function bounded in magnitude by 1 which

is independent of the

ith

coordinate of

Gs+1.

Let a1,...,as+1 be non-zero

integers, and suppose that the characteristic of G exceeds the magnitude of

any of the ai. Show that

|Ex1,...,xs+1∈Gf(a1x1 + · · · + as+1xs+1)

s+1

i=1

gi(x1,...,xs+1)|

≤ f

Us+1(G)

.

(Hint: Induct on s and use (1.33) and the Cauchy-Schwarz inequality.)

This gives us an analogue of Exercise 1.3.15:

Exercise 1.3.23 (Generalised von Neumann inequality). Let Ψ=(ψ1,...,ψt)

be a collection of aﬃne-linear forms ψi :

Gd

→ G with Cauchy-Schwarz com-

plexity s. If the characteristic of G is suﬃciently large depending on the

linear coeﬃcients of ψ1,...,ψt, show that one has the bound

|ΛΨ(f1,...,ft)| ≤ inf

1≤i≤t

fi

Us+1(G)

whenever f1,...,ft : G → C are bounded in magnitude by one.

Conclude, in particular, that if A is a subset of G with |A| = δ|G|, then

ΛΨ(1A,..., 1A) =

δt

+ Ot( 1A − δ Us+1(G)).

From the above inequality, we see that if A has some positive den-

sity δ 0 but has much fewer than

δtN d/2

(say) patterns of the form

ψ1(x),...,ψt(x) with x ∈

Gd,

then we have

1A − δ

Us+1(G) t,δ

1.

This is the initial motivation for studying inverse theorems for the Gowers

norms, which give necessary conditions for a (bounded) function to have

large U

s+1(G)

norm. This will be a focus of subsequent sections.

1.4. Equidistribution of polynomials over finite fields

In the previous sections, we have focused mostly on the equidistribution or

linear patterns on a subset of the integers Z, and in particular on intervals

[N]. The integers are of course a very important domain to study in addi-

tive combinatorics; but there are also other fundamental model examples of

domains to study. One of these is that of a vector space V over a finite field

F = Fp of prime order. Such domains are of interest in computer science