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
available; this then forced
an approximate cocycle equation φh+k φh + T
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 difficulty is that correlation, unlike the property of being
close, is not transitive or multiplicative: just because Δhf correlates with
e(φh), and T
correlates with T
one cannot then conclude that
Δh+kf = (Δhf)T
correlates with e(φh)T
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
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
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
| 1
uniformly in h. Then there exist |V
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
| 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.
Previous Page Next Page