68 1. Higher order Fourier analysis
Applying the union bound for the
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
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 sufficiently close to a polynomial of degree d, then the mode of ∑d
+ ω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| =
+ o(1))|V |
for all r
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
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
h1,...,hD) is constrained to
the space
defined as the subspace of
consisting of all tuples
r = (rω)ω∈{0,1}D obeying the
= 0
for all faces F {0,
of dimension d, where |ω| := ω1 + · · · + ωD is the
sign of ω.
constraints are of course vacuous if D d.
Previous Page Next Page