68 1. Higher order Fourier analysis

2−d−2.

Applying the union bound for the

2d+1

− 1

2d+1

values of ω under

consideration, we conclude that (1.37) happens more than half the time, and

the claim follows.

Note that the above argument in fact shows that the mode is attained

for at least 1 −

2d+1ε

of the choices of h1,...,hd+1.

In view of this lemma, the goal is now to show that if Q is of order

and is suﬃciently close to a polynomial of degree d, then the mode of ∑d

ω∈{0,1}d+1\{0}

(−1)|ω|−1Q(x

+ ω1h1 + · · · + ωd+1hd+1) is also of order d.

By hypothesis, we have Q = F (R1,...,Rm) for some standard m and

some polynomials R1,...,Rm of degree d − 1. To motivate the general

argument, let us first work in an easy model case, in which the R1,...,Rm

are polynomials of degree d − 1 that are linearly independent modulo low

rank (i.e., order d − 2) errors, i.e., no non-trivial linear combination of

R1,...,Rm over F is of low rank. This is not the most general case, but is

somewhat simpler and will serve to illustrate the main ideas.

The linear independence, combined with the inductive hypothesis, im-

plies that any non-trivial linear combination of R1,...,Rm is unbiased.

From this and Fourier analysis, we see that R := (R1,...,Rm) is jointly

equidistributed, thus, in particular, we have

(1.38) |Sr| =

(p−m

+ o(1))|V |

for all r ∈

Fm,

where Sr := {x ∈ V : R(x) = r}.

In fact, we have a much stronger equidistribution property than this;

not only do we understand the distribution of R(x) for a single x, but more

generally we can control the distribution of an entire parallelopiped

R[D](x,

h1,...,hD) := (R(x + ω1h1 + · · · + ωDhD))ω1,...,ωD∈{0,1}

for any standard integer D ≥ 0. Because all the components R are poly-

nomials of degree d − 1, the quantity

R[D](x,

h1,...,hD) is constrained to

the space

Σ[D],

defined as the subspace of

(Fm)2D

consisting of all tuples

r = (rω)ω∈{0,1}D obeying the

constraints12

ω∈F

(−1)|ω|rω

= 0

for all faces F ⊂ {0,

1}D

of dimension d, where |ω| := ω1 + · · · + ωD is the

sign of ω.

12These

constraints are of course vacuous if D d.