46 1. Higher order Fourier analysis
for any cyclic group Z/N Z and any subset A of that group (analogues of
this identity also exist for other finite abelian groups, and to a lesser extent
to non-abelian groups also, although that is not the focus of my current
As it turns out, linear Fourier analysis is not able to discern higher
order patterns, such as arithmetic progressions of length four; we give some
demonstrations of this below the fold, taking advantage of the polynomial
recurrence theory from Section 1.1.
The main objective of this text is to introduce the (still nascent) the-
ory of higher order Fourier analysis, which is capable of studying higher
order patterns. The full theory is still rather complicated (at least, at our
present level of understanding). However, one aspect of the theory is rel-
atively simple, namely that we can largely reduce the study of arbitrary
additive patterns to the study of a single type of additive pattern, namely
the parallelopipeds
(1.18) (x + ω1h1 + · · · + ωdhd)ω1,...,ωd∈{0,1}.
Thus for instance, for d = 1 one has the line segments
(1.19) x, x + h1;
for d = 2 one has the parallelograms
(1.20) x, x +
h1,x + h2,x + h1 + h2;
for d = 3 one has the parallelopipeds
x, x + h1,x + h2,x + h3,x + h1 + h2,x + h1 + h3,x + h2 + h3,x + h1 + h2 + h3.
These patterns are particularly pleasant to handle, thanks to the large num-
ber of symmetries available on the discrete cube {0,
For instance,
whereas establishing the presence of arbitrarily long arithmetic progressions
in dense sets is quite difficult (cf. Szemer´ edi’s theorem [Sz1975]), establish-
ing arbitrarily high-dimensional parallelopipeds is much easier:
Exercise 1.3.1. Let A [N] be such that |A| δN for some 0 δ 1.
If N is sufficiently large depending on δ, show that there exists an integer
1 h 1/δ such that |A∩(A+h)|
(Hint: Obtain upper and lower
bounds on the set {(x, y) A × A : x y x + 10/δ}.)
Exercise 1.3.2 (Hilbert cube lemma). Let A [N] be such that |A| δN
for some 0 δ 1, and let d 1 be an integer. Show that if N is sufficiently
large depending on δ, d, then A contains a parallelopiped of the form (1.18),
with 1 h1,...,hd
1 positive integers. (Hint: Use the previous exercise
and induction.) Conclude that if A Z has positive upper density, then it
contains infinitely many such parallelopipeds for each d.
Previous Page Next Page