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].