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 sufficiently small δ 0 and sufficiently 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 affine) 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 affine-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
Previous Page Next Page