66 1. Higher order Fourier analysis
Theorem 1.4.4. Let P : V F be a limit classical polynomial. If P is
biased, then P is low rank.
In particular, from the Weyl criterion, we see that if P is not equidis-
tributed, then P is of low rank.
In the high characteristic case pd, this claim was shown in [GrTa2009];
the generalisation to the low characteristic case p d was carried out in
[KaLo2008]. The statement is phrased in the language of ultrafilters, but
it has an equivalent finitary analogue:
Exercise 1.4.15. Show that Theorem 1.4.4 is equivalent to the claim that
for every d 1 and δ 0, and every classical polynomial P : V F of de-
gree at most d on a finite-dimensional vector space with |Ex∈V e(P (x))| δ,
that P can be expressed as a function of at most Oδ,d(1) classical polynomials
of degree at most d 1.
The proof of Theorem 1.4.4 is a little lengthy. It splits up into two pieces.
We say that a limit function P : V F (not necessarily a polynomial) is
of order d if it can be expressed as a function of a bounded number
of polynomials of degree less than d. Our task is thus to show that every
polynomial of degree d which is biased, is of order d. We first get within an
epsilon of this goal, using an argument of Bogdanov and Viola [BoVi2010]:
Lemma 1.4.5 (Bogdanov-Viola lemma). Let P : V F be a limit polyno-
mial of degree d which is biased, and let ε 0 be standard. Then one can
find a limit function Q: V F of order d such that |{x V : P (x) =
Q(x)}| ε|V |.
Proof. Let κ 0 be a small standard number (depending on ε) to be
chosen later, let M be a large standard integer (depending on ε, κ) to be
chosen later, and let h1,...,hM be chosen uniformly at random from V . An
application of the second moment method (which we leave as an exercise)
shows that if M is large enough, then with probability at least 1 ε, one
|Em∈M e(P (x + hm)) Ex∈V e(P (x))| κ
for at least (1 ε)|V | choices of x. We can rearrange this as
|e(P (x))
Em∈M e(−∂hm P (x))| κ/δ
where δ := |Ex∈V e(P (x))|; note from hypothesis that δ 1. If we let F (x)
be the nearest
root of unity to
Em∈M e(−∂hm P (x)), then (if κ is small
enough) we conclude that e(P (x)) = F (x) for at least (1 ε)|V | choices of
x. On the other hand, F is clearly of order d, and the claim follows.
Exercise 1.4.16. Establish the claim left as an exercise in the above proof.
Previous Page Next Page