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

discussion).

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

(1.21)

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,

1}d.

For instance,

whereas establishing the presence of arbitrarily long arithmetic progressions

in dense sets is quite diﬃcult (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 suﬃciently large depending on δ, show that there exists an integer

1 ≤ h 1/δ such that |A∩(A+h)|

δ2N.

(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 suﬃciently

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.