1.4. Equidistribution in finite fields 71

(Hint: One can proceed by applying Proposition 1.4.8 with D replaced by

a larger dimension, such as 2D; details can be found in [GrTa2009].)

We can now establish Proposition 1.4.6 in the case where the R1,...,Rm

are independent modulo low rank errors. Let r0 ∈

Fm

and x ∈ Sr0 . It will

suﬃce to show that P (x) does not depend on x as long as x stays inside r0.

Call an atom Sr good if P and Q agree for at least 1−

√

ε of the

of Sr; by Markov’s inequality (and (1.38)) we see that at least 1 −

√elements

ε + o(1)

of the atoms are good. From this and an easy counting argument we can

find an element r = (rω)ω∈{0,1}d in

Σ[d]

with the specified value of r0, such

that rω is good for every {0,

1}d\{0}.

Fix r. Now consider all pinned cubes (x+h1ω1 +···+hdωd)ω1,...,ωd∈{0,1}d

with x + h1ω1 + · · · + hdωd ∈ Srω for all ω ∈ {0,

1}d\{0}.

By (1.40), the

number of such cubes is (

pm

|Σ[d]|

+ o(1))|V

|d.

On the other hand, by Exercise

1.4.17, the total number of such cubes for which

P (x + h1ω1 + · · · + hdωd) = Q(x + h1ω1 + · · · + hdωd)

for some ω ∈ {0,

1}d\{0}

is o(|V

|d−1).

We conclude that there exists a

pinned cube for which

P (x + h1ω1 + · · · + hdωd) = Q(x + h1ω1 + · · · + hdωd)

for all ω ∈ {0,

1}d\{0},

and, in particular, (1.37) holds. However, as Q is

constant on each of the Sr, we see that the right-hand side of (1.37) does

not depend on x, and so the same holds true for the left-hand side.

This completes the proof of Proposition 1.4.6 in the independent case.

In the general case, one reduces to a (slight generalisation of) this case by

the following regularity lemma:

Lemma 1.4.9 (Regularity lemma). Let R1,...,Rm be a bounded number

of limit classical polynomials of degree ≤ d − 1. Then there exists a limit

classical bounded number of polynomials Sd ,1,...,Sd

,m

d

of degree ≤ d for

each 1 ≤ d ≤ d − 1, such that each R1,...,Rm is a function of the Sd

,i

for

1 ≤ d ≤ d and 1 ≤ i ≤ md , and such that for each d , the Sd ,1,...,Sd

,m

d

are independent modulo low rank polynomials of degree d .

Proof. We induct on d. The claim is vacuously true for d = 1, so suppose

that d 1 and that the claim has already been proven for d − 1.

Let Polyd−1 be the space of limit classical polynomials of degree ≤

d − 1, and let Polyd−1

0

be the subspace of low rank limit classical poly-

nomials. Working in the quotient space Polyd−1 / Polyd−1,

0

we see that