1.3. Linear patterns 47

Exercise 1.3.3. Show that if q ≥ 1 is an integer, and d is suﬃciently large

depending on q, then for any parallelopiped (1.18) in the integers Z, there

exists ω1,...,ωd ∈ {0, 1}, not all zero, such that x + h1ω1 + · · · + hdωd =

x mod q. (Hint: Pigeonhole the hi in the residue classes modulo q.) Use

this to conclude that if A is the set of all integers n such that |n − km!| ≥ m

for all integers k, m ≥ 1, then A is a set of positive upper density (and also

positive lower density) which does not contain any infinite parallelopipeds

(thus one cannot take d = ∞ in the Hilbert cube lemma).

The standard way to control the parallelogram patterns (and thus, all

other (finite complexity) linear patterns) are the Gowers uniformity norms

(1.22)

f

Ud(G)

:= Ex,h1,...,hd∈G

ω1,...,ωd∈{0,1}d

Cω1+···+ωd

f(x + ω1h1 + · · · + ωdhd)

with f : G → C a function on a finite abelian group G, and C : z → z is the

complex conjugation operator; analogues of this norm also exist for group-

like objects such as the progression [N], and also for measure-preserving

systems (where they are known as the Gowers-Host-Kra uniformity semi-

norms, see [HoKr2005] for more discussion). In this section we will focus

on the basic properties of these norms; the deepest fact about them, known

as the inverse conjecture for these norms, will be discussed in later sections.

1.3.1. Linear Fourier analysis does not control length four pro-

gressions. Let A ⊂ Z/NZ be a subset of a cyclic group Z/NZ with density

|A| = δN; we think of 0 δ ≤ 1 as being fixed, and N as being very large

or going off to infinity.

For each k ≥ 1, consider the number

(1.23) {(n, r) ∈ Z/NZ × Z/NZ : n, n + r, . . . , n + (k − 1)r ∈ A}

of k-term arithmetic progressions in A (including degenerate progressions).

Heuristically, this expression should typically be close to

δkN 2.

Since there

are N

2

pairs (n, r) and we would expect each pair to have a

δk

“probability”

that n, n+r,...,n+(k−1)r simultaneously lie in A. Indeed, using standard

probabilistic tools such as Chernoff’s inequality, it is not diﬃcult to justify

this heuristic with probability asymptotically close to 1 in the case that A

is a randomly chosen set of the given density.

Let’s see how this heuristic holds up for small values of k. For k = 0, 1, 2,

this prediction is exactly accurate (with no error term) for any set A with

cardinality δN; no randomness hypothesis of any sort is required. For k = 3,

we see from (1.17) and the observation that

ˆA(0)

1 = δ that (1.23) is given