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

has

|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)) −

1

δ

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

pth

root of unity to

1

δ

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.