1.5. Inverse conjecture over finite fields 91
on d, and use Exercise 1.4.6 repeatedly to find a good initial partition into
subspaces on which φ has degree at most d 1.)
Exercise 1.5.7. Use the previous exercise to complete the proof of Theorem
1.5.4. (Hint: Mimic the density increment argument from Section 1.2.)
By using the inverse theorem as a substitute for Lemma 1.2.8, one ob-
tains the following regularity lemma, analogous to Theorem 1.2.11:
Theorem 1.5.10 (Strong arithmetic regularity lemma). Suppose that
char(F) = p d 0. Let f : V [0, 1], let ε 0, and let F :
R+

R+
be an arbitrary function. Then we can decompose f = fstr + fsml + fpsd and
find 1 M = Oε,F,d,p(1) such that
(i) (Nonnegativity) fstr,fstr + fsml take values in [0, 1], and fsml,fpsd
have mean zero;
(ii) (Structure) fstr is a function of M classical polynomials of degree
at most d;
(iii) (Smallness) fsml has an
L2(V
) norm of at most ε; and
(iv) (Pseudorandomness) One has fpsd
Ud+1(V )
1/F (M) for all α
R.
For a proof, see [Ta2007]. The argument is similar to that appear-
ing in Theorem 1.2.11, but the discrete nature of polynomials in bounded
characteristic allows one to avoid a number of technical issues regarding
measurability.
This theorem can then be used for a variety of applications in additive
combinatorics. For instance, it gives the following variant of a result of
Bergelson, Host, and Kra [BeHoKa2005]:
Proposition 1.5.11. Let p 4 k, let F = Fp, and let A
Fn
with
|A|
δ|Fn|,
and let ε 0. Then for
δ,ε,p
|Fn|
values of h
Fn,
one has
|{x
Fn
: x, x + h, . . . , x + (k 1)h A}|
(δk

ε)|Fn|.
Roughly speaking, the idea is to apply the regularity lemma to f := 1A,
discard the contribution of the fsml and fpsd errors, and then control the
structured component using the equidistribution theory from Section 1.4. A
proof of this result can be found in [Gr2007]; see also [GrTa2010b] for an
analogous result in Z/NZ. Curiously, the claim fails when 4 is replaced by
any larger number; this is essentially an observation of Ruzsa that appears
in the appendix of [BeHoKa2005].
Previous Page Next Page