1.3. Linear patterns 47
Exercise 1.3.3. Show that if q 1 is an integer, and d is sufficiently 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
:= Ex,h1,...,hd∈G
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
pairs (n, r) and we would expect each pair to have a
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 difficult 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
1 = δ that (1.23) is given
Previous Page Next Page