1.3. Linear patterns 51

and wish to classify the functions f1,...,ft as best we can. We will normalise

all the norms on the right-hand side to be one, thus |fi(x)| ≤ 1 for all x ∈ G

and i = 1,...,t, and

(1.26) |ΛΨ(f1,...,ft)| = 1.

By the triangle inequality, we conclude that

ΛΨ(|f1|,..., |ft|) ≥ 1.

On the other hand, we have the crude bound

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

Thus equality occurs, which (by the surjectivity hypothesis on all the ψi)

shows that |fi(x)| = 1 for all x ∈ G and i = 1,...,t. Thus we may write

fi(x) = e(φi(x)) for some phase functions φi : G → R/Z. We then have

ΛΨ(f1,...,ft) = Ex∈Gd e(

t

i=1

φi(ψi(x)))

and so from (1.26) one has the equation

(1.27)

t

i=1

φi(ψi(x)) = c

for all x ∈

Gd

and some constant c.

So the problem now reduces to the algebraic problem of solving func-

tional equations such as (1.27). To illustrate this type of problem, let us

consider a simple case when d = 2,t = 3 and

ψ1(x, y) = x; ψ2(x, y) = y; ψ3(x, y) = x + y

in which case we are trying to understand solutions φ1,φ2,φ3 : G → R/Z to

the functional equation

(1.28) φ1(x) + φ2(y) + φ3(x + y) = c.

This equation involves three unknown functions φ1,φ2,φ3. But we can elim-

inate two of the functions by taking discrete derivatives. To motivate this

idea, let us temporarily assume that G is the real line R rather than a

finite group, and that the functions φ1,φ2,φ3 are smooth. If we then ap-

ply the partial derivative operator ∂x to the above functional equation, one

eliminates φ2 and obtains

φ1(x) + φ3(x + y) = 0;

applying ∂y then eliminates φ1 and leaves us with

φ3(x + y) = 0,