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
suffice 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 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
Previous Page Next Page