56 1. Higher order Fourier analysis
vectors vk ∈
for each 1 ≤ k ≤ s + 1 such that
ψ does not annihilate vk,
but all the
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 :
→ 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 :
→ G to be the
largest s such that the powers
→ Q are linearly independent
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).