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 insuﬃcient;

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 suﬃciently 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}.)