1.5. Inverse conjecture over finite fields 83

This should be compared with the 99% theory. There, we were able to

force Δhf close to e(φh) for most h; here, we only have the weaker statement

that Δhf correlates with e(φh) for many (not most) h. Still, we will keep

going. In the 99% theory, we were able to assume f had magnitude 1, which

made the cocycle equation Δh+kf = (Δhf)T

hΔkf

available; this then forced

an approximate cocycle equation φh+k ≈ φh + T

hφk

for most h, k (indeed,

we were able to use this trick to upgrade “most” to “all”).

This doesn’t quite work in the 1% case. First, f need not have mag-

nitude exactly equal to 1. This is not a terribly serious problem, but the

more important diﬃculty is that correlation, unlike the property of being

close, is not transitive or multiplicative: just because Δhf correlates with

e(φh), and T

hΔkf

correlates with T

he(φk),

one cannot then conclude that

Δh+kf = (Δhf)T

hΔkf

correlates with e(φh)T

he(φk);

and even if one had

this, and if Δh+kf correlated with e(φh+k), one could not conclude that

e(φh+k) correlated with e(φh)T

he(φk).

Despite all these obstacles, it is still possible to extract something re-

sembling a cocycle equation for the φh, by means of the Cauchy-Schwarz

inequality. Indeed, we have the following remarkable observation of Gowers

[Go1998]:

Lemma 1.5.7. Let V be a finite additive group, and let f : V → C be a

function, bounded by 1. Let H ⊂ V be a subset with |H| |V |, and suppose

that for each h ∈ H, suppose that we have a function χh : V → C bounded

by 1, such that

|Δhf, χh

L2(V

)

| 1

uniformly in h. Then there exist |V

|3

quadruples h1,h2,h3,h4 ∈ H with

h1 + h2 = h3 + h4 such that

|Ex∈V χh1 (x)χh2 (x + h1 − h4)χh3 (x)χh4 (x + h1 − h4)| 1

uniformly among the quadruples.

We shall refer to quadruples (h1,h2,h3,h4) obeying the relation h1+h2 =

h3 + h4 as additive quadruples.

Proof. We extend χh to be zero when h lies outside of H. Then we have

|Eh∈V θh Δhf, χh

L2(V

)

| 1

and some complex numbers θh bounded in magnitude by one. We rearrange

this as

|Ex,y∈V f(y)f(x)θy−xχy−x(x)| 1.