56 1. Higher order Fourier analysis

vectors vk ∈

Qd

for each 1 ≤ k ≤ s + 1 such that

˙i

ψ does not annihilate vk,

but all the

˙

ψ

j

from Ak do. If we then set

Li(y1,...,ys+1,z1,...,zd) := (z1,...,zd) + y1v1 + · · · + ys+1vs+1,

then we obtain the claim.

Exercise 1.3.15. Let ψ1,...,ψt :

Gd

→ G be a system of aﬃne-linear forms

with Cauchy-Schwarz complexity at most s, and suppose that the equation

(1.27) holds for some finite abelian group G and some φ1,...,φt : G →

R/Z. Suppose also that the characteristic of G is suﬃciently large depending

on the coeﬃcients of ψ1,...,ψt. Conclude that all of the φ1,...,φt are

polynomials of degree ≤ t.

It turns out that this result is not quite best possible. Define the true

complexity of a system of aﬃne-linear forms ψ1,...,ψt :

Gd

→ G to be the

largest s such that the powers

˙s,...,

ψ

1

˙s

ψ

t

:

Qd

→ Q are linearly independent

over Q.

Exercise 1.3.16. Show that the true complexity is always less than or equal

to the Cauchy-Schwarz complexity, and give an example to show that strict

inequality can occur. Also, show that the true complexity is finite if and

only if the Cauchy-Schwarz complexity is finite.

Exercise 1.3.17. Show that Exercise 1.3.15 continues to hold if Cauchy-

Schwarz complexity is replaced by true complexity. (Hint: First understand

the cyclic case G = Z/NZ, and use Exercise 1.3.15 to reduce to the case

when all the φi are polynomials of bounded degree. The main point is to

use a “Lefschetz principle” to lift statements in Z/NZ to a characteristic

zero field such as Q.) Show that the true complexity cannot be replaced by

any smaller quantity.

See [GoWo2010] for further discussion of the relationship between

Cauchy-Schwarz complexity and true complexity.

1.3.3. The Gowers uniformity norms. In the previous section, we saw

that equality in the trivial inequality (1.25) only occurred when the functions

f1,...,ft were of the form fi = e(φi) for some polynomials φi of degree at

most s, where s was the true complexity (or Cauchy-Schwarz complexity) of

the system ψ1,...,ψt. Another way of phrasing this latter fact is that one

has the identity

Δh1 . . . Δhs+1 fi(x) = 1

for all h1,...,hs+1,x ∈ G, where Δh is the multiplicative derivative

Δhf(x) := f(x + h)f(x).