1.3. Linear patterns 49

The above exercises show that a Fourier-pseudorandom set can have

a four-term progression count (1.23) significantly larger than

δ4N.

One

can also make the count significantly smaller than

δ4N

(an observation of

Gowers, discussed at [Wo]), but this requires more work.

Exercise 1.3.6. Let 0 δ 1. Show that there exists a function f :

T2

→

[0, 1] with

T

f(x, y) dy = δ for all x ∈ T, such that the expression

(1.24)

V

f(x1,y1) . . . f(x4,y4)

is strictly less than

δ4,

where V ≤

(T2)4

is the subspace of quadruplets

((x1,y1),..., (x4,y4)) such that x1,...,x4 is in arithmetic progression (i.e.,

xi = x + ir for some x, r ∈ T) and the y1,...,y4 obey the constraint

y1 − 3y2 + 3y3 − y4 = 0.

(Hint: Take f of the form

f(x, y) := δ + ε(f1(x) cos(2πy) + f3(x) cos(6πy))

where ε 0 is a small number, and f1,f3 are carefully chosen to make the

ε2

term in (1.24) negative.)

Exercise 1.3.7. Show that there exists an absolute constant c 0 such

that for all suﬃciently small δ 0 and suﬃciently large N (depending on

δ) and a set A ⊂ [N] with |A| ≥ δN, such that (1.23) with k = 4 is less

than

δ4+cN 2.

(Hint: Take δ ∼

2−m

for some m ≥ 1, and let A be a random

subset of [N] with each element n of [N] lying in A with an independent

probability of

m

j=1

f(αjn mod

1,αjn2

mod 1),

where f is the function in the previous exercise (with δ =1/2), and α1,...,αm

are real numbers which are linearly independent over Z modulo 1.)

1.3.2. The 100% case. Now we consider the question of counting more

general linear (or aﬃne) patterns than arithmetic progressions. A reasonably

general setting is to count patterns of the form

Ψ(x) := (ψ1(x),...,ψt(x))

in a subset A of a finite abelian group G (e.g. a cyclic group G = Z/NZ),

where x =

(x1,...,xd) ∈ Gd, and the ψ1,...,ψt : Gd → G are aﬃne-linear

forms

ψi(x1,...,xd) = ci +

d

j=1

ci,jxj

for some fixed integers ci,ci,j ∈ Z. To avoid degeneracies, we will assume

that all the ψi are surjective (or equilently, that the ci,1,...,ci,d do not have