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(
and so from (1.26) one has the equation
φi(ψi(x)) = c
for all x ∈
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,