48 1. Higher order Fourier analysis
by the formula
N
2

⎝δ3
+
ξ∈Z/NZ:ξ=0
ˆA(ξ)2ˆA(−2ξ)⎠
1 1

.
Let us informally say that A is Fourier-pseudorandom if one has
sup
ξ∈Z/NZ:ξ=0
|ˆA(ξ)|
1 = o(1)
where o(1) is a quantity that goes to zero as N ∞. Then from applying
Plancherel’s formula and Cauchy-Schwarz as in the previous sections, we see
that the number of three-term arithmetic progressions is
N
2(δ3
+ o(1)).
Thus we see that the Fourier-pseudorandomness hypothesis allows us to
count three-term arithmetic progressions almost exactly.
On the other hand, without the Fourier-pseudorandomness hypothesis,
the count (1.23) can be significantly different from
δ3N 2.
For instance, if A
is an interval A = [δN], then it is not hard to see that (1.23) is comparable
to
δ2N 2
rather than
δ3N 2;
the point is that with a set as structured as an
interval, once n and n + r lie in A, there is already a very strong chance
that n + 2r lies in A also. In the other direction, a construction of Behrend
(mentioned in the previous sections) shows the quantity (1.23) can in fact
dip below
δCN 2
for any fixed C (and in fact one can be as small as
δc log
1
δ
N
2
for some absolute constant c 0).
Now we consider the k = 4 case of (1.23), which counts four-term pro-
gressions. Here, it turns out that Fourier-pseudorandomness is insufficient;
it is possible for the quantity (1.23) to be significantly larger or smaller than
δ4N 2
even if A is pseudorandom, as was observed by Gowers [Go1998] (with
a closely related observation in the context of ergodic theory by Furstenberg
[Fu1990]).
Exercise 1.3.4. Let α be an irrational real number, let 0 δ 1, and let
A := {n [N] : 0
{αn2}
δ}. Show that A is Fourier-pseudorandom
(keeping α and δ fixed and letting N ∞). (Hint: One can use Exercise
1.1.21 to show that sums of the form
En∈[N]e(kαn2)e(ξn)
cannot be large.)
Exercise 1.3.5. Continuing the previous exercise, show that the expression
(1.23) for k = 4 is equal to
(cδ3
+ o(1))N
2
as N ∞, for some absolute
constant c 0, if δ 0 is sufficiently small. (Hint: First show, using
the machinery in Section 1.1, that the two-dimensional sequence (n, r)
(αn2,α(n
+
r)2,α(n
+
2r)2,α(n
+
3r)2)
mod
Z4
is asymptotically equidis-
tributed in the torus {(x1,x2,x3,x4)
T4
: x1 3x2 + 3x3 x4 = 0}.)
Previous Page Next Page